When a Family of Iris Flower is Normal, Then are Others Abnormal?

Akira Imada

Brest State Technical University Belarus Network Intrusion Detection

When we design such a system, by means of a machine learning technique

we need an artificial data to train and to test the system.

⇓

Is this method reliable?

(Cont’d)

Specifically, is the frequently used “Iris Flower Data” useful for the purpose?

(CISIM’2006 – at Miedzyzdroje, Poland) 4

This talk is not a report of success, but a challenge to those who have claimed success.

(CISIM’2006 – at Miedzyzdroje, Poland) 5

What is iris flower dataset?

3 families of iris flower;

Each family has 50 samples ⇒ 150 samples in total;

Each with 4 features (length & width of sepal & petal) like

(0.35 0.28 0.46 0.02 Setosa)

(CISIM’2006 – at Miedzyzdroje, Poland) 7

Typical implementation by a neural network Training with GA as an example

chromosome: (w_{1}, w_{2}, w_{3}, · · · · · · , w_{N})

To evaluate fitness:

Firstly, we give a training set of normal and attack samples

to each of the individuals.

Then ratio of correct outputs is the fitness value.

(CISIM’2006 – at Miedzyzdroje, Poland) 9

10-fold cross validation

The whole 150 samples are divided into 10 parts,

⇓

so that each has 15 samples uniformly drawn from 3 classes.

⇓

The system is trained by the remaining 135 samples.

⇓

Then the 15 samples originally picked up are used to test.

⇓

This is repeated 10 times.

(CISIM’2006 – at Miedzyzdroje, Poland) 10

2-fold cross validation for simplicity here Train with a half of both of normal and attack.

⇓ Test with the remaining half.

(CISIM’2006 – at Miedzyzdroje, Poland) 11

Our GA experiment – three families of iris Evolution of average fitness

Reference

Iris-flower & Network Intrusion Detection

Kim, J. and Bentley, P., (1999a), “ The Human Immune System and Network Intrusion Detection. ” 7th European Conference on Intelligent Techniques and Soft Computing (EUFIT ’ 99), Aachen, Germany.

Kim, J. and Bentley, P., (1999b), “ The Artificial Immune Model for Network Intrusion Detection, 7th European Conference on Intelligent Techniques and Soft Computing (EUFIT ’ 99), Aachen, Germany.

Kim, J. and Bentley, P., (2000), “ Negative Selection within an Artificial Immune System for Network Intrusion Detection”, the 14th Annial Fall Symposium of the Korean Information Processing Society, Seoul, Korea.

Yu Guan et al. (2004) ”K-means+: An Autonomous Clustering Algorithm” University of New Brunswick, Fuculty of Computer Science Technical Reports, TR04-164

G. G. Grinstein et al. (2002) ”Benchmark Development for the Evaluation of Visualization for Data Mining” Information Visualization in Data Mining and Knowledge Discovery, Morgan Kaufmann, San Francisco, pp. 129-176.

D. E. Goodman et al. An Investigation into the Source of Power for AIRS, an Artificial Immune Classification System.” Proceedings of International IEEE Joint Conference on Neural Networks, pages 1678-1683.

Emma Hart (2002) ”Immunology as a Metaphor for Computational Information Processing: Fact or Fiction ?” Unpublished dissertation.

J. Timmis et al. (2004) ”An Overview of Artificial Immune Systems.” Computation in Cells and Tissues: Perspectives and Tools for Thought, Natural Computation Series, pp. 51-86. Springer, November 2004.

I.Antoniou et al. ”Information processing in Artificial Immune System: Approaches and State of the Art.”

Z. Ji and D. Dasgupata (2004) ”Augmented Negative Selection Algorithm with Variable-Coverage Detectors.” Proceedings of the Congress on Evolutionary Computation

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.

From success reports so far – 1

Castellano et al. (2000)

assumed one to be attack data while the other two normal.

(by Fuzzy-NN with T-S model on Iris-data)

⇓

• successful attack detection rate = 96% • false alarm rate = 0.6% Yet another success report so far – 2

Kim & Bentley (2001) claimed

(by Artificial Immune Model on Iris-data)

⇓

• Successful Detection Rate reached 100% • False Alarm Rate was only 1%.

(CISIM’2006 – at Miedzyzdroje, Poland) 15

But can we be so optimistic?

⇓

“When a family of iris is normal then are others abnormal?”

Let’s try a thought-experiment an extreme case:

What if we design

always-answer-yes-machine or randomly-answer-machine? ⇓

Detection rate of normal ≈ 100/150 = 66%.

(CISIM’2006 – at Miedzyzdroje, Poland) 17

(Cont’d)

Evolving NN by GA often try to create this “always-output-yes-NN”

(CISIM’2006 – at Miedzyzdroje, Poland) 18

Let’s visualize iris families — Sammon mapping Sammon mapping maps points in a high-D space into 2-D

by

keeping distance relation preserved as much as possible

or approximating distances in the high-D space by distances in 2-D space with a minimal error.

(CISIM’2006 – at Miedzyzdroje, Poland) 19

A Sammon mapping of iris families

(CISIM’2006 – at Miedzyzdroje, Poland) 20

How is a hucker like? (From a newspaper)

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

Where do outliers lie?

Not simply in the domain for the other families, like IRIS data!!

⇓

Not at the point at random, either. But outlier usually hides behind Normal.

(CISIM’2006 – at Miedzyzdroje, Poland) 22

Standard Experiment on Iris-data

Train and test with

one family as attack while the other two as normal

Train with a part of the data ⇓ Test with the remaining data

(CISIM’2006 – at Miedzyzdroje, Poland) 23

Outliers lie:

Not in the domain for the other families

⇓

Not at the point at random, either.

⇓

But outlier usually hides behind Normal.

(CISIM’2006 – at Miedzyzdroje, Poland) 24

What if the 3 families were distributed like below?

This doesn’t look like a reality, but locally, normal and attack data are distributed in this way,

more or less.

(CISIM’2006 – at Miedzyzdroje, Poland) 26

Challenge I

Randomly located normals and attacks (assuming both normal and attack don’t create cluster)

Create 100 normal samples and 50 attacks all at random.

Train with half of normal and attacks. ⇓ Test with remaining half.

Ayara et al. (2002)

”Negative Selection: How to Generate Detectors.” Random attacks in 8-bit binary universe

152 random attacks out of 2^{8} = 256 search points.

⇓

Asserted that successfully trained and detected them.

This is not so difficult due to small universe.

On iris dataset,

this is extremely difficult, if not impossible.

(CISIM’2006 – at Miedzyzdroje, Poland) 29

Our GA experiment – random normal & attack Evolution of average fitness

(CISIM’2006 – at Miedzyzdroje, Poland) 30

Outliers lie:

Not in the domain for the other families.

⇓

Not at the point at random, either.

⇓

But outlier usually hides behind normal.

Challenge II

What if attacks hide behind normals?

Create 100 normal samples again all at random. Then 50 out of those samples are mutated as attack.

Train with half of the normal and mutants behind them.

⇓ Test with the remaining half.

This is even more difficult than the previous one.

Let’s now go back to Iris Data again.

Challenge III

Attacks who hide behind normal iris family

Assume one family as normal. Then those samples are mutated as attack.

Train with half of normal and mutated attacks.

⇓ Test with the remaining half.

(CISIM’2006 – at Miedzyzdroje, Poland) 35

One family and its mutants

(CISIM’2006 – at Miedzyzdroje, Poland) 36

Our GA experiment – normal & mutant Evolution of average fitness

(CISIM’2006 – at Miedzyzdroje, Poland) 37

Challenge IV

Can we train only with normal? (This is actually is our MUST)

Again one family is attack while the other two normal.

Train ONLY with normal. ⇓

• Test-1: with the other family as attack.

• Test-2: with the randomly specified data as attack.

An immune approach – Negative Selection

Exhaustive detector ... Forrest, Perelson et al. (1994)

A bottleneck of the negative-selection algorithm

Size of candidate antibodies increases exponentially with size of normal. (Ayara et al.)

From success reports so far – 3

Gomez et al. (2003)

“A set of fuzzy rules characterized abnormal space using only normal samples.”

(with 10% dataset of KDD-cup-99).

⇓

“It detects attacks with the detection rate 98.30% and false alarm rate 2.0%.”

(CISIM’2006 – at Miedzyzdroje, Poland) 41

Let’s apply Gomez’ idea to iris data

The 5 fuzzy linguistic terms ⇓

{Low, Medium-low, Medium, Medium-high, High}

(Cont’d)

An example of a set of rules

IF

x_{1} is Law or Medium-law;

x_{2} is High;

x_{3} is Medium or Medium-high or High; and

x_{4} is Medium-low or Medium.

⇓

THEN x is ATTACK Assume we have k such rules.

And then,

a degree of membership of x to the attack is calculated for given x.

(CISIM’2006 – at Miedzyzdroje, Poland) 44

(Cont’d)

Gomez’s chromosome in the context of iris data E.g., ((11001)(01001)(10000)(11100)) means

x_{1} is L or ML or H x_{2} is ML or H

x_{3} is L

x_{4} is L or ML or M Fitness is evaluated as

a degree of membership of x to the attack by giving N normal samples Does this still work

on

random or mutated normal & attack data?

(CISIM’2006 – at Miedzyzdroje, Poland) 46

Challenge V

A metaphor of placebo — dummy pill (necessary experiment by pharmaceutical companies)

“Drugs to ... are

no more effective than placebos for most patients.” found no significant difference than the placebos.”

or

at increased risk of death compared to placebo.”

– by Benedict Carey from New York Times on 12 October 2006.

(CISIM’2006 – at Miedzyzdroje, Poland) 47

(Cont’d)

We sometimes have a bias toward a too optimistic apriori expectation.

(as a metaphor of dummy pill) Create a simple device

which randomly returns either normal or attack regardless of the input.

(CISIM’2006 – at Miedzyzdroje, Poland) 48 (CISIM’2006 – at Miedzyzdroje, Poland) 49

From success reports so far – 4

Joshi et al. (2005)

(by Hidden Markov Models on KDD-cup-99)

⇓

• 79% accuracy in correctly detecting attacks,

• 21% is accounted for false positive rate What if data comprises 80% normal and 20% attack? (This is of usual situation in KDD-cup-99 dataset)

(CISIM’2006 – at Miedzyzdroje, Poland) 50

Concluding Remarks

• Can we successfully train the system with randomly distributed attack and normal?

• Can the system recognize a mutant of normal as an attack? · with randomly located normal. · with one family of iris.

• Can the system trained only by normal recognize attack?

• Is the performance better than a random-replying-machine?

We are trying all of the five challenges with many methods: NN, GA, AIS, C4.5, Fuzzy-classifier ... etc.

But so far not so successful except for the original experiment.

Needless to say, no any intention of discouraging but a challenge.

Positive attack to this pessimistic talk will be welcome.

And of course a cooperation too.

We have many data-set immune to be successfully tested.