Kolmogorov complexity based automata modeling for intrusion detection

According to Kolmogorov complexity, a string is considered patternless if the shortest Turing machine that can encode it is at least as long as the string itself. Conversely, a non-random string with patterns can be described by some Turing machine that is shorter than the string. Hence, special forms of Turing machines - such as functions, N-grams, finite automata and stochastic automata - can all be regarded as representations of some approximations of patterns. Based on these observations, system profiles are defined for anomaly-based intrusion detection systems. The results are encouraging.