我有程序计数器在执行特定代码时采用的值序列。使用这个,我想对生成此可执行文件的原始代码进行一些静态分析(需要明确的是:原始代码不可用) - 特别是有多少个循环以及它们是如何嵌套的。举个例子,
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 以及没有编译器优化的循环展开。
最佳答案
- 根据程序计数器序列绘制一个图,其中每个程序计数器是一个顶点,序列中的每对连续程序计数器是一个有向边。 (如果从一个顶点到另一个顶点有多条边,则仅保留其中一条)。
- 从序列中第一个程序计数器产生的顶点开始,执行深度优先搜索以查找循环。找到每个循环后,将该循环的最后一个边移动到单独的列表中。
- 找到所有循环并将其移出图表后,您就拥有了 DAG(有向无环图)。对此 DAG 执行拓扑排序,以恢复程序中语句的正确顺序,与源代码中完全相同,除了 if/else block (您无法从程序计数器序列确定哪一个是 'if',哪一个是 'else' )。为了获得正确的结果,在拓扑排序没有规定任何特定顺序的情况下,应使用深度优先搜索顺序。为了正确放置 while/for 循环体,可以使用步骤 2 中的一些附加信息:循环检测算法可以标记每个循环的第二个节点。
- 要分析 if/else block ,请在图表中创建单独的拆分/合并列表。
- 将循环列表(在步骤 2 中提取)和 if/else 列表(在步骤 4 中提取)合并到单个间隔列表中。使用这些间隔的关系(其中一个嵌套在另一个间隔中)为所有 for/if/else 语句构建一棵树。
- 在某些情况下,“while”循环末尾的“if” block 可能会被错误检测到
while{...if{}}
,如 while{loop{}...} ,具有相同的“while”和“loop”起始地址。由于“while”的起始地址不能与任何嵌套循环的起始地址一致,因此可以轻松地将其后处理回while{...if{}}
。 (嵌套的“do-while”循环可能具有相同的起始地址,但它们与嵌套的“if”没有任何问题)。
此方法仅在最简单的情况下有效,即没有“goto”、“break”或任何其他跳出循环且“for”循环仅检查单个条件时。
关于algorithm - 使用程序计数器(指令指针)值中的模式检测循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10623777/