An evolutionary algorithm to generate hyper-ellipsoid detectors for negative selection

ABSTRACT

This paper introduces hyper-ellipsoids as an improvement to hyper-spheres as intrusion detectors in a negative selection problem within an artificial immune system. Since hyper-spheres are a specialization of hyper-ellipsoids, hyper-ellipsoids retain the benefits of hyper-spheres. However, hyper-ellipsoids are much more flexible, mostly in that they can be stretched and reoriented. The viability of using hyper-ellipsoids is established using several pedagogical problems. We conjecture that fewer hyper-ellipsoids than hyper-spheres are needed to achieve similar coverage of nonself space in a negative selection problem. Experimentation validates this conjecture. In pedagogical benchmark problems, the number of hyper-ellipsoids to achieve good results is significantly (~50%) smaller than the associated number of hyper-spheres.

REFERENCES

• 1: C.L. Blake and C.J. Merz. UCI repository of machine learning databases, 1998. http://www.ics.uci.edu/~mlearn/MLRepository.html.
• 2: Leandro R. de Castro , Jonathan Timmis, Artificial Immune Systems: A New Computational Intelligence Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 3: Fabio A. Gonzalez and Dipankar Dasgupta. Anomaly detection using real-valued negative selection. In Proceedings of Genetic Programming and Evolvable Machines 2003, pages 383--403. Kluwer Academic Publisher.
• 4: Zhou Ji and Dipankar Dasgupta. Real-valued negative selection algorithm with variable-sized detectors. In Proceedings of GECCO 2004, LNCS 3102, Berlin. Springer-Verlag.
• 5: Jungwon Kim and Peter~J. Bentley. An evaluation of negative selection in an artificial immune system for network intrusion detection. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), September.
• 6: Brent McBride. A hyper-geometric data classifier for blind detection of novel steganography. Master's thesis, Air Force Institute of Technology, Wright-Patterson AFB, OH, March 2004.
• 7: Donald Michie , D. J. Spiegelhalter , C. C. Taylor , John Campbell, Machine learning, neural and statistical classification, Ellis Horwood, Upper Saddle River, NJ, 1995
• 8: Patrick M. Kelly , Don R. Hush , James M. White, An adaptive algorithm for modifying hyperellipsoidal decision surfaces, Journal of Artificial Neural Networks, v.1 n.4, p.459-480, 1994
• 9: 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
• 10: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 11: Joseph M. Shapiro. An evolutionary algorithm to generate hyper-ellipsoid detectors for negative selection. Master's thesis, Air Force Institute of Technology, Wright Patterson Air Force Base, Ohio, 2005.
• 12: David J. Smith and Mavina K. Vamanamurthy. How small is a unit ball. Mathematics Magazine, 62(2):103--107, April 1989.
• 13: Gilbert Strang. Introduction to Linear Algebra. Wellesley-Cambridge Press, 2 edition, 1998.
• 14: Jonathan Timmis Susan Stepney, Robert E. Smith and Andy M. Tyrrell. Towards a conceptual framework for artificial immune systems. In Proceedings of International Conference on Artificial Immune Systems (ICARIS 2004), pages 53--64, 2004.
• 15: PAL Core Development Team. Pal project: Gamma function, October 2004.
• 16: Eric W. Weisstein. Gamma function. From Mathworld--A Wolfram Web Resource, http://mathworld.wolfram.com/GammaFunction.html.
• 17: Paul Williams, Kevin Anchor, John Bebo, Gregg Gunsch, and Gary Lamont. CDIS-towards a computer immune system for detecting network intrusions. In Proceedings of Recent Advances In Intrusion Detection, 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

General Terms:
Algorithms

Keywords:
artificial immune systems, computational geometry, evolutionary computation, negative selection