抵御控制流分析的程序混淆算法

樂德廣，趙 杰，龔聲蓉

(1.常熟理工學院 計算機科學與工程學院，江蘇 常熟 215500； 2.蘇州同程網絡科技股份有限公司，江蘇 蘇州 215123)

0 引 言

為提高程序清晰度和執行效率，程序員們大量使用如if-then-else、switch-case等分支語句，或while、do -while、for等循環語句編寫程序[1]。由于這些編程語句具有結構化特點，因此程序的控制流是可歸約的，可以通過控制流分析將程序反編譯成高級語言。近年來，程序控制流分析成為軟件分析的研究熱點，許多學者提出了基于符號執行、程序切片和形式化推理等的程序控制流分析技術[2]，大大提升了程序控制流的完整性和準確性。利用控制流分析技術可以有效地分析程序結構和行為，給程序安全帶來巨大的威脅。為保護程序，許多學者和研究機構對此進行了大量研究，提出了控制流完整性防護[3]、控制流異常檢測[4]和控制流混淆等各種程序安全保護方法[5]。其中，控制流混淆常用的策略有計算混淆、次序混淆和聚合混淆[6]。例如，在計算混淆中，插入非透明謂詞，增加程序中的條件判斷表達式，以此來隱藏真實的程序控制流信息[7]。在次序混淆中，通過控制流平展化打破控制流中結點之間的相關性，使邏輯上相互依賴的結點空間上不相鄰，且攻擊者很難恢復出原始程序結點的執行順序[8]。此外，文獻[9,10]利用機器學習中分類器的內部規則難以被提取和理解這一特性，分別將隨機森林和人工神經網絡用于混淆程序的路徑分支，將逆向分析路徑分支信息的難度等價于抽取分類器內部規則的難度。由于控制流混淆相對于其它兩種控制流保護技術具有更好的安全性，是當下程序混淆領域主要的研究熱點。

在控制流混淆中，程序的控制流分析復雜度很大程度上依賴于程序中的分支路徑。因此，對程序控制流混淆的一種有效方法就是增加程序中的分支路徑。本文通過二態非透明謂詞插入不相關分支路徑和不相關結點，使得原程序控制流的分支路徑和結點信息被破壞掉，增加程序控制流的復雜度。此外，為了進一步加強程序混淆的強度，利用switch-case平展化二態非透明謂詞控制流。同時，采用GetSt調度函數動態賦值算法強化平展控制流的分支變量。在此基礎上，提出了一種程序制流混淆算法。與現有控制流平展化混淆存在控制流結點單一且它們之間的分支路徑順序固定相比，該算法不僅增加控制流分支路徑和結點類型，使分支路徑復雜化，而且分支路徑的執行順序動態化，進一步隱藏程序的控制流信息。測試結果說明該算法能大大增加混淆強度，并有效抵御控制流分析。

1 控制流安全性分析

程序控制流是其內部邏輯關系的執行路徑表示?？刂屏鞣治鐾ㄟ^構造程序的控制流圖分析程序的執行結點，以及由執行結點所組成的分支路徑，來生成程序的控制流信息。其中，控制流圖中的結點稱為基本塊，它是程序的一段指令序列且按順序執行。每個基本塊只有一個唯一的出口和入口，其中入口是基本塊的第一條指令，可以是程序的第一條指令、無條件跳轉的目標指令或條件跳轉的下一條指令。出口是基本塊的最后一條指令，其一般為程序的結束指令、跳轉指令或跳轉目標指令的前一條指令。然后，通過路徑可達性推理得到程序行為同外部執行環境的輸入之間的依賴關系。這些依賴關系可被攻擊者用于程序反編譯破解、隱私數據竊取和程序算法重構等，對程序安全運行和知識產權的保護構成嚴重威脅。

控制流圖是程序編譯器用于尋找編譯優化可能以及分析程序安全性相關技術的研究基礎，因此程序的反編譯可以建立在控制流圖分析的基礎上進行。文獻[11]利用函數定位切分識別函數塊依賴關系，從超匯編指令集中產生粗粒度控制流圖，接著結合中斷標記點處理機制實現對代碼執行路徑可知，并建立精確的控制流基本塊，最終完成以實際控制流引導的程序反編譯逆向破解。

由于程序控制流結點的數據流信息會關聯用戶隱私數據，文獻[12]提出一種基于協同式逆向推理近鄰路徑的控制流分析方法。通過構建程序的控制流圖對程序控制流圖的循環節點進行處理和靜態單賦值來分析用戶隱私數據等敏感數據流。從控制流圖的出口節點開始逐步迭代到起始節點，結合后置條件和節點的執行語義計算其最弱前置條件。在最弱前置條件信息的引導下利用后向符號分析生成與目標后置條件近鄰的路徑集合。在此基礎上，通過對控制流執行路徑的比較識別不可行的近鄰路徑條件，構建程序的行為輪廓并進一步分析程序的行為特征。

程序的控制流信息包含著程序指令的執行軌跡和程序算法。在程序控制流未被混淆的情況下，程序指令與程序算法的控制流圖相同。對于同樣的輸入，程序算法與指令代碼的執行軌跡一致。文獻[13]通過提取和分析二進制程序指令的讀取過程，進行原始二進制程序指令控制流的構建。另外，原始程序的二進制指令執行過程包含著數據的處理過程，通過對程序指令執行過程中的數據流信息進行整理分析，能夠得到程序輸入、輸出數據之間的運算關系，最終重構出程序算法。文獻[14] 在控制流分析基礎上，對存在敏感調用的路徑約束求解路徑條件。最終求解出具體程序行為及觸發條件，識別應用程序敏感行為，揭示出程序行為的執行全過程。

因此，通過對控制流分析與利用，引起程序的破解和盜版、隱私數據泄露和知識產權竊取等安全問題。

2 本文程序混淆算法

根據第1節的控制流安全性分析，針對應用程序的保護，最重要的就是如何有效抵御程序控制流結構的惡意分析。為此，本節在基于控制流混淆技術的研究基礎上，結合二態非透明謂詞插入不相關控制流及控制流平展化，提出一種新的控制流混淆算法，并針對程序特點通過調度函數對該算法做出改進。下面以一個函數為研究對象，圖1左側的代碼為例來闡述本文算法，其原始的控制流如圖1右側所示。

圖1 原始函數及其控制流

2.1 二態非透明謂詞

二態非透明謂詞P是程序中的一種布爾表達式，該表達式的輸出對混淆者而言，其輸出結果已知，但是對破解者卻難以獲知。根據二態非透明謂詞的輸出結果不同，可分為3種類型：如果P在程序的輸出永遠為真(True，T)，則記為PT，例如2|(x2+x) 表達式是一個總是為真的非透明謂詞。如果P的輸出永遠為假(False，F)，則記為PF，例如7*y2-1==x2表達式是一個總是為假的非透明謂詞。如果P的輸出有時為真有時為假，則記為P?，例如xmod 2=0表達式是一時真時假的非透明謂詞。在控制流混淆中，基于二態非透明謂詞插入不相關分支路徑，如圖2所示。

圖2 不同類型的非透明謂詞

圖2中實線表示程序執行時，該路徑有時會執行的控制路徑。虛線表示程序執行時，實際上并不會經過的控制路徑，稱為不相關分支路徑。因此，通過向程序的控制流圖中插入非透明謂詞，并構建不相關的分支路徑，可以提高攻擊者還原控制流結構的難度。使用圖2(a)中的類型來對原始控制流進行混淆。首先，在原始的控制流圖中根據后繼基本塊的唯一性分析非透明謂詞插入的合適位置。然后，根據隨機插入混淆策略插入非透明謂詞及其不可達路徑后的不相關基本塊混淆原始控制流。在圖1示例的基本塊C中添加恒真的非透明謂詞使其變成基本塊C′，其判斷結果永遠為真。真的情況的分支路徑后連接其原始的基本塊D，假的情況的不相關分支路徑后插入一個不相關基本塊E。最終，形成如 圖3 所示的控制流。

圖3 非透明謂詞混淆后的控制流

2.2 控制流平展化

控制流平展化是通過去除控制流圖中的各種分支結構和嵌套結構，使所有的基本塊都處于并列位置，擁有相同的前驅和后繼來達到混淆程序控制流邏輯關系的目的。首先，將程序拆分為多個基本塊，通過基本塊中的轉移指令確定基本塊之間的跳轉關系構建有向邊，并由基本塊和有向邊組成程序的分支路徑，如圖1所示。然后，將這些原本屬于不同層級的基本塊放到同一層級。接著，將所有基本塊封裝到一個Switch選擇分支中，使得分支路徑的位置是動態確定的。最后，用一個分支變量St來引導接下來要實際執行的分支路徑，進行邏輯順序控制。將圖1的控制流圖平展化后如圖4所示。

圖4 平展化后的控制流

從圖4可以看出，程序控制流的分支路徑可以通過分支變量St載入地址而不是直接跳轉地址，這個分支變量可以稱為調度變量。這樣在每一個基本塊中通過計算St的值后，才能確定下一次跳轉到哪一個分支路徑。使得每一個基本塊沒有分支路徑目標地址及執行順序。因此，基本塊的放置位置不必遵循執行的順序，每一個基本塊都可能是其它基本塊的后繼，從而隱藏了基本塊的分支路徑順序信息。

2.3 改進的控制流混淆算法

本小節結合控制流平展化進一步對非透明謂詞插入不相關控制流進行混淆，算法過程如下所示：

步驟1 非透明謂詞插入不相關控制流混淆。根據2.1節，通過二態非透明謂詞進行不相關基本塊的插入，構造分支路徑插入控制流變換，使得原程序的控制流信息被破壞掉。其中，非透明謂詞采用Hui Xu提出的抗符號執行的非透明布爾表達式進行構造[15]。在混淆時，根據插入位置的上下文隨機使用PT和PF中的一個。

步驟2 定義基本塊類型。標記不同基本塊(basic block，BB)的類型屬性(type attribute，Attr)，包含N和I兩種基本塊。其中，N基本塊為混淆前原程序控制流圖中的基本塊[16]，非透明謂詞混淆中插入的不相關基本塊為I。

步驟3 定義基本塊三元組。標記不同基本塊的三元組路徑信息，其由自身基本塊(block of self，BS)、前驅基本塊(block of previous，BP)和后繼基本塊(block of next，BN)構成[16]。其中，BN的路徑數量可能0、1或者2。當后繼基本塊路徑個數為2個時，使用一個布爾值分別標記兩種不同的分支路徑情況。當后繼基本塊路徑個數為1個時，使用恒為真(T)的布爾值標記對應的單分支路徑；當后繼塊路徑個數為0個時，則無需用布爾值標記分支路徑。當沒有前驅或后繼塊時，則把對應的標號設置為空，如圖5所示。

圖5 基本塊三元組

步驟4 非透明謂詞插入不相關控制流平展化。根據2.2小節，創建一個switch-case的分發器結構將程序控制流圖進行平展化。在平展后的控制流圖中，每個分發結點由一個基本塊構成，表示一條分支路徑，則設每個基本塊的分支路徑為St，程序會根據St的不同初始化參數值運行不同的初始分支路徑。根據步驟3定義的三元組，使用基本塊的自身標號BS作為分發結點的執行路徑，后繼塊標號BN作為下一個分發結點的執行路徑，則平展后的控制流如圖6所示。

圖6 非透明謂詞插入不相關控制流進行平展化

步驟5 動態賦值分支變量St。定義一個GetSt(Boo-leanb,Stc)調度函數，其中b表示當前基本塊的BN布爾值，c表示當前基本塊的St值，則下一個的St分支路徑值將通過當前基本塊的BN布爾值(Boolb)、St值(Stc)和基本塊類型屬性(Attr)動態生成。其中，當基本塊的BN為2時，則把對應的布爾值(F，T)傳入b，當BN為1時，把布爾值T傳入b，如圖7所示。

圖7 混淆St分支路徑

步驟6 GetSt算法。在圖7的St分支路徑混淆中，GetSt算法將通過控制流圖中的基本塊類型屬性和三元組路徑信息實現。GetSt算法規則描述如下：①下一執行基本塊由當前執行基本塊的路徑位置三元組確定；②下一執行基本塊的類型由其Attr確定。③原始基本塊N的執行與否與原始邏輯一致。④不相關基本塊I不被執行，則定義隨機被算法返回。根據以上規則描述，GetSt調度函數動態賦值算法的偽代碼實現如下。

St GetSt(Booleanb,Stc) {

Std;

intr;

BB=BN(b,c);

if (BB->Attr==N){

d=BB->St;

}else if (BB->Attr==I){

r=rand()%2;

if (r==0){

d=BB->St;

}else{

d=GetSt(BB->St,b);

}}else{

raise an exception;}

returnd;}

從以上偽代碼可以看出，首先定義St分支變量d用于動態賦值。然后調用BN(b,c)函數，該函數根據GetSt傳入的BN布爾值和St值得到一個新的基本塊BB。接著，根據基本塊BB的類型屬性Attr值分析該基本塊執行與否，并將BB的St值動態賦給d。如果基本塊BB的類型屬性Attr為N，即BB->Attr==N，則直接將該基本塊的分支變量值 (BB->St) 賦給d，即d=BB->St；如果基本塊BB的類型屬性Attr為I，即BB->Attr==I，則通過rand()隨機函數計算生成1或0的隨機數。當隨機數r等于0時，將基本塊BB的分支變量值 (BB→St) 賦給d，表示將執行不相關基本塊I。當隨機數r等于1時，則繼續調用GetSt算法將BB的下一個基本塊分支變量值 (GetSt(BB->St,b)) 賦給d，表示將不執行不相關基本塊I。最后，返回d并執行d對應的分支路徑。

3 測試與分析

本節根據Collberg提出的評價指標[17]分別對本文算法混淆前后的強度和性能進行實驗測試與分析。其中，強度是指混淆后對代碼理解的困難程度。性能是指混淆后由代碼轉換所帶來的軟硬件資源額外開銷。

3.1 強度測試

首先，對本文算法的混淆強度進行測試，構造如下函數作為測試用例。

int Test(inta,intb,intc) {

intresult=0;

intmod=a % 4;

if (mod==0) {

result=(a|0xFFEE)*(b-2);

} else if (mod==1) {

result=(a|0xEEFF)*(c-2);

} else {

result=(c&0xBBAAFFEE)*(a+b);

}

result=result+mod;

returnresult;

}

按照第2.1小節描述的步驟對以上測試用例代碼作混淆。首先，在 “result=(a|0xFFEE)*(b-2);” 之后添加非透明謂詞，使用 “7*y2-1==x2” 作為非透明謂詞表達式，該表達式永遠為假，然后插入 “result+=(a&0xFFEEDDCC);” 作為不相關塊。接著，在 “result=(c&0xBBAAFFEE)*(a+b);” 之后插入第2處非透明謂詞表達式，使用 “prime1*((x|any1)2)==prime2*((y|any2)2)” 作為非透明謂詞表達式，該表達式永遠為假。其中，prime1和prime2為任意兩個不相等的質數，any1和any2為兩個不相等的隨機正數，x和y可以是程序給的數，基于此構造 “(11*((a|5)*(a|5)))==(29*((c|9)*(c|9)))” 表達式，最后插入 “result+=(a&0xFFEEDDCC);” 作為第2處不相關塊。經過上述混淆之后的代碼如下所示。

int Test_OpaPred_Obf(inta,intb,intc) {

intresult=0;

intmod=a% 4;

if (mod==0) {

result=(a|0xFFEE)*(b-2);

if (7*a*a-1==b*b) {

result+=(a&0xFFEEDDCC);

}

}

else if (mod==1) {

result=(a|0xEEFF)*(c-2);

} else {

result=(c&0xBBAAFFEE)*(a+b);

if ((11*((a|5)*(a|5)))==(29*((c|9)*(c|9)))) {

result+=(a&0xFFEEDDCC);

}

}

result=result+mod;

returnresult;

}

接著，把以上代碼使用2.3小節描述的算法作控制流平展混淆Test_OpaPred_Flat_Obf，并利用IDA控制流圖生成模塊構建控制流圖，對比分析其混淆前后的控制流復雜度，分別如圖8和圖9所示。

圖8 測試用例原始控制流

圖9 測試用例OpaPred_Flat混淆控制流

從圖8和圖9混淆前后的控制流圖看，控制流被明顯地展平化，達到了預期的效果。把測試用例Test()代碼使用Obfuscator-LLVM混淆器使用“-mllvm-fla”選項做控制流平展混淆?；煜蟮目刂屏魅鐖D10所示。

圖10 測試用例Obfuscator-LLVM混淆控制流

從圖9和圖10的比較可知，本文控制流平展化方法較之于現有的OLLVM控制流平展化混淆效果有了較大的提高，能夠對抗反混淆技術并給程序提供更高的強度保護。進一步使用IDA插件分析圖8～圖10的控制流復雜度，測試結果見表1。其中，e表示每個控制流圖中邊的數量，n表示每個控制流圖中節點的數量，V(G)表示每個控制流圖的循環復雜度(cyclomatic complexity)[18]。

表1 程序的控制流復雜度測試結果

從表1可以看到，混淆前Test的控制流循環復雜度是4，混淆后Test_OpaPred_Flat_Obf控制流循環復雜度大大增加達到16，相比混淆前其控制流循環復雜度增加了4倍。但是，對比Obfuscator-LLVM同樣使用控制流平展算法混淆的結果，其循環復雜度只增加了1倍，達到優于Obfuscator-LLVM復雜度的效果。因此，通過控制流循環復雜度測試說明本文算法可以有效提升程序的混淆復雜度。

為了進一步測試程序的混淆強度，下面將對混淆前后測試用例的最大嵌套深度、語句數量和外部調用3個指標進行測試和分析[19]，其中最大嵌套深度是根據測試用例中分支嵌套的層數進行計算，語句數量是指測試用例中語句數量，外部調用則根據測試用例中存在的外部函數調用個數進行計算。測試工具采用SourceMonitor，表2顯示了測試結果。

表2 程序的強度指標測試結果

在表2中，混淆前Test的語句數量是10，而混淆后Test_OpaPred_Flat_Obf的語句數量增加到47，是混淆前的4.7倍。而混淆前后測試用例的外部調用數量分別為0和22，有顯著的增加。此外，最大嵌套深度有從混淆前的2變為混淆后的5，也一定增加。以上SourceMonitor不同測試指標的測試結果說明，攻擊者更難理解本文算法混淆后的程序，其強度比混淆前的程序更為復雜。

3.2 性能測試

本小節將測試分析程序混淆前后的性能，測試環境包括：CPU：Inter?CoreTMi5-4590 @ 3.30 GHz；RAM：8 G；SSD：256 G；OS：Windows 7旗艦版。首先，測試混淆前后的程序及內存使用大小，結果見表3。

表3 混淆前后程序及內存使用大小比較

從表3可以看出，混淆前Test的程序大小為11 k，混淆后Test_OpaPred_Flat_Obf的程序大小為19 k，混淆之后的程序大小相比混淆前增加72.7%，其增加的原因主要是混淆后增加了混淆代碼邏輯和基本塊的關系表。此外，混淆前后內存的使用從2704 k增加到2932 k，只有8.4%的增長率，這部分增量主要來自于混淆后調度函數動態賦值算法中所用到的基本塊的關系表，平展后的基本塊越多該表就越大，但相比于原程序的整體內存消耗，其所占的比例并不大。因此，采用本文方法混淆后的內存消耗對程序運行內存的性能影響仍然非常小。

其次，測試程序的運行時間性能，分別以1 000 000、10 000 000和100 000 000次計算混淆前后Test和Test_OpaPred_Flat_Obf的運行時間，并通過多次測試求得其平均單次運行時間，測試數據見表4。

表4 混淆前后程序運行時間比較/μs

從表4可以看出，程序算法在混淆前的運行時間隨著運算次數增加而線性增大，同時混淆后的時間增長仍然保持基本成正比的特性，并且兩個測試用例隨測試次數變化的增長率相近。從平均運行時間來看，其混淆前后的絕對運行時間依舊在很低的水平。

4 結束語

抵御控制流分析的程序保護已經成為了當今國內外軟件安全研究的熱點，其中如何提升程序的混淆強度也成為安全研究人員的重點研究課題。本文分析了程序所面臨的控制流分析與利用，對程序在解析控制流圖時容易被逆向編譯和算法重構等安全問題，提出一種針對控制流圖進行非透明謂詞插入和平展化相結合的抵御控制流分析的程序混淆保護算法，并通過對混淆前后的測試用例進行控制流循環復雜度、最大嵌套深度、語句數量和外部調用的比較測試和分析。測試結果表明了本文算法在混淆強度方面的有效性。在性能測試中，當運行數據達到一定量時，對混淆程序的大小和運行時間性能會產生一定的影響，如何在提高安全性的同時，降低對大小和時間性能的影響將是在今后工作中進一步研究的內容，包括優化調度函數動態賦值算法的內部實現，提高其執行效率。