关键词:
种子策略
常量池
软件测试
程序分析
测试用例自动生成
摘要:
基于搜索的软件测试(Search-based Software Testing,SBST)的测试效率与启发式算法、适应度函数以及种子策略等因素相关。在SBST运行过程中,相比于随机生成的初始值,种子策略可以利用被测程序中的信息提供更好的初始值,提升测试效率。现存的种子策略采样算法大都是基于研究人员的经验直觉给出,其效率影响因素未知,如何解释种子策略的有效性,并提出更好的采样算法是值得关注的问题。
本文通过对种子策略的适用场景对比研究,进一步揭示了种子策略中存在的问题,并提出了一种基于分支的智能种子策略Evo Seed。通过在2000个被测方法以Evosuite中的随机种子策略、静态种子策略、动态种子策略和混合种子策略的比较分析得出,对于具有值保持属性和敏感度保持属性的数据流路径形成的快速通道,种子策略可有效提高测试效率。在此基础上,提出了一种基于分支的智能种子策略,Evo Seed。Evo Seed可以根据被测方法所处场景构建相应的常量池,若被测方法中包含具有快速通道结构的种子分支,则为种子分支动态构建小型的局部常量池,缩小采样范围;若被测方法中不包含具有快速通道结构的种子分支,则保持原有的全局常量池。Evo Seed的自适应采样算法根据未覆盖的种子分支所占比例,动态调整使用常量池的概率,加快目标分支的覆盖,提高采样的有效性。与Evosuite的对比实验结果表明,在相同时间预算下,Evo Seed的分支覆盖率提升了1%;在覆盖率相同的情况下,Evo Seed的收敛速度优化了0.5秒。
综上,本文发现的种子策略快速通道以及所提出的基于分支的种子策略可以提高SBST的效率,相关成果也可以应用到其他的软件测试活动中,丰富软件测试领域的效率优化研究。在实际应用中,该策略思想可以为大规模软件测试工作提供指导性意见,改善其整体效率和质量。