中国工程论文网
代写工程论文
当前位置:工程论文网 > 软件工程论文 > 基于符号化执行的测试用例自动生成方法软件工程研究

基于符号化执行的测试用例自动生成方法软件工程研究

时间:2018-11-13 15:38来源:www.e-lunwen.com 作者:lgg 点击:
本文是一篇软件工程论文,软件系统能最有效的利用计算机的时间和空间资源。各种软件无不把系统的时/空开销作为衡量软件质量的一项重要技术指标。
本文是一篇软件工程论文,软件系统能最有效的利用计算机的时间和空间资源。各种软件无不把系统的时/空开销作为衡量软件质量的一项重要技术指标。很多场合,在追求时间有效性和空间有效性时会发生矛盾,这时不得不牺牲时间有效性换取空间有效性或牺牲空间有效性换取时间有效性。时/空折衷是经常采用的技巧。(以上内容来自百度百科)今天为大家推荐一篇软件工程论文,供大家参考。
 
1绪论
 
1.1研究的背景与意义
这是一个信息化,智能化的时代,智慧医疗,移动支付,网购,无人驾驶,无人机表演,智慧城市等高度信息化的技术和产品走近人们的视野[1]。这些高科技的背后不光有高质量的硬件,软件也是不可缺少的,如果把硬件当做骨骼,那么软件就好比肌肉和血液,渗透到每一件产品中,保障开发的软件可靠平稳运行其中就需要软件测试。软件漏洞问题事件经常报道,2016 年 2 月某银行软件出现漏洞,一些不法人员利用此漏洞非法获利 40余万元。2017 年 2 月某金融信息服务公司一款理财 App 出现漏洞被违法人员利用,涉案者多达百人,涉案金额高达千万。2018 年 1 月 office 软件出现漏洞,利用此漏洞可以控制受感染电脑[2]。这样的例子不胜枚举,总之,软件漏洞问题日益凸显,软件测试的重要性不言而喻,而测试用例的质量又会影响整个软件测试。目前测试用例生成技术逐渐成熟,但在许多中小公司软件测试还是大量依靠手工进行,这势必会降低工作效率,因此研究测试用例自动化生成技术有一定现实意义[3]。测试用例生成方法有随机法、基于搜索、形式化的方法等,这些方法存在覆盖率及执行效率不高,有大量冗余无效用例的问题,对于一些结构复杂程序生成的测试用例质量有限[4]。传统软件测试中的符号执行虽然能够生成覆盖更多路径的测试用例,但是难处理复杂动态数据,因此利用动态符号执行生成测试用例就显得尤为重要,本研究的目的是在程序执行时进行符号执行,收集约束后调用约束求解器求解后生成的测试用例基本上都是有效的,从而避免大量无效测试用例,但是由于路径数量庞大,一部分路径具有相似性,并且会有部分未覆盖的路径。因此本文拟通过对源码进行插桩,然后对符号执行树遍历策略进行设计,利用程序静态分析和函数之间调用关系进行代码二次覆盖,同时设计相似路径预测剪枝方法,这样使生成测试用例可以降低路径膨胀风险,同时又有较高覆盖度,这些方法通过实验验证对生成测试用例的效率和质量有一定的提升作用。
........
 
1.2国内外研究现状综述
 
1.2.1形式化测试用例生成
形式化执行就是通常说的符号执行技术,这里面包括静态符号执行技术和动态符号执行技术,符号执行最先在上世纪 70 年代提出[5],最初是对源代码进行静态分析,利用符号值代替变量,经过一段时间的发展,又提出动态符号执行技术,以符号执行作为技术基础,微软的高级工程师在相关论文中对动态符号执行技术进行定义,在他的论文中对工具DART[6](全称 Diagnostics and Recovery Toolset,诊断和恢复工具集)进行描述,其中包括三种方法:第一是对源码进行静态分析,实现了环境交互。第二是随机生成模拟数据,目的是为了与外部环境交互。第三,通过不同的测试数据进入不同路径。总体就是包括:代码插桩、符号化模拟执行、路径求解。上述 DART 后来经过一定的改进,加入了函数摘要用来缓解路径膨胀问题,由于摘要函数获取的方法导致实际效果不够理想。同时该工具对于非整形约束值测试效果不够理想,DRAT 中处理约束冲突并将具体值和符号结合的方法对于符号执行技术有重要意义[7],后来微软公司的开发者与加州大学研究者提出白盒模糊测试理论,随后在 SAGE[8]软件(全称 SAGESOFT 赛捷是全球第三大管理软件及解决方案专业提供商)中利用这一理论,同时包含符号执行技术,具体做法是:开始利用随机数执行程序,同时符号化变量信息,进行路径约束收集,然后对获取到的路径条件选择性取反,最后调用求解器对约束条件求解,约束求解器使用的是微软的 Z3 求解器,在对于比较大的程序进行求解 Z3 有良好的效果[9]。Koushik Sen 与 Dark Marinov 研究了基于单元测试为基础的 CUTE 工具[10](Cute Test 是一个简单的 C 语言单元测试工具),这其中有对指针的动态操作,在进行收集约束的时候会存在路径识别有误,对于这样的约束是不能够确定求解的,针对这样的问题 Koushik Sen 等认为利用逻辑映射输入可以消除上述不确定性。
..........
 
2符号化执行生成测试用例框架与分析
 
符号执行技术是生成测试用例的基础,符号执行和动态符号执行基础理论一致,但符号执行是一种静态程序分析技术,而动态符号执行是在一些无法求解情况下随机生成具体数值来代替符号值,以符号技术理论为理论背景的测试用例生成技术(本文后面提到符号化执行技术即动态符号执行技术)。本章的重点在于:在分析符号执行理论的基础上提出本文完整的执行框架,并对其进行分析说明。
 
2.1符号执行技术
 
2.1.1符号执行技术原理
这里所说的符号执行是指对程序的静态分析技术[41],动态化符号执行技术也是从符号执行发展起来的,一般符号执行有两个状态,SS(Symbol Status)和 PC(Path Conditions),分别是符号状态和路径约束,程序插桩后通过堆栈机模拟程序运行,进入符号执行,对变量进行符号化操作,在执行到条件语句的时候收集该条件约束,执行完一条路径,即利用符号代替了一类输入,因此最终通过约束求解得出的测试用例理论上可以覆盖一类输入,这样反复执行后可以有很高的覆盖率。利用静态符号执行技术可以达到一定的覆盖率[42-43],但是当程序收集到的路径条件约束求解器无法求解的时候会中止执行,这样不利于测试用例生成。相比于传统的静态符号执行技术,动态化符号执行技术采用实际执行和符号执行混合的方式,一开始输入一组具体值启动符号执行[10],此时程序按照输入值实际执行程序,同时也开始进行符号执行,这个过程其实就是根据程序输入构建从内存到符号的映射。程序一开始要对源码进行插桩,插桩后通过分析源码并根据函数调用关系和插桩函数生成程序控制流图信息,这样再进行符号执行就是按照控制流信息进行执行,程序执行到与符号相关变量后进行符号执行,收集分支处路径条件并按一定的遍历方法取反某个约束条件进行约束求解生成测试用例,而这些约束条件就是一组布尔类型的条件表达式,求出的解如果再次执行将会按照符号执行时相同的路径执行。
.......
 
2.2符号化执行生成测试用例的思路与框架
本节主要是在对符号执行技术深入理解基础上总结出本论文符号化执行生成测试用例总框架,思路如下:首先,对源程序进行代码插桩,目的是能够产生程序的静态结构,从而该计算未覆盖代码信息,同时插桩函数收集约束路径信息。其次,设计改进符号执行树遍历算法,并收集路径信息进行路径信息分析,为后文进行路径相似度预测剪枝提供基础。最后,根据插桩处收集的路径和未覆盖代码信息,在符号执行树遍历记录的路径信息基础上进行相似度统计分析,进而预测执行路径舍去一些高相似度的路径,再次进行符号执行时减少了执行路径数,这样通过约束求解生成的测试用例质量更高且高效。作为软件测试常用技术,程序插桩方法是由 J.C.Huang[44]提出,是在待测试程序中间插入一些代码,这些代码有特定的作用,但是插入的代码不会改变原有程序执行情况,目前有源码和二进制插桩两种方式。
.........
 
3 基于 LLVM 的代码插桩方法 ........13
3.1 符号化执行中的插桩策略分析与实现................13
3.2 插桩实验与分析.......20
3.3 本章小结 .......22
4 符号化执行生成测试用例方法 ................23
4.1 基于符号执行树的遍历算法设计与实现 ............23
4.2 约束求解过程...........30
4.2.1 Z3 求解器概述 ..........30
4.2.2 程序路径求解生成测试用例过程..............31
4.3 本章小结........34
5 未覆盖及相似路径剪枝方法..........35
5.1 程序静态分析...........35
5.1.1 函数过程间控制流分析.......35
5.1.2 函数调用关系............36
5.2 相似度路径计算 .......37
5.2.1 未覆盖度 ........37
5.2.2 矩阵向量、相似系数...........39
5.3 未覆盖相似路径预测及路径剪枝方法设计.........42
5.4 本章小结........44
 
5未覆盖及相似路径剪枝方法
 
本章主要针对源程序插桩后利用插桩信息再对程序进行静态分析,进而确定未覆盖代码,同时设计未覆盖代码测试用例生成方法,使离覆盖最近的有函数调用关系且未覆盖代码进行再次覆盖,接下来又提出对于遍历符号执行树后利用摘要函数保存路径信息,设计相似路径剪枝方法,本方法利用路径矩阵向量,计算相似系数,在对存储的路径进行一定计算和分析后预测执行路径趋势,对于相似系数高的路径进行排序,在执行的时候不予执行相似度高的路径,这样避免执行过多测试路径,进一步提升了路径覆盖率,同时也减少再次执行时路径太多导致路径膨胀。
 
5.1程序静态分析
控制流图信息是软件测试中程序分析的一种手段,利用控制流图可以直观的看到程序执行的大体走向,能反应出程序的执行顺序。本文是借助 LLVM 编译工具生成控制流图,分析完程序结构最后可以通过 Graphviz 工具来转换成 CFG(程序控制流图)可视化图形,方便更直观的分析,图 5-1 是第三章插桩代码的 CFG 图:图 5-1 所示控制流图就是在对源程序进行词法语法分析插桩的基础上构造的 AST(抽象语法树),通过 AST 利用 Graphviz 构造程序的控制流图,通过控制流图信息的分析可以得出程序的函数调用关系,以及对代码的未覆盖情况进行计算分析。本节是在生成控制流图基础上,确定函数之间的调用关系,通过第三章插桩对代码执行情况的记录,计算和分析未覆盖代码的情况。由于函数之间存在调用关系,所以通过一个函数间的调用图和插桩后对应图来分析,目的是为了计算未覆盖分支情况和预测待执行路径信息(本例以一个开发过的电信系统程序为例说明)。
.......
 
总结
 
本文在进行了一定的文献资料查阅和阅读的基础上,对生成测试用例方法进行总结,指出各测试用例生成技术存在的缺陷和不足,进而确定本课题所研究的方向,即符号化执行下的测试用例自动生成,对比其他技术,符号执行生成测试用例能够在一定程度上避免冗余测试用例的产生,因为符号执行是用符号执行代替实际值模拟运行程序,而且在复杂路径处利用实际值代替符号值,这样生成的测试用例有效性更强。但是符号执行也有局限性,那就是路径爆炸,冗余相似路径产生,以及路径覆盖不够全面,本文就是基于以上局限进而确定研究突破点,基于此本文主要研究工作如下:
(1)首先研究程序插桩。选择合适的位置插入桩函数,目的是收集路径信息,启动符号执行进行,通过收集到的信息为后面未覆盖代码块再次覆盖打下基础,同时设计实现了自动化插桩程序,使测试效率更加高效。
(2)针对符号执行树遍历算法进行设计和改进,目的是能够更多的覆盖路径。同时收集路径约束信息,在设计算法时利用了随机遍历的快捷性,同时将深度搜索的优点结合进来,这样可以达到在一定的区域内覆盖多的路径,本算法还将摘要函数思想引进,目的是保存程序的路径信息,为后续进行剪枝策略提供基础。
(3)在程序插桩基础上根据函数调用关系和控制流图信息,计算出未覆盖代码信息进行二次覆盖,同时利用摘要保存的路径信息进行相似度路径预测分析,进而对相似度高的一类路径进行排序,在下次执行的时候只选择其中部分路径进行执行,这样可以避免执行路径过多,同时可以提升求解效率。
(4)根据本研究的算法策略实现基于符号执行的验证性测试用例生成工具(主要来验证本文方法效果,稳定性和实用性需要进一步改进),在进行试验后分析得出,本研究方法的改进和实现在一定程度上提高了代码覆盖率,利用更少的测试用例覆盖更多测试路径,同时,对于解决路径膨胀也有一定作用。
..........
参考文献(略)
(责任编辑:gufeng)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
发表评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
栏目列表
点击提交代写需求
点击提交代写需求
点击提交代写需求
推荐内容