1

我试图了解符号执行引擎的工作原理。本文调查了使用 C 的技术。他们提到了符号记忆:

3.1 全符号记忆

在最高级别的通用性上,引擎可以将内存地址视为完全符号...

以紧凑的形式表示内存。这种方法在 [32] 中采用,它将符号(而不是具体)地址表达式映射到数据,表示使用紧凑、隐式形式的符号地址引用内存所产生的可能替代状态

本文还对 Java 的符号堆进行了一些探讨:

4.1 符号状态表示

符号状态 s 由符号堆 H、原始类型字段的估值、路径条件 PC 和程序计数器组成。

我想知道这在实践中意味着什么,这个符号堆。对我来说,这意味着符号执行中使用的所有数据结构都将使用符号内存而不是实际内存。这意味着像数组这样的结构需要有符号模型。我想知道这些模型是什么样的。我看不到您如何“对数组长度进行符号建模”。在我看来,它是一个整数,所以它将是一个整数值。但作为一个象征性的价值,想知道这意味着什么。我还没有看到。想知道是否可以从高层次上解释如何对一些数据结构(如数组或具有一些不同字段值的结构)进行符号建模,因此它在符号执行中很有用。

这篇较旧的论文提到:

还可以为不需要使用真实数据对象但可以用任意符号表示的编程语言定义另一种“符号执行”语义。

不知道这看起来如何。

4

2 回答 2

1

符号执行引擎的一个完整记录的开源示例是 JPF - Symbolic Pathfinder。它在 Java 虚拟机级别上执行。它还应该回答您关于更复杂的数据结构(如数组或对象数组)的问题。

一个非常好的出版物在这里:“Symbolic PathFinder: Integrating Symbolic Execution with Model Checking for Java Bytecode Analysis”在自动化软件工程杂志 20(3) 2013 https://ti.arc.nasa.gov/publications/5269/download/

在这里,您可以看到一个详细的示例(第 4.9 节),说明具体代码如何“重写”并转换为符号代码。特别是如何处理堆栈和堆内存以及取决于此符号内存的代码条件(图 6+7)。您不能简单地将内存与条件路径执行分开。

非常简化:条件被所有“符号”分支上的循环替换(非确定性选择)。内存被符号值替换(就像你提到的那样 - 通过所谓的属性在这里传播)和对这些值的约束取决于分支循环。约束求解器用于进一步减少不可能的分支(回溯)并最终解决约束。

.Net 代码的另一个非常好的实践示例是使用“Combination.KeepUnexpanded”以完全符号模式运行 Microsoft SpecExplorer (XRT)。在生成的探索遍历路径图中,您可以看到如何表示符号内存和约束的一个很好的示例。不幸的是,XRT 不是开源的。

PS:的确,符号变量的表示是一大挑战。这里有一些非常好的出版物:

于 2018-06-08T08:15:59.420 回答
0

“数组 X 的大小为 100,位置 5 的元素的值为 7”是数组的符号表示。符号表示的关键点是您只关注显式重要的内容。

如果您想表示一个更通用的数组,您也可以通过说“X 的大小为 L”来使其大小具有符号性,并且在分析期间您可能会发现 L=100 或 L>90。

您捕获不同数据结构的程度取决于您想要做什么。链表是一堆内存区域还是更多?

于 2018-06-07T02:40:37.890 回答