Application of Kolmogorov complexity in anomaly detection

Kolmogorov complexity is the basis of algorithmic randomness theory. It quantifies the amount of information of individual object, which is measured by the size of its smallest algorithmic description. The concept of Kolmogorov complexity is used in many applications like spam filtering, data compression, information assurance etc. In this paper, we present the application of Kolmogorov complexity in network security field, particularly for anomaly detection. In order to accomplish that, it is assumed that most of the network attacks change the structure of the traffic. This enforces anomaly and hence subsequent intrusion can be detected if the structure or signature of the traffic flow is investigated. From this notion, we propose a signature based anomaly detection scheme. We show through simulation results that with the help of Kolmogorov complexity, we can detect traffic pattern abnormality in a simplistic way. This detection and quantification of traffic pattern eventually lead to anomaly detection.