A Survey on Anomaly Ditection
by Akira Imada (December 2004)
All the topic of this page is, in short, designing an algorithm
to detect patterns called 'non-self' (anomalcy)
among patterns called 'self' (nomalcy).
Those patterns are basically in a n dimensional
Eucledean space.
Anomaly Detection in General --- Artificial Immune System (AIS) Approach
We explore, first of all, anomaly detection by AIS in this section of this page.
Title of this section includes "in General" while some of the papers
bellow describe specifically "Network Intrusion." IMHO, however,
the algorithms proposed are easily extended to more general case of
"Anomaly Detection."
- Detection of Binary Encoded Anomaly
Let's start with binary-pattern detection as anomaly, since one of my concerns
is search for a-needle-in-a-haystack problem.
- Clonal Selection
-
An Artificial Immune Model for Network Intrusion Detection
J. Kim and P. Bentley
Althought this paper specifically intends to propose
a Network Intrusion Detection System, the algorithm could be
easily extended to a general Anomaly Detection. Authors wrote:
"It combines three
evolutionary stages. Gene library evolution simulates the first stage of evolution,
which learns knowledge of currently existing antigens.
......
Gene expression and negative selection form the second stage of evolution,
generating diverse pre-detectors and selecting mature detector sets by
eliminating false pre-detectors in a self-organising way.
......
Clonal selection is the third stage of evolution, detecting various
intrusions with a limited number of detector sets using approximate binding,
and generating memory detectors.
- Positive Selection
- Negative Selection
-
[4] Gonzalez, F., D. Dasgupta, J. Gomez, The Effect of Binary
Matching Rules in Negative Selection, GECCO-03, 2003
-
[6] Esponda, F., S. Forrest, P. Helman, A Formal Framework
for Positive and Negative Detection Scheme, IEEE
Transaction on Systems, Man, and Cybernetics, 2003
-
[11] Ceong, H. T., et al, Complementary Dual Detectors for
Effective Classification, ICARIS-03, 2003
-
[13] Kim, J., et al, An evaluation of negative selection in an
artificial immune system for network intrusion detection, in
Proceedings Genetic Evolutionary Computation
Conference, San Francisco, 2001
-
[15] Ayara, M., J. Timmis, R. de Lemos, L. de Castro, and R.
Duncan, Negative Selection: How to Generate Detectors,
1st ICARIS, 2002
What we should specially note in algorithms using negative selection is
only the negative (or normal) training data are needed as Dasgupta et all wrote in
-
Dasgupta, et al (1899) "An Anomaly Detection Algorithm
Inspired by the Immune System."
(Dasgupta et al. Eds), Artificial Immune System and Their Application
Dasgupta's group in Memphis US gave us an excellent series of systematic proposal
every year of a detector
to detect "non-self" in the continuous multi-dimensional Eucledian space.
The following a couple of papers are by Dasgupta's group from newer to older ones.
-
Z. Ji and D. Dasgupata (2004)
"Augmented Negative Selection Algorithm with Variable-Coverage Detectors."
Proceedings of the Congress on Evolutionary Computation
As authors denote, Negative selection in this series of papers are very simple
in the sense that
"The inspiration of negative selection, or negative detection, came from the
T cell development process in the thymus. If a T cell
recognizes self cells, it is eliminated before deployment
for immune functionality. In an analogous manner,
the negative selection algorithm generates the detector set
by eliminating any detector candidates that match self
samples. It is thus used as an anomaly detection
mechanism with the advantage that only the negative (or 'normal')
training data are needed.
Then authors proposed two algorithms: one is to generate detectors
of constant sized and the other variable sized sperers. (See my article
"Hints for Implementations".
Immuno-fuzzy Approach
Fuzzy Rules not based on Immune System but Evolved by Genetic Algorithm
-
J. Gomez and D. Dasgupta
"Evolving Fuzzy Classifiers for Intrusion Detection"
Authors wrote:
"proposes a technique to generate
good fuzzy classifiers using genetic algorithms that can detect
anomalies ... The main idea is to
evolve two rules, one for the normal class and other for the
abnormal class ..."
And their algorithm is in
Also the detailed algorithm seems to be in
-
J. Gomez and D. Dasgupta (2002)
"Using Competitive Operators and a Local Selection Scheme in Genetic Search."
Proceedings (Late-Breaking) of the Genetic and Evolutionary Computation Conference,
pp. 193-200.
Using-Competitive-Operators-and-a-Local-Selection-Scheme-in-Genetic-Search."
But I have not succeeded in getting the paper via Internet.
Messy-GA Approach
Yet Another Intrusion Detection --- Data Mining Approach
Anomaly Detection in Particular ---
Network Intrusion Detection --- Proposals in a more Concrete Way