基于符號執行的Android原生代碼控制流圖提取方法

顏慧穎，周振吉，吳禮發，洪征，孫賀

?

基于符號執行的Android原生代碼控制流圖提取方法

顏慧穎，周振吉，吳禮發，洪征，孫賀

（解放軍理工大學指揮信息系統學院，江蘇南京 210000）

提出了一種基于符號執行的控制流圖提取方法，該方法為原生庫中的函數提供了符號執行環境，對JNI函數調用進行模擬，用約束求解器對符號進行求解。實現了控制流圖提取原型系統CFGNative。實驗結果表明，CFGNative可準確識別樣例中所有的JNI函數調用和原生方法，并能夠在可接受的時間內達到較高的代碼覆蓋率。

控制流圖；Android應用軟件；原生代碼；符號執行

1 引言

Android系統的普及使Android應用的數量和種類呈爆發式增長。據Statista的數據統計，2017年3月，僅Google play上的Android應用就達2.8×106多個，比2015年增長了近1×106個[1]。面對海量的Android應用，安全人員可能需要分析程序尋找漏洞或判斷程序是否有惡意行為；開發者傾向于復用已有的程序模塊。而大多數情況下，分析者接觸到的都是編譯后的應用，需要分析程序安裝包（APK，Android package）中的代碼文件（字節碼文件和原生庫文件）獲取有用的信息。因此，人們對高效的Android應用分析方法和技術的需求更加迫切。

控制流圖在程序逆向和分析領域中應用十分廣泛。編譯后的程序丟失了很多源代碼中數據和代碼結構的信息，間接跳轉、不可執行的數據塊、代碼段對齊等使反匯編變得困難?？刂屏鲌D有助于解決這些棘手的問題[2,3]。并且控制流圖是數據流分析、數據依賴分析、程序切片等其他分析方法的基礎[4,5]，也可作為區分惡意和非惡意代碼的特征[6,7]。

傳統的控制流圖提取方法正被逐漸移植到Android應用程序的分析過程中。但由于Android應用程序與PC程序的結構和運行環境存在較大差別，這些方法[8~17]不能直接用于構造Android應用的控制流圖。目前，針對Android應用的工作[18~20]主要關注Dalvik字節碼（簡稱字節碼）的控制流圖提取方法，缺乏對原生庫代碼的研究。而越來越多的Android程序在原生庫中完成一些重要和復雜的功能，如加密、加殼等。惡意代碼也開始傾向于隱藏在原生庫中以逃避檢測，如“百腦蟲”“蜥蜴之尾”等木馬都將其惡意邏輯隱藏在原生庫中，因此僅分析字節碼并不能完整地了解Android應用的真實行為。針對上述問題，本文深入分析了Android應用原生代碼的特點，提出了一種基于符號執行的控制流圖提取方法，設計并實現了原型系統，主要貢獻如下。

1) 提出了一種基于符號執行的控制流圖提取方法，符號執行過程基于中間表示VEX。該方法與平臺無關，可以用來分析為多種平臺編譯的Android原生代碼。

2) 深入分析系統的JNI特性，對系統JNI相關的結構和JNI函數進行模擬，使本文方法能準確識別原生代碼中的原生方法和JNI函數調用。

3) 基于angr設計并實現了用于提取Android原生庫控制流圖的原型系統CFGNative，該系統能自動識別導出函數和注冊的原生方法，并將其作為控制流圖的起點。CFGNative為用戶及現有的Dalvik字節碼分析工具提供了接口，以便于分析者結合CFGNative和字節碼的分析工具提取全部應用的控制流圖或基于該系統實現其他的程序分析方法。

2 背景

2.1 Android應用和JNI函數調用

本文分析的對象是編譯打包后的APK。APK中主要包含Java代碼編譯后生成的Dalvik字節碼文件（后綴為dex），C/C++代碼編譯后的針對不同平臺的原生庫文件（后綴為so）、資源文件和AndroidManifest.xml文件。APK中的可執行文件為字節碼文件和原生庫文件。字節碼運行在Dalvik虛擬機上，原生代碼直接運行在Linux系統上。

Android應用中的字節碼和原生代碼可以通過JNI通信和相互調用。JNI是Java程序設計語言功能最強的特性，它允許Java類的某些方法原生實現，同時讓它們能夠像普通Java方法一樣被調用[21]。Android的Dalvik虛擬機也支持Java的JNI特性。Dalvik字節碼需調用System.loadLibrary方法加載包含原生方法的原生庫文件，并且用關鍵字native聲明原生方法，之后才能調用原生方法。

原生庫按照注冊規則向Dalvik虛擬機注冊暴露給字節碼的原生方法。原生方法需在字節碼中用關鍵字native進行聲明，Dalvik虛擬機調用原生方法時，在原生庫中找到與這些聲明對應的方法實體，并傳遞參數JNI接口指針的地址（如JNIEnv指針）和實例引用或類引用（若該原生方法是實例方法則傳入實例引用，若為靜態方法則傳入類引用）。

原生庫中的代碼通過指向JNI接口的指針獲取JNI函數（或JNI接口函數）的地址，然后調用JNI函數與字節碼進行數據交換，如訪問Java類的字段、創建類的實例、調用類和實例的方法等。JNI函數調用過程示例匯編代碼如下。

.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

.text: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, [R12,#0x84]

.text:00000D74 ADD R3, PC, R3 ; "(Ljava/lang/String;)Ljava/lang/Object;"

.text:00000D78 BLX R12

根據函數調用規約，R0傳遞參數JNIEnv指針，因此代碼00000D38處的R3寄存器和00000D58處的R12寄存器存儲的是JNIEnv的值。JNIEnv是一個接口指針，該接口結構中包含JNI函數表，通過JNIEnv和相對偏移可以訪問函數表。相對JNIEnv偏移0x18的地址上存儲的是JNI函數FindClass的地址。程序在00000D44處獲取FindClass的地址，并通過00000D4C處的間接跳轉指令調用該JNI函數得到android/content/ Context類的引用，在00000D70處獲取存儲在相對JNIEnv偏移0x84地址上的JNI函數GetMethodID的地址，00000D78處的間接跳轉指令調用GetMethodID得到android/content/Context的getSystemService方法的引用。傳統的控制流圖提取方法不能解析程序中的JNI函數調用過程，因此不能直接用來提取Android原生代碼的控制流圖。

2.2 中間表示VEX

隨著嵌入式平臺的發展，Android系統的底層平臺也更加多樣，現在市場上主要的架構有ARM、X86、AMD64和MIPS，所以原生庫可能是不同平臺的目標文件，使用不同的指令集。為了使本文方法與平臺無關，將原生庫中的指令轉化為中間表示，在中間表示上進行符號執行。

本文使用的中間表示是VEX[22]。VEX是一種較成熟的平臺無關的中間語言，使用廣泛，已經被實踐證明能較好地兼容多種平臺（包括Android系統中可能使用的幾種平臺）。一些經典的二進制分析平臺，如Valgrid[23]、angr[24]，將二進制碼轉化為中間表示VEX，再基于VEX進行程序分析。第3.3節將詳細介紹VEX在符號執行過程中的作用。圖1為32 bit ARM指令轉化為VEX的示例，圖1左側是ARM指令，將寄存器R2中的值減8再存入R2寄存器。圖1右側是轉化得到的VEX語句，先將R2的值賦給變量0，使變量1取值8，再將變量0和1的差賦給變量3，然后把3的值存儲到寄存器R2中，最后將下一條指令的地址0x59FC8存入IP寄存器。

3 基于符號執行的控制流圖提取方法

以原生庫文件的導出函數（一般包括靜態注冊的原生方法一般會出現在導出函數表中）和動態注冊的原生方法為符號執行的起點，控制流圖的提取過程如圖2所示。首先為每個起點初始化程序狀態，在程序狀態中模擬JNI相關結構（JNIEnv、JavaVM、JNIInvokeInterface和JNINativeInterface），將無法確定的參數初始化為符號值；然后從起點開始符號執行。遇到跳轉指令時，若跳轉地址是JNI相關結構中的JNI函數地址，則執行模擬JNI函數的SimProcedure，再返回符號執行過程；否則從跳轉地址繼續符號執行。

3.1 程序控制流圖

按照馮諾依曼體系結構，無跳轉指令時，程序執行完一條指令后，緊接著在內存中取下一條指令繼續執行，這種執行順序被稱為順序執行。程序的執行流程有順序、分支和循環這3種。分支和循環都是由跳轉指令破壞當前的順序執行實現的。把連續的順序執行的指令集合作為一個基本塊，將基本塊作為控制流圖的節點，跳轉語句導致的基本塊之間的控制流遷移為控制流圖的邊。因此，提取控制流圖的重點和難點是計算跳轉地址（跳轉指令實現跳轉后，程序繼續執行的地址）。

3.1.1 跳轉指令

每種指令集中都有跳轉指令，這些指令可以使程序接著執行跳轉地址處的指令，而非順序執行下一條指令。按跳轉是否需要條件可將跳轉指令分為強制跳轉指令和條件跳轉指令。一定會發生跳轉的指令為強制跳轉指令，如X86指令集中的CALL、JMP指令，ARM指令集中的B、BL指令，以及直接給PC賦值的指令，如LDR PC、Expr。當滿足特定條件才跳轉的指令為條件跳轉指令，如X86指令集中的JE、JNE指令，ARM指令集中的BE、BNE指令。按跳轉地址的取值方式可以將跳轉指令分為直接跳轉指令和間接跳轉指令。直接跳轉指令將跳轉地址直接編碼到指令中，而間接跳轉指令的跳轉地址依賴于寄存器或內存中的值。每一條跳轉指令都可以表示為jmp(,)的形式，其中，是跳轉指令所在的地址，是跳轉地址，是跳轉的條件?？刂屏鲌D的準確性和完整性很大程度上依賴于跳轉地址計算的準確性。

跳轉指令將PC的值置為跳轉地址而非順序執行的下一條指令地址，同時還可能改變內存或其他寄存器的值，如CALL指令在程序跳轉前會將順序執行的下一條指令的地址壓入堆棧，BL指令會將順序執行的下一條指令存儲到R14寄存器中。因此可以將跳轉指令抽象為改變程序狀態（寄存器和內存的取值情況）的函數，第3.3.2節會進一步介紹。

3.1.2 基本塊

本文將指令轉化為中間表示VEX，因此控制流圖的基本塊是連續且順序執行VEX語句的集合。

將中的指令全部轉換為VEX語句得到的語句序列為VEX基本塊。根據定義可以推斷基本塊（除起始塊）的起始地址都是某一條跳轉語句的跳轉地址，基本塊（除結束塊）的最后一條指令都是跳轉語句。只能從基本塊第一條語句開始執行，且一旦開始必然順序執行到該基本塊中最后一條指令。

3.1.3 控制流圖

本文的目的是分析程序控制流的遷移，并將其表示為由基本塊和邊構成的控制流圖。

定義2 任意一個Android庫文件的指令都可以被劃分為多個基本塊，這些基本塊的集合記為。2個基本塊1和2間存在數據流遷移，當且僅當

定義4沒有main函數，本文從導出函數和不出現在導出表中的原生方法開始提取控制流圖。給控制流圖增加2個特殊節點和若干邊，控制流圖中其他節點和邊的約束依然滿足定義3，得到。

3.2 模擬JNI函數調用

如2.1節所述，原生方法通過間接跳轉調用JNI函數，而傳統的控制流圖提取方法沒有將原生方法的第一個參數解析為JNI接口指針地址，也不能解析JNI接口的結構，因此無法計算出JNI函數調用的間接跳轉地址。對此，本文方法在程序狀態中模擬JNI接口指針等JNI相關結構，找到向虛擬機注冊的原生方法，然后將JNI接口指針的地址傳遞給原生方法。當符號執行遇到JNI函數調用的間接跳轉指令時，即可根據模擬的JNI相關結構計算得到函數表中的JNI函數地址。另外，APK的原生庫中沒有JNI函數的指令，無法符號執行JNI函數，本文方法用SimProcedure代替符號執行過程。

3.2.1 模擬JNI相關結構

JNI相關結構包括JNIEnv、JavaVM、JNIInvokeInterface和JNINativeInterface。Dalvik虛擬機將JNIEnv的地址作為第一個參數傳遞給原生方法（JavaVM的地址是JNI_OnLoad的第一個參數）。JNIInvokeInterface和JNINativeInterface是JNI接口類型，分別包含一個函數表，函數表中包含的是JNI函數的地址。原生代碼通過函數表中的函數訪問虛擬機或字節碼中的內容。JavaVM指向的正是JNIInvokeInterface的起始地址，JNIEnv指向的正是JNINativeInterface的起始地址，因此原生方法通過參數和相對偏移即可找到函數表中某一JNI函數表項的地址，從而得到該JNI函數的地址。JNIEnv、JavaVM、JNIInvokeInterface和JNINativeInterface在內存中的結構如圖3所示。

本文分析的原生庫中不包含這些結構，也不會在內存中構造該結構，因此，在符號執行前需要在程序狀態的內存中模擬該結構。在內存中開辟一塊未使用的空間給JavaVM、JNIEnv、JNIInvokeInterface和JNINativeInterface，在開辟的空間中填入任意未使用地址空間中的地址，執行過程中自動將JavaVM和JNIEnv的地址作為參數傳遞給原生方法。

3.2.2 SimProcedure模擬JNI函數

除了模擬JNI相關結構，還需要模擬接口函數表中的JNI函數。在真實的Android原生庫運行環境中，原生方法通過Dalvik虛擬機調用JNI函數，本文符號執行過程中既無虛擬機也無JNI函數，需要用SimProcedure對JNI函數的功能進行抽象和模擬，并且用SimProcedure hook JNI函數的地址，使執行到JNI函數時，相應的SimProcedure能被調用。

SimProcedure是指用來模擬JNI函數的一類函數，概括了JNI函數的程序邏輯，是程序執行過程中實現JNI函數對程序狀態的改變以及相應控制流圖節點構造的實體。SimProcedure不是原生庫中的代碼，因此其構造的節點只用于記錄該處JNI函數調用的信息，不包含真實代碼對應的VEX語句。

JNIInvokeInterface和JNINativeInterface的函數表中的每個函數都對應一個SimProcedure。有的JNI函數會返回字節碼的類、對象、字段、方法等的引用，后續JNI函數調用中可能會使用這些返回值。而執行環境中不存在字節碼中的結構，這些結構的引用只是標識它們的符號。因此，這些字節碼內容的引用是全局的，且在定義SimProcedure時，應該考慮JNI函數之間的關系，使其他SimProcedure也能夠準確識別這些標識。如FindClass的SimProcedure需要返回一個標識以表示類名為傳入的第二個參數的類，在符號執行過程中，其他JNI函數在遇到這個標識時也應該將其解釋為這個類。

先構造圖3的結構，再用對應的SimProcedure hook JNI接口函數表中填入的地址。執行過程中，當原生方法調用函數表中的JNI函數時，找到的JNI函數地址實際上是被SimProcedure hook的地址，因此執行的是SimProcedure，執行完SimProcedure后返回調用JNI函數的下一條指令繼續執行。

3.2.3 定位注冊的原生方法

本文的符號執行要自動將JNIEnv的地址作為參數傳遞給原生方法，因此需要其能夠識別注冊的原生方法。

注冊原生方法的方式分為靜態注冊和動態注冊這2種。靜態注冊需要根據命名規則命名原生方法，要求用包名加上類名再加上字節碼中聲明的方法名來命名原生庫中對應的原生方法，如應將與android.helloWorld包的MainActivity類中聲明的原生方法helloFromJNI對應的原生庫中的方法命名為Java_android_helloWorld_MainActivity_helloFromJNI。符號表中一般都包含靜態注冊的原生方法，因此可以通過符號表中函數名識別原生函數。而動態注冊將原生方法與其在字節碼中聲明的對應關系記錄到JNINativeMethod結構中，再通過調用JNINativeInterface中的RegisterNatives函數將JNINativeMethod中的原生方法注冊到虛擬機。JNINativeMethod的結構如下所示。

typedef struct {const char* name;

const char* signature;

void* fnPtr;

} JNINativeMethod;

該結構有3個字段，分別為字節碼中聲明的原生方法的名稱、參數和返回值的類型信息以及原生方法在原生庫中的地址。若執行過程中調用了RegisterNatives函數，從參數中可得到JNINativeMethod結構的列表在內存中的地址和列表長度，解析該列表獲得動態注冊的原生方法，該過程由RegisterNatives函數的SimProcedure完成。

動態注冊需要在字節碼調用原生方法之前完成。JNI_OnLoad在原生庫加載時被調用。通常在JNI_OnLoad中調用RegisterNatives，動態注冊過程就會在原生庫加載時完成。因此，如果原生庫中實現了JNI_OnLoad方法，應該優先執行JNI_OnLoad以找到可能出現的動態注冊的原生方法。

3.3 提取控制流圖

本文分析的對象是Android原生庫文件，而原生庫不可單獨執行，如果直接進行動態分析，則需要實現觸發原生庫執行的模塊。而Android應用中調用原生方法的是字節碼，因此需要搭建兩層執行環境（包括Dalvik虛擬機），使環境比較復雜，并且有時需要構造復雜的輸入才能觸發原生庫中代碼的執行，分析效率較低。為此本文提出了一種基于VEX的符號執行方法，直接分析Android原生庫，提取控制流圖。只要構造了函數的執行環境，該方法便可單獨執行某一個函數，無需從main函數開始執行。符號執行的環境由angr[25]提供，angr將指令轉化為中間表示VEX，符號執行引擎根據VEX表達式和語句的語義修改程序狀態，并記錄下路徑的約束條件，當遇到跳轉語句時根據程序狀態和約束條件計算跳轉地址。

3.3.1 程序狀態

程序狀態主要包含程序在某一程序點內存、寄存器、變量（VEX中含有變量）的取值情況。將VEX中寄存器的集合記為，內存區域記為，臨時變量的集合記為。符號執行的程序狀態中有具體值和符號值。將具體值（如立即數0x10、地址0x400000等）的集合記為。符號值表示滿足一定約束的值的集合，用符號（如、等）表示。符號值在執行中也可參與運算，如+、+0x10等。將符號值的集合記為。因此程序狀態中寄存器、內存和變量取值的值域為。原生庫中函數按函數調用規約接收參數，且除JavaVM和JNIEnv的地址外，其他參數在分析者沒有指明的情況下都默認取符號值。只要構造一個函數被調用時的程序狀態并將該狀態輸入符號執行引擎，就能從該函數開始符號執行，因此需要初始化原生函數和其他導出函數開始執行時的程序狀態，如將參數賦值給傳遞參數的寄存器。

定義5 程序狀態state用二元組的集合表示，實際上為內存、寄存器和變量到上的映射。

當程序狀態中有二元組（，）時，則說明該狀態下的取值為。

理論上是無窮且連續的，但程序執行過程中各類型變量的值一般存儲在一塊連續的內存區域中。將該段內存中的值作為中的一個元素，內存即可被看作離散的。另外，運行程序所需的內存空間有限，未使用的內存只是概念上的一塊區域，在符號執行過程中并不分配空間以記錄其狀態，因此記錄和讀取內存是可實現的。

3.3.2 表達式和語句

符號執行是在VEX上進行的，因此需要告知執行引擎VEX表達式和語句的語義，執行引擎才能按照語義執行程序。

定義6 將表達式的集合記為，語句的集合記為。表達式的語義為表達式和程序狀態到上的函數，語句的語義為語句和程序狀態到新的程序狀態上的函數。

VEX語句和表達式的語義要根據具體的表達式和語句定義，如表達式RdTmp(10)的語義為變量10的取值，語句WrTmp(1)=(IR)的語義為將表達式的值賦給1得到新的程序狀態。VEX的表達式和語句的詳細介紹參考文獻[22]。

3.3.3 求解帶符號的跳轉地址

符號執行過程中可能存在帶有符號的跳轉地址。執行過程在程序狀態中記錄了每一條分支對符號的約束。當遇到地址帶有符號的跳轉指令時，用約束求解器求解該符號的約束得到符號值的范圍，計算得到可能的跳轉地址，然后判斷這些可能的跳轉地址是否為指令的起始地址，將滿足條件的值列入最終跳轉地址結果的集合中。

3.3.4 控制流圖提取算法

基于上述討論，控制流圖提取算法的偽代碼如下。

代碼第3)~9)行為算法初始階段，其中，第3)行從導出表中獲取導出函數地址；第4)行獲取導出函數中JNI_OnLoad的地址，若不存在則為空；第5)行識別導出函數中靜態注冊的原生方法；第7)行將導出函數地址加入到工作列表中。

第10)~30)行代碼開始循環，從工作列表中取出地址，如果該地址為JNI函數的地址，第13)行代碼調用JNI函數對應的SimProcedure，若調用的JNI函數是RegisterNatives，則可以找到動態注冊的原生方法，第15)行將新找到的動態注冊的原生方法的地址加入工作列表中；如果該地址不是JNI函數的地址，則執行第18)~29)行。第18)行得到起始地址為的VEX基本塊。第23)行獲取VEX基本塊開始符號執行時的程序狀態，需要為函數的起始塊初始化程序狀態，從程序狀態集合中獲取其他VEX基本塊對應的程序狀態。如果基本塊屬于原生方法，初始化程序狀態時要在內存中模擬JNI相關結構。第24)行得到VEX表達式和語句的語義。第25)行為符號執行過程，第26)~29)行計算跳轉地址，將以跳轉地址為起點的基本塊對應的程序狀態加入程序狀態集合，并將跳轉地址加入工作列表。循環整個過程直到工作列表為空。

4 原型系統實現與實驗

4.1 系統實現

為了驗證本文所提方法的有效性，基于angr實現了提取Android原生庫的控制流圖的原型系統CFGNative，其結構如圖4所示。系統中，模塊loader解析輸入的原生庫文件，并將代碼段和數據段加載到內存中；lifter從給定的地址開始識別并翻譯VEX基本塊；execution simulator在lifter識別的VEX基本塊上進行符號執行并將計算得到的跳轉地址給lifter，lifter從新的地址開始繼續識別VEX基本塊，迭代該過程直到沒有新的VEX基本塊生成；state記錄執行各階段的程序狀態；core engine是符號執行的核心模塊，逐條解析VEX語句的語義；JNI struct constructor在內存中構造JNIInvokeInterface和JNINativeInterface等結構；simprocedures被hook到JNI函數的地址上；constraint solver根據約束求解帶符號跳轉地址。

4.2 實驗及結果分析

本文設計了2個實驗：實驗1用CFGAccurate提取本文構造的Android（源碼見附錄A）應用JNITest中原生庫的一個控制流圖，目的是檢測CFGAccurate是否能準確識別靜態和動態注冊的原生函數和JNI函數調用。實驗2對比angr的CFGAccurate、IDA和CFGNative提取控制流圖的結果，目的是將CFGNative的指令覆蓋率和時間耗費與現有經典分析工具進行對比，檢測CFGNative增加的功能是否對其他性能造成過大影響。實驗硬件配置為Intel(R) Core(TM) i7-3770處理器（8核3.40 GHz），32 GB RAM。操作系統為64 bit的Ubuntu16.04。

1) 實驗1：JNITest

原生方法分為靜態和動態這2種注冊方式，因此JNITest中包含了2個原生方法，分別用2種不同的方式注冊，同時包含多個JNI函數調用，具有一定代表性。

Java_com_example_test_MainActivity_getIMEI為靜態注冊的原生方法，通過JNI函數FindClass找到android.telephony.TelephonyManager類，然后調用JNI函數GetMethodID獲得該類getDeviceId方法的引用，最后通過CallObjectMethod調用該方法獲取設備的IMEI。該方法中的JNI函數會使用其他JNI函數返回的結果，如FindClass返回的Java類的引用會作為GetMethodID的參數，因此可以測試SimProcedure的定義是否正確。helloJNI為動態注冊的原生方法，通過在JNI_ONLoad中調用RegistaerNatives進行注冊，該方法返回JNI函數NewStringUTF構造的字符串“Hello from JNI”。

CFGNative提取的控制流圖顯示其準確識別了這2個原生方法和所有的JNI函數調用，得到的控制流圖中共有8個代表JNI函數的節點，38條包含表示JNI函數節點的邊。代表JNI函數調用的節點和包含這些節點的邊的詳細信息見附錄B。

2) 實驗2：對比

實驗2將Android應用市場APPChina上下載量排名靠前的16個應用作為樣本，過濾樣本原生庫中的廣告包、音視頻處理等第三方工具包，共收集了61個原生庫文件。表4為從每個應用中收集的原生庫的個數，由于有些原生庫存在于多個包中，所以個數的總和大于61。從每個包中獲取的具體的原生庫見附錄C。用CFGNative提取這些原生庫的控制流圖，并與當前最流行的二進制分析工具IDA和angr的CFGAccurate對比。IDA、CFGAccurate和CFGNative都以導出函數和不出現在導出函數表中的原生方法為起點構造控制流圖，去掉編譯過程加入的一些函數，如_gnu_ Unwind_Resume。統計每種方法提取每個原生庫的控制流圖平均耗費的時間和平均每個圖中節點個數、邊數和覆蓋的指令數，結果如表2所示。

表1 樣本中收集的原生庫個數

表2 控制流圖提取結果

CFGAccurate和IDA不具備分析JNI的能力，因此不能識別原生方法和JNI函數調用。CFGNative比其他2種方式識別了更多的節點，其中包含表示JNI函數的節點，這些節點的指令條數為0，從表2中可以看到，CFGNative比IDA和CFGAccurate覆蓋了更多的指令，這是因為CFGNative識別了IDA和CFGAccurate無法識別的間接跳轉，從而發現了新的基本塊中的指令。實驗結果表明，CFGNative不僅能夠識別JNI函數調用，且在可接受的時間內具有較高的代碼覆蓋率。

5 結束語

本文提出了一種基于符號執行的控制流圖提取方法，用于自動提取Android應用原生代碼的控制流圖。該方法可以識別原生方法和JNI函數調用，準確計算間接跳轉地址，且具有較高代碼覆蓋率。下一步研究包括以下2個方面。

1) 符號執行用SimProcedure代替真實的JNI函數調用，因此對SimProcedure定義的準確性會影響符號執行的結果。目前對SimProcedure的定義過于依賴經驗。未來工作將深入分析真實環境下JNI函數的行為并對其進行更系統的建模。

2) 符號執行過程中包含的符號值過多或約束求解器的求解能力不足都可能導致求解所得的符號值范圍過大。當包含符號的跳轉地址取值范圍過大時，可能會產生路徑爆炸問題，需要進一步研究該問題的解決方案。

附錄A 本文構造的Android原碼

#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__)

#define 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 //計算結構元素個數

# define NELEM(x) ((int) (sizeof(x) / sizeof((x)[0])))

#endif

//靜態注冊的原生方法getIMEI

JNIEXPORT 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)-> GetStaticFieldID(env,cls_context,"TELEPHONY_SERVICE","Ljava/lang/String;");

if(TELEPHONY_SERVICE == 0){

return (*env)->NewStringUTF(env,"[+] Error : GetStaticFieldID failed");

}

jstring str = (jstring)(*env)->GetStatic ObjectField(env,cls_context, TELEPHONY_SERVICE);

jobject telephonymanager = ((*env)-> CallObjectMethod(env,mContext, getSystemService, str));

if(telephonymanager == 0){

return (*env)->NewStringUTF (env,"[+] Error: CallObjectMethod failed");

}

jclass cls_TelephoneManager = (*env)-> FindClass(env, "android/telephony/TelephonyManager");

if(cls_TelephoneManager == 0){

return (*env)->NewStringUTF (env,"[+] Error: FindClass TelephoneManager failed");

}

jmethodID getDeviceId = ((*env)-> GetMethodID(env,cls_TelephoneManager, "getDeviceId", "()Ljava/lang/String;"));

if(getDeviceId == 0){

return (*env)->NewStringUTF (env, "[+] Error: GetMethodID getDeviceID failed");

}

jobject DeviceID = (*env)->CallObjectMethod (env,telephonymanager,getDeviceId);

return (jstring)DeviceID;

}

//動態注冊的方法helloJNI

JNIEXPORT jstring helloJNI(JNIEnv* env, jclass clazz){

const char * chs = "Hello from JNI";

return (*env)->NewStringUTF(env, chs);

}

static JNINativeMethod methods[] = {

{"helloJNI", "()Ljava/lang/String;", (void*)helloJNI}

};

jintJNI_OnLoad(JavaVM* vm, void* reserved){

if(JNI_OK != (*vm)->GetEnv(vm, (void**)&g_env, JNI_VERSION_1_6)){

return -1;}

LOGV("JNI_OnLoad()");

native_class = (*g_env)->FindClass(g_env, "com/ example/test/MainActivity");

if (JNI_OK ==(*g_env)->RegisterNatives(g_env, //動態注冊原生方法

native_class, methods, NELEM(methods))){

LOGV("RegisterNatives() --> helloJNI() ok");

} else {

LOGE("RegisterNatives() --> helloJNI() failed");

return -1;}

return JNI_VERSION_1_6;

}

附錄B

附錄表1 JNI函數調用的節點和包含這些節點的邊的信息

節點邊緣 (, ) （, ) (, ) (, ) (, ) (, ) (, ) , ) (, ) (, ) (, ) (, )

續表

節點邊緣 (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) (, ) （, ) (, )

附錄表1中節點表示為的形式，其中nodeName為該節點的名稱，當節點基本塊為函數的起始塊時，以函數名作為節點的名稱，否則以函數名加上節點基本塊起始地址相對于函數起始地址的偏移作為節點的名稱。表示JNI函數的節點以JNI函數的名稱作為節點的名稱。nodeAddr為節點基本塊的起始地址。表示JNI函數的節點的nodeAddr是本文3.2.3節提到的函數表中填入的地址。邊表示為（，）的形式，代表連接名為nodeName1的節點和名為nodeName2的節點的邊。

附錄C

附錄表2 樣本應用中獲取的原生庫

包名原生庫名包名原生庫名 com.qihoo360.mobilesafelibnzdutil-jni-1.0.0.2002.socom.tencent.qqpimsecurelibNativeRQD.so com.tencent.mmlibmm_gl_disp.socom.baidu.homeworklibweibosdkcore.so com.baidu.inputlibbdinput_gif_v1_0_10.solibgaussblur_v1_0.socom.baidu.searchboxlibbitmaps.solibmemchunk.so com.tencent.mttlibbeso.solibbitmaps.solibblur_armv7.solibcmdsh.solibcommon_basemodule_jni.solibdaemon_lib.solibFdToFilePath.solibFileNDK.solibgif-jni.solibmemchunk.solibtencentpos.socom.tencent.qqmusiclibckey.solibdalvik_patch.solibdesdecrypt.solibexpress_verify.solibfilescanner.solibFormatDetector.solibframesequence.solibLPConvert.solibmApptracker4Dau.solibmresearch.solibNativeRQD.solibnetworkbase.solibqalmsfboot.solibqav_graphics.solibRandomUtilJni.solibtmfe30.solibweibosdkcore.solibwnsnetwork.so com.storm.smartliba.solibdaemon.solibgetuiext2.solibMMANDKSignature.solibmresearch.solibpl_droidsonroids_gif.solibpl_droidsonroids_gif_surface.solibstpinit.solibweibosdkcore.socom.UCMobilelibucinflator.so com.kugou.androidlibkgkey.solibkguo.solibLencryption.solibMMANDKSignature.solibrtmp.solibweibosdkcore.socom.sankuai.meituanlibdpencrypt.solibdpobj.solibnetworkbase.solibnh.solibPayRequestCrypt.solibRectifyCard.solibuploadnetwork.so com.baidu.BaiduMaplibcpu_features.solibgif.solibufosdk.solibweibosdkcore.socom.sina.weibolibamapv304ex.solibmemchunk.solibutility.solibweibosdkcore.so com.qiyi.videolibblur.solibdaemon.solibmediacodec.solibMMANDKSignature.solibmresearch.solibpl_droidsonroids_gif.solibrtmp.socom.pplive.androidphonelibbreakpad_util_jni.solibmeet.solibVideoSdkMd5.solibweibosdkcore.so

[1] Statista. number of apps available in leading app stores as of march 2017[EB/OL].https://www.statista.com/statistics/276623/number-of-apps-available-in-leading-app-stores/.

[2] SCHWARZ B, DEBRAY S, ANDREWS G. Disassembly of executable code revisited[C]//The Working Conference on Reverse Engineering. 2002:45-54.

[3] KRUEGEL C, ROBERTSON W, VALEUR F, et al. Static disassembly of obfuscated binaries[C]//Usenix Security Symposium. 2004: 255-270.

[4] REPS T, HORWITZ S, SAGIV M. Precise interprocedural dataflow analysis via graph reachability[C]//The 22nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 1995: 49-61.

[5] HORWITZ S, REPS T, BINKLEY D. Interprocedural slicing using dependence graphs[J]. ACM Sigplan Notices, 2004, 23(7):35-46.

[6] BRUSCHI D, MARTIGNONI L, MONGA M. Detecting self-mutating malware using control-flow graph matching[C]//The International Conference on Detection of Intrusions and Malware and Vulnerability Assessment, 2006:129-143.

[7] CESARE S, XIANG Y. Malware variant detection using similarity search over sets of control flow graphs[C]//The International Conference on Trust, Security and Privacy in Computing and Communications. 2011:181-189.

[8] CIFUENTES C, VAN EMMERIK M. Recovery of jump table case statements from binary code[C]//TheInternational Workshop on Program Comprehension.1999: 192-199.

[9] MENG X, MILLER B P. Binary code is not easy[C]//The 25th International Symposium on Software Testing and Analysis. 2016: 24-35.

[10] SUTTER B D, BUS B D, BOSSCHERE K D, et al. On the Static Analysis of Indirect Control Transfers in Binaries[C]//The International Conference on Parallel & Distributed Processing Techniques & Applications. 2000:1013-1019.

[11] KINDER J, ZULEGER F, VEITH H. An abstract interpretation-based framework for control flow reconstruction from binaries[C]//The International Workshop on Verification, Model Checking, and Abstract Interpretation. 2009: 214-228.

[12] TROGER J, CIFUENTES C. Analysis of virtual method invocation for binary translation[C]//The Working Conference on Reverse Engineering. 2002: 65-74.

[13] JOHNSON R, STAVROU A. Forced-path execution for android applications on x86 platforms[C]//The International Conference on Software Security and Reliability Companion. 2013: 188-197.

[14] XU L, SUN F, SU Z. Constructing Precise Control Flow Graphs from Binaries[J]. University of California. 2012.

[15] ZHAO, J. Analyzing control flow in Java bytecode[C]//The 16th Conference of Japan Society for Software Science and Technology. 1999: 313-316.

[16] 胡剛, 張平, 李清寶,等. 基于靜態模擬的二進制控制流恢復算法[J]. 計算機工程, 2011, 37(5): 276-278.

HU G, ZHANG P, LI Q B, el al. Control flow restoring algorithm for binary program based on static simulation[J]. Computer Enginerring, 2011, 37(5): 276-278.

[17] 張雁, 林英. 程序控制流圖自動生成的算法[J]. 計算機與數字工程, 2010, 38(2):28-30.

ZHANG Y, LIN Y. Automatic generation algorithm of the control flow graph[J]. Computer & Digital Engineering, 2010, 38(2):28-30.

[18] ARZT S, RASTHOFER S, FRITZ C, et al. FlowDroid: precise context, flow, field, object-sensitive and lifecycle-aware taint analysis for android Apps[J]. ACM Sigplan Notices, 2014, 49(6): 259-269.

[19] LI L, BARTEL A, BISSYANDE T F, et al. Iccta: Detecting inter-component privacy leaks in android Apps[C]//The International Conference on Software Engineering. 2015: 280-291.

[20] WEI F, ROY S, OU X. Amandroid: a precise and general inter-component data flow analysis framework for security vetting of android apps[C]//The 2014 ACM SIGSAC Conference on Computer and Communications Security. 2014: 1329-1341.

[21] 辛納（美）. Android C++高級編程——使用NDK[M]. 北京: 清華大學出版社, 2013.

CINAR O. Pro Android C++ wih the NDK[M]. Beijing: Tsinghua University Press, 2013.

[22] Angr. Intermediate Representation[EB/OL]. https://docs.angr.io/ docs/ ir.html.

[23] NETHERCOTE N, SEWARD J. Valgrind: a framework for heavyweight dynamic binary instrumentation[J]. Acm Sigplan Notices, 2007, 42(6): 89-100.

[24] YAN S, WANG R, HAUSER C, et al. Firmalice-automatic detection of authentication bypass vulnerabilities in binary firmware[C]//The Network and Distributed System Security Symposium, 2015.

[25] SHOSHITAISHVILI Y, WANG R, SALLS C, et al. SOK: (State of) the art of war: offensive techniques in binary analysis[C]//Security and Privacy. 2016: 138-157.

Symbolic execution based control flow graph extraction method for Android native codes

YAN 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, China)

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 using 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 time.

control flow graph, Android application, native code, symbolic execution

TP309

A

10.11959/j.issn.2096-109x.2017.00178

顏慧穎（1993-），女，江西吉安人，解放軍理工大學碩士生，主要研究方向為軟件安全。

周振吉（1985-），男，江蘇沭陽人，博士，解放軍理工大學講師，主要研究方向為軟件安全。

吳禮發（1968-），男，湖北蘄春人，博士，解放軍理工大學教授、博士生導師，主要研究方向為網絡安全。

洪征（1979-），男，江西南昌人，博士，解放軍理工大學副教授、碩士生導師，主要研究方向為網絡安全、人工智能。

孫賀（1990-），男，黑龍江齊齊哈爾人，解放軍理工大學博士生，主要研究方向為軟件逆向工程。

2017-05-07；

2017-06-09。

吳禮發，wulifa@vip.163.com

國家重點研發計劃基金資助項目（No.2017YFB0802900）；江蘇省自然科學基金資助項目（No. BK20131069）

The National Key Research and Development Program of China (No.2017YFB0802900), The Natural Science Foundation of Jiangsu Province (No. BK20131069)