作为一种动态的程序分析技术,动态符号执行凭借高代码覆盖率、自动化计算输入值、分析结果准确等优点,已被广泛应用于软件测试和验证领域。路径搜索是动态符号执行过程中的核心操作,是影响程序动态符号执行效率和代码覆盖率的关键因素。传统的路径深度优先搜索是一种常用的路径搜索策略,但该策略存在一些不足之处:(1)路径空间爆炸问题;(2)可能存在“饥饿路径”;(3)程序检测的代码覆盖率增速缓慢;(4)运行时占用大量存储空间。为了解决传统路径搜索中存在的问题,本文对现有的动态符号执行路径搜索方法进行研究,给出了一种基于控制流图(Control Flow Graph,CFG),结合分支覆盖优先搜索、条件语句优先的随机搜索和路径深度优先搜索的动态符号执行路径搜索策略。本文主要贡献包括以下三点。1.研究了符号执行和动态符号执行的基本理论,以及现有的动态符号执行主流路径搜索方法,提出一种新的动态符号执行路径搜索策略,从四个方面解决传统路径搜索中存在的问题。(1)构造与待检测程序源码的底层虚拟机中间表示(LLVM Intermediate Representation,LLVM-IR)相对应的CFG,以CFG代替符号执行树指导路径搜索,缓解复杂程序中因循环结构和函数递归调用造成的路径空间爆炸问题。(2)综合分支覆盖优先、条件语句优先和路径深度优先的路径搜索方式,设置符号值求解范围,避免程序执行陷入“路径饥饿”状态。(3)在保证动态符号执行高路径覆盖率的前提下,以最少的程序执行次数,获得最大的行覆盖率和分支覆盖率,加快代码覆盖率提升速度。(4)仅存储程序下次执行的输入值及相关信息,相较于存储完整的路径约束,所需存储空间大幅减少。2.设计实现路径搜索模块,并集成LLVM-IR插桩模块,开发了相应的动态符号执行工具,用于对建模、仿真和验证语言(Modeling,Simulation and Verification Language,MSVL)编译器生成的LLVM-IR程序进行动态符号执行,为MSVL程序的验证工作提供执行路径。3.通过分析简单程序实例的执行结果,说明路径搜索模块工作流程的正确性。针对实际问题对应的程序实例,分别采用本文提出的策略与传统路径搜索策略进行动态符号执行,通过比较实验结果,表明本文提出的路径搜索策略在行覆盖率和分支覆盖率的增速上有促进作用。