-
-
笔记-对《反编译原理(5)-控制流分析》的学习
-
2023-9-9 12:37
-
说明
最近在整理反编译器设计和实现相关的知识，看看能不能有新的灵感。
发现 vasthao 大哥的《[原创]反编译原理(5)-控制流分析》 https://bbs.kanxue.com/thread-247201.htm
这篇文章除了写的不太适合人类阅读（自己学习！），别的都很不错
我觉得这个文章值得写一篇"学习笔记"，让我把浅层的内容整理并提取一下，通过举例的方法，更好的解读一下这个技术。
这个笔记将尽量通俗的易懂，不带学术公式的讨论下面这几个问题：
1、控制流还原在反编译器中的功能是什么？
2、鲸书《高级编译器的设计与实现》第7章，讲了啥？
3、举例说明，为什么会出现"不可规约"的控制流
4、为什么IDA/Ghidra等反编译器F5后的代码会有goto,没法完全还原控制流
5、其它的补充。
什么是控制流还原
所谓控制流还原，通俗的讲就是将CFG还原成由if、while、for等组成的高级抽象结构。如下图有个控制流图，他的边本身是个jump，反编译器需要理解控制流的结构，把条件分支和循环识别出来
反编译器中的控制流还原
控制流还原部分处于反编译步骤的最后几步，在反编译器中端IR优化完成之后，再通过算法将CFG还原成由if、while、for等组成的高级抽象。
《高级编译器的设计与实现》第7章的结构分析技术
鲸书的第七章描述了一个叫做"结构分析"的控制流恢复的算法。其原理大致是预置好各种流图模式，然后在CFG中寻找能对应上的模式后，把流图按照规则进行"塌缩"，直到塌缩成一个点就完成分析了。
这样说十分的抽象，举例说明。
预置模式
流图塌缩
什么是"不可规约"流图
使用“结构化分析”这种技术，比较麻烦的问题是对“不可规约”流图的处理。
所谓“不可规约流图”，通俗的说，就是一个CFG无法套用上面任何一种规则进行“塌缩”
比较典型的“不可规约流图”有多入口的循环，多出口的循环等等，我这里从书里找了几个典型的“不可规约流图”的例子：
为什么会产生不可规约流图？
虽然源码中，不可规约的情况很少很少。但是，在编译的大型二进制产物中，不可规约流图十分常见。
其主要原因是，编译器对源码的优化会修改CFG，产生不可规约的情况，我以比较好理解的编译器的尾融合（tail-merging或cross-jumping）优化为例；
在这个优化中，编译器寻找最后几条指令相同的两个基本块，若这两个基本块都转移到同一个位置，就将这两个基本块的代码尾部合并，以此来缩小编译产物的代码规模。
示例源码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | int fun(int a, int b){ int ret = 0; if (getchar() > 0x10) { ret = a+b; } else { ret = a-b; if (getchar()>0x20) { printf("hello"); printf("ret=xx"); return ret; } } printf("hi"); printf("ret=xx"); return ret;} |
编译器优化中发现， printf("ret=xx"); return ret; 这两句代码完全一致，为了减少代码量就插入一个goto语句将这两个尾部进行融合。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | int fun(int a, int b){ int ret = 0; if (getchar() > 0x10) { ret = a+b; } else { ret = a-b; if (getchar()>0x20) { printf("hello"); goto LABEL } } printf("hi");LABEL: printf("ret=xx"); return ret;} |
如下图
很明显，这就是一个典型的"不可规约"流图，《鲸书》中第七章将也有专门提到这种无法规约的场景。
由于这种流图无法正常规约，那么IDA这种反编译器对付的方法就是插入一个GOTO语句进行缓解。
为什么IDA F5后的代码会有GOTO语句？
当前，通用的反编译器,比如IDA/Ghidra等使用的控制流还原技术都是基于“结构化分析”，为了解决不可规约流图的问题，反编译器选用了一种保守的方案："删除边"后使用goto替代。并重新进行塌缩。这也是为什么F5后的代码会有GOTO语句的原因。
还是之前那个代码，IDA反编译后会插入goto语句解决这个问题。
简单的说就是下面这样处理
笔记中没有涉及的部分
1、循环定义、强循环识别、支配树相关的内容与算法；
2、对于"不可规约"流图转换相关的知识；
3、较新的学术论文
如果有兴趣可以自己去看一下鲸书的第七章
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
