An evaluation of negative selection algorithm with constraint-based detectors

ABSTRACT

The Negative Selection Algorithm is an immunology-inspired algorithm for anomaly detection application. This algorithm has been implemented with different pattern representations and various matching rules and successfully applied to a broad range of problems. Recent research shows serious problems with this algorithm in terms of both efficiency and effectiveness. In this paper we evaluated the performance of the algorithm constraint-based representation. We argue that the algorithm and problem representations should be considered separately, and that best performance of the algorithm may be obtained by choosing a proper representation.

REFERENCES

• 1: Ayara, M., Timmis, J, de Lemos, R., and Duncan, R. (2002) "Negative Selection: How to Generate Detectors", 2002 ICAIS, 89--98.
• 2: Balthrop, J., Forrest, S. and Glickman, M. (2002) "Revisiting LISYS: parameters and normal behavior", 2002 CEC, 1045--1050.
• 3: Justin Balthrop , Fernando Esponda , Stephanie Forrest , Matthew Glickman, Coverage and Generalization in an Artificial Immune System, Proceedings of the Genetic and Evolutionary Computation Conference, p.3-10, July 09-13, 2002
• 4: Dasgupta, D. (1999) "An overview of artificial immune system and their applications", Artificial Immune Systems and Their Applications, D. Dasgupta, ed., Springer, 3--21.
• 5: Dasgupta, D. and Gonzalez, F. (2002) "An immunity-based technique to characterize intrusions in computer network", IEEE Trans. Evolutionary Computation. 6(3): 281--291.
• 6: Leandro R. de Castro , Jonathan Timmis, Artificial Immune Systems: A New Computational Intelligence Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 7: Patrik D'haeseleer , Stephanie Forrest , Paul Helman, An Immunological Approach to Change Detection: Algorithms, Analysis and Implications, Proceedings of the 1996 IEEE Symposium on Security and Privacy, p.110, May 06-08, 1996
• 8: Esponda, F., Forrest, S., and Helman, P. (2004) "A formal framework for positive and negative detection schemes", IEEE Trans. Systems, Man, and Cybernetics--Part B: Cybernetics, 34(1): 357--373.
• 9: Stephanie Forrest , Alan S. Perelson , Lawrence Allen , Rajesh Cherukuri, Self-Nonself Discrimination in a Computer, Proceedings of the 1994 IEEE Symposium on Security and Privacy, p.202, May 16-18, 1994
• 10: Stephanie Forrest , Steven A. Hofmeyr , Anil Somayaji, Computer immunology, Communications of the ACM, v.40 n.10, p.88-96, Oct. 1997 [doi>10.1145/262793.262811]
• 11: Gonzalez, F, Dasgupta, D. and Kozma, R. (2002) "Combining negative selection and classification techniques for anomaly detection", 2002 CEC, 705--710.
• 12: Gonzalez, F, Dasgupta, D. and Nino, D. (2003) "A randomized real-valued negative selection algorithm", 2003 ICAIS, 261--272.
• 13: Steven A. Hofmeyr , Stephanie A. Forrest, Architecture for an Artificial Immune System, Evolutionary Computation, v.8 n.4, p.443-473, December 2000 [doi>10.1162/106365600568257]
• 14: Hou, H., Zhu, J. and Dozier, G. (2002) "Artificial Immunity using Constraint-based Detectors", 2002 WAC, 13:239--244.
• 15: Ji, Z. and Dasgupta, D. (2004) "Real-valued negative selection algorithm with variable-sized detectors", 2004GECCO, 287--298.
• 16: Zhou Ji , Dipankar Dasgupta, Estimating the detector coverage in a negative selection algorithm, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068056]
• 17: Kim, J. and Bentley, P. (2001) "An evaluation of negative selection in an artificial immune system for network intrusion detection", 2001 GECCO 1330--1337.
• 18: Kim, J. and Bentley, P. (2001) "Towards an artificial immune system for network intrusion detection: an investigation of clonal selection with a negative selection operator", 2001 CEC, 1244--1252.
• 19: Mukherjee, B., Heberlein, T., and Levitt, K. (1994) "Network Intrusion Detection", IEEE Network, 8(3): 26--41.
• 20: Singh, S. (2002) "Anomaly detection using negative selection based on the r-contiguous matching rule", 2002 ICAIS, 99--106.
• 21: Stibor, T., Bayarou, K. and Eckert, C. (2004) "An investigation of r-chunk detector generation on higher alphabets", GECCO 2004, 299--307.
• 22: Stibor, T., Timmis, J. and Eckert, C. (2005) "A comparative study of real-valued negative selection to statistical anomaly detection techniques", ICARIS 2005, 262--275.
• 23: Thomas Stibor , Philipp Mohr , Jonathan Timmis , Claudia Eckert, Is negative selection appropriate for anomaly detection?, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068061]
• 24: Stibor, T., Timmis, J. and Eckert, C. (2005) "On the appropriateness of negative selection defined over hamming shape-space as a network intrusion detection system", 2005 CEC.
• 25: Stawomir T. Wierzchon, Generating Optimal Repertoire of Antibody Strings in an Artificial Immune System, Proceedings of the IIS'2000 Symposium on Intelligent Information Systems, p.119-133, June 12-16, 2000
• 26: Wolberg, W. and Mangasarian, O. (1990) "Multisurface method of pattern separation for medical diagnosis applied to breast cytology", PNAS, 87:9193--9196.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Performance

Keywords:
AIS, anomaly detection, negative selection