基于符号执行的自动测试案例生成工具的研究与设计

摘要

软件测试是提高软件可靠性、确保软件质量的重要手段，在软件测试的各类方法中，测试案例占着举足轻重的位置。本文主要针对在软件测试过程中快速地生成高覆盖度的测试案例集进行了研究，涉及到的关键技术包括符号执行技术和满足性模理论，前者在测试案例生成中主要用于实现自动地构造出在被测试的程序中所具有的执行路径，并且其所构造的路径具有无冗余性的特点；后者主要用于为符号执行技术构造的路径生成对应的真实测试案例输入，由于前者构造的路径是无冗余的，因此所生成的测试案例集也是无冗余的，所以在与传统冗余测试案例集相比而言可以在各种覆盖标准中获得更高的覆盖率。下面是四个本文主要的本文的研究和设计实现内容：
　　第一，系统地研究了符号执行的技术背景、发展历史、研究现状、技术原理和面临的问题，对现有的6款动态符号执行工具进行了详细研究，并统计了领域中比较出名的多款动态符号执行工具，并对它们进行了对比分析。
　　第二，对满足性模理论（SMT：Satisfiability Modulo Theories）求解技术进行了研究，总结分析目前使用较为广泛的约束求解器，详细研究了由SMT-LIB组织提供的所有SMT求解器都能够解析的通用语言的语法规则和脚本编写，为后文进行约束求解优化打下理论基础。
　　第三，对各主流的动态符号执行工具的实现机制和架构进行了总结，为了实现为运行在不同平台的程序自动生成测试案例，设计实现了基于C/S模式的测试案例生成工具，其能够在不影响测试案例生成部分实现的基础上，提供多用户多平台的测试案例生成服务。
　　第四，在第一和第二个研究的基础上，提出了针对路径爆炸问题和约束求解问题的解决方案，针对约束求解，设计实现通用的求解器调用接口，用以方便地扩展和调用不同的求解器，针对路径爆炸问题，设计实现了多种智能搜索策略用以获得高分支覆盖，同时还设计实现了并行机制用以提高测试案例生成工具的效率。
　　根据以上的研究内容，本文最终设计并实现了基于符号执行的自动测试案例生成工具AUTCS，AUTCS能够同时为多个用户提供自动测试案例生成远程服务，能够提供多种智能覆盖标准，并且针对自身架构缺陷和符号执行技术面临的问题实现优化解决方案。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1研究的背景与意义

1.2国内外研究现状

1.3研究的主要内容与贡献

1.4文章组织结构

第二章 背景技术介绍

2.1符号执行技术

2.2 SMT求解技术

2.3本章小结

第三章 基于符号执行的自动测试案例生成工具设计与实现

3.1总体框架设计

3.2测试案例自动生成流程

3.3 AUTCS的设计与实现

3.4实验及分析

3.5本章小结

第四章 SMT求解器适配接口优化约束求解

4.1 SMT-LIB标准语言和SMT求解器

4.2求解器适配接口设计

4.3求解器适配接口实现

4.4本章小结

第五章 智能覆盖策略缓解路径爆炸问题

5.1软件度量

5.2基本搜索策略

5.3基于随机搜索与深度优先搜索结合之快速分支覆盖

5.4基于CFG图的深度优先搜索策略

5.5本章小结

第六章 并行技术提升测试案例生成工具性能

6.1并行处理技术

6.2并行搜索策略

6.3并行求解技术

6.4实验及分析

6.5本章小结

第七章 总结与展望

7.1总结

7.2展望

致谢

参考文献

攻读硕士学位期间取得的成果