程序测试输入的自动生成技术框架及其优化实现

发布时间：2020-11-13 18:19

　　 在软件开发过程中,软件缺陷始终威胁着软件的安全性以及可靠性,并且随着软件规模越发庞大、程序设计越发复杂,这一问题也将变得越发严重。而正因为如此,“测试”作为业界中的主要有效应对手段,也就显得尤为重要。其中,相比较于通过人工方式生成测试输入,“程序测试输入自动生成”在成本方面有着无可比拟的优越性,并且已经被业界广泛投入使用。目前,具备程序测试输入自动生成能力的测试技术种类繁多,包括随机测试、蜕变测试等等。而在所有相关测试技术之中,又以“模糊测试(Fuzzing Testing)”以及“动态符号执行(Dynamic Symbolic Execution)”最为典型、高效,同时彼此之间风格迥异。但是,如何生成高质量的测试输入子集以及如何快速获取目标测试输入,从而最终高效达成程序测试目标,一直都是阻碍程序测试输入自动生成进一步发展的主要难题。截至目前为止,在程序测试输入自动生成研究领域中,已经涌现出了大量的相关技术综述以及技术改进,所有这些相关工作都极大的促进了程序测试输入自动生成的发展。然而可惜的是,直到今天,程序测试输入自动生成依然存在大量问题亟待解决。我们渴望能够在本质上有所突破,从而彻底解决相关问题。但是与此同时,我们也逐渐意识到:如果想要达成这一目标,当下这种在传统理论框架下单纯进行技术改进,已经是远远不够了。所以,我们需要一个全新的、统一的视角,帮助我们理解现有相关工作的特点、优势、劣势,并且以此作为基础,便于我们提出新的程序测试输入自动生成技术。为此,我们开展了如下的主要研究工作:1.我们尝试从搜索空间的角度来理解程序测试输入自动生成,并且以此作为基础,提出了一个基于“邻居关系定义(Neighborhood Definition)”N、“邻居选择策略(Selection Strategy)”以及“初始测试输入集合(Bootstrap Test Inputs)”H0的统一技术框架,记为N,S,H0。这样一个统一技术框架可以包罗目前所有已知的相关技术(包括模糊测试、动态符号执行以及两者技术融合),同时也为我们提供了一个全新的、统一的视角,可以重新省视目前所有相关工作的特点、优势、劣势。2.基于这样一个统一技术框架N,S,H0,我们从定性分析的角度出发,通过开展一份迷你技术调研(调研了模糊测试、动态符号执行以及两者技术融合的29份具有代表性的相关工作),梳理了相关工作的历史发展脉络,与此同时,基于N,S,H0,我们以一个全新的、统一的视角,分析、总结了所有这些相关工作的特点、优势、劣势,并且从中挖掘了具有潜力的未来研究方向。3.基于这样一个统一技术框架N,S,H0,我们从定量分析的角度出发,开展了一份实证研究。在实证研究中,我们使用GNU CoreUtils作为被测程序,使用AFLfast作为模糊测试工具的代表,使用KLEE作为动态符号执行工具的代表。分析了模糊测试以及动态符号执行在现实程序上的代码覆盖表现。同时,基于所统计到的全部142处代码覆盖失败案例,我们总结了“模糊测试/动态符号执行”的代码覆盖失败原因,并且发现:“模拟不充分”占比26%/49%,“算法局限性”占比64%/40%。借此,我们考察了这两项技术间的局限性以及互补性,验证了迷你技术调研中的相关定性结论。4.基于定性分析以及定量分析,我们针对实证研究过程中所发现的AFL中搜索策略的饥饿问题,提出了动态削减低效变异操作的策略,以及基于代码覆盖差异的局部深度优先搜索算法。随后,我们在AFL的基础上进行了相关改进,实现了全新的AFLSU。通过实验,我们发现:AFLSU有效的缓解了饥饿问题,并且在代码覆盖行数方面,相比较于AFL以及AFLfast,AFLSU分别最高提高了40.35%以及36.66%,平均提高了 17.27%以及12.86%。
【学位单位】：南京大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP311.53
【部分图文】：

?第一章绪论??要不充分条件。为了方便阐述其中原理，我们还是先看一个如图１－２所示的代??码案例。??１?ｖｏｉｄ?ｆｕｎｃ（ｃｈａｒ＊?ｓ）?｛??２?ｉｎｔ?ｃｎｔ?＝?０；??３?ｆｏｒ?（ｉｎｔ?ｉ?＝?０；?ｉ?＜?１００；?ｉ＋＋）?｛??４?ｉｆ?（ｓ［ｉ］?＝＝?＇ｘ＇）?｛??５?ｃｎｔ＋＋；??６?｝??７?｝??８?ａｓｓｅｒｔ（ｃｎｔ?！＝?２５）；??９?ｉｆ?（ｃｎｔ?＝＝７５）?｛??ｉ〇?ｂｕｇ?（）；??１１?｝??１２?｝???图１－２：阐述语句全覆盖以及路径全覆盖的程序示例。??与图１－１中的代码案例一样，在当前这个例子中，函数／？ｎｃ的输入是一个??长度为１００的字符串，大小为１００个字节。在这其中：??？如果我们想要触发位于第８行的程序中断，需要满足：在作为输入的１００??个字节当中，有且正好只有２５个单字符’ｘ’。此处，我们将这样一个测试??输入约束记为??鲁如果我们想要触发位于第１０行的错误函数，需要满足：在作为输入的１００??个字节当中，有且正好只有７５个单字符’Ｘ’。此处，我们将这样一个测试??输入约束记为办。??这里可以发现：（：洲办是相互矛盾的。??现在我们己经知道全覆盖从强到弱可以分为：“路径全覆盖（Ｆｕｌｌ?Ｐａｔｈ??Ｃｏｖｅｒａｇｅ）?”、“分支全覆盖（Ｆｕｌｌ?Ｂｒａｎｃｈ?Ｅｄｇｅ?Ｃｏｖｅｒａｇｅ）?”、“语句全覆盖??（Ｆｕｌｌ?Ｓｔａｔｅｍｅｎｔ?Ｃｏｖｅｒａｇｅ）?”。在图１－２所示的代码案例中，我们可以发现：??參当我们达成语句全覆盖的时候

Ｐｏｉｎｔ）?”的两次执行，针对所有后续将会被读取的变量，如果这些变量当前取??值己经相同，那么两者后续路径必然相同，后续符号分析纯属冗余，可以进行??剪枝（状态剪枝原理如图３－１所示）。除了?ＲＷｓｅｔ之外，在ＧＵＩＤＥＳＥ中，用??户向被测程序中插入特殊注释，而ＧＵＩＤＥＳＥ则据此遵循用户意志，有目标的??进行状态合并、路径剪枝。ＭＵＬＴＩＳＥ通过利用状态合并，引导探索方向前往目??标执行路径。??不管如何，状态合并的核心思想是：针对抵达同一程序执行点的两次执??行，如果两者变量状态高度相似，那么两者可以进行合并（如果被判定为等??价），从而剔除冗余、指导搜索（状态合并原理如图３－２所示）。??

＇＇＇??？參。??图３－１：在搜索空间中，状态剪枝原理示意。??图中所有节点代表测试输入，在这其中，黑色节点代表的是目标测试输入，带义号的节点??代表的是那些冗余或者尤价值的测试输入。状态剪枝通过提前剔除这些冗余或者无价值的??测试输入，从而提高邻居选择策略效果。??最后，让我们先回到动态符号执行所面临的挑战。我们现在己经知道，由??于路径约束内部存在依赖关系，后缀约束总是在控制流程上依赖前缀约束。随??意取反某个分支约束，极有可能导致被取反分支约束同前缀约束之间产生矛??盾。最终导致，很多时候，我们很难沿着当前执行路径，通过直接取反目标分??支约束，进入目标分支。另外一边，由于计算资源有限，但是现实程序中的执??行路径总量几乎无限
【相似文献】

相关期刊论文 前10条

1 山磊;;程序测试的心理研究[J];甘肃科技纵横;2006年06期

2 李淑宁;数据流分析在程序测试中的应用[J];小型微型计算机系统;1988年04期

3 黄琳;;符号踪迹测试工具——STTT[J];计算机研究与发展;1989年03期

4 李友仁;刘少英;;COBOL程序测试环境CPTS-1的设计与实现[J];西安交通大学学报;1989年01期

5 刘剑;;重视程序测试 提高软件质量[J];金融电子化;1999年03期

6 陈钢;王能斌;;程序测试与一个程序测试工具[J];南京工学院学报;1983年02期

7 刘远信;程序测试[J];南昌大学学报(理科版);1996年04期

8 赵千川;王达;薛文轩;;PLC程序测试与验证的研究进展[J];清华大学学报(自然科学版);2011年11期

9 黄采伦;RS-485 通讯接口及程序测试方法[J];电子仪器仪表用户;1998年02期

10 郭声;浅谈AXE—10的程序测试系统[J];江苏通信技术;1994年01期

相关硕士学位论文 前10条

1 曹阳;程序测试输入的自动生成技术框架及其优化实现[D];南京大学;2019年

2 王雅楠;基于微信的智慧校园应用[D];西安电子科技大学;2018年

3 胡琰琳;程序正义中的“声音”[D];浙江工商大学;2018年

4 徐文飞;选矿过程自动化逻辑控制程序测试平台的设计与开发[D];东北大学;2015年

5 张超群;选矿过程电气设备逻辑控制程序测试平台的设计与开发[D];东北大学;2014年

6 杨晓光;泵和阀门类设备逻辑控制程序测试平台的研发[D];东北大学;2011年

7 王文军;Java ME程序测试平台的若干关键技术研究[D];大连海事大学;2008年

8 李杜;字符识别技术研究及其在机器视觉测控中的应用[D];江南大学;2011年

9 张新杰;程序切片技术研究及切片方案设计[D];电子科技大学;2017年

10 王大伟;回归测试中基于需求优先级的用例选择算法研究[D];浙江工业大学;2012年

本文编号：2882479