2

我有程序计数器在执行特定代码时采用的值序列。使用它，我想对生成这个可执行文件的原始代码进行一些静态分析（要清楚：原始代码不可用）——特别是那里有多少个循环，以及它们是如何嵌套的。举个例子，

A: for()
B:     if () 
C:         ...
D:     else
E:         ...
F:     for () {
G:         ...
H:         ...
I:     }

在这种情况下，程序计数器序列可能是： ABCDF {GHIGHIGHI} ABDEF {GHIGHI} ABDEF {GHIGHIGHIGHI}

从上面的序列中，我怎么知道有两个循环，一个嵌套在另一个循环中？只是指向要使用的适当解析技术的指针也会有所帮助。

可以进行一些简化假设，例如原始代码中没有 goto 和编译器优化的循环展开。

4

1 回答 1

2
  1. 用程序计数器序列制作一个图形，其中每个程序计数器是一个顶点，序列中每对连续的程序计数器是有向边。（如果从一个顶点到另一个顶点有多条边，则只保留其中一条）。
  2. 从序列中第一个程序计数器产生的顶点开始，执行深度优先搜索以找到循环。找到每个循环后，将此循环的最后一条边移到单独的列表中。
  3. 在找到所有循环并将其移出图后，您就有了一个 DAG（有向无环图）。对此 DAG 执行拓扑排序以恢复程序中的正确语句序列，与源代码中的语句序列完全相同，除了 if/else 块（您无法从程序计数器序列中确定哪个是“if”，哪个是“else” ）。为了得到正确的结果，在拓扑排序没有规定任何特定顺序的情况下，应该使用深度优先搜索排序。为了正确放置 while/for 循环体，可以使用步骤 2 中的一些附加信息：循环检测算法可能会标记每个循环的第二个节点。
  4. 要分析 if/else 块，请在图中创建单独的拆分/合并列表。
  5. 将循环列表（在步骤 2 中提取）和 if/else 列表（在步骤 4 中提取）组合成一个间隔列表。使用这些间隔的关系（其中一个嵌套在另一个中）为所有 for/if/else 语句构造一棵树。
  6. 在某些情况下，'while' 循环结束时的 'if' 块while{...if{}}可能会被错误地检测到，如 while{loop{}...}，'while' 和 'loop' 的起始地址相同。由于 'while' 的起始地址不能与任何嵌套循环的起始地址重合，因此可以很容易地将其后处理回while{...if{}}. （嵌套的 'do-while' 循环可能具有相同的起始地址，但它们与嵌套的 'if' 没有任何问题）。

这种方法仅适用于最简单的情况，即没有“goto”、“break”或任何其他跳出循环并且“for”循环仅检查单个条件时。

于 2012-05-16T18:44:36.470 回答