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

\newtheorem{algorithm}{Algorithm}

\pagestyle{myheadings}
\markright{(ICNNAI'2006 -- at Brest, Belarus )}
\thispagestyle{empty}

\begin{document}
\begin{huge}

%% --- (title) ---
\begin{center}
{\bf How Many Parachutists will be Needed to Find \\ a Needle in a Pastoral?} \\
\hspace*{1in}\\
\hspace*{1in}\\
\hspace*{1in}\\ 
Akira Imada  \\
\hspace*{1in}\\
Brest State Technical University \\ 
Belarus
\end{center}

\clearpage
\begin{center}
{\bf  Simple Gene}\\
\end{center}

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

\clearpage
\begin{center}
{\bf  A Neutrality}\\
\end{center}

\begin{figure}[h]
 \begin{center}
 \epsfile{file=gene-2.eps,width=16cm,height=3.0cm}
 \end{center}
\end{figure}


\clearpage
\begin{center}
{\bf  Intron}\\
\end{center}

\begin{figure}[hb]
 \begin{center}
 \epsfile{file=gene-3.eps,width=10cm,height=3.5cm}
 \end{center}
\end{figure}


\clearpage
\begin{center}
{\bf  How to design an Intrusion Detection System \\ intelligently, if any?}\\
\end{center}
\begin{itemize} 
\item Two categories of detection
   \begin{itemize}
   \item[$\star$] {\it Misuse} detection $\cdots$ to recognize known attack. 
   \item[$\star$] {\it Anomaly} detection $\cdots$ to detects unknown not-normal. \\
   \end{itemize}
\end{itemize}

\noindent
Isn't it meaningful to detect known attacks? \\
\hspace*{2.8in} $\Rightarrow$ Isn't just a lookup table enough?


\clearpage
\begin{center}
{\bf  General assumption:}\\
\end{center}

\begin{itemize} 
\item TCP/IP connection to a network
   \begin{itemize}
   \item[] $\Rightarrow$ can be represented by a $n$-dimensional vector
   \end{itemize}
\end{itemize}

\clearpage
\begin{center}
{\bf  Our Goal}\\
\end{center}

\noindent
$\bullet$ Is a vector input to our system a {\it Normal} or an {\it Attack}?

\begin{figure}[hb]
 \begin{center}
 \epsfile{file=b-box.eps,width=12cm,height=3.5cm}
 \end{center}
\end{figure}

\noindent
\begin{itemize}
\item A successful result might be
   \begin{itemize}
   \item[] {\it Accurately Detected Rate} $>$ 90\%
   \item[]{\it False Alarm Rate} $<$ 10 \%
   \end{itemize}
\end{itemize}


\clearpage
\begin{center}
{\bf  Training \& Testing}\\
\end{center}

\bigskip
\noindent
We need a testset when we want a supervised methods

\bigskip
\begin{itemize}
\item Frequantly used two public domain dataset.
   \begin{itemize}
   \item[$\star$] Spearman's IRIS flower dataset.
   \item[$\star$] KDD-cup-1999 dataset
   \end{itemize}
\end{itemize}

\clearpage
\begin{center}
\hspace*{1in}\\
\hspace*{1in}\\
   \begin{itemize}
   \item[(1)] {\bf IRIS flower dataset}
   \item[(2)] KDD-cup-1999 dataset
   \end{itemize}
\end{center}



%% --- (iris dataset) ---
\clearpage
\begin{center}
{\bf What is IRIS flower dataset}
\end{center}

\begin{LARGE}
\begin{itemize}
\item 3 families of IRIS flower $\Rightarrow$ 150 samples in total;
\item Each family $\Rightarrow$ 50 samples; Each sample $\Rightarrow$ 4 features.
\end{itemize}
\end{LARGE}

\begin{figure}[hb]
 \begin{center}
 \epsfile{file=iris-family.eps,width=12cm,height=4cm}
 \end{center}
\end{figure}


\clearpage
\noindent
\begin{center}
{\bf When a family of iris flower is normal \\ then are others abnormal?}\\

\hspace*{1in}\\
Castellano et al. (2000) \\

$\Downarrow$\\

assumed one to be normal while the other two abnormal.

$\Downarrow$\\

$\bullet$ abnormal detection rate = 96\%  \\ 
$\bullet$ false alarm rate = 0.6\%
\end{center}


\clearpage
\begin{center}
{\bf Let's Visualize IRIS families --- Sammon Mapping} \\
\hspace*{1in}\\
Sammon Mapping maps points in a high-D space to 2-D \\
\hspace*{1in}\\
by\\
\hspace*{1in}\\
keeping distance relation preserved as much as possible
\hspace*{1in}\\
or \\
distances in the $n$-D space are approximated 
by distances in 2-D space with a minimal error.\\
\end{center}

\clearpage
\begin{center} 
{\bf Sammon Mapping of IRIS families}
\end{center}
\begin{figure}[h]\label{fig:iris}
\begin{center}
     \epsfile{file=iris.eps,width=16cm,height=8cm}
\end{center}
\end{figure}


\clearpage
\begin{center} 
{\bf Where do Outliers lie?}\\
\hspace*{1in}\\
Not in the domain for the other families!!\\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}
\\Not at the point at random, either. \\
\hspace*{1in}\\
$\Downarrow$\\
\hspace*{1in}\\
But outlier usually hides behind Normal. \\
\end{center}


\clearpage
\begin{center}
{\bf A Tugher Charrange: Attacks by Mutant} \\
\end{center}
\hspace*{1in}\\
{\bf $\bullet$ Charrange 1}
{\it
\begin{itemize}
\item[(1)] Pick up {\it Normal} samples at random.
\item[(2)] Mutate the {\it Normal} samples.
\item[(3)] Train your system with half of NORMAL + MUTANT.
\item[(4)] Test the system with remaining NORMAL + MUTANT.
\end{itemize}
}


\clearpage
\begin{center}
\hspace*{1in}\\
\hspace*{1in}\\
{\bf $\bullet$ KDD-cup-1999 dataset}
\end{center}

%% --- (KDD-cup-99 dataset) ---

\clearpage
\noindent
{\bf What are Inside of the KDD-cup-1999 Dataset?} 

\begin{itemize}
\setlength{\itemsep}{0pt}
\item {\it Attack} $\Rightarrow$ {\LARGE 32 attack types of the 4 categories:}
   \begin{itemize}
      \item[$\star$] {\it Probing}
         \begin{itemize}
            \item[] {\LARGE by proving a vulnerability of the network;}
         \end{itemize}
      \item[$\star$] {\it Denial-of-Service (DoS)}
         \begin{itemize}
            \item[] {\LARGE by denying legitimate requests to a system;}
         \end{itemize}
      \item[$\star$] {\it User-to-Root (U2R)} 
         \begin{itemize}
            \item[] {\LARGE an unauthorized access to local super-user or root;}
         \end{itemize}
      \item[$\star$] {\it Remote-to-Local (R2L)}
         \begin{itemize}
            \item[] {\LARGE an unauthorized local access from a remote machine.}
         \end{itemize}
   \end{itemize}
\item {\it Normal}
\end{itemize}


\clearpage
\noindent
{\bf $\Box$ How Big is the KDD-cup-1999 Dataset?}
\begin{itemize}
\item Labeled 4,898,430 records $\Rightarrow$ {\it Training}
\item Un-labeled 311,029 records $\Rightarrow$ {\it Testing}
\end{itemize}
\noindent
Too big for Sammon Mapping!


\clearpage
\begin{center}
{\bf Can Dimension be Reduced?}
\end{center}
\begin{itemize}
\item Kuchimanchi et al.~(2004)
   \begin{itemize}
   \item[$\star$] 41 $\Rightarrow$ 19 (by PCA)
      \begin{itemize}
      \item[$\cdot$] (detection accuracy, false positive) = (99.92\%, 0.26\%)
      \end{itemize}
   \item[$\star$] while the original being
      \begin{itemize}
      \item[$\cdot$] (detection accuracy, false positive) = (99.94\%, 0.23\%)
      \end{itemize}
   \end{itemize}
\item Joshi et al.~(2005)
   \begin{itemize}
   \item[$\star$] 41 $\Rightarrow$ 5
      \begin{itemize}
      \item[$\cdot$] (detection accuracy, false positive) = (79\%, 21\%)
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\begin{center}
{\bf Detection rate From a Report (Sabhnani et al.)}
\end{center}
{\it
\begin{table}[h]
\begin{center}
\begin{tabular}{l c c c c} \hline
\hspace*{.1in}                     & Probe  & DoS  & U2R  &  R2L \\ \hline
Multi-layer Perceptron             & 88.7   & 97.2 & 13.2 & 5.6  \\
Gaussian Classifier                & 90.2   & 82.4 & 22.8 & 9.6  \\
$K$-mean Clustering                & 87.6   & 97.3 & 29.8 & 6.4  \\
Nearest Cluster Algorithm          & 88.8   & 97.1 &  2.2 & 3.4  \\
Radial Basis Function              & 93.2   & 73.0 &  6.1 & 5.9  \\
Leader Algorithm                   & 83.8   & 97.2 &  6.6 & 1.0  \\
Hypersphere Algorithm              & 84.8   & 97.2 &  8.3 & 1.0  \\
Fuzzy Art Map                      & 77.2   & 97.0 &  6.1 & 3.7  \\
C4.5 Decision Tree                 & 80.8   & 97.0 &  1.8 & 4.6  \\ \hline
\end{tabular} 
\end{center}
\end{table}
}

\clearpage
\noindent
{\bf The Result of the KDD-cup-1999 Winner}\\
\hspace*{1in}\\
$\bullet$ Detection rate for 4 attack types

{\it
\begin{table}[h]
\begin{center}
\hspace*{1in}\\
\begin{tabular}{c c c c} \hline
                PROBE  & DoS  & U2R  &  R2L \\ \hline
               83.3\%   & 97.1\% & 13.2\% & 8.4\%  \\ \hline
\end{tabular} 
\end{center}
\end{table}
}

\clearpage
\begin{center}
\hspace*{1in}\\
\hspace*{1in}\\
{\bf $\bullet$ Why, on earth, U2R and R2L attacks resist to be detected?}
\end{center}


\clearpage
\begin{center}
{\bf Attacks in Test Samples}
\end{center}
{\it
\begin{table}[h]
\begin{center}
\hspace*{1in}\\
\begin{tabular}{c c c c c} \hline
\hspace*{.1in} Normal & Probe  & DoS    & U2R    &  R2L   \\ \hline
               19.5\% & 1.3\%  & 73.9\% & 5.2\%  & 0.1\%  \\ \hline
\end{tabular} 
\end{center}
\end{table}
}

\clearpage
\begin{center}
{\bf Two Intelligent(?) Strategies:}
\end{center}
\begin{itemize}
\item {\it always-return-U2R strategy}
   \begin{itemize}
   \item[] which returns U2R whatever the input is.
   \end{itemize}
{\it
\begin{table}[h]
\begin{center}
\begin{tabular}{c c c c} \hline
Probe    & DoS     & U2R    & R2L    \\ \hline
0.0\%    & 0.0\%   & 5.2\%  & 0.0\%  \\ \hline
\end{tabular} 
\end{center}
\end{table}
}
\item {\it always-return-randomly strategy}
   \begin{itemize}
   \item[] which returns either Normal, Probe, DoS, U2R, or R2L at random regardless of the input.
      \begin{itemize}
      \item[] \begin{center}$\Rightarrow$  a high score to detect DoS attacks.\end{center}
      \end{itemize}
   \end{itemize}
\end{itemize}


\clearpage
\begin{center}
{\bf What we Want?}
\end{center} 
\begin{figure}[hb]
 \begin{center}
 \epsfile{file=b-box-kdd.eps,width=16cm,height=8cm}
 \end{center}
\end{figure}


\clearpage
\noindent
{\bf $\Box$ Is it possible?} \\
\begin{Large}
\begin{table}[h]
\begin{center}
\hspace*{1in}\\
\begin{tabular}{l c c c c c c} \hline
\hspace*{.1in}         & Total     & Normal & Probe  & DoS  & U2R  &  R2L \\ \hline
Labeled for Training   & 4,898,430 & 19.9\% & 0.8\%  & 79.3\% & $\approx$ 0.0\% & $\approx$0.0\%\\
Non-labeled for Testing& 311,029   & 19.5\% & 1.3\%  & 73.9\% & 5.2\%           & 0.1\%
\end{tabular} 
\end{center}
\end{table}
\end{Large}


\clearpage
\begin{center}
{\bf $\bullet$ Our 1st Conjecture}\\
\hspace*{1in}\\

{\it Real Attack is like a needle in a haystack.}
\end{center}

\clearpage
\noindent
{\bf A fictitious needle in a haystack in 2D} \\
\begin{figure}[hb]
\begin{center}
\epsfile{file=a-needle-0.eps,width=15cm,height=3cm}
\end{center}
\end{figure}

\clearpage
\begin{center}
{\bf Random Fall of Parachutists}\\
\end{center}
\noindent
{\bf $\bullet$ Algorithm 2}\\
{\it
\begin{itemize}
\item[(1)] Create a $p$-bit octal PIN at random.
\item[(2)] Create randomly one $3p$-bit of binary string.
\item[(3)] Translate the string into $p$-bit octal code. 
\item[(4)] Check if the translated code matches the PIN. 
\item[(5)] If matches, end the run. Otherwise go back to 2.
\end{itemize}
}

\clearpage
\begin{center}
{\bf Parachutists Allowed to Walk after Fall}\\
\end{center}
\noindent
{\bf Algorithm 2}\\
{\it
\begin{itemize}
\item [(5)] If matches, end the run. \\Otherwise give a mutation 
by flipping a bit chosen at random
with a probability of $1/3p$
until the translation matches the PIN, or number of steps exceeds 1000.\\
\end{itemize}
}

\clearpage
\begin{center}
{\bf Random Fall \& Walks after Fall}
\end{center}
\begin{figure}[hb]
\begin{center}
\epsfile{file=parachuters.eps,width=16cm,height=9cm}
\end{center}
\end{figure}


\clearpage
\begin{center}
{\bf But really that efficient?} \\
\end{center}

\begin{figure}[hb]
\begin{center}
\epsfile{file=actual-how-many.eps,width=16cm,height=12cm}
\end{center}
\end{figure}


\clearpage
\begin{center}
{\bf Easier or Harder?}

Yu \& Miller's paper 
{\it ``Finding needles in haystack is not hard with neutrality''} (2002)\\
vs.\\
~Collin's 
{\it ``Finding needles in haystack is harder with neutrality''} (2005).\\
\end{center}

\clearpage
\begin{center}
{\bf Walk by Neutral Mutation}
\end{center}
\noindent
{\bf Algorithm 3}
{\it
\begin{itemize}
\item[(3)] Try point-wise mutation on the genotype such that the result maps 
into the same phenotype as the one  before the mutation.
\item[(4)] Assess all possible single-mutation-neighbors of the new genotype 
to determine whether any new phenotype is discovered.
\item[(5)] Step 3 to 4 are repeated untill the phenotype matches the PIN, or
untill a pre-fixed number of steps is reached. 
\end{itemize}
}

\clearpage
\begin{center}
{\bf Does Neutral Mutation on Intron Enhance Efficiency of Search?}
\end{center}
\noindent
{\bf Algorithm 3}
{\it
\begin{itemize}
\item[(1)] Create a PIN at random.
\item[(2)] Create randomly an initial individual
which is considered to be the winner to the next generation.
\item[(3)] Carry out point-wise mutation on the winning parent to generate 4 offspring.
\item[(4)] Construct a new generation with the winner and its offspring.
\item[(5)] Select a winner from the current population using the following rules. 
      \begin{itemize}
      \item[(i)]  If any offspring has a better fitness than the parent,
           the one with highest fitness becomes the winner.
      \item[(ii)] If fitness of all offspring have the same fitness as the parent,
              one offspring is randomly selected, and
           if the parent-offspring pair has a Hamming distance within the permitted range, 
              the offspring becomes the winner, otherwise the parent remains as the winner.
      \end{itemize}
\item[(5)] Back to step 2 unless the maximum number of generations reaches, or a solution is found.
\end{itemize}
}


\clearpage
\begin{center}
{\bf Even-Parity Problem} \\
\end{center}
\begin{figure}[h]
 \begin{center}
 \epsfile{file=even-5-parity.eps,width=12cm,height=3cm}
 \end{center}
\end{figure}


\clearpage
\begin{center}
{\bf $\bullet$ Our 2nd Conjecture}\\
\hspace*{1in}\\
{\it No such effective algorithm to look for a needle}
\end{center}


\clearpage
\begin{center}
{\bf  ``Artificial Immune System Detects an Attack!'' \\ What a fantastic idea!}\\
\hspace*{1in}\\
Two decads has passed since

\begin{itemize}
\item S.~Forrest, A.~S.~Perelson, L.~Allen, and R.~Cherukuri (1994)
   \begin{itemize}
   \item[] {\it ``Self Nonself Discrimination in a Computer''}
   \end{itemize}
\end{itemize}


but still this is an open issue.\\
\hspace*{1in}\\
$\Downarrow$ \\
\hspace*{1in}\\
We hope not, but isn't it just a fantasy?
\end{center}

\clearpage
\begin{center}
{\bf Attack by Dummy}
\end{center}

\noindent
{\bf $\bullet$ Charrange 2}
{\it
\begin{itemize}
\item[(1)] Prepare two sub-datasets from KDD-cup-1999 dataset.
One is picked up from normal samples and call it  $D_{\mbox{\small normal}}$.
The other is from  attack samples and call it $D_{\mbox{\small attack}}$.
\item[(2)] Furthermore, randomly create an attack dataset -- dummy attacks, and call it 
$D_{\mbox{\small dummy}}$. 
\item[(3)] Train your intrusion detection system only with $D_{\mbox{\small normal}}$.
\item[(4)] Then, try two tests, one with only $D_{\mbox{\small attack}}$, and 
the other with only $D_{\mbox{\small dummy}}$, avoiding any a~priori prediction.
\end{itemize}
}


\clearpage
\begin{center}
{\bf Placebo Experiment}
\end{center}

\noindent
{\bf $\bullet$ Charrange 3}
{\it
\begin{itemize}
\item[(1)] Create a simple device which randomly returns 
either one of Normal, Prove, DoS, U2R, or R2L for any input. 
\item[(2)] Prepare a test dataset including enough amount of 
records uniformly from Normal, Prove, DoS, U2R, and R2L.
\item[(3)] Compare the performances of the detector you designed
with the random-reply-machine created in step 1,
feeding the same dataset prepared in step 2.
\end{itemize}
}


\clearpage
\begin{center}
{\bf Conclusion}
\end{center}

\noindent
a hacker is a person who is extremely good at finding 
a pattern which is very close to the normal traffic\\

%%\hspace*{1in}\\

\noindent
Needless to say, however, this article is not to negate the possibility, but
we hope this will be a serious challenge to intrusion detection community
to emerge real innovative ideas.
\end{huge}
\end{document}

