A Change-Detection Method Inspired by the

Immune System:

Theory, Algorithms and Techniques

Patrik D?haeseleer
Department of Computer Science University of New Mexico Albuquerque, New Mexico, 87131 [email protected]
http://www.cs.unm.edu/~patrik

Technical Report No. CS95-6 November 1, 1995

Abstract

This report gives an overview of the tools developed for the change-detection method based on the immune system, introduced by Forrest et al. in [6] and [7]. Some general theoretical results are given. Consequences of the detector generating algorithms from [8] and [5] are examined and some preliminary results with these algorithms are analyzed. Finally, guidelines are given for choosing the various parameters of the matching rule when applying this method to a real data stream.

1 Introduction

The change-detection method introduced in [6] and [7] distinguishes ?self? strings from ?nonself? strings by generating detectors for anything that is not in the self set. This is similar to the generation of T-cells in the immune system. In the thymus, T-cells with effectively random receptors are generated, but before they are released in the bloodstream those T-cells that match self proteins are deleted.

This principle of generating random detectors and then censoring the ones that match the self strings (according to a predefined matching rule) is used in [6] to construct a detector set that matches nonself strings with a given probability of success. More efficient detector generating algorithms are described in [8] and [5]. However, these generate only valid detectors for a specific matching rule (r-contiguousbits matching). This report will focus on the theoretical background of this kind of change-detection method, as well as on the consequences of the algorithms described in [5, 6, 7, 8], and the issues involved in the practical application of these techniques.