%%\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 Intrusion Detection by Soft-computing}\\
\end{center}
{\LARGE \[CONTENTS\]}
\begin{itemize} 
\item Assuming {\it Supervised Learning}
   \begin{itemize}
   \bigskip
   \item[$\star$] We need samples for {\it Training} \& {\it Testing}
      \begin{itemize}
      \bigskip
      \item[$\cdot$] {\it Iris-flower}
      \bigskip
      \item[$\cdot$] {\it KDD-cup-99}
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\hfill(cont'd)
{\LARGE \[CONTENTS\]} 
\begin{itemize}
\item {\it Conjecture 1}\\
\hspace*{.2in}{\it ``Intrusion is like a-needle-in-a-hay-stack \\ 
\hfill not like an iris family.''}\\
\item {\it Conjecture 2} \\
\hspace*{.2in}{\it ``No such  algorithms \\
\hfill to efficiently find a needle in a haystack.''}\\
\end{itemize}

\clearpage
\hfill(cont'd)
{\LARGE \[CONTENTS\]} 
\begin{itemize}
\item Warnings
\begin{itemize}
\item[$\star$] {\it Neither IRIS nor KDD-cup-99 are meaningful!}
\bigskip
\item[$\star$] {\it Training should be only with normal samples!}

\item[$\star$] {\it Don't assume any expectations a priori!}
\end{itemize}
\bigskip
\item Concluding Remarks
\end{itemize}

\clearpage
\begin{center}
{\bf  How to design an intrusion detection system \\ intelligently, if any?}\\
\end{center}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item Two categories
   \begin{itemize}
   \setlength{\itemsep}{0pt} 
   \item[$\star$] Detection of {\it known attack}.
   \item[$\star$] Detection of {\it unknown no-normal}.
   \end{itemize}
\end{itemize}
\bigskip
\begin{center}
To detect known-attacks, intelligence is not necessary but \\ a lookup-table is enough \\
$\Downarrow$\\
Our interest is on detecting {\it unknown no-normal}.
\end{center}


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

\begin{itemize} 
\item {\LARGE 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}\\
\bigskip
To design a machine which tells \\
the input is a {\it normal} or an {\it attack}.
\end{center}

\begin{figure}[hb]
 \begin{center}
 \epsfile{file=b-box.eps,width=8.5cm,height=3cm}
 \end{center}
\end{figure}
\begin{center}
%%A successful result in the literatures seems to be\\
Hopefull with\\
{\it Detection Rate} $>$ 90\% \&
{\it False Alarm Rate} $<$ 10\%
\end{center}


\clearpage
\begin{center}
{\bf An example of NN implementation}
\end{center} 
\begin{figure}[hb]
 \begin{center}
 \epsfile{file=b-box-kdd.eps,width=16cm,height=8cm}
 \end{center}
\end{figure}



\clearpage
\begin{center}
{\bf  A question}\\
\bigskip
{\it ``Is it possible or not?''}
\end{center}



\clearpage
\begin{center}
{\bf  Training \& Testing}\\
\end{center}
\bigskip
\begin{itemize}
\item Frequently used two public domain datasets.
   \begin{itemize}
   \item[$\star$] Iris-flower dataset.
   \item[$\star$] KDD-cup-1999 dataset
   \end{itemize}
\end{itemize}


%% --- (iris dataset) ---
\clearpage
\begin{center}
{\bf [I]  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
\begin{center}
{\bf Lots of successes have reported so far}\\
\hspace*{1in}\\
Castellano et al. (2000) \\
assumed one to be normal while the other two abnormal.\\
$\Downarrow$\\
{\Large (by Fuzzy-NN with T-S model)}\\
$\bullet$ abnormal detection rate = 96\%  \\ 
$\bullet$ false alarm rate = 0.6\%\\
\end{center}

\clearpage 
\hfill (cont'd)
\begin{center}
But can we be so optimistic?\\

$\Downarrow$\\

When a family of iris is normal then are others abnormal?\\
\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 \\
approximating distances in the $n$-D space \\
by distances in 2-D space with a minimal error.\\
\end{center}

\clearpage
\begin{center} 
{\bf A 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!!\\
$\Downarrow$\\
Not at the point at random, either.\\
$\Downarrow$\\
But outlier usually hides behind Normal.
\end{center}

\clearpage
\begin{center}
{\bf $\Box$  Challenge 1}
\end{center}
{\it
\noindent
Attacks by Mutant
\begin{itemize}
\item[(1)] Assume one family as \{Normal\}
\item[(2)] Mutate the Normal samples and take them as \{Attack\}.
\item[(3)] Train with half of the \{Normal + Mutant\}
\item[(4)] Test  with remaining \{Normal + Mutant\}
\end{itemize}
}
\begin{center}
\hspace*{1in}\\
$\Rightarrow$ Will a successful result be possible? \\
\end{center}


\clearpage
\begin{center}
{\bf  The 1st warning} \\
\vspace*{1in}
{\it Iris is good to start with, but not of so useful.}
\end{center}


%% --- (KDD-cup-99 dataset) ---
\clearpage
\begin{center}
{\bf [II] What is the KDD-cup-1999 dataset?} 
\end{center}
\bigskip
\begin{itemize}
\item {\it Normal}
\item {\it Attack} $\Rightarrow$ {\LARGE 32 attack types of the 4 categories:}
\end{itemize}

\clearpage
\hfill (cont'd)
\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}
\end{itemize}

\clearpage
\begin{center}
%%It might be interesting here to see
{\bf KDD-cup-99 winner's result}\\ 
\hspace*{1in}\\
Detection rate for 4 attack types
\end{center}

{\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}
{\bf Detection rate by Sabhnani et al.~(2003)}
\end{center}
{\LARGE
{\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
\begin{center}
{\bf We doubt some sort of the reported success}
\end{center}

\begin{itemize}
\item Dimension Reduction by PCA -- by Kuchimanchi et al.
   \begin{itemize}
   \item[$\star$] 41-D to 19-D
      \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}
\end{itemize}

\clearpage
\begin{center}
{\bf Yet another interesting claim} \hfill(cont'd)
\end{center}
\begin{itemize}
\item Joshi et al.~(2005)
   \begin{itemize}
   \item[$\star$] 41-D to 5-D (taking the first five from above)
      \begin{itemize}
      \item[$\cdot$] (detection accuracy, false positive) = (79\%, 21\%)\\
      \hfill (using Hidden Markov Process)
      \end{itemize}
   \end{itemize}
\end{itemize}

\clearpage
\begin{center}
Let's not go into detail here, but rather focus on\\
\vspace{1in}
{\bf Why U2R and R2L attacks resist to be detected?}
\end{center}


\clearpage
\begin{center}
{\bf How big is the KDD-cup-1999 dataset?}\\
\hspace*{1in}\\
Labeled 4,898,430 records $\Rightarrow$ {\it Training}\\
Un-labeled 311,029 records $\Rightarrow$ {\it Testing}\\
and\\
Each record is 41-dimensional vector\\
\hspace*{1in}\\
$\Downarrow$
\hspace*{1in}\\
Sammon Mapping wouldn't work any more!
\end{center}





\clearpage
\begin{center}

\end{center}
{\it
\begin{table}[h]
\begin{center}
Ratios in the samples for testing\\
\bigskip
\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 Let's try a thought experiment!}
%%{\bf Or}
\end{center}
\begin{itemize}
\item {\it always-return-random-answer-strategy}
   \begin{itemize}
   \item[] which returns either Normal, Probe, DoS, U2R, or R2L at random regardless of the input.
   \end{itemize}
\item[]
\item[] $\Rightarrow$ a high score to detect DoS attacks, like
\end{itemize}
{\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}
%%\hfill {\LARGE (Winner of KDD-cup-99)} \hspace*{1.2in}
\end{table}
}




\clearpage
\begin{center}
{\bf A-tiny-set-of-R2L vs. a-huge-set-of-normal} \\
\end{center}
\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}
%%\begin{center}
%%$\Downarrow$\\
%%\end{center}
\begin{figure}[h]
\begin{center}
{\LARGE Fictitious but possible distributions}\\
\bigskip
  \epsfile{file=gauss-10.eps,width=5.8cm,height=4.1cm}
  \epsfile{file=gauss-20.eps,width=5.8cm,height=4.1cm}
  \epsfile{file=gauss-30.eps,width=5.8cm,height=4.1cm}
%%\epsfile{file=gauss-2.eps,width=12cm,height=4cm}
\end{center}
\end{figure}


\clearpage
\begin{center}
{\bf $\Box$ Conjecture 1}\\
\hspace*{1in}\\

{\it $\bullet$ U2R, R2L and most of real attacks are \\
like needles \\
in a huge haystack of normals.}
\end{center}

\clearpage
\begin{center}
{\bf What does a needle look like in a haystack?}\\
\bigskip
The original Hinton \& Nowlan's Needle: \\
\end{center}
\begin{itemize}
\setlength{\itemsep}{0pt}
\item A-needle $\Rightarrow$ Only one configuration of 20-bit binary string.
             \hspace*{2.1in}{\LARGE like (11000 11010 11101 0100)}
%%   \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}
\bigskip
\begin{center}
A fictitious needle in a haystack in 2D.
\end{center}
\begin{figure}[hb]
\begin{center}
\epsfile{file=a-needle-0.eps,width=15cm,height=1.5cm}
\end{center}
\end{figure}

\clearpage
\begin{center}
{\bf The reason of our title}\\
\hspace*{1in}\\
a needle on pastoral \& random fall of parachutists\\
\bigskip
$\Downarrow$\\
\bigskip
How many parachutists will be needed to find \\ a needle in a pastoral?
\end{center}

\clearpage
{\bf Four experiments to look for a needle in pastoral}\\
\begin{itemize}
\item[1.] Random fall  -- a criterion for comparison
\item[2.] What if we permit walks after fall?
\item[3.] Neutral mutation
\item[4.] Mutation on intron
\end{itemize}

\clearpage
\begin{center}
{\bf Random Fall \& Walks after Fall}
\end{center}
\begin{figure}[hb]
\begin{center}
\epsfile{file=parachuters.eps,width=10cm,height=5cm}
\end{center}
\end{figure}
\begin{center}
9-digit octal ($=$ 27-bit binary) never stops a run
\end{center}

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

\clearpage
\begin{center}
{\bf  Yet another difficulty: The 2nd warning} 
\end{center}
\bigskip
\begin{itemize}
\item[(2)] {\bf Don't assume any expectations a priori!}
\item[(3)] {\it Training should be only with normal samples!}
\end{itemize}

\clearpage
\begin{center}
{\it ``Artificial immune system detects an attack by a virus!''} \\ 
\bigskip
How fantastic it sounds!\\
\hspace*{1in}\\
%%{\LARGE A landmark:} 
Forrest, Perelson et al.~(1994)\\
{\it ``Self Nonself Discrimination in a Computer''}\\
\hspace*{1in}\\
But two decades has passed since then, and still an open issue.\\
$\Downarrow$ \\
We hope not, but isn't it just a fantasy?
\end{center}



\clearpage
\begin{center}
{\bf $\Box$ Challenge 2}\\
\bigskip
{\it $\bullet$ Always-return-random-answer-strategy}\\ 
vs.\\ 
{\it $\bullet$ An intelligently designed system}\\
\end{center}
{\it
\bigskip
Placebo Experiment
\begin{itemize}
\item[(1)] Prepare a dataset uniformly from all attack data
\item[(2)] Test your intelligent system with dataset above 
\item[(2)] Compare the result with the random-return-machine
\end{itemize}
}

\clearpage
\begin{center}
{\bf  The last warning} 
\end{center}
\bigskip
\begin{itemize}
\item[(2)] {\it Don't assume any expectations a priori!}
\item[(3)] {\bf Training should be only with normal samples!}
\end{itemize}

\clearpage
\begin{center}
{\bf From papers}\\
{\LARGE
\bigskip
P. Laskov et al.~(2005)\\
{\it ``In a real application, one can never be sure that a set of available labeled
examples covers all possible attacks. If a new attack appears, examples of it
may not have been seen in training data.''}\

\bigskip
Colin M. Frayn (2006)\\
{\it Real-world data are very rarely well-behaved in the sense required by conventional algorithms.}\\

\bigskip
Me (2005)\\
``When we know the attack, it's too late''
}
\end{center}

\clearpage
\begin{center}
{\bf With goal being training-only-by-normal}\\
\bigskip
Gomez et al.~(2003)\\
{\it ``A  set of fuzzy rules characterized abnormal space 
using only normal samples.''}\\
with\\
10\% dataset of KDD-cup-1999 dataset \\
$\Downarrow$\\
{\it ``It detects attacks with the detection rate 98.30\% 
and false alarm rate 2.0\%.''} \\
$\Downarrow$\\
Really satisfactory, if it's really true.\\
\end{center}


\clearpage
\begin{center}
{\bf $\Box$ Challenge 3}
\end{center}

\noindent
{\it Attack by dummy}
{\it
\begin{itemize}
\item[(1)] Prepare \{Normal\} and \{Attack\}  from KDD-cup-99.
\item[(2)] Create \{Dummy\}  at random
\item[(3)] Train with only \{Normal\}
\item[(4)] Test with \{Attack\} and \{Dummy\} one by one
\end{itemize}
}
\begin{center}
$\Downarrow$\\
Can a Sommelier be trained without bootlegs?
\end{center}



\clearpage
\begin{center} {\bf CONCLUSION} \end{center}
{\it
\begin{itemize}
\item Neither IRIS nor KDD-cup-99 are useful.
\item A hacker is a person who is extremely good at finding 
      a pattern which is very close to the normal.
\item In testing, an attack should be like a mutant-of-normal
\bigskip
\item Needless to say, however, this article is not to negate the possibility, but
\item we hope this will be a new start of debate for a emergence of innovative ideas.
\end{itemize}
}
\end{huge}
\end{document}


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


\begin{itemize}
\setlength{\itemsep}{0pt}
\item[]  \hspace*{2in}$\cdots$
\item[(5)]  If matches, end the run. 
\item[]     If not matches,
   \begin{itemize}
   \item[$\cdot$] give a mutation (by flipping a bit chosen at random) 
                  with a probability of $1/3p$
   \end{itemize}
\item[] until the translation matches the PIN,\\ or number of steps exceeds 1000.
\end{itemize}

      \bigskip
      \item[$\cdot$] Both are useless for practical view point
