Speeding Up k-Means-Clustering-Based Anomaly Detection Systems

Abstract

K-means-algoritmen er en populær grupperingsalgoritme som er mye brukt i ikke-veiledet maskinlæring. Anomalibaserte inntrengningsdeteksjonssystemer (eng: Intrusion Detection Systems, IDS) kan bruke den til å oppdage angrep på verter og nettverk i situasjoner der tradisjonelle signaturbaserte IDS ikke er effektive. På grunn av høye datahastigheter i dagens nettverk kan den originale k-means-algoritmen være for treg til bruk i IDS. I denne oppgaven ser vi på ulike måter å øke hastigheten til k-means-grupperingsbasert IDS, samt bygger en forbedret IDS på Apache Flink, en distribuert streamingplattform.

For det første kan en benytte k-means-algoritmen i forskjellige moduser som varierer i hastighet og nøyaktighet. Vi har testet offline/batch k-means og noen online versjoner. En modus som vi kaller "transforming k-means", var den raskeste modusen og hadde overraskende god nøyaktighet. For det andre finnes det tidligere foreslåtte forbedringer av k-means-algoritmen basert på trekantulikheten, som påvirker hastigheten, men få av disse forbedringene har blitt brukt i inntrengningsdeteksjon. Tre av disse forbedringene er testet i denne oppgaven. En av forbedringene, Compare-Means-algoritmen til Philips, gir en liten økning i hastighet. I denne oppgaven bruker vi også trekantulikheten i online k-means. Testene viste at vi kunne øke hastigheten litt ved å bruke idéen til Philips om å benytte sentroide-til-sentroide-avstander i "transforming k-means".

Denne oppgaven introduserer også domener som et konsept for å håndtere ikke-numeriske data i k-means-basert IDS. Et eget euklidsk plan og et par sentroider er tilordnet data som deler de samme verdiene på alle ikke-numeriske attributter. På den måten har vi formalisert før- og etterbehandlingen av data i k-means-basert IDS, samt diskutert konsekvensene. En konsekvens er at noen domener kan være ondsinnet av natur, i så fall bør en signaturbasert IDS støtte opp om vår anomalibaserte IDS.

Vi implementerte forbedringene og modusene til k-means-algoritmen på den distribuerte streamingplattformen Apache Flink. Denne oppgaven introduserer også en ny modus som kan passe godt til anomalibasert IDS. Den kombinerer "transforming k-means" sin hastighet og overraskende gode nøyaktighet, og batch k-means for å oppdatere modellen underveis. Vi foreslår effektive anomalibaserte IDS, som bruker forbedringene av k-means og forskjellige moduser, på Apache Flink. Ved å gjøre dette, forbedres effektiviteten til anomalibaserte IDS som bruker k-means-gruppering.

The k-means algorithm is a popular clustering algorithm widely used in unsupervised machine learning. Anomaly-based Intrusion Detection Systems (IDS) can use it to detect attacks on hosts and networks in situations where traditional signature-based IDS are not effective. However, due to high data rates in today's networks, the original k-means algorithm may be too slow for IDS applications. In this thesis, we look at ways to speed up k-means-clustering-based IDS and build improved IDS on the distributed streaming platform Apache Flink.

Firstly, one can operate the k-means algorithm in different modes that vary in speed and accuracy. We have tested offline/batch k-means and some online versions. A mode of operation (MoO) that we call "transforming k-means" was the fastest mode and had a surprisingly high accuracy. Secondly, improvements to the original k-means algorithm that affect the speed have earlier been proposed, yet few of these improvements have been applied in intrusion detection. Three improvements based on the triangle inequality have been tested in this thesis. One improvement, Philips' Compare-Means algorithm, provides a slight speedup. In this thesis, we also use triangle inequality in online k-means. The tests showed that we could increase speed slightly by utilising Philips' idea of comparing centroid-to-centroid distances in "transforming k-means".

This thesis also introduces domains as a concept to handle non-numeric data in k-means-based IDS. A separate Euclidean plane and a pair of centroids are assigned to data that share the same values on all non-numeric features. As a result, we have formalised the pre- and post-processing of data in k-means-based IDS, and discussed the consequences. One consequence is that some domains may be malicious by nature, in which case a signature-based IDS should assist our anomaly-based IDS.

We implemented the improvements and MoOs of the k-means algorithm on the distributed streaming platform Apache Flink. This thesis also introduces a new MoO which may be a good fit for anomaly-based IDS. It combines the speed and the surprisingly good accuracy of "transforming k-means", and batch mode to update the model along the way. We propose anomaly-based IDS that apply the k-means speedups and different modes on Apache Flink. By doing so, the efficiency of anomaly-based IDS using k-means clustering are improved.