Một cách nhìn khác về thuật toán chọn lọc âm tính dựa trên bộ dò R -Chunk

Nguyễn Văn Trường và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 45 - 49

45

ANOTHER LOOK AT R-CHUNK DETECTOR-BASED NEGATIVE

SELECTION ALGORITHM

Nguyen Van Truong1*, Trinh Van Ha2

1College of Education – TNU

2College of Information and Telecommunication Technology - TNU

SUMMARY

Artificial immune system (AIS) is a diverse research area that combines the disciplines of

immunology and computation. Negative selection algorithm (NSA) is one of the computational

models of self/nonself discrimination can be designed for anomaly detection in AIS. It contains

two stages: generate a set D of detectors that do not match any element of a given self-set S. Then,

use these detectors to detect whether a given cell is self or nonself. One fast r-chunk detector-based

NSA (rNSA) originally introduced by M. Elberfeld et al. in 2009 [6], the complete generating

detector can detect all nonself space. Here, we develop negative-dual algorithm, called r-chunk

detector-based positive selection algorithm (rPSA), to detect the complement of the nonself space

with the same memory complexity but reduces runtime complexities.

Keywords: Artificial immune system, negative selection algorithm, positive selection algorithm,

computer security, r-chunk detector.

INTRODUCTION*

AIS is inspired by the observation of the

behaviors and the interaction of normal

component of biological systems - the self -

and abnormal one - the nonself. Real immune

system generates T cells randomly with the

ability to detect harmful antigens. The

receptors of new born T cells are assembled

from combined gene fragments. In an organ

called the thymus, the T cells are then

exposed to proteins from self, and cells whose

receptors match such a self protein are bound

to die. Only those that survive negative

selection may leave the thymus, and use their

receptors to screen the organism for nonself

proteins. This process is known as negative

selection and is applicable of computer

security. An algorithmic abstraction of this

biological process is called a NSA.

NSA has been used successfully both in

engineering applications and by naturally

occurring biological systems like human. This

algorithm learns to distinguish a set of

normally occurring patterns (self) from its

complement (nonself) when only positive

instances of the class are available. For

example, it can distinguish safe data from

*

Tel: 0915 016063, Email: nvtruongtn@gmail.com

noise data or even normal processes in a

computer from the others, etc. There are

many well known change-detection and

check-sum algorithms that solve a restricted

form of the anomaly-detection problem, such

as MD5 or SHA algorithms. Here, it assumes

that self is known exactly, is small enough to

be stored in a single location, remains

constantly, and can be unambiguously

distinguished from nonself. However, for

cases in which these assumptions do not hold,

the discrimination task is more challenging,

and in these situations, the NSA may be

appropriate.

The outline of a typical NSA contains two

stages [2]. In the generation stage (Fig. 1), the

detectors are generated by some random

process and censored by trying to match

given self samples taken from set S. Those

candidates that match are eliminated and the

rest are kept as detectors in set D. In the

detection stage (Fig. 2), the collection of

detectors (or detector set) is used to verify

whether an incoming data instance is self or

nonself. If it matches any detector, it is

claimed as nonself or anomaly. Each detector

will cover (match) a subset of the nonself set.

By generating sufficient numbers of

independent detectors, good coverage of the

nonself set will be obtained.