免疫计算的测不准有限计算模型
龚 涛, 蔡自兴
(中南大学 信息科学与工程学院, 湖南 长沙, 410083)
摘要: 以人工免疫系统为研究对象,采用可信计算和系统论的方法,构建了免疫计算的测不准有限计算模型,将该模型划分为三层,即固有免疫计算层、适应免疫计算层和并行/分布计算层。这种免疫计算方法在数据库查询的基础上匹配了已知异体的特征,识别了已知异体的类型。此外,该方法在抗体规则匹配的基础上学习了未知异体,记忆了新异体的特征,在数据库中添加了新异体的特征。该模型通过毁灭器消除了异体,抑制了异体的复制和扩散,控制了免疫计算的毁灭机制的双刃性,监控了免疫计算的负载平衡,维护了系统的鲁棒性和安全性,克服了免疫学理论的不完备性的影响。实验结果表明,这种免疫计算机制检测了病毒和故障等异体,识别出该异体是“爱虫”病毒及其感染的文件,并消除了异体,抑制了异体的复制和扩散,确保了系统的安全性和鲁棒性。
关键词: 免疫计算; 测不准有限计算模型; 毁灭机制; 异体识别; 人工智能
中图分类号:TP311 文献标识码:A 文章编号: 1672-7207(2005)05-0755-06
Non-accurately-measurable limited computing model of immune computation
GONG Tao, CAI Zi-xing
(School of Information Science and Engineering, Central South University, Changsha 410083, China)
Abstract: Artificial immune system was investigated using the approaches of trusted computing and systematics, and the non-accurately-measurable limited computing model of immune computation was built. Besides, the model had three tiers, i.e. the innate immune tier, the adaptive immune tier and the parallel/distributed computing tier. In the immune computation, the features of the anomaly were matched through the query in the database, and the type of the anomaly was recognized. Furthermore, unknown anomaly was learnt through the rule matching of the anomaly, the features of new anomaly were memorized, and the features of the new anomaly were added to the database. In the model, the anomaly was eliminated by the destroyer, the clone and proliferating of the anomaly were restrained, and the two blades of the destroying mechanism in the immune computation were controlled. Moreover, the load balance of the immune computation was monitored, the robustness and security of the system were maintained, and the imperfection of the immunology theories was overcome. The experimental results show that the immune computation mechanism detects the anomalies such as worms and faults, recognizes their types, i.e. the love worms and their infected files, and eliminates the anomalies, so that the clone and proliferating of the anomalies are restrained, and the security and robustness of the system are insured.
Key words: immune computation; non-accurately-measurable limited computing model; destroying mechanism; variant recognition; artificial intelligence
人工免疫系统是从免疫学理论和免疫现象启发灵感, 借助人或计算机实现免疫模型、 实现免疫原理和功能的适应性系统[1]。 近年来, 这门技术得到迅速发展, 显示出强大的鲁棒信息处理和解决复杂问题的能力。 人工免疫系统的研究从20世纪80年代中期的免疫学发展而来。 1990年, H.Bersini等使用免疫算法来解决网络适应性问题[2], Y.Ishida利用人工免疫系统解决传感器网络故障诊断问题[3]。 1994年, D.Dasgupta和S.Forrest将免疫算法应用于计算机安全和病毒检测[4], D.E.Cooke和J.E.Hunt开始将免疫算法应用于机器学习领域[5]。 但理论研究的滞后不利于该技术的进一步发展[6]。
近年来, 国内一些研究人员进行人工免疫系统及算法的研究[7]。 曹先彬等提出并实现了包括阴性/阳性选择、 亲和度变异、 非选择和免疫记忆等模块在内的基于人工免疫的入侵预警算法[8]; 肖人彬等研究了人工免疫系统的原理和模型[9]; JIAO Li-cheng等在遗传算法的基础上引入免疫机制, 模仿生物免疫特点[10]; 梁意文等基于免疫原理创建大规模网络入侵检测和预警模型[11]; DING Yong-sheng等设计和创建了基于免疫突现计算的生物网络结构[12]; 葛红和毛宗源对免疫算法的参数问题展开了研究[13]。 本文作者提出了多维教育免疫网络, 将免疫机制用来解决教育网络的安全问题, 并探讨了鲁棒性与免疫性之间的联系[1], 研究了多维教育免疫艾真体, 探讨了如何应用免疫计算技术创建新型网络教育系统。
但这些前沿研究都是模仿国外的经验在免疫学理论和进化算法基础上建立模型, 探讨其在网络安全和控制方面的应用[14-20], 免疫学理论的不完备性注定了此类研究的不足和局限性。 这些局限性一方面是源于自然免疫系统研究的局限性, 另一方面是由于以应用为依托的优良的新免疫计算模型还没有产生。 过去主要从人工免疫机制的正面效果展开研究和计算机模拟, 却忽视了对人工免疫系统缺点的研究, 还没有研究人工免疫系统毁灭机制的负载极限和潜在可能失控自杀行为。 为了抗非典, 需要采用激素降低人体免疫力, 以解救生命, 这一种奇异免疫现象已经警示世人免疫理论还不完备, 免疫系统也有负载极限。 这就需要对人工免疫系统的负载极限和毁灭机制的双刃性等新内容和新方法展开深入的定量研究。 因此, 有必要从反向思维的角度构建免疫计算的测不准有限计算模型, 为免疫计算应用研发提供有力的计算模型和分析工具, 力求有所创新。
综上所述, 免疫计算的测不准有限计算模型不仅是人工免疫系统技术所亟待解决的课题, 而且是智能系统技术发展的内在需求; 它是该领域研究的关键, 有明显新意, 其研究成果必将促进免疫计算的发展。
1 免疫计算的测不准计算模型
免疫计算对外界异体抗原进行识别、 学习和防御操作, 达到系统整体损害的最小化和纯度的最大化, 以实现系统鲁棒性、 安全性和智能性的最大化[1]。 系统的收敛性主要是由集合序列来转化和解决的。
免疫计算有3层: 固有免疫计算层、 自适应免疫计算层和并行/分布计算层。 自适应免疫计算层的算法常称为免疫算法, 只是由于目前对免疫算法的研究, 过于简单, 不能充分体现自适应免疫计算层的自适应性、 异体—自体识别能力、 智能性和鲁棒性等[7]。 GONG Tao等[21]已提出并证明并行计算及其3层负载平衡定理, 采用并行/分布计算层进行免疫计算的并行/分布处理, 以提高效率和功能分布性。
当抗原侵入个体并激活人工免疫系统时, 首先固有免疫计算层将抗原的提取特征信息与数据库中已有的信息相匹配, 毁灭器直接删除已知异体抗原(即在抗原数据库中有相应的异体信息)。
当固有免疫计算层找不到此抗原在数据库中的相应信息时, 就交自适应免疫计算层处理。 先根据抗原的特征信息产生特定抗体, 接着抗体检测、 捕捉并学习抗原的重要信息, 以根据免疫计算的异体检测规则决定此抗原是否为异体。 若此抗原为异体, 就调用防御策略, 将此抗原交毁灭器删除。 否则, 接受此抗原为新自体, 或作为无毒废物排泄处理。
当免疫计算的信息处理量超过单个处理单元的负载能力时, 就进行并行计算; 当免疫计算需要各免疫计算单元协同工作时, 就进行分布计算。
免疫计算的测不准有限计算模型必须通过多学科交叉研究来实现, 包括并行计算、 状态空间、 规则集成、 混沌理论及智能控制的交集结构等相互作用[21-24]。 免疫计算已得到越来越多的应用, 包括优化求解、 设计、 杀毒、 故障诊断、 鲁棒控制、 智能网络、 防止黑客入侵、 容错、 学习、 匹配、 分类与决策等方面。 基于免疫计算的抗灾智能Web系统将得到大量研究, 并应用于实际抗灾系统信息化进程中; 免疫机器人的提出、 研究和开发将会成为智能机器人的一个亮点[23]; 免疫计算在故障诊断中的应用能大大提高其智能度, 增强诊断效果。
免疫计算的3层模型如图1所示。 这个计算模型的关键在于考虑了免疫计算具有免疫应答的负载极限, 这是过去研究过程中被忽略的问题。 免疫应答的负载极限是因抗体的生成需要较长时间而引起的。
图 1 免疫计算的3层模型
Fig. 1 Tri-tier model of immune computation
图1中, 异体抗原的检测是随机的, 根据抗原的信息与免疫系统特征的匹配结果判定抗原是自体还是异体, 即将抗原分为两类。 对于异体抗原, 免疫计算通过固有免疫计算层和自适应免疫计算层进一步确定异体的特征、 具体类型和消除方法, 这就是人工免疫系统对抗原的识别。
固有免疫计算层对抗原的识别是比较简单和快速的, 因为只需要直接将抗原的特征信息与已知异体的特征数据库中的记录相匹配, 可看作是数据库的查询过程。 这个层次的技术是建立在成熟的数据库技术基础上的, 从而实现起来比较容易。 根据查询结果, 可以调用相应记录中消除异体的方法, 例如删除已感染病毒的文件。
自适应免疫计算层对抗原的识别是关键, 这时的对象是未知的异体抗原, 即在数据库中找不到此抗原的异体特征信息。 首先将未知异体抗原的特征信息作为事实与规则集中一些规则的前部匹配, 这些规则是用来推导出异体抗原的类型和消除方法的。 进而, 这些相匹配的规则的后部再用作事实与其他规则相匹配, 如此反复, 通过规则空间中的随机搜索与匹配, 最后得出结论, 也就是推断出异体类型与异体消除方法。 将这些结论记录到数据库中, 从而未知的异体抗原转化为已知的异体抗原, 这就是免疫计算的记忆功能, 能体现一种智能。 这种智能的优点在于, 下一次遇到同种异体抗原时就不需要进行自适应免疫计算层识别, 只需要快速的固有免疫计算层识别就行了, 从而异体抗原的二次响应比第一次响应快得多。
这种用来识别异体抗原的规则称为抗体。 抗体的搜索常是大规模空间的, 抗体的群体处于混沌状态, 因此, 无法同时测出捕获某抗原的抗体和捕获时间。 可见, 免疫计算具有测不准的特征。 这种测不准特征对免疫计算整体特性的研究很重要。
2 免疫计算的有限性和负载平衡
尽管人工免疫系统表现出优越的免疫性、 鲁棒性和智能, 但这只是正常状态下人工免疫系统的特征, 在免疫计算超负荷和严重损害的情况下并不如此乐观。
免疫计算通过抗体和毁灭器消灭异体抗原, 但人工免疫系统的负载能力是有限的。 当大规模未知恶性异体抗原攻击系统时, 抗体识别异体并由毁灭器消除异体的速度可能就赶不上异体抗原的攻击速度和复制速度, 从而导致相关功能的人工免疫子系统受到异体抗原的感染。 这时, 已感染的人工免疫系统部分就被识别为人工免疫系统所不能接受的新异体抗原, 这样又增加了免疫计算的负载, 从而导致免疫计算的识别与消除速度更加赶不上异体抗原的攻击和复制速度, 人工免疫系统的更多部分受到侵害和感染……如此恶性循环下去, 最后导致相关功能的人工免疫子系统走向崩溃, 随即相关功能模块也被摧毁。 因此, 研究免疫计算的有限性和负载平衡是十分必要的。
免疫计算的毁灭机制在良性循环阶段能毁灭外来异体抗原(如计算机病毒), 保护个体的安全, 维护个体的鲁棒性; 但在超负荷恶性循环阶段却逐步毁灭自身的人工免疫系统, 以致毁灭个体, 对个体而言这是免疫计算被人忽视的缺点, 但对上级系统来说这体现了进化规律的优胜劣汰规则。
免疫计算的抗体搜索与匹配可通过基于进化操作的免疫算法完成的[1, 22-24], 目前看来免疫算法要进化成千上百代、 耗费较长时间才能达到抗体与异体抗原的匹配, 因此, 一定时间内捕获异体抗原的抗体数目是有限的, 其最大数目就是免疫应答的负载极限。 当在这段时间内识别异体抗原所需要的抗体数目超过免疫应答的负载极限时, 就造成抗体不足的局面, 即恶性循环阶段的开始。 只有在免疫应答的负载极限允许范围内, 免疫计算的鲁棒性才是好的。 这就是免疫计算的有限性。 超过此负载极限, 免疫计算就会失调, 甚至走向反面, 毁灭自身系统。 因此, 要从变异率、 选择阈值、 抗体生命周期、 复杂性、 解群体的规模等参数优化免疫算法[13], 提高抗体识别异体抗原的速度, 增大免疫应答的负载极限, 改进免疫计算的良性循环。
增大免疫计算的负载极限的另一种途径就是使用并行计算机制, 即调用并行计算机。 并行计算可以提高抗体识别异体抗原的速度, 改善人工免疫系统的负载平衡, 促进免疫计算的良性循环。
例如, 某人工免疫系统1 s内最多能识别并消除平均3个计算机病毒, 这就是此系统免疫计算的极限。 当1 s内有6个计算机病毒对系统发动攻击并复制时, 系统就会超负荷工作, 以至于部分系统被病毒感染而被识别为新的异体抗原, 从而进入恶性循环, 系统逐步崩溃。 这就是超负荷免疫计算的灾难性后果。
但是, 系统调用3节点的并行计算机后, 情形会明显好转。 并行计算机的一个节点1 s内就能最多识别和消除3个计算机病毒, 整个并行计算机1 s内至多能识别和消除9个计算机病毒。 当相同的6个计算机病毒对系统发动攻击并复制时, 每个节点分配到的杀毒任务只是2个计算机病毒, 计算资源占用率约66.6%, 每个节点工作是相当自如的, 不会出现负荷满载或者甚至超负荷情况。 这样, 病毒的识别和消除速度提高了, 人工免疫系统的负载平衡改善了, 免疫计算进入良性循环。 因此, 并行计算是增大免疫计算的极限的好途径之一。
3 异体—自体识别及实验示例
所有可能为异体的外来体称为抗原; 根据异体抗原的特征信息搜索识别和学习此异体抗原的体, 即抗体。 抗体以一定的规则形式决定未知抗原是否为异体, 确定此抗原不是异体后就确认它为新自体。
根据抗体的规则及其功能可建立抗体的2层算法: 检索算法和决策算法, 如图2所示。
图2中, 检索算法将抗原信息与异体检测规则的条件部分(即前部)相匹配。 若匹配找到了, 就得出此抗原为某种异体的结论, 若是有害异体, 就由毁灭器处理此抗原, 并将此抗原的特征信息加入到抗原数据库中, 这就是所谓的记忆功能, 若此抗原无害, 就由排泄系统处理此抗原。 若没有找到任何匹配, 就确认此抗原为新自体。 这个判断过程通过决策算法实现。
图 2 抗体的2层算法
Fig. 2 Bi-tier algorithm of antibody
下面举个实验示例, 计算机上VD目录为实验环境。 VD目录由2个子目录组成: CLASSES和EXECUTE, 这两个子目录下某些文件被爱虫病毒感染了。 例如, 这两个子目录均有17个文件, CLASSES子目录中有2个文件被爱虫病毒感染, 分别为server.class和FireFighter.bat; EXECUTE子目录中有1个文件被爱虫病毒感染, 此文件为rossum.ini。 本实验中用人工免疫系统的抗体识别这些已感染的病毒文件。
在启动免疫计算的检测和识别功能前, VD目录下文件的可视化表示如图3(a)所示。 免疫计算激活后, 抗体与这些病毒文件的特征信息相匹配, 从而识别出这些异体抗原, 并用不同的颜色标识这些文件, 如图3(b)所示。 这些病毒文件的特征信息主要有3点:
a. 含有“loveletter”字符串;
b. 调用了copy(?)函数, 来复制自身文件;
c. 使用了VBScript脚本语言。
图3(a)中, 黑色的球表示未检测的文件; 图3(b)中, 黑色的球表示正常的文件, 即未被病毒感染的文件, 也就是自体, 白色的球表示已被病毒感染的文件, 即为异体。 之所以采用分子球可视化表示免疫计算过程, 是因为这样能有助于理解自然免疫系统与人工免疫系统的相似之处。
从此实验示例可看出, 免疫计算可识别出自体和异体, 从而消除异体抗原, 例如杀毒。 事实上, 不仅仅是杀毒与计算机安全领域, 免疫计算的异体—自体识别能力还可用于移动机器人在位置环境中的故障诊断、 容错和自修复。 目前正进行的研究主要以故障的免疫检测为切入点。
图 3 免疫计算的异体—自体识别示例
Fig. 3 Examples of non-self/self recognition for immune computation
4 结 论
利用已提出并证明的3层并行计算模型及其负载平衡定理, 按照测不准、 负载极限思想, 构建了免疫计算的测不准有限计算模型, 用免疫算法随机搜索抗体, 实现抗体的异体识别和自适应的免疫计算。 此外, 优化免疫算法, 可增大负载极限, 提高免疫计算的负载平衡能力。 并行计算也是增大免疫计算的负载极限, 改善人工免疫系统的负载平衡的良好途径。
参考文献:
[1]CAI Zi-xing, GONG Tao. Multi-dimension education immune network[A]. Callaos N, Hernandez-Encinas L, Yetim F, et al. Proceedings of the 6th World Multi-Conference on Systemics, Cybernetics and Informatics[C]. Orlando: Int Inst Informatics & Systemics, 2002. 32-37.
[2]Bersini H, Varela F. Hints for adaptive problem solving gleaned from immune network[A]. Schwefel H P, Manner R. Parallel Problem Solving from Nature[C]. Berlin: Springer-Verlag, 1991. 343-354.
[3]Ishida Y. Fully distributed diagnosis by PDP learning algorithm: towards immune network PDP model[A]. Caudill M. Proceedings of International Joint Conference on Neural Networks[C]. Piscataway: IEEE, 1990. 777-782
[4]Dasgupta D, Forrest S. An anomaly detection algorithm inspired by the immune system[A]. Dasgupta D. Artificial Immune System and Their Applications[C]. Berlin: Springer-Verlag, 1998. 262-277.
[5]Cooke D E, Hunt J E. Recognizing promoter sequences using an artificial immune system[A]. Rawlings C, Clark D, Altman R, et al. Proceedings Intelligent Systems in Molecular Biology[C]. Menlo Park: AAAI Press, 1995. 89-97.
[6]de Castro L N, Timmis J. Artificial Immune Systems: A New Computational Intelligence Approach[M]. Heidelberg: Springer-Verlag, 2002.
[7]蔡自兴, 龚涛. 免疫算法研究的进展[J]. 控制与决策, 2004, 19(8): 841-846.
CAI Zi-xing, GONG Tao. Advance in research on immune algorithms[J]. Control and Decision, 2004, 19(8): 841-846.
[8]曹先彬, 刘克胜, 王煦法. 基于免疫进化规划的多层前馈网络设计[J]. 软件学报, 1999, 10(11): 1180-1184.
CAO Xian-bin, LIU Ke-sheng, WANG Xu-fa. Design multilayer feed-forward networks based on immune evolutionary programming[J]. Chinese Journal of Software, 1999, 10(11): 1180-1184.
[9]肖人彬, 王磊. 人工免疫系统: 原理、 模型、 分析及展望[J]. 计算机学报, 2002, 25(12): 1281-1293.
XIAO Ren-bin, WANG Lei. Artificial immune system: principle, models, analysis and perspectives[J]. Chinese J. Computers, 2002, 25(12): 1281-1293.
[10]JIAO Li-cheng, WANG Lei. Novel genetic algorithm based on immunity[J]. IEEE Transactions on Systems, Man, and Cybernetics Part A: Systems and Humans, 2000, 30(5): 552-561.
[11]梁意文, 潘海军, 康立山. 免疫识别器构造的多级演化[J]. 小型微型计算机系统, 2002, 23(4): 441-443.
LIANG Yi-wen, PAN Hai-jun, KANG Li-shan. Multilevel evolution of immune detector[J]. Mini-Micro System, 2002, 23(4): 441-443.
[12]DING Yong-sheng, REN Li-hong. Fuzzy self-tuning immune feedback controller for tissue hyperthermia[A]. IEEE International Conference on Fuzzy Systems[C]. Piscataway: IEEE, 2000. 534-538.
[13]葛红, 毛宗源. 免疫算法几个参数的研究[J]. 华南理工大学学报(自然科学版), 2002, 30(12): 15-18.
GE Hong, MAO Zong-yuan. Research on parameters of immune algorithm[J]. Journal of South China University of Technology (Natural Science Edition), 2002, 30(12): 15-18.
[14]de Castro L N, Timmis J. Artificial immune systems as a novel soft computing paradigm[J]. Soft Computing, 2003, 7(8): 526-544.
[15]de Castro L N, Von Zuben F J. Automatic determination of radial basis function: an immunity-based approach[J]. International Journal of Neural Systems, 2002, 11(6): 523-535.
[16]Dasgupta D, Gonzalez F. An immunity-based technique to characterize intrusions in computer networks[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(3): 281-291.
[17]Gonzalez F, Dasgupta D, Nino L F. A randomized real-valued negative selection algorithm[A]. Timmis J, Bentley P, Hart E. Proceedings of the 2nd International Conference on Artificial Immune System[C]. Berlin: Springer-Verlag, 2003. 261-272.
[18]Chao D L, Forrest S. Information immune systems[A]. Timmis J, Bentley P. International Conference on Artificial Immune Systems[C]. Canterbury: University of Kent at Canterbury Printing Unit, 2002. 132-140.
[19]Smith D J. Applications of bioinformatics and computational biology to influenza surveillance and vaccine strain selection[J]. Vaccine, 2003, (21): 1758-1761.
[20]Hofmeyr S A, Forrest S. Architecture for an artificial immune system[J]. Evolutionary Computation, 2000, 7(1): 45-68.
[21]GONG Tao, CAI Zi-xing. Parallel evolutionary computing & 3-tier load balance of remote mining robot[J]. Transactions of Nonferrous Metals Society of China. 2003, 13(4): 948-952.
[22]GONG Tao, CAI Jing-feng, CAI Zi-xing. A coding & control mechanism of natural computation[A]. Yen G G, LIU De-rong. Proceedings of the 2003 IEEE International Symposium on Intelligent Control[C]. Piscataway: IEEE, 2003. 727-732.
[23]GONG Tao, CAI Zi-xing. Mobile immune-robot model[A]. Proceedings of IEEE International Conference on Robotics, Intelligent Systems and Signal Processing[C]. Piscataway: IEEE, 2003. 1091-1096.
[24]龚涛, 蔡自兴. 教育艾真体的免疫机制及其应用[J]. 计算机工程与应用, 2003, 39(24): 77-79.
GONG Tao, CAI Zi-xing. Immune mechanism of education Agent: principles and applications[J]. Computer Engineering and Application, 2003, 39(24): 77-79.
收稿日期:2005-01-28
基金项目:国家自然科学基金资助项目(60404021,60234030)
作者简介:龚 涛 (1978-), 男, 湖南常德人, 博士研究生, 从事免疫计算、 移动机器人故障诊断等研究
论文联系人: 龚 涛, 男, 博士研究生; 电话: 0731-8830583(O); E-mail: taogong@sigmaxi.org
