Approximate search in misuse detection-based intrusion detection by using the q-gram distance

Abstract

NORSK: Innbruddsdeteksjonssystemer har i de siste årene blitt en ofte brukt og viktig komponent i perimetersikringen for mange organisasjoner. Denne typen systemer bruker ofte en signaturbasert deteksjonsmodell for å oppdage spor etter kjente angrep som er lagret i en signaturdatabase. Ved å benytte feil-tolerant tilnærmet søk i innbruddsdeteksjonssystemet kan også ukjente angrep bli oppdaget hvis disse angrepene ligner nok på eksisterende angrep. Dette er spesielt effektivt i de tilfeller hvor det ukjente angrepet er basert på eksisterende kjente angrep. Forøvrig, ettersom mengden med angrep vokser så vil også tiden som er nødvendig for å søke gjennom signaturdatabasen øke. Feil-tolerant søk vil også legge til kompleksitet til søket og kan derfor også ytterligere øke tiden som er nødvendig for å søke gjennom signaturdatabasen. Tilnærmet søk benytter ofte et avstandsmål i sin mønstergjenkjenning for å finne avstanden mellom inndata og signaturene i databasen. Hvis avstanden er under en forhåndsdefinert terskel vil inndata og signaturen bli beregnet som like. Tidligere forskning har benyttet såkalt “edit distance” og “constrained edit distance” som et avstandsmål for tilnærmet søk, men begge disse avstandsmålene har høy tidskompleksitet. I denne masteroppgaven ser vi på et raskere alternativ for å måle avstand i tilnærmet søk for signaturbasert innbruddsdeteksjon kalt “q-gram distance”. Som avstandsmål er q-gram distance kjent for å kunne estimere vanlig edit distance for enkelte bruksområder. Vi tar en titt på hvordan q-gram distance kan bli implementert i innbruddsdeteksjon som et avstandsmål for tilnærmet søk. Vi foreslår en to stegs metode hvor q-gram distance blir benyttet i tilnærmet søk i innbruddsdeteksjon, og sammenligner ytelsen og nøyaktigheten til denne i forhold til vanlig edit distance og constrained edit distance som avstandsmål i et tilsvarende søk. I disse sammenligningene vil vi benytte regler fra innbruddsdeteksjonssystemet SNORT som vår signaturdatabase. Resultater fra våre eksperimenter tyder på at vanlig q-gram distance kan bli brukt som et alternativ til constrained edit distance, og at den med god margin kan utkonkurrere både vanlig edit distance og constrained edit distance med tanke på ytelse for innbruddsdeteksjon.

ENGELSK: Intrusion detection systems have in the last years become a commonly used and important component in the perimeter security for many organizations. Such systems often use a misuse detection-based model for detection of known attack patterns from a finite signature database. By applying fault-tolerant approximate search to the IDS, unknown attacks may also be detected if they are similar enough to known attacks. This is especially efficient if the unknown attack is based on existing, known, attack. However, as the amount of attacks increases, so does the time needed to search through the signature database. Fault-tolerant search also adds complexity to the search and may therefore increase the time needed to search the signature database even further. Approximate search often uses a distance measure in its pattern matching for finding the distance between the input data and the signatures in the database. If the distance is below a pre-defined threshold, the input data and the signature is considered a match. Previous research have used the edit distance or the constrained edit distance as a distance measure for approximate search. However, both of these have a high time complexity. In this thesis we look at a fast alternative for measuring the distance in approximate search for misuse detection-based intrusion detection, called the q-gram distance. The q-gram distance is known to estimate the edit distance well for some applications. We look at how the q-gram distance can be implemented in intrusion detection as a distance measure in approximate search. We suggest a two-stage approximate search method in which the q-gram distance can be applied to approximate search in intrusion detection, and compare its data reduction, performance and accuracy against the ordinary edit distance and the constrained edit distance using SNORT rules as test data. Experimental results indicate that the q-gram distance can be used as an alternative to the constrained edit distance, and by far outperform both the ordinary edit distance and the constrained edit distance in terms of performance for intrusion detection.