基于启发式算法的测试数据自动生成方法研究.pdf

基于启发式算法的测试数据自动生成方法研究

摘要

测试数据自动生成可以帮助测试人员更高效、更准确地完成测试工作，提高测试的

效率和质量。测试数据生成工作首先要获得目标路径集，基本路径集中的不可行路径会

造成算法和测试资源的浪费，所以要排除不可行路径。覆盖目标路径有许多方法，包括

静态法和动态法，其中属于动态法的启发式算法可以将这类问题转化为搜索问题，通过

不断地迭代来生成并优化测试数据，直至覆盖全部目标路径。本文将围绕测试数据的自

动生成问题展开研究。主要从以下两个方面开展工作：

首先针对基本路径集中不可行路径检测不全面的问题，提出了基于数据流测试和粒

子群算法的不可行路径检测系统。该系统通过预处理、生成分支覆盖表和关联树、排除

不可行路径三个步骤来检测不可行路径。在预处理步骤中，获得被测程序的所有变量的

定义—使用路径，作为不可行路径检测系统的输入。在生成分支覆盖表和关联树步骤中，

使用粒子群算法运行被测程序获得路径覆盖信息，填充分支覆盖表并得到关联树。在排

除不可行路径步骤中，使用假设路径生成器组件和比较器组件来检查定义—使用路径集

中的每个路径，从而删除不可行路径。实验结果表明，系统可以检测由“分支-分支”冲

突导致的条件相关不可行路径，还可以自动检测不可行的定义—使用对，从而检测由“分

配-分支”冲突导致的定义—清除不可行路径。

然后针对使用蚁群算法进行测试数据自动生成工作中存在测试数据覆盖率偏低、算

法执行时间长、进化代数偏高的问题，提出了蚁群算法和否定选择算法相结合的ACO-

NSA混合算法，算法将否定选择算法的策略应用到蚁群算法中，使用汉明距离进行检测

集与非检测集的数据匹配，目的是去除蚁群算法过程中的冗余数据，包括初始种群的生

成，搜索过程中更新测试数据集，提出蚁群算法的局部搜索、全局搜索、信息素更新和

针对测试数据生成的适应度函数。最后给出ACO-NSA混合算法的和子函数，用流程图

直观展示算法流程。

最后给出使用启发式算法进行测试数据生成的对比实验。实验结果表明，与蚁群算

法、遗传算法、粒子群算法相比，使用ACO-NSA混合算法来生成测试数据，可以减少

测试数据的生成数量，提高测试数据的覆盖率，提高完全覆盖的成功率，减少算法的进

化代数，提高算法收敛性。

关键词：软件测试；不可行路径；测试数据自动生成；蚁群算法；否定选择算法

基于启发式算法的测试数据自动生成方法研究

Abstract

Automatedtestdatagenerationcanhelptesterscompletetheirworkmoreefficientlyand

accurately,thusimprovingtheefficiencyandqualityoftesting.Thefirststepintestdata

generationistoobtainthetargetpathset.Inthebasicpathset,infeasiblepathscanwaste

resourcesandcausealgorithmicinefficiency.Thus,itisnecessarytoexcludeinfeasiblepaths.

Variousmethodscanbeusedtocovertargetpaths,includingstaticanddynamicmethods.

Amongthem,dynamicheuristicalgorithmscantransformthistypeofproblemintoasearch

problem,generatingandoptimizingtestdatathroughiterativeprocessesuntilalltargetpaths

arecovered.Thispaperfocusesontheproblemoftestdatageneration,a