基于懒符号执行的软件脆弱性路径求解算法

Software Vulnerable Trace's Solving Algorithm Based on Lazy Symbolic Execution

为了解决软件测试中路径爆炸、新路径发现率低以及静态分析中虚报率高等问题,提出了动静态分析结合的脆弱性挖掘框架,并针对循环爆炸问题设计了基于懒符号执行的路径求解算法,该路径求解算法应用最短路径、条件约束集概率和可达路径数量3种静态信息制导符号执行,提高了路径选择的准确率,能较快地逼近脆弱点,并利用懒符号执行技术自动识别循环结构,通过推迟变量实例化等方法,有效地缓解了循环结构的路径组合爆炸问题,最终生成到达脆弱点集的数据包.对coreutils6.10命令包的实验结果表明,与现有的方法 KLEE、Otter和SAGE相比,该文提出的方法可以有效地对具有较多分支的程序进行分析,当测试程序越大其优势越明显.

To solve path explosion,low rate of new path＇s finding in the software testing and high rate of false alarm of static analysis,this paper proposes a vulnerability discovering architecture which combined dynamic analysis and static analysis,and design the trace solving algorithm based on lazy symbolic execution for the problem of loop explosion.This trace solving algorithm applies3 key factors consisting of shortest path,constraint probability and reachable trace number to guide the symbolic execution which can reach the vulnerability faster with the more accuracy of trace choosing.Through the lazy symbolic execution to automatically identify the loop structure and delay the variables＇ concreting,we can fit the problem of trace combination explosion of loop structure efficiently and get the test cases which can reach the vulnerability sets.Our algorithm is also tested on coreutils6.10 and compared with KLEE,Otter and SAGE.The experiment result shows that our algorithm can analyze the program containing more branches effectively,and the larger testing program is,the more obvious advantage it has.