Page 186 - 《软件学报》2021年第7期

2104 Journal of Software 软件学报 Vol.32, No.7, July 2021

的要求也日益提高.这类软件使用算法来解析数据,从数据中学习到规律,并掌握这种规律,然后对真实世界中
的事件做出决策或预测.与传统软件不同,数据驱动的智能化软件通常使用大量的数据来训练,通过各种算法从
数据中学习如何完成任务.数据驱动的智能化软件的关键是良好的数据,其核心是算法,如果算法或其实现存在
任何问题,那么很可能造成严重的后果,因此对其算法正确性的要求是非常高的.如何对这类系统进行充分的测
试引起了越来越多的研究关注.由于对软件质量的更高的要求,其测试所消耗的开销也更大,需要更有效的手段
对测试用例的规模进行控制.软件测试的预算大部分都花费在回归测试上,因此,如何对回归测试用例集合进行
有效的缩减进而降低这一类非确定性软件整体的测试开销是一个值得研究的主题.
在程序执行过程中,如果在某一程序点观测到的变量 y 的取值可以降低更早之前某一点上变量 x 取值的不
确定性,则称从 x 到 y 产生了一个信息流,而信息流强度表示 x 取值的不确定性降低的程度.信息流及其强度可
[1]
在一定程度上反映程序执行时变量之间的依赖程度.Masri 和 Podgurski 等人 的工作表明,实际场景中弱信息
流是非常普遍的,甚至其中大多数信息流的强度为 0.数据驱动的智能系统包含大量数据处理过程,并产生许多
中间值,而这些中间值之间的关联性很弱,因此在数据驱动的智能系统中信息流弱的现象更加严重.弱信息流现
象意味着如果程序执行过程中产生了一个错误的中间值,这个错误的状态很可能无法传递到程序输出或检查
点上,从而无法被测试人员发现,即发生偶然正确性现象(coincidental correctness,简称 CC).偶然正确性现象是指
程序中包含错误的语句被执行但仍通过了测试的现象,其原因是错误语句被执行时没有产生错误的中间结果
或状态,或者这个错误的中间结果或状态没有被传递到程序的输出或检查点中.当程序执行时的信息流强度较
弱时,程序输出或检查点上的值与各个中间结果之间的关联性较弱,很可能会出现偶然正确性现象.
许多研究工作已经证明偶然正确性现象在实际场景中是非常普遍的 [2,3] ,并且影响了许多测试技术的有效
[4]
性 .其中,回归测试技术也受到了偶然正确性现象的影响.常用的回归测试用例选择技术是基于代码修改分析
选择出与代码修改相关的用例.然而,这种方法选择出的回归测试集合包含了大量发生偶然正确性现象的用例,
这些测试用例虽然覆盖了被修改代码但仍无法检测其中包含的错误.对于数据驱动的智能系统等偶然正确性
现象的发生概率相对较高的系统,回归测试用例选择的结果更易受到偶然正确性现象的不良影响.因此,我们从
偶然正确性现象的角度出发,提出一种有效缩减回归测试规模的测试用例选择方法,从而降低测试开销.
在以往工作中 [5,6] ,我们提出了一种估算偶然正确性现象发生概率的方法,该方法通过估算错误在执行过程
中的传播概率来估计偶然正确性现象的发生概率.基于这项工作,我们提出一种基于偶然正确性概率的回归选
择技术.基于代码修改的回归测试选择技术所选出的测试集合包含大量无法检测出故障的用例(即发生偶然正
确现象的用例),本文根据偶然正确性概率对覆盖修改的用例作进一步选择,以提高测试选择的准确性.
本文第 2 节介绍偶然正确性现象和回归测试选择技术,并给出估算偶然正确性现象的发生概率的方法.第 3
节给出根据偶然正确性概率进行回归测试选择的方法.第 4 节通过实验对基于偶然正确性概率的回归测试选
择方法进行评估.最后第 5 节对本文工作进行总结.

2 背景知识

2.1 偶然正确性现象
[7]
偶然正确性现象的概念最初是由 Budd 和 Angluin 提出的,是指程序中包含错误的语句被执行但仍通过了
[8]
测试的现象 .Masri 根据 PIE(propagation-infection-execution,传播-感染-执行)模型对偶然正确现象给出了更明
[9]
确的定义.PIE 模型是由 Voas 提出来的,强调了程序缺陷的执行并不是程序失效的充分条件,还需要满足将错
误的中间状态传播到程序的输出中.类似地,在 Ammman 和 Offutt 于 2008 年提出的 RIP(reachiability-infection-
propagation,到达-感染-传播)模型等其他研究工作 [10,11] 中也对该问题进行了讨论.Voas 指出,当且仅当满足下面
3 个条件时错误才会被观测到.
(1) 执行(execution),错误代码需要被执行到.
(2) 感染(infection),执行错误代码时必须触发一个错误的中间状态.
(3) 传播(propagation),这个错误的中间状态必须能够传播到最后并输出,使得我们能够观测到它与预期的