一種基於SimHash算法的二進位文件快速比較方法與流程
2023-07-01 22:20:56 4
本發明主要涉及到計算機系統安全技術領域，特指一種基於SimHash算法的二進位文件快速比較方法。
背景技術：
隨著計算機技術的飛速發展和網際網路的廣泛應用，軟體自身的規模也隨著功能的多樣性而變得越來越大。日趨豐富的功能在給用戶帶來良好體驗的同時，也帶來了諸多安全問題。同時，一定規模的軟體難免會使用第三方的組件，而第三方的組件往往缺乏原始碼：如微軟系統的動態連結庫文件，欲對這樣的軟體進行代碼審查，逆向工程手段幾乎是唯一的選擇。
在逆向工程中，靜態分析的主要任務是全部或部分恢復二進位文件中被完全抹除的函數和數據信息，為後續版本的系統分析、設備攻擊和控制利用的關鍵點定位等工作奠定基礎。但由於當前軟體版本眾多、規模龐大，使這項工作越來越無法依靠人力來完成。因此自動化逆向需求應運而生。在這其中所用到的主要方法就是二進位文件的比對技術。
目前，常用的二進位文件比對方法大致有四種，分別是基於源文件的二進位字節內容比較、基於源文件反彙編後的彙編指令比較、基於彙編指令的相似性圖形比較和基於彙編指令的結構化圖形比較。這幾種方法按照先後順序不斷克服前面方法存在的缺陷，但對於一些大型複雜的二進位文件而言，這些方法仍存在著不足。
現有的二進位比較方法中，除直接比較二進位內容的方法外，大都採用了：提取特徵，遍歷函數集合尋找匹配函數，迭代修正匹配結果的三步走流程。對於兩個二進位文件A和B。假設N(A)表示A中函數的個數，N(B)表示B中函數的個數，t表示兩個特徵籤名比較所需要的時間，n表示循環迭代次數。則該算法流程的時間複雜度大致為O(n*N(A)*N(B)*t)。雖然後續的一些方法做了改進，能逐步縮小比較的集合，但從整體時間複雜度上分析，並沒有明顯的提升。對於某些大型軟體而言，反彙編後的函數集合往往為幾十萬甚至上百萬，對於這些軟體而言傳統方法的比較次數達到了1010～12次(不計較特徵匹配時間和迭代次數)，這樣的時間效率令人無法接受，需要一種新的方法能縮小比較的集合，只計算那些可能相似的函數之間進行匹配。
技術實現要素：
本發明要解決的技術問題就在於：針對現有技術存在的技術問題，本發明提供一種通用性好、具有較高效率和準確度的基於SimHash算法的二進位文件比較方法。
為解決上述技術問題，本發明採用以下技術方案：
一種基於SimHash算法的二進位文件比較方法，其步驟為：
S1：利用IDA Pro的擴展功能，編寫插件對二進位文件進行信息提取；所述信息包括二進位文件的彙編指令序列、控制流圖、調用流圖信息；
S2：對提取到的二進位文件信息進行預處理；
S3：對預處理過後的二進位文件信息進行關鍵字定義；
S4：對提取到的關鍵字進行權重衡量；
S5：利用提取到的關鍵字及其權重，計算函數的SimHash指紋特徵，並對指紋特徵進行存儲；
S6：基於查詢後的相似結果，再採用基於結構化匹配的經典算法進行精確匹配。
作為本發明的進一步改進：在步驟S3中，對關鍵字的定義考慮：單個指令、基本塊、基本路徑；取單個指令的操作碼和操作數作為關鍵字，用SPP算法計算每個基本塊的SPP值，基本路徑的SPP值作為關鍵字。
作為本發明的進一步改進：在步驟S4中，關鍵字重要性程度為：基本路徑＞基本塊＞單個指令；對於單個指令而言，其操作碼和操作數的權重為1；於基本塊而言，其權重為其SPP值；對於基本路徑而言，其權重為該路徑所經過的指令數目。
作為本發明的進一步改進：在步驟S3的詳細流程為：
S301：對控制流圖進行分割塊合併；
S302：對指令序列進行寄存器模糊化處理；
S303：對指令序列中的地址信息進行重定向。
作為本發明的進一步改進：在步驟S301中，CFG中當一個基本塊只有一個子塊，且該子塊也只有一個父塊時，這兩個基本塊就被定義為分割塊；假設函數F中所有基本塊的集合為B，p(a)為CFG中基本塊a的父節點的集合，c(a)為CFG中基本塊a的子節點的集合，e(a，b)為CFG中以a為起點，b為終點的一條邊，流程為：
i.遍歷集合B中的基本塊；如果已遍歷完，則跳轉到步驟v；否則，從集合B中取基本塊b，執行步驟ii；
ii.如果基本塊b的子節點集合c(b)的大小為1，執行步驟iii，否則返回i；
iii.令a＝c(b)，如果基本塊a的父節點集合p(a)的大小為1，執行步驟iv，否則返回i；
iv.將b和a合併為新的基本塊c；同時，移除邊e(b，a)，{e(x，b)|x∈p(b)}和{e(a，x)|x∈c(a)}；並建立新的邊{e(x，c)|x∈p(b)}和{e(c，x)|x∈c(a)}；同時將基本塊c加入集合B中，返回步驟i；
v.結束。
作為本發明的進一步改進：在步驟S303的流程為：
i.對於代碼段跳轉指令而言，在提取特徵值時忽略指令後的偏移地址，選擇目的地址塊的哈希值作為特徵；
ii.對於數據段的數據指針，提取該指針所索引的數據值的opcode作為特徵。
作為本發明的進一步改進：所述步驟S5的流程為：
S501：函數的SimHash指紋特徵計算；
S502：函數的SimHash指紋特徵存儲；
S503：函數的SimHash指紋特徵查詢。
作為本發明的進一步改進：所述步驟S501的流程為：
i.設一個32維的向量V和一個32位的二進位數S，並將它們初始化為0；
ii.設關鍵字集合為K，s(k)＝{hash(k)|k∈K}為關鍵字k的長度為32位的哈希值，v(k)為關鍵字k的權重；
iii.對於每一個關鍵字k∈K，for(i＝0 to 31)：如果s(k)的第i位為1，則V的第i個元素加上v(k)，否則減去v(k)；
iv.對所有的關鍵字按照步驟iii進行操作後，如果V的第i個元素大於0，則將S的第i位置為1，否則為0；最後的輸出S即為函數的指紋特徵。
作為本發明的進一步改進：所述步驟S502的流程為：
i.遍歷二進位文件的函數集合F，對於每一個函數f∈F，計算指紋S(f)；
ii.建立一個8位的索引表，索引範圍為：0～255；
iii.對每個指紋S(f)的32位二進位表示，按照31～24，23～16，15～8，7～0分成4段，每段8位，將完整的32位指紋存在這4段所表示的索引項中。
作為本發明的進一步改進：所述步驟S503的流程為：
i.遍歷待匹配文件的函數集合F，對於每一個函數f∈F，計算指紋S(f)；
ii.對每個指紋S(f)的32位二進位表示，按照31～24，23～16，15～8，7～0分成4段，每段8位；記為S1，S2，S3，S4；
iii.將S1，S2，S3，S4作為索引項，在已擁有知識庫的二進位文件中進行查詢。
與現有技術相比，本發明的優點在於：
1.本發明的基於SimHash算法的二進位文件比較方法，具有很好的通用性，重點解決了時間效率這一根本問題，使得對大型軟體的比較成為可能。同時，在對函數提取特徵時，更多關注函數的結構特徵和關聯關係，並採用SimHash算法將函數的不同特徵進行綜合評價，使得對於採用代碼混淆技術等的複雜軟體比較成為可能。
2.本發明的基於SimHash算法的二進位文件比較方法，二進位文件比較的準確性好。在本發明所提出的方法中，首先對基本塊和基本路徑採用了SPP算法提取其關鍵字，解決了其內部指令重排的問題；同時，在對提取函數的SimHash指紋特徵時，由於SimHash的無序性和關鍵字的結構化特性，進一步解決了由於微小改變和指令重排導致的誤判，提高了函數的匹配準確率。
3.本發明的基於SimHash算法的二進位文件比較方法，具有較好的高效性。採用本發明所提出的方法，對於A中的每個函數的特徵指紋(32位)，將其分為4段(每段8位)，利用這4段作為索引，在B的指紋索引表中查找索引項。則對於每個索引，最多會返回2(y-8)個候選結果。時間比較複雜度從2x+y降為4*2x+y-8＝2x+y-6。對於一些大型程序，大大減少了比較耗時，達到了快速查詢的目的。
附圖說明
圖1是本發明方法的流程示意圖。
具體實施方式
以下將結合說明書附圖和具體實施例對本發明做進一步詳細說明。
如圖1所示，本發明的一種基於SimHash算法(相似哈希，Similarity Hashing)的二進位文件比較方法，步驟為：
S1：利用IDA Pro的擴展功能，編寫插件對二進位文件進行信息提取；所述信息包括二進位文件的彙編指令序列、控制流圖、調用流圖等信息。所述IDA Pro為交互式反彙編器專業版(Interactive Disassembler Professional)。
S2：對提取到的二進位文件信息進行預處理。
S3：對預處理過後的二進位文件信息進行關鍵字定義。
在具體應用實例中，關鍵字的定義主要考慮以下幾個方面：單個指令、基本塊、基本路徑。
a)單個指令作為函數實現其功能的基本單元，是函數的基本特徵之一。取單個指令的操作碼和操作數作為關鍵字；
b)基本塊作為函數控制流圖中的節點，反映了函數的內部結構特徵。本發明採用SPP算法計算每個基本塊的SPP值。由於SPP算法的無序性和可重複性，解決了指令重排所造成的指令序列不同的問題。因此可將SPP值作為關鍵字；
c)基本路徑，基本路徑為函數功能實現的途徑，功能大體相同的函數，其基本路徑基本相同，可將基本路徑的SPP值作為關鍵字。
S4：對提取到的關鍵字進行權重衡量。
在具體應用實例中，關鍵字重要性程度為：基本路徑＞基本塊＞單個指令。對於單個指令而言，其操作碼和操作數的權重為1。對於基本塊而言，其權重為其SPP值。對於基本路徑而言，其權重為該路徑所經過的指令數目。
S5：利用提取到的關鍵字及其權重，計算函數的SimHash指紋特徵，並對指紋特徵進行存儲。
在對帶匹配二進位文件和基準二進位文件中所有函數進行完指紋特徵計算和存儲後，利用指紋特徵對待匹配函數進行相似函數查詢。
S6：基於查詢後的相似結果，再採用基於結構化匹配的經典算法進行精確匹配。
作為較佳的實施例，本發明的上述步驟S3的詳細流程為：
S301：對控制流圖進行分割塊合併。分割塊的定義為：「CFG中當一個基本塊只有一個子塊，且該子塊也只有一個父塊時，這兩個基本塊就被定義為分割塊，CFG為函數控制流程圖(Control Flow Graph)」。假設函數F中所有基本塊的集合為B，p(a)為CFG中基本塊a的父節點的集合，c(a)為CFG中基本塊a的子節點的集合，e(a，b)為CFG中以a為起點，b為終點的一條邊，合併算法如下：
vi.遍歷集合B中的基本塊。如果已遍歷完，則跳轉到步驟v。否則，從集合B中取基本塊b，執行步驟ii
vii.如果基本塊b的子節點集合c(b)的大小為1，執行步驟iii，否則返回i
viii.令a＝c(b)，如果基本塊a的父節點集合p(a)的大小為1，執行步驟iv，否則返回i
ix.將b和a合併為新的基本塊c。同時，移除邊e(b，a)，{e(x，b)|x∈p(b)}和{e(a，x)|x∈c(a)}。並建立新的邊{e(x，c)|x∈p(b)}和{e(c，x)|x∈c(a)}。同時將基本塊c加入集合B中，返回步驟i
x.算法結束。
S302：對指令序列進行寄存器模糊化處理。一般寄存器類型為編譯器經常會優化的選項，因此對其進行模糊化處理，認為(EAX＝EBX＝ECX＝EDX)，對於16位(AX，BX，CX，DX)以及高(AH，BH，CH，DH)、低位(AL，BL，CL，DL)做同樣操作。
S303：對指令序列中的地址信息進行重定向。
具體操作如下：
iii.對於代碼段跳轉指令而言，在提取特徵值時忽略指令後的偏移地址，選擇目的地址塊的哈希值作為特徵。
iv.對於數據段的數據指針，提取該指針所索引的數據值的opcode作為特徵。
作為較佳的實施例，本發明的上述步驟S5的詳細流程為：
S501：函數的SimHash指紋特徵計算：
v.設一個32維的向量V和一個32位的二進位數S，並將它們初始化為0。
vi.設關鍵字集合為K，s(k)＝{hash(k)|k∈K}為關鍵字k的長度為32位的哈希值，v(k)為關鍵字k的權重。
vii.對於每一個關鍵字k∈K，for(i＝0 to 31)：如果s(k)的第i位為1，則V的第i個元素加上v(k)，否則減去v(k)。
viii.對所有的關鍵字按照步驟iii進行操作後，如果V的第i個元素大於0，則將S的第i位置為1，否則為0。最後的輸出S即為函數的指紋特徵。
S502：函數的SimHash指紋特徵存儲：
iv.遍歷二進位文件的函數集合F，對於每一個函數f∈F，計算指紋S(f)。
v.建立一個8位的索引表，索引範圍為：0～255。
vi.對每個指紋S(f)的32位二進位表示，按照31～24，23～16，15～8，7～0分成4段，每段8位，將完整的32位指紋存在這4段所表示的索引項中。
S503：函數的SimHash指紋特徵查詢：
iv.遍歷待匹配文件的函數集合F，對於每一個函數f∈F，計算指紋S(f)。
v.對每個指紋S(f)的32位二進位表示，按照31～24，23～16，15～8，7～0分成4段，每段8位。記為S1，S2，S3，S4。
vi.將S1，S2，S3，S4作為索引項，在已擁有知識庫的二進位文件中進行查詢。
對每一個查詢到的函數表項，計算它其完整SimHash指紋與待匹配函數的完整SimHash指紋的海明距離。如果海明距離小於等於3，則認為是相似函數。
當前主流的二進位文件比較工具均不支持大規模軟體的比較，並且對於一些存在代碼混淆技術的軟體比較準確率較低。主要原因在於：大規模軟體函數眾多且改變複雜，時間效率和匹配準確性難以把握。在本發明所提出的上述方法中，由於重點解決了時間效率這一根本問題，使得對大型軟體的比較成為可能。同時，在對函數提取特徵時，更多關注函數的結構特徵和關聯關係，並採用SimHash算法將函數的不同特徵進行綜合評價，使得對於採用代碼混淆技術等的複雜軟體比較成為可能。
在傳統方法中，不論是基於函數籤名還是基本塊的指令籤名提取都必須兼容編譯器對代碼產生的影響。在利用結構化籤名匹配基本塊時，有時並不能發現由於指令序列顛倒等原因而造成的問題，這些問題將導致判斷失誤。同樣，對於基於結構化比對的函數籤名，如果僅考慮內部基本塊個數，調用指令數，跳轉指令數等函數的結構特徵，而忽略指令內容，可能會將兩個結構相同但語義不同的函數匹配到一起，如：最大值函數與最小值函數。在本發明所提出的上述方法中，首先，對基本塊和基本路徑採用了SPP算法提取其關鍵字，解決了其內部指令重排的問題；同時，在對提取函數的SimHash指紋特徵時，由於SimHash的無序性和關鍵字的結構化特性，進一步解決了由於微小改變和指令重排導致的誤判，提高了函數的匹配準確率。
傳統的二進位文件比較方法，採用了盲目的一一比較的方式來確定匹配對象。假設兩個二進位文件各有2x和2y個函數，則傳統方法的比較次數至少為2x+y次。時間耗費巨大，並且做了很多無用的比較。而採用本發明所提出的上述方法，對於A中的每個函數的特徵指紋(32位)，將其分為4段(每段8位)，利用這4段作為索引，在B的指紋索引表中查找索引項。則對於每個索引，最多會返回2(y-8)個候選結果。時間比較複雜度從2x+y降為4*2x+y-8＝2x+y-6。對於一些大型程序，大大減少了比較耗時，達到了快速查詢的目的。
以上僅是本發明的優選實施方式，本發明的保護範圍並不僅局限於上述實施例，凡屬於本發明思路下的技術方案均屬於本發明的保護範圍。應當指出，對於本技術領域的普通技術人員來說，在不脫離本發明原理前提下的若干改進和潤飾，應視為本發明的保護範圍。