软件质量是软件的生命,它直接影响着软件的使用和维护。软件测试是保证软件质量的重要手段,也是软件开发流程不可或缺的环节,用来检验软件是否满足规定的需求或者检验预期结果与实际结果是否相符。符号执行可以用来查找程序缺陷、生成测试用例、验证程序正确性等。针对符号执行面临的路径爆炸和约束求解问题,本文研究提升符号执行效率的方法。主要工作包括:(1)提出了冗余路径的消除方法。在软件测试中,探索更多的路径不一定会揭示更多的程序行为。如果在路径中展示的程序行为已经被其它先前探索过的路径表现,则这样的路径是多余的,不需要进行探索。基于此,本文提出了一种通过符号价值概念实现路径缩减的方法,此外针对控制依赖、数据依赖和潜在依赖的不足,引入一种称为交互依赖的新型依赖关系。实验结果表明,冗余路径消除的方法与传统符号执行相比,探索了6.69%-96.57%的路径,实现了1.02-49.56倍的加速。(2)提出了基于蚁群算法的路径搜索策略。猜测符号执行的核心思想是猜测,由于猜测失败时需要进行回溯,降低猜测符号执行的效率,所以猜测的成功率高低是影响整体效率的关键。基于蚁群算法的路径搜索策略,以分支路径的可行性大小为信息素,路径搜索时选择信息素量大的分支方向进行猜测,并在搜索后动态更新分支的可行性(权重)。实验结果表明,基于蚁群算法的路径搜索策略明显减少了路径搜索时间和约束求解时间。(3)改进了传统的集中式调度策略,并使用负载均衡技术共同提升并行符号执行的效率。集中式调度明显的缺点是节点间频繁的通信会导致中心节点繁忙,工作节点出现空闲,影响并行效率。为了解决这个问题,本文增加了缓冲区来存储任务队列,解决任务分发和处理速度不一致的问题,减少工作节点的空闲时间。同时,使用最小任务队列算法来保证各个任务队列长度基本相等,各工作节点负载均衡。实验表明,设置了任务队列的集中式调度,对比传统的集中式调度,能再提高1倍左右的速度。