基于FSM的测试用例生成和测试优化

论文摘要

随着软件复杂性的增长、软件不断向其它领域的渗透及对软件可靠性要求的增加,如何保证软件的质量和可信性变得越来越困难,相应的成本也不断增加。早期的研究表明测试成本已经占软件开发总成本的50%以上,未经充分测试的软件会带来严重的经济影响。基于模型的测试是指由软件的行为模型产生测试用例,再测试实际的软件实现是否与模型一致。模型描述了软件“做什么”而不是“怎么做”,因此由模型导出测试用例时不必考虑到程序的具体实现。过去,一些基于模型的测试生成方法和测试准则已被相继提出。例如W方法、UIO方法、DS方法、状态覆盖准则、迁移覆盖准则和迁移对覆盖准则等等。然而,由于测试意图的不同,上述这些测试生成方法和测试准则并不能解决所有的问题且具有一定的局限性。例如,虽然W方法具有很强的错误探测能力,但该方法生成的测试序列包含大量的冗余,导致测试成本的急剧增加。为此,PW方法和R-PW方法被相继提出。这些方法具有与W方法相同的测试效率,同时可减少测试序列中的冗余。然而这些被提议的方法同样也有其自身的缺点,例如实现算法的效率问题。本文主要研究基于FSM模型的测试用例生成和测试用例优化。采用的建模语言为有限状态机。本文的研究成果同样适用于带标签迁移系统（LTS）、约束逻辑程序和Petri网等。基于状态机的理论,本文提出了一整套基于FSM模型的测试用例生成及测试优化的理论和技术。首先本文研究了基于模型的测试理论,包括三种主要的建模语言（约束逻辑程序、有限状态机、标签迁移系统）的理论基础。其中重点是介绍了有限状态机的原理,由有限状态机产生测试用例的前提和假设,常见基于模型的测试生成方法的理论基础,测试覆盖准则及它们适用范围,并对现有测试覆盖准则进行了一定的理论评估。另外还介绍了常用的测试优化技术等。接着本文讨论了现有的一些基于模型的测试生成算法及满足测试覆盖准则的一些经典算法,并分析了不同算法的时间效率和空间效率。针对现有的特征集合和迁移覆盖集合的算法效率过低问题,提出了两个改进算法,并采用形式方法给出了这两个算法的理论支持,最后实验对比了这两个算法与现有算法的效率。软件测试的目的是用最小的成本测试软件中的每一部分。然而,实际软件测试中,穷尽测试软件中的每一部分是不现实的。因此需要对测试成本和测试效率进行权衡。依据程序中80%的错误来源于20%的代码原理,本文提出了确定性有限状态机的最小测试成本迁移覆盖准则。由该准则产生一组测试序列集合具备完备性、无冗余或冗余较小、集合较小、测试序列总长度较短,有效的平衡了测试成本和测试效率。在针对复杂系统进行测试时,本文建议采用正则表达式来描述系统的有限状态机模型,再对正则表达式进行有效分解,获取相关的子正则表达式,最后由子正则表达式产生相关的测试用例。该方法的重点及难点是如何获取正则表达式的有效分解,使得测试用例来源于被分解的正则表达式与来源于原表达式的测试用例具有相同的错误探测能力。这种测试生成方法与最小测试成本迁移覆盖相互补充,弥补了最小测试成本迁移覆盖对FSM模型中循环部分测试不足的问题。为解决测试序列集合中的冗余问题,本文也提出了解决方案。一类是针对由某个测试覆盖准则产生测试用例时存在冗余问题的解决。本文将一个测试序列看成一个字符串,利用字符串匹配的方式约简冗余的字符,同时增加满足该覆盖准则的必要约束条件,保留满足约束条件的冗余,删除不满足约束条件的冗余。随后设计了一组转换规则,将约简后的无效测试片段转换成有效的测试序列。为设计有效测试用例,本文建议首先采用逻辑运算进行约简,再采用了逻辑覆盖准则设计测试用例。随后本文讨论了现有的逻辑覆盖准则,分析了逻辑覆盖准则与测试用例生成之间的关系,并提出了一种新的逻辑覆盖准则（TTJ准则）。最后本文开发了一个基于FSM模型的测试生成工具。该工具整合了上述所有的测试生成及测试优化算法。利用该工具,能建立软件系统的可视化FSM模型,并能由该模型产生有效的测试用例。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 一致性测试
• 1.2 形式规格说明
• 1.2.1 约束逻辑程序
• 1.2.2 有限状态机
• 1.2.3 标签迁移系统
• 1.3 测试覆盖准则
• 1.4 成就与挑战
• 1.5 本文的主要研究内容
• 第2章 基于FSM 的测试理论与实现
• 2.1 一致性测试的假设
• 2.2 状态和迁移覆盖
• 2.3 W 方法与Wp 方法
• 2.3.1 P 集与W 集
• 2.3.2 W 方法的例子
• 2.3.3 Wp 方法
• 2.3.4 Wp 方法的例子
• 2.4 UIO 方法与DS 方法
• 2.4.1 UIO 方法
• 2.4.2 DS 方法
• 2.5 其它方法
• 2.6 小结
• 第3章 两个改进算法
• 3.1 BTF 算法
• 3.2 BDF 算法
• 3.3 实验评估
• 3.3.1 P 集算法的比较
• 3.3.2 W 集算法的比较
• 3.3.3 W 集的评估
• 3.3.4 实验结论
• 3.4 小结
• 第4章 有限状态机的最小测试成本迁移覆盖准则
• 4.1 引言
• 4.2 案例动机
• 4.3 迁移覆盖
• 4.4 必要条件和优化迁移覆盖算法
• 4.4.1 必要条件
• 4.4.2 优化迁移覆盖算法
• 4.4.3 例子
• 4.5 充分条件和最小测试成本迁移覆盖算法
• 4.5.1 充分条件
• 4.5.2 最小测试成本迁移覆盖算法
• 4.5.3 例子
• 4.5.4 有效性讨论
• 4.6 实验对比
• 4.6.1 实验环境
• 4.6.2 实验对象
• 4.6.3 实验方法
• 4.6.4 错误探测能力的讨论
• 4.6.5 实验结果及评估
• 4.6.6 实验有效性讨论
• 4.7 相关工作比较
• 4.7.1 测试覆盖准则
• 4.7.2 组合爆炸问题
• 4.8 小结
• 第5章 基于正则表达式分解的自动测试生成
• 5.1 引言
• 5.2 案例动机
• 5.3 基于正则表达式的测试生成
• 5.4 正则表达式的分解
• 5.5 实现
• 5.5.1 理论基础
• 5.5.2 案例研究
• 5.5.3 DSIM 算法
• 5.5.4 测试输入生成
• 5.6 自动支持工具
• 5.7 相关工作
• 5.8 小结
• 第6章 冗余约简
• 6.1 引言
• 6.2 测试集的冗余约简方法
• 6.2.1 贪婪启发式G 算法
• 6.2.2 启发式HGS 算法
• 6.2.3 启发式GRE 算法
• 6.2.4 模拟退火算法和遗传算法
• 6.2.5 ILP 模型
• 6.2.6 效率分析
• 6.3 预备知识
• 6.4 冗余类型和约简规则
• 6.5 测试片段的有效性
• 6.6 自动冗余约简算法
• 6.7 案例研究
• 6.8 小结
• 第7章 测试用例生成
• 7.1 引言
• 7.2 案例动机
• 7.3 逻辑覆盖
• 7.3.1 语句覆盖
• 7.3.2 判断覆盖
• 7.3.3 条件覆盖
• 7.3.4 条件-判断覆盖
• 7.3.5 条件组合覆盖
• 7.3.6 路径覆盖
• 7.3.7 BRO
• 7.3.8 比较
• 7.4 测试用例的评估
• 7.5 TTJ 覆盖准则
• 7.5.1 TTJ 覆盖准则的原理
• 7.5.2 TTJ 覆盖准则的应用
• 7.5.3 算法步骤
• 7.6 小结
• 第8章 工具的设计与实现
• 8.1 工具概述
• 8.2 状态图
• 8.3 XMI 解析器
• 8.4 XML 管理器
• 8.5 可视化FSM
• 8.6 存储结构与序列生成
• 8.7 测试用例生成
• 8.8 小结
• 第9章 结束语
• 9.1 主要贡献
• 9.2 将来的工作
• 参考文献
• 作者在攻读博士学位期间发表的论文
• 作者在攻读博士学位期间参与的科研项目
• 致谢