测试用例自动生成技术综述

王廷永 黄松

（陆军工程大学指挥控制工程学院 江苏省南京市 210007）

1 引言

测试用例是软件测试过程中的重要资产，根据ISO/IEEE-24765的定义，测试用例是对输入、执行条件、测试过程和预期结果的规范，这些规范定义了为实现特定的软件测试目标而执行的单个测试，例如执行特定的程序路径或验证是否符合特定的需求[1]。一直以来，测试用例生成技术是软件测试领域研究的热门方向，国内外学者针对测试用例生成技术已经提出若干种方法，如基于模型的测试用例生成方法、基于搜索的测试用例生成方法、基于随机测试的测试用例生成方法、组合测试用例生成方法、基于变异的测试用例生成方法、基于符号执行的测试用例生成方法、基于需求的测试用例生成方法、基于录制与回放的测试用例生成方法。

根据是否需要软件源代码，本文将以上测试用例生成技术分为白盒测试用例生成技术和黑盒测试用例生成技术。其中基于模型的测试用例生成技术、随机测试用例生成技术、基于需求的测试用例生成技术以及基于录制与回放的测试用例生成技术属于黑盒测试用例生成技术，基于搜索的测试用例生成技术、基于变异的测试用例生成技术、基于符号执行的测试用例生成技术以及组合测试用例生成技术属于白盒测试用例生成技术。

2 白盒测试用例生成技术

2.1 基于搜索的测试用例生成

基于搜索的测试用例生成是指利用各种搜索算法例如爬山算法，模拟退火算法，禁忌搜索，遗传算法，粒子群优化算法以及蚁群算法等生成高覆盖的测试用例。2020年Kappé[2]等人将爬山算法引入RESTful API 测试中，实验结果表明爬山算法实现了更高的分支覆盖率。2020年Damia[3]等人提出了一种结合萤火虫算法和无性繁殖优化算法的测试用例生成方法，通过使用无性繁殖优化解决萤火虫算法中的过早收敛问题，实验结果表明此方法在覆盖率与适应性方面取得比现有方法更好的表现。

2.2 基于变异的测试用例生成

基于变异的测试用例生成是指利用变异现有的软件源代码，发现“无用”测试用例和设计新的测试用例。变异测试能够很好发现评估的测试用例发现缺陷的能力。2021年Jeangoudoux[4]等提出一种将测试用例和 oracle 生成作为数值区间域上的一个约束满足问题，通过解决约束问题进行变异测试并生成对应测试用例的方法，实验结果表明其方法优于随机测试，并生成有用的测试用例集。2019年Almeida[5]等人提出一种基于用户行为结合变异算子的Web测试用例生成方法。采用将变异算子扩展了基于录制与回放生成的测试用例，获取更多测试用例。

2.3 基于符号执行的测试用例生成

基于符号执行的测试用例生成是指通过符号化执行待测软件以收集约束条件，并借助约束求解器为每条路径生成测试用例[6]。2019年谢肖飞[6]等人提出一种将模糊测试与符号执行相结合的测试用例生成方法，通过模糊测试提供覆盖率信息来引导符号执行的搜索方向，从而生成更高覆盖率的测试用例，实验结果表明此方法相比于只基于模糊测试的测试用例生成方法取得更高覆盖率以及发现更多的漏洞。

2.4 基于组合测试的测试用例生成

待测软件的输入参数存在多种内外约束，且彼此之间也存在相互作用，借助参数组合方式发现因为参数违反约束条件或参数之间相互作用的缺陷称为组合测试。将组合测试应用于测试用例生成称为组合测试用例生成技术。组合测试存在问题是面对相互作用强度较高的待测软件会导致搜索时间呈指数级别的增长，2020年Hasan[7]等人采用随机选择策略对混合邻域禁忌搜索(RMiTS)算法进行改进，成功提升了较高的相互作用强度组合测试的测试效率，生成更高覆盖的测试用例。2020年Bombarda[8]等人提出基于有限状态机生成约束来解决组合测试的参数组合爆炸问题；自动机检查无效测试序列，并对无效测试序列设置修复方法。结果表明此方法比传统基于测试序列的测试用例有更高的覆盖率以及更多有用测试用例。

3 黑盒测试用例生成技术

3.1 基于模型的测试用例生成技术

基于模型的测试用例生成是指通过建立对被测软件预期行为动作的抽象描述的模型，从模型中派生出测试用例。目前应用测试用例生成的模型主要分为UML 状态图、FSM 有限状态机以及马尔可夫链模型。

基于UML 模型的测试用例生成的研究近年来有2018年李艳梅[9]以 UML 时序图为基础，将时序图首先转化成顺序有向图，再使用遗传蚁群算法进行优化计算，最后生成测试用例，2019年Wang[10]为了解决UML 语义不够精确无法生成完整程序的问题，提出了一种可扩展语言xUML。分析xUML 的活动图以获得系统的层次语法图，然后根据层次语法图获得 JAVA 程序的测试用例。

基于有限状态机模型的测试用例生成研究主要包含有限状态机（FSM）、分层有限状态机（HFSM）与扩展有限状态机（EFSM）。利用有限状态机（FSM）的测试用例生成研究有陈亚龙[11]等人基于最小测试成本迁移覆盖的准则，使用退火遗传算法遍历FSM 模型来生成测试用例。Lefticaru[12]、Briand[13]等人都选择使用遗传算法（GA）来从状态机模型中生成测试用例。利用分层有限状态机（HFSM）实现测试用例生成研究有Florentin Ipate[14]和Logica Banica[15]基于W 方法提出了分层有限状态机（HFSM，Hierarchical FSM）模型的测试方案生成方法，通过对每层FSM 应用W 方法，再将测试生成序列进行合并，能够保证错误检测能力。对于复杂系统采用该算法，既可防止状态爆炸，又可达到测试的充分性。在利用扩展有限状态机生成测试用例的研究有杨瑞等人[16]提出了一种基于EFSM 模型的自动化测试用例生成方法(ATGEM)，通过使用基于数据流分析的路径可行性度量方法来解决不可行路径问题。苏宁等人[17]研究了基于EFSM 不定型切片的测试用例生成方法，发现基于使用模型切片的效率比原模型更高。李栋[18]将EFSM 模型用于Web 应用的安全测试，从威胁模型中解析出安全测试用例。

基于马尔可夫链模型实现测试用例的生成近年的研究有2019年赵卫东[19]等人提出的改进的高阶马尔可夫测试模型，以此模型提出基于快速轮盘赌的二分查找的测试用例生成方法。2020年Gebizli[20]等人引入了一种三步更新优化的基于马尔可夫链测试用例生成方法。用马尔可夫链的形式来表示测试模型。先根据使用概况更新模型中的状态转移概率。再根据静态代码分析估计的故障可能性执行更新。最后是基于动态分析估计的错误可能性。在每次更新优化之后都会生成并执行测试用例，该方法在智能电视系统经过验证，证实了多角度对测试模型进行连续改进是可以提高基于模型的测试的有效性。

3.2 随机测试用例生成技术

随机测试用例生成是指通过在待测软件的输入域上随机产生测试输入并生成测试用例的自动化测试技术。2020年Wetzlmaier[21]等人通过将增加额外的随机步骤以扩展原有测试用例，从而扩大测试用例的窗口覆盖范围以及提升代码覆盖率，提高原有测试用例发现缺陷的能力。2020年Mao[22]等人提出一种灵活划分的自适应随机测试用例生成方法，此方法结合了迭代分割测试和随机分区自适应随机测试的有点，不仅保证生成的测试用例具有较高随机性还保证测试用例分布均匀，同时保持与随机分区自适应随机测试的相同复杂度水平。

3.3 基于需求的测试用例生成技术

基于需求的测试用例生成是指针对待测软件的需求文档进行分析并派生出测试用例的方法。基于需求的测试用例生成方法分为两类：一种是直接分析由自然语言描述的测试需求派生出测试用例，2018年Veera 等人[23]提出从需求到测试用例(Req2Test)方法。预先通过处理特定领域的语料库，建立特定领域的知识库。然后，处理每个需求语句 并根据领域知识库和领域本体来验证需求，并提取实体的领域层次结构生成需求说明。最后从提取的需求说明中构建一个测试模板 并通过使用自然语言生成或基于规则的方法从模板中生成测试用例。另一种是通过分析测试需求构建可用于描述待测软件系统的抽象模型。2015年Lindsay[24]等人通过分析需求建立行为树模型，并以此模型生成从测试用例，实验结果表明此方法能够实现测试用例与需求之间可追溯性，显著减少测试用例数量，提高测试效率。

3.4 基于录制与回放的测试用例生成技术

基于录制与回放的测试用例生成是指通过获取用户操作的信息，经过处理生成相应的测试用例。2018年侯津等人[25]提出的基于控件路径的跨设备UI 自动化测试方法，解决跨设备查找控件失败的问题，2020年张文烨[26]利用深度学习的目标检测提高控件查找的准确度。基于录制与回放的测试用例生成方法在面对不断迭代的软件产品显得力不从心，测试用例以及测试脚本的维护变得繁重又困难。

4 结束语

本文首先介绍测试用例定义，然后介绍了测试用例生成的两个方向：白盒测试用例生成技术与黑盒测试用例生成技术。尽管测试用例生成研究成果层出不穷，并不断结合最新的技术，但是测试用例自动生成还有克服各种困难，比如复杂度问题，不仅白盒测试用例生成技术存在，黑盒测试用例生成技术也同样存在。除此之外，对于如何有效将研究成果真正应用到实际测试用例生成中，目前还缺乏有效解决方案，因此测试用例生成技术有效应用也是今后的研究方向之一。