編譯與反編譯相關(guān)的知識是比較枯燥的，本文試圖結(jié)合對androguard(https://github.com/androguard/androguard)的內(nèi)置dad反編譯器來進(jìn)行講解。那么學(xué)習(xí)這一部分知識有什么用處呢？就拿android應(yīng)用來說，VMP/java2c等等加固混淆的實(shí)現(xiàn)和對抗都和編譯與反編譯的原理息息相關(guān)，理解這一部分的知識無論是對于正向開發(fā)還是逆向分析都是有很大幫助的。比如github上開源的一個java2c方案dcc(https://github.com/amimo/dcc)也用了dad的代碼。java2c可以理解成是一個比較特殊的編譯的過程，正常情況是把java代碼編譯成字節(jié)碼交給虛擬機(jī)解釋執(zhí)行，java2c是把java代碼”編譯”成c代碼。本文首先會介紹一些編譯與反編譯相關(guān)的基本理論，然后會讓讀者大致了解一下androguard，最后會對androguard的內(nèi)置dad反編譯器中的一些關(guān)鍵的代碼進(jìn)行講解。
基本理論
支配(dominates)：若從進(jìn)入程式塊到達(dá)基本塊N的所有路徑，都會在到達(dá)基本塊N之前先到達(dá)基本塊M，則基本塊M是基本塊N的支配點(diǎn)。由支配點(diǎn)構(gòu)成的樹就是支配樹。
前進(jìn)邊(advancing edge)：是指向的基本塊是在圖的深度優(yōu)先搜索中沒有走過的基本塊。
倒退邊(back edge)：是指向的基本塊是在圖的深度優(yōu)先搜索中已經(jīng)走過的基本塊。倒退邊多半表示有循環(huán)。
區(qū)間圖(interval graph)：是指給定一個節(jié)點(diǎn)h，其區(qū)間圖是h為入口節(jié)點(diǎn)，并且其中所有閉合路徑都包含h的最大的單入口子圖。h被稱為區(qū)間頭節(jié)點(diǎn)或簡稱頭節(jié)點(diǎn)。
對于一個CFG，可以把它區(qū)間圖稱為一階圖。二階圖將每個區(qū)間圖作為一個節(jié)點(diǎn)，以此類推。如果最終能夠把CFG轉(zhuǎn)化為單個節(jié)點(diǎn)，就稱該CFG是可規(guī)約的(reducible)。
拓?fù)渑判?topological sorting)：拓?fù)渑判蚴且粋�有向無環(huán)圖的所有頂點(diǎn)的線性序列。且該序列必須滿足下面兩個條件：
每個頂點(diǎn)出現(xiàn)且只出現(xiàn)一次。
若存在一條從頂點(diǎn) A 到頂點(diǎn) B 的路徑，那么在序列中頂點(diǎn) A 出現(xiàn)在頂點(diǎn) B 的前面。
前序/后序/逆后序：
深度優(yōu)先搜索在遍歷圖的過程中，可以記錄如下順序：
前序：即在遞歸調(diào)用之前將頂點(diǎn)加入隊列，代表深度優(yōu)先搜索訪問頂點(diǎn)的順序。
后序：即在遞歸調(diào)用之后將頂點(diǎn)加入隊列，代表深度優(yōu)先搜索頂點(diǎn)遍歷完成的順序。
逆后序：即在遞歸調(diào)用之后將頂點(diǎn)壓入棧，代表著頂點(diǎn)的拓?fù)渑判颉?/p>
androguard簡介
本文分析的androguard源代碼版本為3.3.5。
decompiler：提供反編譯功能，主要有兩種方式實(shí)現(xiàn)，一種是使用jadx，一種是使用內(nèi)置的名為dad的反編譯器，(還有一些其他的第三方反編譯器均已廢棄)。decompiler/dad目錄即為dad反編譯器的實(shí)現(xiàn)了。
我們運(yùn)行一下decompile.py試試，apk就直接用提供的測試apk：androguard-3.3.5/examples/android/TestsAndroguard/bin/TestActivity.apk。
% python3 decompile.py
INFO: ========================
INFO: Classes:
......
INFO: Ltests/androguard/TestActivity;
......
INFO: ========================
Choose a class (* for all classes): TestActivity
INFO: ======================
......
INFO: 9: foo
......
INFO: ======================
Method (* for all methods): 9
INFO: Source:
INFO: ===========================
package tests.androguard;
public class TestActivity extends android.app.Activity {
private static final int test2 = 20;
public int[] tab;
private int test;
public int test3;
public int value;
public int value2;
public int foo(int p3, int p4)
{
int v0 = p4;
while(true) {
int v4_1;
if (p3 < v0) {
v4_1 = (v0 + 1);
try {
p3 = (v0 / p3);
v0 = v4_1;
} catch (RuntimeException v1) {
p3 = 10;
}
} else {
if (p3 == 0) {
break;
}
v4_1 = v0;
}
v0 = v4_1;
}
return v0;
}
}
同時在/tmp/dad/blocks，/tmp/dad/pre-structured和/tmp/dad/structured可以看到生成的CFG圖。非條件節(jié)點(diǎn)的邊是藍(lán)色的，條件節(jié)點(diǎn)為true的邊是綠色的，條件節(jié)點(diǎn)為false的邊是紅色的。try catch的邊是黑色的虛線。
/tmp/dad/pre-structured：
/tmp/dad/structured：
這一部分之后還會詳細(xì)解釋，下面對dad目錄下的文件做個簡介。
源碼分析
網(wǎng)上找的一張圖。按照反編譯技術(shù)實(shí)施的順序劃分，則可以分為7個階段，它們是：句法分析、語義分析、中間代碼生成、控制流圖生成、控制流分析、代碼生成。
當(dāng)我們運(yùn)行decompile.py的時候調(diào)用了DvMachine處理提供的apk(dex/odex)文件，通過androguard/core/analysis/analysis.py中的Analysis類對其進(jìn)行分析。對于每個class通過ClassAnalysis進(jìn)行分析；對于每個method通過MethodAnalysis進(jìn)行分析。
self.vms.append(vm)
for current_class in vm.get_classes():
self.classes[current_class.get_name()] = ClassAnalysis(current_class)
for method in vm.get_methods():
self.methods[method] = MethodAnalysis(vm, method)
在MethodAnalysis中，h表示分支指令和對應(yīng)的目的地址，l表示所有的目的地址，例如對于下面這個method：
(0)，v1, +5，length:4，if-lez
(4)，v0, v1, 2，length:4，mul-int/lit8
(8)，v0，length:2，return
(10) v0, v1, 2，length:4，add-int/lit8
(14) -3，length:2，goto
h:
{0: [4, 10], 8: [-1], 14: [8]}
l:
[4, 10, -1, 8]
所有的分支指令：
throw
throw.
if.
goto
goto.
return
return.
packed-switch$
sparse-switch$
據(jù)此創(chuàng)建DVMBasicBlock并通過BasicBlocks列表進(jìn)行管理，接下來主要的處理是在process函數(shù)中。
下面就重點(diǎn)講一下process函數(shù)中涉及到的控制流圖生成(graph.py)，數(shù)據(jù)流分析(dataflow.py)和控制流分析(control_flow.py)。
opcode_ins.py
所有的opcode。
instruction.py
表示opcode的類，對應(yīng)于上圖中的中間代碼生成，比如if-eq，if-ne等等這些opcode都用ConditionalExpression類表示。
writer.py
輸出源代碼。
dast.py
輸出AST。
basic_blocks.py
提供build_node_from_block函數(shù)，根據(jù)提供的block的最后一條指令返回對應(yīng)的block類型。返回的類型包括：
ReturnBlock，SwitchBlock，CondBlock，ThrowBlock和StatementBlock。
graph.py
compute_rpo函數(shù)
得到CFG的逆后序。
post_order函數(shù)
得到CFG的后序。
split_if_nodes函數(shù)
將CondBlock拆分為StatementBlock和新的CondBlock，StatementBlock是頭節(jié)點(diǎn)，新的CondBlock僅由跳轉(zhuǎn)條件組成。
simplify函數(shù)
通過合并/刪除StatementBlock來簡化CFG：如果StatementBlock B跟在StatementBlock A后面，并且StatementBlock B除了StatementBlock A沒有其它的前任節(jié)點(diǎn)，那么我們可以將A和B合并成一個新的StatementBlock。
還刪除除了重定向控制流之外什么都不做的節(jié)點(diǎn)(只包含goto的節(jié)點(diǎn))。
dom_lt函數(shù)/immediate_dominators函數(shù)
通過Lengauer-Tarjan算法構(gòu)造支配樹。dom[i]表示支配i的節(jié)點(diǎn)。
bfs函數(shù)
廣度優(yōu)先搜索。
make_node函數(shù)
通過block(DVMBasicBlock)得到node(basic_blocks.py中定義的block類型)。
首先檢查該block是否有對應(yīng)的node，沒有就創(chuàng)建出來。
如果說這是一個try block，則把catch node也創(chuàng)建出來，加到catch_edges(try node，即CFG中黑色虛線箭尾)和reverse_catch_edges(catch node，即CFG中黑色虛線箭頭)。
對于該block的所有child如果沒有對應(yīng)的node就創(chuàng)建出來，添加該node到child node的edge。如果這個node是SwitchBlock，則將child node添加到node的cases中；如果這個node是CondBlock，則將node的true或false設(shè)置為child node。
construct函數(shù)
構(gòu)造CFG。
調(diào)用bfs函數(shù)得到DVMBasicBlock序列，對于每個DVMBasicBlock調(diào)用make_node函數(shù)然后加到圖中，設(shè)置graph的entry和exit。
control_flow.py
控制流分析。
intervals函數(shù)
給定一個控制流圖，計算該圖區(qū)間圖(interval graph)的集合。
對于最前面運(yùn)行decompile.py舉的例子，如果大家去看/tmp/dad/pre-structured中生成的CFG圖，該圖有兩個區(qū)間圖，一個是1-Statement(foo-BB@0x0)這一個節(jié)點(diǎn)組成的區(qū)間圖，另外一個就是其他節(jié)點(diǎn)組成的區(qū)間圖。
算法：
將圖的入口加入頭節(jié)點(diǎn)列表，遍歷所有頭節(jié)點(diǎn)：取出頭節(jié)點(diǎn)并標(biāo)記，將其加入一個區(qū)間圖，如果存在一個節(jié)點(diǎn)，其所有前驅(qū)節(jié)點(diǎn)都在當(dāng)前區(qū)間圖中就將該節(jié)點(diǎn)加入當(dāng)前區(qū)間圖，重復(fù)直到所有可能的節(jié)點(diǎn)都被加入當(dāng)前區(qū)間圖； 此時如果存在一個節(jié)點(diǎn)不在區(qū)間圖中但是它的一個前驅(qū)節(jié)點(diǎn)在區(qū)間圖中，那么這個節(jié)點(diǎn)就是另一個區(qū)間圖的頭節(jié)點(diǎn)，將該節(jié)點(diǎn)加入頭節(jié)點(diǎn)列表，重復(fù)直到所有可能的節(jié)點(diǎn)都被加入頭節(jié)點(diǎn)列表。
derived_sequence函數(shù)
計算CFG的導(dǎo)出序列，也就是如把CFG最終轉(zhuǎn)化為單個節(jié)點(diǎn)。返回兩個參數(shù)，第一個參數(shù)Gi是區(qū)間圖的列表，第二個參數(shù)Li是區(qū)間圖的頭節(jié)點(diǎn)的列表。Gi[0]是原始圖，Gi[1]是一階圖，Gi[x]是x階圖；Li[0]是一階圖的頭節(jié)點(diǎn)，Li[1]是二階圖的頭節(jié)點(diǎn)，Li[x]是x+1階圖的頭節(jié)點(diǎn)。
loop_type函數(shù)
返回循環(huán)的類型：
Pre-test Loop：檢查條件后才執(zhí)行循環(huán)；
Post-test Loop：先執(zhí)行循環(huán)再檢查條件；
End-less Loop：無限循環(huán)。
loop_follow函數(shù)
標(biāo)記x.follow['loop'] = y，表示x這個循環(huán)節(jié)點(diǎn)結(jié)束之后應(yīng)該是y節(jié)點(diǎn)。
loop_struct函數(shù)
識別循環(huán)。遍歷derived_sequence函數(shù)返回的兩個列表，如果對于一個頭節(jié)點(diǎn)，有一個它的前驅(qū)節(jié)點(diǎn)和它位于同一個區(qū)間圖，那么就標(biāo)記一個循環(huán)。
比如對于下面的代碼：
public void testWhile() {
int i = 5;
int j = 10;
while (i < j) {
j = (int) (((double) j) + (((double) i) / 2.0d) + ((double) j));
i += i * 2;
}
f13i = i;
f14j = j;
}
derived_sequence函數(shù)返回的結(jié)果：
Gi[0]:（原始圖）
[
1-Statement(testWhile-BB@0x0),
2-If(testWhile-BB@0x6),
4-Statement(testWhile-BB@0xa),
3-Return(testWhile-BB@0x24)
]
Gi[1]:（一階圖）
[
Interval-testWhile-BB@0x0({1-Statement(testWhile-BB@0x0)}),
Interval-testWhile-BB@0x6({2-If(testWhile-BB@0x6), 3-Return(testWhile-BB@0x24), 4-Statement(testWhile-BB@0xa)})
]
Li[0]:（一階圖的頭節(jié)點(diǎn)）
{
1-Statement(testWhile-BB@0x0): Interval-testWhile-BB@0x0({1-Statement(testWhile-BB@0x0)}),
2-If(testWhile-BB@0x6): Interval-testWhile-BB@0x6({2-If(testWhile-BB@0x6), 3-Return(testWhile-BB@0x24), 4-Statement(testWhile-BB@0xa)})
}
Li[1]:（二階圖的頭節(jié)點(diǎn)）
{
Interval-testWhile-BB@0x0({1-Statement(testWhile-BB@0x0)}): Interval-Interval-testWhile-BB@0x0({Interval-testWhile-BB@0x6({2-If(testWhile-BB@0x6), 3-Return(testWhile-BB@0x24), 4-Statement(testWhile-BB@0xa)}), Interval-testWhile-BB@0x0({1-Statement(testWhile-BB@0x0)})})
}
遍歷Li[0]，BB@0x0沒有前驅(qū)節(jié)點(diǎn)；BB@0x6的第一個前驅(qū)節(jié)點(diǎn)BB@0x0和它不在同一個區(qū)間圖中；第二個前驅(qū)節(jié)點(diǎn)BB@0xa和它在同一個區(qū)間圖中(BB@0x6為頭節(jié)點(diǎn)，包含節(jié)點(diǎn)BB@0x6，BB@0x24，BB@0xa的區(qū)間圖)，所以標(biāo)記一個循環(huán)。
if_struct函數(shù)
標(biāo)記x.follow['if'] = y，表示x這個if{…}else{…}結(jié)束之后應(yīng)該是y節(jié)點(diǎn)。
switch_struct函數(shù)
標(biāo)記x.follow['switch'] = y，表示x這個switch結(jié)束之后應(yīng)該是y節(jié)點(diǎn)。
short_circuit_struct函數(shù)
短路求值，將兩個CondBlock合并成一個�？偣菜姆N情況。
第一種情況合并前后：
第二種情況合并前后：
第三種情況合并前后：
第四種情況合并前后：
實(shí)際例子：
public static int testShortCircuit4(int p, int i) {
if ((p <= 0 || i == 0) && (p == i * 2 || i == p / 3)) {
return -p;
}
return p + 1;
}
pre-structured:
structured:
while_block_struct函數(shù)
根據(jù)loop_struct函數(shù)識別出的循環(huán)添加一個LoopBlock類型的node并刪除原來的node。
catch_struct函數(shù)
通過reverse_catch_edges遍歷所有catch塊，支配其的節(jié)點(diǎn)即為對應(yīng)的try塊，據(jù)此新建CatchBlock和TryBlock，加入圖中并更新圖。
update_dom函數(shù)
更新支配樹。
identify_structures函數(shù)
主要就是調(diào)用前面提到的這些函數(shù)識別出一些結(jié)構(gòu)。
dataflow.py
數(shù)據(jù)流分析。一些基本知識可以參考下面這幾篇文章。
靜態(tài)分析之?dāng)?shù)據(jù)流分析與 SSA 入門 （一）
靜態(tài)分析之?dāng)?shù)據(jù)流分析與 SSA 入門 （二）
反編譯器C-Decompiler關(guān)鍵技術(shù)的研究和實(shí)現(xiàn)
實(shí)際例子：
public int test1(int val) {
return (val + 16) - (this.value * 60);
}
get_loc_with_ins返回的loc和ins：
0 ASSIGN(VAR_0, CST_16)
1 ASSIGN(VAR_1, (+ PARAM_4 VAR_0))
get_used_vars：0，4
2 ASSIGN(VAR_2, THIS.value)
get_used_vars：3
3 ASSIGN(VAR_2, (* VAR_2 CST_60))
get_used_vars：2
4 ASSIGN(VAR_1, (- VAR_1 VAR_2))
get_used_vars：1，2
5 RETURN(VAR_1)
register_propagation函數(shù)
寄存器傳播。
build_def_use函數(shù)
對于上面的例子構(gòu)建的DU和UD鏈：
use_defs:
(x, y):[z]表示第y行的var x是在第z行定義的
{ (0, 1): [0], (4, 1): [-2], (3, 2): [-1], (2, 3): [2], (1, 4): [1], (2, 4): [3], (1, 5): [4] }
def_uses:
(x, y):[z]表示第y行定義的var x在第z行使用
{ (0, 0): [1], (4, -2): [1], (3, -1): [2], (2, 2): [3], (1, 1): [4], (2, 3): [4], (1, 4): [5]} )
-1表示第一個參數(shù)，-2表示第二個參數(shù)。
split_variables函數(shù)
靜態(tài)單賦值SSA，通過分割變量使得每個變量僅有唯一的賦值。
對于上面的例子split_variables之后的DU和UD鏈：
use_defs:
{ (0, 1): [0], (4, 1): [-2], (3, 2): [-1], (5, 4): [1], (6, 5): [4], (7, 3): [2], (8, 4): [3] }
def_uses:
{ (0, 0): [1], (4, -2): [1], (3, -1): [2], (5, 1): [4], (6, 4): [5], (7, 2): [3], (8, 3): [4]} )
dead_code_elimination函數(shù)
清除死代碼并更新DU和UD鏈。
經(jīng)營性網(wǎng)站備案信息
可信網(wǎng)站信用評價
網(wǎng)絡(luò)警察提醒您
誠信網(wǎng)站
中國互聯(lián)網(wǎng)舉報中心
網(wǎng)絡(luò)舉報APP下載
