\documentstyle[twocolumn,eclepsf,IEEEtran]{article}

\def\BibTeX{{\rm B\kern-.05em{\sc i\kern-.025em b}\kern-.08em
    T\kern-.1667em\lower.7ex\hbox{E}\kern-.125emX}}
\def\bs{-0.5ex}
\newtheorem{theorem}{Theorem}

\begin{document}

\title{{\LARGE {\bf Can an Immuno-fuzzy Approach Detect Only
a Few Non-self Cells Existed in an Enormous Amount of Self Cells?}}\\ [\bs]}

\author{\hspace*{1in} \\
{\bf Akira Imada} \\
            \normalsize Brest State Technical University, Belarus \\ [\bs]}
            %% \normalsize Moskowskaja 267, 224017 Brest, Belarus \\ [\bs]
            %% \normalsize akira@bstu.by \\ [\bs]
\pagestyle{empty}
\maketitle

\begin{abstracttext}
\noindent
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, what 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 extremely few comparing to  
the normal ones, and what if it eventually shrinks to zero, which is
what they call a-needle-in-a-haystack.
\end{abstracttext}


\bigskip
\section{Introduction}
\noindent
This paper reports a snapshot of our on-going experiments 
in which a common target we call {\it 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 {\it huge lake} are normal while 
ones found on the {\it tiny island} are abnormal.
Our goal here is twofold. One is to know 
{\it whether or not it is possible
to train a system using just normal data alone.}
The other is to study {\it a limit of the size of the detectable area},
when we decrease the size of the island 
eventually shrinking to zero, equivalently  so-called
{\it 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.\\

\begin{figure}[hb]
 \begin{center}
 \epsfile{file=a-needle-0.eps,width=8cm,height=1.5cm}
 \caption{A fictitious sketch of fitness landscape of 
          {\it a-needle-in-a-haystack}. The haystack here is drawn 
          as a two-dimensional flat plane of fitness zero.}
 \end{center}
\end{figure}

\noindent
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 cases.
Then our concern is how we can train a system
with a lack of negative training data.\\

\noindent
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. 
In other words, 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.\\


\noindent
{\it ``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~\cite{akir}, 
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.\\

\noindent
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 $[-1,1]$. This construct 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.\\

\bigskip
\section{EXPERIMENT}
\noindent
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_1, \cdots, x_n)$ where $x_i \in [-1,1]$.
Then a fuzzy rule to detect non-self patterns is
\vspace{.025in}
\begin{center}
{\it
If $x_1$ is $T_1$, $\cdots$, and $x_n$ is $T_n$ then {\bf x} is non-self
}
\end{center}
\vspace{.025in}
where $T_i$ is a fuzzy linguistic terms which is either one of 
{\it \{Low, Low-Middle, Middle, Middle-High, High\}.}
Each of $T_i$ maps the $x_i$ 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 sence too, this test-set is a good one.

\begin{figure}[h]
\begin{center}
\epsfile{file=member-s.eps,width=7cm,height=3.5cm}
\caption{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.}
\end{center}
\end{figure}


\noindent
Then a genetic algorithm evolves these fuzzy rules,
with chromosomes being $(T_1, \cdots, T_n)$, 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 
$\mbox{\bf x} = (x_1, \cdots, x_n)$, one by one, and calculated as

\begin{displaymath}
\mbox{fitness} (R) = 1 - \max_{\mbox{\bf x} \in Self} 
\{ \min_{i=1, \cdots, n} \{ \mu_{T_i} (x_i)\}\}
\end{displaymath}
\noindent
which implies how the rule covers the non-self space.\\

\noindent
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~\cite{gome}.

\bigskip
\section{RESULTS \& DISCUSSION}
\noindent
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 Figure.~2, and we found
it is still not such a difficult problem if we use
a standard PC found everywhere nowadays.\\ 

\begin{figure}[h]
\begin{center}
\epsfile{file=mesa-random-modified.eps,width=7cm,height=4cm}
\caption{The number of happened-to-be-the-needle out of 
          5000 random creations of the candidate.}
\end{center}
\end{figure}
\noindent
Then what will happen if we exploit one of the lately reported
more sophisticate methods? \\

\noindent
As our goal is to find a rule to identify an island, that is
whether or not the search point {\bf x} $=(x_1, \cdots, x_n)$ fulfills
the condition that $ -a < x_i < a$ for all $i = 1, \cdots, n$, all we
need is one rule, that is,
\begin{center}
{\it IF $x_1$ is Middle, and $\cdots$, and $x_{n}$ is Middle}
\end{center}
\hfill {\it THEN {\bf x} is on the island.}\\

\noindent
And we found an evolution converges to a successful such chromosome 
\begin{center}
(2 2 2 2 2 2).
\end{center}
However, this holds only on the condition that 
the dimension is small and the island is fairly large.
\begin{figure}[t]
\begin{center}
\epsfile{file=result.eps,width=8cm,height=5cm}
\caption{Evolution to find the island in the 6-dimensional lake.  
         Upper plot is when $x_i \in [0.25, 0.75]$ and lower plot is 
         for a small island where $x_i \in [0.45, 0.55]$ \hspace{.01in}
         $(i = 1, \cdots, 6)$.}
\end{center}
\end{figure}
In Figure~4. we plot two cases of 
evolution. One is the island made up of the points 
$x_i \in [0.25, 0.75]$ and the other is 
$x_i \in [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 {\it a-needle-in-a-haystack}
is far beyond from this critical point. A trial of a search 
for the island of $x_i \in [0.45, 0.55]$ \hspace{.01in}
$(i = 1, \cdots, 20)$
in the 20-dimensional 
lake converged a chromosome
\begin{center}
(0 1 3 4 0 4 4 1 4 4 1 1 4 1 4 3 0 0 0 2).
\end{center}
Alas, the curse of dimensionality.\\

\noindent
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 {\it MIDDLE}.

\noindent
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.
That is, the dataset is 10\% version of KDD-CUP99 
removing all the categorical 
attributes, which results in the 492021 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\%.
%%Wonderful result, isn't it?
%%Comparing to our poor results, what is the difference?
The difference between two experiments is size of abnormal samples,
whch suggests the method proposed by Gomez et al.~works
when number of abnormal samples and normal sample is similar.
Otherwise, i.e., 
when we are to look for one of a few abnormal samples
embedded in huge normal samples, the method does not work. 


\bigskip
\section{CONCLUSION}
\noindent
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.\\

\noindent
We need test samples to test the system we are designing.
So far, so many such sample are proposed. For example,
Ayara et al.~\cite{ayar} used randomly generated 8-bit binary patterns 
assuming they are  normal patterns;
Kim \& Bentley~\cite{kim} 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.~(2004)~\cite{gome}
used the 1998 DARPA intrusion detection evaluation data-set prepared by MIT,
also known as KDD cup 99 
data-set.\footnote{http://kdd.ics.uci.edu/databases/kddcup99}
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.\footnote{http://www.cs.cornell.edu/projects/kddcup}\\

\noindent
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.
\begin{itemize}
\item[(1)] dataset is comprised of all possible patterns. 
\item[(2)] Training should be only by normal samples
\item[(3)] Number of normal sample should be enormous while abnormal sample is only a few. 
\end{itemize}
When an iris flower is normal then are others abnormal?
None of the above mentioned examples fulfills all of the three conditions.\\

\noindent
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.\\

\noindent
We hope this article will play a role of call for challenges to this issue.



\bigskip
\begin{thebibliography}{99}

\bibitem{akir}
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.

\bibitem{gome}
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.


\bibitem{ayar} 
M.~Ayara, J.~Timmis, R.~D.~Lemos, L.~N.~D.~Castro, and R.~Duncan (2002) 
"Negative Selection: How to Generate Detectors." 
Proceedings of 1st International Conference on Artificial Immune Systems
pp.~89--98.

P. Helman and S. Forrest (1994)
"An Efficient Algorithm for Generating Random Antibody Strings." 
Technical Report 94-07, University of New Mexico, Albuquerque, NM.



P. D'haeseleer, S. Forrest, and P. Helman (1996)
"An immunological approach to change detection: algorithms, analysis and implications."
Proceedings of the 1996 IEEE Symposium on Computer Security and Privacy, pp. 110--119.

F. Esponda, S. Forrest (2002)
"Detector coverage under the r-contiguous bits matching rule."
University of New Mexico Technical Report TR-CS-2002-03.

F. Esponda, S. Forrest, and P. Helman (2004)
"A formal framework for positive and negative detection." 
IEEE Transactions on Systems, Man, and Cybernetics 34:1 pp. 357-373.


\bibitem{kim}
J.~Kim and P.~J.~Bentley (2001)
``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.

Clonal Selection
J. Kim and P. Bentley 
"An Artificial Immune Model for Network Intrusion Detection"


Positive Selection
Kwee-Bo Sim and Dong-Wook Lee (2003)
"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</A>

Negative Selection
Dasgupta, et al (1999) "An Anomaly Detection Algorithm
Inspired by the Immune System." 
Dasgupta et al. (Eds), Artificial Immune System and Their Application

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

F. Gonzalez, D. Dasgupta (2003)
"Anomaly Detection Using Real-Valued Negative Selection."
Genetic Programming and Evolvable Machines, Vol. 4 No. 4, 
Kluwer Academic Press, pp 383-403. </A>

F. Gonzalez, D. Dasgupta and L. F. Nino (2003)
"A Randomized Real-Valued Negative Selection Algorithm."
Proceedings of the 2nd International Conference on Artificial Immune Systems,

[12] Gonzalez, F., D. Dasgupta, J. Gomez (2003)
"The Effect of Binary Matching Rules in Negative Selection." 
GECCO-03.
</UL><BR>

D. Dasgupta and N. S. Majumdar (2002)
"Anomaly detection in Multidimensional Data using Negative Selection algorithm."
Proceedings of the Congress on Evolutionary Computation</A>

Ceong, H. T., et al, (2003)
"Complementary Dual Detectors for Effective Classification."
ICARIS-03, pp.242-248.

J. Kim and P. Bentley (2001)
"An evaluation of negative selection in an artificial 
immune system for network intrusion detection."
Proceedings Genetic Evolutionary Computation Conference </A>

Immuno-fuzzy Approach
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.

Fuzzy Rules not based on Immune System but Evolved by Genetic Algorithm
J. Gomez and D. Dasgupta
"Evolving Fuzzy Classifiers for Intrusion Detection" </A>

J. Gomez, O. Nasraoui, D. Dasgupta, and F. Gonzalez (2002)
"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.

J. Gomez and D. Dasgupta (2002)
"Using Competitive Operators and a Local Selection Scheme in Genetic Search." 
Proceedings (Late-Breaking) of the Genetic and Evolutionary Computation Conference,
pp. 193-200.

Messy-GA Approach

F. HOFFMANN
Soft Computing Techniques for the Design of Mobile Robot Be-
haviours"


F. Hofmann and G. Pfister (1995)
"A New Learning Method for the Design of Hierarchical Fuzzy Controllers
Using Messy Genetic Algorithms"

M. M. Chowdhury and Yun Li
"Messy Genetic Algorithm Based New Learning Method
for Structurally Optimised Neurofuzzy Controllers"

Yet Another Intrusion Detection --- Data Mining Approach
W. Lee and S. Stolfo (1998) 
"Data mining approaches for intrusion detection"
Proceedings of the 7th USENIX security symposium (San Antonio, TX).






\end{thebibliography}
%%\end{tiny}
\end{document}


