论文部分内容阅读
演化测试是一种新兴的极有潜力的测试数据自动生成技术。它通过将测试数据的生成问题转化为搜索问题,并利用进化算法进行搜索从而生成所需的测试数据。在演化测试中,测试数据的搜索过程是在适应度函数的引导下进行的,因此,适应度函数的导向能力极其重要。然而,由于实际程序本身各种各样的非线性特征,一个具有导向性的适应度函数的设计在这里变得尤为困难。近年来,已有大量研究针对这个问题进行。然而,传统工作所提出的适应度函数要么只能适用于某种特殊的程序结构,要么需要改变搜索过程。特别是,对于程序中普遍使用的标志变量情况,传统工作对于不同标志变量的出现情况往往必须采用不同的适应度函数,而对于普遍存在的嵌套If-Else结构、Switch-Case结构和函数调用结构,则鲜有工作进行研究。为此,本文对不同程序结构下的适应度函数设计问题进行了研究。在研究中发现,现有适应度函数导向性丢失的根本原因是适应度函数设计中未能充分考虑程序本身固有的数据依赖和控制依赖信息。因此,在对适应度函数的研究过程中,本文始终坚持将程序的数据依赖和控制依赖信息引入适应度函数计算公式的基本思路,并针对如下程序结构的适应度函数计算进行了具体研究：(1)针对标志变量问题,考虑了标志变量对其它变量的数据依赖,引入“标志变量代价函数”替换传统适应度函数中的分支距离,提出了针对标志变量的统一适应度函数。(2)针对嵌套If-Else结构,考虑了嵌套分支间的控制依赖关系,同时引入了“分支乐观度”用于评价测试输入对各个内层判断分支条件的满足程度,设计了一种新的针对嵌套If-Else结构的适应度函数计算规则。(3)针对Switch-Case结构,提出了通过展平控制依赖图来准确地反映各个case分支并列的语义结构,更好的度量测试数据与目标分支在控制流上的距离。(4)针对函数调用结构,考虑了函数调用链上的控制依赖关系,首次提出了一种基于函数调用依赖结构的适应度函数。实验研究和工程应用充分表明,在不同的程序特征下,本文所提出的适应度函数计算公式有效地引导了演化测试的搜索过程,大大降低了搜索的时空开销,使得实际工程代码的演化测试更加实际可行。