基于程序谱的错误定位技术的研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于程序谱的错误定位技术的研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要基于程序谱的错误定位技术经由执行成功和失败测试用例来获取测试用例的代码覆盖信息，并基于这些信息来识别程序的错误所在。然而，这些技术的有效性会受到巧合正确性的不利影响。所谓的巧合正确性，是指当程序即便执行了错误处代码，却仍然能够产生正确的输出的情况。本文提出了一种基于聚类的策略，以提高基于程序谱的错误定位技术的有效性。这种策略基于相同聚类的测试用例拥有类似的行为的思想。因此，巧合正确测试用例不仅有很高的概率与失败测试用例类似，而且也有很高的概率彼此类似。

【关键词】基于程序谱的错误定位 巧合正确性 聚类分析 覆盖矩阵重建

在软件开发生命周期和过程中，软件调试对提高软件质量有着非常强大的作用。然而，调试通常需要花费大量的人力和时间，在调试的主要任务中，错误定位已被公认为最困难，最繁琐，以及最耗时的步骤。为了减少调试的成本，很多研究人员把注意力放到了基于程序谱的错误定位（SFL）技术，该技术具有简单、自动和高效率的优点。

SFL通常会收集失败以及成功的测试用例的执行信息，用于构建程序谱。信息收集完毕后，SFL将可采用不同的统计公式来评估程序中代码的可疑程度并且按照可疑程度对程序代码进行排序。虽然SFL的有效性已得到证实，但仍然受到巧合正确性的影响，巧合正确是指在错误代码被执行时，程序仍然能产生正确的输出的情况。SFL技术之所以受到巧合正确性的影响，根源在于SFL的基本思想，即在程序内主要由错误测试运行所执行的代码比那些由成功测试运行所执行的代码要更有可能是包含错误。基于该理念，当出现大量巧合正确的测试用例时，错误代码的可疑性将可能会低于主要由失败测试运行执行的程序代码的可疑性，从而增加了发现错误的开销。因此，排除巧合正确测试用例能够安全地提高SFL的效率和准确性。然后，由于错误代码的位置无法预知，很难识别所有通过测试用例中的巧合正确的测试用例。同时，用于识别巧合正确测试用例的策略也可能会排除掉很多其他测试用例。

1 研究背景及动机

1.1 背景

基于程序谱的错误定位是错误定位方法中最受欢迎的方法之一，并且因其简便性及有效性受到了多方关注。该方法基于一个简单的常识经验：主要由失败测试运行用例执行的程序代码更可能包含错误，而主要由通过成功测试用例所执行的程序代码包含错误的可能性更小。在SFL中，测试用例的动态执行可以采用一个二进制序列进行表示，例如程序谱。在程序谱中每一比特对应一条程序代码，其中1表示该代码在本次运行中被执行，而0表示该代码未被执行。

以往研究表明：巧合正确性对SFL的准确度的影响很大，巧合正确是指当错误代码被执行而程序仍能够产生正确结果输出的情况。W.Masri等人已经证明了巧合正确性会降低SFL的安全性。SFL的效率和准确性可以通过清理巧合正确的测试用例得到改善。然而，由于我们无法预知错误地点，很难识别出巧合正确测试用例。X. Wang等人提出了提出了情景模式以帮助覆盖精细化，从而加强程序错误和错误语句的覆盖之间的联系。W. Masri等人主要专注于如何识别通过测试用例中更有可能包含有巧合性正确的子集。他们首先确定程序单元（cce）中有可能与巧合正确的测试用例相关的部分，然后将导致一些可疑cce为巧合正确的测试用例进行分类。Aritra通过比较测试用例之间的相似性来识别巧合正确的测试用例。为了削弱巧合正确性对SFL的影响，他对于那些与失败测试用例相似的通过测试用例采用了两种不同的策略―给予其低权重或将其排除。与Aritra的想法类似，Yi Miao等人同样认为巧合正确的测试用例肯定与失败测试用例有相似行为，他们将测试用例划分聚类，并且将与失败测试用例在同一聚类的通过测试用例加以标签，作为识别出的巧合正确的测试用例（Ticc）。为了降低巧合正确性的不利影响，采用以下两种方式来处理识别出的巧合正确的测试用例：将其删除或重贴标签。

1.2 研究动机

Yi Miao等人已说明在软件测试中，巧合正确性是很常见的，并且通过排除巧合正确的测试用例，错误定位的准确度会得到提高，同时SFL的有效性可以得到改善。然而，由于错误单元的位置不可预知，几乎不可能做到识别出所有巧合正确测试用例。在之前的研究中，排除巧合正确测试用例的策略可能会同时排除掉很大一部分其他成功测试用例。

在进行聚类分析后，具有相似程序谱的测试用例会被认为是具有相似行为，从而划分至相同聚类。若我们认为巧合性正确测试用例的行为彼此类似，则我们同样可以认为在所有聚类中包含巧合性正确测试用例的聚类在聚类中所占的百分比小于在所有测试用例中的巧合性正确测试用例所占的百分比。基于该假设，基于聚类的策略可以用于降低巧合正确性问题，并且能够提高SFL的有效性。

2 我们的方法

在本文中，我们提出了一种基于聚类的方法来削弱巧合正确性对错误定位技术的影响，该方法基于程序谱将测试用例进行聚类处理，使具有相似行为的测试用例被分组到同一聚类中，同时相互间差异很大的测试用例会被放置在不同的聚类中。我们的策略是：在使用SFL技术找寻程序错误时，开发人员可以采用以下步骤来提高SFL的有效性。

2.1 程序谱收集

在本文中，我们使用gcov来进行代码插装，并借此来收集代码覆盖信息。收集完成后，每个测试用例的执行信息将由其程序谱表示：pi = ，其中n表示给定程序中可执行语句的数量，ej=1表示第j条语句在第i个测试用例的运行中被执行，否则ei=0。

2.2 聚类分析

已收集测试用例的覆盖信息即程序谱将作为聚类的对象。对象的数量与测试用例的数量相同。距离函数使用N维欧几里得距离-因为其计算方便并且使用广泛。

由于程序中可能存在太多的可执行语句，测试用例的程序谱的维度可能会非常大，从而严重影响了聚类分析的时间。因此，我们使用动态基本块（DBB）来降低单个对象的维度。一个DDB是程序中若干代码的集合-这些代码被测试组件中相同的测试用例所覆盖，同一个DDB中的代码在覆盖矩阵中对应的行是完全相同的，因此，DDB的数量要远小于statements的数量。通过使用DBB，我们可以将程序谱pi=转化为新的程序谱pi’= ，其中DBBi=1表示第i个DBB中的代码全部被执行。通常，m要远远小于n，所以使用新的程序谱进行聚类分析可以节约大量的时间。

由于其简便和快速性，我们选择了简单K均值方式作为聚类算法。简单K均值算法需要事先输入聚类的数量作为参数。在本论文中，该参数是根据所选测试组中程序的DBB数量决定。假设n表示聚类的数量，则n = |DBB|*s，其中|DBB|指DBB的数量。

2.3 覆盖矩阵重建

在聚类之后，测试用例依据其程序谱被划分至不同的聚类。根据本文中提出的假设，我们将通过聚类的语句覆盖信息重建覆盖矩阵。根据聚类中包含测试用例的不同，我们将聚类划分为Cf与Cp两类，Cf是指包含失败测试用例的聚类，而Cp则仅包含成功用例。对于不同种类的聚类，我们采用不同的策略来收集聚类程序谱：

Cf中的聚类： 由于成功测试用例与失败测试用例一起被分类至Cf聚类中，将有很大可能是巧合正确的测试用例，我们将采用失败测试用例的程序谱来构建整个聚类的程序谱：对于Cf中的第m个聚类，我们使用聚类程序谱cm=，其中si= i表示执行第i个语句时cm中有i个失败测试用例。

Cp中的聚类： Cp中的测试用例是巧合正确的可能性很小。对于Cp中的第j个聚类，我们采用聚类程序谱cj=，其中si=1表示聚类中至少有一个测试用例执行第i个语句。

因此，通过连接所有聚类的程序谱，我们可以重建一个新的覆盖矩阵，用于表现不同种类行为的代码覆盖信息。

2.4 错误定位

在重建新的覆盖矩阵后，我们可以使用统计公式来计算程序代码为错误的可疑程度。

由于我们的目的不是与各种错误定位技术进行比较，而是为了提高错误定位技术的准确度，我们选择了 Ochiai、Jaccard、Hamming以及Optimalp这些参考文献与我们的策略一起来对缺陷进行定位。正如XiaoyuanXie等人在参考文献中所提到的，我们选择的SFL技术可以代表其他的SFL技术。因此，我们有理由相信，只要我们的策略能够提高上述5种技术的有效性，则其也将有益于其他SFL技术。

3 实验与评估

3.1 实验设置

在本论文中，我们选择西门子程序组以及Space作为测试程序。西门子的程序组件中包含7个C程序，并且所有的程序均包含正确的版本，一定数量包含单一错误的错误版本，以及一个相关的测试集。Space 是由欧洲航天局最初编写的，并且包含有38个错误版本。 所选择程序的详细信息见表1。 表格的第一列是程序的名称。第二列中列出了外面实验中所使用每个程序的错误版本数量。第三列说明了每个程序包含可执行语句的数量（代码行数）。第四列说明了每个程序中测试用例的数量。

此外，我们排除那些任何测试用例均不会检测到异常的错误版本，以及那些修改了头文件的错误版本，再忽略掉定义或声明类型的错误版本。最终，实验中使用了146种错误版本。

有两种错误需要特别注意。第一种是一个错误由多个语句共同组成，我们假设对这些语句的任意一个进行检查都能够定位该错误。另外一种是与缺少的代码相关的单一错误，我们假设开发者对缺少代码的前后语句进行检查均能发现缺少代码的错误。

我们使用gcov（GNU call-coverage profiler）来收集程序中的语句覆盖信息，然后通过Weka进行聚类分析。所有的实验均使用配置有2.20 GHz英特尔（R）酷睿（TM）2双核CPU、4 GB内存以及Ubuntu 10.04系统的电脑进行。

3.2 评估标准

SFL的准确度通常由在找到错误语句前所需检查的语句数量所占百分比来评估。我们也采用这一概念，通过对比原始的SFL与我们策略的错误定位精度（简称Acc）来对我们的策略性能进行评估。Acc值越低表明性能越好。

为了进行更详细的比较，我们使用相对改善（简称Imp）进行分析。Imp是对使用我们的策略与使用SFL找到所有的错误需要检查的总语句数量进行比较。Imp值越低表明性能越好。

3.3 结果及分析

3.3.1 聚类数量的影响

在我们的论文中，聚类的数量n是一个影响我们策略的重要因素。在之前的部分，我们假设n = |DBB|*s是聚类的数量。

图1呈现的是在不同s下我们的方法的Imp值。从图1中可以看出，我们的策略可以改善SFL的性能，并且当s > =1.2时达到最佳。

3.3.2 精度的提高

图2表明在我们选择的所有错误版本中SFL与我们方法的Acc的比较。x轴表示被检测可执行语句的百分比。y轴表示错误版本的百分比。图2中的任一点表示在检查了百分之几的代码后，能够找到百分之几的错误版本中的错误。

如图2所示，对于Optimalp公式，我们方法的曲线与其相关的SFL很接近。但是我们方法在采用其他SFL公式时，其曲线总是比只采用该公式的SFL技术曲线提升得更快，接近Optimalp’的曲线。这表明了我们的方法明显提高了所选类型SFL（不包括Optimalp’）的准确度。

为了进一步的详细比较，图3说明了在每个程序中我们所采用的基于聚类的策略对于每种类型SFL的Imp值。x轴表示程序的名称。y轴展现了特定种类SFL的Imp值。图3中的表格列出了每个程序Imp的具体数值。

如图3中所示，除了Optimalp，每个程序的Imp数值均小于100%。这表明我们的策略改善了所有程序SFL的有效性。以图5中的Ochiai为例，在程序print_tokens2中最低Imp为58%，在程序program replace中最高Imp为98%。这说明我们的策略对于基于Ochiai 的定位技术在程序print_tokens2中获得了最大的改善，在程序program replace中则改善得最少。此外，这还意味着在定位程序print_tokens2中的错误时，我们的方法需要检测Ochiai所需检测语句的58%，同时在定位程序program replace时，我们的方法需要检测基于Ochiai 的定位技术所需检测语句的98%。

然而，我们的策略也有失败的时候。表2中列出了基于Ochiai 的定位技术得到的Imp值小于，等于以及大于100%时失败版本的百分比。有10.9%的失败版本的Imp大于100%，这表明我们的策略在此情况下未能改善其有效性。但总体而言，我们的策略仍然是有效的。

3.3.3 与排除策略对比

在之前关于巧合正确性问题的研究中，研究人员通常对识别出的巧合性正确测试用例采用排除策略。为了验证我们的方法，将我们的方法与Masri的方法以及Yi Miao的方法进行比较。

Masri等人仅选择了18个错误版本作为其主体程序，他们使用安全性变化和精度变化作为其评估指标。表3说明了对于他们选择的18种错误版本，他们及我们方法的实验结果。正如表3所示，我们的方法能够更加有效的改善SFL的准确性。

图4是我们选择的119个错误版本（如图2所示）中Yi Miao的方法与Ochiai的方法，以及我们的方法与Ochiai的方法的ACC的比较。如图所示，我们方法的曲线始终要高于Yi Miao的方法。这表明了我们基于聚类的策略要优于Yi Miao的排除策略。

3.4 对实验有效性的影响

我们实验有效性的不足之处可以概括如下：

首先，我们使用西门子的程序组件作为我们主体程序，该程序均为小型C程序，并且所有的错误均为手动输入。为了降低这个不足之处，我们计划在将来将我们的技术应用于更加大型的程序。

此外，在我们的程序中使用gcov记录覆盖信息，同时使用数据挖掘工具Weka进行聚类分析。这两项方法均为成熟并且广泛使用的方法。同时，在我们的研究中，由于其简便和有效性，采用了简单的K均值作为聚类算法。然而，在对失败测试用例进行聚类时，过于集中或过于分散的情况，均会对结果产生不利影响。

4 结论及今后的工作

在本论文中，我们提出了一种基于聚类的策略以降低巧合正确性对SFL有效性的不利影响。为了提高SFL的有效性，为重建覆盖举证引入了两种策略，即选择Cf中的失败测试用例的程序谱，以及获取Cp中聚类的覆盖信息。为了评估所提出的方法，我们进行了一项实验。实验结果表明，该实验取得了预计理想情况结果相近似的结果。

在今后的工作中，我们准备进行更全面的实证研究，并探讨一下问题：

（1）通过更多程序评估我们基于聚类的策略。

（2）寻求更好的聚类算法以适应本文中的情况。在我们的方法中，失败的测试用例聚类要么过于集中，要么过于分散都会导致不好的结果。由于其简便性，在我们的实验中采用了K均值，事实上还有许多其他的聚类算法需要进行探讨。

（3）对于多错误如何对我们的方法的影响进行实证研究，并探讨如何应对此种情况以最小化其不利影响。

（4）探索我们策略失败的原因。

作者简介

蔡烨挺（1988-）男，国防科技大学计算机学院硕士。研究方向为软件工程。

作者单位

1.国防科技大学计算机学院 湖南省长沙市 410073

2.北京信息技术研究所 北京市 100085