Research on Anomaly Detection Method Based on Improved Negative Selection Algorithm

doi:10.3969/j.issn.1671-1122.2020.10.010

Abstract

Abstract:

Artificial immune theory is currently widely used in intrusion detection systems to solve the problem of not being able to identify unknown anomalies. The most used one is the negative selection algorithm. The traditional real-valued negative selection algorithm generates candidate detectors in a random manner. The time complexity of mature detector generation increases exponentially with the rise of the number of self sets , leading to a long time-consuming in training phase. In order to solve the problem of excessive time consumption in the process of detector generation, this paper proposes a real-valued negative selection algorithm based on neighborhood searching. The algorithm aims at finding self objects that fall in the neighborhood of the candidate detector and using these objects to create a new self set, with a view to improving the generation efficiency of mature detectors. In this paper, a negative selection algorithm based on neighborhood searching is used as the core to construct an anomaly detection model NSRNSAADM. Experiments are carried out on this model to verify the performance of the neighborhood searching based negative selection algorithm. Experiments show that the method proposed in this paper can reduce the time required for the self-tolerance process while ensuring a certain detection rate and false alarm rate.

Key words: negative selection algorithm, neighborhood searching, anomaly detection

CLC Number:

TP309

WANG Yudi, LIU Xiaojie, WANG Yunpeng. Research on Anomaly Detection Method Based on Improved Negative Selection Algorithm[J]. Netinfo Security, 2020, 20(10): 75-82.

Figures/Tables 12

References 15

[1]	FORREST S, PERELSON A S. Self-nonself Discrimination in a Computer [C]//IEEE. IEEE SymposiumonSecurity and Privacy, May 16-18, 1994, Oakland, USA. New York: IEEE, 1994: 202-213.
[2]	GONZALEZ F, DASGUPTA D. Anomaly Detection Using Real-valued Negative Selection[J]. Genetic Programming & Evolvable Machines, 2003,4(4):383-403.
[3]	ZHOU J, DASGUPTA D. V-detector: An Efficient Negative Selection Algorithm with “Probably Adequate” Detector Coverage[J]. Inf Sci, 2009,179(10):1390-1406.
[4]	FOULADVAND S, OSAREH A, SHADGAR B, et al. DENSA: Sn Effective Negative Selection Algorithm with Flexible Boundaries for Self-space and Dynamic Numberof detectors[J]. Engineering Applications of Artificial Intelligence, 2017,62(1):359-372.
[5]	YANG Tao, CHEN Wen, LIU Zhengjun, et al. A Real Value Negative Selection Algorithm Based on Antibody Evolution for Anomaly Detection [C]//IEEE. 2018 Tenth International Conference on Advanced Computational Intelligence (ICACI), May 29-30, 2018, Xiamen, China. New York: IEEE, 2018: 692-699.
[6]	CHEN Wen, LI Tao, LIU Xiaojie, et al. A Negative Selection Algorithm Based on Self-set Hierarchical Clustering[J]. Science in China: Information Science, 2013,43(5):611-625.
	陈文, 李涛, 刘晓洁, 等. 一种基于自体集层次聚类的否定选择算法[J]. 中国科学:信息科学, 2013,43(5):611-625.
[7]	ZHANG Fan, CHEN Wen, LI Tao, et al. An Antigen Space Triangulation Coverage Based Real-Value Negative Selection Algorithm[J]. IEEE Access, 2019,19(7):51886-51898.
[8]	LIU Zhengjun, GAO Jiangjin, YANG Tao. Improved Negative Selection Algorithm Based on Antigen Soft Subspace Clustering[J]. Application Research of Computer, 2018,18(3):680-684.
	刘正军, 高江锦, 杨韬. 一种基于抗原软子空间聚类的否定选择算法[J]. 计算机应用研究, 2018,18(3):680-684.
[9]	WANG Yi, LI Tao, HU Fangdong. Augmented Negative Selection Algorithm with Complete RandomSubspace Technique for Anomaly Detection [C]//IEEE. 2019 IEEE 2nd International Conference on Information and Computer Technologies (ICICT), May 14-17, 2015, Kahului, HI, USA. New York: IEEE, 2019: 1-4.
[10]	CHAO Yang, LIN Jia, CHEN Bingqiu, et al. Negative Selection Algorithm Basedon Antigen Density Clustering[J]. IEEE Access, 2020,20(8):4496-4497.
	朝阳, 林佳, 陈炳秋, 等. 基于抗体空间密度聚类的否定选择算法[J]. IEEE Access, 2020,20(8):4496-4497.
[11]	LIU Zhengjun, TAO Li, JIN Yang, et al. An Improved Negative Selection Algorithm Based on Subspace Density Seeking[J]. IEEE Access, 2017,17(5):12189-12198.
	刘正军, 陶力, 金阳, 等. 基于子空间密度搜索的否定选择算法[J]. IEEE Access, 2017,17(5):12189-12198.
[12]	ZHANG Fan, YANG Jin, LI Tao, et al. DnyNSA: A Novel Real-Value Based Negative Selection Algorithm [C]//IEEE.8th IEEE Symposium Series on Computational Intelligence(SSCI), November 18-21, 2018, Bangalore, India. New York: IEEE, 2018: 1104-1109.
[13]	GONZALEZ F, DASGUPTA D, NINO L F. A Randomized Real-Valued Negative Selection Algorithm [C]//ICARIS. International Conferences on Artificial Immune Systems, September 1-3, 2003, Edinburgh, UK. USA: Proceeding of ICARIS , 2003: 261-272.
[14]	ZHENG Xufei, FANG Yonghui, LI Tao. Secondary Negative Selection Algorithm[J]. Science in China: Information Science, 2013,43(4):529-544.
	郑旭飞, 方永慧, 李涛. 二次否定选择算法[J]. 中国科学:信息科学, 2013,43(4):529-544.
[15]	B SCHMIDT, A Al-FUQAHA. A New Approach to Optimized Negative Selection [C]//IEEE. 2016 IEEE Congress on Evolutionary Computation(CEC), July 24-29, 2016, Vancouver, Canada. New York: IEEE, 2016: 1793-1799.

算法	时间复杂度
RNSA	$O\left( \frac{\left\| D \right\|{{N}_{S}}}{{{\left( 1-p \right)}^{{{N}_{S}}}}} \right)$^[3]
CB-RNSA	$O\left( {{N}_{S}}\left\| C \right\|+(1-p){{N}_{S}}(\left\| D \right\|+\left\| C \right\|) \right)$^[6]
V-Detector	$O\left( \frac{Num\sum\limits_{i=0}^{{{N}_{d}}-1}{{{C}_{i}}}{{N}_{S}}\left( 1-{{\left( 1-p \right)}^{{{N}_{d}}}} \right)}{{{N}_{d}}p{{\left( 1-p \right)}^{{{N}_{s}}}}{{\left( 1-p \right)}^{{{N}_{d}}-1}}} \right)$^[6]
NS-RNSA	$O\left( mq\text{log}{{N}_{S}}+\frac{\left\| D \right\|\left\| L \right\|}{{{(1-p)}^{\left\| L \right\|}}} \right)$

指标	含义及计算表达式
Accuracy	最直观的指标,表示模型判断正确数据占总数据的比例： $Accuracy\text{=}\frac{TP\text{+}TN}{TP\text{+}TN\text{+}FP\text{+}FN}$
FPR	针对数据集中所有正例而言,表示模型错误判断的正例占数据集中所有正例样本的比例： $FPR\text{=}\frac{FP}{FP\text{+}TN}$
FNR	针对数据集中所有反例而言,表示模型错误判断的反例占数据集中所有反例样本的比例： $FNR\text{=}\frac{FN}{FN\text{+}TP}$