关键词:
符号执行
负载均衡
约束求解
并行加速
可扩展性
摘要:
符号执行作为一种高效的测试生成技术,被广泛应用于软件测试、安全分析等领域.然而,由于程序中的执行路径数量随着分支数量的增加而指数级上升,符号执行往往无法在大规模程序上进行高效执行,缺乏可扩展性.已有的基于多进程的并行化方法具有较大的额外通信开销,并且缺乏对现有约束求解优化技术的利用.提出了基于多线程并行处理模型的符号执行加速方法.具体来讲,为解决并行符号执行中的不同工作节点负载不平衡问题,设计了不需要中间节点参与的工作窃取算法.为充分利用现有约束求解优化技术,提出了让不同工作节点共享约束求解信息的加速求解方法.基于符号执行引擎(KLEE)实现了多线程并行化符号执行方案,从而形成多线程并行化符号执行引擎(PKLEE).实验验证表明,在穷尽执行路径场景下,KLEE平均耗时是在给定8个线程下PKLEE的3~4倍;在同样的时间内,PKLEE执行的有效工作负载平均是KLEE的3倍.