\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}
\newtheorem{excersize}{Problem}
\newtheorem{algorithm}{Algorithm}

\begin{document}
%\title{How Many Parachuters will be Needed to Find a Needle in a Pastral?}
\title{How Many Parachutists will be Needed to Find a Needle in a Pastral?}

\author{{\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
This article is a consideration on 
computer network intrusion detection using artificial neural networks.
We assume an intrusion is like so-called a needle in a haystack 
not like one family of iris flower, and consider how
a detection is likely to detected by artificial neural networks.
\end{abstracttext}

\bigskip
\section{Introduction}
\begin{quotation}
\begin{small}
\noindent
{\it 
The paracute drop went smoothly ... slithering down the chute and out into space ...
Flick landed perfectly, with her knees bent and her arms tucked into her sides
as she fell to the ground ... She folded her parachute into a neat bundle,
then set out to find the other Jackdows. -- ``Jackdows'' by Ken Follett.
}
\end{small}
\end{quotation}

\noindent
Most Banks nowadays fascilitate their ATM (Automaic Teller Machine) in which we may have
a parsonal account to which we can access with PIN-code -- usually four digits of 
decimal numerals.
For security reason, if we failed to enter the PIN more than three times, then
the PIN would loose its validity therefter. Then what we are curious is, 
``How many trials would be needed for random challanges to reveal the secret PIN
if it were permitted to try infinit times?''
Let's formalize this problem.

\bigskip
\begin{excersize}[Breaking a PIN]
Assuming $p$-bit of octal numeral is employed to construct a PIN,
and only one configuration out of those $8^{p}$ possible combinations is 
the PIN for one person to be identified. No one excpt for him/her knows the code. 
How could others could reveal the PIN just by trial and error approach?
%% a blac box which asks us to enter a $p$ bits of octal and return the entry is PIN or not.
Then qustion is how many average trials will be needed to know the PIN under a specific strategy?
\end{excersize}

\bigskip
\noindent
This might be reminiscent of the famous problem called {\it a needle in a haystack}
which is originally proposed by Hinton \& Nowlan~\cite{hint} in 1987 
in which the needle was exactly the one configuration of 20-bit of binary string.
In other words, the search space is made up of $2^{20}$ points and 
only one point is the needle to be searched for. 
No information such as how close is a currently searching point to the needle,
or how likely is a searching point to be the needle. See Figure 1.\\

\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
We assume TCP connections to a computer network are represented with $n$-dimensional vectors
and those represented by intrusions are such as {\it needles}
among huge amount of normal transactions which might be taken to be a {\it haystack.}


\bigskip
\section{Network Intrusion Detection}
\begin{quotation}
\begin{small}
\noindent
{\it Those highly qualified hackers who provide security services to companies during 
the daytime and then go home at night to conduct totally illegal hacking are the ones 
who are the most dangerous. -- by Enis Senerdem from Turkish Daily News on 29 March 2006}.
\end{small}
\end{quotation}



\noindent
When we are to design a network intrusion detection system, which is one of the hottest topics
these days, by means of 
so called {\it soft computations} like {\it artificial immune system},
{\it fuzzy logic}, {\it evolutionary computations}, {\it neural networks}, whatever it might be,
we need a set of sample data to train the system and test the system afterwards.


\bigskip
\subsection{When a Faimily of Iris Flowers is Normal Then are Others Abnormal?}
\noindent
As is often mentioned, 
the iris flower database\footnote{University of California Urvine Machine Learning Repository. 
ics.uci.edu: pub/machine-learning-databases.} 
is perhaps the most often used dataset 
in pattern recognition/clssification, machine learning, data mining, etc.
As such, there have been fair amount of studies in which this Spereman's iris flower 
database is employed as a dataset to train and to test the intrusion detection system.
A total of 150 samples consists of three species: 
{\it setosa, versicolor} and {\it virginica}
each of which includes 50 samples. 
Each sample is a four-dimensional vector 
representing four attributes of the iris flower, that is,
{\it sepal length, sepal width, petal length}, and {\it petal width}.\\

\noindent
Let us take an example. 
Castellano et al.~\cite{cast} assumed one class to be normal 
whilst the other two to be abnormal.
The whole dataset was divided into 10 parts each of which has  
15 samples and are uniformly drawn from the three classes.
The system is trained by the remaining 135 samples.
The originally picked up 15 samples are used to test the results. 
After this 10-fold cross validation, 
the authors concluded that after training the system shows
the invation detection rate is 96\% while the false alarm rate is 0.6\%.
%% for dataset kept by test the system.
In reality, however, it is not simple.
It might be not so difficult for a hucker to find an unlearned reasion
which could work to invade the system.\\

\noindent
We now look at the Figure 2 to see how the three spieces are distributed in 
the whole search space. This is depicted by the Sammon Mapping. \\

\noindent
Sammon Mapping is a mapping a set of points a in high-dimensional space to 
the 2-dimensional space with the distance relation being preserved as much as possible,
or equivalently, the distances in the $n$-dimensional space are approximated 
by distances in the 2-dimensional distance with a minimal error.\\

\noindent
Just a brief look at the figure reveals us that there remains an enormously
wide region of unlearned.

\begin{figure}[h]\label{fig:iris}
 \begin{center}
   \epsfile{file=iris.eps,width=8cm,height=6cm}
\caption{A 2-D visualization of iris flower data by Sammon Mapping}
 \end{center}
\end{figure}


\begin{figure}[hb]
 \begin{center}
 \epsfile{file=rnd-500-5.eps,width=8cm,height=5.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}

\bigskip
\subsection{Is an Intrusion Like a Needle?}
\noindent
The other type of dataset more often employed is a so called KDD cup 99 data
which was prepared by MIT Lincoln Laboratory
as a dataset for the 1998 DARPA intrusion detection 
evaluation.~\footnote{http://kdd.ics.uci.edu/databases/kddcup99/kddcup99.html.}\\

\noindent
This dataset is made up of two sets. 
The one is called {\it labeled} dataset which includes 4,898,430 records 
each consists of 41 attributes.
The other is called {\it unlabeled} which includes 311,029 records
each of which consists of the same 41 attributes as above plus one attributes
representing normal or one of 22 attack types.
Usually the laveled dataset is used for training and the unlaveled 
is for testing the system afterwards. So huge dataset, isn't it?\\

\noindent
Indeed, Kuchimanchi et al.~\cite{kuch} 
used the {\it principal component analysis}, 
and conclude the first most important 19 attributes.~\footnote{They are {\it src\_bytes, 
dst\_bytes, duration, is\_guest\_login, is\_host\_login, srv\_diff\_host\_rate,
diff\_srv\_rate, service, flag, protocol\_type, num\_root, hot, num\_compromised,
dst\_host\_same\_srv\_rate, dst\_host\_count, rerror\_rate, srv\_count}, and
{\it dst\_host\_srv\_diff\_host\_rate}.} \\

\noindent
Gomez et al.~\cite{gome} used 10\% dataset which reduced the number of records
into 10\% of the original ones. 
Further they removed categorical attributes and 
normalized these remaining 33 numerical atributes
between 0 and 1 using the maximum and minimum values found.
Then 80\% of the normal samples were picked up at random for training 
while the remaining 20\% 
along with the same number of abnormal samples were used for testing. 
Gomez et al.~ designed with what they called a  {\it immuno-fuzzy approach}
and system they call  {\it Evolving Fuzzy Rules Detectors}
detects records laveled attack with the detection rate 98.30\% 
and false alarm rate 2.0\%. How wonderful!\\

\noindent
We, however, again doubt their reported successful result.
Just see the Figure in which 
an attack datum among randomly picked up 100 normal data are shown 
by again the Sammon Mapping.
The attack is more like a needle in a haystack, isn't it?


\bigskip
\section{Experiments}
\begin{quotation}
\begin{small}
\noindent
{\it 
Flick remembered
the legend of the Jackdow of Reims, the bird that stole the bishop's ring.
The monks couldn't figure out who had taken it, so the bishop
cursed the unknown thief. Next thing they knew, the jackdaw
appeared all bedraggled, and they realized he was suffering from the effects
of curse, and must be the culplit.
Sure enough they found the ring in his nest. -- ``Jackdows'' by Ken Follett.
}
\end{small}
\end{quotation}

\bigskip
\noindent
Let's see how easy or difficult a needle in a haystack problem. Starting with a random search,
which consists our placebo. Note that some proposed algorithms, reported suceess,
actually are not good as asserted
and sometimes found to be worse than a random search.

\bigskip
\subsection{Random Fall of Parachutists}
\begin{algorithm}[Random Fall]
(1) Create a $p$-bit octal PIN at random.
(2) Create randomly $3p$-bit of binary string.
(3) Translate the string into $p$-bit octal code.
(4) Check if the translated code matches the PIN.
(5) If matches end the run. Otherwise go back to (2).
\end{algorithm}

%% \bigskip
%% \noindent
%% Algorithm 1 (Random Fall)
%% {\it (1) Create a $p$-bit octal PIN at random.
%% (2) Create randomly $3p$-bit of binary string.
%% (3) Translate the string into $p$-bit octal code.
%% (4) Check if the translated code matches the PIN.
%% (5) If matches end the run. Otherwise repeat from (2).}\\

\bigskip
\noindent
Let us allow to use a metaphore here.
We now assume only one needle in a pastral, 
and parachutists fall from the airplane to the pastral
one by one, then how would it be likely for a parachutist
to fall just on the needle.
This might be taken as a random search,
and will be our criterion of comparison hereafter, 
in other words, our experiment for {\it placebo}.\\

\noindent
Note that one parachutist is represented our genotypes of 
a $3p$-digits binary strings. Let's take an example of $p=4$:
\begin{displaymath}
    ((100) (111) (000)(010))
\end{displaymath}
maps into its phenotype (4 7 0 2).\\

\noindent
First, one $p$-bit octal PIN is created which we assume no one dosen't know {\it a priori}.
With $p$ being increasing from 2, we count the number of 
randomly created genotypes until its phenotype strictly matches to the hidden PIN.
The average number, during 1024 runs, of parachutists needed to firstly finds the needle 
for $p = 2, 3, 4, 5, 6$ are, respectively,
\begin{equation}
   (350, 3500, 50000, 50000, 60000).
\end{equation}


\bigskip
\subsection{What if Parachutists are Allowed Walks after Fall?}
\begin{algorithm}[Random Fall]
(1) Create a $p$-bit octal PIN at random.
(2) Create randomly $3p$-bit of binary string.
(3) Translate the string into $p$-bit octal code.
(4) Check if the translated code matches the PIN.
(5) If matches end the run. Otherwise give a mutation
by flipping bit chosen with a probablity of $1/3p$
until the translation matches the PIN or
number of steps exceeds 1000.
(6) If still hasn't been matched, then repeat from (2).
\end{algorithm}
\bigskip

\noindent
Then what will happen if the fallen parachutist allows to explore, say, 1000 random
steps, around the folling spot?
This is reminiscent of the seminal experiment once made by 
Hinton \& Nowlan \cite{hint}
reffering {\it ``lifetime learning --- Baldwin Effect''}
though our parachutists, in this paper end her life without creating a next generation.
The results, again the average in 1024 runs,  
for $p = 2, 3, 4, 5, 6$ are, respectively,
\begin{equation}
   (350, 3500, 50000, 50000, 60000).
\end{equation}


\noindent
The results are also shown in Figure 2 with the result of our random parachutists
in the previus subsection.
In both cases, we can see complexity is an exponential order.
How impressive an exploration after fall improves the performance!\\

\noindent
As you have probably noticed already, however, it's not fair just compare the number of 
parachutists. The total number of points searched by those walking parachutists
are plotted as a function of $p$ in Figure 3. We can see rather worse than our placebo experiment.
In fact for $p = 7$ we cannot find any parachutist even if we run the algorithm
for 3 days in a raw using a standard pentium PC.


\begin{figure}[hb]
\begin{center}
\epsfile{file=parachuters.eps,width=8cm,height=5cm}
\caption{(a) Numer of random creations of candidate until the PIN is matched 
(filled circles), and (b) The number when created candiate allowed random walks
of 1000 steps (empty circles). Both are the average of 1024 runs.}
\end{center}
\end{figure}

\begin{figure}[hb]
\begin{center}
\epsfile{file=actual-how-many.eps,width=8cm,height=5cm}
\caption{Average number of points searched by randam creation of a candidate
who are allowd further random walks of 100 stemps. Average are taken among 1024 runs.}
 \end{center}
\end{figure}


\bigskip
\subsection{Neutral Mutation}
\begin{algorithm}[Walk by Nutral Mutations]
(0) Create a PIN at random.
(1) Create one genotype at random.
(2) Try point-wise mutation so that rusult maps into the same phenotype.
(3) Assess each single mutation neighbour of the new genotype 
to determine whether any new phenotypes were discovered.
(4) Step 2 to 3 are repeated untill the phenotype matches the PIN, or
untill a pre-fixed number of steps is reached. 
\end{algorithm}
This is a paraphrase of the algorithm proposed by Shipman et al.~\cite{ship}. 
Shipman et al.~call the step (2) as a {\it neutral mutation}.
Its efficiency was studied in their paper by applying it to
a random Boolean network and
telecommunications networks.
But why not more simple example can be explored, if it is to work universaly?\\

\noindent
To apply this in our problem of searching for the needle, that is,
octamal $p$-bit PIN, we design our genotype 
as $12p$-bit binary string so that the number of 1 in each of 6-digit blocks
in the string (mod 8) mapps into one bit of the corresponding bit of 
octamal code.\footnote{A brief consideration might gives us
6-bit binary for each octamal is enough, however, we implement in this way
so that each octamal from 0 to 7 are created uniformly at random.}
For example
\begin{displaymath}
    ((100110000100) (111111111111) (111110110110))
\end{displaymath}
maps into (4 8 1).\\

\noindent
The average number, during 1024 runs, of parachutists needed to firstly finds the needle 
for $p = 2, 3, 4, 5, 6$ are, respectively,
\begin{equation}
   (350, 3500, 50000, 50000, 60000).
\end{equation}

\bigskip
\subsection{Does Neutral Mutation on Intron Increase Efficiency of Search?}
\begin{algorithm}[Neutral Network]
(0) Create a PIN at random.
(1) Create randomly an initial population of 5 genotypes
and select one at random 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;
(4) Select a winner from the current population using the following rules: 
      (i) If any offspring has a better fitness, it becomes the winner.
          Otherwise, an offspring with the same fitness is randomly selected.
     (ii) 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.
(5) Go to step 2 unless the maximum number of generations reached or a solution with needle 
      fitness is found.
\end{algorithm}

\bigskip
\noindent
We had an interesting discussion between 
Yu \& Miller's paper 
{\it ``Finding Needles in Haystacks is Not Hard with Neutrality'' (2002)} \cite{tina}
vs.~Collin's 
{\it ``Finding Needles in Haystacks is Harder with Neutrality'' (2005)}. \cite{coll}\\

%% must mention intron
\noindent
What Yu and Miller attacked as a type of {\it a needle in a haystack} problem
was the {\it even-n-parity} logic circuit only by employing {\it XOR} and {\it EQ},
not {\it AND} and {\it OR} and so an,
which has a peculiar fitness landscape.
The {\it even-n-parity} logic has $n$-bit binary inputs and if and only if 
the number of 1 is even it returns 1 and otherwise 0.
Hence, we can evaluate the fitness value of any one candidate of the solution, 
by giving all the possible configurations of 0 and 1 and counting how many correct outputs.
Thus, from a combinatorial point of view we have $2^n$ different fitness values.
In reality, however,
we have, only three different values in this case. That is, 0 and $2~(n-1)$ and $2^n$, namely,
the output is all correct, half correct, or no correct at all. \\

\noindent
Though Yu \& Miller claimed a random creation of 4,000,000 candidate of {\it even-12-parity},
the solution (fitness 4096) was never emerged, while {\it even-10-parity}
100,000 random creation of candidates yielded 540 solutions with perfect fitness.
On the other hand, when neutral mutaion is applied, the 48 out of 100 runs reached
solution(s) with each run being  only 10,000 iterations.\\

\noindent
Collins argued back 
concluding reported success is due to bias of the selection \cite{coll}.\\

\noindent
In the other of Collin's work \cite{coll-2}, it was analytically shown that
the number of possible candidate is $1.315 x 10^{139}$ in which number of
real solutions is $2.568 x 10^{132}$, claiming that Yu \& Miller's result is
worse than a possible random search.\\

\noindent
Again what we want to emphasise is if the assertion is universal
it would work in yet more principally simple examples. Befor going to proceed, let's see 
what is {\it intron} that Yu \& Miller assumed to play an inportant role in their evolution.
For example for, {\it even-3-parity} logic circuit.
A genotype
\begin{displaymath}
((EQ,A,B)(EQ,C,D)(XOR,1,E)(EQ,F,G)(EQ,3,H))
\end{displaymath}
where each gene which corresponds to one unit
constructs triples: with the 1st being which logic (EQ or XOR) is to be used; 
and with the 2nd and 3rd being connections to either one of 
the inputs or the outputs of previous units.
Note that 2nd and 4th genes do not contribute to construct the phenotype 
since those two genes will not be connected to any other unit,
and are called {\it intron} as a biological metophore.
Any mutation on an intron has no effect on phenotype, and as such, they are  called {\it neutral}.
The above genotype as an example can be interpreted as the phenotype below.\\
\begin{figure}[hb]
 \begin{center}
 \epsfile{file=even-5-parity.eps,width=7cm,height=1.8cm}
 \end{center}
\end{figure}


\noindent
Now we try to apply this to our finding PIN problem.
This time we use 4-digit binary instead of 3-digit as above to represent one octamal
numeral in the candidate of PIN. Then translation is into decimal instead of octamal,
and the translated decimal is larger than eight we consider it an {\it intron}.
For example
\begin{displaymath}
((0001)(1100)(0101)(0010)(0111))
\end{displaymath}
is translated into $(1, 5, 2, 7)$ since sencond gene is translated into 12 and 
supposed to be {\it intron}.

\noindent
The average number, during 1024 runs, of parachutists needed to firstly finds the needle 
for $p = 2, 3, 4, 5, 6$ are, respectively,
\begin{equation}
   (350, 3500, 50000, 50000, 60000).
\end{equation}

\section{Concluding Remarks}
\noindent
We observed impressive improvement by ...
We have compared the improvement with three other method so far proposed.
None of them have not revealed better results than a random search.\\

\noindent
Moreover, when we applied this algorithm in the context of network intrusion detection,
we will have a togher problem of how the system learn only by normal data to detect
abnormal. Although we have enormous amount of normal data (hay) but we have no information
about abnormals (needles) until it's too late.\\

\noindent
Hope this is a challange and will be emerge a auchheven.

\bigskip
\begin{thebibliography}{99}

\bibitem{hint}G.~E.~Hinton and S.~J.~Nowlan (1987)
``How Learning can Guide Evolution.''
Complex Systems, 1, pp.~495--502. 


\bibitem{cast}
G.~Castellano and A.~M.~Fanelli (2000)
``Fuzzy Inference and Rule Extraction using a Neural Network.''
Neural Network World Journal Vol.3 ,pp.361-- 371.

\bibitem{gome}
J.~Gomez, F.~Gonzalez and  D.~Dasgupta (2003)
``An Immuno-Fuzzy Approach to Anomaly Detection.''

\bibitem{kuch}
G. K. Kuchimanchi, V. V. Phoha, K. S. Balagani and S. R. Gaddam (2004) 
``Dimension Reduction Using Feature Extraction Methods for Real-time Misuse Detection Systems.''
Proceedings of Workshop on Information Assurance and Security, Unitid
States Military Academy, West Point , NYT, pp. 1555 -- 1563.

\bibitem{akir}
A. Imada (2004)
``How a Peak on a Completely-flatland-elsewhere can be Searched for?''
Proceedings of Advanced Computer Systems (ACS) and 
Computer Information Systems
and Industrial Management Applications (CISIM), Vol.2, pp. 171--150.

\bibitem{tina}
Tina Yu and J. Miller (2002)
``Finding Needles in Haystacks is Not Hard with Neutrality.''
Proceedings of EuroGP 2002, LNCS 2278, pp. 13-25.

\bibitem{coll}
M. Collins (2005)
``Finding Needles in Haystacks is Harder with Neutrality.''
Proceedings of GECCO-2005, pp 1613--1618.

\bibitem{coll-2}
M. Collins
``Counting Solutions in Reduced Boolean Parity.''
Proceedings of GECCO-2004, pp 1613--1618.


\bibitem{ship}
R. Shipman, M. Shackleton and I. Harvey (????)
``The use of neutral genotype-phenotype mappings for improved evolutionary search.''

\end{thebibliography}
\end{document}


\begin{quotation}
\begin{small}
\noindent
{\it An ant climbs a blade of grass, over and over, seemingly without purpose, seeking neither 
nourishment nor home. -- Daniel C. Dennett "Breaking the Spell: 
Religion as a Natural Phenomenon"}
\end{small}
\end{quotation}

\begin{quotation}
\noindent
{\it One day I'd cooked soba. Great! I tried teuchi udon the next day and it was also great. It is really easy to make such delicious dishes just from flour or buckwheat flour. The main thing is sauce, however. It is either tasty or not. Nothing in between. - Edward Venskovich (Personal Communication).}
\end{quotation}