algorithm - 使用程序计数器(指令指针)值中的模式检测循环

Question

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

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

在这种情况下，程序计数器序列可能是:A B C D F {G H I G H I G H I} A B D E F {G H I G H I} A B D E F {G H I G H I G H I G H I}

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

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

Answer 1

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

---

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