基于改进否定选择算法的异常检测方法研究

doi:10.3969/j.issn.1671-1122.2020.10.010

信息网络安全 ›› 2020, Vol. 20 ›› Issue (10): 75-82.doi: 10.3969/j.issn.1671-1122.2020.10.010

基于改进否定选择算法的异常检测方法研究

王玉娣, 刘晓洁, 王运鹏()

四川大学网络空间安全学院,成都 610065

收稿日期:2020-08-03 出版日期:2020-10-10 发布日期:2020-11-25
通讯作者: 王运鹏 E-mail:yunhuasheng@163.com
作者简介:王玉娣（1995—）,女,辽宁,硕士研究生,主要研究方向为人工免疫理论|刘晓洁（1965—）,女,江苏,教授,硕士,主要研究方向为网络信息对抗与保护技术、数字虚拟资产保护技术|王运鹏（1984—）,男,河南,讲师,博士,主要研究方向为信息安全、区块链。
基金资助:
国家自然科学基金(U1736212);国家自然科学基金(U19A2068);四川省重点研发项目(2018GZ0183);四川省重点研发项目(20ZDYF3145);中国博士后科学基金(2019TQ0217)

Research on Anomaly Detection Method Based on Improved Negative Selection Algorithm

WANG Yudi, LIU Xiaojie, WANG Yunpeng()

College of Cybersecurity, Sichuan University, Chengdu 610065, China

Received:2020-08-03 Online:2020-10-10 Published:2020-11-25
Contact: WANG Yunpeng E-mail:yunhuasheng@163.com

摘要/Abstract

摘要：

人工免疫理论目前被广泛应用于入侵检测系统,以解决无法识别的未知异常问题,应用最多的是否定选择算法。传统的实值否定选择算法通过随机方式生成候选检测器,随着自体集数量的增多,成熟检测器生成的时间复杂度呈指数级增长,导致训练阶段耗费时间长。为解决检测器生成过程中时间消耗过长问题,文章提出基于邻域搜索的实值否定选择算法（Real-Valued Negative Selection Algorithm Based on Neighborhood Searching,NS-RNSA）,通过邻域搜索算法找到落在候选检测器邻域的自体样本点,利用这些样本点构建新的自体集合,以提高成熟检测器生成效率。文章以NS-RNSA算法为核心构建异常检测模型NSRNSAADM,在此模型基础上进行实验,验证基于邻域搜索的否定选择算法的性能。实验表明,文章提出的方法在保证检测率、误报率的基础上,能够降低自体耐受过程所需时间。

关键词: 否定选择算法, 邻域搜索, 异常检测

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

中图分类号:

TP309

王玉娣, 刘晓洁, 王运鹏. 基于改进否定选择算法的异常检测方法研究[J]. 信息网络安全, 2020, 20(10): 75-82.

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.

图/表 12

图1

表1

图2

表2

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 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}$

基于改进否定选择算法的异常检测方法研究

Research on Anomaly Detection Method Based on Improved Negative Selection Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 15

相关文章 15

编辑推荐

Metrics

本文评价

[1]	陆佳丽. 基于改进时间序列模型的日志异常检测方法[J]. 信息网络安全, 2020, 20(9): 1-5.
[2]	黄娜, 何泾沙, 吴亚飚, 李建国. 基于LSTM回归模型的内部威胁检测方法[J]. 信息网络安全, 2020, 20(9): 17-21.
[3]	顾兆军, 任怡彤, 刘春波, 王志. 基于一致性预测算法的内网日志检测模型[J]. 信息网络安全, 2020, 20(3): 45-50.
[4]	王伟, 沈旭东. 基于实例的迁移时间序列异常检测算法研究[J]. 信息网络安全, 2019, 19(3): 11-18.
[5]	杨威超, 郭渊博, 钟雅, 甄帅辉. 基于设备型号分类和BP神经网络的物联网流量异常检测[J]. 信息网络安全, 2019, 19(12): 53-63.
[6]	朱海麒, 姜峰. 人工智能时代面向运维数据的异常检测技术研究与分析[J]. 信息网络安全, 2019, 19(11): 24-35.
[7]	邓海莲, 刘宇靖, 葛一漩, 苏金树. 域间路由异常检测技术研究[J]. 信息网络安全, 2019, 19(11): 63-70.
[8]	李巍, 狄晓晓, 王迪, 李云春. 基于子图的服务器网络行为建模及异常检测方法研究[J]. 信息网络安全, 2018, 18(2): 1-9.
[9]	何利, 姚元辉. 基于上下文聚类的云虚拟机异常检测与识别策略[J]. 信息网络安全, 2018, 18(12): 54-65.
[10]	赵刚, 姚兴仁. 基于用户画像的异常行为检测模型[J]. 信息网络安全, 2017, 17(7): 18-24.
[11]	吴鑫, 严岳松, 刘晓然. 基于改进HMM的程序行为异常检测方法[J]. 信息网络安全, 2016, 16(9): 108-112.
[12]	杨连群, 温晋英, 刘树发, 王峰. 一种改进的图分割算法在用户行为异常检测中的应用[J]. 信息网络安全, 2016, 16(6): 35-40.
[13]	何明亮, 陈泽茂, 左进. 基于多窗口机制的聚类异常检测算法[J]. 信息网络安全, 2016, 16(11): 33-39.
[14]	刘汝隽, 辛阳. 网络安全数据可视分析系统的设计与实现[J]. 信息网络安全, 2016, 16(11): 40-44.
[15]	汤健, 孙春来, 毛克峰, 贾美英. 基于主元分析和互信息维数约简策略的网络入侵异常检测[J]. 信息网络安全, 2015, 15(9): 78-83.