第３５卷第８期 文章编号：１００６—９３４８（２０１８）０８—０３２７—０４ 计算机仿真 ２０１８年８月 复杂软件程序运行异常源点准确定位仿真分析 郝世选 （河南大学濮阳工学院，河南濮阳４５７０００） 摘要：当复杂软件各个程序同时运行时，对应的程序节点间存在较强的差异性，当前异常定位方法进行异常源点定位过程 中，没有考虑到节点间的强差异性，导致异常源点定全率和定准率较低。针对上述问题，提出基于多域划分的复杂软件程序 运行异常源点准确定位方法。根据软件程序节点不同异常类型的发生几率，采用Ｋ—ｉＴｌｅａｎ８算法将软件程序域分割为多个 子域，使发生近似异常的节点聚集在相同的子域内。提取子域内异常节点特征，通过粒子多次迭代搜索异常源点特征最优 解，获得的即是异常源点定位结果。实验结果表明，所提方法Ｃｕｓｔｏｍ定位效果有４８％的提升，Ｅｌｅｖａｔｏｒ定位效果有２２％的 提升，Ｓｇｒｅｐ定位效果有３９％的提升，极大地提高了定位精度。 关键词：复杂软件程序；异常源点；源点定位；多域划分 中图分类号：ＴＰ３１１．５ 文献标识码：Ｂ Ａｃｃｕｒａｔｅ Ｐｏｓｉｔｉｏｎｉｎｇ ａｎｄ Ａｎａｌｙｓｉｓ ｏｆ Ａｂｎｏｒｍａｌ Ｓｏｕｒｃｅ Ｐｏｉｎｔｓ ｏｆ Ｃｏｍｐｌｅｘ Ｓｏｆｔｗａｒｅ Ｐｒｏｇｒａｍｓ ＨＡ０ Ｓｈｉ—ｘｕａｎ （Ｐｕｙａｎｇ Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ，Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ，Ｐｕｙａｎｇ Ｈｅｎａｎ ４５７０００，Ｃｈｉｎａ） ＡＢＳＴＲＡＣＴ：Ａｎ ａｃｃｕｒａｔｅ ｍｅｔｈｏｄ ｆｏｒ ｌｏｃａｔｉｎｇ ａｂｎｏｒｍａｌ ｓｏｕｒｃｅ ｐｏｉｎｔｓ ｉｎ ｃｏｍｐｌｅｘ ｓｏｆｔｗａｒｅ ｐｒｏｇｒａｍ ｂａｓｅｄ ｏｎ ｍｕｌｔｉ— ｄｏｍａｉｎ ｐａｒｔｉｔｉｏｎ ｗａｓ ｐｒｏｐｏｓｅｄ．Ａｃｃｏｒｄｉｎｇ ｔｏ ｔｈｅ ｐｒｏｂａｂｉｌｉｔｙ ｏｆ ｏｃｃｕｒｒｅｎｃｅ ｏｆ ｄｉｆｅｒｅｎｔ ａｂｎｏｒｍａｌ ｔｙｐｅｓ ｉｎ ｓｏｆｔｗａｒｅ ｐｒｏ— ｇｒａｍ ｎｏｄｅｓ，ｔｈｅ Ｋ—ｍｅａｎｓ ａｌｇｏｒｉｔｈｍ ｗａｓ ｕｓｅｄ ｔｏ ｄｉｖｉｄｅ ｔｈｅ ｓｏｆｔｗａｒｅ ｐｒｏｇｒａｍ ｄｏｍａｉｎ ｉｎｔｏ ｍａｎｙ ｓｕｂ—ｄｏｍａｉｎｓ，ＳＯ ｔｈａｔ ｔｈｅ ｎｏｄｅｓ ｗｉｔｈ ａｐｐｒｏｘｉｍａｔｅ ａｎｏｍａｌｙ ｗｅｒｅ ｃｌｕｓｔｅｒｅｄ ｉｎ ｔｈｅ ｓａｍｅ ｓｕｂ—ｄｏｍａｉｎ．Ｔｈｅｎ，ｔｈｅ ｃｈａｒａｃｔｅｒｉｓｔｉｃ ｏｆ ａｂｎｏｒ— ｍａｌ ｎｏｄｅ ｉｎ ｓｕｂ—ｄｏｍａｉｎ ｗａｓ ｅｘｔｒａｃｔｅｄ．Ｆｉｎａｌｌｙ，ｔｈｅ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｆｏｒ ａｂｎｏｒｍａｌ ｓｏｕｒｃｅ ｐｏｉｎｔ ｆｅａｔｕｒｅｓ ｗａｓ ｉｔｅｒａ— ｔｉｖｅｌｙ ｓｅａｒｃｈｅｄ．Ｔｈｕｓ，ｔｈｅ ｐｏｓｉｔｉｏｎｉｎｇ ｒｅｓｕｌｔ ｏｆ ａｂｎｏｒｍａｌ ｓｏｕｒｃｅ ｐｏｉｎｔ ｉｓ ｏｂｔａｉｎｅｄ．Ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ Ｃｕｓｔｏｍ ｐｏｓｉｔｉｏｎｉｎｇ ｅｆｆｅｃｔ ｏｆ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｈａｓ ｂｅｅｎ ｉｎｃｒｅａｓｅｄ ｂｙ ４８％，Ｅｌｅｖａｔｏｒ ｐｏｓｉｔｉｏｎｉｎｇ ｅｆｆｅｃｔ ｈａｓ ｂｅｅｎ ｉｎ— ｃｒｅａｓｅｄ ｂｙ ２２％，ａｎｄ Ｓｇｒｅｐ ｐｏｓｉｔｉｏｎｉｎｇ ｅｆｆｅｃｔ ｈａｓ ｂｅｅｎ ｉｎｃｒｅａｓｅｄ ｂｙ ３９％．Ｔｈｕｓ，ｔｈｅ ｐｏｓｉｔｉｏｎｉｎｇ ａｃｃｕｒａｃｙ ｉｓ ｇｒｅａｔｌｙ ｉｍｐｒｏｖｅｄ． ＫＥＹＷＯＲＤＳ：Ｃｏｍｐｌｅｘ ｓｏｆｔｗａｇｅ ｐｒｏｇｒａｍ；Ａｂｎｏｒｍａｌ ｓｏｕｒｃｅ ｐｏｉｎｔ；Ｓｏｕｒｃｅ ｐｏｉｎｔ ｌｏｃａｔｉｏｎ；Ｍｕｌｔｉ—ｄｏｍａｉｎ ｐａｒｔｉｔｉｏｎ 的程序节点同时工作，编码规则的不同致使程序节点之间存 １ 引言 互联网时代的到来，计算机和电子通信技术的快速发 展，软件规模越来越大，逻辑结构和系统形态越来越复杂，对 软件程序运行可靠性的要求也越来越高 Ｊ。影响软件系统 可靠性的主要原因是软件程序运行中潜在的错误，频繁的程 序代码变更将会产生非预期的执行逻辑，影响软件系统功能 的正常发挥 ｊ。在复杂软件程序运行过程中，不同编码规则 在较强的差异性 Ｊ，现行软件异常定位方法，多数以相同规 则编码下的程序代码统一特征对比为基础，定位效果不好且 难度大。若软件程序中存在多个异常程序节点，则需要重复 这样的多次特征对比过程，大大降低了软件系统服务效 率 。如何识别复杂软件中，那些测试用例执行异常是由同 一错误导致的，是软件异常定位中的一个难题 Ｊ。 针对软件程序运行异常定位问题，曹鹤玲等人 提出一 种基于动态聚类分析的异常定位方法。合并异常程序与正 基金项目：２０１６年度河南省高等学校青年骨干教师培养计划 （２０１６ＧＧＪＳ一２７１） 常程序的运行轨迹，根据怀疑度排序结果选择高可疑节点， 将其作为软件程序运行轨迹的特征向量；根据该向量对异常 程序运行轨迹分类；将异常程序运行轨迹集合与成功程序运 ．．．——收稿日期：２０１８—０２—２８ ３２７．．．—— 行轨迹合并，以合并后生成的怀疑度序列定位软件运行过程 其中，ｄ（ 表示全部异常点，可以描述的征兆集合，Ｓ 表示 可观测的征兆集合，ｄ（ 表示异常点，的覆盖区间。根据参 数覆盖区间ｃ（ 的设定可将程序运行异常点筛选问题转换 中的异常源点。该方法存在以下２点问题：①每次分析合并 后，需要将异常测试用例和正常测试用例的运行轨迹信息合 并，重新计算怀疑度，计算量较大。②在复杂软件中，各个程 序同时运行，对应的程序节点之间存在较强的差异性，该方 法在迭代过程中若将某个程序运行轨迹特征向量划分至某 个集合中，则该特征向量在后续划分过程中永远属于该集 为信号处理问题，采用压缩感知方法 去除冗余异常点，即 （日ｓ）＝（Ｉ １一１日 ５）／｛Ｆ。１ Ｒ（ ）＝ｌ ｌ／ｆ／４，ｌ＝１一Ｉ Ｉ／ｌ ｆ 其中， （Ｈｓ）和Ｒ（／１，）分别表示筛选后的异常点集合 （４） （５） 的 合，分类准则没有考虑到集合内部节点之间的差异性，导致 异常源点很难定位，大大降低了异常源点的定全率和定 准率。 真实覆盖率和冗余度， 表示由真实异常点构成的集合。 软件程序运行过程中，可能存在多个异常点同时具有最 大覆盖区间的情况，采用覆盖区间作判别参数进行异常源点 定位的可能会产生误判，针对此问题，引入新的参数异常点厂 基于多域划分的异常定位方法可以克服传统基于动态 聚类分析的异常定位方法的缺点，在异常源点定位时：①将 软件程序应用域划分为多个异常发生关联性较高的子域，将 程序异常的发生定位在较小的子域内，缩短程序运行异常源 点的定位范围，降低了计算量。②在子区域内定位时，考虑 到子域内异常节点之间的差异性，根据差异化特征构造粒子 群，通过粒子多次迭代搜索异常源点特征最优解，解决了采 用传统异常定位方法难以实现精准定位难题，提高了异常源 点定全率和定准率。 ２软件程序运行异常源点定位原理 根据概率加权二分图可组建软件程序运行异常行为传 播模型，通过传播模型找出征兆相应的最大可能异常集合， 引人参数异常点覆盖范围将最大可能异常集合转换为信号， 采用压缩感知方法消除信号冗余信息，设定参数异常信息熵 差辨别出异常源点，完成定位，具体过程如下所述： 假设，Ｇ 表示软件程序运行异常节点关系图， 表示程 序运行异常节点，Ⅳ表示异常节点的数量，确定程序运行源 点必然是Ｇ 中Ⅳ个节点中的一个，Ｐ（Ｇ ｌ ）表示Ｇ 中 为异常源点的概率，基于异常传播的随机性和性，根据 概率加权二分图 可组建软件程序运行异常行为传播模型 Ⅳ Ｐ（Ｇ Ｉ ）＝∑Ｐ（Ｃｋ一－（ ） ） （１） 其中，Ｃ （０）表示标记的第 一１个已感染的节点， 表示 下一阶段被感染异常的节点。 依据异常行为传播模型可以快速准确地找出与征兆集 合中征兆关联的全部可能异常，获得最大可能异常行为集 合。设定参数冗余度Ｒ表征冗余异常数量在最大异常行为 集合中所占的比例，即 １Ｆ １ （ ）＝Ｐ（Ｇ ｌ ）（ 一 ） （２） 其中， 表示月 中冗余异常点构成的集合，Ｆ。表示软件中 真实异常点集合。 为了降低冗余度，必须筛选出关于式（２）中的最大可能 异常点集合 中的冗余故障，设定参数覆盖区间Ｃ（ｆ），Ｃ （ 反映了异常点发生的可能性，即 ｃ（ ＝Ｒ（ ）Ｊ ｄ（／）ｎ Ｓ Ｊ （３） ．．．——３２８．．．—— 的信息熵作为判别参数△ｌ厂Ｉ进行异常点定位 口·（／）＝一∑△Ｊｆｌｌｏｇｐ（ｆｆ ｓ ） （６） （／）ｎ ０ 其中，．ｓ（／）表示异常点，相应的征兆集合，Ｓ 表示软件程序 运行过程中能够显示出的征兆集合，Ｐ（ｆ｛ｓ ）表示征兆集合 对异常点厂提供的信息熵。 软件运行异常 ６ｄｆ的信息熵差ＡＨ（ｆ）：Ｈ。（ 一／１２（＿厂） 越小，说明异常点实际引发的征兆与实际情况较为接近，可 视为异常点．厂为异常源点的几率较大，对其定位。 ３ 复杂软件程序运行异常源点准确定位方法 ３．１基于多域划分的软件程序 根据软件程序节点不同异常类型的发生几率，采用Ｋ— ｍｅａｎｓ算法将软件程序应用域划分为多个子域，使发生近似 异常的节点聚集在相同的子域内，其主要目的在于缩小软件 程序运行异常源点定位的范围。对于各个软件程序节点ｉ， 建立一个异常行为类型的发生几率向量 Ｐ ＝（Ｐ …，Ｐ ） （７） 其中，Ｐ 表示节点ｉ发生异常研的几率。各个应用程序节点 对应一个异常行为发生几率向量，此向量刻画了不同节点容 易诱发的异常行为类型，且满足 ＝Ｆ ∑Ｐ ＝１ （８） 在获知程序异常行为类型后划分应用域，将软件运行网络与 应用空间作为一个整体考虑，Ｐ 、Ｐｊ分别表示节点ｉ√的异常 几率向量，采用余弦近似度准则计算程序应用域内节点ｉ与 之间的关联性，计算式如下 ｓ（ （９） 利用误差平方和准则 作为程序应用域内异常节点的聚类 准则函数，即 Ｅ＝∑∑ｌｉｐ 一７ ｌＩ （１０） 式中，Ｄ 表示子域Ｋ内的异常节点集合，表示应用域的可被 划分的数量， 表示子区域Ｋ的中心，并假设子域，ｃ中节点 数量为Ｚ ，“ 表示其中一个程序节点。 直至应用域内异常节点聚类中心不发生改变为止，即完 成对程序应用域的划分，其主要目的在于缩小软件程序运行 异常点定位的范围，降低计算量，为进一步进行异常源点定 位划分合适的定位范围。 ３．２子区域内异常源点定位 Ｙ：Ｙ…一 ｒ （ｂ）× （１５） 其中，Ｙ…、Ｙｍｉ．表示最大权重系数及最小权重系数。通过计 算粒子的关联适应度函数的取值区间ｈ（ｂ），选择区间内的 最小值，以获取软件程序运行异常源点定位的最优解。 综合上述方法，可以避免传统的异常源点定位的局限 性，通过粒子多次迭代搜索异常源点特征最优解，解决了采 将软件程序节点进行多区域划分后，提取子域内异常节 点特征，并计算其权重，并对特征提取误差进行补偿实现差 异化异常节点特征提取。根据差异化特征构造粒子群，通过 用传统异常定位方法难以实现精准定位难题，实现异常源点 的准确定位。 粒子多次迭代搜索异常源点特征最优解，获得的即是异常源 点定位结果，具体过程如下所述： 在３．１节应用程序子区域划分的基础上继续根据具体 的节点异常行为提取异常点特征，假设ｏ＝（ｎ 一，％） 表 征某一异常点特征分量，；：Ｇ［ｚ］表示某个分量方向上的平 均值，为了明确地观测软件程序运行子域内不同节点之间存 在的特征差异，利用下式表示应用程序运行子域内节点特征 对比结果 ６： …） 其中， 表示特征描述项， ， ；， ，Ｕ表示特征维度，“表 示特征属性向量，ｑ表示节点特征对比差异系数， 表示程 序运行域。设定五表示子域内节点的权值系数，利用下式求 取各个子域内节点权值系数 Ｍ ａ＝［∑ｂ＋∑ ］．ｙ （ｐ） （１２） 其中，ｅ 、 表示特征分量上的平均值。根据上式给出的节点 权值系数，ｒ表示节点的失效信息，ｕ 表示残差分量，利用式 （１４）便可提取出特征残差参数 ｙ （Ｐ）：Ｇ［（。一五） ］ （１３） 其中，（ｎ—ａ）表示特征差值，Ｇ表示残差项数，令特征分量上 的平均值满足ｅ ＝Ｈ［ｂ ］／ｒ· （Ｐ）是使得异常节点特征提 取误差为最小，Ｈ［ｂ ］表示阈值。 复杂软件运行过程中所有异常节点定位均具有不确定 性，根据对式（１４）调整后提取的节点动态特征，结合粒子群 优化算法 可以设定作用在异常节点上的粒子权重系数 ， ｅ 和ｅ：分别表示节点间的信息交互参数，ｔ 和ｔ：分别表示 异常节点间关联系数，通过迭代算法 ｕ＿对粒子当前搜索速 度和空间位置进行实时更新 ｒ ｍ（ ＋１）＝ ｘ ｍ（ ）＋ｅ１ｔ。（Ｒ ｍ（ ）一Ｚ ｍ（ ））＋ ｛ ｅ２ｔ （Ｒ （ ）一ｚ （ ）） Ｚ （ ＋１）＝Ｚ （ ）＋Ｚ。 （ ＋１） （１４） 其中， （”）和Ｚ （ ）分别表示粒子 初始搜索速度和空 间位置参数，Ｚ （ ）表示第 ＋１次迭代下的粒子空间位置。 假设， 表示软件程序异常节点定位迭代次数， 表示粒 子当前搜索迭代次数，利用下式计算种群内部粒子的权重 系数 ４实验结果与分析 为了验证本文提出的基于多域划分的复杂软件程序运 行异常源点准确定位方法的综合有效性，实验配置为Ｗｉｎ— ｄｏｗｓ系统，ＣＰＵ为２．６ＧＨｚ，内存为４ＧＢ，利用Ｓｉｅｍｅｎｓ Ｓｕｉｔｅ 作为软件程序运行异常源点定位方法评价数据集。选取３ 个软件程序在Ｍａｔｌａｂ中进行实验。 设定Ｏ表示失效的软件程序输入异常源点，Ｄ和Ｄ 分 别表示Ｓｉｅｍｅｎｓ Ｓｕｉｔｅ数据集中的两个子集，给出两个指标： 定准率Ｐ和定全率ｒｅ来评价基于多域划分的异常定位方法 和基于动态聚类分析的异常定位方法，应用于复杂软件程序 运行异常源点的定位效果。 ＪＰ（。）＝ ｃ（。）／ｕ （。 （１Ｉ ｌ６）ｏ Ｊ Ｌｒ（ｏ）＝Ｕ。（ｏ）／ （ｏ） 其中，Ｐ（Ｏ）表示异常源点。的定准率，ｒ（Ｏ）表示异常源点Ｏ 对应的定全率， （ｏ）表示异常源点的失效类型， （Ｏ）表示 异常源点检出的次数。选取３个软件程序（Ｃｕｓｔｏｍ、Ｅｌｅｖａｔｏｒ、 Ｓｇｒｅｐ），这３个软件包含命令行、网络通信多线程等目前常见 的软件运行故障特征。 表１给出了基于多域划分的异常源点定位方法和基于 动态聚类分析的异常定位方法中，３个软件程序异常源点的 定准率实验结果。其中，Ｌ表示不同软件程序。Ｕ和ｂ分别表 示基于多域划分的定位方法和基于动态聚类分析的定位 方法。 表１不同方法异常源点定准率评价结果 分别表１可知，采用基于多域划分的定位方法在３个软 件程序上均有较好的定位表现。在Ｃｕｓｔｏｍ、Ｅｌｅｖａｔｏｒ、Ｓｇｒｅｐ软 件程序上异常源点定准率分别为９８．９６５％、９７．９８５％、 ９８．６５７％，远高于基于动态聚类分析的定位方法获得的定位 结果，可以看出基于多域划分的定位方法在异常源点定准率 上具有明显优势。 为了定量分析基于多域划分的定位方法在实现复杂软 ．．．——３２９．．．—— 件程序运行异常源点定位中的性能，采用基于多域划分的定 位方法和基于动态聚类分析的异常定位方法，以定全率（％） 为测试指标，获得对比结果如图１所示。从图１中可以看 表２采用不同方法时异常源点平均定位误差 出，采用基于多域划分的定位方法进行复杂软件运行异常源 点定位的定全率高于基于动态聚类分析的定位方法。主要 原因在于基于动态聚类分析的定位方法没有考虑到节点之 间的差异性，导致异常源点很难定位，大大降低了异常源点 的定全率，而基于多域划分的复杂软件程序运行异常源点准 确定位方法，考虑到节点问的差异性，根据软件运行程序子 域内异常节点差异化特征构造粒子群，通过粒子多次迭代搜 ５结论 提出一种基于多域划分的复杂软件运行异常源点准确 定位方法。通过提取应用程序子域内的节点特征，实现异常 索异常源点特征最优解，使得最终的定全率较高。 ９９ ９７ ９５ ９３ ９１ ８９ ８７ ８５ 图１不同方法定全率评价结果 设定异常源点定位误差ｅｒｒ和平均定位误差ＡｖｅｒＥｒｒ ｅｒ ＝￣／（ 。一 ：） ＋（Ｙ 一 ） （１７） １ ｈ ＡｖｅｒＥｒｒ＝亡∑ｅ￡ ｌ ｒｒ （１８） 其中，（ ，Ｙ ）表示第 个软件程序运行测试点的实际位置， （ ：， ）表示第Ｌ个测试点的估计位置，ｈ表示测试点的总 数量。 表２为采用不同方法时软件程序运行异常源点平均定 位误差对比，定位误差值为常数，单位用Ｃ表示。表２中，Ｇ、 Ｊ分别表示基于多域划分的定位方法、基于动态聚类分析的 定位方法。基于多域划分的定位方法，Ｃｕｓｔｏｍ软件异常源点 定位效果有４８％的提升，Ｅｌｅｖａｔｏｒ软件异常源点定位效果有 ２２％的提升，Ｓｇｒｅｐ软件异常源点定位效果有３９％的提升，实 验结果表明，基于多域划分的定位方法定位精度更高。 －－－——３３０·－－—— 节点特征提取。依据特征提取结果构建初始粒子群，搜索最 优解，得到即是应用程序中异常源点的定位结果。实验结果 表明，所提方法Ｃｕｓｔｏｍ定位效果有４８％的提升，Ｅｌｅｖａｔｏｒ定 位效果有２２％的提升，Ｓｇｒｅｐ定位效果有３９％的提升，极大 地提高了定位精度。 参考文献： ［１］ 王琦，孙文辉．基于程序变异分析的软件错误定位［Ｊ］．计算 机工程，２０１７，４３（１２）：５５—５９． ［２］ 苏小红，等．一种基于加权软件行为图挖掘的软件错误定位方 法［Ｊ］．计算机学报，２０１６，３９（１１）：２１７５—２１８８． ［３］ 何海江．基于线性分类算法的软件错误定位模型［Ｊ］．计算机 工程与应用，２０１７，５３（２１）：４２—４８． ［４］宗芳芳，黄鸿云，丁佐华．基于二次定位策略的软件故障定位 ［Ｊ］．软件学报，２０１６，２７（８）：１９９３—２００７． ［５］ 杨书新，文．一种改进的基于交叉矩阵统计的软件故障定位 技术［Ｊ］．计算机工程与科学，２０１６，３８（４）：６７９—６８５． ［６］ 曹鹤玲，姜淑娟．基于Ｃｈａｍｅｌｅｏｎ聚类分析的多错误定位方法 ［Ｊ］．电子学报，２０１７，４５（２）：３９４—４００． ［７］ 张华．物联网异常节点定位方法的改进．［Ｊ］．西安工程大学学 报，２０１７，２（３１）：２２５—２３１． ［８］徐勇，毋国庆，袁梦霆．结合Ｃｒａｉｇ插值分析的软件错误诊断方 法［Ｊ］．电子学报，２０１６，４４（１０）：２５１４—２５２１． ［９］ 王琦，孙文辉．基于程序变异分析的软件错误定位［Ｊ］ 计算 机工程，２０１７，４３（１２）：５５—５９． ［１Ｏ］ 何海江．基于排序学习算法的软件错误定位模型研究［Ｊ］． 电子科技大学学报，２０１７，４６（３）：５７７—５８２． ［作者简介］ 郝世选（１９８０一），男（汉族），河南濮阳人，硕士，讲 师，工程师，主要研究方向：软件工程。
