基于频率差异积分的故障定位算法研究.pdf

《基于频率差异积分的故障定位算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、２０１３年６月西北工业大学学报Ｊｕｎｅ２０１３第３１卷第３期ＪｏｕｒｎａｌｏｆＮｏｒｔｈｗｅｓｔｅｒｎＰｏｌｙｔｅｃｈｎｉｃａｌＵｎｉｖｅｒｓｉｔｙＶｏｌ．３１Ｎｏ．３基于频率差异积分的故障定位算法研究郑炜，李知隆，靳如一（西北工业大学软件与微电子学院，陕西西安　７１００８２）摘要：软件故障定位是软件测试实践中最重要的活动之一。目前，利用人工方式通过调试器进行故障定位仍然占据主导地位，故障定位能力常常依赖于人员的知识和经验，调试效率低，调试支持工具相对较弱，对程序员要求高。因此，无论在软件开发阶段还是软件投入使用以后，软件调试和故障定位的自动化技术越来越成为一个有重要价值的研

2、究课题。研究了多种成熟的基于谓词的统计学错误定位技术，分析了典型的参数化和非参数化故障定位统计模型，提出了一种新的基于谓词统计的故障定位算法：频率差异积分算法（ＦｒｅｑｕｅｎｃｙＤｉｆｆｅｒｅｎｃｅＩｎｔｅｇｒａｔｉｏｎ，简称为ＦＤＩ），突破了现有算法的部分限制；最后对ＦＤＩ算法进行了验证，并和已有算法进行了对比，验证了其有效性和高效性。借助该研究成果，可以有效提高故障定位的准确率和覆盖率，这对于推动程序自动化调试技术、缩短软件开发周期、降低软件的维护成本具有一定的意义和实用价值。关键词：算法，计算机软件，计算复杂度，计算效率，故障检测，数学模型，概率密度函数，软件工程，软件

3、可靠性，软件测试，统计；故障定位，谓词统计中图分类号：ＴＰ３１１．５　　　文献标识码：Ａ文章编号：１０００-２７５８（２０１３）０３-０４３５-０５随着软件规模越来越大，再加之当前软件开发和运行环境的开放性、动态性、多变性，使得软件产1FDI算法原理：利用真值率频率分品在推出时就含有很多已知或未知的缺陷，很多时布密度函数包络面积量化差异候不以人们期望的方式工作，经常发生故障、失效，［１］给人们带来了各种损失。软件故障严重影响软伊利诺伊大学香槟分校的ＣｈａｏＬｉｕ提出错误定件的生产和质量，并且影响在日益加剧。位算法ＳＯＢＥＲ，建立了分别在正确和错误的运行中目前，利用人工方式通过

4、调试器进行故障定位对谓词的评估方法模型：如果一个谓词在错误和正仍然占据主导地位，故障定位能力常常依赖于人员确的运行中的评估结果相差很大，那么就认为它是的知识和经验。特别是对于大型、复杂的、并发的软与错误相关的，并且以通过对模式差异的有原则量件系统而言，如何制定调试策略、进行故障诊断均很［３］化来测量程序谓词的错误相关度。ＳＯＢＥＲ在处有技巧性的要求，而当前的软件调试支持与故障诊理收集到的数据时，假设数值的分布为正态分布，采断分析技术，仍然处于较原始的状态，调试主要以手用了正态分布拟合的方法对收集到的数据进行工方式为主进行，调试效率低，调试支持工具相对较处理。弱，对程序员要求高

5、。因此，研究软件调试和故障定［２，３］同ＳＯＢＥＲ一样，我们对某个程序的一次运位的自动化技术支持，无论在软件开发阶段还是软行过程中某一个谓词P多次赋值的记录采用真值件投入使用以后，故障定位问题日益成为一个有重率来描述：要价值的研究课题。１）在程序的一次运行中，假设谓词P被记录为真的次数为nt，被记录为假的次数为nf，则将收稿日期：２０１２-０９-０４作者简介：郑炜（１９７５—），西北工业大学副教授，主要从事软件测试、验证的研究。·４３·６西北工业大学学报第３１卷ntπ（P）＝（１）nt＋nf称为谓词P在这次执行中的真值（频）率。由极大似然法知，在样本足够多的情况下，P的真值频

6、率无限逼近P取值为真的概率，因此π（P）在一定程度上反映了谓词P在一次执行中取值为真的概率。２）假设对于一个程序，所有的测试用例集合为T，其中Tf表示失败的测试用例集合，Tp表示成功的测试用例集合，则用f（X｜θp）和f（X｜θf）分别表示图２　对面积化整为零Tf和Tp的真值率的概率密度函数。假如图１为某一程序中某一谓词Pd的f（X｜θp）假设在总共X次的程序执行中，谓词P得到了Y和f（X｜θf）在同一坐标系中的函数图像。个真值率记录（因为可能有的执行从不经过谓词P，图中，横坐标表示真值率π（P），纵坐标表示某故有X＞＝Y。真值率占有的比例，即真值率为该值的概率。谓词P的真值

7、率π（P）的取值范围为闭区间［０，１畅０］，因此可以将该区间分成N段单独处理：例如取N＝１００００，我们就得到了［０，０畅０００１），［０畅０００１，０畅０００２），［０畅０００２，０畅０００３），［０畅０００３，０畅００４）⋯［０畅９９９９，１畅０］这１００００个子区间。假设对于每个子区间［a，b］（０＜＝a＜b＜＝１）上，在成功运行和失败运行的样本中，π（P）落在该区间范围内的样本数分别为Zp和Zf，则相应的分布密度可分别表示为ZpZfFp（a，b）＝Ff（a，b）＝（３）YY于是在该子区间上，２个