\documentstyle[eclepsf]{article} \textheight 260mm \topmargin 5mm
\textwidth 180mm \oddsidemargin -7mm

\pagestyle{myheadings}
%%\markright{(ANNIP'2005 -- at Barcelona, Spain)}
\thispagestyle{empty}

\begin{document}
\begin{Large}

%% --- (title) ---
\begin{center}
{\LARGE {\bf
Network intrusion might be like needles in hay.\\
\hspace*{2in}\\
How can we detect them?
}} \\
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\ 
Akira Imada  \\
\hspace*{1in}\\
Brest State Technical University \\ 
Belarus
\end{center}

% --------------------
\clearpage
\begin{itemize}
\item One spiecis of iris flower represent abnormal while others normal?
\item An abnormal transaction is far enough from normal?
\item Can a system be trained only by abnormal sample?
\item Can artificial ant colony find needles?
\end{itemize}

% --------------------
\clearpage
\begin{center}
{\bf When an iris flower is normal then are others abnormal?}\\
\hspace*{1in}\\
{A visualization of IRIS data by Sammon Mapping}
\end{center}
\begin{figure}[h]
\begin{center}
\epsfile{file=final-2d.eps,width=18cm,height=8cm}
\end{center}
\end{figure}

% --------------------
\clearpage
\begin{center}
{\bf The data from KDD challange cup 98}\\
\hspace*{1in}\\
\hspace*{1in}\\
4,920,210 data are given\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
each is made up of 42 attributes of which\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
4-crisp + 17-binary + 6-integer + 15-real\\
\hspace*{1in}\\
\hspace*{1in}\\
\noindent
Still infinitely large area of not-defiened possible transactions remain!
\end{center}

% -------------------
\clearpage
\begin{center}
{\bf Ayara's Random Anomaly in 8-bit Binary Universe}\\
\end{center}
\hspace*{1in}
\begin{itemize}
\item self non-self descrimination by negative selection metapor
\item self $\Rightarrow$ (e.g.) normal network traffic between computers
\item candidate non-self detector $\Rightarrow$ by "If match?" with self-data exhaustively
\end{itemize}

\begin{figure}[h]
\begin{center}
\epsfile{file=ayara.eps,width=8cm,height=4cm}
\end{center}
\end{figure}



% -------------------
\clearpage
{\bf Exhaustive detector generating algorithm (Forrest, Perersen et al 1994)}
%%{\bf Negative Selection -- Exhaustive Search}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=negative-s.eps,width=12cm,height=6cm}
\end{center}
\end{figure}


\begin{center}
152 and 160 abnormal patterns out of $2^8 = 256$ search points.\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Asserted that successfully trained.
\end{center}

%% --- our problem might remind us of also a schematic skecth on fictitious 2D-space
\clearpage
\begin{center}
{\bf A Needle in a Haystack}\\

\hspace*{1in}\\
A schematic skecth on fictitious 2D-space
\end{center}

\begin{figure}[h]
\begin{center}
\epsfile{file=a-needle-0.eps,width=15cm,height=3cm}
\end{center}
\end{figure}

\noindent
The original Hinton \& Nowlan's Needle: 
\begin{itemize}
\item A-needle $\Rightarrow$ Only one configuration of 20 bits of binary string.
   \begin{itemize}
   \item[$\star$] We don't know where the needle locates, but God knows.
   \end{itemize}
\item Haystack $\Rightarrow$ $2^{20}-1$ search points
\end{itemize}

%% --- 
\clearpage
\begin{center}
{\bf How can we train the detector?}\\
\end{center}

\begin{figure}[hbtp]
\begin{center}
\epsfile{file=needle-b-box.eps,width=13.5cm,height=6cm}
\end{center}
\end{figure}

\begin{center}
Can we train it with most likely haystack points?
\end{center}

%% ---
\clearpage
\begin{center}
{\bf How could we break a pincode of ATM?}\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Also a needle in a haystack!\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Would a population search work?\\
\hspace*{1in}\\
(2 4 3 8)\\
(0 9 5 7)\\
(3 2 2 4)\\
......\\
\end{center}


\clearpage
\begin{center}
Lifetime Learning -- Baldwin Effect (Hinton \& Nowlan 1993)
\end{center}

\begin{figure}[hbtp]
\begin{center}
\epsfile{file=a-needle-0.eps,width=10cm,height=2cm}
\end{center}
\end{figure}

\hspace*{1in}\\
\begin{center}
Population search + learning\\
\hspace*{1in}\\
(1 1 0 0 1 ? 0 ? 1 1 0 ? 1 0 0 ? 1 ? 0 1)\\
(0 0 1 ? 1 0 0 1 1 ? 0 0 1 1 0 1 1 1 ? 1)\\
(1 1 1 1 0 0 0 0 0 1 ? ? 0 0 1 0 ? 1 0 1)\\
......\\
\end{center}

%% --- 
\clearpage
\begin{center}
{\bf How difficult?}\\
\hspace*{1in}\\
Random Search
\hspace{.2in}
$\Rightarrow$
\hspace{.2in}
$2^{20} = 1,048,576$
\end{center}

%% ---
\clearpage
\begin{center}
{\bf Random Search}
\end{center}

\begin{figure}[h] 
\begin{center}
\epsfile{file=mesa-random.eps,width=14cm,height=6cm}
\end{center}
\end{figure}

\begin{center}
$\Downarrow$ \\
\hspace*{1in}\\
Placebo $\Rightarrow$ Criteria of Comparison
\end{center}


%% ---
\clearpage
\begin{center}
{\bf Yet another needles in hay --- even-n-parity}\\
\hspace*{1in}\\
\hspace*{1in}\\
Strange behavior of Even-n-parity constructed with only XOR and EQ 
\end{center}

%% ---
\clearpage
\begin{center}
{\bf An even-n-parity}\\
\end{center}

\begin{figure}[h]
\begin{center}
\epsfile{file=parity-3-by-nn.eps,width=15cm,height=8cm}
\end{center}
\end{figure}



%% ---
\clearpage
\begin{center}
{\bf A strange behavior of even-n-parity when made up of XOR and EQ}\\
\end{center}

\begin{figure}[h]
\begin{center}
\epsfile{file=parity-3.eps,width=15cm,height=8cm}
\end{center}
\end{figure}


%% ---
\clearpage
\begin{center}
T. Yu \& J. Miller (2002)\\
Finding Needles in Haystacks is Not Hard with Neutrality (EuroGP)\\
\hspace*{1in}\\
\hspace*{1in}\\
  vs\\
\hspace*{1in}\\
\hspace*{1in}\\
M. Collins (2004)\\
Finding Needles in Haystacks is Harder with Neutrality (GECCO) \\
\end{center}

%% ---
\clearpage
\begin{center}
{\bf Experiment on even-12-parity by T. Yu \& J. Miller (2002)}\\
\hspace*{1in}\\
Neutral Mutation\\
%%\hspace*{1in} \\
$\Downarrow$  \\
%%\hspace*{1in} \\
more than 55 success from 100 runs each max of 10,000 iterations \\
\hspace*{1in} \\
\hspace*{1in} \\

Random Search \\
%%\hspace*{1in} \\
$\Downarrow$  \\
%%\hspace*{1in} \\
never succeeded in 4,000,000 trials.
\end{center}

%% ---
\clearpage
\begin{center}
{\bf GA by T. Yu \& J. Miller (2002)}\\
\hspace*{1in}\\
\begin{itemize}
\item[1.] Generate an initial population of 5 chromosomes at random.
\item[2.] Select one chromosome at random.
\item[3.] Create 4 chromosomes by giving a mutation 4 timrd to the cromosome selected above
\item[4.] Select a winner from the current population using the following rules:
\begin{itemize}
\item[(1)] If any offspring has a better fitness, it becomes the winner.
\item[(2)] Otherwise, an offspring is randomly selected. 
\item[(3)] If the parent-offspring pair has a Hamming distance within the permitted range
the offspring becomes the winner.
\item[(4)] Otherwise, the parent remains as the winner.
\end{itemize}
\item[5.] Repeat 3 -- 4.
\end{itemize}
\end{center}
%%1. Randomly generate an initial population of 5 genotypes with the lowest possible
%%fitness and select one (randomly) as the winner.
%%2. Carry out point-wise mutation on the winning parent to generate 4 offspring;
%%3. Construct a new generation with the winner and its offspring;
%%5. Go to step 2 unless the maximum number of generations reached or a solution
%% with needle fitness is found.

%% ---
\clearpage
\noindent
%%{\bf $\Box$ We have attacked this problem with lately reported approaches}\\
{\bf $\Box$ Snapshot of our ongoing works}\\

\begin{itemize}
\item Fuzzy Rule
\item Artificial Immune System
\item Evolutionary Computation
\item Data-mining Technique
\item etc
\end{itemize}

\hspace*{1in}\\
As needle is crisp:\\
\hspace*{1in}{\it a-needle-in-a-haystack} $\Rightarrow$ {\it a-tiny-island-in-a-huge-lake}


%% ---
\clearpage
\noindent
\begin{center}
{\bf All claim it  very SUCCESSFUL.}\\
\hspace*{1in}\\
Aren't they too optimistic?\\
\hspace*{1in}\\
$\Downarrow$ e.g.\\
\hspace*{1in}\\
Kim \& Bentley (2001) claimed \\
\hspace*{1in}\\
assuming one family of IRIS is abnormal while other two normal\\
\hspace*{1in}\\
\hspace*{1in}\\
TP (Successful Detection Rate) reached 100\%  \\
FP (False Alarm Rate) was only 1\%.

\end{center}

%% --- (Figure) ---
\clearpage
\noindent
\begin{center}
{\bf O.K. Let's check them one by one...}
\hspace*{1in}\\
\hspace*{1in}\\
{\bf I. Can a  set of Fuzzy-rules search for the tiny-island?}
\end{center}

%% ---
\clearpage
\noindent
{\bf $\Box$ A simplest approach\\
\hspace*{.6in}with membership-functions whose shape and location are fixed.}\\

\begin{figure}[h]
\begin{center}
\epsfile{file=member-s.eps,width=7cm,height=2.5cm}
\end{center}
\end{figure}
\begin{center}
$\Downarrow$ \\
\hspace*{2.5in}\\
How many rules we need?\\
\hspace*{2.5in}\\
$(M M M M M M \cdots M)$ \\
\hspace*{2.5in}\\
$\Downarrow$ \\
\hspace*{2.3in}\\
IF \{$x_1$ is Middle\}, $\cdots$, and \{$x_{20}$ is Middle\} THEN no-self.
\end{center}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Island in the 6-D lake}\\  

\begin{center}
Fairly large island ($x_i \in [0.25, 0.75]$) 
\hspace{.1in}
vs.
\hspace{.1in}
Small island ($x_i \in [0.45, 0.55]$)\\
\hspace*{2.5in}\\
$\Downarrow$ \\
\end{center}

\begin{figure}[h]
\begin{center}
\epsfile{file=result-fuz2.eps,width=14cm,height=5.5cm}
\end{center}
\end{figure}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Training with Non-self}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=fitness-19.eps,width=8cm,height=6cm}
\epsfile{file=fitness-20.eps,width=8cm,height=6cm}
\end{center}
\end{figure}

\clearpage
\noindent
{\bf $\Box$ With Gaussian Membership Function.\\
\hspace*{1in} --- Evolving both shape and location.}


\clearpage
\noindent
{\bf $\Box$ What is Fuzzy Rule Extraction?} \\

\begin{center}
To extract knowledge (rules) from  data given.\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
Assume all the data are $n$-dimensional. \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
Then rules are like\\
\hspace*{1in}\\
IF ($x_1$ is $A_1^k$) and $\cdots$ and ($x_n$ is $A_n^k$)
THEN ($y_1$ is $\nu_{k1}$)  and $\cdots$ and ($y_m$ is $\nu_{km}$) \\
\hspace*{1in}\\
where $y_i$ is a likliness of each of $m$ classes.
\end{center}

\clearpage
\noindent
{\bf $\Box$ A Fuzzy Neural Network Approach}
\begin{figure}[h]
 \begin{center}
   \epsfile{file=fuzzy-nn.eps,width=15cm,height=7.5cm}
 \end{center}
\end{figure}


%% --- (Figure) ---
\clearpage
\noindent
{\bf A result of an evolution}

\begin{center}
{\it M}\\
\hspace*{2.5in}\\
$\Downarrow$ 
\end{center}

\begin{figure}[h]
 \begin{center}
   \epsfile{file=mu-1.eps,width=7cm,height=3.5cm}
 \end{center}
\end{figure}

%% ---
\clearpage
\hspace*{1in}\\
\begin{center}
{\bf 
While usually we have huge NORMAL samples, \\
we don't know many ABNORMAL samples\\ 
(when we know them it's too late) \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Can training be performed only by using NORMAL samples? \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
a-needle or tiny-island\\
as test-data to design a network intrusion detector.
}
\end{center}

%% ---
\clearpage
\noindent
\begin{center}
{\bf III. An immune approach --- Constant-sized hyper-shpere Detectors}
\hspace*{1in}\\
\end{center}

\begin{figure}[h]
\begin{center}
\epsfile{file=negative-s.eps,width=12cm,height=6cm}
\end{center}
\end{figure}

%% ---
\clearpage
\noindent
{\bf $\Box$ A result in 2-D space}
\begin{figure}[h]
\begin{center}
\epsfile{file=detector.eps,width=12cm,height=6cm}
\end{center}
\end{figure}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ What if top area shrinks to zero?}\\

\begin{figure}[h]
\begin{center}
%% \epsfile{file=result-2.eps,width=6.0cm,height=4.6cm}
\epsfile{file=result-1.eps,width=14cm,height=6cm}
%\caption{The number of iteration required to find 500 successful detectors 
%         (Left), and the number of successes when 500 detectors tried to 
%          detect 500  non-self samples, 
%          that is, the number of successes out of 25000 events (Right). 
%          Both are as a function of value of $a$ 
%          when we experimented with the Algorithm-1 
%          with $r_s = 0.1$ in 2-dimensional space.
\end{center}
\end{figure}

%% --- (Figure) ---
\clearpage
\noindent
{\bf $\Box$ Alas! As dimension grows...}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=t-positive.eps,width=14cm,height=8cm}
\end{center}
\end{figure}


\clearpage
\noindent
{\bf $\Box$ Conclusion}\\
\begin{center}
{\bf 
Results have not been wonderful at all AS THEY CLAIMED.\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Worse than Placebo experiment?\\
\hspace*{1in}\\
Or, experiments have sometimes reversed our expectations. \\
\hspace*{1in}\\
We now are negative more or less, but still want to be neutral.
}
\end{center}

%% ----- motivation -----
\clearpage
\begin{center}
{\bf
Our Interest here\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
a NETWORK INTRUSION DETECTION SYSTEM\\
\hspace*{1in}\\
in which \\
\hspace*{1in}\\
we need a set of TEST-DATA  \\
\hspace*{1in}\\
to TRAIN and TEST the system with.\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
a consideration on such a test-data.
}
\end{center}

%% --- 
\clearpage
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\begin{center}
{\bf 
So many artificial data-samples have been proposed so far. \\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Let's categorize them 
}
\end{center}

% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample --- Type I}
\begin{figure}[h]
 \begin{center}
\epsfile{file=universe-minus-2.eps,width=4.5cm,height=6cm}
\end{center}
\end{figure}

\begin{center}
{\large{\bf
E.g., \\
Fisher's IRIS Flower \\
KDD-cup 1999/2003 \\
$\cdots$
}}
\end{center}


%% --- forgery
\clearpage
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\
\begin{center}
{\bf GUCCI vs. GUCCI-made-in-Hong-Kong \\
      \hspace*{3in} (Yet another from Istanbul, etc.)}\\
\end{center}

% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample --- Type II}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=universe-minus-1.eps,width=10cm,height=6cm}
\end{center}
\end{figure}

\noindent
{\large
\hspace*{1.7in}Fisher's IRIS Flower \hspace{0.85in}Ayara et al.\\
\hspace*{1.7in}KDD-cup 1999/2003    \hspace{0.85in}$\cdots$ \\
\hspace*{1.7in} $\cdots$
}

% ---
\clearpage
\noindent
{\bf $\Box$ Ayara's Random Anomaly in 8-bit Binary Universe}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=ayara.eps,width=8cm,height=4cm}
\end{center}
\end{figure}

\begin{center}
152 and 160 abnormal patterns out of $2^8 = 256$ search points.\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
Asserted that successfully trained.
\end{center}

% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample --- Type II}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=universe-minus-1.eps,width=10cm,height=6cm}
\end{center}
\end{figure}

\noindent
{\large
\hspace*{1.7in}Fisher's IRIS Flower \hspace{0.85in}Ayara et al.\\
\hspace*{1.7in}KDD-cup 1999/2003    \hspace{0.85in}$\cdots$ \\
\hspace*{1.7in} $\cdots$
}

% ---
\clearpage
\noindent
{\bf $\Box$ What if abnormal sample are only a few?}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=ayara-2.eps,width=8cm,height=4cm}
\end{center}
\end{figure}
\begin{center}
Still can we train the system with normal and abnormal sample?
\end{center}

% ---
\clearpage
\noindent
{\bf $\Box$ Fictitious 2-D pictures of test-sample --- Type III}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=universe.eps,width=16cm,height=6cm}
\end{center}
\end{figure}

\noindent
{\large
\hspace*{0.45in}Fisher's IRIS Flower \hspace{0.95in}Ayara et al. \hspace{1.15in}None so far\\
\hspace*{0.45in}KDD-cup 1999/2003    \hspace{0.95in}$\cdots$ \\
\hspace*{0.45in} $\cdots$
}

%% --- 
\clearpage
\noindent
{\bf $\Box$ Three of our claims.}
\begin{itemize}
\item[1.] Data should cover the whole universe.
\item[] \hspace*{1in}$\Rightarrow$ We could miss crucial abnormal in 
                                   no-defined area. \\
\item[2.] Abnormal Sample should be assumed extremely tiny. 
\item[]   \hspace*{1in}$\Rightarrow$ This is of usual case. \\
\item[3.] Can we train the sytem only by NORMAL data?
\end{itemize}

%% --- forgery
\clearpage
\begin{center}
{\bf A sommelier who is trained only by real champagne \\
can tell the difference when given a bootleg or other sparkling wine?}\\
\hspace*{1in}\\
\hspace*{1in}\\
{\bf How about Caviar?}\\
\hspace*{1in}\\
\hspace*{1in}\\
{\bf Forgery coins recognition?}
\end{center}

%% ---
\clearpage
\begin{center}
{\bf
Our Goal is \\
\hspace*{1in}\\
to search for only a few ABNORMAL (no-self) pattern \\
\hspace*{1in}\\
hidden in \\
\hspace*{1in}\\
an enormous amount of NORMAL (self) patterns\\
\hspace*{1in}\\
by \\
\hspace*{1in}\\
training using only NORMAL patterns
}
\end{center}

%% --- Our peculiar fitness landscape is somehow ...
\clearpage
\noindent
{\bf $\Box$ A test-sample
-- A tiny-flat-island-in-a-huge-lake}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=universe-2.eps,width=4cm,height=4cm}
\end{center}
\end{figure}

\begin{itemize}
\item Lake  $\Rightarrow$ $n$-D Hypercube where $x_i \in [-1, 1]$ \hspace{.15in} $(i=1, �c,n)$
\item Island $\Rightarrow$ $x_i \in [-a, a]$ \hspace{.25in} $(a < 1)$.\\
\end{itemize}
\noindent
\hspace*{1.5in}--- We can control the complexity by changing the size. \\

%% --- Our peculiar fitness landscape is somehow ...
\clearpage
\noindent
{\bf $\Box$ From a fitness landscape point of view}\\
\begin{figure}[h]
\begin{center}
\epsfile{file=island-1.eps,width=15cm,height=3cm}
\end{center}
\end{figure}

%% --- our problem might remind us of also a schematic skecth on fictitious 2D-space
\clearpage
\noindent
{\bf $\Box$ A Needle in a Haystack}\\

\noindent
A schematic skecth on fictitious 2D-space
\begin{figure}[h]
\begin{center}
\epsfile{file=a-needle-0.eps,width=15cm,height=3cm}
\end{center}
\end{figure}

\noindent
The original Hinton \& Nowlan's Needle: 
\begin{itemize}
\item A-needle $\Rightarrow$ Only one configuration of 20 bits of binary string.
   \begin{itemize}
   \item[$\star$] We don't know where the needle locates, but God knows.
   \end{itemize}
\item Haystack $\Rightarrow$ $2^{20}-1$ search points
\end{itemize}

%% --- 
\clearpage
\noindent
{\bf $\Box$ How can we train the detector?}\\
\begin{figure}[hbtp]
\begin{center}
\epsfile{file=needle-b-box.eps,width=13.5cm,height=6cm}
\end{center}
\end{figure}

\begin{center}
Can we train it with most likely haystack points?
\end{center}

%% --- 
\clearpage
\noindent
{\bf $\Box$ How difficult?}\\
\begin{itemize}
\item Random Search
\begin{center}
$2^{20} = 1,048,576$
\end{center}
\item[]
\item Lifetime Learning -- Baldwin Effect (Hinton \& Nowlan 1993)
\end{itemize}

\begin{figure}[hbtp]
\begin{center}
\epsfile{file=a-needle-0.eps,width=10cm,height=2cm}
\end{center}
\end{figure}

%% ---
\clearpage
\noindent
{\bf $\Box$ Random Search}
\begin{figure}[h] 
\begin{center}
\epsfile{file=mesa-random.eps,width=14cm,height=6cm}
\end{center}
\end{figure}

\begin{center}
$\Downarrow$ \\
\hspace*{1in}\\
Placebo $\Rightarrow$ Criteria of Comparison
\end{center}


\end{Large}
\end{document}






















