基于求解开销预测的符号执行搜索策略研究

摘要：

符号执行中约束求解所占的时间比例非常高．同时，不同复杂度约束的求解时间开销差距悬殊，这一现象在对包含复杂数值计算的程序进行符号执行时尤为明显．在指定时间内求解更多约束有利于覆盖更多语句和探索更多路径．为此，提出了基于求解开销预测的符号执行搜索策略．基于实验总结出了度量约束复杂度的经验公式，并结合约束的历史求解开销来预测当前的求解开销，从而在符号执行过程中优先探索求解开销较小的路径．在 KLEE 中实现了上述搜索策略，并对 GNU 科学计算库（GSL ）中的12个模块进行了实验．实验结果表明，相比现有搜索策略，提出的搜索策略在保证语句覆盖率的同时，可以探索更多的路径（平均24．34％提高）；而且，在相同时间内，可以查找出更多的软件缺陷，同时查找出相同缺陷的时间开销平均降低了44．43％．

关键词：符号执行、约束求解、加权随机搜索、缺陷查找、语句覆盖

所属期刊栏目：53

分类号：TP311(计算技术、计算机技术)

资助基金：国家“九七三”重点基础研究计划基金项目2014CB340703；国家自然科学基金项目61120106006，61472440，61272140 This work was supported by the National Basic Research Program of China 973 Program 2014CB340703;the National Natural Science Foundation of China 61120106006，61472440，61272140．

在线出版日期：2016-06-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1086-1094