Transcript PowerPoint 演示文稿

A Change-Detection Algorithm Inspired by the Immune System
Stephanie Forrest,
Lawrence Allen,
Alan S. Perelson,
Rajesh Cherukuri
Presented by Wei Mao
Human Immune System
-What is it?
The basic idea of the human immune system is the ability
to distinguish self, which is normal, from non-self, which
is abnormal.
- How does it work?
For a human body, various detector cells, called antibodies,
are continuously generated and distributed to a whole body.
The distributed antibodies monitor all living cells and detect
non-self cells, called antigens, invading into a human body.
Characteristics of Human Immune System
- The human immune system is distributed:
The human immune system is implemented through the
interactions between a large number of different types of cells,
instead of employing a central coordinator
- Each copy of the detection is unique and independent:
The human immune system generates various groups of
antibodies to detect different antigens. Its evolution
mechanism through natural selection of gene libraries and
clone selection maintains a number of different sets of
antibodies. Therefore, each antibody set is unique and
independent.
Characteristics of Human Immune System (Cont’d)
- Detection of previously unseen foreign material:
Immune system remember previous infections and mount a more
aggressive response against those that have been seen before.
However, in the case of a novel infection, the immune system
initiates a preliminary response, evolving new detectors that are
specialized for the infection.
- Detection is imperfect:
Not all antigen are well matched by a preexisting detector. The
immune system uses two strategies to confront this problem learning (during The preliminary response) and then distributed
new detectors
Characteristics of Human Immune System (Cont’d)
- Self-organization
The overall immune response is composed of three evolutionary
stages:
- Gene library evolution: It generating effective antibody
- Negative selection: It eliminate inappropriate antibodies
- Clone selection: It clone well-performing antibodies.
These three stages are self-organizing rather than being directed
by a central organ or predefined information.
Network-based Intrusion Detection System
The main goal of intrusion detection is to detect unauthorized
use, misuse and abuse of computer systems by both system
insiders and external intruders. It monitors any number of
hosts on a network by scrutinizing the audit trails of multiple
hosts and network traffic.
Mapping from HIS to AIS
Two types of detectors:
- An anomaly detector: The anomaly detector establishes the
profiles of normal activities of users, systems, system resources,
network traffic and/or services and detects intrusions by
identifying significant deviations from the normal behaviors
patterns observed from profiles.
- A misuse detector: The misuse detector defines suspicious
misuse signatures based on known system vulnerabilities and a
security policy.
Negative Selection Algorithm
- Why need it?
When a new antibody is generated, the gene segments of different
gene libraries are randomly selected and concatenated in a random
order, see figure 1. The main idea of this gene expression mechanism
is that a vast number of new antibodies can be generated from new
combinations of gene segments in the gene libraries.
Negative Selection Algorithm (Cont’d)
However, this mechanism introduces a critical problem. The
new antibody can bind not only to harmful antigens but also to
essential self cells. To prevent such serious damage, the
human immune system employs negative selection. This
process eliminates immature antibodies, which bind to self
cells passing by the thymus and the bone marrow. From newly
generated antibodies, only those which do not bind to any self
cell are released from the thymus and the bone marrow and
distribute throughout the whole human body to monitor other
living cells. Therefore, the negative selection stage of the
human immune system is important to assure that the
generated antibodies do not to attack self cells.
Negative Selection Algorithm (Cont’d)
-How it works:
This algorithm consistes of three phases: defining self, generating
detectors and monitoring the occurrence of anomalies. It regards
the profiled normal patterns as ‘self’ patterns. The second phase, it
generates a number of random patterns that are compared to each
self pattern defined in the first phase. If any randomly generated
pattern matches a self pattern, this pattern fails to become a
detector and thus it is removed. Otherwise, it becomes a ‘detector’
pattern and monitors subsequent profiled patterns of the monitored
system. During the monitoring stage, if a ‘detector’ pattern matches
any newly profiled pattern, it is then considered that new anomaly
must have occurred in the monitored system.
Negative Selection Algorithm (Cont’d)
-Define self:
AIS (Artificial Immune System) addresses a similar problem,
in which we define a set S of equal-length strings to be “protected”
(self). More commonly, a single string (representing programs,
files, activity patterns) are segmented into set of strings with equal
length. All the other strings that are not included in the original set
S are called nonself N. These two sets form a universe U
(i.e. S ∪ N=U, S ∩ N=). The string here could be a string of
bits, a string of assembly instructions, a string of ASCII characters
or a pattern of activities.
Negative Selection Algorithm (Cont’d)
- Generating detectors:
AIS (Artificial Immune System) generates a set of R
detectors that are circulating around a distributed
environment. The detectors will be the string of the same
length as the “protected” strings and more importantly, these
detectors must not match any of the protected data.
Negative Selection Algorithm (Cont’d)
- Matching process:
In order to keep a sufficiently small set of detectors and
make sure a relatively constant size of it with the increase
of “protected” string, exact non-matching cannot be
adopted.
- Matching rule:
Two equal-length strings match if they are equal in r
contiguous positions.
Negative Selection Algorithm (Cont’d)
An example of matching rule for ASCII characters:
Alphabet={a,b,c,d}
Length=8
R<=3
S=abadcbab
D=cagdcbba
Negative Selection Algorithm (Cont’d)
An example of matching rule for binary bits:
Negative Selection Algorithm (Cont’d)
Matching algorithm:
Negative Selection Algorithm (Cont’d)
Monitoring Algorithm:
Advantages
-Unseen anomalies detected
One of the formidable features is that this novel approach does
not define specific anomalies to be detected and thus it does not
require the prior knowledge of anomalies. This feature allows it
to be able to detect previously unseen anomalies.
-Highly adaptive
Since each copy of detectors are unique and independent, each
host can tune their own copy of detectors according to their
own needs and running environment.
Advantages (Cont’d)
-Combination of distributed and local detection
In addition, the detection is distributed and local. That is to say,
an individual detector contains only a subset of the patterns
needed to describe all existing anomalies, and it monitors only
small parts of the system. Therefore, each detector recognizes
only the anomalies of the small section of the system that it
monitors, and the overall abnormal status is diagnosed by the
collection of independent detection results. Moreover, this
distributed detection by local detectors provides robustness
within the system.
Disadvantages
- Excessive computing time
The most significant problem is the excessive computational
time caused by the random generation approach to building
valid detectors. This results in the exponential growth of
computational effort with the size of self patterns
Disadvantages (Cont’d)
- Number of detectors are hard to pre-determined
Moreover, it is very difficult to know whether the number
of generated detectors is large enough that can satisfy the
acceptable detection failure probability. Some other
algorithms like greedy algorithm and negative selection
with niching then were created to tackle these drawback.