Can a negative selection detect only a few non-self cells existed in an enormous amount of

self cells?

Akira Imada

Brest State Technical University Moskowskaja 267, 224017 Brest, Republic of Belarus akira@bsty.by

Abstract. We have had lots of reports that assert a negative selection algorithm can successfully distinguish non-self cells from self cells, especially frequently in a context of “Network Intrusion Detection by Artificial Immune System” in which self cell is assumed to represent normal transaction while a non-self cells represent anomaly. They further assert a negative selection gives us an advantage that we can only use a set of self cells as training samples. This would be really an advantage since we usually don’t know what do anomaly patterns look like until they complete an intrusion. We, however, suspect its applicability more or less. This paper gives it a consideration to one of the latest such approaches.

1 Introduction

A sultan has granted a commoner a chance to marry one of his 100 daughters by presenting the daughters one at a time with showing the dowry defined previously. The commoner must immediately decide whether to accept or reject her and he is not allowed to return to an already rejected daughter. The sultan will allow the marriage only if the commoner picks the daughter with the highest dowry. — “Sultan’s Dowry Problem” ^{1}

In real world, we have many problems in which it is easy to access to any one of the huge number of candidate solutions which could be a true sloution but mostlikely not and we don’t know it in advance.

The ultimate extreme is called a-needle-in-a-haystack problem. The originally proposed form by Hinton & Nowlan [3] is that only one configuration of 20 binary bits should be searched for. In other words, the search space is made up of 2^{20} points and only one points is the target point. No information such as how close a currently point is to the needle.

1 According to the author(s) of the web-page of Cunningham & Cunningham, Inc. (http://c2.com) the problem was probably first stated in Martin Gardner’s Mathematical Recreations column in the February 1960 issue of The Scientific American. To explore the problem more in detail, see, e.g., http://mathworld.wolfram.com

Yet another one, a-tiny-flat-island-in-a-huge-lake — this is a problem we came accross when we had explored a fitness landswcape defined on all the possible synaptic weight values of a fully-connected spiking neurons to give them a function of associative memory. Our proposal is formalized as follows.

Test-function 1 (Tiny Flat Island in Huge Lake) Assuming an n-dimensional hypercube all of whose coordinate x_{i} (i = 1, …, n) lies [−1, 1], find an algorithm to locate a point in the region A all of whose coordinates are in [0, a] (a ≤ 1).

Many researchers in Artificial Immunne System community have suggested us that it might be easy if we use Negative Selection. The Negative Selection is a evolutionary selection mechanism by which immune system trains itself only using self cells as a training sample, so that it can recognize non-self cells afterwords.

So, our idea is as follows. We try to test samples one by one, as many as possible, whether each of those randomly picked up samples is the real solution or not. If we find the needle/island during the search procedure by happen, then our goal is attained. We are more than lucky. During the procedure, whichever it might find the solution or not, we train the system, in parallel, during the procedure with using those picked up samples. Then we expect the trained system will recognize the needle/island.

In this paper, we approach the problem from this view point. That is, we take it just a pattern classification problem, in general, under the constraint that we have two classes one of which has an extremely few patterns while the other has almost infinite number of patterns. Or, we might as well take it a task of discrimination of a few of non-self cells as anomaly patterns from enormous amount of self cells which represent normal patterns.

One of the latest approaches, among others, from this point of view is by Ji & Dasgupta [2]. They wrote

The idea of negative selection was from 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 (normal) training data are needed.

Then they proposed two algorithms: one is to generate detectors of constant sized spheres and the other variable sized spheres. They asserted that detectors which detect anomaly patterns are successfully created just by training with normal patterns.

When we think of a network intrusion detection, we usually don’t know what do anomaly patterns look like in advance. Hence this feature of training with only normal patterns is really advantageous. Our concern then is what if the number of non-self cells is extremely smaller than self cells, which is of usual cases when we think of a network intrusion detection. In order to explore this issue, we formalize the problem as follows. Assuming we have n-dimensional patterns all of whose real-valued coordinates lie in [−1, 1] in which anomaly pattern has its coordinate whose value lie in [−a, a] while all other patterns are normal patters. This is just a-tiny-island-in-a-huge-lake mentioned above when we set a a very small value. We can control the difficulty of the task by changing the value of a. In the ultimate case in which the pattern whose coordinates are all shrunk to zero, is the problem called a-needle-in-a-haystack.

2 Algorithm

Lots of algorithms to distinguish non-self patterns from self patterns have been proposed. The goal of some of these algorithms is to create detectors which cover non-self space as much as possible. Here, among others, we concentrate on the algorithm called “Augmented Negative Selection Algorithm with Variable-Coverage Detectors” proposed by Zhou Ji and D. Dasgupata (2004) and it’s simpler version in which constant sized detectors instead of variavle-sized are used proposed by the same authors in the same article [2]. The followings are these two algorithms we paraphrased the original ones with the semantics being intact. Firstly, the simpler versions of the algorithm is:

Algorithm 1 (Constant-sized Detector Generation) After setting (i) N_{t} — the number of training samples, (ii) r_{d} — the radius of detector, and (iii) N_{d} — the total number of detectors:

1. Create N_{s} — samples of self cells randomly.

2. Create a hyper-sphere which has the radius r_{d} and its center locates at random in [−1, 1]. This is a candidate detector to detect non-self cells.

3. If this-hyper shpere does not contain any self cells, then put it as a detector in D — the detector’s repertoire. Otherwise delete the hyper-shpere.

4. Repeat 2-3 until we find N_{d} detectors.

This algorithm does not contain the concept of Negative Selection or whatever in Immune System metophor neither. The second one is:

Algorithm 2 (Constant-sized Detector Generation) After setting (i) N_{t} — the number of training samples, (ii) r_{s} — the radius of self cells, (iii) c_{0} — expected coverage, i.e., the degree to how much those created detectors cover non-self cells, (iv) c_{max} — the upper bound of self coverage, and (v) N_{d} — the maximum number of detectors:

1. Empty D — the detector’s repertoire.

2. Try to find a point x = (x_{1}, ⋯, x_{n}) ∈ [−1, 1]^{n} which is not contained by any of the valid detectors so far created, unless the number of those trials exceeds 1/(1 − c_{0}). If no such x is found, then terminate the run.^{2}

3. If r — the distance between x and its closest self sell in the training sample, is less than the radius r_{s}, then add the sphere whose center is x and radius is r to D as a new valid detector.

4. If such x cannot be found within the time 1/(1 − c_{max}) then terminate the run.^{3} Otherwise repeat 2 and 3, until we find a predefined number of detectors.

We don’t think this algorithm also does not strongly reflects an Artificial Immune System, despite the title of the original paper indicates. However at least title holds true in the sense that detectors are chosen by matching them to the self strings and if a detector matches it is discarded, otherwise, it is kept.

3 Experiment, Results, and Discussion

We assume here the whole universe is n-dimensional hyper-cube [−1, 1]^{n}; any point all of whose coordinates lie in [−a, a] where 0 < a < 1 are a non-self cell, whilst other points in the universe are self cells; and all the self cells are hyper-sphere whose radius is r_{s}.

3.1 A 2-dimensional version of an-island-in-a-lake

First of all, in order to observe the behavior of the algorithms our experiment is performed on a 2-dimensional space, that is, we set n = 2. We employ a set of 500 randomly selected points in the self region as the training sample, and 1000 points randomly chosen from entire space is the test data. The reason of these settings is to enable us to compare our results with ones in the original proposition [2].

Nomal moints and created detectors when we set r_{s} = 0.1 which is recommended by the original proposition [2] are shown in Fig. 1. Our goal, however, is to recognize non-self patterns from extremly tiny reageon. Hence the next experiment is a dependency on the value of a. Fig. 2 shows the number of required trial to find the pre-defined number of detectors, which is 500 here, and ... As we can see in the Figure The dificulty of the task becomes hard exponentially, and therefore we know this algorithm would not work if the region to be searched for is extremly tiny.

2 This is because when we have sampled m points and only one point was not covered, the expected coverage is 1 − 1/m. Hence the necessary number of tries to ensure expected coverage c_{0} is m = 1/(1 − c_{0}).

3 See also the footnote above.

Fig. 1. The points employed in the 2-D experiments. A set of five hundred self-sells (Left), and a set of five hundreds detectors created by the Algorithm-1 with the value of a being 0.5 and r_{s} = 0.1 (Right).

Fig. 2. The number of iteration required to find N_{d} detectors versus the value of a when we experimentd with the Algorihtm-1 with r_{s} = 0.1 (Left).

Also the relation between r_{s} and the detection-rate/false-alarm trade-off will be shown. That is, correctly detected rate and false alarm rate will be plotted against r_{s} changed from 0.01 to 0.20 (not shown in this submission paper, though.)

3.2 A 20-dimensional version of an island in a lake

Here experiments are performed on the test-bed that we call a-tiny-flat-island-in-a-huge-lake^{4} which is an extension of a-needle-in-a-haystack-problem — a

4 It is not necessarily to be said for the top of the island to be flat, but the originally this was a test-bed for evolutionary computations, and the fitness of the island region is one and zero in a lake region, that is why.

Fig. 3. The number of iteration required to find N_{d} detectors versus the value of a when we experimentd with the Algorihtm-1 with r_{s} = 0.1 (Left).

reminiscent of the seminal experiment by Hinton & Nowlan [3].

In a preliminary experiment, we found it much more difficult than in the case n = 2. What we found, for example, is even if we increase the number of training sample of self patterns to 10000 from 1000, the distribution of the sample is very sparce under the condition of n = 20. If the algorithm works well, the detector are supposed to locate in the non-self region, such as Fig. 1 (Right), while the result is not in that way as shown in Fig. 3 (Left). The coordinates of whole detectors are almost uniformly distributed. We will furthe explore different parameter values with the goal being to learn the limit of the size of non-self domain in which the algorithm can detect the non-self cells. Then we will experiment by lowering the value c_{0} which is 99.99% and 99% in the original version.

Further, we give it a consideration of how the Algorithm-2, Variable sized detector, improve the situation.

4 Conclusion

We have obtained the similar results with the experiments by Zhou et al [2] on the condition that the island is not so small, that is, the value a is sufficiently large.

Usually, however, in the real world problem, anomaly patterns are extremely fewer than the normal ones. As such, our concern is on this case. Unfortunately, we have not so far observed a satisfactory result under this situation. In fact, Ji et al. denotes

As an exception, the algorithm may also terminate when it fails to sample any non-self point after many repetitions. That implies that the self region covers almost the entire space. It may happen when the self samples are randomly distributed over the space, or the chosen self-radius is too big.

And they went on to write “One of the three types of iris data is considered as normal data, while the other two are considered abnormal,” the number of normal and abnormal is a kind of comparable in usual such experiment.

5 Others of our Related Works

We are exploring the same target — a-tiny-flat-island-in-a-huge-lake, or its binary version, with a number of different approaches. So far we are progressing the experiments using (1) a negative selection of binary detector using r-contiguous matching to detect a-needle-in-a-haystack; (2) evolving a set of fuzzy rules to detect non-self cells in a-tiny-island-in-a-huge-lake; (3) the same as (2) but using a data-mining techniques.

The objective of these series of works is to detect anomaly phenomena which take place only occasionally and hence we don’t know how does it look, while we have enormous amount of daily normal phenomena. As far as we know this is still an open issue and we try to find some approaches, or at least evoke interests to this problem. The challenge awaiting us is to find a more effective algorithm to find detectors to detect tiny amount of non-self patterns.

References

1. A. Imada (2004) “How a Peak on a Completely-flatland-elsewhere can be Searched for? — A Fitness Landscape of Associative Memory by Spiking Neurons.” Proceedings of Advanced Computer Systems (ACS) and Computer Information Systems and Industrial Management Applications (CISIM), Vol.2, pp. 171–150.

2. Zhou Ji and D. Dasgupata (2004) “Augmented Negative Selection Algorithm with Variable-Coverage Detectors.” Proceedings of the Congress on Evolutionary Computation

3. G. E. Hinton and S. J. Nowlan (1987) How Learning can Guide Evolution. Complex Systems, 1, pp. 495–502.

This article was processed using the L^{A}TEX macro package with LLNCS style