MDLcompress for Intrusion Detection: Signature Inference and Masquerade Attack

MDLcompress is a grammar inference algorithm that uses Minimum Description Length principles from the theory of Kolmogorov Complexity and Algorithmic Information Theory to infer a grammar, finding patterns and motifs that aid most in compressing unknown data sets. This technology has been applied to detection of FTP exploits and inference of DNA sequence motifs related to breast cancer. In this paper we apply MDLcompress to infer grammars, and then apply those grammars to identify masquerades in the publicly available Schonlau system call data sets. Compared to similar protocols our system detects anomalous events with comparable performance with the advantage of executing in linear time.