A formal framework for positive and negative detection schemes

• Published in: IEEE transactions on cybernetics 2004-02, Vol.34 (1), p.357-373
• Main Authors: Esponda, F., Forrest, S., Helman, P.
• Format: Article
• Language: English
• Subjects: Artificial immune systems; Biological systems; Computer science; Detectors; Distributed processing; Intrusion detection; Iron; Object detection; Pattern matching; Random variables; Studies
• ISSN: 1083-4419; 2168-2267; 1941-0492; 2168-2275
• DOI: 10.1109/TSMCB.2003.817026

In anomaly detection, the normal behavior of a process is characterized by a model, and deviations from the model are called anomalies. In behavior-based approaches to anomaly detection, the model of normal behavior is constructed from an observed sample of normally occurring patterns. Models of normal behavior can represent either the set of allowed patterns (positive detection) or the set of anomalous patterns (negative detection). A formal framework is given for analyzing the tradeoffs between positive and negative detection schemes in terms of the number of detectors needed to maximize coverage. For realistically sized problems, the universe of possible patterns is too large to represent exactly (in either the positive or negative scheme). Partial matching rules generalize the set of allowable (or unallowable) patterns, and the choice of matching rule affects the tradeoff between positive and negative detection. A new match rule is introduced, called r-chunks, and the generalizations induced by different partial matching rules are characterized in terms of the crossover closure. Permutations of the representation can be used to achieve more precise discrimination between normal and anomalous patterns. Quantitative results are given for the recognition ability of contiguous-bits matching together with permutations.