Can a negative selection detect an extremely few non-self among enormous amount of self cells?

Akira Imada

Brest State Technical University Belarus

(ACS-CISIM’2005 – at Elk, Poland) 2

Our Interest

⇓

a NETWORK INTRUSION DETECTION SYSTEM

in which

we need a set of TEST-DATA to TRAIN and TEST the system with.

⇓

a consideration on such a test-data.

(ACS-CISIM’2005 – at Elk, Poland) 3

So many artificial data-samples have been proposed so far.

⇓ Let’s categorize them □ Fictitious 2-D pictures of test-sample — Type I

E.g., Fisher’s IRIS Flower KDD-cup 1999/2003

⋯

(ACS-CISIM’2005 – at Elk, Poland) 5

□ A visualization of IRIS data by Sammon Mapping

(ACS-CISIM’2005 – at Elk, Poland) 6

□ The data from KDD challange cup 98

4,920,210 data are given

⇓

each is made up of 42 attributes of which

⇓

4-crisp + 17-binary + 6-integer + 15-real

Still infinitely large not-defiened possible transactions remain!

□ Fictitious 2-D pictures of test-sample — Type II

Fisher’s IRIS Flower Ayara et al. KDD-cup 1999/2003 ⋯ ⋯

□ Ayara’s Random Anomaly in 8-bit Binary Universe

152 and 160 abnormal patterns out of 2^{8} = 256 search points. ⇓ Asserted that successfully trained.

□ What if abnormal sample are only a few?

Still can we train the system with normal and abnormal sample?

□ Fictitious 2-D pictures of test-sample — Type III

Fisher’s IRIS Flower  Ayara et al.  None so far

KDD-cup 1999/2003 ⋯ ⋯

(ACS-CISIM’2005 – at Elk, Poland) 11

□ Three of our claims.

1. Data should cover the whole universe.

⇒ We could miss crucial abnormal in no-defined area.

2. Abnormal Sample should be assumed extremely tiny. ⇒ This is of usual case.

3. Can we train the sytem only by NORMAL data?

(ACS-CISIM’2005 – at Elk, Poland) 12

A sommelier who is trained only by real champagne

can tell the difference when given a bootleg or other sparkling wine?

How about Caviar?

GUCCI vs. GUCCI-made-in-Hong-Kong (Yet another from Istanbul) Forgery coins recognition?

(ACS-CISIM’2005 – at Elk, Poland) 13

Our Goal is

to search for only a few ABNORMAL (no-self) pattern

hidden in

an enormous amount of NORMAL (self) patterns

by

training using only NORMAL patterns □ A test-sample – A tiny-flat-island-in-a-huge-lake

• Lake ⇒ x_{i} ∈ [−1, 1] (i = 1, …, n)

• Island ⇒ x_{i} ∈ [−a, a] (a < 1).

— We can control the complexity by changing the size.

(ACS-CISIM’2005 – at Elk, Poland) 15

□ From a fitness landscape point of view □ A Needle in a Haystack

A schematic skecth on fictitious 2D-space

The original Hinton & Nowlan’s Needle:

• A-needle ⇒ Only one configuration of 20 bits of binary string. ⋆ We don’t know where the needle locates, but God knows.

• Haystack ⇒ 2^{20} − 1 search points □ How can we train the detector?

Can we train it with most likely haystack points?

(ACS-CISIM’2005 – at Elk, Poland) 18

□ How difficult?

• Random Search

2^{20} = 1, 048, 576

• Lifetime Learning – Baldwin Effect (Hinton & Nowlan 1993)

□ Random Search

⇓ Placebo!

□ We have attacked this problem with lately reported approaches each of which claims very SUCCESSFUL.

• Artificial Immune System

• Evolutionary Computation

• Fuzzy Rule

• Data-mining Technique

• etc □ When a species of iris flower is normal then are others abnormal?

E.g., Kim & Bentley (2001) claimed

assuming one subspieces of IRIS is abnormal while other two normal

⇓ TP (Successful Detection Rate) reached 100% FP (False Alarm Rate) was only 1%.

□ A snapshot of our ongoing works A Fuzzy Rule approach — Can a fuzzy rule find an island?

⇓

How many rules we need? (MMMMMM ⋯ M)

⇓

IF {x_{1} is Middle}, ⋯, and {x_{20} is Middle} THEN no-self.

(ACS-CISIM’2005 – at Elk, Poland) 23

□ Island in the 6-D lake

Fairly large island (x_{i} ∈ [0.25, 0.75]) vs. Small island (x_{i} ∈ [0.45, 0.55])

⇓

(ACS-CISIM’2005 – at Elk, Poland) 24

□ A curse of dimension

For the island x_{i} ∈ [0.45, 0.55] in the 20-D lake ⇓ (0 1 3 4 0 4 4 1 4 4 1 1 4 1 4 3 0 0 0 2)

(ACS-CISIM’2005 – at Elk, Poland) 25

Shape/Location adaptive membersip function

(ACS-CISIM’2005 – at Elk, Poland) 26

A Fuzzy Neural Network Approach

(ACS-CISIM’2005 – at Elk, Poland) 27

A result of an evolution M ⇓

(ACS-CISIM’2005 – at Elk, Poland) 28

□ Yet another snapshot An immune approach — Constant-sized hyper-shpere Detectors

(ACS-CISIM’2005 – at Elk, Poland) 29

□ A result in 2-D space

(ACS-CISIM’2005 – at Elk, Poland) 30

□ What if top area shrinks to zero?

(ACS-CISIM’2005 – at Elk, Poland) 31

□ Alas! As dimension grows...

While usually we have huge NORMAL samples,

we don’t know many ABNORMAL samples (when we know them it’s too late)

⇓

Can training be performed only by using NORMAL samples?

⇓

a-needle or tiny-island

as test-data to design a network intrusion detector.

(ACS-CISIM’2005 – at Elk, Poland) 33

□ Conclusion

Results have not been wonderful at all AS THEY CLAIMED. Or, experiments have always reversed our expectations.

Though we now are negative more or less, still want to be neutral.