国家自然科学基金面上青年基金项目进展报告

国家自然科学基金面上青年基金项目进展报告“免疫计算的测不准有限计算模型与鲁棒性分析”项目的主要任务1.免疫计算的分层计算与负载平衡基于正常模型，人工免疫系统的3层是指固有免疫计算层、适应性免疫计算层和并行免疫计算层。对一种基于文件的人工免疫系统建立正常模型，用其正常组件文件的时空属性唯一确定该人工免疫系统的正常状态。正常模型为人工免疫系统的可信建模奠定基础，可提高人工免疫系统的性能。人工免疫系统的正常模型图1基于文件人工免疫系统的正常模型文件的空间属性是其绝对路径名，文件的时间属性是其最后修改时间。人工免疫系统的3层结构(图2)在图2中，第1层是固有免疫计算层，用来检测所有的自体和异体，并识别所有已知的异体；第2层是适应性免疫计算层，用BP网络、RBF网络等神经网络对未知的异体进行识别、学习和记忆，然后消除所有被人工免疫系统看作威胁的异体；第3层是并行免疫计算层，这一层为人工免疫系统提供了改善效率的辅助工具，是受自然免疫系统中用作生物基础组织的并行免疫细胞和分子启发而来的。自体数据库设计为正常模型的数据集，该自体数据库用来在人工免疫系统中100%检测自体和异体。所有已知异体的特征存储在异体数据库中，该异体数据库用来识别所有已知的异体和大多数未知的异体。对于未知的异体，用神经网络学习它们。与该未知异体最相似的已知异体将用作学习的样本，以选择该未知异体的最佳类似物。人工免疫系统中所有受损的文件在被识别为异体并要被删除时，将记录在临时数据库中。通过该临时数据库和所述自体数据库，受损的人工免疫系统能最大可能地自动被修复。并行免疫计算层的节点是计算机主机，其中表示节点的总数，并行节点为人工免疫系统提供了高性能的计算基础组织。有关人工免疫系统正常模型的定理定理1文件的时空属性二元组唯一确定了该文件的状态。定理2人工免疫系统中所有文件都处于正常状态时，其各个文件的时空属性二元组唯一确定了该系统的正常状态。定理3基于人工免疫系统的正常模型，对其自体的检测率从理论上可以达到100%，对其异体的检测率从理论上也可以达到100%。定理4基于人工免疫系统的正常模型和神经网络，同等误差条件下对异体的识别率将比不采用正常模型更高。人工免疫系统的并行免疫计算层为固有免疫计算层和适应性免疫计算层提供高性能的计算基础组织，解决有限计算和负载平衡的问题。一台主机的计算能力和资源总是有限的，高负荷的计算是不可靠的、易摧毁的并且高风险的。当移动机器人等系统的免疫信息处理量超过单个处理器的负载能力时，便调用并行免疫计算层，并行免疫计算层还能用来实现数据的多备份和系统恢复。对于移动机器人等系统的每个功能模块，其相应的免疫子系统监视和保护这个模块，来维护每个功能模块的局部免疫和移动机器人的整体免疫。免疫计算模块建立在移动机器人等系统的功能模块上，成为一系列相对独立的免疫计算体。移动机器人的并行免疫计算(图3)并行免疫计算的复杂度定理定理5假设并行计算机有d个主机节点，且每个节点有2个处理器，那么，并行计算机解决导航问题的时间复杂度与单机解决此问题的时间复杂度之间的关系如下：。定理6假设并行计算机有d个主机节点，且每个节点有2个处理器，那么，并行计算机解决抗病毒问题的时间复杂度与单机解决此问题的时间复杂度之间的关系如下：。定理7假设移动机器人的软件系统由n个文件和m个文件夹组成，异体数据库nonselfdb中共有K个已知异体，发生故障的机器人软件系统中有k1个异体文件，其中k3个异体文件是该系统中正常文件的异常状态。假设并行计算机有d个主机节点，且每个节点有2个处理器，那么，并行计算机解决抗病毒问题的时间复杂度与单机解决此问题的时间复杂度之间的关系如下：。2.免疫计算的算法设计基于正常模型和3层免疫计算模型，人工免疫系统的算法设计包括人工免疫系统的正常模型构建算法设计、基于正常模型的自体/异体检测算法设计、基于异体数据库的异体识别算法设计、基于BP神经网络的未知异体识别算法设计、基于临时数据库的异体消除算法设计、基于正常模型的系统恢复算法设计和基于Java多线程技术的并行免疫计算算法设计。2.1人工免疫系统的正常模型构建算法•第1步对系统进行备份，提供该备份系统的根目录路径；•第2步读取系统的根目录，从其根目录中查找文件；•第3步如果当前目录中至少存在一个未读取的文件或子文件夹，那么依次读取当前选定文件或子文件夹的绝对路径名和最后修改时间，否则进入第9步；•第4步建立到自体数据库的JDBC连接，对自体数据库进行初始化；•第5步将该文件或子文件夹的绝对路径名和最后修改时间添加到该自体数据库中；•第6步关闭自体数据库的当前数据库连接；•第7步如果刚处理的是子文件夹，那么递归构建该文件夹所对应子系统的正常模型；•第8步重复第3步；•第9步如果已处理的文件有个，且已处理的文件夹有个，就结束算法。图4用自体数据库selfdb存储的正常模型数据2.2基于正常模型的自体/异体检测算法•第1步读取系统的根目录，从其根目录中查找文件；•第2步如果在当前目录中至少存在一个未读取的文件或文件夹，那么依次读取当前选定文件或文件夹的绝对路径名和最后修改时间，否则进入第9步；•第3步建立到自体数据库的JDBC连接；•第4步用该文件或文件夹的绝对路径名和最后修改时间查询自体数据库；•第5步如果存在相匹配的记录，那么该文件或文件夹标识为自体，否则标识为异体，并把其中的异体文件交由异体识别算法进行识别；•第6步关闭自体数据库的当前数据库连接；•第7步如果刚检测的是子文件夹，那么递归检测该文件夹所对应子系统中的各个文件；•第8步重复第2步；•第9步如果已处理的文件有个，且已处理的文件夹有个，就结束算法。图5正常网页系统的自体检测2.3基于异体数据库的异体识别算法•第1步依次选定被检测的异体文件，读取其文件扩展名；•第2步建立到异体数据库的JDBC连接；•第3步用该文件的扩展名查询异体数据库；•第4步如果在异体数据库中不存在与该异体文件的扩展名相匹配的记录，那么该异体文件是未知的异体，需要用未知异体识别算法对它识别，否则从异体数据库中读取与之匹配的记录，包括特征串、文件复制行为、对注册表的行为和对邮件的调用等字段数据；•第5步关闭异体数据库的当前数据库连接；•第6步读取该文件的数据，寻找与异体数据库中记录相匹配的特征串、文件复制行为、对注册表的行为和对邮件的调用等信息，如果找到一致的特征匹配，那么该异体文件被识别为已知异体，在异体数据库中已有其记录，否则需要用未知异体识别算法对它识别；•第7步关闭文件读取器，结束算法。图6已知异体识别算法的测试结果2.4基于BP神经网络的未知异体识别算法•第1步，依次选定已知异体识别算法所不能识别的未知异体文件，读取其第个特征；•第2步建立到异体数据库的JDBC连接；•第3步查询异体数据库中所有已知异体的第个特征，计算查到的特征与未知异体的特征之间的相似度，选择其中最大的相似度及其对应的特征编码；•第4步根据最大相似度及其对应的特征编码，计算未知异体的第个特征所对应的不确定编码；•第5步关闭异体数据库的当前数据库连接，结束算法。图7BP神经网络的训练结果图8BP神经网络对未知异体的识别结果2.5基于临时数据库的异体消除算法•第1步如果存在未消除的异体文件，就依次读取选定异体文件或文件夹的绝对路径名，否则进入第8步；•第2步如果该异体是文件，就建立到自体数据库的JDBC连接，否则进入第7步；•第3步用该异体文件的绝对路径名查询该自体数据库；•第4步如果找到与之匹配的记录，就推断该异体文件是原来的正常文件受异体感染而产生的，然后根据其绝对路径名、系统的根目录路径和其备份系统的根目录路径生成该异体文件的备份文件路径，并将该异体文件的绝对路径名和备份文件路径存入临时数据库usefulfile中；•第5步如果该异体文件处于打开状态，就关闭该异体文件，然后删除该异体文件；•第6步关闭自体数据库的当前数据库连接；•第7步如果该异体是子文件夹，并且该子文件夹非空，那么递归消除该文件夹中的异体文件；否则删除该异体文件夹；•第8步重复第1步；•第9步如果已处理的异体有个，并且临时数据库usefulfile中有个记录，就结束算法。图9异体消除算法的测试结果图10在临时数据库中添加了受异体感染的正常文件信息2.6基于正常模型的系统恢复算法•第1步建立到自体数据库的JDBC连接，并查询该自体数据库；•第2步如果在自体数据库中存在未读取的记录，依次读取当前选定记录的空间属性，否则进入第5步；•第3步如果该空间属性所对应的文件不存在，就计算该文件的备份文件路径，并用其备份文件恢复；•第4步重复第2步；•第5步关闭到自体数据库的JDBC连接，并建立到临时数据库的JDBC连接；•第6步如果在临时数据库中存在记录，依次读取当前选定的记录，否则进入第9步；•第7步根据该记录的绝对路径名和备份文件路径，将相应的备份文件拷贝到该绝对路径名所指定的位置；•第8步重复第6步；•第9步关闭临时数据库的当前数据库连接，结束算法。图11系统恢复算法的测试结果3.免疫计算的测不准特征在自然免疫系统中，抗体、免疫细胞和抗原都是纳米量度的微观世界事物，现有的生物医学设备无法准确测量抗体识别未知异体的位置和时间，这和量子物理的卢森堡测不准原理类似，表现为微观世界的测不准特征。这种生物医学领域的测不准特征也影响到了人工免疫系统领域，因为人工免疫系统是根据生物医学的免疫学说灵感启发而设计的。在基于正常模型的人工免疫系统中，对未知异体的特征识别不可能是完全准确的，测量误差和未知异体的复杂性是直接原因。因此，对未知异体的识别属于非精确推理，这里采用相似度推理，寻找和未知异体最相似的已知异体。这种推理建立在概率和可信度的基础上。所述未知异体的特征提取是和对已知异体的识别同步进行的，在读取并通过异体数据库匹配待识别异体的特征时，计算该异体的特征信息与异体数据库中最相似的已知异体特征之间的相似度。该相似度是一种概率值，用来表示对待识别异体计算特征值的可信度。例如，蠕虫病毒特征字符串的相似度是指在异体数据库中和该特征串最相似的特征串与该特征串匹配的长度，除以最相似特征串的长度的比率，待识别蠕虫病毒的特征字符串为“happybirthday”，在异体数据库中和该特征串最相似的是已知蠕虫病毒“欢乐时光”病毒的特征串“happytime”，这两个特征串匹配的长度为6，欢乐时光”病毒的特征串长度为10，这样其相似度为。因此，相似度必定为大于或等于0、小于或等于1的小数，是一种概率，表示未知异体特征提取的不确定性。未知异体的特征编码就是由在异体数据库中与之最相似的特征所对应的编码值和这两个特征之间的相似度决定的。4.分布式人工免疫系统的鲁棒性分析自然免疫系统是天然的并行、分布式生物信息处理系统，人工免疫系统也具有分布式信息处理的特征。因此，根据已提出的多真体鲁棒性归约模型，可以用分布式系统的鲁棒性分析方法分析人工免疫系统的鲁棒性。问题归约法是一种把问题由繁化简、由多元转化为一元的有效分析方法，用问题归约法分析人工免疫系统的鲁棒性，就能建立人工免疫系统的鲁棒性归约模型，并分析实际人工免疫系统的鲁棒相关性。4.1人工免疫系统的分布式结构人工免疫系统主要包括几个相对独立的计算模块：正常模型生成模块、自体/异体检测模块、已知异体识别模块、未知异体学习模块、异体消除模块和系统修复模块。在理想情况下各个计算模块完全独立，该人工免疫系统是一种对等型的分布式系统。图12人工免疫系统的分布式结构4.2人工免疫系统的鲁棒性归约定理4.3实际人工免疫系统的鲁棒相关性图13人工免疫系统的鲁棒相关性模型预期研究成果与现有研究成果的比较预期研究成果•拟提交《免疫计算的测不准有限计算模型与鲁棒性分析》总结报告1份•在国内外重要会议和重要学术刊物上发表论文9篇，其中国际4篇•编写专著1本，申请专利1项•培养博士研究生1名，硕士研究生1名。现有研究成果•已提交进展报告1份，总结技术报告5份•在国内外重要会议和重要学术刊物上已发表论文13篇，其中国际5篇•正在编写专著1本以上，申