Một thuật toán chọn lọc âm tính nhanh 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Ệ 90(02): 55 - 58

55

A FAST R-CHUNK DETECTOR-BASED NEGATIVE SELECTION

ALGORITHM

Nguyen Van Truong1*

, Vu Duc Quang1

, Trinh Van Ha2

1College of Education – TNU

2College of Information Technology and Communication- TNU

ABSTRACT

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

disciplines of immunology and computation. Many researches focus on applying immunological

principles to computer security. Negative selection algorithm (NSA) is one of the computational

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

stages: generate a set D of detectors that do not match any element of a given self-set S, then using

these detectors to detect if a given cell is self or nonself. The performance of NSA often bases on

the efficiency of generation and detection. Here, we present an r-chunk detector-based NSA that

reduces the overall runtime complexity significantly.

Keywords: Artificial immune system, negative 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 ones - 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.

The outline of a typical NSA contains two

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

detectors are generated by some random

processes 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

*

Tel: 0915016063; Email: [email protected]

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 an anomaly. This

description is limited to some extent, but

conveys the essential idea.

Figure 1. Model of detector generation

No

No

Yes

Begin

Generate random

candidates

Match self

samples?

Accept as new detector

End

Enough detectors?

Yes

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn