基于抽象内存模型的复杂类型测试用例生成方法研究

With the drastic increasing of the scale and complexity of computer systems, the costs of software development and life and property losses caused by software faults increase correspondingly. Unit testing is an important sector of software testing, and its automatic testing methods and theory are developing in a deeper direction. Due to the dynamic structure and complicated constraint of complex types ,test case generation for them has become a hot spot as well as a difficult point for the academic circle. Starting with the automatic generating of test cases of complex types in software unit testing, this project establishes unified abstract memory models to express the structure and constraints between variables , proposes complete algorithms on different operator semantics, maps actual operator semantics on the operation of abstract memory models so as to analyze statically the change of context circumstances for different program points. With above foundation, the symbolic constraint expressions are extracted, the non-numeric expressions are analyzed and the outline of their test cases constructed, numeric expressions are solved to acquire the values of the numeric domain symbols, and finally test cases are constructed. The successful implementation of this project will facilitate the automation of software unit testing, and improves the efficiency of software testing and software quality.

随着计算机系统的规模和复杂性急剧增加，计算机软件的开发成本以及由于软件故障而造成的生命财产损失也在不断增加，软件测试作为软件质量保证的重要手段越来越受到人们的重视。单元测试作为软件测试过程的重要环节，其自动化测试方法和理论的研究正在向纵深层次发展。复杂数据类型因其结构动态变化、约束关系复杂等特点使其测试用例的生成问题成为目前学术界研究的一大热点和难点。本课题从软件单元测试中复杂类型测试用例的自动生成问题着眼，建立统一的抽象内存模型来静态表示变量之间的结构和约束关系，提出完备的操作语义模拟算法，将实际操作语义映射为对抽象内存的操作，以便精确分析语句的上下文环境。在此基础上，提取路径中的符号约束表达式，分析非数值型约束构造出测试用例的形状，求解数值型约束得出数值域符号的取值，从而构造出测试用例。这一项目的成功实施，将有助于提高软件单元测试的自动化程度，提高软件测试的效率和软件质量水平。

随着计算机系统的规模和复杂性急剧增加，计算机软件的开发成本以及由于软件故障而造成的生命财产损失也在不断增加，软件测试作为软件质量保证的重要手段越来越受到人们的重视。单元测试作为软件测试过程的重要环节，其自动化测试方法和理论的研究正在向纵深层次发展。复杂数据类型因其结构动态变化、约束关系复杂等特点使其测试用例的生成问题成为目前学术界研究的一大热点和难点。.在本项目的资助下，课题组围绕复杂数据类型的测试用例生成问题展开深入研究，主要完成了以下研究内容：（1）基于抽象解释理论，提出一种统一基于区域的符号化三值逻辑RSTVL，全面并精确的分析出各种类型内存对象的存储状态，对于原子符号取值区间，采用扩展区间抽象域的方法，RSTVL的区间及区间上的操作构成一个完备格，基于RSTVL的静态分析可被映射为在格上的操作；（2）基于抽象内存静态表示模型，深入分析了标准C语言中的指针、数组、字符串和结构体类型对象在赋值运算、关系运算、逻辑判断运算等表达式中的模拟操作算法和约束提取规则，提出三个原子操作函数来模拟常见字符串操作相关的库函数语义；（3）借鉴人工智能领域问题解空间搜索的分支限界思想，提出一种新的面向路径的适用于多种变量类型的测试用例生成方法，同时提出了多种加速策略，包括变量动态排序、基于爬山法的回退、基于迭代区间运算的弧一致性判断等；（4）研发了一款面向C语言的代码覆盖测试原型系统，支持标准C语言的各种复杂数据类型，可自动完成对函数单元的语句、分支、MC/DC的覆盖测试，大量实际工程的测试结果表明，本课题的研究成果对于提高单元测试的自动化程度起到了重要的作用。除了完成任务书中的研究内容，申请人在探索过程中进一步扩展研究了与本课题密切相关的支持循环结构的路径生成、面向路径的自适应打桩、代码缺陷检测和测试结果自动确认等问题。.基于上述研究内容，本项目发表学术论文26 篇，其中SCI检索的国际期刊论文5篇，EI/ISTP检索的期刊和国际学术会议论文11篇；新申请国家发明专利10项（其中授权2项），本项目培养了博士研究生5名，硕士研究生10名。