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

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

2、類號：TP309文獻(xiàn)標(biāo)識碼：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基金項目：國家重點研發(fā)計劃基金資助項目（No.2017YFB0802900）；江蘇省自然科學(xué)基金資助項目（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ā)式增長。據(jù)Statista的數(shù)據(jù)統(tǒng)計，2017年3月，僅Google play上的Android應(yīng)用就達(dá)2.8106多個，比2015年增長了近1106個1。面對海量的Android應(yīng)用，安全人員可能需要分析程序?qū)ふ衣┒椿蚺袛喑绦蚴欠裼袗阂庑袨?；開發(fā)者傾向于復(fù)用已有的程序模塊。而大多數(shù)情況下，分析者接觸到的都是編譯后的應(yīng)用，需要分析程序安裝包（APK，Android package）中的代碼文件（

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

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

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

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

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

12、用JNI函數(shù)與字節(jié)碼進(jìn)行數(shù)據(jù)交換，如訪問Java類的字段、創(chuàng)建類的實例、調(diào)用類和實例的方法等。JNI函數(shù)調(diào)用過程示例匯編代碼如下。.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寄存器存儲的是JNIEnv的值。JNIEnv是一個接口指針，該接口結(jié)構(gòu)中包含JNI函數(shù)表，通過JNIEnv和相對偏移可以訪問函數(shù)表。相對JNIEnv偏移0x18的地址上存儲的是JNI函數(shù)FindClass的地址。程序在00000D44處獲取FindClass的地址，并通過0000

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

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

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

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

19、的重點和難點是計算跳轉(zhuǎn)地址（跳轉(zhuǎn)指令實現(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)指令。一定會發(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)地址計算的準(zhǔn)確性。跳轉(zhuǎn)指令將PC的值置為跳轉(zhuǎn)地址而非順序執(zhí)行的下一條指令地址，同時還可能改變內(nèi)存或其他寄存器的值，如CALL指令在程序跳轉(zhuǎn)前會將順序執(zhí)行的下一條指令的地址壓入堆棧，BL指令會將順序執(zhí)行的下一條指令存儲到R14寄存器中。因此可以將跳轉(zhuǎn)指令抽象為改變程序狀態(tài)（寄存器和內(nèi)存的取值情況）的函數(shù)，第3.3.2節(jié)會進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、EX語句和表達(dá)式的語義要根據(jù)具體的表達(dá)式和語句定義，如表達(dá)式RdTmp(t10)的語義為變量t10的取值，語句WrTmp(t1)=(IR expr)的語義為將表達(dá)式expr的值賦給t1得到新的程序狀態(tài)。VEX的表達(dá)式和語句的詳細(xì)介紹參考文獻(xiàn)22。3.3.3 求解帶符號的跳轉(zhuǎn)地址符號執(zhí)行過程中可能存在帶有符號的跳轉(zhuǎn)地址。執(zhí)行過程在程序狀態(tài)中記錄了每一條分支對符號的約束。當(dāng)遇到地址帶有符號的跳轉(zhuǎn)指令時，用約束求解器求解該符號的約束得到符號值的范圍，計算得到可能的跳轉(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)行識別導(dǎo)出函數(shù)中靜態(tài)注冊的原生方法；第7)行將導(dǎo)出函數(shù)地址加入到工作列表中。00178-8圖4 CFGNative體系結(jié)構(gòu)第10)30)行代碼開始循環(huán)，從工作列表中取出地址，如果該地址為JNI函數(shù)的地址，第13)行代碼調(diào)用JNI函數(shù)對應(yīng)的SimProcedure，若調(diào)用的JNI函數(shù)是RegisterNatives，則可以找到動態(tài)注冊的原生方法，第15)行將新找到的動態(tài)注冊的原生方法的地址加入工作列表中；如果該地址

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

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

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

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

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

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

44、Accurate對比。IDA、CFGAccurate和CFGNative都以導(dǎo)出函數(shù)和不出現(xiàn)在導(dǎo)出函數(shù)表中的原生方法為起點構(gòu)造控制流圖，去掉編譯過程加入的一些函數(shù)，如_gnu_ Unwind_Resume。統(tǒng)計每種方法提取每個原生庫的控制流圖平均耗費(fèi)的時間和平均每個圖中節(jié)點個數(shù)、邊數(shù)和覆蓋的指令數(shù)，結(jié)果如表2所示。表1樣本中收集的原生庫個數(shù)包名原生庫個數(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é)點/個邊/條指令/條時間/sIDA559.801 413.413 592.310.45CFGAccurate(angr)740.161 322.193 057.91110.52CFGNative1 050.51 805.

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

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

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