Path explosion
[CACM’13] Symbolic execution for software testing: three decades later
Path explosion represents one of the biggest challenges facing symbolic execution.
符号执行的一个关键挑战是除了最小的程序之外的所有程序路径都是大量的，这通常是代码中静态分支数量的指数。但是，请注意，符号执行仅探索依赖于符号输入的可行路径，这会减少产生新路径的条件数。例如，在测试多个中型应用程序的几个实验中，我们发现不到42％的执行语句依赖于符号输入，并且通常在执行期间遇到的符号分支不到20％具有双方可行。
尽管存在这种隐式过滤，但路径爆炸代表了符号执行面临的最大挑战之一，并且考虑到固定的时间预算，首先探索最相关的路径至关重要。在这里，我们提出了为解决这个问题而开发的技术的代表性选择。
搜索启发式。符号执行工具用于优先考虑路径探索的主要机制是使用搜索启发式算法。大多数启发式专注于实现高度陈述和分支覆盖，但它们也可用于优化其他所需的标准。我们在这里描述了当前符号执行工具成功使用的几种覆盖优化搜索启发式算法。 一种特别有效的方法是使用静态控制流图（CFG）来指导探索最接近的路径（如使用CFG进行静态测量）来自未经确认的指令[7,8]。类似的方法，如Cadar等人所述。 ，10是赞成运行次数最少的语句。
另一个例子，基于随机探索的启发式方法也证明是成功的.7,8主要思想是从程序的开头开始，并在每个符号分支开始，双方都可以随意选择哪一方探索。请注意，这种随机策略有许多重要的优点：与随机选择执行路径相比，当程序的一部分快速分配许多新路径时，它避免了饥饿;与随机生成输入相比，它具有更高的概率来到达由一小部分输入覆盖的分支。此外，该策略在执行早期有利于路径，对输入的约束更少，从而达到新的程序语句。
交错随机和符号执行。另一种成功的方法是在分析测试的背景下进行探索，是将符号探索与随机测试交织在一起.这种方法结合了随机测试的能力，可快速达到深度执行状态，具有象征性的力量执行以彻底探索特定社区的州。
修剪冗余路径。避免一遍又一遍地探索相同代码行的另一种方法是在探索期间自动修剪冗余路径。在Boonstoppel等人[5]中描述的RWset技术背后的关键是，如果程序路径到达与先前探索的路径具有相同符号约束的相同程序点，则该路径将继续完全执行从那时起也是如此，因此可以被丢弃。通过重要的优化增强了这种技术：当比较两个执行路径上的约束时，它会丢弃仅依赖于程序不会随后读取的值的那些。请注意，修剪这些路径的效果可能很大，因为通过继续执行产生的新路径的数量可以是已确定分支的数量的指数。
懒惰的测试生成。延迟测试生成[27]是一种类似于静态软件验证的反例引导细化范例的方法。该技术首先通过使用不受约束的输入替换每个被调用函数来探索，使用concolic执行，对被测函数的抽象。其次，对于由此抽象生成的每个（可能是虚假的）跟踪，它尝试通过递归扩展被调用函数并在被调用函数中查找可以拼接在一起的具体执行来将跟踪扩展为具体可实现的执行。用原始跟踪形成一个完整的程序执行。因此，它减少了关于过程间路径的推理过程中的符号推理的负担（在探索阶段），以及通过功能的局部和约束搜索（在融合阶段）。