符号执行结合随机方法.ppt

1、院系：软件学院,答辩人：屈媛媛,指导老师：洪 玫,专业：软件工程,毕业答辩,面向对象软件的单元测试用例生成方法,目录,Contents,研究背景及意义,1,论文主要工作,2,研究方法,3,计量分析结果,4,5,文献综述结果,6,讨论,7,总结,1.1研究背景,研究背景及意义,论文主要工作,研究方法,计量分析结果,双击添加标题文字,软件测试是保证软件质量的有效手段，单元测试是测试过程的基础。测试用例的生成方法给自动化单元测试提供了可能。 由于面向对象软件的封装、继承、多态性，其单元测试是针对类和类中方法的测试。针对传统软件的单元测试用例生成方法可能不完全使用于面向对象软件。,1.2研究意义,研究

2、背景及意义,论文主要工作,研究方法,计量分析结果,论文主要关注针对面向对象测试用例生成方法，通过整理分析历年来专家学者对该方面的研究，回答了以下两个问题：（1）面向对象软件的测试用例生成有哪些方法？对比分析了这些方法各自的优缺点。（2）有哪些自动生成针对面向对象软件的单元测试的工具？,2论文主要工作,研究背景及意义,论文主要工作,研究方法,计量分析结果,3.1研究方法,研究背景及意义,论文主要工作,研究方法,计量分析结果,3.2文献数据来源,输入文字,研究背景及意义,论文主要工作,研究方法,计量分析结果,会议,数据库,期刊,搜索引擎,国际会议国内外论文（报告）等,IEEE Digital Li

3、braryCNKI万方学位论文库,GoogleGoogle Scholar, IE EXplore,EISCI,3.3文献检索及筛选原则,研究背景及意义,论文主要工作,研究方法,计量分析结果,2003年1月2013年12月,国际会议、EI、SCI期刊、博士论文,5页以上,关键词、摘要,最终，确定111篇文献作为研究对象。,研究背景及意义,研究方法,论文主要工作,计量分析结果,4.1文献年代分布,文献主要集中在2011年-2012年，说明学术界在这两年间对该问题关注度较高。,研究背景及意义,研究方法,论文主要工作,计量分析结果,4.2文献类型分布,文献集中在会议论文，其中以国际会议论文居多，这与

4、检索和筛选时预定的文献级别标准是相符的。,研究背景及意义,研究方法,论文主要工作,计量分析结果,4.3高被引文献,通过对文献被引用量统计，给出引用量在100以上的文献。图示的几篇文献对该课题参考价值较大。,研究背景及意义,研究方法,论文主要工作,计量分析结果,4.4高产作者统计,在选出的111篇文献对应286位作者中，发文量超过5篇的作者共有4位。，说明他们对该领域研究较为深入，其发表的文献具有一定指导意义。这四位作者分别是Xie Tao(8篇)，Fraser, G.(7篇) Tillmann, NikolaiArcuri, A. (6篇)，Tillmann, Nikolai（5篇）。,研究背

5、景及意义,研究方法,论文主要工作,计量分析结果,4.5研究热点,论文采用关键词词频法、共词分析方法来揭示该领域的研究热点。为此借助了文献统计工具EndNote和文献分析工具Refvize。累计关键词共590个，篇均关键词约5.3个。由图可以看出，从图中可以看出test case generation 最高，跟论文研究的课题一致，也契合了检索策略。,研究背景及意义,研究方法,论文主要工作,计量分析结果,4.5研究热点,借助Refvize文献分析工具，得出关键词共现现频率图（左），方格颜色越深表明词汇共现频率越高。 generation case object-oriented 与genetic

6、coverage program 等共现频次较高，class case generate 与object-oriented program 共现频次较高，说明热点集中在面向对象软件中的类测试、用例生成方法和测试覆盖上。,文献综述结果,总结,讨论,致谢,5.文献综述结果,文献综述结果,总结,讨论,致谢,5.1随机方法,该方法基本思想是在程序输入空间内进行随机的选取，将选取的样本作为测试输入，与相应的测试输出结合即测试用例。通过执行大量的随机测试用例，让程序错误自己暴露出来。随机生成单元测试用例，不需要分析程代码的逻辑、动态结构、函数内部调用这些复杂的程序约束条件，仅分析程序的输入参数结构类型，为

7、输入参数构造随机的测试用例。纯随机方法具有一定的盲目性，目前很多学者都针对纯随机方法做出了一些改进，产生了一些衍生的随机方法，如带反馈的随机、有指导的随机（静态分析、动态分析指导）、规避了传统的纯随机算法的一些缺陷。,文献综述结果,总结,讨论,致谢,5.2符号执行方法,未超过,超过,符号执行方法用符号代替实际值模拟程序执行，从而实现对程序的源代码的分析，是一种静态形式化技术，符号执行与约束求解结合能用于自动生成测试用例。符号执行方法用于生成测试用例的过程中需要先将程序经过词法、语法分析转化为中间语言，用控制流图描述中间语言，符号执行的思想是从控制流图的入口处用符号值代替具体的输入值来模拟程序符

8、号化的执行过程。一个完整的执行框架包括将源程序转化为中间语言的机制、路径遍历算法和约束求解器。遍历控制流图，产生每条路径的约束表达式运用约束求解工具进行求解，能够生成每条路径可满足的解数据集合。,文献综述结果,总结,讨论,致谢,5.2符号执行方法,未超过,超过,使用Soot解析工具在将源程序转化成控制流图时，常会用到程序解析工具，图示为使用Soot解析工具，再利用符号执行生成测试用例。,文献综述结果,总结,讨论,致谢,5.2符号执行方法,未超过,超过,输入,要求解的约束,执行代码时收集到的约束,选择分支,约束求解器,随机选择,文献综述结果,总结,讨论,致谢,5.2符号执行方法,文献综述结果,总

9、结,讨论,致谢,5.2符号执行方法,符号执行结合随机方法,谢涛等人提出的MseqGen方法使用了符号执行结合随机方法生成测试用例。使用符号执行方法转化从代码库中提取的方法序列，即泛化序列，最后将这些单个的序列随机组合在一起，新的方法调用序列易于构造理想的状态对象。,文献综述结果,总结,讨论,致谢,5.3搜索寻优方法,遗传算法,强类型的遗传规划,分布估计算法,文献综述结果,总结,讨论,致谢,5.3搜索寻优方法,进化算法框架,文献综述结果,总结,讨论,致谢,5.3搜索寻优方法,结合JML、JUnit、遗传算法的自动单元测试框架 有学者认为：一个完整的测试用例需要包括测试数据和测试谕示，所以提出了利

10、用JML详细设计，基于遗传算法生成完整的测试用例，该用例能直接用于JUnit平台。,目前有学者提出这两种方法结合生成测试用例，其思想是利用符号执行信息指导搜索寻优产生测试用例方法中适应度函数的构造，以指导进化过程。,文献综述结果,总结,讨论,致谢,5.3搜索寻优方法,谢涛等人提出的EVACON方法框架如下图:,文献综述结果,总结,讨论,致谢,5.4 测试用例生成工具,6.讨论,文献综述结果,讨论,总结,致谢,研究趋势：关注方法的有机结合：随机&符号执行，符号执行&进化寻优,7.总结,文献综述结果,讨论,总结,致谢,文献计量分析。总结了该领域内主流的几类生成方法：随机方法、符号执行方法、进化搜索寻优方法。对比分析了这些方法各自的优劣，需要解决的问题。整理了测试用例自动生成工具。给出了研究热点和未来发展趋势。,答辩人,谢谢观看,洪玫,屈媛媛,指导老师,