大家好，我是Teddybe4r,今天给大家带来基于支配树和CFG回边的自然循环识别模块,这个模块是基于我自己的静态分析框架做的，具体可以看我的前面的文章 [原创]实现一个基于LLIL的x86/x64的静态分析框架 ，这个文章阐述了我是如何设计这个静态分析框架的，说实话研究方向有点跑偏了本来应该是继续写静态分析相关的东西的(虽然这个也算是也能用在过程间分析中，但是感觉不太沾边)，但是觉得反汇编实现挺有意思的就还是写了这个东西，也测试一下我的框架的能力如何，这篇文章读者可能需要先去看看我前面的文章了解CFG BasicBlock的概念,学过编译原理当然更好，在此文章中我还将给出一种基于特征的循环类别检测，但是目前根据nesting level的排序方式导致循环的显示顺序有点问题需要调整一下，不过大体功能还是正常的，目前论坛里有关该类工具的文章几乎没有只有些许大佬的研究并且仅限于理论，我希望这篇文章能够给各位坛友一些帮助，也能够带领读者了解IDA反汇编的一些内部原理，老样子文章还是分为理论+实践算法两个部分，我们开始吧。

这里的数学符号实在难写我就放图片了，没看到哪里支持latex....

这玩意儿其实不是必须的只是提高构建效率，一句话理解就是通过 DFS 生成的 DFN 序（及 DFS 树）为基础框架，通过半支配点（semi-dominator）的定义简化直接支配者的计算逻辑，再结合并查集路径压缩实现近线性时间复杂度。

甩个伪代码

想要对该算法深入研究的坛友可以去这篇文章 支配树Lengauer-Tarjan算法 可以详细查看下具体的数学论证与解释，也可以看看龙书的支配书章节。

我们在这里服用前面的支配树定义体系给出如下的回边定义

给出自然循环的定义

需要注意回边具有以下性质

我们要识别回边就一定要牢记核心的理解，在程序的控制流图（CFG）里，找那些 “往回跳、且跳过去的节点是必经之路” 的边，基于如上核心理解我们给出以下代码

回边之所以能形成循环，是因为它跳回了 “必经节点”,相当于 “绕了一圈又回到了必须经过的地方”，所以必然会重复执行（循环），比如你从家（A）出发，必须经过小区大门（B）才能到超市（C），超市门口有个门直接通回大门（C→B），那你就能反复走 “大门→超市→大门” 的循环（这就是回边的作用）。为了理解请各位一定要深入理解回边以及支配树以及自然循环的相关定义.

首先我们讲下思路，我们先通过支配关系识别所有 “目标节点支配源节点” 的回边，再对每条回边逆向遍历 CFG 收集所有可达的前驱块，形成最小的自然循环体，接着分析循环的出口和嵌套关系，最后标记循环属性然后生成可视化结果即可。所以自然循环结构的识别核心就是前面的定义以及最后一点点的循环属性标记，对于nesting level的计算也非常简单，我们仅仅需要判断该自然循环的循环头是否存在别的自然循环的循环体中就能够知晓是否为嵌套循环。当我们计算完之后需要标记循环块然后打印输出即可得到最后的结果。思路讲完了我们给出代码实现

这里我做的还不够好大家凑合看看吧，主要是for和while的区分比较难所以做了简化处理。

先讲下思路 若回边的源节点 == 循环头（loop.header == loop.backEdgeSource），直接判定为DO_WHILE_LOOP,do-while 是 “先执行循环体、后判断”，编译后常表现为循环头自环（判断指令在循环体末尾，跳回自身），这是 do-while 最典型的汇编特征。

若自环不成立，则检查回边源块的最后一条指令，若该指令是条件分支（InstType::BRANCH，如 jl/jle/jg 等），且跳转目标是循环头 判定为DO_WHILE_LOOP，do-while 的判断逻辑在循环体末尾，编译后表现为 “循环体最后一条指令是条件跳转，跳回循环头”，而非在循环头做判断。

然后根据 循环头最后一条指令是分支类型（InstType::BRANCH), 循环头有且仅有 2 个后继节点（successors.size() == 2),for/while 是 “先判断、后执行”，循环头作为条件判断节点，必然有两个分支：一个进入循环体（后继在循环体内），一个退出循环（后继在循环体外。

检查循环头的两个后继中，是否有一个不在循环体中（loop.body.count(succ) == 0）确认是 “条件退出” 分支，符合 for/while 的核心特征。

对于for/while的区分我通过判断循环体的大小来进行判断的。

1. 循环体块数 ≤4 → 判定为FOR_LOOP（for 循环通常结构更紧凑）

2. 循环体块数 >4 → 判定为WHILE_LOOP（while 循环体更灵活，可能更大）。

先给出测试源码

先说一下框架使用方法

[培训]Windows内核深度攻防：从Hook技术到Rootkit实战！