| 题名 | 基于约束的测试用例生成中可扩展性问题研究 |
| 作者 | 王轶 |
| 学位类别 | 博士 |
| 答辩日期 | 2013-05-24 |
| 授予单位 | 中国科学院大学 |
| 授予地点 | 北京 |
| 导师 | 蒋同海 |
| 关键词 | 符号执行 约束求解 可扩展性问题 中间计算结果重用 |
| 学位专业 | 计算机应用 |
| 中文摘要 | 软件测试作为保证软件质量的重要手段，一直是计算机工程领域科学界关注的一个重要问题，已经成为软件生命周期中的重要组成部分。其中测试用例的设计与生成 是决定软件测试效果的重要因素之一。基于约束的测试用例生成是一种基于符号执行与约束求解技术的形式化方法，能够生成高覆盖、无冗余的测试用例集。这一方 式是当前被广泛认可的一种测试用例自动生成方法，也是大多数现有测试用例自动生成工具的底层技术。但其仍然受到可扩展性等问题困扰，使其实际应用受到极大 限制。本文针对这一技术面临的可扩展性问题，提出了两项优化策略来提高用例生成的效率：1.共享的解匹配策略（Shared Solution Matching Strategy，SSM）昂贵的约束求解开销是引发测试用例生成中可扩展性问题的重要原因，复杂的路径条件表达式和用例生成过程中频繁的求解器调用也加 剧了这一现象。共享的解匹配策略使用一种中间计算结果的重用机制，来降低约束求解的开销，提高测试用例生成效率。SSM通过对符号执行中路径可行性验证过 程进行分析，将本应被抛弃的中间计算结果转化为测试路径的潜在解，用简单约束的可满足性匹配代替对整个路径条件的约束求解过程，降低测试路径可满足性验证 过程的时间开销。同时在符号执行的搜索过程中对潜在解进行传递和迁移，保证每一个潜在解都能够到达程序出口。这一过程实现了对表示路径条件的SMT表达式 优化，能够通过对不完整的路径条件求解获得最终的测试路径，并能够帮助符号执行提高应对复杂约束条件的能力。最终将两者结合构成共享的解匹配策略，完全消 除了不必要的约束求解调用，使符号执行过程中对求解器的调用次数仅为可行路径与约束冲突的和，有效的降低了测试用例生成中约束求解的开销。2.跳步的循环 边界覆盖策略（Jumping Boundary Coverage Strategy，JBC）在符号执行中，循环结构往往带来大量的测试路径和求解器调用，导致严重可扩展性问题。本文借鉴已经在业界广泛使用的手工白盒测 试中对循环结构的处理方式，提出一种跳步的循环边界覆盖策略来缓解这一问题。这一策略的实现分为两个过程：在搜索过程中对循环结构的探测和对非关键路径的 剪枝。本文通过对编译后循环结构的分析，提出了一种符号执行过程中循环结构的探测模型，能够在运行时同步的识别出被测代码的循环结构。然后应用共享的解匹 配策略，减少约束求解器调用次数，并且能够避免在循环入口处对因跳出循环导致的不可行路径进行约束求解验证，降低循环覆盖测试过程中的时间开销。最后提供 一种灵活的跳步剪枝策略来削减非关键路径，能够给测试人员提供更多的选择，在测试有效性和测试效率之间依照实际情况作出权衡。最后，本文以NASA的开源 项目SPF(Symbolic PathFinder)为基线系统，对上述两项优化策略进行评估。与SPF相比，SSM能够减少测试用例生成过程中约60%的约束求解器调用次数，降低约 30%的约束求解时间开销，极大的缓解了约束求解过程带来的可扩展性问题。在对循环结构进行覆盖测试时，JBC优化策略能够减少一部分对不可行路径的约束 求解判定次数，在本文中的例子中降低了至少20%的时间开销。配合灵活的跳步剪枝策略后，可以让测试人员依据测试任务的需求大量的削减循环结构产生的非关 键路径。 |
| 英文摘要 | As an important means to ensure software quality, software testing has become an important part of the software life cycle. It has been an important issue of concern by the scientific community in the field of Computer Engineering. Test case generation is one of the important factors to determine the effect of software testing.Constraint-based test casegeneration is a formal method based on symbolic execution and constraint solving technology, capable of generating high-coverage and non-redundant set of test cases automatically. This is a widely recognized automatic test case generation method, as well as the underlying technology of most existing automatic test case generation tools. However, it still suffers from scalability problems and be limited in practice. |
| 公开日期 | 2013-05-31 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.xjipc.cas.cn/handle/365002/2467]  |
| 专题 | 新疆理化技术研究所_多语种信息技术研究室 |
| 作者单位 | 中国科学院新疆理化技术研究所 |
| 推荐引用方式 GB/T 7714 | 王轶. 基于约束的测试用例生成中可扩展性问题研究[D]. 北京. 中国科学院大学. 2013. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论