A method for approximate matching in intrusion detection systems using an extended bit-parallel algorithm

Abstract

Flere av dagens innbruddsdeteksjonssystemer baserer seg på eksakt mønstergjenkjenning for å oppdage trusler. Algoritmer som Aho-Corasick er foretrukne siden de prosesserer flere mønstre om gangen, noe som gjør dem i stand til å håndtere store mengder med signaturer på en effektiv måte. Men dagens tilnærming oppmuntrer til økt størrelse og kompleksitet på signaturdatabasen, og vil kun ha mulighet til å detektere kjente og eksplisitt spesifiserte mønstre. Denne oppgaven foreslår å inkludere et steg for omtrentlig mønstergjenkjenning etter steget som prosesserer flere mønstre samtidig slik at deteksjonsmotoren kan kombinere de to stegene ved behov, med et mål om at kompleksiteten og antallet mønstre i det første steget reduseres samtidig som man legger til rette for å kunne oppdage nye variasjoner av kjente angrep i steg to. En utvidelse av nåværende algoritmer som vil åpne for muligheten til å blande eksakt og omtrentlig søk blir beskrevet, og kjøretid og deteksjonskvalitet måles for nye og gamle metoder gjennom kontrollerte eksperimenter. Oppgavens hovedfunn er et bruksområde for omtrentlig søk i signaturbaserte innbruddsdeteksjonssystemer, i tillegg til en forbedret implementasjonsmetode som fører til færre falske positive alarmer uten å utsette systemet for uønsket tidskompleksitet. Vår konklusjon er at omtrentlig mønstergjennkjenning fortjener en plass i deteksjonsverktøykassen, og at vår metode på nåværende tidspunkt er den beste løsningen for å nå gjeldende ytelseskriterier.

Many of today's intrusion detection systems rely on exact pattern matching to be able to detect threats. Multi-pattern search algorithms like Aho-Corasick are a preferred choice because they are able to process large amounts of signatures efficiently, but the current approach encourages the signature database's growth in size and complexity, and only allows for known and explicitly specified patterns to be detected. This thesis proposes the addition of a stage for approximate pattern matching after the multi-pattern stage so that the detection engine can combine the two stages where appropriate, with the goal being to reduce the amount and complexity of signatures in the first stage while facilitating for the detection of new variations of known attacks in stage two. An extension to current algorithms that will allow for a mix of exact and approximate search is described, and execution time and detection quality is measured for new and old methods through controlled experiments. The thesis' main findings is a use-case for approximate matching in signature-based intrusion detection systems, as well as an improved implementation method that leads to fewer false positive alerts without subjecting the system to computational overhead. Our conclusion is that approximate matching deserves a place in the intrusion detection toolbox, and that our method is the current optimal way for meeting performance criteria.