论文部分内容阅读
计算机网络的普及使人类的生活发生了翻天覆地的变化,但随之带来的安全问题也对人们的生活和工作造成了极大的影响。软件漏洞检测技术是软件安全的重要保障,传统的人工静态检测技术早已不能满足人们迫切的需求,而自动化的Fuzzing测试技术由于其自身固有的缺陷,也不能满足现在软件测试精确、全面的检测需求。符号执行技术早在上世纪70年代已被提出以来,并在近年重新崛起,已逐步发展成为一种重要的自动化软件测试手段。动态符号执行能自动生成被测软件所有可执行路径对应的测试用例,不需要人工开销,同时消除了Fuzzing测试的随机性,是现今最具前景的软件漏洞检测技术之一。目前有众多专家在对动态符号执行进行深入的研究,并且开发出的工具在实践中已取得了显著的成绩。但是,动态符号执行技术还存在一些亟待解决的问题,如约束求解、浮点指针计算、路径爆炸等,其中路径爆炸是动态符号执行应用于大中型软件测试的发展瓶颈。受路径爆炸的影响,动态符号执行工具在有效的时间资源内只能完成小部分可行路径的测试,代码覆盖率极低,严重影响其执行性能。而目前针对路径爆炸的解决方案都不能有效的提高代码覆盖率。本课题通过对动态符号执行技术进行深入的研究,从驱动算法入手,针对路径爆炸问题提出一种新的路径选择算法,能够用尽量少的测试用例获取最高的代码覆盖率,以达到提升动态符号执行的执行性能的目的。该算法利用被测程序对应的静态全局超级块支配图来控制符号执行的路径选择,使其每次选择的路径最少能覆盖的基本块最多。全局超级块支配图由被测程序的控制流图和函数调用关系图根据支配关系理论转化而来。此外,为验证算法的有效性,课题实现了一个功能完善的动态符号执行的原型系统DDse(Domination based Dynamic SymbolicExecution)。DDse采用Valgrind作为插桩和漏洞检测工具,采用Stp作为约束条件求解器,并在其框架上实现了包括超级支配图算法在内的六种路径选择算法。最后,在DDse上对Linux平台下的多个开源大中型软件进行测试,通过测试数据对比证明本课题提出的算法有效性。与现有的驱动算法相比,能用更少的时间覆盖更多的基本块,有效的提升动态符号执行的性能。