分存技術在代碼混淆中的研究

楊秋翔，王 蕊，陳夠喜，牛文瑞

（中北大學 計算機與控制工程學院，山西 太原030051）

0 引 言

近年來，軟件破解者不斷運用逆向工程技術對軟件代碼進行靜態分析、動態跟蹤等攻擊。代碼混淆技術［1－2］通過代碼變換來降低程序的可理解性，使代碼更難于被靜態分析，增加了軟件被篡改或非法復用的難度。其中，代碼控制流混淆是當前代碼混淆技術中的研究熱點。目前，存在著許多種代碼控制流混淆變換［3－4］，但都由于變換形式過于單一，很容易被逆向工程所過濾。針對這種情況，文獻［5］提出不透明謂詞變換和降級高級控制結構變換，加大了反編譯及逆向工程的難度；文獻 ［6］提出插入垃圾代碼的改進的控制變換，增加了防止破解者靜態分析的能力；文獻 ［7］提出混沌不透明謂詞變換，盡可能地防止破解者對代碼進行靜態攻擊。但是這些變換最終無法確定代碼的混淆強度是否足夠抵抗攻擊，并且無法動態地檢驗破解者的非法操作。

針對混淆強度和動態檢驗非法操作的問題，本文在現有的代碼控制流混淆變換的基礎上，提出了一種基于分存技術的代碼控制流混淆方法。該方法將分存技術與常規控制變換相結合，并應用于軟件的注冊驗證機制，改變了代碼的控制流結構，增加了破解者攻擊軟件的難度，具有足夠的混淆強度，能夠隨時檢驗破解者的非法操作，成本較低且易于實現，在一定程度上實現了對代碼的安全保護。

1 相關定義

定義1 Bernstein多項式。設f（x）∈C ［0，1］，n∈Z＋，則Bernstein多項式函數Bn（x）定義為

定義2 不透明謂詞。設i∈ ｛1，2，…，n｝，-Pi，當程序中點p 上的輸出在混淆程序之前就已確定時，稱謂詞Pi在點p 上是不透明謂詞。如果Pi的輸出一直為真，就記作 （Pi）T；如果Pi的輸出一直為假，就記作 （Pi）F；如果Pi的輸出時為真時為假，就記作 （Pi）？。

定義3 偏好關系。設非空集合M＝ ｛mi，i＝1，2，…，n｝是定義于RN＋上的抵抗破解者逆向工程的所有可選方法的集合，如果對于M 中的任意兩種方法存在關系：m1m2，就可認為用戶對方法m1的評估偏好于方法m2。

假設軟件破解者對程序實施攻擊，用戶分別用方法m1和m2進行代碼保護。在理想條件下，任何代碼都可以被逆向工程所攻擊，因此可將獲得逆向工程所需的難度系數記為s（m1）與s（m2）。若s（m1）＞s（m2），則說明使用方法m1保護代碼更難被逆向分析，即s（mi）可表示為當用戶使用方法mi保護代碼時破解者的攻擊復雜度。由于偏好的方法能夠造成破解者的攻擊復雜度加倍，所以s（·）就能夠反映出偏好關系，于是用戶更偏好的方法總能被s（·）賦一個更高的值，即m1m2s（m1）≥s（m2）。

2 基于分存技術的代碼控制流混淆方法

2.1 分存技術

分存技術是將一個單載體分解為若干個多載體再進行傳輸或存儲的過程，用來增強載體信息的安全性。已有的實現分存技術的方法包括基于Lagrange插值、基于Bernstein多項式和基于中國剩余定理。由于利用基于Bernstein多項式的分存技術對載體進行分存可以實現從離散到連續的推廣，所以本文采取Bernstein多項式把軟件密鑰分解為若干個加密算法不同的密鑰段，進而在軟件程序中實現分存，以便增加代碼的安全性。

由定義1可推導為

設∑：f＝f（u，r）為一參數曲面，f（u，r）＝ ｛fi，j︱i＝0，…，n1，j＝0，…，n2｝， （u，r）D∈R2，對式（1）Bn（x）進行擴展，可得二維乘積型Bernstein多項式函數為

根據式 （2）可知二維乘積型Bernstein多項式函數可構成Bézier曲面，即兩組Bernstein多項式函數在D＝ ［0，1］× ［0，1］上可構成n1×n2次Bernstein－Bézier曲面為

利用基于Bernstein多項式的方法對載體進行分存，把軟件的密鑰按照定義1分解為不同加密算法的若干密鑰段，進而推導出式 （1）、式 （2），再根據用戶與若干密鑰段間的映射關系函數，運用式 （3）構造出多個不同的Bernstein－Bézier曲面參數方程，進而把這些曲面參數方程看作驗證函數，最終將它們隱藏在程序代碼中實現分存技術。

由于構造出了多個互不相同且個數未知的驗證函數，所以通過任意一個驗證函數的驗證都只是判斷用戶是否合法的必要條件，不是充分條件，真正合法的密鑰需要通過所有驗證函數的驗證。即使破解者攻擊了驗證函數中的任意幾個，也無法確定其總共的個數，也無法求得密鑰中任何一段的內容。即使破解者攻擊了所有的驗證函數，也必須具有一定深度的數學功底才能求得密鑰。同時為了保護驗證函數，可對其使用不同的加密算法來增強加密強度，盡可能地防止破解者通過驗證函數破解密鑰。

2.2 改進的代碼控制流混淆方法

代碼控制流混淆是在軟件發布前對程序代碼的控制流程進行變換的過程，該變換在不改變程序執行結果的前提下，盡可能地使得控制流復雜化，降低程序的可讀性，模糊程序的邏輯關系，提高程序的抗攻擊能力?，F有常用的代碼控制流混淆方法有插入垃圾代碼、使用不透明謂詞、擴展分支跳轉和循環條件等［8］。

本文改進的代碼控制流混淆方法的思想是：將分存技術應用于代碼控制流混淆，使構造出的多個互不相同的驗證函數分別與不透明謂詞和分支函數相結合，共同插入到程序代碼中。由于程序的跳轉表恢復機制是根據分支函數的判斷條件來控制跳轉的目的地址的，所以本文將在順序執行語句塊中構造出多個分支控制流，利用跳轉地址的重定向來混淆跳轉表恢復機制，使得原有的順序流程變為選擇分支，更好地改變程序代碼的控制流結構且不影響其執行過程，能夠加大混淆的強度，阻礙軟件破解者獲得準確程序代碼的信息，還可以動態地驗證非法性操作。

（1）驗證函數與不透明謂詞的結合

由于驗證函數和不透明謂詞都可以通過布爾值確定程序代碼的控制流方向，于是可以將其共同作為判斷條件插入順序執行語句塊，構造出偽分支控制流。根據定義2在程序中點p 上分別插入永真不透明謂詞 （Pi）T和永假不透明謂詞 （Pi）F，設j∈ ｛1，2，…，n｝，驗證函數的表達式為Fj，具體的插入情況如圖1、圖2所示。

圖1 順序執行塊中插入驗證函數與永真不透明謂詞

圖2 順序執行塊中插入驗證函數與永假不透明謂詞

圖1表示在順序語句A 和B中間插入的判斷條件是永真不透明謂詞和驗證函數表達式相與的運算，即插入之后的表達式為 （Pi）T＆＆Fj，并且構造出了兩個分支控制流。假定A 通過了Fj的驗證，則和 （Pi）T相與后的結果依舊為真，而反之若未能通過驗證，則和 （Pi）T相與后的結果依舊為假。將B放在分支結構為真的部分，為假的部分放入不會被真正執行的任意代碼，使得插入判斷條件后不改變程序真正的執行過程。

圖2表示在A 和B中間插入的判斷條件是永假不透明謂詞和驗證函數表達式相或的運算，即插入之后的表達式為，同樣構造出了兩個分支控制流。假定A 通過了Fj的驗證，則和 （Pi）F相或后的結果依舊為真，而反之若未能通過驗證，則和 （Pi）F相或后的結果依舊為假。將B放在分支結構為假的部分，為真的部分放入不會被真正執行的任意代碼，同樣使得插入判斷條件后不改變程序真正的執行過程。

（2）驗證函數與分支函數的結合

基于分支函數的代碼控制流混淆思想是將程序代碼中的直接跳轉語句構造為對分支函數的調用，使用分支函數替代直接跳轉，并且返回條件跳轉語句的目的地址［9］。將驗證函數與分支函數相結合，進一步擴展成用驗證分支函數替代直接跳轉語句，實現程序代碼的控制流混淆，具體的插入情況如圖3所示。

圖3表示在順序結構的分支跳轉中插入驗證分支函數，利用驗證分支函數來驗證并修改分支調用函數的目的地址，最終返回程序真正的目的地址，不改變程序的執行過程。

圖3 直接跳轉結構中插入驗證分支函數

驗證分支函數采用多重重定向結構，如圖4 所示，構造出n個分支函數，其中含有1個正確的調用分支和n－1個設置了虛假函數返回地址的偽調用分支，于是跳轉表恢復機制將產生一個包含大量虛假目的地址的跳轉表，使得軟件破解者無法正確定位程序代碼真正的目的地址。由于在調用驗證分支函數后，系統會根據跳轉表恢復機制中的跳轉目的地址執行被調函數，并立即把被調函數的返回地址壓棧，再返回調用函數處繼續順序執行下一條語句，所以在調用函數后加入若干垃圾代碼以及多個驗證函數，一方面能夠使得破解者進入大量的混淆代碼中，返回到調用函數處的下一條語句中的虛假目的地址，造成對程序的理解錯誤；另一方面能夠在返回真正正確的目的地址之前，檢測程序是否被攻擊，一旦被攻擊，驗證分支函數將返回錯誤的目的地址，響應程序運行異常。

圖4 驗證分支函數多重重定向結構

綜上所述，程序代碼的控制流依賴于分支函數內部對判斷條件的控制變量的修改，擴展分支函數是利用間接控制分支跳轉來加大條件結構的復雜度，達到混淆代碼的效果。為了隱藏跳轉的實際目的地址，使分支函數的真出口為條件跳轉的目的地址，假出口為使其跳轉到原程序接下來的下一條語句，并保證原程序模塊間的相對執行順序和功能不變。通過重構控制結構，能夠有效地提高軟件抵抗攻擊的能力，達到更深一層次的代碼保護。

3 實驗分析與驗證

代碼混淆的目的是保證軟件代碼的安全性，使代碼更難于被靜態分析或逆向工程。在實際應用中，許可注冊驗證模塊屬于軟件代碼的敏感環節，為了防止攻擊者破解注冊機，進而對關鍵代碼進行篡改或非法復用，應對注冊碼驗證過程實施有效的防范措施，于是選用基于分存技術的代碼控制流混淆方法。設用戶碼為u，注冊碼為rj，注冊機為fj，驗證函數為Fj，j∈ ｛1，2，…，n｝，具體操作的一般步驟如下：

（1）將軟件密鑰r分存成若干段rj；

（2）構造不同的f映射關系，使得：rj＝fj（u）；

（3）構造曲面參數方程Fj（u，rj），使得：Fj＝fj－1；

（4）將Fj結合常規控制流混淆方法插入軟件代碼，使代碼達到足夠的混淆強度。

本文提出的基于分存技術的代碼控制流混淆方法能夠混淆軟件代碼的控制流程，增加破解者攻擊代碼的難度，動態地保證注冊碼驗證的安全性，有效地保護代碼的安全。具體可從如下幾方面驗證：

首先，結合上文提到的兩種控制變換方法，對一段小程序進行控制流混淆變換，用反匯編工具Ollydbg2.01b對其進行反匯編分析，結果如圖5、圖6所示。

圖5 原始程序的反匯編指令

圖6 控制變換后程序的反匯編指令

由圖5和圖6中可以看出：將舉例小程序中的直接跳轉和循環函數的結構改造成了調用復雜的多分支函數的結構，利用不透明謂詞，在代碼中加入了不會被程序執行的混淆跳轉，導致變換后的代碼出現了與原始代碼結合的難以分析的垃圾代碼，造成了反匯編結果的錯誤，擾亂了代碼的控制流結構。由于最終提升了破解者恢復出原有程序控制流結構的難度，所以能夠證明這個方法起到了混淆代碼的作用。

其次，由于對于軟件代碼沒有絕對安全的保護措施，只要破解軟件的難度大于獲得合法軟件的代價時，就可認為該措施是合理安全的，于是從攻擊者破解軟件的復雜程度的角度出發，采用將加入分存技術后的控制變換與原始的控制變換的攻擊復雜度作對比的方法，判斷本文改進方法的混淆強度是否足夠抵抗攻擊，進而驗證改進方法的正確性和有效性。

以Matlab 8.0為實驗平臺，選取10個程序代碼段，比較攻擊者欲想成功破解經過兩種方法處理的軟件所需的攻擊復雜度，實驗結果如圖7所示，K 表示千行。

圖7 兩種方法處理的抗攻擊性比較

從圖7中的曲線趨勢可以看出：隨著程序代碼的行數增加，會隱藏更多個不確定的Fj，經過它們在程序內部不斷地驗證安全性和混淆控制流，會導致破解者攻擊Fj的攻擊范圍逐漸擴大，以至于攻擊程序代碼的難度相應增大，即開發者使用基于分存技術的代碼控制流混淆方法導致的攻擊者所需攻擊復雜度的倍數大于使用原始的代碼控制流混淆方法。同時，把改進方法看作方法m1，原始方法看作方法m2，從實驗結果可以得出：s（m1）＞s（m2），根據定義3足以說明m1與m2滿足關系：m1m2，即改進方法是偏好于原始方法的。經過計算得出，當程序代碼為106行時，使用改進的方法進行代碼保護效果更優，破解者的攻擊將高達10倍于軟件代碼的保護能力才能夠破解成功［10］。改進方法在一定程度上抵抗攻擊性強，更適用于大型軟件代碼的保護。

最后，由于構造的驗證函數Fj的個數未知，并且可以存在于代碼中的任何位置，所以不易被攻擊者發現，隱蔽性較強，使得攻擊者根本無法完全了解注冊機f的映射關系。將密鑰r以密文的形式寫入一個自定義格式的數據文件，注冊登錄時使用F1進行驗證，如果驗證通過就顯示注冊成功。將其它的Fj－1隱藏在程序中或與不透明謂詞和分支函數相結合，每當程序順序執行到該處或者用戶后續執行特定的操作的時候才會被調用。但是一旦任意一個F 驗證到r非法，程序就會清除r并將軟件初始化，恢復為未注冊狀態，實現動態地判斷非法操作，時刻驗證安全性，以便保護代碼的安全。綜上所述，基于分存技術的代碼控制流混淆方法是一種可行有效的代碼保護方法。

4 結束語

因為代碼混淆技術只要能夠有效地延緩被靜態分析及逆向工程就達到了保護代碼的目的，所以隨著研究的深入，會被更加廣泛地應用。本文用基于分存技術的代碼控制流混淆方法對軟件代碼的薄弱環節注冊碼驗證進行保護，與采用原始方法相比，具有更好的混淆效果，增大了破解者的攻擊復雜度，增加了軟件的抗攻擊能力，在一定條件下保證了程序抵抗逆向工程的能力。不過本方法更適合于大型軟件代碼的保護，需要在日后進一步研究更全面性的保護并考慮開銷問題。

［1］ZHAO Yujie，TANG Zhanyong，WANG Ni，et al.Evaluation of code obfuscating transformation ［J］.Journal of Software，2012，23 （3）：700－711 （in Chinese）. ［趙玉潔，湯戰勇，王妮，等.代碼混淆算法有效性評估 ［J］.軟件學報，2012，23 （3）：700－711.］

［2］XU Changzheng，DU Yujie，CHEN Yan，et al.Research of code obfuscation and its efficiency ［J］.Application Research of Computers，2009，26 （9）：3502－3505 （in Chinese）.［徐長征，杜玉杰，陳巖，等.代碼迷惑及其有效性研究 ［J］.計算機應用研究，2009，26 （9）：3502－3505.］

［3］Hang JC.Research and implementation of a code obfuscation algorithm based on control flow flattening ［D］.Xi’an：Northwest University，2010.

［4］YANG Le，ZENG Fanxing，HE Huojiao，et al.Research of obfuscating algorithms based on the garbage code ［J］.Microelectronics ＆ Computer，2011，28 （4）：127－130 （in Chinese）.［楊樂，曾凡興，何火嬌，等.一種基于垃圾代碼的混淆算 法 研 究 ［J］.微 電 子 學 與 計 算 機，2011，28 （4）：127－130.］

［5］FU Jianjing.Application of transformation techniques for code obstructing to software protection ［J］.Computer Applications and Software，2008，25 （4）：103－105 （in Chinese）. ［付 劍晶.代碼干擾變換在軟件保護中的使用 ［J］.計算機應用與軟件，2008，25 （4）：103－105.］

［6］JIANG Hua，LIU Yong，WANG Xin.Code confusion technology research based on control flow ［J］.Application Research of Computers，2013，30 （3）：897－899 （in Chinese）.［蔣華，劉勇，王鑫.基于控制流的代碼混淆技術研究 ［J］.計算機應用研究，2013，30 （3）：897－899.］

［7］SU Qing，WU Weimin，LI Zhongliang，et al.Research and application of chaos opaque predicate in code obfuscation ［J］.Computer Science，2013，40 （6）：155－159 （in Chinese）.［蘇慶，吳偉民，李忠良，等.混沌不透明謂詞在代碼混淆中的研究與應用 ［J］.計算機科學，2013，40 （6）：155－159.］

［8］WANG Chaokun，FU Junning，WANG Jianmin，et al.Survey of software tamper proofing technique ［J］.Journal of Computer Research and Development，2011，48 （6）：923－933（in Chinese）.［王朝坤，付軍寧，王建民，等.軟件防篡改技術綜述 ［J］.計算機研究與發展，2011，48 （6）：923－933.］

［9］SHANG Tao，GU Dawu.Research on resistance to disassembly of software ［J］.Application Research of Computers，2009，26 （12）：4553－4557 （in Chinese）.［尚濤，谷大武.軟件防反匯編技術研究 ［J］.計算機應用研究，2009，26 （12）：4553－4557.］

［10］WANG Rui，YANG Qiuxiang，CHEN Gouxi，et al.Software protection game model based on divided－storage strategy［J］.Journal of Computer Applications，2013，33 （9）：2525－2528 （in Chinese）. ［王蕊，楊秋翔，陳夠喜，等.基于分存策略的軟件保護博弈模型 ［J］.計算機應用，2013，33 （9）：2525－2528.］