基于符號(hào)執(zhí)行Android原生代碼控制流圖提取方法

1、第7期顏慧穎等：基于符號(hào)執(zhí)行的Android原生代碼控制流圖提取方法45基于符號(hào)執(zhí)行的Android原生代碼控制流圖提取方法顏慧穎，周振吉，吳禮發(fā)，洪征，孫賀（解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院，江蘇 南京 210000）摘 要：提出了一種基于符號(hào)執(zhí)行的控制流圖提取方法，該方法為原生庫(kù)中的函數(shù)提供了符號(hào)執(zhí)行環(huán)境，對(duì)JNI函數(shù)調(diào)用進(jìn)行模擬，用約束求解器對(duì)符號(hào)進(jìn)行求解。實(shí)現(xiàn)了控制流圖提取原型系統(tǒng)CFGNative。實(shí)驗(yàn)結(jié)果表明，CFGNative可準(zhǔn)確識(shí)別樣例中所有的JNI函數(shù)調(diào)用和原生方法，并能夠在可接受的時(shí)間內(nèi)達(dá)到較高的代碼覆蓋率。關(guān)鍵詞：控制流圖；Android應(yīng)用軟件；原生代碼；符號(hào)執(zhí)行中圖分

2、類號(hào)：TP309文獻(xiàn)標(biāo)識(shí)碼：Adoi: 10.11959/j.issn.2096-109x.2017.00178Symbolic execution based control flow graphextraction method for Android native codesYAN Hui-ying, ZHOU Zhen-ji, WU Li-fa, HONG Zheng, SUN He(Institute of Command Information System, PLA University of Science and Technology, Nanjing 210000, Chi

3、na)Abstract: A symbolic execution based method was proposed to automatically extract control flow graphs from native libraries of Android applications. The proposed method can provide execution environments for functions in native libraries, simulate JNI function call processes and solve symbols usi

4、ng constraint solver. A control flow graph extraction prototype system named CFGNative was implemented. The experiment results show that CFGNative can accurately distinguish all the JNI function calls and native methods of the representative example, and reach high code coverage within acceptable ti

5、me.Key words: control flow graph, Android application, native code, symbolic execution1 引言收稿日期：2017-05-07；修回日期：2017-06-09。通信作者：吳禮發(fā)，wulifa基金項(xiàng)目：國(guó)家重點(diǎn)研發(fā)計(jì)劃基金資助項(xiàng)目（No.2017YFB0802900）；江蘇省自然科學(xué)基金資助項(xiàng)目（No. BK20131069）Foundation Items: The National Key Research and Development Program of China (No.2017YFB0802900

6、), The Natural Science Foundation of Jiangsu Province (No. BK20131069)Android系統(tǒng)的普及使Android應(yīng)用的數(shù)量和種類呈爆發(fā)式增長(zhǎng)。據(jù)Statista的數(shù)據(jù)統(tǒng)計(jì)，2017年3月，僅Google play上的Android應(yīng)用就達(dá)2.8106多個(gè)，比2015年增長(zhǎng)了近1106個(gè)1。面對(duì)海量的Android應(yīng)用，安全人員可能需要分析程序?qū)ふ衣┒椿蚺袛喑绦蚴欠裼袗阂庑袨?；開(kāi)發(fā)者傾向于復(fù)用已有的程序模塊。而大多數(shù)情況下，分析者接觸到的都是編譯后的應(yīng)用，需要分析程序安裝包（APK，Android package）中的代碼文件（

7、字節(jié)碼文件和原生庫(kù)文件）獲取有用的信息。因此，人們對(duì)高效的Android應(yīng)用分析方法和技術(shù)的需求更加迫切?？刂屏鲌D在程序逆向和分析領(lǐng)域中應(yīng)用十分廣泛。編譯后的程序丟失了很多源代碼中數(shù)據(jù)和代碼結(jié)構(gòu)的信息，間接跳轉(zhuǎn)、不可執(zhí)行的數(shù)據(jù)塊、代碼段對(duì)齊等使反匯編變得困難?？刂屏鲌D有助于解決這些棘手的問(wèn)題2,3。并且控制流圖是數(shù)據(jù)流分析、數(shù)據(jù)依賴分析、程序切片等其他分析方法的基礎(chǔ)4,5，也可作為區(qū)分惡意和非惡意代碼的特征6,7。00178-2傳統(tǒng)的控制流圖提取方法正被逐漸移植到Android應(yīng)用程序的分析過(guò)程中。但由于Android應(yīng)用程序與PC程序的結(jié)構(gòu)和運(yùn)行環(huán)境存在較大差別，這些方法817不能直接用于構(gòu)

8、造Android應(yīng)用的控制流圖。目前，針對(duì)Android應(yīng)用的工作1820主要關(guān)注Dalvik字節(jié)碼（簡(jiǎn)稱字節(jié)碼）的控制流圖提取方法，缺乏對(duì)原生庫(kù)代碼的研究。而越來(lái)越多的Android程序在原生庫(kù)中完成一些重要和復(fù)雜的功能，如加密、加殼等。惡意代碼也開(kāi)始傾向于隱藏在原生庫(kù)中以逃避檢測(cè)，如“百腦蟲(chóng)”“蜥蜴之尾”等木馬都將其惡意邏輯隱藏在原生庫(kù)中，因此僅分析字節(jié)碼并不能完整地了解Android應(yīng)用的真實(shí)行為。針對(duì)上述問(wèn)題，本文深入分析了Android應(yīng)用原生代碼的特點(diǎn)，提出了一種基于符號(hào)執(zhí)行的控制流圖提取方法，設(shè)計(jì)并實(shí)現(xiàn)了原型系統(tǒng)，主要貢獻(xiàn)如下。1) 提出了一種基于符號(hào)執(zhí)行的控制流圖提取方法，符號(hào)

9、執(zhí)行過(guò)程基于中間表示VEX。該方法與平臺(tái)無(wú)關(guān)，可以用來(lái)分析為多種平臺(tái)編譯的Android原生代碼。2) 深入分析系統(tǒng)的JNI特性，對(duì)系統(tǒng)JNI相關(guān)的結(jié)構(gòu)和JNI函數(shù)進(jìn)行模擬，使本文方法能準(zhǔn)確識(shí)別原生代碼中的原生方法和JNI函數(shù)調(diào)用。3) 基于angr設(shè)計(jì)并實(shí)現(xiàn)了用于提取Android原生庫(kù)控制流圖的原型系統(tǒng)CFGNative，該系統(tǒng)能自動(dòng)識(shí)別導(dǎo)出函數(shù)和注冊(cè)的原生方法，并將其作為控制流圖的起點(diǎn)。CFGNative為用戶及現(xiàn)有的Dalvik字節(jié)碼分析工具提供了接口，以便于分析者結(jié)合CFGNative和字節(jié)碼的分析工具提取全部應(yīng)用的控制流圖或基于該系統(tǒng)實(shí)現(xiàn)其他的程序分析方法。2 背景2.1 Andr

10、oid應(yīng)用和JNI函數(shù)調(diào)用本文分析的對(duì)象是編譯打包后的APK。APK中主要包含Java代碼編譯后生成的Dalvik字節(jié)碼文件（后綴為dex），C/C+代碼編譯后的針對(duì)不同平臺(tái)的原生庫(kù)文件（后綴為so）、資源文件和AndroidManifest.xml文件。APK中的可執(zhí)行文件為字節(jié)碼文件和原生庫(kù)文件。字節(jié)碼運(yùn)行在Dalvik虛擬機(jī)上，原生代碼直接運(yùn)行在Linux系統(tǒng)上。Android應(yīng)用中的字節(jié)碼和原生代碼可以通過(guò)JNI通信和相互調(diào)用。JNI是Java程序設(shè)計(jì)語(yǔ)言功能最強(qiáng)的特性，它允許Java類的某些方法原生實(shí)現(xiàn)，同時(shí)讓它們能夠像普通Java方法一樣被調(diào)用21。Android的Dalvik虛擬

11、機(jī)也支持Java的JNI特性。Dalvik字節(jié)碼需調(diào)用System. loadLibrary方法加載包含原生方法的原生庫(kù)文件，并且用關(guān)鍵字native聲明原生方法，之后才能調(diào)用原生方法。原生庫(kù)按照注冊(cè)規(guī)則向Dalvik虛擬機(jī)注冊(cè)暴露給字節(jié)碼的原生方法。原生方法需在字節(jié)碼中用關(guān)鍵字native進(jìn)行聲明，Dalvik虛擬機(jī)調(diào)用原生方法時(shí)，在原生庫(kù)中找到與這些聲明對(duì)應(yīng)的方法實(shí)體，并傳遞參數(shù)JNI接口指針的地址（如JNIEnv指針）和實(shí)例引用或類引用（若該原生方法是實(shí)例方法則傳入實(shí)例引用，若為靜態(tài)方法則傳入類引用）。原生庫(kù)中的代碼通過(guò)指向JNI接口的指針獲取JNI函數(shù)（或JNI接口函數(shù)）的地址，然后調(diào)

12、用JNI函數(shù)與字節(jié)碼進(jìn)行數(shù)據(jù)交換，如訪問(wèn)Java類的字段、創(chuàng)建類的實(shí)例、調(diào)用類和實(shí)例的方法等。JNI函數(shù)調(diào)用過(guò)程示例匯編代碼如下。.text:00000D34 MOV R4, R0.text:00000D38 LDR R3, R0.text:00000D3C BEQ loc_E60.text:00000D40 LDR R1, = (aAndroidContent - 0xD50).text:00000D44 LDR R3, R3,#0x18.text:00000D48 ADD R1, PC, R1 ; android/content/Context.text:00000D4C BLX R3.t

13、ext:00000D50 SUBS R5, R0, #0.text:00000D54 BEQ loc_E74.text:00000D58 LDR R12, R4.text:00000D5C MOV R0, R4.text:00000D60 LDR R2, = (aGetsystemservi - 0xD74).text:00000D64 MOV R1, R5.text:00000D68 LDR R3, = (aLjavaLangStrin - 0xD7C).text:00000D6C ADD R2, PC, R2 ; getSystemService.text:00000D70 LDR R12

14、, R12,#0x84.text:00000D74 ADD R3, PC, R3 ; (Ljava/lang/String;)Ljava/lang/Object;.text:00000D78 BLX R12根據(jù)函數(shù)調(diào)用規(guī)約，R0傳遞參數(shù)JNIEnv指針，因此代碼00000D38處的R3寄存器和00000D58處的R12寄存器存儲(chǔ)的是JNIEnv的值。JNIEnv是一個(gè)接口指針，該接口結(jié)構(gòu)中包含JNI函數(shù)表，通過(guò)JNIEnv和相對(duì)偏移可以訪問(wèn)函數(shù)表。相對(duì)JNIEnv偏移0x18的地址上存儲(chǔ)的是JNI函數(shù)FindClass的地址。程序在00000D44處獲取FindClass的地址，并通過(guò)0000

15、0D4C處的間接跳轉(zhuǎn)指令調(diào)用該JNI函數(shù)得到android/content/ Context類的引用，在00000D70處獲取存儲(chǔ)在相對(duì)JNIEnv偏移0x84地址上的JNI函數(shù)GetMethodID的地址，00000D78處的間接跳轉(zhuǎn)指令調(diào)用GetMethodID得到android/content/Context的getSystemService方法的引用。傳統(tǒng)的控制流圖提取方法不能解析程序中的JNI函數(shù)調(diào)用過(guò)程，因此不能直接用來(lái)提取Android原生代碼的控制流圖。2.2 中間表示VEX隨著嵌入式平臺(tái)的發(fā)展，Android系統(tǒng)的底層平臺(tái)也更加多樣，現(xiàn)在市場(chǎng)上主要的架構(gòu)有ARM、X86、AM

16、D64和MIPS，所以原生庫(kù)可能是不同平臺(tái)的目標(biāo)文件，使用不同的指令集。為了使本文方法與平臺(tái)無(wú)關(guān)，將原生庫(kù)中的指令轉(zhuǎn)化為中間表示，在中間表示上進(jìn)行符號(hào)執(zhí)行。00178-3本文使用的中間表示是VEX22。VEX是一種較成熟的平臺(tái)無(wú)關(guān)的中間語(yǔ)言，使用廣泛，已經(jīng)被實(shí)踐證明能較好地兼容多種平臺(tái)（包括Android系統(tǒng)中可能使用的幾種平臺(tái)）。一些經(jīng)典的二進(jìn)制分析平臺(tái)，如Valgrid23、angr24，將二進(jìn)制碼轉(zhuǎn)化為中間表示VEX，再基于VEX進(jìn)行程序分析。第3.3節(jié)將詳細(xì)介紹VEX在符號(hào)執(zhí)行過(guò)程中的作用。圖1為32 bit ARM指令轉(zhuǎn)化為VEX的示例，圖1左側(cè)是ARM指令，將寄存器R2中的值減8再

17、存入R2寄存器。圖1右側(cè)是轉(zhuǎn)化得到的VEX語(yǔ)句，先將R2的值賦給變量t0，使變量t1取值8，再將變量t0和t1的差賦給變量t3，然后把t3的值存儲(chǔ)到寄存器R2中，最后將下一條指令的地址0x59FC8存入IP寄存器。圖1 ARM指令轉(zhuǎn)化為VEX示例3 基于符號(hào)執(zhí)行的控制流圖提取方法以原生庫(kù)文件的導(dǎo)出函數(shù)（一般包括靜態(tài)注冊(cè)的原生方法一般會(huì)出現(xiàn)在導(dǎo)出函數(shù)表中）和動(dòng)態(tài)注冊(cè)的原生方法為符號(hào)執(zhí)行的起點(diǎn)，控制流圖的提取過(guò)程如圖2所示。首先為每個(gè)起點(diǎn)初始化程序狀態(tài)，在程序狀態(tài)中模擬JNI相關(guān)結(jié)構(gòu)（JNIEnv、JavaVM、JNIInvokeInterface和JNINativeInterface），將無(wú)法確

18、定的參數(shù)初始化為符號(hào)值；然后從起點(diǎn)開(kāi)始符號(hào)執(zhí)行。遇到跳轉(zhuǎn)指令時(shí)，若跳轉(zhuǎn)地址是JNI相關(guān)結(jié)構(gòu)中的JNI函數(shù)地址，則執(zhí)行模擬JNI函數(shù)的SimProcedure，再返回符號(hào)執(zhí)行過(guò)程；否則從跳轉(zhuǎn)地址繼續(xù)符號(hào)執(zhí)行。圖2 控制流圖提取過(guò)程3.1 程序控制流圖按照馮諾依曼體系結(jié)構(gòu)，無(wú)跳轉(zhuǎn)指令時(shí)，程序執(zhí)行完一條指令后，緊接著在內(nèi)存中取下一條指令繼續(xù)執(zhí)行，這種執(zhí)行順序被稱為順序執(zhí)行。程序的執(zhí)行流程有順序、分支和循環(huán)這3種。分支和循環(huán)都是由跳轉(zhuǎn)指令破壞當(dāng)前的順序執(zhí)行實(shí)現(xiàn)的。把連續(xù)的順序執(zhí)行的指令集合作為一個(gè)基本塊，將基本塊作為控制流圖的節(jié)點(diǎn)，跳轉(zhuǎn)語(yǔ)句導(dǎo)致的基本塊之間的控制流遷移為控制流圖的邊。因此，提取控制流圖

19、的重點(diǎn)和難點(diǎn)是計(jì)算跳轉(zhuǎn)地址（跳轉(zhuǎn)指令實(shí)現(xiàn)跳轉(zhuǎn)后，程序繼續(xù)執(zhí)行的地址）。3.1.1 跳轉(zhuǎn)指令每種指令集中都有跳轉(zhuǎn)指令，這些指令可以使程序接著執(zhí)行跳轉(zhuǎn)地址處的指令，而非順序執(zhí)行下一條指令。按跳轉(zhuǎn)是否需要條件可將跳轉(zhuǎn)指令分為強(qiáng)制跳轉(zhuǎn)指令和條件跳轉(zhuǎn)指令。一定會(huì)發(fā)生跳轉(zhuǎn)的指令為強(qiáng)制跳轉(zhuǎn)指令，如X86指令集中的CALL、JMP指令，ARM指令集中的B、BL指令，以及直接給PC賦值的指令，如LDR PC、Expr。當(dāng)滿足特定條件才跳轉(zhuǎn)的指令為條件跳轉(zhuǎn)指令，如X86指令集中的JE、JNE指令，ARM指令集中的BE、BNE指令。按跳轉(zhuǎn)地址的取值方式可以將跳轉(zhuǎn)指令分為直接跳轉(zhuǎn)指令和間接跳轉(zhuǎn)指令。直接跳轉(zhuǎn)指令將跳轉(zhuǎn)

20、地址直接編碼到指令中，而間接跳轉(zhuǎn)指令的跳轉(zhuǎn)地址依賴于寄存器或內(nèi)存中的值。每一條跳轉(zhuǎn)指令都可以表示為jmpaddr(target, guard)的形式，其中，addr是跳轉(zhuǎn)指令所在的地址，target是跳轉(zhuǎn)地址，guard是跳轉(zhuǎn)的條件?？刂屏鲌D的準(zhǔn)確性和完整性很大程度上依賴于跳轉(zhuǎn)地址計(jì)算的準(zhǔn)確性。跳轉(zhuǎn)指令將PC的值置為跳轉(zhuǎn)地址而非順序執(zhí)行的下一條指令地址，同時(shí)還可能改變內(nèi)存或其他寄存器的值，如CALL指令在程序跳轉(zhuǎn)前會(huì)將順序執(zhí)行的下一條指令的地址壓入堆棧，BL指令會(huì)將順序執(zhí)行的下一條指令存儲(chǔ)到R14寄存器中。因此可以將跳轉(zhuǎn)指令抽象為改變程序狀態(tài)（寄存器和內(nèi)存的取值情況）的函數(shù)，第3.3.2節(jié)會(huì)進(jìn)

21、一步介紹。3.1.2 基本塊00178-4本文將指令轉(zhuǎn)化為中間表示VEX，因此控制流圖的基本塊是連續(xù)且順序執(zhí)行VEX語(yǔ)句的集合。定義1 指令ins的長(zhǎng)度記為，所在地址記為。若ins為跳轉(zhuǎn)指令， ，否則。若指令使函數(shù)結(jié)束，否則。指令序列為一個(gè)指令基本塊，當(dāng)該指令序列中的指令滿足條件將iseq中的指令全部轉(zhuǎn)換為VEX語(yǔ)句得到的語(yǔ)句序列為VEX基本塊。根據(jù)定義可以推斷基本塊（除起始?jí)K）的起始地址都是某一條跳轉(zhuǎn)語(yǔ)句的跳轉(zhuǎn)地址，基本塊（除結(jié)束塊）的最后一條指令都是跳轉(zhuǎn)語(yǔ)句。只能從基本塊第一條語(yǔ)句開(kāi)始執(zhí)行，且一旦開(kāi)始必然順序執(zhí)行到該基本塊中最后一條指令。3.1.3 控制流圖本文的目的是分析程序控制流的遷移

22、，并將其表示為由基本塊和邊構(gòu)成的控制流圖。定義2 任意一個(gè)Android庫(kù)文件P的指令都可以被劃分為多個(gè)基本塊，這些基本塊的集合記為。2個(gè)基本塊b1和b2間存在數(shù)據(jù)流遷移，當(dāng)且僅當(dāng)其中，為b1中最后一條指令，為b2中第一條指令。定義3 稱為P的一個(gè)控制流圖（N是控制流圖中節(jié)點(diǎn)的集合，E是控制流圖中邊的集合），當(dāng)且僅當(dāng)在中，b為中指令基本塊，n為VEX語(yǔ)句基本塊，即將b中的每一條指令轉(zhuǎn)化為VEX語(yǔ)句得到的結(jié)果。定義4 P沒(méi)有main函數(shù)，本文從導(dǎo)出函數(shù)和不出現(xiàn)在導(dǎo)出表中的原生方法開(kāi)始提取控制流圖。給控制流圖增加2個(gè)特殊節(jié)點(diǎn)和若干邊，控制流圖中其他節(jié)點(diǎn)和邊的約束依然滿足定義3，得到。其中，為入口節(jié)

23、點(diǎn)，為的結(jié)束節(jié)點(diǎn)。P中導(dǎo)出函數(shù)和不出現(xiàn)在導(dǎo)出表中原生方法的第一個(gè)基本塊的集合記為，當(dāng)n中最后一條語(yǔ)句為函數(shù)結(jié)束語(yǔ)句時(shí)，、否則。本文提取的是滿足定義的控制流圖。3.2 模擬JNI函數(shù)調(diào)用如2.1節(jié)所述，原生方法通過(guò)間接跳轉(zhuǎn)調(diào)用JNI函數(shù)，而傳統(tǒng)的控制流圖提取方法沒(méi)有將原生方法的第一個(gè)參數(shù)解析為JNI接口指針地址，也不能解析JNI接口的結(jié)構(gòu)，因此無(wú)法計(jì)算出JNI函數(shù)調(diào)用的間接跳轉(zhuǎn)地址。對(duì)此，本文方法在程序狀態(tài)中模擬JNI接口指針等JNI相關(guān)結(jié)構(gòu)，找到向虛擬機(jī)注冊(cè)的原生方法，然后將JNI接口指針的地址傳遞給原生方法。當(dāng)符號(hào)執(zhí)行遇到JNI函數(shù)調(diào)用的間接跳轉(zhuǎn)指令時(shí)，即可根據(jù)模擬的JNI相關(guān)結(jié)構(gòu)計(jì)算得到函

24、數(shù)表中的JNI函數(shù)地址。另外，APK的原生庫(kù)中沒(méi)有JNI函數(shù)的指令，無(wú)法符號(hào)執(zhí)行JNI函數(shù)，本文方法用SimProcedure代替符號(hào)執(zhí)行過(guò)程。3.2.1 模擬JNI相關(guān)結(jié)構(gòu)00178-5JNI相關(guān)結(jié)構(gòu)包括JNIEnv、JavaVM、JNIInvokeInterface和JNINativeInterface。Dalvik虛擬機(jī)將JNIEnv的地址作為第一個(gè)參數(shù)傳遞給原生方法（JavaVM的地址是JNI_OnLoad的第一個(gè)參數(shù)）。JNIInvokeInterface和JNINativeInterface是JNI接口類型，分別包含一個(gè)函數(shù)表，函數(shù)表中包含的是JNI函數(shù)的地址。原生代碼通過(guò)函數(shù)表中

25、的函數(shù)訪問(wèn)虛擬機(jī)或字節(jié)碼中的內(nèi)容。JavaVM指向的正是JNIInvokeInterface的起始地址，JNIEnv指向的正是JNINativeInterface的起始地址，因此原生方法通過(guò)參數(shù)和相對(duì)偏移即可找到函數(shù)表中某一JNI函數(shù)表項(xiàng)的地址，從而得到該JNI函數(shù)的地址。JNIEnv、JavaVM、JNIInvokeInterface和JNINativeInterface在內(nèi)存中的結(jié)構(gòu)如圖3所示。圖3 內(nèi)存中JNINativeInterface和JNIInvokeInterface的結(jié)構(gòu)本文分析的原生庫(kù)中不包含這些結(jié)構(gòu)，也不會(huì)在內(nèi)存中構(gòu)造該結(jié)構(gòu)，因此，在符號(hào)執(zhí)行前需要在程序狀態(tài)的內(nèi)存中模擬該

26、結(jié)構(gòu)。在內(nèi)存中開(kāi)辟一塊未使用的空間給JavaVM、JNIEnv、JNIInvokeInterface和JNINativeInterface，在開(kāi)辟的空間中填入任意未使用地址空間中的地址，執(zhí)行過(guò)程中自動(dòng)將JavaVM和JNIEnv的地址作為參數(shù)傳遞給原生方法。3.2.2 SimProcedure模擬JNI函數(shù)除了模擬JNI相關(guān)結(jié)構(gòu)，還需要模擬接口函數(shù)表中的JNI函數(shù)。在真實(shí)的Android原生庫(kù)運(yùn)行環(huán)境中，原生方法通過(guò)Dalvik虛擬機(jī)調(diào)用JNI函數(shù)，本文符號(hào)執(zhí)行過(guò)程中既無(wú)虛擬機(jī)也無(wú)JNI函數(shù)，需要用SimProcedure對(duì)JNI函數(shù)的功能進(jìn)行抽象和模擬，并且用SimProcedure hoo

27、k JNI函數(shù)的地址，使執(zhí)行到JNI函數(shù)時(shí)，相應(yīng)的SimProcedure能被調(diào)用。SimProcedure是指用來(lái)模擬JNI函數(shù)的一類函數(shù)，概括了JNI函數(shù)的程序邏輯，是程序執(zhí)行過(guò)程中實(shí)現(xiàn)JNI函數(shù)對(duì)程序狀態(tài)的改變以及相應(yīng)控制流圖節(jié)點(diǎn)構(gòu)造的實(shí)體。SimProcedure不是原生庫(kù)中的代碼，因此其構(gòu)造的節(jié)點(diǎn)只用于記錄該處JNI函數(shù)調(diào)用的信息，不包含真實(shí)代碼對(duì)應(yīng)的VEX語(yǔ)句。JNIInvokeInterface和JNINativeInterface的函數(shù)表中的每個(gè)函數(shù)都對(duì)應(yīng)一個(gè)SimProcedure。有的JNI函數(shù)會(huì)返回字節(jié)碼的類、對(duì)象、字段、方法等的引用，后續(xù)JNI函數(shù)調(diào)用中可能會(huì)使用這些返

28、回值。而執(zhí)行環(huán)境中不存在字節(jié)碼中的結(jié)構(gòu)，這些結(jié)構(gòu)的引用只是標(biāo)識(shí)它們的符號(hào)。因此，這些字節(jié)碼內(nèi)容的引用是全局的，且在定義SimProcedure時(shí)，應(yīng)該考慮JNI函數(shù)之間的關(guān)系，使其他SimProcedure也能夠準(zhǔn)確識(shí)別這些標(biāo)識(shí)。如FindClass的SimProcedure需要返回一個(gè)標(biāo)識(shí)以表示類名為傳入的第二個(gè)參數(shù)的類，在符號(hào)執(zhí)行過(guò)程中，其他JNI函數(shù)在遇到這個(gè)標(biāo)識(shí)時(shí)也應(yīng)該將其解釋為這個(gè)類。先構(gòu)造圖3的結(jié)構(gòu)，再用對(duì)應(yīng)的SimProcedure hook JNI接口函數(shù)表中填入的地址。執(zhí)行過(guò)程中，當(dāng)原生方法調(diào)用函數(shù)表中的JNI函數(shù)時(shí)，找到的JNI函數(shù)地址實(shí)際上是被SimProcedure h

29、ook的地址，因此執(zhí)行的是SimProcedure，執(zhí)行完SimProcedure后返回調(diào)用JNI函數(shù)的下一條指令繼續(xù)執(zhí)行。3.2.3 定位注冊(cè)的原生方法本文的符號(hào)執(zhí)行要自動(dòng)將JNIEnv的地址作為參數(shù)傳遞給原生方法，因此需要其能夠識(shí)別注冊(cè)的原生方法。注冊(cè)原生方法的方式分為靜態(tài)注冊(cè)和動(dòng)態(tài)注冊(cè)這2種。靜態(tài)注冊(cè)需要根據(jù)命名規(guī)則命名原生方法，要求用包名加上類名再加上字節(jié)碼中聲明的方法名來(lái)命名原生庫(kù)中對(duì)應(yīng)的原生方法，如應(yīng)將與android.helloWorld包的MainActivity類中聲明的原生方法helloFromJNI對(duì)應(yīng)的原生庫(kù)中的方法命名為Java_android_helloWorld_

30、 MainActivity_helloFromJNI。符號(hào)表中一般都包含靜態(tài)注冊(cè)的原生方法，因此可以通過(guò)符號(hào)表中函數(shù)名識(shí)別原生函數(shù)。而動(dòng)態(tài)注冊(cè)將原生方法與其在字節(jié)碼中聲明的對(duì)應(yīng)關(guān)系記錄到JNINativeMethod結(jié)構(gòu)中，再通過(guò)調(diào)用JNINativeInterface中的RegisterNatives函數(shù)將JNINativeMethod中的原生方法注冊(cè)到虛擬機(jī)。JNINativeMethod的結(jié)構(gòu)如下所示。00178-6typedef struct const char* name; const char* signature; void* fnPtr; JNINativeMethod;該結(jié)

31、構(gòu)有3個(gè)字段，分別為字節(jié)碼中聲明的原生方法的名稱、參數(shù)和返回值的類型信息以及原生方法在原生庫(kù)中的地址。若執(zhí)行過(guò)程中調(diào)用了RegisterNatives函數(shù)，從參數(shù)中可得到JNINativeMethod結(jié)構(gòu)的列表在內(nèi)存中的地址和列表長(zhǎng)度，解析該列表獲得動(dòng)態(tài)注冊(cè)的原生方法，該過(guò)程由RegisterNatives函數(shù)的SimProcedure完成。動(dòng)態(tài)注冊(cè)需要在字節(jié)碼調(diào)用原生方法之前完成。JNI_OnLoad在原生庫(kù)加載時(shí)被調(diào)用。通常在JNI_OnLoad中調(diào)用RegisterNatives，動(dòng)態(tài)注冊(cè)過(guò)程就會(huì)在原生庫(kù)加載時(shí)完成。因此，如果原生庫(kù)中實(shí)現(xiàn)了JNI_OnLoad方法，應(yīng)該優(yōu)先執(zhí)行JNI_O

32、nLoad以找到可能出現(xiàn)的動(dòng)態(tài)注冊(cè)的原生方法。3.3 提取控制流圖本文分析的對(duì)象是Android原生庫(kù)文件，而原生庫(kù)不可單獨(dú)執(zhí)行，如果直接進(jìn)行動(dòng)態(tài)分析，則需要實(shí)現(xiàn)觸發(fā)原生庫(kù)執(zhí)行的模塊。而Android應(yīng)用中調(diào)用原生方法的是字節(jié)碼，因此需要搭建兩層執(zhí)行環(huán)境（包括Dalvik虛擬機(jī)），使環(huán)境比較復(fù)雜，并且有時(shí)需要構(gòu)造復(fù)雜的輸入才能觸發(fā)原生庫(kù)中代碼的執(zhí)行，分析效率較低。為此本文提出了一種基于VEX的符號(hào)執(zhí)行方法，直接分析Android原生庫(kù)，提取控制流圖。只要構(gòu)造了函數(shù)的執(zhí)行環(huán)境，該方法便可單獨(dú)執(zhí)行某一個(gè)函數(shù)，無(wú)需從main函數(shù)開(kāi)始執(zhí)行。符號(hào)執(zhí)行的環(huán)境由angr25提供，angr將指令轉(zhuǎn)化為中間表示

33、VEX，符號(hào)執(zhí)行引擎根據(jù)VEX表達(dá)式和語(yǔ)句的語(yǔ)義修改程序狀態(tài)，并記錄下路徑的約束條件，當(dāng)遇到跳轉(zhuǎn)語(yǔ)句時(shí)根據(jù)程序狀態(tài)和約束條件計(jì)算跳轉(zhuǎn)地址。3.3.1 程序狀態(tài)程序狀態(tài)主要包含程序在某一程序點(diǎn)內(nèi)存、寄存器、變量（VEX中含有變量）的取值情況。將VEX中寄存器的集合記為Regs，內(nèi)存區(qū)域記為Mems，臨時(shí)變量的集合記為T(mén)mps。符號(hào)執(zhí)行的程序狀態(tài)中有具體值和符號(hào)值。將具體值（如立即數(shù)0x10、地址0x400000等）的集合記為Cons。符號(hào)值表示滿足一定約束的值的集合，用符號(hào)（如x、y等）表示。符號(hào)值在執(zhí)行中也可參與運(yùn)算，如x+y、x+0x10等。將符號(hào)值的集合記為Syms。因此程序狀態(tài)中寄存器、

34、內(nèi)存和變量取值的值域?yàn)?。原生?kù)中函數(shù)按函數(shù)調(diào)用規(guī)約接收參數(shù)，且除JavaVM和JNIEnv的地址外，其他參數(shù)在分析者沒(méi)有指明的情況下都默認(rèn)取符號(hào)值。只要構(gòu)造一個(gè)函數(shù)被調(diào)用時(shí)的程序狀態(tài)并將該狀態(tài)輸入符號(hào)執(zhí)行引擎，就能從該函數(shù)開(kāi)始符號(hào)執(zhí)行，因此需要初始化原生函數(shù)和其他導(dǎo)出函數(shù)開(kāi)始執(zhí)行時(shí)的程序狀態(tài)，如將參數(shù)賦值給傳遞參數(shù)的寄存器。定義5 程序狀態(tài)state用二元組的集合表示，實(shí)際上為內(nèi)存、寄存器和變量到Vals上的映射。當(dāng)程序狀態(tài)中有二元組（a，val）時(shí)，則說(shuō)明該狀態(tài)下a的取值為val。Mems理論上是無(wú)窮且連續(xù)的，但程序執(zhí)行過(guò)程中各類型變量的值一般存儲(chǔ)在一塊連續(xù)的內(nèi)存區(qū)域中。將該段內(nèi)存中的值作為

35、Vals中的一個(gè)元素，內(nèi)存即可被看作離散的。另外，運(yùn)行程序所需的內(nèi)存空間有限，未使用的內(nèi)存只是概念上的一塊區(qū)域，在符號(hào)執(zhí)行過(guò)程中并不分配空間以記錄其狀態(tài)，因此記錄和讀取內(nèi)存是可實(shí)現(xiàn)的。3.3.2 表達(dá)式和語(yǔ)句符號(hào)執(zhí)行是在VEX上進(jìn)行的，因此需要告知執(zhí)行引擎VEX表達(dá)式和語(yǔ)句的語(yǔ)義，執(zhí)行引擎才能按照語(yǔ)義執(zhí)行程序。定義6 將表達(dá)式的集合記為Exprs，語(yǔ)句的集合記為Stmts。表達(dá)式的語(yǔ)義為表達(dá)式和程序狀態(tài)到Vals上的函數(shù)fe，語(yǔ)句的語(yǔ)義為語(yǔ)句和程序狀態(tài)到新的程序狀態(tài)上的函數(shù)fs。表示表達(dá)式expr在當(dāng)前程序狀態(tài)state取值val。表示語(yǔ)句stmt將當(dāng)前狀態(tài)變成了新的程序狀態(tài)。00178-7V

36、EX語(yǔ)句和表達(dá)式的語(yǔ)義要根據(jù)具體的表達(dá)式和語(yǔ)句定義，如表達(dá)式RdTmp(t10)的語(yǔ)義為變量t10的取值，語(yǔ)句WrTmp(t1)=(IR expr)的語(yǔ)義為將表達(dá)式expr的值賦給t1得到新的程序狀態(tài)。VEX的表達(dá)式和語(yǔ)句的詳細(xì)介紹參考文獻(xiàn)22。3.3.3 求解帶符號(hào)的跳轉(zhuǎn)地址符號(hào)執(zhí)行過(guò)程中可能存在帶有符號(hào)的跳轉(zhuǎn)地址。執(zhí)行過(guò)程在程序狀態(tài)中記錄了每一條分支對(duì)符號(hào)的約束。當(dāng)遇到地址帶有符號(hào)的跳轉(zhuǎn)指令時(shí)，用約束求解器求解該符號(hào)的約束得到符號(hào)值的范圍，計(jì)算得到可能的跳轉(zhuǎn)地址，然后判斷這些可能的跳轉(zhuǎn)地址是否為指令的起始地址，將滿足條件的值列入最終跳轉(zhuǎn)地址結(jié)果的集合中。3.3.4 控制流圖提取算法基于上述

37、討論，控制流圖提取算法的偽代碼如下。 代碼第3)9)行為算法初始階段，其中，第3)行從導(dǎo)出表中獲取導(dǎo)出函數(shù)地址；第4)行獲取導(dǎo)出函數(shù)中JNI_OnLoad的地址，若不存在則為空；第5)行識(shí)別導(dǎo)出函數(shù)中靜態(tài)注冊(cè)的原生方法；第7)行將導(dǎo)出函數(shù)地址加入到工作列表中。00178-8圖4 CFGNative體系結(jié)構(gòu)第10)30)行代碼開(kāi)始循環(huán)，從工作列表中取出地址，如果該地址為JNI函數(shù)的地址，第13)行代碼調(diào)用JNI函數(shù)對(duì)應(yīng)的SimProcedure，若調(diào)用的JNI函數(shù)是RegisterNatives，則可以找到動(dòng)態(tài)注冊(cè)的原生方法，第15)行將新找到的動(dòng)態(tài)注冊(cè)的原生方法的地址加入工作列表中；如果該地址

38、不是JNI函數(shù)的地址，則執(zhí)行第18)29)行。第18)行得到起始地址為addr的VEX基本塊。第23)行獲取VEX基本塊開(kāi)始符號(hào)執(zhí)行時(shí)的程序狀態(tài)，需要為函數(shù)的起始?jí)K初始化程序狀態(tài)，從程序狀態(tài)集合中獲取其他VEX基本塊對(duì)應(yīng)的程序狀態(tài)。如果基本塊屬于原生方法，初始化程序狀態(tài)時(shí)要在內(nèi)存中模擬JNI相關(guān)結(jié)構(gòu)。第24)行得到VEX表達(dá)式和語(yǔ)句的語(yǔ)義。第25)行為符號(hào)執(zhí)行過(guò)程，第26)29)行計(jì)算跳轉(zhuǎn)地址，將以跳轉(zhuǎn)地址為起點(diǎn)的基本塊對(duì)應(yīng)的程序狀態(tài)加入程序狀態(tài)集合，并將跳轉(zhuǎn)地址加入工作列表。循環(huán)整個(gè)過(guò)程直到工作列表為空。4 原型系統(tǒng)實(shí)現(xiàn)與實(shí)驗(yàn)4.1 系統(tǒng)實(shí)現(xiàn)為了驗(yàn)證本文所提方法的有效性，基于angr實(shí)現(xiàn)了提

39、取Android原生庫(kù)的控制流圖的原型系統(tǒng)CFGNative，其結(jié)構(gòu)如圖4所示。系統(tǒng)中，模塊loader解析輸入的原生庫(kù)文件，并將代碼段和數(shù)據(jù)段加載到內(nèi)存中；lifter從給定的地址開(kāi)始識(shí)別并翻譯VEX基本塊；execution simulator在lifter識(shí)別的VEX基本塊上進(jìn)行符號(hào)執(zhí)行并將計(jì)算得到的跳轉(zhuǎn)地址給lifter，lifter從新的地址開(kāi)始繼續(xù)識(shí)別VEX基本塊，迭代該過(guò)程直到?jīng)]有新的VEX基本塊生成；state記錄執(zhí)行各階段的程序狀態(tài)；core engine是符號(hào)執(zhí)行的核心模塊，逐條解析VEX語(yǔ)句的語(yǔ)義；JNI struct constructor在內(nèi)存中構(gòu)造JNIInvoke

40、Interface和JNINativeInterface等結(jié)構(gòu)；simprocedures被hook到JNI函數(shù)的地址上；constraint solver根據(jù)約束求解帶符號(hào)跳轉(zhuǎn)地址。4.2 實(shí)驗(yàn)及結(jié)果分析本文設(shè)計(jì)了2個(gè)實(shí)驗(yàn)：實(shí)驗(yàn)1用CFGAccurate提取本文構(gòu)造的Android（源碼見(jiàn)附錄A）應(yīng)用JNITest中原生庫(kù)的一個(gè)控制流圖，目的是檢測(cè)CFGAccurate是否能準(zhǔn)確識(shí)別靜態(tài)和動(dòng)態(tài)注冊(cè)的原生函數(shù)和JNI函數(shù)調(diào)用。實(shí)驗(yàn)2對(duì)比angr的CFGAccurate、IDA和CFGNative提取控制流圖的結(jié)果，目的是將CFGNative的指令覆蓋率和時(shí)間耗費(fèi)與現(xiàn)有經(jīng)典分析工具進(jìn)行對(duì)比，檢測(cè)

41、CFGNative增加的功能是否對(duì)其他性能造成過(guò)大影響。實(shí)驗(yàn)硬件配置為Intel(R) Core(TM) i7-3770處理器（8核3.40 GHz），32 GB RAM。操作系統(tǒng)為64 bit的Ubuntu16.04。1) 實(shí)驗(yàn)1：JNITest原生方法分為靜態(tài)和動(dòng)態(tài)這2種注冊(cè)方式，因此JNITest中包含了2個(gè)原生方法，分別用2種不同的方式注冊(cè)，同時(shí)包含多個(gè)JNI函數(shù)調(diào)用，具有一定代表性。Java_com_example_test_MainActivity_getIMEI為靜態(tài)注冊(cè)的原生方法，通過(guò)JNI函數(shù)FindClass找到android.telephony.TelephonyMana

42、ger類，然后調(diào)用JNI函數(shù)GetMethodID獲得該類getDeviceId方法的引用，最后通過(guò)CallObjectMethod調(diào)用該方法獲取設(shè)備的IMEI。該方法中的JNI函數(shù)會(huì)使用其他JNI函數(shù)返回的結(jié)果，如FindClass返回的Java類的引用會(huì)作為GetMethodID的參數(shù)，因此可以測(cè)試SimProcedure的定義是否正確。helloJNI為動(dòng)態(tài)注冊(cè)的原生方法，通過(guò)在JNI_ONLoad中調(diào)用RegistaerNatives進(jìn)行注冊(cè)，該方法返回JNI函數(shù)NewStringUTF構(gòu)造的字符串“Hello from JNI”。CFGNative提取的控制流圖顯示其準(zhǔn)確識(shí)別了這2個(gè)

43、原生方法和所有的JNI函數(shù)調(diào)用，得到的控制流圖中共有8個(gè)代表JNI函數(shù)的節(jié)點(diǎn)，38條包含表示JNI函數(shù)節(jié)點(diǎn)的邊。代表JNI函數(shù)調(diào)用的節(jié)點(diǎn)和包含這些節(jié)點(diǎn)的邊的詳細(xì)信息見(jiàn)附錄B。2) 實(shí)驗(yàn)2：對(duì)比 00178-9實(shí)驗(yàn)2將Android應(yīng)用市場(chǎng)APPChina上下載量排名靠前的16個(gè)應(yīng)用作為樣本，過(guò)濾樣本原生庫(kù)中的廣告包、音視頻處理等第三方工具包，共收集了61個(gè)原生庫(kù)文件。表4為從每個(gè)應(yīng)用中收集的原生庫(kù)的個(gè)數(shù)，由于有些原生庫(kù)存在于多個(gè)包中，所以個(gè)數(shù)的總和大于61。從每個(gè)包中獲取的具體的原生庫(kù)見(jiàn)附錄C。用CFGNative提取這些原生庫(kù)的控制流圖，并與當(dāng)前最流行的二進(jìn)制分析工具IDA和angr的CFG

44、Accurate對(duì)比。IDA、CFGAccurate和CFGNative都以導(dǎo)出函數(shù)和不出現(xiàn)在導(dǎo)出函數(shù)表中的原生方法為起點(diǎn)構(gòu)造控制流圖，去掉編譯過(guò)程加入的一些函數(shù)，如_gnu_ Unwind_Resume。統(tǒng)計(jì)每種方法提取每個(gè)原生庫(kù)的控制流圖平均耗費(fèi)的時(shí)間和平均每個(gè)圖中節(jié)點(diǎn)個(gè)數(shù)、邊數(shù)和覆蓋的指令數(shù)，結(jié)果如表2所示。表1樣本中收集的原生庫(kù)個(gè)數(shù)包名原生庫(kù)個(gè)數(shù)com.qihoo360.mobilesafe1com.baidu.BaiduMap4com.baidu.input2com.storm.smart9com.pplive.androidphone4com.kugou.android6com.s

45、ankuai.meituan7com.qiyi.video7com.tencent.mtt11com.tencent.qqmusic17com.baidu.searchbox2com.tencent.qqpimsecure1com.baidu.homework1com.UCMobile1com.sina.weibo4com.tencent.mm1表2控制流圖提取結(jié)果方法平均數(shù)節(jié)點(diǎn)/個(gè)邊/條指令/條時(shí)間/sIDA559.801 413.413 592.310.45CFGAccurate(angr)740.161 322.193 057.91110.52CFGNative1 050.51 805.

46、793 602.49319CFGAccurate和IDA不具備分析JNI的能力，因此不能識(shí)別原生方法和JNI函數(shù)調(diào)用。CFGNative比其他2種方式識(shí)別了更多的節(jié)點(diǎn)，其中包含表示JNI函數(shù)的節(jié)點(diǎn)，這些節(jié)點(diǎn)的指令條數(shù)為0，從表2中可以看到，CFGNative比IDA和CFGAccurate覆蓋了更多的指令，這是因?yàn)镃FGNative識(shí)別了IDA和CFGAccurate無(wú)法識(shí)別的間接跳轉(zhuǎn)，從而發(fā)現(xiàn)了新的基本塊中的指令。實(shí)驗(yàn)結(jié)果表明，CFGNative不僅能夠識(shí)別JNI函數(shù)調(diào)用，且在可接受的時(shí)間內(nèi)具有較高的代碼覆蓋率。5 結(jié)束語(yǔ)本文提出了一種基于符號(hào)執(zhí)行的控制流圖提取方法，用于自動(dòng)提取Androi

47、d應(yīng)用原生代碼的控制流圖。該方法可以識(shí)別原生方法和JNI函數(shù)調(diào)用，準(zhǔn)確計(jì)算間接跳轉(zhuǎn)地址，且具有較高代碼覆蓋率。下一步研究包括以下2個(gè)方面。1) 符號(hào)執(zhí)行用SimProcedure代替真實(shí)的JNI函數(shù)調(diào)用，因此對(duì)SimProcedure定義的準(zhǔn)確性會(huì)影響符號(hào)執(zhí)行的結(jié)果。目前對(duì)SimProcedure的定義過(guò)于依賴經(jīng)驗(yàn)。未來(lái)工作將深入分析真實(shí)環(huán)境下JNI函數(shù)的行為并對(duì)其進(jìn)行更系統(tǒng)的建模。2) 符號(hào)執(zhí)行過(guò)程中包含的符號(hào)值過(guò)多或約束求解器的求解能力不足都可能導(dǎo)致求解所得的符號(hào)值范圍過(guò)大。當(dāng)包含符號(hào)的跳轉(zhuǎn)地址取值范圍過(guò)大時(shí)，可能會(huì)產(chǎn)生路徑爆炸問(wèn)題，需要進(jìn)一步研究該問(wèn)題的解決方案。附錄A 本文構(gòu)造的And

48、roid原碼#include #include #include #include jnitest.h#define LOGV(.) _android_log_print(ANDROID_ LOG_VERBOSE, com.exaple.test, _VA_ARGS_)#define LOGD(.) _android_log_print(ANDROID_ LOG_DEBUG, com.exaple.test, _VA_ARGS_)#define LOGI(.) _android_log_print(ANDROID_ LOG_INFO, com.exaple.test, _VA_ARGS_)#d

49、efine LOGW(.) _android_log_print(ANDROID_ LOG_WARN, com.exaple.test, _VA_ARGS_)#define LOGE(.) _android_log_print(ANDROID_ LOG_ERROR, com.exaple.test, _VA_ARGS_)JNIEnv *g_env;JavaVM *g_vm;jclass native_class;#ifndef NELEM /計(jì)算結(jié)構(gòu)元素個(gè)數(shù)# define NELEM(x) (int) (sizeof(x) / sizeof(x)0)00178-10#endif/靜態(tài)注冊(cè)的原

50、生方法getIMEIJNIEXPORT jstring Java_com_example_test_Main Activity_getIMEI(JNIEnv *env, jobject mContext) if(mContext = 0) return (*env)-NewStringUTF(env,+Error : Context is 0); jclass cls_context = (*env)-FindClass (env, android/content/Context); if(cls_context = 0) return (*env)-NewStringUTF(env,+ Error: FindClass Error); jmethodID getSystemService = (*env)- GetMethodID(env,cls_context,getSystemService,(Ljava/lang/String;)Ljava/lang/Object;); if(getSystemService = 0) return (*env)-NewStringUTF(env,+ Error : GetMethodID failed); jfieldID TELEPHONY_SERVICE = (*env)- GetStaticFie