论文部分内容阅读
如何生成高质量的测试用例一直是软件测试领域的重要研究课题。不同于其他测试用例生成技术,基于符号执行的测试用例自动生成技术在程序执行的过程中使用符号化的变量代替具体值的变量,同时维护整个执行过程中的路径约束,当遇到分支语句的时候即调用底层的约束求解器求解该路径约束以生成触发该分支路径的测试用例。该技术经过多年发展已经被应用到了诸多测试工具,比如jCUTE,KLEE和SPF等。当前基于符号执行的测试用例生成技术在应用到真实程序时仍然面临着不少的挑战。其中一个最主要的挑战就是底层约束求解器无法对真实程序中的复杂路径约束提供有效支持。造成这个问题主要有两个方面的原因:一是真实程序中存在着大量复杂的数值计算,包括非线性数值计算,常见的数学函数的计算等,现有的约束求解器对这类约束很难提供有效支持;二是真实程序中存在着大量的函数调用,现有的约束求解器通常只提供纯数学表达式形式的约束支持,在函数具体实现细节无法得知的情况下,约束求解器很难对这类包含函数调用的路径约束进行求解。为了解决以上两个方面的问题,提高符号执行技术应用在真实程序的效率,本文的主要工作如下:·基于机器学习约束求解的符号执行框架。不同于传统的符号执行框架,本文提出了一种新的基于机器学习的符号执行框架——MLBSE。MLBSE与传统符号执行框架最显著的区别就是底层约束求解技术。针对复杂路径约束,MLBSE首先借助约束不满足程度将路径约束的满足性问题转化为优化问题,然后使用基于机器学习的优化算法RACOS对路径约束进行求解。借助于这种基于机器学习的约束求解方法的优势,MLBSE能够更好地支持包含大量复杂数值计算和函数调用的真实程序。·基于MLBSE的符号执行功能增强。在已有的基于机器学习约束求解的符号执行框架MLBSE的基础上,为了进一步增强MLBSE符号执行功能,本文做了包括黑盒执行模式,可解置信度报告和基于可解置信度报告的搜索策略三个方面的功能拓展。借助黑盒执行模式,MLBSE能更加高效地处理包含函数调用的真实程序。通过引入可解置信度报告,MLBSE能够在计算资源有限的情况下为用户提供额外参考,帮助用户判断是否需要投入更多计算资源在求解失败的路径约束上。除此以外,MLBSE还提供了一种基于可解置信度报告的搜索策略。基于该策略,MLBSE能自动为求解失败且可解置信度高的路径约束投入更多的计算资源,从而在不影响整体效率的前提下提高符号执行的效果。·实现和实验。在开源符号执行引擎SPF的基础上,本文完整地实现了基于机器学习约束求解的符号执行工具MLB。为了验证MLB在真实程序上执行的效果和效率,本文选择了 19个真实使用的程序作为测试程序,并同4个基于符号执行的测试用例自动生成工具做了严格的对比实验。实验表明,MLB在效率、稳定性和生成测试用例的质量上都有着更好的表现。除此之外,本文还针对MLB的三个拓展功能做了一系列的实验。实验表明,MLB提供的可解置信度报告是具有参考价值的,同时黑盒执行模式和基于可解置信度报告的搜索策略能进一步增强符号执行的功能。