Page 68 - 《软件学报》2021年第9期

2692 Journal of Software 软件学报 Vol.32, No.9, September 2021

软件测试是为了发现程序错误,以提高程序质量的一个过程 [1,2] .软件测试贯穿软件开发的整个过程,是软
[3]
件开发不可或缺的一个环节.通常在软件生命周期中,30%~40%的时间和精力花在软件测试上 .研究表明:在
软件测试中,毫无限制地对所有程序进行验证,将会花费维护费用的 50% [4,5] .而软件测试的重用在提高软件测
试质量、缩短测试周期和改善测试人员的经验不足等方面,均起着十分重要的作用.目前,软件测试重用的研究
[6]
已成为软件测试工程化研究的热点之一 .
软件测试重用技术是指在新的软件测试工作中重复使用已有的测试资源,其目的是充分利用之前软件测
[7]
试中的经验和成果,增强测试的效率和可靠性 .测试用例的重用是指测试工程师在执行回归测试或者一项新
的测试工作时,通过直接调用或修改已经生成的测试用例,并将它们运用测试的过程,而不用每次面对新的测试
工作都需要从头开始设计测试用例.测试用例作为软件测试的核心内容,它的重用是整个软件测试重用的关键
[8]
环节 .
[9]
测试用例重用的研究主要包含两个方面:可重用测试用例的生成和可重用测试用例的管理 .本文主要研
究将程序已有测试用例使用到相似程序测试用例的生成过程中,故检测待测程序之间的相似度是研究用例重
用的前提.
程序代码相似性的研究技术基本成熟,主要运用于计算机教学和软件剽窃检测等领域 [10] .最长公共子串和
Levenshtein 距离等程序相似性度量算法重点考察源代码之间的相似程度,而基于图的结构特征的相似性分析
[9]
方法使用图的结构来反映程序功能特征的相似性分析方法 .图的结构特征是较为高级的语法特征,主要包括
控制流图和数据流图两种:控制流图反映了程序的逻辑结构,数据流图反映了程序的数据流转关系.
可见,程序相似性的判定可以从序列和图等不同的特征进行.本文研究程序间相似性的目的是研究相似程
序间测试用例重用的方法,以此提高测试用例的生成效率,减少软件测试的工作量.主要做了以下工作.
1) 对于待比较相似性的程序,构建它们的关键字流图.比较流图节点中的关键字是否相同,具有相同关
键字的节点构成公共关键字流图子图;
2) 程序的关键字流图和关键字流图最大公共子图构建完成后,利用最大公共子图距离方法比较待测程
序的相似程度,相似程度较高的程序可用于测试用例的重用;
3) 测试用例的重用是将程序已有的测试用例共享于相似程序.采用遗传算法来完成测试用例的重用,将
相似程序已经生成的测试用例引用到种群进化的过程中,种群的其他个体通过向这些测试用例学习
加快进化速度,完成测试用例的重用.
本文第 1 节分析程序相似性及测试用例重用的相关工作.第 2 节研究相似程序的判定,主要涉及关键字流
图构建方法、关键字流图最大公共子图的查找以及根据最大公共子图距离求得待测程序的相似度.第 3 节提出
相似程序间测试用例重用的方法,并阐明将遗传算法用于测试用例重用的原因;实验多方面将本文方法与传统
方法在测试用例生成中的效率进行对比,根据实验结果给出本文存在的不足以及有效性分析.第 4 节总结全文,
并提出下一步的研究工作.

1 相关工作

程序相似性的制定标准是一项重要工作,近年来,不少学者从语义结构和图等不同方面探究程序的相似性.
Kwon 等人 [11] 利用子图作为检测恶意程序的特征,因为同一个恶意程序家族中的程序会共享子图.子图的
查找则需要程序样本中抽取 API 调用建立分层级行为依赖图,用它们寻找子图.Wang 等人 [12] 提出了使用控制
流图和数据流图特征对二进制程序进行相似性比较和同源分析的方法,实验对象采用微软不同版本的动态链
接库验证算法的有效性.该算法比较适用于同一公司发布的同源良性程序相似度的比较.
1965 年,Levenshtein [13] 提出 Levenshtein 距离算法,该算法常用于字符串的比较,计算两个字符串差异的大
小.源字符串通过添加、修改、删除等操作变化到目标字符串,其最少的改变次数看作是 Levenshtein 距
离.Levenshtein 距离越小,字符串的相似度越大.Wang 等人 [14] 提出两种基于双向比较的最长公共子串算法,该算
法将动态规划算法(LCSstrDP)与后缀数组算法(LCSstrSA)相结合,有效地解决了动态规划算法计算速度较慢的