基于級(jí)聯(lián)森林的控制流錯(cuò)誤檢測(cè)優(yōu)化算法

董志騰，顧晶晶

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 南京 211106)

1 引 言

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

瞬時(shí)故障引起的錯(cuò)誤如果打亂了程序正常的執(zhí)行順序?qū)е鲁绦虺鲥e(cuò)，我們將這種錯(cuò)誤稱為控制流錯(cuò)誤.研究表明，瞬時(shí)故障引起的錯(cuò)誤中有約33%～77%的錯(cuò)誤是控制流錯(cuò)誤[3,4].控制流錯(cuò)誤主要是由于瞬時(shí)故障發(fā)生在程序計(jì)數(shù)器(PC)，地址存儲(chǔ)單元或者條件判斷語(yǔ)句中的變量存儲(chǔ)單元.控制流錯(cuò)誤會(huì)造成計(jì)算機(jī)程序不按照正確的指令順序執(zhí)行，可能會(huì)干擾程序的運(yùn)行結(jié)果、造成程序陷入死循環(huán)甚至崩潰[5].

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

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

1)本文通過(guò)收集分析大量程序數(shù)據(jù)，使用多粒度級(jí)聯(lián)森林模型[12]，對(duì)程序中易發(fā)生控制流錯(cuò)誤的基本塊進(jìn)行識(shí)別，取得了不錯(cuò)的識(shí)別率.

2)本文使用LLVM編譯器[13-15]，對(duì)程序中的基本塊進(jìn)行重新拆分，并編寫LLVM Pass文件實(shí)現(xiàn)CFCSS單標(biāo)簽檢測(cè)算法和RCFC雙標(biāo)簽檢測(cè)算法，在拆分好的程序上自動(dòng)添加標(biāo)簽.

3)本文在選用MiBench測(cè)試集[16]中的6個(gè)測(cè)試程序進(jìn)行驗(yàn)證，證明我們的方法使用較低的額外開(kāi)銷可以提升較高的檢測(cè)率.

2 背景和相關(guān)工作

對(duì)于控制流錯(cuò)誤的檢測(cè)，相比于基于硬件的檢測(cè)方法[17]，目前的軟件檢測(cè)方法通常是基于標(biāo)簽的檢測(cè)方法[18]，主要流程是將程序劃分成基本塊，為每個(gè)基本塊分配若干個(gè)標(biāo)簽，并在程序運(yùn)行期間維護(hù)一個(gè)隨當(dāng)前基本塊變化而變化的全局變量來(lái)進(jìn)行錯(cuò)誤檢測(cè).

目前實(shí)用性最強(qiáng)的基于標(biāo)簽的檢測(cè)方法是CFCSS[10](Control Flow Checking by Software Signatures)，CFCSS將程序劃分成若干個(gè)指令序列，并正式提出基本塊的概念.CFCSS在編譯階段為每個(gè)基本塊分配靜態(tài)標(biāo)簽，通過(guò)比較靜態(tài)標(biāo)簽和運(yùn)行時(shí)的全局變量來(lái)判斷程序是否發(fā)生了控制流錯(cuò)誤.

RCFC也是一種基于標(biāo)簽的控制流錯(cuò)誤檢測(cè)算法，它提出了一種雙標(biāo)簽的檢測(cè)方法，利用應(yīng)用程序中的循環(huán)嵌套結(jié)構(gòu)將程序基本塊分割成有條件的和無(wú)條件的基本塊，有選擇性的對(duì)其進(jìn)行標(biāo)簽跟蹤[11].該方法雖然泛化性不高，但是提出的雙標(biāo)簽算法為后續(xù)的研究工作提供了一些思路.雙標(biāo)簽檢測(cè)方法一般會(huì)維護(hù)兩個(gè)全局變量跟蹤程序運(yùn)行時(shí)的前驅(qū)和后繼節(jié)點(diǎn)，并通過(guò)設(shè)計(jì)比較規(guī)則來(lái)判斷程序是否發(fā)生了控制流錯(cuò)誤.

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

本文著眼于使用軟件方法檢測(cè)控制流錯(cuò)誤的問(wèn)題.針對(duì)傳統(tǒng)的基于標(biāo)簽的檢測(cè)算法在標(biāo)簽插樁粒度和錯(cuò)誤檢測(cè)率之間難以平衡的難點(diǎn)以及塊內(nèi)錯(cuò)誤難以檢測(cè)的難點(diǎn)，設(shè)計(jì)了一套的針對(duì)基于標(biāo)簽檢測(cè)方法的通用優(yōu)化算法.

3 控制流錯(cuò)誤檢測(cè)優(yōu)化方案

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

圖1 控制流錯(cuò)誤檢測(cè)方案流程圖

3.1 相關(guān)定義

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

定義2.基本塊(Basicblock，bb)是一個(gè)最大的連續(xù)指令集合，記為bb={Iin，…，Ii，…，iout}.在每個(gè)基本塊中，指令由第一條順序執(zhí)行至最后一條，即每個(gè)基本塊只有唯一的入口指令I(lǐng)in和唯一的出口指令I(lǐng)out.基本塊中除了最后一條指令外，不可能包含額外的分支、跳轉(zhuǎn).同時(shí)，每個(gè)基本塊也不可能分支、跳轉(zhuǎn)或者調(diào)用其他基本塊中除第一條指令以外的指令.

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

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

定義5.基本塊脆弱性描述該基本塊在程序運(yùn)行時(shí)發(fā)生控制流錯(cuò)誤的難易程度.脆弱性越高代表該基本塊越容易發(fā)生控制流錯(cuò)誤.

3.2 數(shù)據(jù)采集模塊

3.2.1 原始數(shù)據(jù)集

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

表1 原始數(shù)據(jù)集程序名稱

3.2.2 基本塊編號(hào)插樁

本文討論的控制流錯(cuò)誤主要依賴于程序的基本塊信息.每個(gè)基本塊是一個(gè)連續(xù)的指令集合，記為bb={Iin，…，Ii，…，Iout}，如定義2所描述.為了準(zhǔn)確獲取程序運(yùn)行時(shí)基本塊bb與指令集合的對(duì)應(yīng)關(guān)系，需要對(duì)基本塊進(jìn)行標(biāo)號(hào)，記作bbi.構(gòu)建bbi到指令集合的一對(duì)多的映射關(guān)系.

在程序運(yùn)行時(shí)分析程序當(dāng)前運(yùn)行的指令所在基本塊的編號(hào)是很困難的，而這恰恰是分析程序控制流錯(cuò)誤發(fā)生位置的關(guān)鍵點(diǎn).本文提出基本塊編號(hào)插樁的方法，對(duì)程序的每個(gè)基本塊分配唯一的編號(hào)，并使用一個(gè)全局變量記錄當(dāng)前程序正在運(yùn)行的位置.具體的步驟為：

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

步驟2.使用LLVM Pass對(duì)程序進(jìn)行分析，遍歷所有基本塊，依次為其編號(hào)；

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

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

經(jīng)過(guò)基本塊號(hào)標(biāo)簽插樁的程序在運(yùn)行的任何時(shí)間點(diǎn)的變量GSIG記錄的值都是程序基本塊的標(biāo)號(hào).

3.2.3 故障注入

為了分析程序中每個(gè)基本塊的脆弱性，需要收集每個(gè)基本塊發(fā)生控制流錯(cuò)誤后的數(shù)據(jù).收集這類數(shù)據(jù)一般有兩類方案：1)大量的故障注入實(shí)驗(yàn)，使得控制流錯(cuò)誤覆蓋到每個(gè)基本塊；2)針對(duì)每個(gè)基本塊做相同數(shù)量的故障注入實(shí)驗(yàn).程序在運(yùn)行過(guò)程中，每個(gè)基本塊的執(zhí)行次數(shù)、執(zhí)行時(shí)間有很大的差異，所以，方案1會(huì)造成樣本的數(shù)量很不均衡，在極端情況下會(huì)造成部分基本塊因?yàn)楣收献⑷氪螖?shù)過(guò)少使得樣本無(wú)效.很顯然方案2是一種比較合適的方法.

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

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

步驟1.啟動(dòng)GDB工具；

步驟2.針對(duì)全局變量GSIG設(shè)置檢測(cè)點(diǎn)；

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

步驟5.當(dāng)GSIG的值發(fā)生變化時(shí)，重復(fù)執(zhí)行步驟2、步驟3；

步驟6.程序運(yùn)行結(jié)束.

在故障注入時(shí)，針對(duì)每個(gè)不同的基本塊，我們只需要隨機(jī)選取對(duì)應(yīng)映射關(guān)系中的PC值，并在該處打斷點(diǎn)，當(dāng)程序運(yùn)行到該位置時(shí)，隨機(jī)翻轉(zhuǎn)PC寄存器的值，即可完成針對(duì)基本塊的控制流錯(cuò)誤故障注入.在已知程序所有指令所對(duì)應(yīng)的PC寄存器值的情況下，還可以做到指定跳轉(zhuǎn)目的地址，做到控制基本塊內(nèi)、塊間以及過(guò)程間的控制流跳轉(zhuǎn).

程序在運(yùn)行時(shí)按照一定的故障發(fā)生率[21]進(jìn)行故障注入，需要收集一些動(dòng)態(tài)特征，首先基本塊脆弱性定義為該基本塊中發(fā)生控制流錯(cuò)誤后，程序發(fā)生錯(cuò)誤的概率與該基本塊的占程序總運(yùn)行時(shí)間占比的乘積，具體定義如下：

基本塊集合：B={bb1，…，bbi，…，bbN}，基本塊動(dòng)態(tài)特征集合為：Bdynamic={round1，…，roundi，…，roundN}，其中roundi為基本塊bbi的執(zhí)行次數(shù)，比如循環(huán)體基本塊在程序執(zhí)行過(guò)程中會(huì)多次執(zhí)行，假設(shè)計(jì)算機(jī)執(zhí)行每條指令的時(shí)間大致相同，那么每個(gè)基本塊占程序執(zhí)行總時(shí)間的比重為：

(1)

針對(duì)程序的每個(gè)基本塊故障注入M次，程序發(fā)生錯(cuò)誤的次數(shù)統(tǒng)計(jì)為：C={C1，…，Ci，…，CN}，基本塊的脆弱性定義為：

(2)

3.2.4 靜態(tài)特征

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

靜態(tài)特征是指程序代碼在編寫完成后就具備的特征.這些特征與程序執(zhí)行過(guò)程中的輸入無(wú)關(guān)，僅僅與代碼相關(guān).

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

3.3 模型訓(xùn)練模塊

數(shù)據(jù)采集階段收集的基本塊特征集合，經(jīng)數(shù)據(jù)預(yù)處理之后，篩除一些無(wú)效樣本.使用跨樣本的滑動(dòng)窗口技術(shù)對(duì)數(shù)據(jù)集進(jìn)行處理，獲得了基本塊執(zhí)行序列的相關(guān)特性集合Fexpand，與特征集合Fi合并為初始的輸入特征Forigin=.Forigin將作為級(jí)聯(lián)森林的初始輸入數(shù)據(jù)進(jìn)行模型訓(xùn)練.模型訓(xùn)練模塊將在第4章給出詳細(xì)過(guò)程.

3.4 基于標(biāo)簽檢測(cè)算法的優(yōu)化策略

使用Clang編譯器[22]將待檢測(cè)程序編譯成LLVM IR中間代碼，目標(biāo)程序待預(yù)測(cè)的基本塊集合為Bpredict={bb1，…，bbi，…，bbN}.其中bbi表示程序中的第i個(gè)基本塊，N為程序中的基本塊數(shù)量.通過(guò)LLVM Pass對(duì)Bpredict集合中的所有基本塊進(jìn)行分析得到基本塊的靜態(tài)特征，并使用GDB工具獲取基本塊的動(dòng)態(tài)特征，合并得到基本塊特征Fi.基于已經(jīng)訓(xùn)練好的基本塊脆弱性預(yù)測(cè)模型對(duì)目標(biāo)程序的基本塊脆弱性進(jìn)行預(yù)測(cè)，并輸出基本塊標(biāo)號(hào)和脆弱性關(guān)系到統(tǒng)計(jì)文件中.

將預(yù)測(cè)結(jié)果中脆弱性大于閾值的基本塊進(jìn)行拆分，得到的新程序使用基于標(biāo)簽的控制流錯(cuò)誤檢測(cè)算法進(jìn)行驗(yàn)證.對(duì)比算法在程序拆分前后的檢測(cè)率以及時(shí)空開(kāi)銷的變化情況.對(duì)比預(yù)測(cè)模型在多種待測(cè)程序和多種標(biāo)簽檢測(cè)算法上的運(yùn)行結(jié)果，驗(yàn)證本文的基于標(biāo)簽的檢測(cè)算法優(yōu)化策略可行.

4 基于多粒度級(jí)聯(lián)森林的基本塊脆弱性預(yù)測(cè)算法描述

4.1 數(shù)據(jù)分析

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

表2 基本塊特征描述表

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

不同類別指令數(shù)量是描述程序基本塊中不同指令數(shù)量的特征[23].不同類型的指令代表了程序的不同功能，比如讀取存儲(chǔ)指令、運(yùn)算指令數(shù)量越多，程序更有可能只是進(jìn)行單一順序的執(zhí)行，這時(shí)若發(fā)生控制流錯(cuò)誤很有可能會(huì)造成程序運(yùn)行結(jié)果錯(cuò)誤；若跳轉(zhuǎn)指令、函數(shù)調(diào)用指令數(shù)量越多，程序更有可能在發(fā)生跳轉(zhuǎn)或者在執(zhí)行循環(huán)操作，這時(shí)若發(fā)生控制流錯(cuò)誤，很有可能會(huì)造成程序進(jìn)入死循環(huán)或者掛起.基本塊中包含的不同類別的指令數(shù)量基本可以表示當(dāng)前基本塊的作用，因此本章將不同類別指令數(shù)量作為特征提取并表示為：Vins_type.

程序基本塊的出度入度是描述程序基本塊執(zhí)行順序的特征.程序從入度為零的基本塊按照順序執(zhí)行直到最后一個(gè)出度為零的基本塊.基本塊的入度出度也描述了該基本塊的執(zhí)行重要程度.比如經(jīng)常被調(diào)用的函數(shù)包含的基本塊的入度會(huì)比較大，包含if、switch等條件跳轉(zhuǎn)語(yǔ)句所在的基本塊出度會(huì)比較大.這類基本塊在發(fā)生控制流錯(cuò)誤時(shí)很有可能會(huì)造成程序跳轉(zhuǎn)關(guān)系的混亂，造成不可預(yù)知的錯(cuò)誤.因此，本章將程序基本塊的出度入度作為特征提取并表示為：Vin_and_out.

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

程序中不同基本塊由于功能不同，在程序運(yùn)行過(guò)程中，基本塊的執(zhí)行次數(shù)相差很大.一些與參數(shù)初始化有關(guān)的基本塊在程序執(zhí)行過(guò)程中只會(huì)執(zhí)行一次，而有些與循環(huán)相關(guān)的基本塊可能會(huì)執(zhí)行成千上萬(wàn)次.基本塊的執(zhí)行次數(shù)與該基本塊的執(zhí)行時(shí)間直接相關(guān).同時(shí)程序在不同測(cè)試用例下，相同的基本塊執(zhí)行次數(shù)也會(huì)有差異，使用單一測(cè)試用例進(jìn)行測(cè)試得到的基本塊執(zhí)行次數(shù)并不完全準(zhǔn)確.LLVM提供了一種啟發(fā)式算法，可以對(duì)程序基本塊的執(zhí)行次數(shù)進(jìn)行預(yù)測(cè)，預(yù)測(cè)出的基本塊執(zhí)行次數(shù)可以對(duì)單一測(cè)試用例下基本塊執(zhí)行次數(shù)的測(cè)量值進(jìn)行補(bǔ)充，盡可能接近真實(shí)的基本塊執(zhí)行次數(shù).因此，本章將程序基本塊執(zhí)行次數(shù)作為特征提取并表示為：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表示基本塊中的包含的指令數(shù)量，ins_type1，ins_type2，…，ins_type9分別表示第1類到第9類的指令數(shù)量，in，out表示基本塊的入度和出度，opavg表示平均每條指令的操作數(shù)數(shù)量，realrounds表示程序在單一測(cè)試用例下完整運(yùn)行一次基本塊執(zhí)行的次數(shù)，predictrounds表示LLVM啟發(fā)式算法計(jì)算的基本塊執(zhí)行次數(shù).故障注入工具對(duì)程序集中所有的基本塊逐個(gè)進(jìn)行故障注入，根據(jù)程序運(yùn)行結(jié)果統(tǒng)計(jì)每個(gè)基本塊的脆弱性Pi，并結(jié)合基本塊的靜態(tài)特征與動(dòng)態(tài)特征構(gòu)建基本塊脆弱性預(yù)測(cè)模型的特征集合E={(Fi，Pi)}.

4.2 算法描述

gcForest是一種決策樹(shù)集成方法，在多分類任務(wù)中具有與深度神經(jīng)網(wǎng)絡(luò)相近的性能.本章介紹級(jí)聯(lián)森林在程序基本塊脆弱性預(yù)測(cè)的構(gòu)造過(guò)程.主要分為兩部分：多粒度掃描和級(jí)聯(lián)森林結(jié)構(gòu).多粒度掃描可以挖掘樣本間的特征相關(guān)性，構(gòu)造更適用于級(jí)聯(lián)森林模型的數(shù)據(jù)集；級(jí)聯(lián)森林可以利用不同森林的特性，提高預(yù)測(cè)的準(zhǔn)確性.

4.2.1 多粒度掃描

為了增強(qiáng)級(jí)聯(lián)森林結(jié)構(gòu)的訓(xùn)練效果，我們采用多粒度掃描對(duì)特征進(jìn)行處理.多粒度掃描的基本思想來(lái)源于深度神經(jīng)網(wǎng)絡(luò)，類似于深度神經(jīng)網(wǎng)絡(luò)中的卷積核滑動(dòng)過(guò)程.但一般情況下單一粒度的滑動(dòng)窗口掃描只能獲取固定序列中的有效特征，而多粒度掃描可以利用樣本間的相關(guān)性特征.本文的多粒度掃描模型如圖2所示.

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

圖2 多粒度掃描模型

4.2.2 級(jí)聯(lián)森林

本文中使用級(jí)聯(lián)森林對(duì)程序基本塊脆弱性進(jìn)行預(yù)測(cè).級(jí)聯(lián)森林由多層隨機(jī)森林結(jié)構(gòu)集合而成，每一層由不同的隨機(jī)森林組成，本文采用普通隨機(jī)森林和完全隨機(jī)森林，每一層的訓(xùn)練結(jié)果作為下一層的特征信息，從而增強(qiáng)下一層深林的訓(xùn)練結(jié)果，如圖3所示.

圖3 級(jí)聯(lián)森林模型

4.2.3 基本塊拆分策略

為了提升控制流錯(cuò)誤的檢測(cè)粒度，本文對(duì)脆弱性高的基本塊進(jìn)行拆分，以檢測(cè)更多發(fā)生于該基本塊的塊間和塊內(nèi)錯(cuò)誤.具體策略為：

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

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

步驟2.拆分基本塊

在選取的k個(gè)基本塊中選擇合適的指令位置，使用LLVM Pass將選中的基本塊從該指令后一分為二.為了防止基本塊拆分過(guò)程使程序的代碼規(guī)則被破壞，在基本塊拆分時(shí)，不選擇phi指令前進(jìn)行拆分，在LLVM IR中間代碼規(guī)則中，phi指令記錄了當(dāng)前基本塊的前驅(qū)，故phi指令之前不允許有其他指令出現(xiàn).

步驟3.插樁錯(cuò)誤檢測(cè)標(biāo)簽

程序經(jīng)過(guò)基本塊拆分后，選擇不同的基于標(biāo)簽的檢測(cè)算法(本文選擇CFCSS和RCFC算法)進(jìn)行檢測(cè)標(biāo)簽插樁，并確?；緣K拆分并插樁檢測(cè)標(biāo)簽后可以正常運(yùn)行.

5 控制流錯(cuò)誤檢測(cè)驗(yàn)證實(shí)驗(yàn)

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

1)首先將所選程序使用LLVM編譯程中間代碼形式(LLVM IR)，使用LLVM Pass提取基本塊靜態(tài)特征并在每個(gè)基本塊首插樁塊號(hào)標(biāo)簽，再使用GDB調(diào)試工具運(yùn)行程序獲取程序的動(dòng)態(tài)特征.

2)結(jié)合靜態(tài)動(dòng)態(tài)特征，使用訓(xùn)練好的級(jí)聯(lián)森林對(duì)基本塊的脆弱性進(jìn)行預(yù)測(cè).

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

4)針對(duì)拆分前后的測(cè)試程序，使用CFCSS和RCFC兩種標(biāo)簽檢測(cè)算法進(jìn)行控制流錯(cuò)誤檢測(cè).對(duì)比其開(kāi)銷和檢測(cè)率.

本章對(duì)故障注入實(shí)驗(yàn)做了以下假設(shè)[25]：1)僅考慮因PC寄存器發(fā)生故障導(dǎo)致的控制流錯(cuò)誤；2)程序每次執(zhí)行過(guò)程中有且只有一次故障.

從兩個(gè)方面評(píng)估本文提出的方法：1)基本塊脆弱性預(yù)測(cè)的準(zhǔn)確性；2)針對(duì)高脆弱性基本塊拆分的策略對(duì)傳統(tǒng)基于標(biāo)簽的控制流錯(cuò)誤檢測(cè)方法在檢測(cè)率上的提升.

5.1 基本塊脆弱性預(yù)測(cè)實(shí)驗(yàn)

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

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

圖4 分類準(zhǔn)確性對(duì)比

由實(shí)驗(yàn)結(jié)果可見(jiàn)，多粒度級(jí)聯(lián)森林在多分類任務(wù)中的效果相比于傳統(tǒng)多分類機(jī)器學(xué)習(xí)模型有較好的準(zhǔn)確性.

對(duì)于預(yù)測(cè)出“極易發(fā)生控制流錯(cuò)誤”的基本塊，需要進(jìn)行進(jìn)一步的拆分，不僅可以防止發(fā)生在該基本塊內(nèi)部的控制流錯(cuò)誤漏檢，也可以提高程序整體的錯(cuò)誤檢測(cè)率.

5.2 高脆弱性基本塊拆分對(duì)傳統(tǒng)基于標(biāo)簽的控制流錯(cuò)誤檢測(cè)算法的影響

本節(jié)評(píng)估針對(duì)高脆弱性基本塊的拆分策略對(duì)傳統(tǒng)的基于標(biāo)簽的控制流錯(cuò)誤檢測(cè)方法的檢測(cè)率與開(kāi)銷的影響.故障檢測(cè)率方面，我們對(duì)選取的每個(gè)測(cè)試程序進(jìn)行2500次的隨機(jī)故障注入實(shí)驗(yàn)，對(duì)比其在不同檢測(cè)算法下拆分前后的故障檢測(cè)率；開(kāi)銷方面，我們對(duì)選取的每次測(cè)試程序，分別對(duì)比其拆分前后原程序、插樁不同檢測(cè)算法標(biāo)簽后的運(yùn)行時(shí)間開(kāi)銷和空間開(kāi)銷.最終對(duì)比其檢測(cè)率，以驗(yàn)證本文提出的方法的可行性.

采用MiBench測(cè)試套件中6個(gè)測(cè)試程序：Qsort、Dijkstra、FFT、Isqrt、Bit string和Rad2deg.分析6個(gè)測(cè)試程序的時(shí)空開(kāi)銷如圖5、圖6所示.

圖5 檢測(cè)方案額外空間開(kāi)銷對(duì)比

圖6 檢測(cè)方案額外時(shí)間開(kāi)銷對(duì)比

為了驗(yàn)證CFCSS和RCFC算法在基本塊進(jìn)行針對(duì)性的拆分后算法檢測(cè)性能的提升情況，對(duì)6個(gè)測(cè)試程序進(jìn)行了程序間跳轉(zhuǎn)故障注入和隨機(jī)跳轉(zhuǎn)故障注入各2500次，實(shí)驗(yàn)結(jié)果如表4所示.其中程序內(nèi)跳轉(zhuǎn)代表程序發(fā)生錯(cuò)誤跳轉(zhuǎn)，跳轉(zhuǎn)的目的地址依舊在程序內(nèi)；隨機(jī)跳轉(zhuǎn)表示程序發(fā)生錯(cuò)誤跳轉(zhuǎn)，跳轉(zhuǎn)目的地址為隨機(jī)的計(jì)算機(jī)地址空間.CFCSS-S和RCFC-S分別代表經(jīng)過(guò)基本塊拆分后再加固的程序.

表4中程序的故障注入運(yùn)行結(jié)果分為4類：“系統(tǒng)錯(cuò)誤”表示程序發(fā)生系統(tǒng)故障被檢測(cè)；“方法報(bào)錯(cuò)”表示程序發(fā)生故障被檢測(cè)方法檢測(cè)；“正確運(yùn)行”表示程序發(fā)生故障但是輸出結(jié)果正確；“錯(cuò)誤漏檢”表示程序發(fā)生故障沒(méi)有被檢測(cè)到.從實(shí)驗(yàn)結(jié)果可以看出，錯(cuò)誤檢測(cè)算法能檢測(cè)出大多數(shù)程序內(nèi)跳轉(zhuǎn)錯(cuò)誤，但是隨機(jī)跳轉(zhuǎn)錯(cuò)誤主要是被系統(tǒng)直接檢測(cè)出來(lái).單標(biāo)簽檢測(cè)算法CFCSS在各類程序不同錯(cuò)誤類型下普遍低于雙標(biāo)簽檢測(cè)算法RCFC.兩種方法不論是在程序內(nèi)跳轉(zhuǎn)還是隨機(jī)跳轉(zhuǎn)情況下，控制流錯(cuò)誤檢測(cè)率均有提升.

表4 檢測(cè)算法故障注入結(jié)果統(tǒng)計(jì)表

經(jīng)過(guò)對(duì)比發(fā)現(xiàn)，不論是CFCSS算法還是RCFC算法，在經(jīng)過(guò)智能拆分后的程序上驗(yàn)證，控制流錯(cuò)誤檢測(cè)率都有較高的提升.其中，程序內(nèi)跳轉(zhuǎn)檢測(cè)率提升尤為明顯，是因?yàn)閷?duì)程序進(jìn)行基本塊智能拆分后，提升了基本塊內(nèi)的控制流跳轉(zhuǎn)錯(cuò)誤檢測(cè)率.隨機(jī)跳轉(zhuǎn)檢測(cè)率提升較低，是因?yàn)殡S機(jī)跳轉(zhuǎn)目的地址空間很大，有很大概率跳轉(zhuǎn)到程序空間外，只有當(dāng)程序地址發(fā)生低位翻轉(zhuǎn)時(shí)，程序會(huì)發(fā)生內(nèi)部跳轉(zhuǎn)，進(jìn)而被優(yōu)化后的算法檢測(cè)到.

6 總 結(jié)

本文提出了一種針對(duì)傳統(tǒng)基于標(biāo)簽的控制流錯(cuò)誤檢測(cè)算法的通用優(yōu)化方案.使用GDB開(kāi)發(fā)了控制流錯(cuò)誤故障注入工具，使用LLVM Pass實(shí)現(xiàn)基本塊拆分的自動(dòng)化工具，并在LLVM IR層級(jí)設(shè)計(jì)實(shí)現(xiàn)了程序基本塊特征自動(dòng)提取工具.利用多粒度級(jí)聯(lián)森林實(shí)現(xiàn)了基本塊脆弱性預(yù)測(cè)模型，并對(duì)高脆弱性基本塊進(jìn)行拆分.實(shí)驗(yàn)表明，拆分后的程序時(shí)空開(kāi)銷增加量很小.并且在單標(biāo)簽檢測(cè)算法CFCSS和雙標(biāo)簽檢測(cè)算法RCFC上均可以實(shí)現(xiàn)高效費(fèi)比的控制流錯(cuò)誤檢測(cè).對(duì)傳統(tǒng)的標(biāo)簽檢測(cè)算法的優(yōu)化有著重要的意義.