首页
社区
课程
招聘
[原创]反编译原理(5)-控制流分析
发表于: 2018-10-9 23:48 13650

[原创]反编译原理(5)-控制流分析

2018-10-9 23:48
13650

控制流结构恢复、变量和类型恢复是反编译器中端向后端转化最关键的两个步骤,本文讨论控制流结构恢复。

主要是概述鲸书“高级编译器的设计与实现”第7章控制流分析,并且增加了一些内容,所涉及的相关论文书籍自行查找学习,还可以从维基百科了解学习。

可以从论文"Notes on Graph Algorithms Used in Optimizing Compilers"了解学习

ControlFlowGraph(控制流程图),BasicBlock(基本块)、Predecessor(前驱)、Successor(后继)、Entry(入口)、Exit(出口)等概念,大部分的编译器控制流分析相关书籍论文都有介绍这些内容,还有应该熟悉了解图论中的有向图的相关知识。

BFS(广度优先搜索)和DFS(深度优先搜索)是图论中的两个概念,重点关注深度优先搜索,深度优先搜索有前序遍历、中序遍历、后序遍历三种遍历方法,前序遍历和后序遍历在控制流分析时是非常关键的两种遍历。大部分数据结构书籍中的图论都有介绍这些内容。

如果从流图的入口(Entry)结点到结点d的每一条可能的路径都经过结点n,称n是d的必经结点,或者说d支配n;如果从流图的结点d到出口(Exit)结点的每一条可能的路径都经过结点n,称n是d的后必经结点,或者说d后支配n。一种有效的表示支配结点信息的方法是用支配树(Dominator Tree)表示,构建支配树有静态和动态两种方法。

1.4.1 Static

主要有以下三种方法:

The Iterative Algorithm

可以从论文"A Simple, Fast Dominance Algorithm"学习了解,大部分编译器用这种方法构建支配树。

The Lengauer-Tarjan Algorithm

可以从论文"A Fast Algorithm for Finding Dominators in A Flowgraph"学习了解,一部分编译器用这种方法构建支配树。

The SEMI-NCA Algorithm

可以从论文"Finding Dominators in Practice"学习了解

1.4.2 Dynamic

主要有以下三种方法:

The Sreedhar-Gao-Lee Algorithm

可以从论文"Incremental Computation of Dominator Trees"学习了解,编译器GCC实现了该算法

The Dynamic SEMI-NCA Algorithm

可以从论文"An Experimental Study of Dynamic Dominators"学习了解,是Static构建方法The SEMI-NCA Algorithm的改进版本

The Depth-Based Search Algorithm

可以从论文"An Experimental Study of Dynamic Dominators"学习了解,最新LLVM版本实现了该算法

编译器和反编译器在控制流分析时,需要处理循环结构,循环结构最普遍的是流图中的SCC(强连通分量),大部分数据结构书籍中的图论都有介绍SCC(强连通分量)。

可归约性是流图的一个非常重要的性质,假设对流图进行若干变换,该变换将子图蜕化为单个结点,归约成更简单的若干子图,如果一系列的转化最终能够把流图归约成单个结点,则称这个流图是可归约的。某些控制流模式会使得流图不可约,大概有以下几种方法处理不可约流图:

1.6.1 Node Spilt

因为传统的结点分割很容易造成流图的结点个数指数级增长,不推荐使用这种方法。
可以从论文"Controlled Node Splitting"和论文Handling Irreducible Loops: Optimized Node Splitting vs. DJ-graphs学习非传统方法的结点分割。

1.6.2 CFG Flattening

CFG Flattening(控制流平坦化),虽然常用于代码混淆,但实际上也是把不可约流图转化成可归约流图的一种方法。

1.6.3 DataFlow Analysis

对于不可约流图,还可以进行数据流分析,该内容不在本文讨论范围。

由于历史原因,区间分析Region Analysis也称为Interval Analysis。区间分析将流图划分成各种类型的区域,使每一个区域蜕化成一个抽象节点,最终得到层次化、嵌套的抽象流图,该流图产生一棵控制树。

1.7.1 T1-T2 Interval

最简单、最早的区间分析,可从鲸书“高级编译器的设计与实现”第7章控制流分析了解详情。

1.7.2 Maximal Interval

区间分析使用极大区间,忽略不可归约区域,可从鲸书“高级编译器的设计与实现”第7章控制流分析了解详情。

1.7.3 Minimal Interval

更为现代的区间分析,有考虑不可归约区域,可从鲸书“高级编译器的设计与实现”第7章控制流分析了解详情。

1980年Sharir的论文"Structural Analysis: A New Approach to Flow Analysis in Optimizing Compilers"定义了结构化分析。
结构化分析是区间分析的增强版本,比区间分析能分析更多的区间类型。可从鲸书“高级编译器的设计与实现”第7章控制流分析了解该传统结构化分析。

区间分析或结构化分析只能处理SESE(Single-Entry-Single-Exit) 区间类型的流图,PST/RPST就是构建只包含SESE(Single-Entry-Single-Exit) 区域类型的控制树的一种方法

1.9.1 PST

可以从论文"The Process Structure Tree"了解学习

1.9.2 RPST

Graph Decomposition

区间分析或结构化分析的第一步骤和图论中的画图类似,都是要划分流图。图论的画图把流图划分成每一个最小组件,该最小组件称为Triconnected Components,有效表示Triconnected Components的方法是用SQPR-Tree表示。可以从论文"Application of SPQR-Trees in the Planarization Approach for Drawing Graphs"了解学习

RPST

RPST树就是一棵层次化、每个叶子节点都是一个SESE(Single-Entry-Single-Exit) 区间类型的控制树。可以论文"The Refined Process Structure Tree" 和论文"Simplified Computation and Generalization of the Refined Process Structure Tree"了解学习,开源库codebase能构建RPST树

反编译器进行控制流结构恢复时,所使用的算法很多来自于编译器的控制流分析。

反编译器的控制流程图比编译器控制控制流程图结点数量更多,分析时需要更多的时间和内存。早期LLVM版本构建支配树使用静态方法Lengauer-Tarjan算法,最新LLVM版本构建支配树已使用动态方法Depth-Based Search算法。

反编译的不可归约流图比编译器的不可约流图数量和类型更多。

2.2.1 Node Spilt

teavm,实现了论文"Handling Irreducible Loops: Optimized Node Splitting vs. DJ-graphs"的结点分割算法。

2.2.2 CFG Flattening

编译器的不可约流图通常是多入口的循环,但反编译器的不可约流图有更多的类型,LLVM源码目录lib/Target/WebAssembly/WebAssemblyFixIrreducibleControlFlow的实现类似于用控制流平坦化处理不可约循环。

2.2.3 DataFlow Analysis

数据流分析不在本文讨论范围。

反编译器的控制流分析有迭代控制流分析、区间分析和结构化分析三种方法。

迭代分析主要有以下三种方法:

2.4.1 Simple

最简单的控制流分析,根据模式进行归约合并,一些反编译器会使用编译器前端语法分析的一些方法。

2.4.2 CFG + Dominator

最基础的控制流分析,虽然用Simple的方法可以归约合并控制流图,但是有一些缺陷:比如假设有一个控制流的基本块,它的前驱代码位置不在它的前面,它的后继代码位置不在它的后面,则Simple方法根据模式归约合并将会出错,但如果是使用了控制流图和支配树的方法进行归约合并将不会出错。

开源反编译Retdec就使用了控制流图和支配树的方法进行控制流图重建恢复,问题在于它处理不可约流图时所使用的结点分割是传统的结点分割,导致反编译后的源码膨胀率严重,随便测试了一个百K左右的二进制文件的反编译,最后竟然生成了3-4M的c源码。

2.4.3 DFS parenthesis

DFS parenthesis特性,可以从算法导论第22章了解。开源反编译器boomerang就是用DFS parenthesis进行控制流分析。

区间分析比迭代分析更有效。

2.5.1 T1-T2 Interval

axtor,采用论文"Controlled Node Splitting"的结点分割算法和T1-T2结构化分析进行控制流图重建
fernflower,开源Java反编译器,采用传统的结点分割和T1-T2结构化分析进行控制流图重建

2.5.2 Maximal Interval

dcc是第一个使用极大化区间分析(Maximal Interval)的开源反编译器,没有考虑不可归约图,只支持16位二进制程序反编译,当然扩展支持32位/62位二进制程序反编译也不会太困难。

2.5.3 Minimal Interval

通常对不可约非正常区域,极小化区间分析方法采用将一个公共节点作为必经节点,其它节点边就必须要从控制流程图删除,并插入goto语句,另外,一些正常区域由于编译优化或代码混淆的原因,匹配规则不确定,也是无法归约的,同样是插入goto语句。

eclipse omr的区间分析实现不知道是不是极小化区间分析。

结构化分析是反编译器控制流分析最主要的分析方法。

2.6.1 Sharir Structural

鲸书“高级编译器的设计与实现”第7章控制流分析有详细说明

2.6.2 Zadeck Structural

Zadeck StructuralGCC补丁,并没有相关论文,使用gcc后端IR RTL,由于它是用于编译器,而编译器比反编译器拥有更多的信息,因此如果要把该算法用于反编译器需要一些修改

2.6.3 Hex-Rays Structural

IDA Pro反编译插件Hex-Rays Decompiler是反编译器的事实标准,它的结构化分析算法应该和sharir或zadeck的算法有些类似,只是对不可约非正常区域的处理方法有些不同。第14章会不完全探讨它的实现

LLVM的Region Analysis,也是SESE(Single-Entry-Single-Exit) Region Analysis,源码注释了说明其最基本的思路来自于PST/RPSTLLVM源码目录lib/Transform/Scalar下的StructurizeCFG源文件是算法的具体实现,好像是来自早期LLVM源码目录lib/Target/AMDGPU下的AMDGPUMachineCFGStructurizer源文件。

最新LLVM源码目录lib/Target/AMDGPU下的AMDGPUMachineCFGStructurizer源文件算法在编译器后端实现,变得更加复杂。算法大概思路是把IF基本块和Else基本块都转化成IF_Then_Else基本块。

2.7.1 PST

Harpoon,构建PST树进行控制流分析

2.7.2 RPST

abcd,java开源反编译器,用支配树来建立RPST树,好像并不能称为构建RPST树,只能称为构建控制树。

传统结构化分析的扩展,传统结构化分析只能处理只包含SESE(Single-Entry-Single-Exit) 区域的流图,扩展结构化分析新定义了SESS(Single-Exit-Single-Successor) 区域类型,好像能处理部分流图是Multi-Exit区域类型的情况

2.8.1 Type 1

可以从论文"Enhanced Structural Analysis for C Code Reconstruction from IR Code"学习了解

2.8.2 Type 2

可以从论文"Native x86 Decompilation using Semantics-Preserving Structural Analysis and Iterative Control-Flow Structuring"了解学习

因为区间分析或结构化分析只能处理只包含SESE(Single-Entry-Single-Exit) 区间类型的流程图,因此需要把原来的控制流图转化成只包含SESE (Single-Entry-Single-Exit) 区间类型的流程图,当前主要有以下两种方法:

2.9.1 Type 1

可以从论文"Emscripten: An LLVM-to-JavaScript Compiler"学习了解。

2.9.2 Type 2

可以从论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"学习了解

反编译器的控制流分析,是结构化分析,是基于控制树的控制流消去法,有些类似于数据流分析。

2.10.1 Normalized

反编译器的流图的区间类型有四种类型:SESE(Single-Entry-Single-Exit)SEME(Single-Entry-Multi-Exit)MESE(Multi-Entry-Single-Exit)MEME(Multi-Entry-Multi-Exit) 。为了能够进行结构化分析,需要把原来的流图都转化成只包含SESE(Single-Entry-Single-Exit) 区间的流程图。

当前有三种方法:第一种,构建RPST树,然后进行结构化分析;第二种,控制流平坦化,然后用Emscripten实现的ReLooper算法进行控制流分析;第三种,使用论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"的方法进行结构化分析。

2.10.2 Structuring Acyclic Regions

如何最小化控制流图重建后goto语句的数量的大小,无环区域的简化和优化的实现非常关键。

IF Regions

条件跳转区域简化和合并主要有以下两种方法:

一、Rules Matching

根据规则进行模式匹配,开始进行类型归类时有些想当然了,如何用规则匹配进行If语句合并将在另一篇“if-else分支的识别和合并”说明

二、Path Finding

根据规则匹配归约合并条件语句的方法有最大的缺陷:并不能覆盖所有的规则,由于二进制代码经过编译器优化,代码混淆的原因,匹配的规则数量是不确定的,则控制流图重建后不可避免有goto语句。
因此,需要考虑一种不使用规则模式匹配的方法来进行条件归约合并,
可以使用类似于符号执行所使用的Path Finding方法进行条件语句归约合并,论文"No More Gotos: Decompilation Using Pattern-Independent Control-Flow Structuring and Semantics-Preserving Transformations"中所使用的条件归约合并方法类似于Path Finding,论文有些晦涩,并不容易理解,有些类似于数据流分析自顶向下(Top-Down)向前问题(Forward)的到达-定值(Reaching Definitions)。

Switch Regions

Switch Regions 三种表现形式:位计算,跳转表,If跳转或二叉树If跳转。

控制流重建时主要考虑跳转表,需要考虑两种特殊的情况:case 块没有用Break语句,直接Fallthrough到下一个case 块;case 块没有用Break语句,而是使用Return语句。

Return/Finish Regions

某一无环区域有多个Return/Finish(Finish块通常用于资源释放),编译优化后二进制代码可能会共用一个Return/Finish块,结构化分析时需要复制Return/Finish块。

Other Regions


[培训]内核驱动高级班,冲击BAT一流互联网大厂工作,每周日13:00-18:00直播授课

最后于 2018-10-14 00:11 被vasthao编辑 ,原因:
收藏
免费 2
支持
分享
打赏 + 2.00雪花
打赏次数 2 雪花 + 2.00
 
赞赏  jinsheng   +1.00 2018/10/19
赞赏  junkboy   +1.00 2018/10/10
最新回复 (19)
雪    币: 1392
活跃值: (5142)
能力值: ( LV13,RANK:240 )
在线值:
发帖
回帖
粉丝
2
牛逼 牛逼~~~
2018-10-10 10:13
0
雪    币: 47147
活跃值: (20410)
能力值: (RANK:350 )
在线值:
发帖
回帖
粉丝
3
3和4文章没见到
2018-10-10 14:12
0
雪    币: 2141
活跃值: (7221)
能力值: ( LV11,RANK:180 )
在线值:
发帖
回帖
粉丝
4
2018-10-10 14:19
0
雪    币: 1258
活跃值: (1434)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
5
厉害了
2018-10-10 14:43
0
雪    币: 3425
活跃值: (1479)
能力值: ( LV9,RANK:320 )
在线值:
发帖
回帖
粉丝
6

这四篇论文有谁可以下载的希望分享一下:
1.Incremental computation of dominator trees

 

2.Structuring Assembly Programs

 

3.Enhanced Structural Analysis for C Code Reconstruction from IR Code

 

4.The refined process structure tree

2018-10-13 00:00
0
雪    币: 6682
活跃值: (1156)
能力值: ( LV5,RANK:158 )
在线值:
发帖
回帖
粉丝
7

完全不懂,不过从scholar.google.com帮楼主下载到两篇论文。

上传的附件:
2018-10-13 11:06
0
雪    币: 2605
活跃值: (5058)
能力值: ( LV9,RANK:225 )
在线值:
发帖
回帖
粉丝
8
贴地膜。
2018-10-15 22:40
0
雪    币: 1867
活跃值: (3958)
能力值: ( LV6,RANK:90 )
在线值:
发帖
回帖
粉丝
9
赞,之前摸索这做js代码的控制流扁平化反混淆,靠自己总结的算法做代码合并,那可真是幸苦,终于在这找到理论指导了
2018-10-18 18:54
0
雪    币: 400
活跃值: (1279)
能力值: ( LV3,RANK:30 )
在线值:
发帖
回帖
粉丝
10
好文,mark一下
2018-10-28 23:07
0
雪    币: 34
活跃值: (118)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
11
国人一点都不争气,一款反编译器都没搞出来啊。
最后于 2019-5-24 13:54 被goodgirls编辑 ,原因:
2019-5-24 13:53
0
雪    币: 249
活跃值: (346)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
12
goodgirls 国人一点都不争气,一款反编译器都没搞出来啊。
别把国人说得一无是处,版主大大的GDA不都是国产的反编译器么
https://bbs.pediy.com/thread-203916.htm

https://github.com/charles2gan/GDA-android-reversing-Tool
2019-5-24 16:55
0
雪    币: 249
活跃值: (346)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
13
好像还有不少学术反编译器,只能说搞这个的人少罢了
2019-5-24 16:56
0
雪    币: 34
活跃值: (118)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
14
hackevil 别把国人说得一无是处,版主大大的GDA不都是国产的反编译器么[em_10] https://bbs.pediy.com/thread-203916.htm https://github.com ...
这不是android的反编译器么,我说的是pc上的x86之类的。
2019-5-24 17:00
0
雪    币: 249
活跃值: (346)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
15
goodgirls 这不是android的反编译器么,我说的是pc上的x86之类的。
用的思想和理论都一样啊,解析机器码和字节码本质都差不多,后面的中间表示,控制流数据流分析,结构化分析使用的理论都差不了多少。
2019-5-24 17:06
0
雪    币: 34
活跃值: (118)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
16
hackevil 用的思想和理论都一样啊,解析机器码和字节码本质都差不多,后面的中间表示,控制流数据流分析,结构化分析使用的理论都差不了多少。
好吧,你说的这个我也不懂,算我瞎说
2019-5-24 17:08
0
雪    币: 1664
活跃值: (1194)
能力值: ( LV3,RANK:20 )
在线值:
发帖
回帖
粉丝
17
goodgirls 国人一点都不争气,一款反编译器都没搞出来啊。
搞得出的,懒得发出来了,这么多反编译器。
2019-5-25 12:22
0
雪    币: 204
活跃值: (74)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
18
要学习的太多了
2019-5-26 10:27
0
雪    币: 249
活跃值: (346)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
19
nonamei 搞得出的,懒得发出来了,这么多反编译器。
看来这位是高人,把你的反编译器发出来观摩观摩
2019-5-28 21:14
0
雪    币: 164
活跃值: (61)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
20
nonamei 搞得出的,懒得发出来了,这么多反编译器。
其实并不多,好多都是个界面,用的第三方的核心工具,还有很多反混淆能力和对抗能力不强根本没法用,不知道你的是哪种
2019-5-31 14:56
0
游客
登录 | 注册 方可回帖
返回
//