Transcript Project Overview

Fuzzy Intrusion Detection
Fuzzy Systems
Alireza Shakibaee
June 7, 2005
Agenda


Introduction
IDS functional components
– Information source
– Analysis engine
– Decision maker


Artificial intelligence techniques
Dynamic fuzzy boundary
– Fuzzy logic
– Support vector machine

Conclusion
2
Introduction



Intrusion detection systems focus on
discovering abnormal system events in
computer networks and distributed
communication systems
Uncertainty nature of intrusions => Fuzzy Set
Different levels of security needs => Dynamic
fuzzy boundary
3
Introduction (Cont.)

Intrusion detection systems are important in
maintaining proper network security

People use intrusion detection systems to:
– Monitor the events occurring in a computer
system or network
– Analyze the system events
– Detect suspected intrusion
– Raise an alarm
4
IDS functional components

A typical IDS consists of three functional
components:
– An information source
• Provides a stream of event records (event generator)
– Data sources related to operating systems (system calls)
– Network traffic monitors (generate raw network packets)
– Data collectors of different applications
– An analysis engine
– A decision maker
5
Analysis engine

The analysis engine finds signs of intrusions
 There are two basic approaches used to
detect intrusions:
– Misuse detection
• Detects intrusions which follow well-known
patterns
– Anomaly detection
• Recognizes patterns of activities that appear to be
normal
6
Decision maker

Applies some rules on the outcomes of the
analysis engine
 Decides what reactions should be done on
the outcomes of the analysis engine
 Major function:
– Increase the usability of an intrusion
detection system
7
Artificial intelligence techniques

For a misuse detection system:
– An expert system can be used to store a set of
rules designed to detect the known intrusion
activities
– Pattern matching (Kumar et. al.)
• Known intrusion signatures are encoded as patterns
• Then matched against the audit data introduced by
the analysis component
8
Artificial intelligence techniques (Cont.)

Anomaly intrusion detection consists of two
processes (from the viewpoint of classification):
– Training the parameters of a classifier from a training data set
– Using the classifier to classify a data set

Some approaches:
– Using Hidden Markov Model to analyze the trace of system calls
coming from a UNIX system (Qiao)
– Combining neural networks and fuzzy logic
– Using genetic algorithms to optimize the membership function for
mining fuzzy association rules (Wang)
9
Artificial intelligence techniques (Cont.)

All the methods mentioned use static classifier or
static decision boundary to classify data, then
detect possible intrusions
 However,
The security needs may differ for various
applications

There are some connections between:
detection accuracy & computation complexity
10
Fuzzy logic

Fuzzy logic is very appropriate for using on
intrusion detection:
– Usually there is no clear boundary between
normal and anomaly events
• Use of fuzziness to smooth the abrupt separation of
normality and abnormality
– When to raise an alarm is fuzzy
• At what degree of intrusion we should raise an
alarm?
11
Support vector machine

SVM in short is a machine learning method based
on statistical learning theory
 SVM classifies data by determining a set of
support vectors, which are members of a set of
training inputs
 SVM has two unique features:
– Based on Structural Risk Minimization principal, SVM
minimizes the generalization error
– The ability to overcome the curse of dimensionality
12
Support vector machine (Cont.)

SVM constructs the classifier by evaluating
a kernel function between two vectors of the
training data instead of explicitly mapping
the training data into the high dimensional
feature space
 So,
SVM is capable of handling a large
number of features
13
Support vector machine (Cont.)

The nonlinear discrimination function of SVM is:
l

 
f ( x )  sgn( i yi K ( xi , xi )  b)
i 1

The Radial Basis Function is used as the kernel
function so, the final discrimination function is:
l
  2

 xi  x .
f ( x )  sgn( i yi e
 b)
i 1
14
Dynamic fuzzy boundary

A hybrid method consisting SVM & fuzzy logic
techniques is used to develop a dynamic and fuzzy
decision boundary

The dynamic decision boundary is based on a set
of support vectors generated by SVM and fuzzed
with fuzzy logic technique

With the hope of two features:
High generalization from SVM &
flexibility from fuzzy logic
15
Dynamic fuzzy boundary (Cont.)

The basic thought of our method is extracting a
fuzzy rule set from support vectors which are the
training result of a SVM

To make the decision boundary dynamic, we train
a SVM several times using different values of
parameters, extract different fuzzy rule sets, and at
last build a dynamic decision boundary according
to the fuzzy rule sets
16
Dynamic fuzzy boundary (Cont.)

The fuzzy rule set would be like:

where
b0  b, A0k  a k (0),
bi   i yi , Aik  a k ( zik ),
k  1,...,n, i  1,...,m.
17
Dynamic fuzzy boundary (Cont.)

From the fuzzy rule set, the binary
discrimination function can be written as
the following form:
m

f ( x )  sgn(
(b0  t )   (bi  t )k 1 aik ( xk  z ik )
n
i 1
m
1   (bi  t )k 1 aik ( xk  z ik )
)
n
i 1
18
Conclusion

Using the proposed method, the decision boundary
can be adjusted easily, and the computing costs
corresponding to different decision boundaries are
different
Larger value of  => higher detection rate & high
computation cost
 Adjusting the decision boundary must be within a
range (when the accuracy is above some level,
increasing the accuracy becomes more difficult)
19
Conclusion (Cont.)

Users may decrease the computation cost
with only a small accuracy sacrifice
 It is also possible to build a dynamic
decision boundary using other popular
artificial intelligence techniques such as,
neural networks, decision tree and Bayesian
Networks
20
Any Question?
21