The effectiveness of using the SBOM search algorithm in Intrusion Detection Systems

Abstract

Skadevare utgjør en alvorlig trussel overfor enkeltpersoner, selskaper og myn- digheter. Å kunne søke etter skadevare i sanntid er en av hovedoppgavene til et Intrusion Detection System (IDS) for å forhindre at skadevaren forårsaker skade på systemet. Med en økende mengde data og flere omfattende høyhastighets- nettverk, blir evnen til å hurtig kunne søke gjennom data en viktig faktor.

Ved å endre hvilken søkealgoritme som brukes i en IDS kan man gjøre den raskere til å søke gjennom data. Hendelser de siste to tiårene har vist at det er mu- lig å angripe en IDS for å sette den ut av spill før videre penetrering av systemet som den beskytter. På bakgrunn av dette må det settes krav til søkealgoritmen som brukes i en IDS. Søkealgoritmen må, i tillegg til å være rask, også være motstands- dyktig overfor algoritmiske angrep, såkalte ”algorithmic complexity attacks”.

Denne masteroppgaven tar en nærmere kikk på den svært raske søkealgor- itmen ”Set Backward Oracle Matching algorithm” (SBOM) og hvor effektiv den kan være brukt i en IDS. Resultatene viser at den er opp til 6 ganger så rask som Aho-Corasick søkealgoritmen som ofte blir benyttet i dag. Resultatene viser også at det er mulig å gjennomføre et vellykket algoritmisk angrep mot SBOM algor- itmen. Videre viser resultatene at hvis SBOM algoritmen implementeres sammen med Aho-Corasick algoritmen er det mulig å utnytte hastigheten til SBOM søkeal- goritmen på en svært god måte og samtidig gjøre den mer motstandsdyktig mot algoritmiske angrep.

Malware poses a severe threat to people, companies, and governments. To search for malware in real-time is the main task of an Intrusion Detection System (IDS) to be able to prevent the malware from causing any damage to the system. With an increasing amount of data and more extensive high-speed networks, the IDS’ ability to search through data fast becomes more important.

A way to make the IDS faster is to change the search algorithm. Events during the last two decades have also shown that it is possible to launch attacks against the IDS to neutralize it before penetrating the system it protects. Hence, a search algorithm used in an IDS has to be both fast and resilient to possible algorithmic complexity attacks.

This thesis takes a closer look at the very fast Set Backward Oracle Matching (SBOM) search algorithm and its effectiveness in an IDS. The results show that it is up to 6 times faster than the commonly used Aho-Corasick search algorithm. The results also show that it is possible to launch a successful algorithmic complexity attack against an IDS that uses the SBOM search algorithm. Further on, the results show that if implemented with the Aho-Corasick search algorithm, it is possible to get full advantage of the SBOM search algorithm’s speed while making it more resilient to algorithmic complexity attacks.