Kernighan-Lin heuristic in an IDS

Abstract

NORSK: Organisasjoner og bedrifter i dag krever å være online og koblet til Internet. Dette stiller høye sikkerhetskrav. I perimetersikring for organisasjonen er Intrusion Detection System, IDS, et viktig element. Men dette er en ung teknologi som på grunn av manglende forståelse og kunnskap ikke blir benyttet i særlig grad. Denne Masteroppgaven tar for seg en forklaring av IDS og kort forklaring om de forskjellige måtene som en IDS opererer på. Intrusion Detection Systemer har enda å vise sitt fulle potensiale som et forsvarsverk. En veldig sterk egenskap er at en IDS kan oppdage angrep før de er kjent, ved at den sammenligner normal trafikk mot unormal trafikk. Desverre har denne typen IDS en tendens til å generere mange falske advarsler. Denne Master0ppgaven skal undersøke om det er mulig å forbedre feilraten i en IDS ved å benytte Kernighan-Lin heuristic og sammenligne de resultatene med k-means heuristic. Kernighan-Lin er ikke benyttet i en IDS, mens k-means har allerede blitt implementert og testet. Testing av de to algoritmene, Kernighan-Lin og k-means viste at Kernighan-Lin har et godt potensiale i en IDS. Den har noen begrensninger men disse kan løses. Styrken til Kernighan-Lin ligger i at den er veldig presis til å identifisere angrep. Forsøkene gjort i denne Masteroppgaven viser at Kernighan-Lin er veldig presis, men den har også en fordel i forhold til k-means testen.

ENGELSK: With the need for organizations to stay online and connected to the World Wide Web, the need for security measures is stronger than ever. One important security feature is the utilization of an Intrusion Detection System, IDS. But as this is a relatively new technology it is still hazed in a grey cloud of confuse and misunderstanding. This thesis will focus on giving the reader an insight of IDS and methods used. The Intrusion Detection Systems of today have yet to prove their full potential. An especially strong feature of an IDS is to alert currently unknown attacks/misuse as it detects traffic that is outside the normal boundaries. Unfortunately this kind of IDS have a tendency to produce a high number of alerts on normal traffic as well. This thesis will investigate if the Kernighan-Lin algorithm may be used in an Intrusion Detection System and compare the results with the k-means algorithm. The Kernighan-Lin has not been used in an IDS, but k-means have already been implemented and tested. The study of Kernighan-Lin heuristic will hopefully reveal if it can perform better than the k-means regarding accuracy without a significant loss in speed. The testing of the two algorithms, Kernighan-Lin and k-means, shows that Kernighan-Lin has a good potential as a classifier in an IDS. It does have some limitations, but they can be solved or circumvented. The true strength of Kernighan-Lin was the accuracy it provided. It managed to correctly identify each attack. However the tests done do favor the Kernighan-Lin in some degree.