在二进制代码中查找循环的“标准”方法是什么？

#1 楼

这个问题的经典编译器理论答案是建立控制流图，然后进行图分析以识别自然循环。我相信可以在《龙书》中找到用于此目的的算法，并在以下幻灯片中给出摘要：

http://www.cs.cmu.edu/afs/cs/academic/class/ 15745-s03 / public / lectures / L7_handouts.pdf

您还可以查看LLVM如何实现其循环检测：

http://llvm.org/docs/doxygen/ html / LoopInfo_8h_source.html

要查找更多信息的搜索词是“自然循环”和“后边缘”。

#2 楼

您可能会发现有关查找递归函数的问题很有帮助，答案非常好。在恕我直言的二进制代码级别下，检测循环（即到同一目标的一些jmp）和递归调用（即到同一目标的一些call）几乎没有区别。

#3 楼

我不认为有一种标准的方法，但是一种方法可能是使用类似Johnson的算法来检测函数有向图中的周期。 。

#4 楼

从二进制代码检测循环并不容易。基于多种图形数据结构（CFG，SSA形式，DDG等）的算法很多。
我提供了一组其他有用的文档link1，link2，link3。
您可以检查MAQAO的基于SSA的环路检测器的实现。另外，我建议您检查DynInst的代码和文档link4。

现在，您可以实现一个汇编代码分析器，该代码分析器可以通过跟随分支来检测基本块/循环。 br />分解二进制文件并仔细阅读说明。
如果遇到条件跳转（Jxx模式），请检查它是在上方还是下方跳转。

如果跳转点在上方，请检查距离（Delta（BRANCH_ADDRESS，BRANCH_TARGET_ADDRESS）），如果距离不太大（您必须确定一个限制），则可以对分支条件进行一些分析（检查它是否包含移位的寄存器[递增/递减]）。分支条件分析可以是一个简单的模式匹配：是一个循环。


如果跳转点在下面，则其成为循环控制结构一部分的可能性较小。因此，您可以忽略它，然后继续执行下一个指令。