Efficient representation of data in intrusion detection systems

Abstract

Bedrifter er veldig avhengige av deres IT-systemer, som kan være store og komplekse å sikre. Nettverks-deteksjonssystemer (NIDS) brukes ofte til å overvåke sentrale punkter i nettverket og varsle administratorer når et mulig angrep oppdages. Signaturbasert NIDS søker etter mønstre av kjente angrep i nettverkstrafikk, hvor mengden signaturer vokser ettersom nye angrep dukker opp. Hastighet er kritisk i slike systemer for å oppdage en mulig trussel så raskt som mulig. Dermed er minne nøkkelen for å gi god ytelse, som ofte er begrenset. Effektiv representasjon av data i NIDS kan redusere mengden minne i eksisterende implementasjoner, eller muligens utvide bruken til enheter med begrenset minne, uten å påvirke ytelsen. Arbeidet i dette prosjektet ser på en måling av effektivitet, hvor effektive to av de mest brukte deteksjonssystemene er og foreslår forbedringer. To sentrale elementer blir undersøkt, nemlig en mye brukt søkealgoritme og representasjon av signaturer ved bruk av en kvantitativ metode. En teknisk analyse med kodegjennomgang presenterer oppdaterte modeller av relevante datastrukturer. Modellene blir deretter sammenlignet og analysert på et teoretisk nivå for å se om det er rom for forbedring. De foreslåtte forbedringene er basert rundt tilpasning av sentrale komponenter i kompakte datastrukturer fra tidligere forskning for å passe egenskaper og formålet med de eksisterende representasjonene. Videre så utvikles to algoritmer for å utføre operasjoner på de resulterende forbedringene. Til slutt så vil et praktisk eksperiment sammenlikne hvor effektive de foreslåtte forbedringene er, ved bruk av den utviklede formelen for å måle effektivitet og en variasjon av mye brukte signatur samlinger. Funnene gjennom oppgaven er datastrukturer som er mer effektive enn eksisterende implementasjoner.

Businesses are very dependent on their information technology (IT) systems, which can be large and complex to secure. Network intrusion detection systems (NIDS) are often used to monitor central network locations and alert administrators when a possible attack is detected. Signature based NIDS search for patterns of known attacks in network traffic, where the amount of signatures are growing as new attacks emerge. Speed is critical in such systems in order to detect the possible threat as fast as possible. Thus, memory is key in order to provide good performance, which is often limited. Efficient representation of data in NIDS can reduce the amount of required memory in existing implementations or possibly extend the usage to devices with limited memory, whilst not impacting the performance. The work in this project looks at a measure of implementation efficiency, how efficient existing implementations are in two of the most used open source intrusion detection systems (IDS) and suggests improvements. Two central elements in an IDS are investigated, namely the fast pattern matcher and representation of signatures using a quantitative method. A technical analysis with a code review presents up to date models of relevant data structures. The models are then compared and analysed on a theoretical level in order to see if there is room for improvement. The suggested improvements are based around applying and customising elements of compact data structures from previous research in order to fit characteristics and the purpose of the existing representation. Furthermore, two algorithms to perform operations on the resulting improvements are developed. In addition to the suggested improvements, a proof of concept compares the existing implementation to the alternative ones, using a developed metric for efficiency and a variation of widely used signature collections. The findings throughout the thesis are data structures which are more efficient than the existing implementations.