dc.contributor.advisor | Petrović, Slobodan | |
dc.contributor.author | Mokkelbost, Bodil Åberg | |
dc.date.accessioned | 2022-03-19T18:19:23Z | |
dc.date.available | 2022-03-19T18:19:23Z | |
dc.date.issued | 2021 | |
dc.identifier | no.ntnu:inspera:95563329:35978701 | |
dc.identifier.uri | https://hdl.handle.net/11250/2986281 | |
dc.description.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. | |
dc.description.abstract | 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. | |
dc.language | eng | |
dc.publisher | NTNU | |
dc.title | The effectiveness of using the SBOM
search algorithm in Intrusion
Detection Systems | |
dc.type | Master thesis | |