\documentstyle[twocolumn,eclepsf]{article}

\textheight 232mm     %% 257mm
\topmargin -5mm       %%   5mm
\textwidth 160mm      %% 170mm
\oddsidemargin -3mm   %%  -2mm

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

\author{Akira Imada\\
        \hspace*{1in}\\
        Brest State Technical University\\
        Moskowskaja 267, 224017 Brest, Republic of Belarus\\
        akira@bsty.by}

\date{}

\begin{document}

\maketitle
\thispagestyle{empty}
\pagestyle{empty}

%%% \documentstyle[eclepsf]{llncs}
%%% \title{Can an immuno-fuzzy approach detect only a few non-self cells
%%% existed in an enormous amount of self cells?}
%%% \author{Akira Imada}
%%% \institute{Brest State Technical University\\
%%%           Moskowskaja 267, 224017 Brest, Republic of Belarus\\
%%%           akira@bsty.by}


%%%%% \begin{abstract}
%%%%% ----------------------------------------------------
\noindent{\it {\bf Abstract: }
We apply a lately reported technique which generates
a set of fuzzy rules to recognize unknown abnormal patterns
only by training with already known normal patterns.
Our concern here is an extreme case where
a  sample of abnormal patterns are crucially smaller than 
the normal ones. 
Experiment is made with a test-data --- 
what we call a-tiny-island-in-a-huge-lake.}\\
%%%%% ----------------------------------------------------
%%%%% \end{abstract}

\hspace*{1in}\\
\noindent
{\it Keywords:  
Fuzzy rule extraction, 
network intrusion detection,
detection of self and non-self cells,
a needle in a haystack.}

\begin{center}
\section*{I. INTRODUCTION}
\end{center}
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 tuckling 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 usually don't know
what do anomaly patterns look like in advance. 
Hence we need to train the system with only normal patterns.
So far, lots of approaches to this problem have been proposed successfully. 
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 anomal pattern is given. \\

\noindent
Our concern, then, is what if the number of normal patterns
is extremely larger than the number of possible anomal patterns, 
which is of usual cases in a network intrusion detection. \\

\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 discribed, in particular, a fitness landscape 
when we searched for a weight configuration 
which gives a network with fully-conected 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 pattern classification problem, in general,
however on the condition 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 its co-ordinates each of whose value 
lies in $[-a,a]$,  while all others  are regarded as normal patters.
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.\\

%%\section* {II. EXPERIMENT}
\begin{center}
{\Large{\bf II. EXPERIMENT}}
\end{center}

\noindent
A set of fuzzy rules is used to cover the non-self patterns. 
As already mentioned,
self/non-self sells 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.\\

\begin{figure}[h]
\begin{center}
\epsfile{file=member-s.eps,width=7cm,height=3.5cm}
\caption{Five fixed shaped membership functions
each of which  discribes how
liklly 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 Dasgupt et al's experiment~\cite{gome}.

\begin{center}
\section*{III. RESULTS \& DISCUSSION}
\end{center}
As a preliminary experiment, we tried a random search
for the 20-dimensional needle by creating 
5000 candidat 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 modern PC. 

\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)$ fullfills
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 successfull 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 smalle island where $x_i \in [0.45, 0.55]$ \hspace{.01in}
         $(i = 1, \cdots, 6)$.}
\end{center}
\end{figure}
In Figure 3. we plot two cases of 
evolution. One is the island is made up of the points 
$x_i \in [0.25, 0.75]$ and the other is $(i = 1, \cdots, 6)$.
both in the 6-dimensional lake, which 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 from here. 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
{\it MIDDLE}.


\begin{center}
\section*{IV. CONCLUSION}
\end{center}
We have descrived 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 metaphore in which
a very few of unpredictable abnormal transaction patterns 
hidden in a 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.



\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{prov}
F. Provost, T. Fawcett, and R. Kohavi (1989)
``The case against accuracy estimation for comparing induction algorithms.''
Proceedings of international conference on machine learning, (San Francisco, Ca),
pp. 445--453.

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

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

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


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


