一種面向二進位的混合模糊測試方法

2023-10-10 14:35:34 2

一種面向二進位的混合模糊測試方法
【專利摘要】本發明提供了一種面向二進位的混合模糊測試方法，包括：採用模糊測試作為前端處理，其中利用測試用例來驅動被測試程序的執行；採用二進位代碼覆蓋率監測處理作為中間層處理，其中在被測試程序的執行過程中，記錄被測試程序覆蓋的基本塊，由此計算模糊測試的覆蓋率；當計算出的模糊測試的覆蓋率不再提高時，執行作為後端處理的符號執行處理，在符號執行處理中生成覆蓋與當前測試用例的路徑不同的其它路徑的新的測試用例，然後將新的測試用例反饋至模糊測試，使得模糊測試利用新的測試用例來驅動被測試程序的執行。
【專利說明】一種面向二進位的混合模糊測試方法

【技術領域】
[0001] 本發明涉及計算機【技術領域】，更具體地說，本發明涉及一種面向二進位的混合模 糊測試方法。

【背景技術】
[0002] 隨著計算機科學技術和網際網路技術飛速發展，軟體安全問題層出不窮，軟體安全 一直備受關注。在軟體安全性測試領域，模糊測試和符號執行是兩種使用較為廣泛的測試 方法。
[0003] 模糊測試（Fuzzing)是目前安全性測試領域最常用的技術手段，其基本思想是向 目標程序提供大量的畸形輸入並監控目標系統的異常結果來發現軟體缺陷。模糊測試的基 本流程為：
[0004] 1)確定待測試的目標程序，分析程序輸入數據的基本結構信息，程序輸入包括命 令行參數、文件、網絡數據包、環境變量等；
[0005] 2)依據待測目標程序和輸入數據的基本結構信息的不同，選擇相應的測試用例生 成方案,生成模糊測試數據；
[0006] 3)將測試輸入逐個推送至目標程序，驅動程序執行並監控程序運行狀態；
[0007] 4)將引起程序異常的測試用例和系統狀態進行記錄；
[0008] 5)進一步分析系統異常原因，確定該異常信息是否可被進一步利用（該階段為非 必須階段）。
[0009] 模糊測試技術的優勢在於其不需要任何關於軟體或協議的先驗知識，且測試過程 簡單、高效，自動化程度高。但由於測試用例生成策略的限制，模糊測試存在一定的局限性。 其生成的測試用例具有單一性，多個用例往往覆蓋程序的同一條路徑，無法保證測試的代 碼覆蓋率，致使測試過程不全面。
[0010] 傳統模糊測試技術的不足促進了符號執行技術的發展。
[0011] 符號執行是一種驗證程序正確性的方法，其基本思想是將目標程序的具體輸入用 符號變量表示，根據程序語義，使用符號變量解釋執行程序，在程序的執行過程中使用符號 變量表示程序變量，在程序的分支跳轉處使用符號表達式表示跳轉條件。程序的最終輸出 是由符號變量組成的邏輯或算術表達式，稱為路徑約束條件。對路徑約束條件進行可滿足 性的判斷，通過對約束條件取反，進行符號變量的求解，生成新的測試用例，新生成的測試 用例可以覆蓋程序中新的路徑。
[0012] 符號執行試圖通過分析程序中所有可執行路徑，達到程序狀態空間的完全遍歷。 在理論上，符號執行可以保證較高的測試覆蓋率，但具體使用中存在路徑爆炸，約束求解耗 時耗能等問題。
[0013] 目前，對於原始碼的安全性測試已經有將模糊測試和符號執行相結合的方法。非 專利文獻 I (Internat ional Conference on Software Engineering，29 卷，416-426 頁） 針對C程序提出了一種混合執行的測試方法，模糊測試和符號執行交替執行，同時從廣度 上和深度上探索程序狀態空間。非專利文獻1在原始碼符號執行工具CUTE上實現了該算 法，實驗結果表明在相同的系統開銷下，該方法相比於單獨的模糊測試和符號執行都可達 到較高的測試覆蓋率，能探索更大的程序狀態空間。
[0014] 但是，非專利文獻1中提出的方法只適用於原始碼層面，無法針對二進位程序進 行分析。


【發明內容】

[0015] 本發明所要解決的技術問題是針對現有技術中存在上述缺陷，提供一種能夠針對 二進位程序的混合模糊測試方法，該將模糊測試和符號執行相結合，同時從廣度上和深度 上探索程序狀態空間。通過該方法可以在合理的系統資源開銷下，獲得較高的測試覆蓋率。
[0016] 為了實現上述技術目的，根據本發明，提供了一種面向二進位的混合模糊測試方 法，包括：採用模糊測試作為前端處理，其中利用測試用例來驅動被測試程序的執行；採用 二進位代碼覆蓋率監測處理作為中間層處理，其中在被測試程序的執行過程中，記錄被測 試程序覆蓋的基本塊，由此計算模糊測試的覆蓋率；當計算出的模糊測試的覆蓋率不再提 高時，執行作為後端處理的符號執行處理，在符號執行處理中生成覆蓋與當前測試用例的 路徑不同的其它路徑的新的測試用例，然後將新的測試用例反饋至模糊測試，使得模糊測 試利用新的測試用例來驅動被測試程序的執行。
[0017] 優選地，符號執行處理採用動態符號執行技術。
[0018] 優選地，在符號執行處理中，對被測試程序的輸入進行符號化處理，抓取當前測試 用例的執行軌跡，使用中間語言對軌跡文件進行形式化描述，生成當前路徑的約束條件，採 用基於代的路徑搜索算法對路徑約束條件取反，藉助約束求解器求解路徑約束條件，最終 生成覆蓋與當前測試用例的路徑不同的其它路徑的新的測試用例。
[0019] 優選地，模糊測試在接收到從符號執行處理反饋來的新的測試用例之前，利用基 於變異的策略生成的測試用例來驅動被測試程序的執行。
[0020] 優選地，所述面向二進位的混合模糊測試方法用於軟體安全性測試。
[0021] 本發明的混合模糊測試方法針對的是二進位程序，相比於原始碼測試更具適用性 和實際價值。本發明的混合模糊測試方法在每次切換到符號執行時，只進行一次符號執行 操作，並非重複執行符號執行，增強了符號執行的可用性。將模糊測試和符號執行相結合提 出混合模糊測試方法，該方法引入符號執行指導部分測試用例的生成，構成一個帶反饋式 的模糊測試系統，消除了傳統模糊測試生成測試用例的盲目性，整個系統在合理的資源開 銷下，可以達到更高的測試覆蓋率。

【專利附圖】

【附圖說明】
[0022] 結合附圖，並通過參考下面的詳細描述，將會更容易地對本發明有更完整的理解 並且更容易地理解其伴隨的優點和特徵，其中：
[0023] 圖1示意性地示出了根據本發明優選實施例的面向二進位的混合模糊測試方法 的系統架構簡圖。
[0024] 圖2示意性地示出了根據本發明優選實施例的面向二進位的混合模糊測試方法 的系統架構詳圖。
[0025] 圖3示意性地示出了根據本發明優選實施例的混合模糊測試系統的偽代碼實現 的示例。
[0026] 圖4示意性地示出了本發明具體實施例採用的基於代的路徑遍歷算法。
[0027] 圖5示意性地示出了根據本發明優選實施例的針對Linux系統下的常用二進位程 序Is的中間語言片段的具體示例。
[0028] 需要說明的是，附圖用於說明本發明，而非限制本發明。注意，表示結構的附圖可 能並非按比例繪製。並且，附圖中，相同或者類似的元件標有相同或者類似的標號。

【具體實施方式】
[0029] 為了使本發明的內容更加清楚和易懂，下面結合具體實施例和附圖對本發明的內 容進行詳細描述。
[0030] 對二進位代碼分析，相比原始碼分析具有以下優勢：首先，對二進位可執行程序分 析不依賴於原始碼，可以很好地保護商業機密。其次，在原始碼編譯成最終的二進位程序的 過程中，可能會有編譯器優化或代碼混淆器引入的隱蔽軟體缺陷。因此，原始碼正確，二進 製程序不一定正確，只有對最終的二進位程序進行測試分析，才可能發現此類問題。最後， 現有的不同軟體是由不同的程式語言（(：工++、從￥八、腳本語言等）編寫而來，目前還不存在 跨程式語言的原始碼安全性分析系統，對原始碼進行分析，需要對不同的程式語言的語法 和語義信息建立不同的模型後進行分析。但它們最終的二進位代碼都是統一形式的機器指 令，因此，對二進位程序分析不受程式語言差異的影響。
[0031] 本發明提出的混合模糊測試方法的系統架構簡圖如圖1所示，系統架構詳圖如圖 2所示。
[0032] 如圖1和圖2所示，根據本發明優選實施例的面向二進位的混合模糊測試方法包 括：
[0033] 採用模糊測試100作為前端處理，其中利用測試用例來驅動被測試程序的執行 (模糊測試1〇〇初始地可以利用基於變異的策略生成的測試用例來驅動被測試程序的執 行，即，模糊測試1〇〇在接收到從符號執行處理300反饋來的新的測試用例400之前，利用 基於變異的策略生成的測試用例來驅動被測試程序的執行）；
[0034] 採用二進位代碼覆蓋率監測處理200作為中間層處理，其中在被測試程序的執行 過程中，記錄被測試程序覆蓋的基本塊，由此計算模糊測試100的覆蓋率；
[0035] 當計算出的模糊測試100的覆蓋率不再提高時，執行作為後端處理的符號執行處 理300,其中符號執行處理300生成覆蓋與當前測試用例的路徑不同的其它路徑的新的測 試用例400,然後將新的測試用例400反饋至模糊測試100,使得模糊測試100利用新的測 試用例400來驅動被測試程序的執行。
[0036] 具體地說，例如如圖2所示，符號執行處理300可採用動態符號執行技術，首先對 被測試程序的輸入進行符號化處理，抓取當前測試用例的執行軌跡，使用中間語言對軌跡 文件進行形式化描述，生成當前路徑的約束條件，採用基於代的路徑搜索算法對路徑約束 條件取反，藉助約束求解器求解路徑約束條件，最終生成覆蓋與當前測試用例的路徑不同 的其它路徑的新的測試用例400 ;然後將新的測試用例400反饋至模糊測試100,使得模糊 測試100利用新的測試用例400來驅動被測試程序的執行。
[0037] 而且，在具體實施時，可以重複執行上述方法的過程。
[0038] 上述面向二進位的混合模糊測試方法用於軟體安全性測試。
[0039] 為了更詳細地描述本發明的具體實施細節，下面將詳細描述本發明的具體實施方 式及具體實例。
[0040] 混合模糊測試系統的偽代碼實現的實例如圖3所示。算法的基本流程為：算法輸 入為可執行程序和本次測試的目標（例如測試用例數量，覆蓋率），3-15行是循環的主體： 循環過程首先將覆蓋率提高標誌（ C〇Verage_flag)設為真（3行）；在執行模糊測試的同 時監測代碼覆蓋率情況，直到程序覆蓋的基本塊數量不再增加時，將c 〇Verage_flag設為 假（4-10行）；此時結束內層循環，轉為符號執行，產生新的輸入，繼續執行循環體（13-15 行）。
[0041] 傳統的模糊測試作為整個混合模糊測試系統的前端，採用基於變異或者基於生成 的測試用例生成方法，持續不斷地產生測試用例，將生成的測試用例注入到目標程序中，驅 動程序執行。在目標程序的執行過程中，通過二進位代碼覆蓋率監測實時計算測試覆蓋率。 [0042] 混合模糊測試系統在代碼覆蓋率不再提高時轉入後端符號執行，代碼覆蓋率不再 提高意即所覆蓋的基本塊的數量不再增加。符號執行模塊作為混合模糊測試系統的後端， 主要任務是在程序執行過程中收集路徑約束條件，通過一定的路徑搜索策略生成新的路徑 約束條件，最後使用特定的約束求解器求解生成覆蓋其他路徑的測試用例，以此提高模糊 測試的測試覆蓋率。在符號執行過程中，對二進位程序的分析，實質上是對內存單元和寄 存器分析。彙編指令雖然能表示出機器語言的所有操作，但並未將這些操作所產生的影響 (s ide effect)體現出來，也就無法將標誌寄存器EFlags的狀態體現出來。程序執行到 分支跳轉指令時，會根據EFlags中的某些標誌位決定是否跳轉，EFlags是一個32位寄存 器，由狀態標誌位，控制標誌位和系統標誌位組成。符號執行系統收集路徑約束條件時，主 要依據軌跡中的條件轉移指令（jcc)，條件轉移指令依據EFlags的值決定執行不同的分 支。而EFlags中的值又依賴於前面能影響EFlags寄存器的機器指令，因此在將該機器指 令轉換成彙編指令的同時將其對EFlags寄存器的影響表示出來，就可以確定條件轉移指 令處該選擇的路徑。需採用某種中間語言（Intermediate Language)來表示指令及指令對 於EFlags寄存器的影響。
[0043] 符號執行得到的路徑約束條件是由符號變量表示的表達式組成的函數，為構造新 的路徑約束條件，需採用一定的路徑搜索策略。本發明的具體實施例可以採用一種基於代 的路徑遍歷算法（Generat ion Search, GS)，如圖4所示。GS算法的基本思想是：對於當 前輸入所產生的路徑約束條件，依次對約束條件進行取反操作，生成下一代路徑約束條件 集，重複該過程，即可遍歷程序中所有可執行路徑。相比於深度遍歷和廣度遍歷每次產生一 個新的路徑，GS算法每次可產生多個新的路徑約束，從而求解產生多個新的輸入。符號執 行模塊作為模糊測試系統的後端，是當模糊測試在執行過程中監測到代碼覆蓋率不再提高 時，轉為符號執行，由符號執行產生通往其他路徑的新輸入，並不是循環執行符號執行以搜 索程序中所有的路徑，因此本文在符號執行過程中只產生第一代的新的約束條件，通過約 束求解器求解產生新的輸入。
[0044] 【具體實例】
[0045] 對Linux系統下的常用二進位程序Is(以列表形式顯示目錄內容）進行安全性分 析。目標程序Is的外部輸入由一系列選項參數及目標路徑組成，採用基於變異的測試用例 生成策略隨機產生測試用例。使用生成的測試用例驅動目標程序Is運行。
[0046] Is程序開始運行，同時啟動二進位代碼覆蓋率監測模塊。每個測試用例執行完畢 後，分析該用例覆蓋的基本塊，將該測試用例加入到以往所有執行過的測試用例中，構成一 個新的測試用例集，然後計算整個測試用例集的代碼覆蓋率（也可以計算用例集覆蓋的不 同的基本塊數量）。
[0047] 當二進位代碼覆蓋率監測模塊監測到新執行的測試用例無法提高整個測試用例 集的覆蓋率時，暫停模糊測試的執行過程，轉入後端的符號執行。符號執行模塊將最後一次 執行的測試用例作為具體輸入，抓取Is程序執行該測試用例的執行軌跡。將軌跡文件通 過逆向工程提升為某種中間語言，收集本次執行過程的路徑約束條件。約束條件關注條件 跳轉類指令，以Is軌跡文件的中間語言片段圖5為例，對於比較指令"cmp$Oxffffffff，％ ecx"，其含義是比較寄存器ecx的值與立即數Oxffffffff的大小，BIL顯式表達並計算出 該比較指令所影響到的EFlags寄存器中各個標誌位的變化，其中零標誌位ZF由於兩操作 數相減結果不為零置為"false"。下一條指令"je 0x000000009d4e403e"為條件轉移類指 令，當EFf lags寄存器的ZF標誌位為1時跳轉到0x000000009d4e403e地址處繼續執行，否 則順序執行接下來的指令。在這裡，由於ZF = 0,程序沒有發生跳轉。此時收集到的路徑 約束條件為"…八（ECX〈-1)八…"，省略號表示其他約束條件，各個約束條件使用"且"連 接。
[0048] 為構造新的路徑約束條件，從而探索到其他新的路徑，採用GS算法較為關鍵的一 步是對約束取反。對於圖4的約束條件進行取反的結果為："…八=(ECX〈-1)"，（ECX〈-1) 之後的約束條件捨棄，之前的約束條件保留。由於新的約束條件是對原約束條件取反，使得 程序在"je 0X000000009d4e403e"指令處發生跳轉，從而探索到程序中新的路徑。若本條 路徑上有n個約束條件，經過一次符號執行後採用GS算法得到第一代的結果，就可以構造 n個新的路徑約束條件，藉助約束求解器進行可滿足性判斷及約束求解，可以生成覆蓋特定 路徑的具體的測試用例。
[0049] 將經過符號執行生成的測試用例注入到Is程序中，同樣地進行代碼覆蓋率的監 測和計算。最後，繼續執行模糊測試。重複該過程。直到達到Is程序的測試需求（如要求 達到的覆蓋率、執行的測試用例數）時，終止混合模糊測試的執行。
[0050] 可以理解的是，雖然本發明已以較佳實施例披露如上，然而上述實施例並非用以 限定本發明。對於任何熟悉本領域的技術人員而言，在不脫離本發明技術方案範圍情況下， 都可利用上述揭示的技術內容對本發明技術方案作出許多可能的變動和修飾，或修改為等 同變化的等效實施例。因此，凡是未脫離本發明技術方案的內容，依據本發明的技術實質對 以上實施例所做的任何簡單修改、等同變化及修飾，均仍屬於本發明技術方案保護的範圍 內。
【權利要求】
1. 一種面向二進位的混合模糊測試方法，其特徵在於包括： 採用模糊測試作為前端處理，其中利用測試用例來驅動被測試程序的執行； 採用二進位代碼覆蓋率監測處理作為中間層處理，其中在被測試程序的執行過程中， 記錄被測試程序覆蓋的基本塊，由此計算模糊測試的覆蓋率； 當計算出的模糊測試的覆蓋率不再提高時，執行作為後端處理的符號執行處理，在符 號執行處理中生成覆蓋與當前測試用例的路徑不同的其它路徑的新的測試用例，然後將新 的測試用例反饋至模糊測試，使得模糊測試利用新的測試用例來驅動被測試程序的執行。
2. 根據權利要求1所述的面向二進位的混合模糊測試方法，其特徵在於，符號執行處 理採用動態符號執行技術。
3. 根據權利要求1或2所述的面向二進位的混合模糊測試方法，其特徵在於，在符號執 行處理中，對被測試程序的輸入進行符號化處理，抓取當前測試用例的執行軌跡，使用中間 語言對軌跡文件進行形式化描述，生成當前路徑的約束條件，採用基於代的路徑搜索算法 對路徑約束條件取反，藉助約束求解器求解路徑約束條件，最終生成覆蓋與當前測試用例 的路徑不同的其它路徑的新的測試用例。
4. 根據權利要求1或2所述的面向二進位的混合模糊測試方法，其特徵在於，模糊測試 在接收到從符號執行處理反饋來的新的測試用例之前，利用基於變異的策略生成的測試用 例來驅動被測試程序的執行。
5. 根據權利要求1或2所述的面向二進位的混合模糊測試方法，其特徵在於，所述面向 二進位的混合模糊測試方法用於軟體安全性測試。
【文檔編號】G06F11/36GK104375942SQ201410758900
【公開日】2015年2月25日 申請日期:2014年12月11日 優先權日:2014年12月11日
【發明者】董芳泉, 董超群, 張慧, 張垚, 楊書軒, 程來旺 申請人:無錫江南計算技術研究所