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.