The effectiveness of using the SBOM search algorithm in Intrusion Detection Systems
Master thesis
Permanent lenke
https://hdl.handle.net/11250/2986281Utgivelsesdato
2021Metadata
Vis full innførselSamlinger
Sammendrag
Skadevare utgjør en alvorlig trussel overfor enkeltpersoner, selskaper og myn-digheter. Å kunne søke etter skadevare i sanntid er en av hovedoppgavene til etIntrusion Detection System (IDS) for å forhindre at skadevaren forårsaker skadepå 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 denraskere 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 systemetsom den beskytter. På bakgrunn av dette må det settes krav til søkealgoritmen sombrukes 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 denkan være brukt i en IDS. Resultatene viser at den er opp til 6 ganger så rask somAho-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 sammenmed 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 motalgoritmiske angrep. Malware poses a severe threat to people, companies, and governments. To searchfor 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. Withan 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 duringthe last two decades have also shown that it is possible to launch attacks againstthe IDS to neutralize it before penetrating the system it protects. Hence, a searchalgorithm used in an IDS has to be both fast and resilient to possible algorithmiccomplexity 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 isup to 6 times faster than the commonly used Aho-Corasick search algorithm. Theresults also show that it is possible to launch a successful algorithmic complexityattack against an IDS that uses the SBOM search algorithm. Further on, the resultsshow that if implemented with the Aho-Corasick search algorithm, it is possibleto get full advantage of the SBOM search algorithm’s speed while making it moreresilient to algorithmic complexity attacks.