vmp trace的優化處理
前言
在之前寫的《利用機器學習分析vmp的思路》中，把讀寫內存的操作數直接替換成了絕對地址的形式，這就產生了大量賦值語句，閱讀起來也不是很友好。寫這篇文章的主要目的是如何做進一步的優化，本篇文章用到了程序切片技術和編譯原理中的一些優化算法，復制傳播、死代碼刪除和有向無環圖DAG的局部優化。
trace的處理
在之前寫的文章基礎上對trace增加了eflags寄存器的記錄。利用程序切片技術提取了handle與寫內存相關的指令后，通過一些簡單的特征就可以處理該樣本trace中所有的handle，所以本篇沒有使用深度學習的方法對handle進行分類處理，深度學習也只是通過有標簽的handle數據集代替了人工提取特征的過程。
trace處理后會得到以下文件：
NormalCode表示正常的代碼，不需要對其優化處理，VmProcedureCode表示虛擬機中執行的代碼，后面的數字表示執行的順序。handle的識別和處理參考相應的代碼
復制傳播
復制傳播(Copy Propagation)的思想：對于給定的關于某個變量v和s的賦值v=s，在沒有出現其他關于v定值的程序范圍內，可以用s來替代出現的v的引用。
handle處理后，trace中含有大量的mov語句，可以利用復制傳播配合死代碼消除處理掉冗余的mov語句。
比如有以下指令序列：
復制代碼 隱藏代碼 b=ac=bd=c
按照復制傳播的思想，c可以用a代替，即d=a。如果c是不活躍的，那么c=b是可以刪除的。
復制傳播可以通過ud鏈(Use-Definition Chains)實現，ud鏈描述的是指令或語句中引用的變量可能定值點的位置。因為在很多情況下，一個定值是否能實際到達某一特定程序點是不可判定的，有時候需要依賴于特定的外部輸入。當然，在trace中可以直接認為都是可到達的。ud鏈的構造可以通過到達定值分析實現，但是在trace中，可以認為語句之間是順序執行的，ud鏈的構造只要向上遍歷找到最后出現的對當前變量定值的語句即可。代碼實現在VmProcedureCode類中的CopyPropagation和DeadCodeEliminatioin部分
在虛擬機的代碼中，設定的活躍變量如下：
復制代碼 隱藏代碼 eax、ebx、ecx、edx、esi、edi、esp、eip、eflags寄存器esp+4，對應虛擬機退出后的跳轉地址，去執行正常函數esp+8，正常函數執行完后的跳轉地址，通常是虛擬機的入口esp+12，可能是正常函數的參數一esp+16，可能是正常函數的參數二esp+20，可能是正常函數的參數三esp+24，可能是正常函數的參數四esp+28，可能是正常函數的參數五esp+32，可能是正常函數的參數六
以VmProcedureCode0.txt中的最后幾行代碼為例
復制代碼 隱藏代碼 0x0076591d: mov eax, dword ptr [0xffffcb5c]0x007e9342: mov dword ptr [0xffffcac8], eax0x006cbe8e: mov eax, dword ptr [0xffffcb34]0x006cbe9d: add eax, 0x77cb5a 0x0068849d: mov dword ptr [0xffffcad8], eax0x007df911: mov eax, dword ptr [0xffffcb34]0x007df919: add eax, 0x74fbf3 0x007df91b: mov dword ptr [0xffffcb60], eax 0x0068867f: mov eax, dword ptr [0xffffcb34] 0x00688684: add eax, 0x68304e 0x0068868a: mov dword ptr [0xffffcb5c], eax 0x007cf964: mov edx, dword ptr [0xffffcac8] 0x006ef09c: mov dword ptr [0xffffcb58], edx 0x006d717b: mov ebp, dword ptr [0xffffcad0] 0x006d717e: mov ecx, dword ptr [0xffffcac4] 0x006d7180: mov ebx, dword ptr [0xffffcaec] 0x006d7181: mov eax, dword ptr [0xffffcad8] 0x006d7185: mov edi, dword ptr [0xffffcae0] 0x006d7187: mov edx, dword ptr [0xffffcab8] 0x006d718d: mov esi, dword ptr [0xffffcac0] 0x006d718e: popfd
最后一行的代碼中esp=0xffffcb58，0x00688684地址處的0x68304e剛好對應虛擬機退出后的跳轉地址，0x007df919地址處的0x74fbf3對應的是下一個虛擬機入口。0x006cbe9d地址處的 0x77cb5a 對應0x68304e函數的參數，ida中0x68304e地址處的代碼反編譯如下：
復制代碼 隱藏代碼
HMODULE __usercall GetModuleHandleA_68304E@<eax>(int a1@<eax>)
{
unsigned int v1; // edx int v2; // edi CHAR v3; // al CHAR ModuleName[260]; // [esp+0h] [ebp-104h] BYREF v1 = 0;
v2 = a1 - (_DWORD)ModuleName;
do {
v3 = ModuleName[v1 + v2] ^ (v1 + __ROL4__(0x4BB06C51, v1));
ModuleName[v1] = v3;
if ( !v3 )
break;
++v1;
}
while ( v1 < 0x104 );
return GetModuleHandleA_1(ModuleName);
}
程序切片技術
程序切片技術是為了替換之前使用的污點分析，方便獲取handle中與寫內存相關的指令。
給定一個感興趣的語句以及它所使用的變量，程序切片(program slicing)是一個影響該條語句變量值的語句集合，而切片準則(slicing criterion)用來描述這個感興趣的語句及其變量。切片準則可以定義為C = <statement, variables>，statement可以為語句的唯一序號，variables為變量集。比如有以下程序，令切片準則C=<10, {product}>，箭頭左邊為原程序，箭頭右邊為對應C的程序切片。
程序切片的實現主要有基于程序依賴圖和基于數據流方程兩種方法。程序依賴圖包含數據依賴和控制依賴，它的構建可以查看鯨書等相關資料，這里只介紹基于數據流方程的方法。數據流方程迭代的公式如下：
k表示迭代次數，如果把語句當做CFG中的一個結點而不是基本塊的話，那么i和j就是一個語句，其中i是j的前驅結點。
DEF(i)和REG(i)分別表示i結點的變量定值集和引用集。
C和(b, REF(b))表示相應的切邊準則。
B[k][C]是分支語句集，表示影響S[k][C]中切片語句的分支語句集合，用來跟蹤控制依賴關系，迭代過程中當B[k][C]不在改變時，迭代終止。
INFL(b)表示從b開始到距離它最近的后向支配語句之間的路徑上除去端點以外所有語句的集合，INFL(b)在其直接后驅大于等于2時才不為空，否則為空集。INFL(b)中的語句執行受b語句執行結果的影響，控制依賴于b。
R[k]C表示結點i中與切片準則C相關的變量集合，用來跟蹤數據依賴。
S[k][C]表示程序切片。
初始化時，R[0]C等于切片準則C中的變量集variables，n為C中的statement,當n≠m時，R[0]C為空集。之后再從以下公式計算各個結點的R[0][C]和S[0][C]。
基于數據流方程的過程內切片偽算法如下：
由于vmp的handle代碼是順序執行，所以針對handle的切片處理不需要多輪迭代和控制依賴的跟蹤，也就不需要計算INFL(b)，相應的切片算法會變得很簡單，只需要一輪迭代計算出R[0][C]和S[0][C]就可以得到對應的切片。
基于DAG有向無環圖的局部優化
把基本塊轉換到DAG有向無環圖的表示，在DAG上可以對基本塊中的代碼進行一些轉換，改進代碼的質量。
龍書中的關于DAG的構造方式如下：
1）基本塊中出現的每個變量有一個對應的DAG的結點表示其初始值。
2）基本塊中的每個語句s都有一個相關的結點N。N的子結點是基本塊中的其他語句的對應結點。這些語句是在s之前、最后一個對s所使用的某個運算分量進行定值的語句。
3）結點N的標號是s中的運算符，同時還有一組變量被關聯到N，表示s是在此基本塊內最晚對這些變量進行定值的語句。
4）某些結點被指明為輸出結點（output node），這些結點的變量在基本塊的出口處活躍。也就是說，這些變量的值可能以后會在流圖的另一個基本塊中被使用到。計算得到這些“活躍變量”是全局數據流分析的問題。
針對vmp的trace主要做一些以下優化：
1、消除局部公共子表達式(local common subexpression)，公共子表達式就是重復計算一個已經計算得到的值的指令。當一個新的結點M將被加入到DAG中時，我們檢查是否存在一個結點N，它和M具有同樣的運算符和子結點，且子結點順序相同。如果存在這樣的結點，N計算的值和M計算的值是一樣的，可以用N替換M
2、常量折疊
3、使用代數規則簡算計算過程，比如vmp中not、and和or等指令組合起來的MBA表達式
以VmProcedureCode0.txt中的前面103行代碼為例
復制代碼 隱藏代碼 0x0064d71e: mov dword ptr [0xffffcfe8], ecx 0x006fa4c2: mov dword ptr [0xffffcf34], edx 0x00746037: mov dword ptr [0xffffcf3c], ebp 0x0064fb73: mov eax, 4 0x006b7076: add eax, 0xffffcff8 0x006b707f: mov dword ptr [0xffffcff4], eax 0x0075d399: mov eax, 8 0x0075d3a7: add eax, 0xffffcff4 0x0081c8fb: mov ecx, eax 0x0081c903: mov edx, dword ptr [0xffffcff4] 0x0081c906: not ecx 0x006e651b: not edx 0x006e651e: or ecx, edx 0x00750b99: mov eax, ecx 0x00750ba3: add eax, 0x20 0x00750bb2: pushfd 0x00750bba: pop dword ptr [0xffffcff4] 0x0077cd5f: mov ecx, dword ptr [0xffffcff4] 0x007294f8: mov dword ptr [0xffffcf18], ecx 0x007b85c7: mov ecx, eax 0x007b85d0: mov edx, eax 0x007b85d3: not ecx 0x007b85d6: not edx 0x007b85d8: or ecx, edx 0x007b85e0: pushfd 0x007b85e9: pop dword ptr [0xffffcff4] 0x00687ebb: mov ecx, dword ptr [0xffffcf18] 0x00687ebf: mov edx, dword ptr [0xffffcf18] 0x00674371: not ecx 0x0067437a: not edx 0x0067437f: or ecx, edx 0x00674383: mov dword ptr [0xffffcfd8], ecx 0x006a83d9: mov ecx, 0xfffff7ea 0x006a83df: mov edx, dword ptr [0xffffcfd8] 0x006a83e2: not ecx 0x006a83e4: not edx 0x006a83ed: and ecx, edx 0x006a83ef: mov dword ptr [0xffffcfd8], ecx 0x00809c7d: mov ecx, dword ptr [0xffffcff4] 0x00809c7f: mov edx, dword ptr [0xffffcff4] 0x00739b61: not ecx 0x00739b63: not edx 0x00739b65: or ecx, edx 0x00739b67: mov dword ptr [0xffffcfd4], ecx 0x00740510: mov ecx, 0x815 0x00740516: mov edx, dword ptr [0xffffcfd4] 0x00740519: not ecx 0x00740520: not edx 0x00740525: and ecx, edx 0x007f9eca: mov eax, ecx 0x007f9ed9: add eax, dword ptr [0xffffcfd8] 0x007bd4bc: mov dword ptr [0xffffcf50], 0 0x0070d7e7: mov dword ptr [0xffffcf20], ebx 0x00723792: mov dword ptr [0xffffcf14], eax 0x006f8562: mov dword ptr [0xffffcf44], esi 0x006d7d4c: mov ecx, dword ptr [0xffffcfe8] 0x006d7dab: mov dword ptr [0xffffcf28], ecx 0x007964f4: mov ecx, dword ptr [0xffffcf34] 0x0079653f: mov dword ptr [0xffffcf1c], ecx 0x007bdb9e: mov dword ptr [0xffffcf30], edi 0x0069f4d8: mov dword ptr [0xffffcf24], eax 0x007bd4bc: mov dword ptr [0xffffcf34], 0xffffcfd4 0x006f8529: mov ecx, dword ptr fs:[0] 0x006f8562: mov dword ptr [0xffffcf4c], ecx 0x0068a851: mov eax, 4 0x0068a867: add eax, 0xffffcfc0 0x0068a86e: mov dword ptr [0xffffcfbc], eax 0x007d8470: pushfd 0x007d8478: pop dword ptr [0xffffcfb8] 0x006d7d4c: mov ecx, dword ptr [0xffffcfb8] 0x006d7dab: mov dword ptr [0xffffcf48], ecx 0x007fb9d4: mov eax, 8 0x007fb9d9: add eax, 0xffffcfbc 0x007fb9ea: pushfd 0x007fb9eb: pop dword ptr [0xffffcfb4] 0x0067df7a: mov ecx, dword ptr [0xffffcfb4] 0x0067dfd4: mov dword ptr [0xffffcf2c], ecx 0x006a4226: mov ecx, dword ptr [0xffffcfbc] 0x006d370e: not eax 0x006d3710: not ecx 0x006d3712: or eax, ecx 0x006d3717: pushfd 0x006d3718: pop dword ptr [0xffffcfb8] 0x0077c25e: mov ecx, dword ptr [0xffffcfb8] 0x007e2e9f: mov dword ptr [0xffffcf38], ecx 0x00745a49: add eax, 0x454 0x00745a4e: pushfd 0x00745a4f: pop dword ptr [0xffffcfbc] 0x007964f4: mov ecx, dword ptr [0xffffcfbc] 0x0079653f: mov dword ptr [0xffffcf40], ecx 0x00697f01: mov edx, eax 0x00697f09: mov ecx, eax 0x00697f0d: not edx 0x00697f11: not ecx 0x00697f14: and edx, ecx 0x00813a43: pushfd 0x00813a4b: pop dword ptr [0xffffcfbc] 0x00764298: mov ecx, dword ptr [0xffffcfbc] 0x007bdb9e: mov dword ptr [0xffffcf18], ecx 0x00716b65: mov ecx, 0x40 0x0064c470: pushfd 0x00753bc8: mov esi, 0xffffcf14 0x00753bca: mov edi, 0xffffcab0
DAG優化后的輸出為
復制代碼 隱藏代碼 ds[0xffffcfe8] = ecxds[0xffffcf28] = ecxds[0xffffcf1c] = edxds[0xffffcf3c] = ebpds[0xffffcfd8] = 0x815 & eflags0_0ds[0xffffcff4] = eflags1_128ecx = 0xfffff7ea & eflags1_128ds[0xffffcf14] = ecx + ds[0xffffcfd8]ds[0xffffcf24] = ds[0xffffcf14]ds[0xffffcf50] = 0x0ds[0xffffcf20] = ebxds[0xffffcf44] = esids[0xffffcf30] = edids[0xffffcf34] = 0xffffcfd4ds[0xffffcf4c] = fs[0x00000000]ds[0xffffcf48] = eflags2_128ds[0xffffcfb4] = eflags3_144ds[0xffffcf2c] = eflags3_144ds[0xffffcfb8] = eflags4_0ds[0xffffcf38] = eflags4_0eax = 0x348fds[0xffffcf40] = eflags5_0edx = 0xffffcb70ds[0xffffcf10] = eflags6_128ds[0xffffcfbc] = eflags6_128ds[0xffffcf18] = eflags6_128ecx = 0x40ds[0xffffcaa4] = eflags7_128esi = 0xffffcf14edi = 0xffffcab0
eflags7_128第一個數值7表示出現次數的編號，128為eflags寄存器的值。這里用到了一個化簡規則：a = ~(~a | ~a)，在化簡前DAG的可視化如下：
藍色圈就對應a = ~(~a | ~a)的運算，那么可以直接使用a對應的結點代替這個藍色圈
如果覺得賦值語句還是多的話，也可以利用DAG刪除無用賦值。DAG的優化只支持部分x86指令，大家可以根據自己需要自行增減，代碼的實現部分在DAGoptimizer類
參考資料
《編譯器設計之路》
《編譯原理》（龍書）
《高級編譯器設計與實現》（鯨書）
基于程序分析與測試的二進制軟件漏洞挖掘技術研究
WEISER M.Program Slicing[J].IEEE Transactions on Software Engineering,1984,SE-10(4):352--357.
