Can an Immuno-fuzzy Approach Detect Only a Few Non-self Cells Existed in an Enormous Amount of Self Cells?
Akira Imada 
Brest State Technical University, Moskowskaja 267 Brest 224017 Belarus, akira@bstu.by, http://neuro.bstu.by/ai/akira.html 

Abstract - In the context of Network Intrusion Detection, we test a lately reported technique which generates a set of fuzzy rules to recognize unknown abnormal patterns using a test-function which we call a-tiny-island-in-a-huge-lake. Our concern is whether or not we can train the system only with a set of already known normal patterns. Yet another of our concern is what happens in an extreme case where a sample of abnormal patterns are very few comparing to the normal ones, and what if it eventually shrinks to zero, which is what they call a-needle-in-a-haystack

Keywords - Network Intrusion Detection, Test samples, Fuzzy rule.

I.	Introduction
This paper reports a snapshot of our on-going experiments in which a common target that we call a-tiny-island-in-a-huge-lake is explored with different methods ranging from a data-mining technique to an artificial immune system. Our implicit interest is a network intrusion detection, and we assume data floating in the huge lake are normal while ones found on the tiny island are abnormal. Our goal here is twofold. One is to know whether or not it is possible to train a system using just normal data alone. The other is to study a limit of the size of  detectable area, when we decrease the size of the island eventually shrinking to zero, equivalently  so-called a-needle-in-a-haystack (See Fig. 1) which is still an open and worth while tackling problem. To learn these two issues, a fuzzy rule extraction system with fixed triangle/trapezoid membership functions are exploited in this paper.
When we think of a network intrusion detection, we have a large collection of normal patterns while the number of possible anomaly patterns we know is extremely few, which is of usual case. Then our concern is how we can train a system with a lack of negative training data.
Furthermore, we usually don't know what do anomaly patterns look like in advance. It is usually too late when we know it.  Hence, our second concern is whether or not we can train the system with only a set of normal patterns. So far, lots of such approaches have been proposed claiming they had very successful results. Especially Artificial Immune Approach is exploited to search for abnormal patters. For example, a binary search space is explored by using Negative Selection [3, 4, 5, 6, 7], a continuous space by Clonal Selection [8], also by Positive Selection [9], again Negative Selection [10, 11, 12, 13, 14, 15, 16, 17]. Furthermore, other concepts are also employed, such as Fuzzy Approach [18, 19, 20], Messy Genetic Algorithm [21, 22, 23], Data-mining [24] and so on.
Thus far those intrusion detection systems train themselves with already known normal patterns and then it succeeds in warning when a so far unknown anomaly pattern is given, though we doubt it more or less.

Fig. 1. A fictitious sketch of fitness landscape of a needle  in a haystack. The haystack here is drawn as a two-dimensional flat plane of fitness zero.

A tiny island in a huge lake --- this is a problem we'd proposed in which a few number of unknown patterns should be recognized or classified from an enormous number of known patterns [1], which is up to now still an open issue. Originally the problem described, in particular, a fitness landscape when we searched for a weight configuration which gives a network with fully-connected spiking neurons a function of associative memory. In this paper, we regard the problem from a view point of anomaly detection by an immuno-fuzzy approach.
That is, we take it just a general  pattern classification problem on the condition, however, 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 from artificial immune system point of view.
In order to explore this issue, we formalize the problem as follows. We assume we have n-dimensional patterns all of whose real-valued co-ordinates lie in the interval [-1,1]. This constructs our self/non-self space. Anomaly patterns have their co-ordinates each of whose value lies in [-a, a], while all others are regarded as normal patterns. We can control the difficulty of the task by changing the value of a. In the ultimate case in which the pattern whose co-ordinates are all zero, is called a-needle-in-a-haystack problem.

II.	Experiment
A set of fuzzy rules is used to cover the non-self patterns. As already mentioned, self/non-self cells are represented by n-dimensional real valued vectors each of whose coordinate lies in [-1, 1]. That is, the self/non-self space is [-1, 1]n, and a self/non-self pattern is represented by a vector x = (x1, …, xn) where xi  [-1, 1]. Then a fuzzy rule to detect non-self patterns is

If x1 is T1, … , and xn is Tn then x is non-self

where Ti is a fuzzy linguistic term which is either one of {Low, Low-Middle, Middle, Middle-High, High}. Each of Ti maps the xi to a real value between 0 and 1, expressing the degree to how it is likely to the linguistic value. This is calculated by a membership function, which is defined here using fixed shaped triangular and trapezoidal fuzzy membership functions.
We know how many rules are needed in this problem  only one rule is sufficient. In this sense too, this test-set is a good one.

Fig.2. Five fixed shaped membership functions each of which describes how likely a coordinate is either Low (L), Middle-Low (ML), Middle (M), Middle-High (MH), or High (H). Note that the coordinates in [-1,1] are translated into [0,1] with interpretation being intact.

Then a genetic algorithm evolves these fuzzy rules, with chromosomes being (T1, …, Tn), starting with those chromosomes randomly created. To be more specific, our chromosome is made up of n integer genes whose value is chosen from {0, 1, 2, 3, 4}. The fitness of a rule is evaluated by applying the rule to all the self patterns  x = (x1, …, xn) and calculated as

which implies how the rule covers the non-self space.
The size of self cells is fixed to 400; each GA run is iterated for 1000 generations; size population of chromosmes are 100, to be comparable with the original Dasgupta et al's experiment [2].
III.	Results & Discussion
As a preliminary experiment, we tried a random search for the 20-dimensional needle by creating 5000 candidate strings of 20 binary bit at random, assuming all 0 string alone is the needle. The result is shown in Fig. 2, and we found it is still not such a difficult problem if we use a standard PC found everywhere nowadays.

Fig.3. The number of happens-to-be-the-needle out of 5000 random creations of the candidate.

Then what will happen if we exploit one of the lately reported more sophisticate methods? As our goal is to find a rule to identify an island, that is whether or not the search point x = (x1, …, xn) fulfills the condition that  -a < xi < a for all i = 1, …, n, all we need is one rule, that is, 

IF x1 is Middle, and…, and xn is Middle 
THEN x is on the island.

And we found an evolution converges to a successful such chromosome 

(2 2 2 2 2 2).

However, this holds only on the condition that the dimension is small and the island is fairly large. In Fig. 4.  we plot two cases of evolution. One is the island made up of the points xi  [0.25, 0.75] and the other is xi  [0.45, 0.55], both in the 6-dimensional lake. This discrepancy in the size of the lake depending on the dimensionality is around a critical condition for the success of the evolution. Our temporary goal of 20-dimensional a-needle-in-a-haystack is far beyond from this critical point. A trial of a search for the island of xi  [0.45, 0.55] (i = 1, …, 20) in the 20-dimensional lake converged a chromosome

(0 1 3 4 0 4 4 1 4 4 1 1 4 1 4 3 0 0 0 2)

due to a curse of dimension.
As for the size of the island, we might explore the evolution in which shape of membership functions are also adaptively evolved, Such as Gaussian one, expecting very narrow membership function corresponding to the linguistic term MIDDLE.
The scheme of training only with normal sample with the exactly same set of 5 membership functions as the one described above, and an almost same way of genetic algorithm, Gomez et al applied this technique to the dataset from KDD CUP 99 [25]. That is, the dataset is 10% version of KDD-CUP 99 removing all the categorical attributes, which results in the 492,021 data each made up of 33 attributes which are normalized between 0 and 1 using maximum and minimum values found  also the same way as ours. An 80% of the normal samples were picked randomly and used as training data set, while the remaining 20% was used along with the abnormal samples as a testing set. Then they claimed, for example, the detection rate of 98.22% while false alarm rate being 1.9%. 

Fig.4.  Evolution to find the island in the 6-dimensional lake. Upper plot is when xi  [0.25, 0.75] and lower plot is for a small island where xi  [0.45, 0.55] (i = 1, …, 6).

Comparing to our poor results, what is the difference? The difference between two experiments is size of abnormal samples, which suggests the method proposed by Gomez et al. works when number of abnormal samples and normal sample is similar. Otherwise, that is, when we are to look for one of a few abnormal samples embedded in huge normal samples, the method does not work.
IV.	Conclusion
We have described how we would be able to find a small island in a huge lake with a system training only using data in a lake. This is a metaphor in which a very few of unpredictable abnormal transaction patterns hidden in an enormous amount of normal patterns, in the context of network intrusion detection. We need test samples to test the system we are designing. So far, so many such samples are proposed. For example, Ayara et al. [2] used randomly generated 8-bit binary patterns assuming they are normal patterns; Kim & Bentley [8] used Fisher's Iris Flower Database, which includes the data of three different species of Iris flower, by taking one set as a normal pattern set and the rest as an abnormal set. Then with a tenfold cross-validation method, it was claimed the best true positive rate reached 100% and the worst false positive rate was only 1%; or more directly, some others such as Gomez et al. [3] used the 1998 DARPA intrusion detection evaluation data-set prepared by MIT, also known as KDD cup 99 data-set [25]. We have also a newer such public domain data-set called KDD cup 2003 which was used in the data mining competition held in conjunction with the Ninth Annual ACM SIGKDD Conference [26].
We assume three conditions for a set of database to be used for the purpose of train and test a system we are designing as follows.

•	Data-set is comprised of all possible patterns. 
•	Training should be only by normal samples
•	Number of normal sample should be enormous while abnormal sample is only a few. 

When an iris flower is normal then are others abnormal? None of the above mentioned examples fulfills all of the three conditions.
We are still neutral as for the possibility of designing an intrusion detection system using test samples in this way. Or rather negative if we are not beating around the bush. We hope this article will play a role of call for challenges to this issue.

References

[1] A. Imada "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, 2004.
[2] J. Gomez, F. Gonzalez, and D. Dasgupta (2003) "An Immuno-Fuzzy Approach to Anomaly Detection" Proceedings of the 12th IEEE International Conference on Fuzzy Systems, Vol. 2, pp.~1219-1224, 2003.
[3] M. Ayara, J. Timmis, R. D. Lemos, L. N. D. Castro, and R. Duncan. "Negative Selection: How to Generate Detectors."  Proceedings of 1st International Conference on Artificial Immune Systems pp. 89--98, 2002.
[4] P. Helman and S. Forrest. "An Efficient Algorithm for Generating Random Antibody Strings." Technical Report 94-07, University of New Mexico, Albuquerque, NM. 1994.
[5] P. D'haeseleer, S. Forrest, and P. Helman. "An immunological approach to change detection: algorithms, analysis and implications." Proceedings of the 1996 IEEE Symposium on Computer Security and Privacy, pp. 110--119, 1996.
[6] F. Esponda, S. Forrest. "Detector coverage under the r-contiguous bits matching rule." University of New Mexico Technical Report TR-CS-2002-03, 2002.
[7] F. Esponda, S. Forrest, and P. Helman. "A formal framework for positive and negative detection." IEEE Transactions on Systems, Man, and Cybernetics 34:1 pp. 357-373, 2004.
[8] J. Kim and P. J. Bentley "Towards an Artificial Immune System for Network Intrusion Detection: An Investigation of Clonal Selection with a Negative Selection Operator.'' Proceedings of the Congress on Evolutionary Computation. pp. 1244—125, 2001.
[9] Kwee-Bo Sim and Dong-Wook Lee.  "Modeling of Positive Selection for the Development of a Computer Immune System and a Self-Recognition Algorithm." International Journal of Control, Automation, and Systems Vol. 1, No. 4, pp. 453--458, 2003.
[10] Dasgupta, et al. "An Anomaly Detection Algorithm Inspired by the Immune System." Dasgupta et al.. (Eds), Artificial Immune System and Their Application, 1999.
[11] Z. Ji and D. Dasgupata., "Augmented Negative Selection Algorithm with Variable-Coverage Detectors." Proceedings of the Congress on Evolutionary Computation, pp. 1081-1088, 2004.
[12] F. Gonzalez, D. Dasgupta. "Anomaly Detection Using Real-Valued Negative Selection." Genetic Programming and Evolvable Machines, Vol. 4 No. 4, Kluwer Academic Press, pp. 383-403, 2003.
[13] F. Gonzalez, D. Dasgupta and L. F. Nino. "A Randomized Real-Valued Negative Selection Algorithm." Proceedings of the 2nd International Conference on Artificial Immune Systems,  pp.261-272, 2003
[14] Gonzalez, F., D. Dasgupta, J. Gomez. "The Effect of Binary Matching Rules in Negative Selection." Proceedings of the Genetic and Evolutionary Computation Conference, 2003
[15] D. Dasgupta and N. S. Majumdar. "Anomaly detection in Multidimensional Data using Negative Selection algorithm." Proceedings of the Congress on Evolutionary Computation, pp.1039-1044, 2002.
[16] Ceong, H. T., et al.  "Complementary Dual Detectors for Effective Classification." ICARIS-03, pp.242-248, 2003.
[17] J. Kim and P. Bentley. "An evaluation of negative selection in an artificial immune system for network intrusion detection." Proceedings Genetic Evolutionary Computation Conference, pp. 1330-1337, 2001.
[18] J. Gomez, F. Gonzalez, and  D. Dasgupta. "An Immuno-Fuzzy Approach to Anomaly Detection" Proceedings of the 12th IEEE International Conference on Fuzzy Systems, Vol. 2, pp. 1219-1224, 2003.
[19] J. Gomez and D. Dasgupta. "Evolving Fuzzy Classifiers for Intrusion Detection"  Proceedings of the IEEE, North American Fuzzy Information Processing Society Conference on Fuzzy Learning. pp. 469- 474, 2002
[20] J. Gomez, O. Nasraoui, D. Dasgupta, and F. Gonzalez. "Complete Expression Trees for Evolving Fuzzy Classifier Systems with Genetic Algorithms and Application to Network Intrusion Detection." Proceedings of the IEEE, North American Fuzzy Information Processing Society Conference on Fuzzy Learning, pp.469-474, 2002.
[21] J. Gomez and D. Dasgupta. "Using Competitive Operators and a Local Selection Scheme in Genetic Search." Proceedings (Late-Breaking) of the Genetic and Evolutionary Computation Conference, pp. 193-200, 2002.
[22] F. Hofmann  “Soft Computing Techniques for the Design of Mobile Robot Behaviours." Journal of Information Sciences, Vol. 122. No. 2-4, pp. 241-258, 2000. 
[23] F. Hofmann and G. Pfister "A New Learning Method for the Design of Hierarchical Fuzzy Controllers Using Messy Genetic Algorithms."  6th International Fuzzy Systems Association World Congress Vol. 1, pp. 249-252, 1995
[24] M. M. Chowdhury and Yun Li "Messy Genetic Algorithm Based New Learning Method for Structurally Optimised Neurofuzzy Controllers." Proceedings of the IEEE International Conference on Industrial Technology. pp. 274-278, 1996 
[25] W. Lee and S. Stolfo. "Data mining approaches for intrusion detection." Proceedings of the 7th USENIX security symposium , pp. 79-94, 1998.
[26]  http://kdd.ics.uci.edu/database/kddcup99.
[27] http://www.cs.cornel.edu/projects/kddcup