Foundations of intrusion detection [computer security]

Computer use is modeled as a mixture of two stochastic processes, normal and misuse. Intrusion detection is formally defined as identifying those transactions generated by the misuse process. Bounds for detection performance are derived in terms of the ratios of the densities of the processes at the individual transactions. It is shown that any optimal intrusion detection system must rank transaction suspicion consistently with these ratios. Sparsity of data requires that transactions be grouped into equivalence classes that preserve the order of the true ratio ranking and reduce the number of singleton and unobserved transactions. Results are described that demonstrate that in general this `singleton reduction´ problem is NP-hard