基于前向探针的符号执行路径搜索算法  

Path Search Algorithm for Symbolic Execution Based on Forward Probe

作　　者：柳晓龙 武泽慧 魏强[1] 王允超[1] LIU Xiaolong;WU Zehui;WEI Qiang;WANG Yunchao(Information Engineering University,Zhengzhou 450001,China)

机构地区：[1]信息工程大学,河南郑州450001

出　　处：《信息工程大学学报》2019年第4期427-431,共5页Journal of Information Engineering University

基　　金：国家重点研发计划资助项目(2017YFB0802901)。

摘　　要：Driller利用符号执行技术辅助模糊测试工具绕过复杂检查,有效提高测试覆盖率。为减少路径数量,Driller的符号执行路径选择算法对于不能立即产生新的状态转移的分支点不翻转,不约束求解。有些分支点,例如循环结构内的分支点,虽然被翻转后并不能立即产生新的状态转移,但是可能间接影响后续的状态转移。设计基于前向探针的符号执行路径搜索算法FB-SA,即向前符号执行若干步来探测分支点附近是否存在新的状态转移。若存在新的状态转移,则翻转该分支点。实验数据表明,FB-SA算法可以快速提高覆盖率。Driller uses the symbolic execution technique to assist the fuzzing test tool in bypassing complex checks,thus effectively improving test coverage.In order to reduce the number of paths,Driller’s symbolic execution path selection algorithm does not flip the branch points that cannot immediately generate a new state transition,nor does it solve the constraints.Some branch points,such as branch points within a loop structure,do not immediately generate new state transitions after being flipped,but may indirectly affect subsequent state transitions.A path search algorithm FB-SA for the symbolic execution based on the forward probe is designed,which symbolically performs several steps to detect if there is a new state transition near the branch point.If there is a new state transition,the branch point will be flipped.Experimental data shows that the FB-SA algorithm can quickly improve coverage.

关 键 词：符号执行 覆盖率 前向探针 状态转移 

分 类 号：TN918.1[电子电信—通信与信息系统] O157.4[电子电信—信息与通信工程]