增強型虛擬寄存器輪轉算法

潘雁，林偉

（數學工程與先進計算國家重點實驗室，河南 鄭州 450001）

1 引言

數據流分析是逆向分析中重要的方法之一，各類數據流分析工具與方法層出不窮[1,2]，如二進制插樁框架Pin[3]、動態污點傳播分析技術[4]、符號執行技術等，用以輔助逆向分析人員進行數據流分析。其中，在對虛擬機代碼保護的逆向分析中，Sharif[5]對被保護程序執行過程中的數據流信息進行記錄，然后采用動態數據流分析和污點分析的方法對記錄的程序軌跡進行分析，構建控制流圖等數據結構，為進一步分析奠定基礎；黃荷潔等[6]提出一種基于動態數據流分析的破解方法，通過Pin記錄代碼在虛擬機執行過程中的數據流信息，整理分析可有效還原算法的控制流圖，輔助逆向分析人員的算法重構。

在代碼混淆領域，由于在匯編語言層面數據流混淆難以操作，因此數據流混淆主要針對源代碼混淆。而在虛擬機代碼保護領域，為對抗數據流分析，徐方華等[7]提出解釋函數跳轉表的隨機輪轉機制，跳轉表是維持整個虛擬機解釋器執行流程的重要數據結構，虛擬機調度器通過跳轉表實現虛擬機字節碼和虛擬指令解釋函數之間的映射，該方法通過在每次執行一條字節碼后動態亂轉跳轉表，增大逆向分析的跟蹤難度；Wang等在文獻[8]中提出在虛擬指令中添加寄存器旋轉指令（RRI，register rotation instruction），其主要功能是在執行過程中通過旋轉改變虛擬寄存器之間的對應關系，其虛擬指令為RRI operand1, operand2，其中第2個操作數表明其將會旋轉幾個單位。該指令可以在字節碼序列中任意插入，使虛擬寄存器與字節碼之間的對應關系在該特殊指令前后發生變化，能在一定程度上增加逆向分析的難度，但缺乏隱蔽性，逆向分析人員識別該特殊指令后可對其他的樣本進行同樣的分析。

符號執行技術、污點分析技術的發展提升了數據流分析的能力，為更好地對抗基于數據流分析的語義攻擊，本文基于跳轉表、虛擬寄存器輪轉的思想，詳細分析虛擬寄存器在虛擬機代碼保護過程中的關鍵作用，改進寄存器旋轉的機制，提出一種增強型虛擬寄存器輪轉算法。

2 虛擬機代碼保護框架

2.1 虛擬機代碼保護技術概述

虛擬機保護的核心思想是利用自定義指令系統和現有指令系統之間的差異性，增加逆向分析的難度。它虛擬出一套自己設計的指令系統，用于將一系列指令放在一個解釋引擎中執行。在該指令系統中，大部分常用的匯編指令，都可以用虛擬機中的相應指令代替[9]。

虛擬機保護機制如圖1所示，具體保護步驟如下。

Step1 提取待保護程序 P中使用軟件開發工具包（SDK，software development kit）標識的目標代碼。

Step2 將目標代碼翻譯為虛擬指令序列，稱為虛擬指令翻譯過程。

Step3 虛擬指令經虛擬編譯為字節碼，稱為虛擬編譯過程，與Step2合稱為虛擬化過程。

Step4 構造解釋函數集合和解釋函數跳轉表。

Step5 重建可執行程序文件，將虛擬機上下文、字節碼、解釋函數、調度器重新構成新節或加至最后一節，并在目標代碼處填充垃圾代碼。

圖1 虛擬機代碼保護機制

一個被虛擬機保護的程序主要由虛擬機字節碼指令、虛擬機調度器、虛擬指令解釋函數和虛擬機上下文組成。其中，虛擬機解釋器由虛擬機調度器和虛擬指令解釋函數組成。虛擬機保護通常采用中心解碼結構，此外還會采用一些線性結構。在虛擬機運行過程中，虛擬機解釋器先通過虛擬機調度器循環進行取指——解碼操作，然后交由虛擬指令解釋函數進行解釋執行。

隨著逆向分析技術的發展以及逆向分析者對虛擬機結構、解釋函數的持續分析，虛擬機代碼保護技術逐漸被攻破[10～12]。與此同時，正向保護研究人員不斷以虛擬機代碼保護框架中的各個模塊為對象研究新的混淆方法，并將隨機化、動態多樣化思想應用于虛擬機代碼保護技術。

1) 解釋函數：房鼎益等[13]提出通過設計數據流混淆引擎對解釋函數進行數據流混淆，增大數據流結構的復雜性；謝鑫等[14,15]提出對所有解釋函數進行變長切分和隨機亂序，實現代碼并行化與虛擬機多樣化；Wang等[16,17]提出指令等價替換來增強多解釋函數序列間的差異性，并通過隨機選擇路徑以抵御累積攻擊。

2) 虛擬機上下文：使用多個上下文代替單個，并動態跳轉，增大數據流分析難度[18]。

3) 虛擬機調度器：使用多個虛擬機調度器，并在每一個解釋函數后插入一個控制單元指令，隨機決定跳轉的下一個調度器，將單一的循環調度結構擴充為循環結構與鏈式結構混合調度結構[19,20]。

4) 指令集隨機化：每次執行保護時打亂字節碼與解釋函數的對應關系，使不同的保護程序中字節碼語義不同，延長攻擊者的分析時間[21,22]。

總結分析研究現狀，本文以對抗語義攻擊為目標，將關注點放在虛擬寄存器。

2.2 虛擬寄存器

機器指令由操作碼與操作數構成，操作數主要包括寄存器、內存、立即數。虛擬機中字節碼與機器指令類似，組成結構如圖2所示，包含操作碼與操作數，其中，操作碼占2 byte，操作數則對應虛擬寄存器和立即數，因此，虛擬寄存器在虛擬機代碼保護過程中記錄數據流轉，是極為重要的組成部分。在解釋執行過程中，基于堆棧的虛擬機通過開辟內存空間的方式存儲虛擬機上下文，虛擬機上下文提供虛擬執行過程中所需的緩存空間，包括虛擬棧、虛擬寄存器、密鑰等，每個部分隨機分布在新開辟的內存空間。以本文研究的對象——虛擬寄存器為例，若干個虛擬寄存器順序存儲于內存。其中，每個虛擬寄存器對應的數字代表其在虛擬編譯過程中的字節碼，即其在內存中的偏移，稱該對應關系為虛擬編譯映射。例如，VR1→6，表示編譯過程中 VR1被虛擬編譯為二進制0x06，該映射關系在每次混淆過程中都是隨機生成的。在解釋執行時，解釋函數會依據每條字節碼的操作數，根據偏移到內存中操作相應的虛擬寄存器，稱此對應關系為解釋執行映射。

圖2 VRR-VM虛擬指令實例

3 輪轉算法實現

寄存器輪轉算法的基本原理如圖3所示，由于虛擬寄存器在內存中是線性存儲的，因此輪轉算法需要在邏輯上模擬環形旋轉，虛擬機在解釋執行字節碼時需要依據當前狀態下的對應關系操作相應的內存，而輪轉算法使對應關系在運行過程中是動態的。原始的對應關系如圖3左側，經左旋一個單位后，對應關系如右側，對于虛擬寄存器VR3，在旋轉之前，其對應的字節碼為0，即在內存中的偏移的0*32，而經過旋轉后其對應的字節碼為1，即其在內存中的偏移為1*32。

圖3 寄存器輪轉原理示意

依據寄存器輪轉混淆算法的原理，該算法需在虛擬編譯過程與解釋執行過程分別對虛擬編譯映射和虛擬機上下文進行調整，以保證程序的正確執行。特別地，在解釋執行過程中解釋執行映射關系是不變的。在虛擬編譯過程中，對于每一類虛擬指令都采用輪轉策略，隨機輪轉n個單位長度，同時實時更新每條指令對應的虛擬編譯映射關系；在解釋執行過程中，每一類虛擬指令對應的解釋函數執行時，伴隨著內存的輪轉操作，其輪轉的單位長度同虛擬編譯時相同。

而在邏輯上，字節碼的生成過程是靜態分析的過程，而在字節碼的解釋執行過程中存在跳轉、循環等動態執行過程，因此，若對所有的虛擬寄存器進行旋轉，其在靜態分析過程中形成的旋轉順序，在動態執行中會被打亂。因此，虛擬寄存器輪轉是相對的，在解釋執行過程中必須要存在不變的虛擬寄存器，如圖4所示。因此，對于每條字節碼來說，虛擬寄存器是輪轉的；對被保護的 X86指令來說，虛擬寄存器是不變的，否則程序是無法正確執行的。而從逆向分析者的角度，由于每條 X86指令都被虛擬化為多條虛擬指令，因此，從虛擬指令角度看，X86指令是不存在分界線的。所以，對于逆向者虛擬寄存器始終是輪轉的。

圖4 寄存器輪轉示意

綜上，虛擬寄存器輪轉算法如下所示。

1) 虛擬編譯過程輪轉算法

① 初始化虛擬編譯映射關系 reg_opcode[VMR_NUM];

② 選取輪轉的虛擬寄存器數目VMR_ROTATE_NUM；

③ for 每條虛擬指令

④ 將reg_opcode[VMR_ROTATE_NUM]旋轉n個單位;

⑤ 虛擬指令編譯為字節碼;

⑥ end for

⑦ 得到字節碼序列

2) 解釋執行過程輪轉算法

① for 每條虛擬指令

② 將內存旋轉n個單位;

③ 解釋執行當前字節碼;

④ end for

⑤ 完成解釋執行

而對于每條指令輪轉的單位長度，本算法提供3種機制進行隨機選取，如下。

① 每一類虛擬指令擁有獨立的輪轉單位長度，在虛擬機初始化時，每一類虛擬指令隨機設定固定值，而在解釋執行時需將其硬編碼至對應的解釋函數。

② 每一類虛擬指令擁有獨立的輪轉單位長度，其輪轉單位長度采用該類虛擬指令字節碼的變換值，優點是輪轉單位長度無需硬編碼，同時保證隨機性。

③ 每一條指令擁有獨立的輪轉單位長度，可以使用其操作碼、操作數為基進行變換以獲取其輪轉的單位長度，優點是相較于前2種機制都更為復雜。

對于不同次混淆，其輪轉單位長度的選取都是隨機的；而對于同一種機制，每一類或每一條虛擬指令都會進行隨機的輪轉；而對于虛擬寄存器的輪轉，在解釋執行過程中，為保證內存中寄存器與編碼的正確對應關系，解釋函數的每次執行都伴隨著內存中寄存器的旋轉，增加了數據流的復雜性。

4 實驗及分析

4.1 理論分析

在抗逆向分析方面，虛擬寄存器隨機輪轉算法較為隱蔽地打亂虛擬寄存器與操作數的虛擬編譯映射關系，增加了數據流向的復雜性，混淆了逆向分析者對虛擬指令操作數的識別；同時輪轉長度選取機制的隨機性增強了虛擬機代碼保護系統的多樣性。

具體來說，假定寄存器初始化布局如圖3左側，某明文字節碼序列如表1第一列所示，其中，字節碼A2標識的虛擬指令為V_Pop，2D標識的虛擬指令為V_Mov，對應寄存器的初始化布局，第一條指令的第一操作數 03對應的寄存器為VR7，由于每執行一條字節碼，寄存器對應關系將逆時針旋轉n個單位，類似于復式替換密碼。假定該條虛擬指令執行時旋轉了3個單位，因此下一條指令的第一操作數 01對應 VR1，第二操作數對應VR7，因此其對應的助記符指令序列正確識別應為第三列，而逆向分析者在未破解寄存器輪轉之前會錯誤識別為第二列，其實際意義將會被完全曲解。

即使逆向分析者發現了寄存器輪轉這一策略，解釋函數在連續執行的過程中隨機輪轉虛擬寄存器，充滿了不確定性，導致分析人員不容易分析清代碼究竟訪問的是哪一個寄存器。因此，分析者靜態還原虛擬機是比較困難的，而動態調試過程中只要出現一個偏差，就會導致后續的指令分析錯誤。

表1 字節碼與助記符指令序列對應關系

在時間與空間開銷方面，在構成的虛擬機代碼保護系統中，該算法在解釋函數中增添了一個內存旋轉單元，在控制旋轉長度的前提下，其帶來的多余空間開銷相較整個系統較小，而由于內存旋轉單元將對內存進行旋轉，所以帶來的時間開銷將由平均旋轉長度決定。

4.2 實驗驗證

本文實驗環境為 Windows 7操作系統，Intel(R) Core i7-6700 CPU @ 3.40 GHz處理器，32 GB內存，編譯環境為Visual Studio 2012，采用的實例為Validity.exe，結合源碼以及逆向分析工具為IDA與OllyDbg來驗證虛擬寄存器隨機輪轉算法的有效性。

實驗1 有效性分析

對保護代碼中的第一條指令xor eax，eax進行跟蹤。在虛擬化過程中，目標指令經由虛擬指令翻譯得到11條虛擬指令，而后通過虛擬編譯生成對應的字節序列，如圖5所示，其中，第7條虛擬指令處理了真實的xor功能，其余虛擬指令用以實現對操作數和符號的處理。

容易發現，在虛擬指令中第2條與第7條虛擬指令的目標操作數同為虛擬寄存器 VR41，而在虛擬編譯過程中，第2條的VR41編譯為14，而第7條的VR41編譯為0C，在未采用寄存器輪轉算法的虛擬機代碼保護系統中，兩條語句的VR41將被編譯為相同的二進制。相同地，第3條與第7條虛擬指令也存在相同的情況。逆向分析者在僅獲取字節碼的前提下，必須分析虛擬寄存器的輪轉策略，以獲取虛擬指令的語義，否則差之毫厘，謬以千里。

圖5 X86指令到字節碼的轉換

在解釋執行過程中，為對應虛擬編譯過程中的輪轉策略，需對內存進行旋轉。虛擬機寄存器在內存中的分布如圖6所示，前11個DWORD是在執行過程中不進行旋轉操作的寄存器，后32個DWORD是進行旋轉操作的寄存器。由于第一條虛擬指令是垃圾指令，因此從第二條指令開始分析。第二條指令執行結束，偏移位20處被賦值，在下一條指令執行之前內存已被修正，向左旋轉了一個單位，效果如圖7所示，若內存中數值較多，會極大地影響數據的分析。同時，由于輪轉長度的不確定性，逆向分析人員需跟蹤每條虛擬指令，若想通過自動化工具進行分析，則必須完全理解輪轉的機制，包括輪轉的算法與長度選擇的機制。

圖6 虛擬寄存器在內存中的分布

圖7 虛擬寄存器輪轉效果

實驗2 算法帶來的額外時間與空間開銷

為驗證算法帶來的時間與空間開銷，本節將采用該算法與未采用該算法虛擬機代碼保護系統進行比較，其中，輪轉算法的平均輪轉長度為 2，測試用例采用有效性程序Validify.exe、希爾排序ShellSort.exe、插入排序InsertionSort.exe、冒泡排序BubbleSort.exe和快速排序QuickSort.exe。

表2是2種策略保護前后文件大小變化，表3是目標代碼執行時間開銷比較，可見該算法增加的空間開銷極小，但時間開銷增長較大，且與平均輪轉長度正相關，如圖8所示。

表2 有無輪轉算法策略保護前后文件大小變化

表3 有無輪轉算法策略保護前后目標代碼執行時間變化

圖8 時間增長率與平均輪轉長度相關性

實驗3 原型系統與商業軟件的對比情況分析

該實驗從時間和文件大小2個角度來對比分析原型系統與商業軟件的性能，其中，CV（code virtualizer）版本號為2.2.1.0，使用的虛擬機類型為Tiger32 White；VMP（virtual machine protection）版本號為2.13.8，采用最快速度策略進行虛擬機保護。測試用例選用4類排序程序，如表4所示，其中，目標代碼指令數為靜態反匯編得到的指令數；排序的輸入為500位隨機數；同時，為消除計算機產生的時間誤差，執行時間為將目標代碼循環執行10次的結果。

表4 測試用例描述

表5為保護前后文件大小變化，表6為保護前后目標代碼執行時間變化，其中，執行時間與指令膨脹率正相關，由于每次執行時間都有所不同，圖表中執行時間為10次執行時間的平均值。為了更加直觀地比較不同方法之間的差別，將數據進行一定的處理后做出下列比較，如圖9和圖10所示，其中，將CV保護的文件大小縮小5倍，圖10中采用的數據是3種方法與保護前運行時間的比例。由圖表可知，原型系統時間與文件的增加比例與商業軟件VMProtect接近，而相較于CV則有文件開銷上的優勢。

表5 保護前后文件大小變化

表6 保護前后目標代碼執行時間變化

圖9 文件開銷比較

圖10 時間開銷比較

5 結束語

惡意的逆向分析給軟件保護帶來嚴峻的挑戰，代碼混淆與虛擬機代碼保護技術能對軟件中的代碼與數據進行保護，增加程序的控制流與數據流的復雜度，以對抗逆向分析。本文關注虛擬機代碼保護框架中的數據流，以虛擬寄存器為著力點，通過在虛擬機解釋執行過程中變換虛擬寄存器與字節碼中操作數的對應關系，增大字節碼在執行過程中的不確定性，有效增加了虛擬機在解釋執行過程中的數據流復雜度；與此同時，隨機采用3種機制對輪轉長度進行設定，增強了虛擬機代碼保護系統的多樣性。最后，設計并實現了基于虛擬寄存器輪轉的虛擬機代碼保護原型系統，通過有效性用例驗證了算法的有效性與可行性，并借助性能測試用例對比了其相對于不添加虛擬寄存器輪轉的原型系統的時間與空間開銷，通過控制平均輪轉長度能將時間開銷控制在一定比例之內；對比商業軟件則具有相近的時間與空間開銷。

以該算法為基礎，今后可研究的方向包括：1) 輪轉策略具有一定的改進空間，可以采取更復雜的輪轉策略替代較為簡單的旋轉；2) 由于虛擬寄存器是存放在新的內存空間，因此可擴展至對虛擬機上下文輪轉，具有更強的混淆效果；3) 本文的原型系統是堆棧機，相較而言，基于寄存器的虛擬機具有更復雜的數據流信息，若將寄存器輪轉算法應用于基于寄存器的虛擬機，可能將會擁有更好的混淆效果。

參考文獻：

[1]NEWSOME J, SONG D. Dynamic taint analysis for automatic detection, analysis, and signature generation of exploits on commodity software[J]. Chinese Journal of Engineering Mathematics,2005, 29(5)：720-724.

[2]徐欣. 動態數據流分析技術在惡意軟件分析中的應用研究[D].合肥： 中國科學技術大學, 2016.XU X. Research of dynamic data flow analysis technology application in malware analysis[D]. Hefei： University of Science and Technology of China, 2016.

[3]REDDI, JANAPA V, ALEX, et al. PIN： a binary instrumentation tool for computer architecture research and education[C]//The Workshop on Computer Architecture Education, 2004：22.

[4]CHOW J, PFAFF B, GARFINKEL T, et al. Understanding data lifetime via whole system simulation[C]//Usenix Security Symposium, 2004：321--336.

[5]SHARIF M, LANZI A, GIFFIN J, et al. Automatic reverse engineering of malware emulators[C]//2009 30th IEEE Symposium on Security and Privacy. 2009： 94-109.

[6]黃荷潔, 康緋, 舒輝,等. 基于動態數據流分析的虛擬機保護破解技術[J]. 計算機工程, 2014, 40(9)：59-65.HUANG H J, KANG F, SHU H, et al. Reverse technology of virtual machine protection based on dynamic dataflow analysis[J].Computer Engineering, 2014, 40(9)：59-65.

[7]徐方華. 基于虛擬堆的虛擬保護技術的研究[D]. 昆明：云南大學 , 2013.XU F H. Research on virtual protection technology based on virtual heap[D]. Kunming： Yunnan University, 2013.

[8]WANG H, FANG D, LI G, et al. NISLVMP： improved virtual machine-based software protection[C]//The Ninth International Conference on Computational Intelligence and Security. 2013：479-483.

[9]舒柏程, 李毅超, 曹躍. 基于虛擬機的軟件保護技術研究[J]. 計算機工程與科學, 2008, 30(A1)： 25-28.SHU B C, LI Y C, CAO Y. Research on software protection based on virtual machine[J]. Computer Engineering & Science, 2008,30(A1)： 25-28.

[10]GHOSH S, HISER J, DAVIDSON J W. Replacement attacks against VM-protected applications[C]//ACM Sigplan/sigops Conference on Virtual Execution Environments. 2012：203-214.

[11]COOGAN K P. Deobfuscation of packed and virtualization- obfuscation protected binaries[D]. Arizona： University of Arizona, 2011.

[12]COOGAN K, LU G, DEBRAY S. Deobfuscation of virtualization-obfuscated software： a semantics-based approach[C]//ACM Conference on Computer and Communications Security. 2011：275-284.

[13]房鼎益, 張恒, 湯戰勇,等. 一種抗語義攻擊的虛擬化軟件保護方法[J]. 四川大學學報(工程科學版), 2017, 49(1)：159-168.FANG D Y, ZHANG H, TANG Z Y, et al. DAS-VMP： a virtual machine-based software protection method for defending against semantic attacks[J]. Journal of Sichuan University (Advanced Engineering Sciences), 2017, 49(1)： 159-168.

[14]謝鑫, 劉粉林, 蘆斌,等. Handler混淆增強的虛擬機保護方法[J].計算機工程與應用, 2016, 52(15)：146-152.XIE X, LIU F L, LU B, et al. Virtual machine protection based on Handler obfuscation enhancement. Computer Engineering and Applications, 2016, 52(15)：146-152.

[15]謝鑫, 劉粉林, 蘆斌, 等. 一種基于代碼并行化和虛擬機多樣化的軟件保護方法[J]. 小型微型計算機系統, 2015, 36(11)： 2588-2593.XIE X, LIU F L, LU B, et al. Software protection scheme based on code parallelization and virtual machine diversity[J]. Journal of Chinese Computer Systems, 2015, 36(11)：2588-2593.

[16]房鼎益, 趙媛, 王懷軍,等. 一種具有時間多樣性的虛擬機軟件保護方法[J]. 軟件學報, 2015, 26(6)：1322-1339.FANG D Y, ZHAO Y, WANG H J, et al. Software protection based on virtual machine with time diversity[J]. Journal of Software, 2015,26(6)： 1322-1339.

[17]WANG H J, FANG D Y, LI G, et al. TDVMP： Improved virtual machine-based software protection with time diversity[C]//ACM Sigplan on Program Protection and Reverse Engineering Workshop.2014：1-9.

[18]WANG H J, FANG D Y, LI G, et al. NISLVMP： improved virtual machine-based software protection[C]//The Ninth International Conference on Computational Intelligence and Security.2013：479-483.

[19]KUANG K, TANG Z, GONG X, et al. Exploiting dynamic scheduling for vm-based code obfuscation[C]//IEEE Trustcom/bigdatase/ispa. 2017：489-496.

[20]KUANG K, TANG Z, GONG X, et al. Enhance virtual-machine-based code obfuscation security through dynamic bytecode scheduling[J]. Computers & Security, 2018, 74： 202-220.

[21]TANG Z, LI G, FANG D, et al. Code virtualized protection system with instruction set randomization[J]. Journal of Huazhong University of Science & Technology, 2016.

[22]XU J F, ZHANG W, SUN B. Research on software protection based on virtual machine[J]. Journal of China Universities of Posts &Telecommunications, 2012, 19(S1)：122-126.