2.2.4　迭代松弛法

1998年,Neelam Gupta提出了迭代松弛法[72]。该方法引入程序切片思想,任选一组数据输入考察路径上的分支谓词,通过数据流分析确定谓词函数对输入变量的依赖关系,构造谓词片和动态切片,先建立谓词函数关于当前输入的线性算术表示,再建立输入变量的增量线性约束系统,求解约束系统,获得一个输入增量,进而得到下次迭代的输入值,最终产生覆盖路径的测试用例。由于该方法在每次迭代时程序执行次数与路径长度无关,仅受限于变量个数,因此它能够避免Korel和Gallagher方法中回溯带来的资源浪费。

Neelam Gupta等人最初采用高斯消去法求解约束系统,如果自由变量取值不合适,则会令线性方程不相容,从而需要重新试探新的取值。后来,他们提出了用最小二乘逐步向可行解逼近[73]。John Edvardsson等人[74]指出,对于线性程序路径约束,Gupta方法是不完备和非终止的。Neelam Gupta等人将该方法用于分支覆盖的测试用例生成[75]。(https://www.daowen.com)

国防科技大学的单锦辉等人[76,77]对Gupta方法进行了改进,省略构造谓词片和输入依赖集的过程,任选一组输入运行路径语句,求得路径上各谓词函数的线性算术表示,直接为输入变量建立线性方程系统,求解后直接获得一组新的输入。