面向大数据环境的检测器快速筛选算法

1、面向大数据环境的检测器快速筛选算法 蔡涛 倪晓蓉 王伟生 牛德姣(江苏大学 计算机科学与通信工程学院 江苏镇江 )( )摘要 筛选成熟检测器是决定人工免疫系统的性能和效率的关键因素，在大数据环境下由于初始检测器的数量极其庞大，造成现有检测器筛选算法时间开销过大的问题。本文针对海量的初始检测器，设计海量初始检测器的分布存储模式，为提高筛选初始检测器的效率提供基础；利用Map/Reduce模型，设计了新型的海量初始检测器快速筛选算法，给出了混合式初始检测器快速筛选架构、海量初始检测器分区检查策略和成熟检测器集优化策略，提高筛选初始检测器的效率，优化成熟检测器。最后在

2、Hadoop集群中，实现了面向大数据环境检测器快速筛选算法原型系统，使用CERT synthethic sendmail data数据集进行了测试与分析，验证了算法能减少58.87%的时间开销，并在初始检测器数量不断增加时保持时间开销的稳定。关键字 检测器生成算法，大数据系统，人工免疫算法，Map/Reduce中图法分类号 TP391 文献标识码 AThe Fast Detector Generation Algorithm for the Big Data SystemCai Tao, Ni Xiaorong, Wang Weisheng, Niu Dejiao(School of Comp

3、uter Science and Telecommunication Engineering, JiangSu University, Zhenjiang, Jiangsu )Abstract The detector generation algorithm is important for the performance and efficiency of artificial immune system. But the time overhead of current detector generation algorithm is too big due to the large n

4、umber of initial detector in the big data system. In this paper, the new distributed initial detector storage strategy is designed to provide the basis for improving the massive initial detector selection efficiency. Then, the new fast detector generation algorithm for the big data system is given b

5、y analyzing the different character of map and reduce stage in Map/reduce model, and it is used to improve the initial detector selection efficiency and optimize the mature detector set. It includes hybrid initial detector selection architecture, massive initial detection partition inspection algori

6、thm and mature detector set optimization algorithm. At last, the fast detector generation algorithm prototype for big data system is realized in Hadoop system. CERT synthethic sendmail data set is used to evaluate and compare with the current detector generation algorithm. The result shows the 58.87

7、% time overhead is reduced, and time overhead can been maintained stability with the number of initial detector increasing.Key Words Detector generation algorithm, Big data system, Artificial immune algorithm, Map/Reduce1 引言基金项目：国家自然科学基金()，浙江省自然科学基金(LY13F) ，江苏省科技支撑项目(BE)，深圳市科技项目(JCYJ)，作者简介：蔡涛，男，上海南汇

8、人，1976年生，副教授，博士，主要研究领域为大数据、人工智能，CCF会员（E20-M）。倪晓蓉，女，江苏盐城人，1989年生，硕士研究生，研究方向为人工智能逆光、大数据系统。王伟生，男，广东汕头人 ，1990年生，硕士研究生，研究方向为信息存储、大数据系统。牛德姣，女，河南叶县人，1978年生，硕士，博士研究生，副教授，研究方向为信息存储。检测器生成算法是影响人工免疫系统（AIS，Artificial Immune System）检测性能和效率的重要因素之一。检测器生成算法的主要工作从初始检测器中筛选成熟检测器，使用匹配算法检查初始检测器与自体是否匹配，选择与所有自体均不匹配的初始检测器作为

9、成熟检测器。Forrest等研究者给出了经典的检测器生成算法，并不断有研究者进行各种改进；为保证所选择成熟检测器对非自体的覆盖率，需要计算全部初始检测器与自体的匹配度后进行筛选，这使得筛选检测器的时间和空间开销与初始检测器的数量密切相关，在初始检测器数量较少的情况下，检测器生成算法能较快的完成筛选检测器的工作。将人工免疫算法用于大数据系统时，初始检测器的数量会达到几十万、甚至上亿的规模，筛选检测器所需的时间与空间开销将非常巨大，导致无法使用现有的人工免疫算法。现有检测器生成算法的研究中，主要是针对如何提高对非自体的识别率，优化自体和检测器的匹配规则，缺乏针对海量初始检测器时可计算性的考虑。因此

10、在大数据系统中应用人工免疫算法时，如何提高筛选检测器的效率是急需解决的重要问题。并行化是提高算法执行速度的常用手段，通过将复杂的计算过程分解为多个可以并行执行的部分，并分布到在多个处理核心上运行以提高执行的速度。但检测器生成算法中匹配规则的计算复杂度较低，传统并行计算方法所提高的计算效率很有限。而在初始检测器数量庞大时，影响筛选检测器时间和空间开销的主要因素是海量初始检测器所导致的巨大匹配检查次数，这是很典型的大数据应用。因此通过构建分布式的海量初始检测器存储系统，引入Map/Reduce模型设计新型的检测器快速筛选算法，利用分布存储节点的并行计算能力提高筛选海量初始检测器的效率是良好的选择。

11、本文首先分析初始检测器数量巨大时，影响检测器生成算法执行速度的因素，在此基础上构建混合式的海量初始检测器快速筛选架构，设计海量初始检测器分区检查策略和成熟检测器集优化策略，实现对海量初始检测器的快速筛选，并实现面向大数据环境检测器快速筛选算法的原型系统，使用通用数据集进行测试与分析。 2 相关工作文献1、2给出了人工免疫系统中经典的否定选择算法、贪心检测器生成算法、r连续位匹配规则等；文献3引入多种群遗传算法，提高所生成检测器对非自体的覆盖率；文献4、5给出了检测器克隆选择算法；文献6设计了动态的克隆选择算法；文献7、8给出了抗独特型克隆选择算法，提高了生成检测器的效率；文献9引入聚类算法提高

12、检测器的生成速度；文献10针对基于海明距离的匹配规则，给出了启发式检测器生成算法；文献11通过改变初始检测器的生成方法，提高生成成熟监测器的效率，提高成熟检测器检测非自体的效率和准确性。文献12设计了Map/Reduce计算模型，用于解决分布式存储系统中海量数据的计算问题；文献13给出了大数据系统的特征，针对流式计算系统，分析了目前大数据流式计算在低延迟、高吞吐、持续可靠运行方面存在的技术挑战；文献14-16给出了大数据流式计算系统的架构，以及大数据流式计算与复杂事件处理的关键技术；文献17介绍了Map/Reduce和传统数据库技术的融合。3 海量初始检测器快速筛选算法 检测器生成算法中需要使

13、用匹配规则检查每个自体和每个初始检测器，才能选择出成熟的检测器，因此筛选检测器的效率与初始检测器和自体数量密切相关，所需进行匹配检查的次数与初始检测器和自体数量之间呈指数级递增关系。在大数据环境下，必然出现海量的初始检测器或自体，现有检测器生成算法无法在有限时间内完成筛选初始检测器的任务。因此在大数据环境下提高筛选检测器的效率是急需解决的关键问题。人工免疫算法中，自体与初始检测器是两个互补的集合；因此在大数据环境下，当自体的数量较少时，初始检测器必然非常巨大，反之亦然。我们针对初始检测器数量巨大的情况，设计快速的初始检查器筛选算法，利用多个节点的分布式计算能力提高与自体匹配检查的速度，再进行汇

14、总，从而快速构建成熟监测器集。 我们首先给出海量初始检测器快速筛选算法的结构，再给出各阶段的具体流程。3.1 混合式海量初始检测器快速筛选架构我们针对大数据环境下海量初始检测器和有限自体的特点，适应初始检测器筛选算法的要求，通过初始检测器和自体的合理冗余与分布，构建适合快速筛选海量初始检测器的环境。首先改变现有检测器生成算法中集中存储初始检测器的方式，将海量初始检测器分散存储到Hadoop集群中的各个存储与计算节点中，为快速筛选初始检测器奠定基础。同时改变自体的存储方式，在每个存储与计算节点中均存储数量较小的自体集，为筛选初始检测器提供依据。由此我们设计了混合式的海量初始检测器快速筛选架构，如

15、图1所示。图1 混合式海量初始检测器快速筛选架构在Hadoop集群中分散存储海量的初始检测器，能利用存储与计算节点的并行计算能力提高检查初始检测器与自体匹配的效率；而在各个存储与计算节点中冗余保存数量相对较少的自体，能使得各个存储与计算节点都能分担检查初始检测器的任务。使用Map/Reduce模型，能将海量初始检测器筛选算法分为分区检查和汇总优化两个阶段，首先利用Hadoop集群中的存储与计算节点分布式检查海量初始检测器是否与自体匹配，并将相应结果提交给优化节点，优化节点再根据检查结果挑选最优的若干初始检测器构成成熟检测器集。3.2 海量初始检测器分区检查策略利用Map/Reduce模型中Ma

16、p阶段在各存储与计算节点中分布式并发执行的特点，在将海量初始检测器子集保存到各存储与计算节点的基础上，设计海量初始检测器分区监测策略。Detector_Optimization(detector_set,detector_mature)对detector_set中的检测器按照最大匹配度max_match从小到大进行排序, 构建集合detector_op;While (detector_mature 中的检测器数量未达到系统的设定值)取出detector_op中的第一个候选成熟检测器,放入detector_mature集中;将该候选成熟检测器从detector_op中删除;首先将数量有限的自体保

17、存到存储与计算节点的内存中，依据匹配规则，与该存储与计算节点海量初始检测器子集中的检测器进行匹配检查，判断该海量初始检测器子集中的那些初始检测器能成为候选成熟检测器，同时将候选成熟检测器以及与自体之间的最大匹配值发送给优化节点，具体步骤如图2所示。其中detector_subset表示某个存储与计算节点中保存的海量初始检测器子集，self_set表示自体集。Partition_Selection(detector_subset, self_set)While (detector_subset中还有未检查的初始检测器)取出还未检查的初始检测器;设置最大匹配度max_match的值为0;设置该检测

18、器是否能为候选成熟检测器的标志flag=1;While (self_set中还有未检查的自体) 使用匹配规则检查初始检测器与自体的匹配度m; If (匹配度m max_match) max_match=m; else 该检测器不能成为候选成熟检测器,设置flag=0;If (flag=1) 向优化节点输出该候选成熟检测器、以及与自体之间的最大匹配度max_match;图2 海量初始检测器分区检查策略海量初始检测器分区检查策略利用了Map/Reduce模型中Map阶段分布式执行的特点，在将海量初始检测器分区分布存储到集群中不同存储与计算节点的基础上，每个存储与计算节点中分别检查对应分区中初始检测

19、器是否能成为候选成熟检测器，能利用大量存储与计算节点的分布式并行计算能力提高检查初始检测器效率；同时各存储与计算节点仅将候选成熟检测器提交给优化节点，能有效减少网络通信量。3.3 成熟检测器集优化策略人工免疫系统中一般仅仅使用一定数量的成熟检测器检测非自体，各存储与计算节点筛选的候选成熟检测器通常远多与检测非自体所需的成熟检测器，但各个候选成熟检测器在检测非自体能力等方面存在差异，因此需要合理选择部分候选成熟检测器用于人工免疫系统检测非自体。集群中各存储与计算节点在反馈候选成熟检测器的同时也反馈了与自体之间的最大匹配度，这反映了候选成熟检测器与自体之间的相识程度，而候选成熟检测器对非自体的覆盖

20、能力则与之相反。我们设计成熟检测器优化策略，在优化节点中利用Reduce阶段对候选成熟检测器进行整理和优化，挑选最适合的候选成熟检测器用于检测非自体，具体步骤如图3所示。其中detector_set表示候选成熟检测器集，保存全部存储与计算节点发送给优化节点的候选成熟检测器；detector_mature表示成熟检测器集，保存优化后用于检测非自体的成熟检测器。图3 成熟检测器集优化策略成熟检测器集优化策略能依据候选成熟检测器与自体的匹配度，优先选择与自体匹配度小的检测器构建成熟检测器集，从而提高所构建的成熟检测器集对非自体的检测率和检测效率；集群中各存储与计算节点使用海量初始检测器分区检查策略时

21、仅将候选成熟检测器提交给了优化节点，因此优化节点中所需处理的候选成熟检测器数量非常有限，保证了从候选成熟检测器集中选择成熟检测器时的效率。4 系统原型的测试与分析我们构建了拥有四个节点的Hadoop集群，采用二进制字符串的形式表示自体、初始检测器和成熟检测器，使用r连续位匹配规则判断初始检测器与自体是否匹配，在存储和计算节点增加海量初始检测器分区检查子模块，主控节点增加成熟检测器优化子模块构成优化节点，实现面向大数据环境检测器快速筛选算法的原型系统。原型系统中，包括一个主控节点和三个存储和计算节点，配置如表1所示。表1 原型系统的配置主控节点存储和计算节点1和2存储和计算节点3CPUIntel

22、 Core2 Duo CPU E7400 2.80GHzIntel Pentium 4 CPU 2.93GHz内存2GB1GB操作系统Centos6.3Centos6.3使用用于email安全检测的标准数据集CERT synthethic sendmail data作为测试数据集，通过抽取CERT synthethic sendmail data中的记录，解析成24位二进制字符串构建自体集。4.1 生成检测器所需的时间开销我们同时也实现了传统检测器生成算法的原型系统，用于比较。设置初始检测器的数量分别为5万、10万、20万、50万、100万，自体数据为5000，测试传统检测器生成算法和面向大数

23、据环境检测器快速筛选算法的时间开销，结果如图2所示。Fig.2 Total time cost图2 不同监测器生成算法的时间开销从图2可知，在初始检测器的数量分别从5万增加到100万，相比传统的检测器生成算法，面向大数据环境检测器快速筛选算法均能明显减少生成检测器所需的时间开销，所减少的时间开销在58.87%-83.17%之间；同时随着初始检测器数量的大幅度增加，面向大数据环境检测器快速筛选算法所减少的时间开销呈现缓慢上升，这是由于存储和计算节点的数量没有增加，而每个存储和计算节点中需要处理的初始检测器数量上升，从而导致了总时间开销的增加；但相比传统检测器生成算法，时间开销的增加幅度明显减少；

24、这验证了面向大数据环境检测器快速筛选算法具有显著减低生成检测器所需时间开销的能力。4.2 初始检测器数量变化时分区检查的时间开销设置初始检测器的数量分别为5万、10万、20万、50万、100万、500万、1000万，自体数据为5000，测试海量初始检测器分区检查所需的时间开销，与面向大数据环境检测器快速筛选算法总时间开销进行比较。结果如图3所示。 Fig.3 Time cost of partition selection stage and total with the different number of original detector图3初始检测器数量变化时算法总时间开销与分区检查

25、阶段的时间开销从图3中可知，海量初始检测器分区检查所需的时间开销随着初始检测器数量的增加而上升，上升幅度与面向大数据环境检测器快速筛选算法总的时间开销基本一致；同时海量初始检测器分区检查所需的时间开销占据了生成检测器总时间开销的75%以上；因此海量初始检测器的分区检查是影响面向大数据环境检测器筛选算法效率的主要因素。当前Hadoop集群中仅有三个节点执行海量初始检测器分区检查子模块，在增加节点数量后可有效的减低海量初始检测器分区检查所需的时间开销，进而提高面向大数据环境检测器快速筛选算法的效率。4.3 节点数量变化时分区检查的时间开销设置初始检测器的数量为100万，增加集群中存储和计算节点的数

26、量，分别为3、4、5和6个，测试海量初始检测器分区检查的时间开销，并与检测器快速筛选算法的总时间开销进行比较。结果如图4所示。Fig.4 Time cost of partition selection stage and total with different number of Map stage nodes图4 存储和计算节点数量变化时算法总时间开销与分区检查阶段的时间开销从图4中可以发现，通过增加集群的存储和计算节点数量，海量初始检测器分区检查所需的时间开销明显减少，当节点数从3增加到6后时间开销减少了接近一半，同时面向大数据环境检测器快速筛选算法的时间开销也呈现明显下降趋势；这是由

27、于增加存储和计算节点，能有效的减少每个存储和计算节点需要检查的初始检测器数量，从而减少了检查海量初始检测器所需的时间开销。这验证了，虽然海量初始检测器分区检查所需的时间开销占生成检测器总时间开销的75%以上，但通过增加集群节点数量能明显减少所需的时间开销，从而在初始检测器数量不断增加时，仍然能快速生成检测器。4.4 优化成熟检测器集的时间开销采用同样的设置参数，测试成熟检测器集优化所需的时间开销，并与面向大数据环境检测器快速筛选算法总时间开销进行比较。结果如图5所示。Fig.5 Time cost of Partition Selection stage and Detector_Optimi

28、zation Stage图5 分区检查阶段、和成熟检测器优化阶段的时间开销从图5中可以发现，优化成熟检测器集所需的时间开销同样也随着初始检测器数量的增加而上升，但增加幅度明显小于初始检测器数量增加的幅度，这是由于海量初始检测器分区检查之后所产生的候选成熟检测器数量已非常有限；同时优化成熟检测器集所需的时间开销仅占生成检测器总时间开销的25%以内，对面向大数据环境检测器筛选算法效率的影响很小；因此集群中一个节点足以完成优化成熟检测器集的任务。5 总结检测器生成算法是人工免疫系统的重要组成部分，也是决定人工免疫系统准确性和效率的关键因素。在大数据环境下，现有检测器生成算法难以在有限的时间内完成对数

29、量庞大的初始检测器的筛选。本文针对初始检测器数量庞大的情况，给出了混合式的初始检测器快速筛选架构，通过将海量初始检测器分布存储，为快速筛选检测器奠定基础；设计了海量初始检测器分区检查策略和成熟检测器集优化策略，利用Map/Reduce模型中，Map和Reduce阶段的不同特性，提高筛选初始检测器的效率，优化成熟检测器；并在Hadoop集群中实现了原型系统，使用CERT synthethic sendmail data数据集进行了测试与分析，结果表明了面向大数据环境的检测器快速筛选算法能减少58.87%的时间开销，并能在初始检测器数量不断增加时保持时间开销的稳定。目前面向大数据环境检测器快速筛选

30、算法主要针对如何提高筛选成熟检测器时效率，保证人工一算法在大数据环境下的可用性方面；下一步我们拟针对大数据环境特点，对检测器表示方法、匹配规则、检测率和对非自体的覆盖率等方面展开研究。参 考 文 献1 Forrest S, Helman P. An Immunological Approach to Change Detection: Algorithms, Analysis, and Implications C Proceedings of the 1996 IEEE Symposium on Computer Security and Privacy .1996:192-2112 For

31、rest S, Perelson A S, Allen S, et al. Self-Nonself Discrimination in a ComputerC / Proceedings of 1994 IEEE Symposium on Research in Security and Privacy. 1994:202-212 3 杨东勇,陈晋因.基于多种群遗传算法的检测器生成算法研究J.自动化学报,2009,35(4):425-432.4 de Castro LN, von Zuben FJ. The clonal selection algorithm with engineerin

32、g applicationsJ. In: Langdon WB, Cantu-Paz E, Mathias KE, Roy R, Davis D, eds. Proc. of the 2002 GECCO, Workshop on Artificial Immune Systems and Their Applications. San Francisco: Morgan Kaufmann Publishers, 2000. 3637.5 De Castro L N, Von Zuben F J. Learning and optimization using the clonal selec

33、tion principleJ. IEEE Transactions on Evolutionary Computation, 2002, 6(3): 239-251.6 Kim J, Bentley PJ. Towards an artificial immune system for network intrusion detection: An investigation of clonal selection with a negative selection operator. In: Kim JH, Zhang BT, Fogel G, Kuscu I, edsC. Proc. o

34、f the 2001 Congress on Evolutionary Computation. Piscataway: IEEE Press, 2001. 12441252. 7 焦李成, 杜海峰, 刘 芳,等. 免疫优化计算、学习与识别M.北京:科学出版社, 20068 张立宁,公茂果,焦李成,马文萍.抗独特型克隆选择算法J.软件学报,2009,20(5):1269-12819 AGRAWAL R, SRIKANT R Fast algorithms for mining association rules C / / Proceeding of the 20th VLDB Confere

35、nce. Santiago: Morgan Kaufmann,1994:487-49910 Wenjian Luo, Zeming Zhang, Xufa Wang. A Heuristic Detector Generation Algorithm for Negative Selection Algorithm with Hamming Distance Partial Matching RuleC. Proceedings of the 5th International Conference on Artificial Immune Systems (ICARIS-2006), Lecture Notes