基于級聯森林的控制流錯誤檢測優化算法

董志騰，顧晶晶

(南京航空航天大學 計算機科學與技術學院， 南京 211106)

1 引 言

隨著科技的進步，計算機芯片中的晶體管尺寸越來越小，這使得芯片更容易受到外界環境的影響.尤其是在航空航天和醫療領域等高輻射場景下，計算機很有可能會發生瞬時故障[1]，這些瞬時故障往往會造成災難性的后果.預計在未來瞬時故障發生的概率將會呈指數增長[2].1990年發射的“風云一號”氣象衛星，由于發生瞬時故障提前退役；1998年有報道顯示在心臟除顫器中發生了瞬時故障；2011年，我國一顆探測衛星“螢火一號”發生瞬時故障，導致探測任務失敗.

瞬時故障引起的錯誤如果打亂了程序正常的執行順序導致程序出錯，我們將這種錯誤稱為控制流錯誤.研究表明，瞬時故障引起的錯誤中有約33%～77%的錯誤是控制流錯誤[3,4].控制流錯誤主要是由于瞬時故障發生在程序計數器(PC)，地址存儲單元或者條件判斷語句中的變量存儲單元.控制流錯誤會造成計算機程序不按照正確的指令順序執行，可能會干擾程序的運行結果、造成程序陷入死循環甚至崩潰[5].

針對瞬時故障，現有的故障檢測方法可以分為硬件方法和軟件方法.硬件方法主要依靠硬件模塊的冗余或者設置錯誤檢測電路來實現，需要針對不同的硬件體系專門定制，成本極高且不靈活[6-9].相比于硬件方法，軟件方法不需要依賴于硬件體系，成本低、靈活度高且容易配置.

本文提出了一種針對基于標簽分析的錯誤檢測方法的通用優化算法.為了尋找出合適的標簽插樁位置和數量，本文設計了一種基于級聯森林的基本塊脆弱性預測模型，該模型經過大量的故障注入實驗樣本訓練，可以識別出脆弱性高的基本塊.我們針對性的將這些高脆弱性的基本塊進行重新拆分，使其能夠更好的配合基于標簽的檢測算法.我們對MiBench測試集[16]中6個測試程序進行故障注入實驗，結果表明，在對程序基本塊進行選擇并拆分后，CFCSS算法[10]和RCFC算法[11]的檢測率均有提升，且相對于隨機插樁標簽的開銷較低，實現了高效費比的基本塊拆分.本文的主要貢獻如下：

1)本文通過收集分析大量程序數據，使用多粒度級聯森林模型[12]，對程序中易發生控制流錯誤的基本塊進行識別，取得了不錯的識別率.

2)本文使用LLVM編譯器[13-15]，對程序中的基本塊進行重新拆分，并編寫LLVM Pass文件實現CFCSS單標簽檢測算法和RCFC雙標簽檢測算法，在拆分好的程序上自動添加標簽.

3)本文在選用MiBench測試集[16]中的6個測試程序進行驗證，證明我們的方法使用較低的額外開銷可以提升較高的檢測率.

2 背景和相關工作

對于控制流錯誤的檢測，相比于基于硬件的檢測方法[17]，目前的軟件檢測方法通常是基于標簽的檢測方法[18]，主要流程是將程序劃分成基本塊，為每個基本塊分配若干個標簽，并在程序運行期間維護一個隨當前基本塊變化而變化的全局變量來進行錯誤檢測.

目前實用性最強的基于標簽的檢測方法是CFCSS[10](Control Flow Checking by Software Signatures)，CFCSS將程序劃分成若干個指令序列，并正式提出基本塊的概念.CFCSS在編譯階段為每個基本塊分配靜態標簽，通過比較靜態標簽和運行時的全局變量來判斷程序是否發生了控制流錯誤.

RCFC也是一種基于標簽的控制流錯誤檢測算法，它提出了一種雙標簽的檢測方法，利用應用程序中的循環嵌套結構將程序基本塊分割成有條件的和無條件的基本塊，有選擇性的對其進行標簽跟蹤[11].該方法雖然泛化性不高，但是提出的雙標簽算法為后續的研究工作提供了一些思路.雙標簽檢測方法一般會維護兩個全局變量跟蹤程序運行時的前驅和后繼節點，并通過設計比較規則來判斷程序是否發生了控制流錯誤.

目前主流的控制流錯誤檢測方法，大多與CFCSS或RCFC很相似，只是在標簽設置的數量、標簽插樁的位置以及標簽更新方式上的不同.近些年軟件實現的控制流錯誤檢測技術已有了長足的發展.一度陷入了為了提高檢測率而不斷增加開銷的陷阱中.往往犧牲了大量的空間性能，只能提高少量的錯誤檢測率.如何提升標簽檢測技術的檢測率，同時又能控制額外的性能開銷，成為基于軟件的控制流錯誤檢測及加固領域的研究關鍵.調整標簽插樁的位置和數量可以一定程度上提高錯誤檢測率，但是無限提高標簽的數量很明顯不是一種好的方法，如何尋找合適的位置添加合適數量的標簽是一個亟待解決的問題.

本文著眼于使用軟件方法檢測控制流錯誤的問題.針對傳統的基于標簽的檢測算法在標簽插樁粒度和錯誤檢測率之間難以平衡的難點以及塊內錯誤難以檢測的難點，設計了一套的針對基于標簽檢測方法的通用優化算法.

3 控制流錯誤檢測優化方案

本文設計了一種對傳統控制流錯誤檢測技術的優化方案.如圖1所示.主要包括3個部分：1)數據采集模塊.為了保證程序的普適性，首先從GitHub上收集大量的使用C語言程序編寫的常規算法和數據結構；使用LLVM工具對程序進行預處理和靜態特征提取[19]；對GDB程序調試工具進行二次開發，通過修改程序運行時的PC寄存器的值完成控制流故障注入，記錄程序故障結果同時提取程序運行時的動態特征.計算每個基本塊的脆弱性值[20]，并構建訓練集.2)模型訓練模塊.使用多粒度級聯森林對程序基本塊的脆弱性進行預測.3)基于標簽的檢測算法的優化.針對預測出的脆弱性高的基本塊進行重新拆分，驗證程序在拆分前后在相同的標簽檢測算法下控制流錯誤檢測率和時空開銷的效費比提高.

圖1 控制流錯誤檢測方案流程圖

3.1 相關定義

定義1.指令(Instruction，I)是計算機處理的命令.每個程序都需要編譯程指令的形式由計算機執行.

定義2.基本塊(Basicblock，bb)是一個最大的連續指令集合，記為bb={Iin，…，Ii，…，iout}.在每個基本塊中，指令由第一條順序執行至最后一條，即每個基本塊只有唯一的入口指令Iin和唯一的出口指令Iout.基本塊中除了最后一條指令外，不可能包含額外的分支、跳轉.同時，每個基本塊也不可能分支、跳轉或者調用其他基本塊中除第一條指令以外的指令.

定義3.控制流(Control flow，CF)是基本塊的跳轉順序，這種跳轉順序在程序編譯完成就確定了，一般不會改變.定義為E={eij|0≤i，j≤n}，其中n表示一個程序中的基本塊總數量，eij表示bbi跳轉到bbj的分支.

定義4.非法控制流(Illegal Control flow)描述一系列非正常的程序跳轉.正常的程序跳轉只有兩種情況：1)基本塊內部的前一條指令順序執行至下一條指令；2)基本塊最后一條指令跳轉至合法的后繼基本塊的第一條指令.除了這兩種情況外的其他所有跳轉均為非法控制流.程序運行中一旦有非法控制流的存在，即該程序發生了控制流錯誤.

定義5.基本塊脆弱性描述該基本塊在程序運行時發生控制流錯誤的難易程度.脆弱性越高代表該基本塊越容易發生控制流錯誤.

3.2 數據采集模塊

3.2.1 原始數據集

程序的控制流在程序編寫完成時就已經確定，每個程序只會根據程序的不同輸入改變控制流的不同路徑，每條路徑上的指令執行序列是不會發生改變的.所以程序的控制流信息與程序員的代碼風格有關，對于相同功能的程序，不同程序員可能會編寫出截然不同的代碼.為了得到程序控制流錯誤發生的一般規律，需要收集大量的程序控制流錯誤信息.訓練數據集中的程序代碼來自于GitHub，包括排序算法、數據結構、字符串操作、基礎數學運算、最短路徑算法等每種程序選擇1至3個符合條件的共61個程序，如表1所示.為了方便進一步操作，這61個程序符合以下要求：1)程序輸入為空或文件；2)程序輸出為文本；3)程序運行時間小于10秒.

表1 原始數據集程序名稱

3.2.2 基本塊編號插樁

本文討論的控制流錯誤主要依賴于程序的基本塊信息.每個基本塊是一個連續的指令集合，記為bb={Iin，…，Ii，…，Iout}，如定義2所描述.為了準確獲取程序運行時基本塊bb與指令集合的對應關系，需要對基本塊進行標號，記作bbi.構建bbi到指令集合的一對多的映射關系.

在程序運行時分析程序當前運行的指令所在基本塊的編號是很困難的，而這恰恰是分析程序控制流錯誤發生位置的關鍵點.本文提出基本塊編號插樁的方法，對程序的每個基本塊分配唯一的編號，并使用一個全局變量記錄當前程序正在運行的位置.具體的步驟為：

步驟1.使用LLVM工具將程序轉換成LLVM IR中間代碼；

步驟2.使用LLVM Pass對程序進行分析，遍歷所有基本塊，依次為其編號；

步驟3.使用LLVM Pass在程序開頭聲明全局變量記作GSIG(Global Signature)，并在每個基本塊開頭的第一個不為空指令(LLVM規則中phi指令為空指令)之前插樁GSIG賦值語句，將當前的基本塊號賦值給GSIG；

步驟4.使用LLVM將中間代碼編譯成可執行程序.

經過基本塊號標簽插樁的程序在運行的任何時間點的變量GSIG記錄的值都是程序基本塊的標號.

3.2.3 故障注入

為了分析程序中每個基本塊的脆弱性，需要收集每個基本塊發生控制流錯誤后的數據.收集這類數據一般有兩類方案：1)大量的故障注入實驗，使得控制流錯誤覆蓋到每個基本塊；2)針對每個基本塊做相同數量的故障注入實驗.程序在運行過程中，每個基本塊的執行次數、執行時間有很大的差異，所以，方案1會造成樣本的數量很不均衡，在極端情況下會造成部分基本塊因為故障注入次數過少使得樣本無效.很顯然方案2是一種比較合適的方法.

控制流錯誤故障注入一般分為靜態注入和動態注入兩種方式.靜態注入包含隨機刪除跳轉指令、隨機修改(翻轉)跳轉指令的目的地址、隨機添加跳轉指令3種，這些都可以在程序執行前完成故障注入，故稱為靜態故障注入；動態注入主要是在程序運行中，隨機修改當前的PC寄存器的值，使得程序在運行期間發生跳轉，故稱為動態注入.動態故障注入可以模擬出靜態故障注入的全部效果，且更具有靈活性，所以本文采用動態故障注入方式.

使用GDB工具模擬動態故障注入，GDB是一Linux環境下最常用的程序調試工具之一，可以在程序運行時獲取寄存器中的值，打斷點，設置檢查點等分析程序運行時的各類信息.并創新地完成了針對基本塊的控制流錯誤故障注入方案.控制流錯誤故障注入的基本原理是在程序運行時隨機暫停程序運行，改變當前程序的PC寄存器的值，使程序執行的下一條指令不再屬于正常的指令序列.針對基本塊的故障注入則是在隨機翻轉任意一條指令的PC寄存器的值的基礎上做到針對指定基本塊內的指令的PC寄存器的值的隨機翻轉.這就要求隨機暫停程序運行的位置在指定的基本塊內，首先在程序編譯前，在每個基本塊頭插入全局變量GSIG，記錄當前基本塊的編號.之后利用GDB的檢查點機制，獲取基本塊號以及其所包含的指令集合中每條指令對應的PC寄存器值的一對多映射關系.具體流程如下：

步驟1.啟動GDB工具；

步驟2.針對全局變量GSIG設置檢測點；

步驟4.逐條執行指令，保存PC寄存器的值，添加到“基本塊號-指令PC寄存器值”映射表中；

步驟5.當GSIG的值發生變化時，重復執行步驟2、步驟3；

步驟6.程序運行結束.

在故障注入時，針對每個不同的基本塊，我們只需要隨機選取對應映射關系中的PC值，并在該處打斷點，當程序運行到該位置時，隨機翻轉PC寄存器的值，即可完成針對基本塊的控制流錯誤故障注入.在已知程序所有指令所對應的PC寄存器值的情況下，還可以做到指定跳轉目的地址，做到控制基本塊內、塊間以及過程間的控制流跳轉.

程序在運行時按照一定的故障發生率[21]進行故障注入，需要收集一些動態特征，首先基本塊脆弱性定義為該基本塊中發生控制流錯誤后，程序發生錯誤的概率與該基本塊的占程序總運行時間占比的乘積，具體定義如下：

基本塊集合：B={bb1，…，bbi，…，bbN}，基本塊動態特征集合為：Bdynamic={round1，…，roundi，…，roundN}，其中roundi為基本塊bbi的執行次數，比如循環體基本塊在程序執行過程中會多次執行，假設計算機執行每條指令的時間大致相同，那么每個基本塊占程序執行總時間的比重為：

(1)

針對程序的每個基本塊故障注入M次，程序發生錯誤的次數統計為：C={C1，…，Ci，…，CN}，基本塊的脆弱性定義為：

(2)

3.2.4 靜態特征

提升企業形象。四川雅安地震發生后，所屬自貢公司繼2008年參與汶川抗震救災后，再次代表中國水務公司，在第一時間組織供水搶修救援隊伍奔赴抗震救災第一線。搶修隊的工作得到災區政府和群眾一致好評，中央各大媒體對其表現出高度的關注，新聞聯播和新聞30分等欄目給予全方位報道。搶修隊樹立了中國水務員工英勇、專業、能打硬仗的良好形象，踐行了中國水務勇于承擔社會責任的莊嚴承諾。

靜態特征是指程序代碼在編寫完成后就具備的特征.這些特征與程序執行過程中的輸入無關，僅僅與代碼相關.

LLVM工具可以將程序轉換成LLVM IR中間代碼形式.對中間代碼進行分析，LLVM可以快捷地將程序分解成基本塊，我們可以得到程序的每個基本塊的信息，對于每個基本塊，我們提取它的塊號、指令數、不同類別指令數、出度、入度、平均每條指令操作數個數等作為基本塊的靜態特征.

3.3 模型訓練模塊

數據采集階段收集的基本塊特征集合，經數據預處理之后，篩除一些無效樣本.使用跨樣本的滑動窗口技術對數據集進行處理，獲得了基本塊執行序列的相關特性集合Fexpand，與特征集合Fi合并為初始的輸入特征Forigin=.Forigin將作為級聯森林的初始輸入數據進行模型訓練.模型訓練模塊將在第4章給出詳細過程.

3.4 基于標簽檢測算法的優化策略

使用Clang編譯器[22]將待檢測程序編譯成LLVM IR中間代碼，目標程序待預測的基本塊集合為Bpredict={bb1，…，bbi，…，bbN}.其中bbi表示程序中的第i個基本塊，N為程序中的基本塊數量.通過LLVM Pass對Bpredict集合中的所有基本塊進行分析得到基本塊的靜態特征，并使用GDB工具獲取基本塊的動態特征，合并得到基本塊特征Fi.基于已經訓練好的基本塊脆弱性預測模型對目標程序的基本塊脆弱性進行預測，并輸出基本塊標號和脆弱性關系到統計文件中.

將預測結果中脆弱性大于閾值的基本塊進行拆分，得到的新程序使用基于標簽的控制流錯誤檢測算法進行驗證.對比算法在程序拆分前后的檢測率以及時空開銷的變化情況.對比預測模型在多種待測程序和多種標簽檢測算法上的運行結果，驗證本文的基于標簽的檢測算法優化策略可行.

4 基于多粒度級聯森林的基本塊脆弱性預測算法描述

4.1 數據分析

通過對進行針對性的故障注入實驗后得到基本塊脆弱性預測算法的數據集.該數據集包括61個程序中的2505個基本塊特征以及每個基本塊100次故障注入實驗得到的實驗結果數據.程序基本塊特征包括指令數量、指令類別、出度、入度、平均每條指令操作數個數、基本塊運行次數等共16個特征.提取的特征如表2所示，并遵循如下依據：

表2 基本塊特征描述表

基本塊的指令數量是描述程序基本塊大小的特征.計算機執行每條指令的時間大致相同，所以指令數量越多的基本塊執行的時間越長，那么在程序運行期間更有可能受到控制流錯誤的影響.因此本章將指令數量作為特征提取并表示為Vins_num.

不同類別指令數量是描述程序基本塊中不同指令數量的特征[23].不同類型的指令代表了程序的不同功能，比如讀取存儲指令、運算指令數量越多，程序更有可能只是進行單一順序的執行，這時若發生控制流錯誤很有可能會造成程序運行結果錯誤；若跳轉指令、函數調用指令數量越多，程序更有可能在發生跳轉或者在執行循環操作，這時若發生控制流錯誤，很有可能會造成程序進入死循環或者掛起.基本塊中包含的不同類別的指令數量基本可以表示當前基本塊的作用，因此本章將不同類別指令數量作為特征提取并表示為：Vins_type.

程序基本塊的出度入度是描述程序基本塊執行順序的特征.程序從入度為零的基本塊按照順序執行直到最后一個出度為零的基本塊.基本塊的入度出度也描述了該基本塊的執行重要程度.比如經常被調用的函數包含的基本塊的入度會比較大，包含if、switch等條件跳轉語句所在的基本塊出度會比較大.這類基本塊在發生控制流錯誤時很有可能會造成程序跳轉關系的混亂，造成不可預知的錯誤.因此，本章將程序基本塊的出度入度作為特征提取并表示為：Vin_and_out.

程序中每條指令都有不同數量的操作數，由于操作數的讀寫需要消耗計算機資源，所以操作數的多少一定程度上影響了指令的執行時間.基本塊包含若干指令，所以將每條指令的平均操作數數量作為基本塊的特征進行提取并表示為：Vins_avg.

程序中不同基本塊由于功能不同，在程序運行過程中，基本塊的執行次數相差很大.一些與參數初始化有關的基本塊在程序執行過程中只會執行一次，而有些與循環相關的基本塊可能會執行成千上萬次.基本塊的執行次數與該基本塊的執行時間直接相關.同時程序在不同測試用例下，相同的基本塊執行次數也會有差異，使用單一測試用例進行測試得到的基本塊執行次數并不完全準確.LLVM提供了一種啟發式算法，可以對程序基本塊的執行次數進行預測，預測出的基本塊執行次數可以對單一測試用例下基本塊執行次數的測量值進行補充，盡可能接近真實的基本塊執行次數.因此，本章將程序基本塊執行次數作為特征提取并表示為：Vround.

綜上所述，基本塊特征向量可以表示為：

Vorigin={Vins_num，Vins_type，Vin_and_out，Vins_avg，Vround}

在LLVM IR中間代碼表示中，具體的指令類別如表3所示.

表3 指令類別表

基本塊特征集合可以定義為：

F=Vorigin

={Vins_num，Vins_type，Vin_and_out，Vins_avg，Vround}

={ins_num，ins_type1，ins_type2，…，ins_type9，

in，out，op_avg，real_rounds，predict_rounds}

其中ins_num表示基本塊中的包含的指令數量，ins_type1，ins_type2，…，ins_type9分別表示第1類到第9類的指令數量，in，out表示基本塊的入度和出度，opavg表示平均每條指令的操作數數量，realrounds表示程序在單一測試用例下完整運行一次基本塊執行的次數，predictrounds表示LLVM啟發式算法計算的基本塊執行次數.故障注入工具對程序集中所有的基本塊逐個進行故障注入，根據程序運行結果統計每個基本塊的脆弱性Pi，并結合基本塊的靜態特征與動態特征構建基本塊脆弱性預測模型的特征集合E={(Fi，Pi)}.

4.2 算法描述

gcForest是一種決策樹集成方法，在多分類任務中具有與深度神經網絡相近的性能.本章介紹級聯森林在程序基本塊脆弱性預測的構造過程.主要分為兩部分：多粒度掃描和級聯森林結構.多粒度掃描可以挖掘樣本間的特征相關性，構造更適用于級聯森林模型的數據集；級聯森林可以利用不同森林的特性，提高預測的準確性.

4.2.1 多粒度掃描

為了增強級聯森林結構的訓練效果，我們采用多粒度掃描對特征進行處理.多粒度掃描的基本思想來源于深度神經網絡，類似于深度神經網絡中的卷積核滑動過程.但一般情況下單一粒度的滑動窗口掃描只能獲取固定序列中的有效特征，而多粒度掃描可以利用樣本間的相關性特征.本文的多粒度掃描模型如圖2所示.

如圖2所示，本文中的樣本特征有16個維度，每個程序大約包含數10個基本塊，每個基本塊特征為一條樣本.為了獲取基本塊的序列特征，我們每次選取10條連續的基本塊特征樣本拼接成160維的新特征向量.分別設置窗口(Window)大小為32，64和80.以窗口大小32為例，為了獲取每條樣本之間的相關性特征，每次向前滑動16個單位，共滑動9次生成9個新樣本，樣本數量記作s.同理，窗口大小為64和80時，可以生成7個和6個新樣本.每個子樣本都用于完全隨機森林和普通隨機森林的訓練，每個森林都會得到一個長度為5(分類個數)的概率向量，即每個森林都會生成一個5×s的表征向量，最后把每層的隨機森林結果拼接得到樣本輸出.

圖2 多粒度掃描模型

4.2.2 級聯森林

本文中使用級聯森林對程序基本塊脆弱性進行預測.級聯森林由多層隨機森林結構集合而成，每一層由不同的隨機森林組成，本文采用普通隨機森林和完全隨機森林，每一層的訓練結果作為下一層的特征信息，從而增強下一層深林的訓練結果，如圖3所示.

圖3 級聯森林模型

4.2.3 基本塊拆分策略

為了提升控制流錯誤的檢測粒度，本文對脆弱性高的基本塊進行拆分，以檢測更多發生于該基本塊的塊間和塊內錯誤.具體策略為：

步驟1.選擇待拆分基本塊

使用多粒度級聯森林模型對基本塊脆弱性進行預測，將基本塊集合B={bb1，…，bbi，…，bbN}按照脆弱性重新排序，選擇脆弱性高的且基本塊大小大于閾值(一般選擇平均基本塊大小作為閾值)的前k個基本塊作為拆分對象.

步驟2.拆分基本塊

在選取的k個基本塊中選擇合適的指令位置，使用LLVM Pass將選中的基本塊從該指令后一分為二.為了防止基本塊拆分過程使程序的代碼規則被破壞，在基本塊拆分時，不選擇phi指令前進行拆分，在LLVM IR中間代碼規則中，phi指令記錄了當前基本塊的前驅，故phi指令之前不允許有其他指令出現.

步驟3.插樁錯誤檢測標簽

程序經過基本塊拆分后，選擇不同的基于標簽的檢測算法(本文選擇CFCSS和RCFC算法)進行檢測標簽插樁，并確?；緣K拆分并插樁檢測標簽后可以正常運行.

5 控制流錯誤檢測驗證實驗

本節設計了針對本文提出方法的驗證實驗.實驗環境為：i7-8750H CPU、運行內存16G、Ubuntu Linux操作系統.本文隨機選取了MiBench測試套件中的6個程序作為測試集，包括Qsort(快速排序)、Dijkstra(迪杰斯特拉最短路徑算法)、FFT(快速傅里葉變換)、Isqrt(整數平方根計算)、Bit string(位類型數據轉換為字符轉類型數據)和Rad2deg(弧度轉換為角度).實驗過程主要包括4個內容：程序特征提取、基本塊脆弱性預測、脆弱基本塊拆分和標簽檢測算法檢測率開銷對比.

1)首先將所選程序使用LLVM編譯程中間代碼形式(LLVM IR)，使用LLVM Pass提取基本塊靜態特征并在每個基本塊首插樁塊號標簽，再使用GDB調試工具運行程序獲取程序的動態特征.

2)結合靜態動態特征，使用訓練好的級聯森林對基本塊的脆弱性進行預測.

3)選取一定比例脆弱性高的基本塊進行重新拆分.

4)針對拆分前后的測試程序，使用CFCSS和RCFC兩種標簽檢測算法進行控制流錯誤檢測.對比其開銷和檢測率.

本章對故障注入實驗做了以下假設[25]：1)僅考慮因PC寄存器發生故障導致的控制流錯誤；2)程序每次執行過程中有且只有一次故障.

從兩個方面評估本文提出的方法：1)基本塊脆弱性預測的準確性；2)針對高脆弱性基本塊拆分的策略對傳統基于標簽的控制流錯誤檢測方法在檢測率上的提升.

5.1 基本塊脆弱性預測實驗

預測基本塊的脆弱性是本文提出的方法的關鍵部分.本實驗使用模型及參數設置如3.2節所述.我們將數據采集模塊收集的61個不同程序，共2505個基本塊的運行故障數據，并添加基本塊脆弱性標簽，基本塊脆弱性計算公式為：公式(2).根據基本塊脆弱性將其分為5類：一定發生控制流錯誤、極易發生控制流錯誤、比較容易發生控制流錯誤、很少發生控制流錯誤、不發生控制流錯誤，排除第1類和第5類的數據，其他3類樣本數量按照基本塊脆弱性由高到低3等分.

采用多粒度掃描對初始數據集進行處理，提取基本塊間特征相關度，并生成新的特征集合作為級聯森林的輸入數據.將訓練好的模型在MiBench測試套件中的6個程序上進行驗證.我們對每個測試程序的基本塊進行100次的故障注入實驗，根據故障注入結果計算每個基本塊的脆弱性，并根據脆弱性大小進行分類，從高到低一共分為五類.同時對比了不同分類模型的分類效果，不同模型的分類準確性如圖4所示.

圖4 分類準確性對比

由實驗結果可見，多粒度級聯森林在多分類任務中的效果相比于傳統多分類機器學習模型有較好的準確性.

對于預測出“極易發生控制流錯誤”的基本塊，需要進行進一步的拆分，不僅可以防止發生在該基本塊內部的控制流錯誤漏檢，也可以提高程序整體的錯誤檢測率.

5.2 高脆弱性基本塊拆分對傳統基于標簽的控制流錯誤檢測算法的影響

本節評估針對高脆弱性基本塊的拆分策略對傳統的基于標簽的控制流錯誤檢測方法的檢測率與開銷的影響.故障檢測率方面，我們對選取的每個測試程序進行2500次的隨機故障注入實驗，對比其在不同檢測算法下拆分前后的故障檢測率；開銷方面，我們對選取的每次測試程序，分別對比其拆分前后原程序、插樁不同檢測算法標簽后的運行時間開銷和空間開銷.最終對比其檢測率，以驗證本文提出的方法的可行性.

采用MiBench測試套件中6個測試程序：Qsort、Dijkstra、FFT、Isqrt、Bit string和Rad2deg.分析6個測試程序的時空開銷如圖5、圖6所示.

圖5 檢測方案額外空間開銷對比

圖6 檢測方案額外時間開銷對比

為了驗證CFCSS和RCFC算法在基本塊進行針對性的拆分后算法檢測性能的提升情況，對6個測試程序進行了程序間跳轉故障注入和隨機跳轉故障注入各2500次，實驗結果如表4所示.其中程序內跳轉代表程序發生錯誤跳轉，跳轉的目的地址依舊在程序內；隨機跳轉表示程序發生錯誤跳轉，跳轉目的地址為隨機的計算機地址空間.CFCSS-S和RCFC-S分別代表經過基本塊拆分后再加固的程序.

表4中程序的故障注入運行結果分為4類：“系統錯誤”表示程序發生系統故障被檢測；“方法報錯”表示程序發生故障被檢測方法檢測；“正確運行”表示程序發生故障但是輸出結果正確；“錯誤漏檢”表示程序發生故障沒有被檢測到.從實驗結果可以看出，錯誤檢測算法能檢測出大多數程序內跳轉錯誤，但是隨機跳轉錯誤主要是被系統直接檢測出來.單標簽檢測算法CFCSS在各類程序不同錯誤類型下普遍低于雙標簽檢測算法RCFC.兩種方法不論是在程序內跳轉還是隨機跳轉情況下，控制流錯誤檢測率均有提升.

表4 檢測算法故障注入結果統計表

經過對比發現，不論是CFCSS算法還是RCFC算法，在經過智能拆分后的程序上驗證，控制流錯誤檢測率都有較高的提升.其中，程序內跳轉檢測率提升尤為明顯，是因為對程序進行基本塊智能拆分后，提升了基本塊內的控制流跳轉錯誤檢測率.隨機跳轉檢測率提升較低，是因為隨機跳轉目的地址空間很大，有很大概率跳轉到程序空間外，只有當程序地址發生低位翻轉時，程序會發生內部跳轉，進而被優化后的算法檢測到.

6 總 結

本文提出了一種針對傳統基于標簽的控制流錯誤檢測算法的通用優化方案.使用GDB開發了控制流錯誤故障注入工具，使用LLVM Pass實現基本塊拆分的自動化工具，并在LLVM IR層級設計實現了程序基本塊特征自動提取工具.利用多粒度級聯森林實現了基本塊脆弱性預測模型，并對高脆弱性基本塊進行拆分.實驗表明，拆分后的程序時空開銷增加量很小.并且在單標簽檢測算法CFCSS和雙標簽檢測算法RCFC上均可以實現高效費比的控制流錯誤檢測.對傳統的標簽檢測算法的優化有著重要的意義.