Kolmogorov complexity estimation and application for information system security

Kolmogorov Complexity is explored as a fundamental property of information that is an attractive parameter for monitoring and preserving the health of information systems. In this dissertation we first review and motivate the use of Kolmogorov Complexity for this application and summarize current strategies for information system security and intrusion detection. We apply existing methods for complexity estimation to the problem of Information Assurance and devise a strategy named “Conservation of Complexity” for Intrusion Detection using Complexity estimates. We derive a new heuristic for complexity estimation from Minimum Description Length principles and develop a new complexity estimator and compression algorithm based on Grammar Inference using this heuristic. Our new complexity estimation algorithm and its companion metric (known as Sophistication) that estimates optimal model size is benchmarked against other complexity estimators and applied to the problem of information system security and fault detection. Results showing the utility of complexity based information assurance to detect exploits over File Transfer Protocol are presented and analyzed. We show that complexity metrics are able to distinguish between FTP exploits and normal sessions within some margin of error and that our Sophistication metric provides meaningful insight for characterizing data and aiding in classifying protocol behavior. Further research is motivated by encouraging results using information complexity distance metrics.