基于機(jī)器學(xué)習(xí)的指令SDC脆弱性分析方法

張倩雯,莊 毅

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,南京 211106) E-mail:zy16@nuaa.edu.cn

1 概 述

隨著半導(dǎo)體制造技術(shù)的不斷發(fā)展,處理器不斷縮減集成電路的尺寸、降低工作的電壓.在計(jì)算機(jī)性能大幅度提升的同時(shí)使得芯片更容易受到空間輻射的影響.在太空等輻射環(huán)境中,由高能粒子輻照或電磁干擾等造成的單粒子效應(yīng)是計(jì)算機(jī)系統(tǒng)失效的主要原因,單粒子翻轉(zhuǎn)(Single Event Upset,SEU)是單粒子效應(yīng)最主要的表現(xiàn)形式.SEU是指高能粒子轟擊器件使其邏輯狀態(tài)發(fā)生翻轉(zhuǎn),使得存儲(chǔ)值的某一位由1變?yōu)?或由0變?yōu)?,可以通過重新寫入邏輯值恢復(fù)其狀態(tài),這種由單粒子翻轉(zhuǎn)造成的系統(tǒng)硬件故障稱為軟錯(cuò)誤[1],是一種瞬時(shí)故障.

軟錯(cuò)誤對(duì)系統(tǒng)可靠性的影響在于它會(huì)傳播到程序中,造成程序的狀態(tài)異?；蚬δ苁?瞬時(shí)故障對(duì)程序運(yùn)行的影響大致可分為3種:

1)沒有影響程序的正常運(yùn)行及結(jié)果(Benign);

2)導(dǎo)致程序崩潰(Crash)或掛起(Hang);

3)程序正常運(yùn)行,但出現(xiàn)了結(jié)果錯(cuò)誤,稱為SDC(Silent Data Corruption)錯(cuò)誤.

第二類錯(cuò)誤較易被檢測(cè)到,已有基于癥狀的檢測(cè)方法[2,3]對(duì)其進(jìn)行檢測(cè),并使用檢查點(diǎn)機(jī)制進(jìn)行恢復(fù).與這類錯(cuò)誤相比,SDC錯(cuò)誤是隱蔽傳播的.由于隱蔽傳播在程序的執(zhí)行過程中不會(huì)有系統(tǒng)錯(cuò)誤的提示,因而無法被檢測(cè)機(jī)制捕獲,但卻會(huì)導(dǎo)致程序產(chǎn)生錯(cuò)誤的結(jié)果,這也是本文研究的重點(diǎn).

隨著工藝尺寸的減小,軟錯(cuò)誤引起的失效問題也越來越多.為了解決空間輻射對(duì)軟件執(zhí)行的影響,尤其是在高可靠性的航空航天領(lǐng)域,要使得程序在SDC錯(cuò)誤存在的條件下仍然可以正確的運(yùn)行,我們必須實(shí)現(xiàn)針對(duì)SDC錯(cuò)誤的容錯(cuò)機(jī)制.然而,傳統(tǒng)的基于冗余的容錯(cuò)方案導(dǎo)致較大的性能開銷,因此需要設(shè)計(jì)輕量級(jí)的容錯(cuò)機(jī)制,這對(duì)于必須在嚴(yán)格的性能約束下操作的嵌入式系統(tǒng)尤其如此.已有研究表明,SDC錯(cuò)誤是由相對(duì)較小比例的指令中的數(shù)據(jù)變量錯(cuò)誤引起的[4],因此如可以事先找到軟件中的脆弱點(diǎn)并選擇性的保護(hù)這些變量,則可實(shí)現(xiàn)高效費(fèi)比的容錯(cuò)機(jī)制.

本文提出了一種基于機(jī)器學(xué)習(xí)的指令SDC脆弱性分析方法.SDC脆弱性(SDC vulnerability)指的是錯(cuò)誤發(fā)生后會(huì)導(dǎo)致程序SDC錯(cuò)誤的概率.該方法針對(duì)SDC錯(cuò)誤,結(jié)合了程序分析和機(jī)器學(xué)習(xí)方法,根據(jù)故障注入的結(jié)果在程序編譯時(shí)對(duì)指令特征進(jìn)行提取,訓(xùn)練指令SDC脆弱性預(yù)測(cè)模型.對(duì)于待分析的程序,可以在不需要故障注入的前提下預(yù)測(cè)指令的SDC脆弱性.

2 相關(guān)工作

目前分析程序中指令SDC脆弱性的方法主要有三種:基于故障注入的SDC脆弱性分析、基于程序靜態(tài)分析的SDC脆弱性分析、基于機(jī)器學(xué)習(xí)的SDC脆弱性分析.以下分類進(jìn)行相關(guān)研究工作分析介紹,并闡述本文的研究動(dòng)機(jī).

故障注入方法將需要注入故障的指令信息列入注入計(jì)劃表,接著依照計(jì)劃表依次進(jìn)行故障注入,這類方法往往代價(jià)過高,需要耗費(fèi)大量的時(shí)間.現(xiàn)有的研究工作一般通過有選擇的進(jìn)行故障注入降低注入的開銷.Hari等人基于控制流等價(jià)策略對(duì)故障空間進(jìn)行壓縮,利用指令的控制流上下文環(huán)境預(yù)測(cè)故障的結(jié)果,刪除結(jié)果可能相同的故障從而減少故障注入的開銷[5].Li等人在基于控制流等價(jià)策略的基礎(chǔ)上結(jié)合了數(shù)據(jù)流分析并開發(fā)了不同靜態(tài)指令間的等價(jià)性,提出了更有效的故障空間壓縮方法,實(shí)現(xiàn)了更高效的故障刪除[6].Xu等人通過指令級(jí)脆弱性分析從故障空間中刪除良性故障從而達(dá)到壓縮故障空間的目的[7].基于故障注入的方法具有可控性好、成本低等優(yōu)勢(shì),但面臨著權(quán)衡故障注入狀態(tài)空間與分析精度之間關(guān)系等問題.

基于靜態(tài)分析的方法通過分析程序的特征對(duì)程序的SDC脆弱性進(jìn)行分析,不需要進(jìn)行故障注入實(shí)驗(yàn).楊學(xué)軍等人通過建立錯(cuò)誤流模型來進(jìn)行瞬時(shí)故障在程序中傳播的分析,包括錯(cuò)誤傳播的規(guī)則和定律,給出了任意數(shù)據(jù)在任意計(jì)算后程序發(fā)生SDC錯(cuò)誤的概率,對(duì)錯(cuò)誤的傳播進(jìn)行了細(xì)致的量化研究[8].Pattabiraman等人利用符號(hào)執(zhí)行抽象程序中變量的錯(cuò)誤狀態(tài),利用模型檢驗(yàn)技術(shù)抽象執(zhí)行,分析錯(cuò)誤的傳播路徑及程序受到的影響從而識(shí)別程序中的SDC脆弱指令[9].這類基于程序靜態(tài)分析的技術(shù)容易導(dǎo)致狀態(tài)爆炸,因此很難應(yīng)用于大規(guī)模程序的分析.

馬駿馳等人將靜態(tài)分析與故障注入相結(jié)合,根據(jù)已執(zhí)行的故障注入的信息動(dòng)態(tài)的推測(cè)出SDC脆弱指令,在保證了準(zhǔn)確率的同時(shí)減低了故障注入的開銷,但這種方法很難覆蓋到所有與地址相關(guān)的指令,而且沒有考慮指令的操作數(shù)發(fā)生軟錯(cuò)誤后導(dǎo)致程序SDC錯(cuò)誤的概率性[10].

基于機(jī)器學(xué)習(xí)的SDC脆弱性分析方法通過提取程序的一系列特征來預(yù)測(cè)其脆弱性.Bronovetsky等人比較了支持向量機(jī)和神經(jīng)網(wǎng)絡(luò)這兩種機(jī)器學(xué)習(xí)方法在預(yù)測(cè)程序脆弱性時(shí)的優(yōu)缺點(diǎn),但他們提出的方法局限于線性代數(shù)應(yīng)用程序[11].Lu等人首先在程序編譯時(shí)提取指令的靜態(tài)特征,接著利用決策回歸樹對(duì)程序中的存儲(chǔ)指令和比較指令進(jìn)行脆弱性預(yù)測(cè),最后通過程序分析的方法得出程序中所有指令的SDC脆弱性[12].

綜上所述,故障注入的方法代價(jià)較高,而程序靜態(tài)分析的方法也面臨著空間代價(jià)和準(zhǔn)確率之間的權(quán)衡問題.如果能在編譯的中間代碼階段實(shí)現(xiàn)指令SDC脆弱性的分析,那么這種方法不僅靈活、可配置,還能利用編譯器來分析程序,支持多種硬件平臺(tái)和高級(jí)語言.本文在故障注入實(shí)驗(yàn)結(jié)果的基礎(chǔ)上,訓(xùn)練指令脆弱性預(yù)測(cè)模型.對(duì)于待分析的程序可以在不需要故障注入的前提下直接得到其指令的SDC脆弱性,用以指導(dǎo)錯(cuò)誤檢測(cè)機(jī)制的部署.

3 故障注入分析

瞬時(shí)故障有一定概率會(huì)引起程序的錯(cuò)誤,如指令操作結(jié)果發(fā)生錯(cuò)誤、訪問了錯(cuò)誤的內(nèi)存空間等.SDC錯(cuò)誤是由于錯(cuò)誤傳播到了程序的輸出導(dǎo)致的,因此一條指令的SDC脆弱性取決于在故障發(fā)生后它是如何傳播錯(cuò)誤的.在本節(jié)中,我們對(duì)故障模型進(jìn)行了假設(shè),描述了我們的故障注入實(shí)驗(yàn),最后討論了故障注入的實(shí)驗(yàn)結(jié)果并利用得到的結(jié)果在下一節(jié)中以指令為研究對(duì)象進(jìn)行具體的SDC脆弱性分析.

3.1 故障模型

為了通過故障注入實(shí)驗(yàn)對(duì)錯(cuò)誤傳播進(jìn)行分析,我們對(duì)故障模型做了如下的假設(shè):

1)本文主要考慮單粒子效應(yīng)單位翻轉(zhuǎn)的情況,通過改變指令寄存器的一個(gè)二進(jìn)制位來模擬單位翻轉(zhuǎn).考慮到真實(shí)硬件系統(tǒng)的軟錯(cuò)誤率[13]及單粒子翻轉(zhuǎn)故障重復(fù)率小、隨機(jī)性強(qiáng)、暫時(shí)性的特點(diǎn),我們有足夠的時(shí)間在下一次瞬時(shí)故障發(fā)生前對(duì)錯(cuò)誤進(jìn)行恢復(fù).因此,和之前的工作一樣,我們假設(shè)在程序的一次執(zhí)行中只會(huì)有一次故障的發(fā)生[12].

2)在硬件系統(tǒng)中,有些存儲(chǔ)模塊固化了ECC(Error Correcting Code)進(jìn)行數(shù)據(jù)效驗(yàn)從而實(shí)現(xiàn)對(duì)軟錯(cuò)誤的容錯(cuò),所以在我們的研究工作中考慮處理器中的功能部件和寄存器中(如,ALU、LSU、GPR等)發(fā)生的瞬時(shí)故障問題;我們不考慮程序計(jì)數(shù)器中發(fā)生的瞬時(shí)故障,因?yàn)檫@類故障導(dǎo)致的控制流錯(cuò)誤可以被控制流檢測(cè)機(jī)制[14]捕獲;同時(shí)指令操作碼發(fā)生錯(cuò)誤一般會(huì)導(dǎo)致程序的崩潰,因此本文只考慮指令操作數(shù)發(fā)生錯(cuò)誤.

3.2 故障注入實(shí)驗(yàn)

為了得到程序中指令的脆弱性并理解其是如何隨指令的不同而變化的,我們需要進(jìn)行故障注入實(shí)驗(yàn).我們使用LLFI作為故障注入工具,該工具已經(jīng)被驗(yàn)證了可用于檢測(cè)程序SDC錯(cuò)誤的準(zhǔn)確性[15].LLFI基于LLVM編譯器框架的,工作在LLVM IR(Intermediate Representative)指令層.我們通過將故障注入到程序中的任意動(dòng)態(tài)指令中來模擬分析瞬時(shí)故障對(duì)程序運(yùn)行的影響.LLVM的IR指令使用靜態(tài)單次賦值(Static Single Assignment,SSA)方式表示,所有的變量只能被賦值一次,每一條指令都定義了唯一的變量.

3.3 故障注入結(jié)果

以MiBench基準(zhǔn)程序?yàn)檠芯繉?duì)象進(jìn)行故障注入實(shí)驗(yàn),對(duì)造成程序SDC錯(cuò)誤的指令即SDC脆弱指令進(jìn)行統(tǒng)計(jì).結(jié)果如圖 1所示,對(duì)程序10000次的注入中,所有的SDC錯(cuò)誤由平均29.44%的靜態(tài)指令發(fā)生的瞬時(shí)故障造成,而90%的SDC錯(cuò)誤僅由程序中14.82%的靜態(tài)指令發(fā)生故障造成.因此,只有部分的靜態(tài)指令發(fā)軟錯(cuò)誤后會(huì)導(dǎo)致程序最終的SDC錯(cuò)誤,而我們的工作就是對(duì)程序中的指令進(jìn)行脆弱性預(yù)測(cè).

我們定義指令的SDC脆弱性為發(fā)生故障后會(huì)導(dǎo)致SDC錯(cuò)誤的概率.如圖 2所示,我們截取了MiBench基準(zhǔn)測(cè)試程序集中的SHA程序的一行作為示例.表 1中的列出了這行代碼對(duì)應(yīng)的IR指令,為了指令的可讀性對(duì)其寄存器名進(jìn)行了重命名.

圖1 SDC脆弱指令占比Fig.1 SDC-causing instructions ratio

從表1中可以看出,指令的SDC脆弱性和數(shù)據(jù)依賴關(guān)系是高度相關(guān)的.指令4和指令5中的結(jié)果變量會(huì)在地址相關(guān)的load/store指令的引用,有較大的可能造成程序的崩潰,因此具有較低的SDC脆弱性.指令2中的結(jié)果變量會(huì)在SDC脆弱性較高的指令7中被引用,但由于該指令中定義的%conv在移位操作中被引用,使其SDC脆弱性降低.

表1 示例代碼的指令SDC脆弱性
Table 1 SDC vulnerability of the sample code

ID指令SDC脆弱性1%1=loadi32*%count.addr,align40.752%conv=sexti32%1toi640.63%shl=shli64%conv,30.864%2=load%struct.SHA_INFO**%sha_info.addr,align80.15%count_lo=getelementptrinbounds%struct.SHA_INFO*%2,i320,i3210.156%3=loadi64*%count_lo,align80.897%add=addi64%3,%shl0.98storei64%add,i64*%count_lo,align8—

通過故障注入實(shí)驗(yàn)可知,瞬時(shí)故障是否會(huì)引起最終的SDC錯(cuò)誤是高度依賴于我們所要加固的應(yīng)用程序的,因此研究高效費(fèi)比的錯(cuò)誤檢測(cè)機(jī)制需要我們識(shí)別出程序中SDC脆弱性較高的指令.下一節(jié)中,我們會(huì)對(duì)影響指令脆弱性的指令特征進(jìn)行提取與分析,為指令SDC脆弱性的預(yù)測(cè)提供依據(jù).

4 指令的特征提取

指令的SDC脆弱性會(huì)受到多個(gè)方面的影響,為了設(shè)計(jì)針對(duì)SDC錯(cuò)誤的指令脆弱性分析方法,本節(jié)對(duì)影響指令SDC脆弱性的指令特征進(jìn)行了討論.在研究中,我們引入了切片技術(shù),以指令作為分析的基本單位.通過第3節(jié)中的故障注入實(shí)驗(yàn)的結(jié)果分析并提取了程序中影響指令脆弱性的特征.在本文的研究中,不考慮與指令脆弱性無關(guān)的特征,如模塊名等,也不考慮無法在LLVM IR指令中獲取的特征信息,如體系結(jié)構(gòu)相關(guān)的信息.4.1節(jié)介紹了程序切片技術(shù)并給出了相關(guān)的定義.以此為基礎(chǔ),4.2節(jié)對(duì)故障的傳播依賴進(jìn)行分析,給出了指令的依賴特征.4.3節(jié)對(duì)指令的固有特征進(jìn)行了提取.

4.1 程序切片技術(shù)

在程序的執(zhí)行過程中,指令的依賴關(guān)系在一定程度上能夠反映該指令的SDC脆弱性,我們需要識(shí)別出程序中受到所關(guān)注指令上變量的值所影響的語句或控制謂詞.本文引入了程序切片技術(shù)來實(shí)現(xiàn)這一目的.程序切片的概念由Mark Weiser提出,它是一種理解程序和分析程序的方法[16],在軟件測(cè)試和軟件調(diào)試領(lǐng)域應(yīng)用廣泛.我們?cè)贚LVM中通過依賴圖PDG(Program Dependency Graph)將程序切分為切片并利用程序切片進(jìn)行相關(guān)的研究從而實(shí)現(xiàn)對(duì)整個(gè)程序的理解.

程序依賴圖是根據(jù)指令的數(shù)據(jù)依賴和控制依賴建立的有向圖.其中節(jié)點(diǎn)集合V代表程序中的靜態(tài)指令,V={I0,I1,…,IN},N為程序中指令的數(shù)目.邊集合E代表指令間的依賴關(guān)系.將指令定義為六元組I=[Os,Od,SB,SF,BB,F],Os為指令I(lǐng)中的源操作數(shù),Od為指令I(lǐng)中的目的操作數(shù),SB為指令I(lǐng)的后向切片,SF為指令I(lǐng)的前向切片,BB為指令I(lǐng)所在的基本塊,F為指令I(lǐng)所在的函數(shù).

4.2 依賴特征選擇

在程序的運(yùn)行過程中,故障會(huì)通過數(shù)據(jù)的依賴關(guān)系傳播到程序的其他數(shù)據(jù)中,我們稱這種故障為傳播引起的故障.導(dǎo)致SDC錯(cuò)誤的執(zhí)行過程不會(huì)拋出系統(tǒng)異常的信息,硬件故障通過在程序中傳播導(dǎo)致最后程序的結(jié)果錯(cuò)誤,因此對(duì)程序中的數(shù)據(jù)依賴關(guān)系進(jìn)行分析有助于我們提取指令的依賴特征并用以指令的脆弱性分析.在分析指令脆弱性時(shí)將與數(shù)據(jù)依賴相關(guān)的指令特征稱為指令的依賴特征.

一條指令的SDC脆弱性取決其結(jié)果變量在數(shù)據(jù)依賴鏈的傳播路徑和其數(shù)據(jù)依賴鏈末端指令的脆弱性.在LLVM IR指令中,存儲(chǔ)指令store和轉(zhuǎn)移指令br沒有目的寄存器,函數(shù)調(diào)用指令call會(huì)產(chǎn)生一個(gè)新的棧幀,因此這些指令都會(huì)終止數(shù)據(jù)的依賴鏈.基于數(shù)據(jù)流的依賴關(guān)系,可將程序中的指令分為3類:

1)指令中發(fā)生的瞬時(shí)故障會(huì)傳播到存儲(chǔ)指令中;

2)指令中發(fā)生的瞬時(shí)故障傳播到分支跳轉(zhuǎn)操作;

3)指令中發(fā)生的瞬時(shí)故障傳播到函數(shù)調(diào)用指令中.在對(duì)第二類指令研究時(shí),由于分支跳轉(zhuǎn)指令的執(zhí)行取決于較比指令的結(jié)果,我們使用比較指令來分析指令的依賴脆弱因子.圖 3給出了分類代碼的示例,表示發(fā)生軟錯(cuò)誤的源代碼和對(duì)應(yīng)IR指令中故障傳播的依賴關(guān)系.

4.2.1 故障傳播分析

發(fā)生瞬時(shí)故障后,在指令的數(shù)據(jù)依賴鏈的傳播路徑中,影響指令脆弱性的因素主要有兩個(gè):傳播過程中故障是否會(huì)被屏蔽;傳播過程中故障是否會(huì)導(dǎo)致程序的崩潰.我們用SDC錯(cuò)誤屏蔽概率和程序崩潰概率分別來衡量這兩個(gè)因素,并基于此定義了依賴脆弱因子來衡量依賴關(guān)系對(duì)指令脆弱性的影響.

1)SDC錯(cuò)誤屏蔽

瞬時(shí)故障在程序的傳播過程中,有些指令會(huì)屏蔽錯(cuò)誤的傳播,如在x=y&0xfff0中會(huì)屏蔽y中低4位的錯(cuò)誤傳播到x,我們稱這類指令為Imask.因此如果指令中的結(jié)果會(huì)在這些指令中被使用,那么它的SDC脆弱性會(huì)降低.對(duì)于任意指令I(lǐng)i,我們定義Pmask(Ii)表示該指令屏蔽錯(cuò)誤的概率,錯(cuò)誤屏蔽指令的類型如表 2所示.其計(jì)算公式如公式(1)所示.

(1)

圖3 基于依賴關(guān)系劃分的指令分類Fig.3 Instruction classification based on dependencies

表2 SDC錯(cuò)誤屏蔽指令
Table 2 SDC error masking instructions

分 類指令操作邏輯操作and、or移位操作shl、lshr轉(zhuǎn)換操作trunc、fptosi

對(duì)于程序中的指令I(lǐng)i,我們定義屏蔽因子MF(Mask Factor)來表征該指令的SDC脆弱性受屏蔽指令的影響,屏蔽因子越大,指令發(fā)生錯(cuò)誤后被屏蔽的概率越小,那么它發(fā)生瞬時(shí)故障后程序發(fā)生SDC錯(cuò)誤的可能性也就越大.其計(jì)算公式如公式(2)所示.

MF(Ii)=FSDC(Iend)×(1-Pmask(Ii,p))

(2)

其中,Pmask(Ii,p)為指令I(lǐng)i發(fā)生錯(cuò)誤后在其傳播路徑p上被屏蔽的概率,其計(jì)算的具體過程在算法1中給出.FSDC(Iend)用來衡量指令I(lǐng)i數(shù)據(jù)依賴鏈末端指令I(lǐng)end的SDC脆弱性.對(duì)于數(shù)據(jù)依賴鏈的末端指令I(lǐng)end,若該指令在程序結(jié)果輸出指令的后向切片中,則FSDC(Iend)為1,若不在則為0,公式如下:

(3)

2)程序崩潰

在程序執(zhí)行時(shí),與地址相關(guān)的指令發(fā)生錯(cuò)誤后,絕大部分情況會(huì)導(dǎo)致程序的崩潰.由于瞬時(shí)故障造成的程序崩潰99%都是由于段錯(cuò)誤造成的,即程序的訪存空間超出了系統(tǒng)給這個(gè)程序的內(nèi)存空間[17].在程序中,地址變量的位數(shù)越大意味著越多的位發(fā)生錯(cuò)誤會(huì)導(dǎo)致程序崩潰.對(duì)地址相關(guān)的變量發(fā)生錯(cuò)誤后導(dǎo)致程序崩潰的概率以變量的位數(shù)進(jìn)行分類統(tǒng)計(jì),如圖 4(a)所示.為了衡量程序崩潰對(duì)SDC脆弱性的影響,我們提取與程序崩潰相關(guān)的特征,如后向切片中與地址相關(guān)的指令數(shù)、目的操作數(shù)的位數(shù)等.

圖4 操作數(shù)位數(shù)和循環(huán)深度對(duì)脆弱性的影響Fig.4 Effect of data width and loop depth on SDC vulnerability

4.2.2 末端指令

在數(shù)據(jù)依賴鏈末端指令中,對(duì)于第一類和第三類指令,其存儲(chǔ)的值是否會(huì)在比較指令或地址相關(guān)的指令中被使用會(huì)影響該指令SDC脆弱性;對(duì)于第二類指令,嵌套循環(huán)深度是影響比較指令SDC脆弱性的重要因素.循環(huán)深度與比較指令SDC脆弱性的關(guān)系圖 4(b)所示,我們選取循環(huán)深度作為一個(gè)特征,若不在循環(huán)內(nèi)則該值為0.

綜合上面的分析,我們提取了指令的依賴特征如表 3指令依賴特征所示.圖 5中的算法1給出了指令依賴特征分析的具體過程.算法首先將程序中的所有指令按照依賴關(guān)系分為三類并生成了從該指令到數(shù)據(jù)鏈末端指令的傳播路徑(第3-16步),接著基于傳播路徑為每個(gè)指令計(jì)算其錯(cuò)誤屏蔽因子(第18-20步),最后根據(jù)表3遍歷所有的指令提取相關(guān)的特征(第21-26步).

表3 指令依賴特征
Table 3 Instruction dependence features

類 別特 征 名存儲(chǔ)指令相關(guān)is_used_in_store函數(shù)調(diào)用指令相關(guān)is_used_in_call比較指令相關(guān)is_used_in_icmpis_used_in_fcmpis_used_in_zero_cmploop_depth程序崩潰相關(guān)is_used_in_addraddr_ins_numbytes_in_dest_operand錯(cuò)誤屏蔽相關(guān)mask_factor

4.3 固有特征選擇

指令的固有特征是用來表征指令本身的性質(zhì)的.在程序的執(zhí)行過程中,指令的屬性、指令所在基本塊或函數(shù)的特征都能在一定程度上反映指令的SDC脆弱性,通過分析指令及其所在的基本塊和函數(shù),提取出我們所關(guān)注的特征.

算法1.基于程序依賴圖PDG分析指令依賴特征

輸入：程序依賴圖PDG(V，E)

輸出：每條指令的依賴特征

1:SetEndPointOpcodeas {store,cmp,call},ListL() as null

2:Identify the backward slice ofIOand sae it as an istruction chainSB(IO)

3:forallIiinPDGdo

4:ifIi.opcode=cmpandIi.dest_operand!=?then

5: analyze features of category 3 in table 3

6:elseifIi.dest_operand!=?then

7: Identify the forward sice ofIiand save it as an instruction chainSF(Ii)

8:L().add(Ii)

9:iterateIk∈SF(Ii)do

10:ifIk.opcode∈EndPointOpcodethen

11:Ii.Iend=Ik

12: GeneratepfromIitoIi.Iend

13:enditeration

14:endif

15:endfor

16:forallIiinL()do

17: find the consecutiveImaskinIi.pand save it as ListLmask()

18:reverseiterateIj∈lmask()do

19:Pmask(I.Pre,p)=Pmask(I)+(1-Pmask(I))×Pmask(I.Suc,p)

20:enditeration

21:ifIi.Iend.opcode=store/calldo

22: analyze features of category 1 and 2 in table 3

23: analyze the forward slice ofIendand get features of category 3 and 4

24:else

25: analyze features of category 3 in table 3

26:endif

27:endfor

圖5 指令依賴特征分析算法
Fig.5 Algorithm of instruction dependence features analysis

4.3.1 指令類別

不同的指令發(fā)生瞬時(shí)故障后程序的失效結(jié)果與其種類是高度相關(guān)的.圖 6為在我們的訓(xùn)練程序集中注入故障后按指令類別進(jìn)行分類的統(tǒng)計(jì)結(jié)果.對(duì)于二元操作,浮點(diǎn)數(shù)之間的運(yùn)算由于其工作方式會(huì)對(duì)瞬時(shí)造成屏蔽,因此SDC脆弱性較低.與地址操作相關(guān)的指令有極大的概率會(huì)造成程序的崩潰降低了它的SDC脆弱性.而程序中的整型二元操作、比較指令等若發(fā)生瞬時(shí)故障則有極大的概率傳播到最后的結(jié)果中造成最終的SDC錯(cuò)誤.本文將指令類別抽象為一個(gè)特征向量,包含8個(gè)元素,分別表示該指令是否為整型二元操作、是否為浮點(diǎn)型二元操作、是否為比較指令、是否為邏輯操作、是否為轉(zhuǎn)換操作、是否為地址相關(guān)的操作、是否為函數(shù)調(diào)用指令、是否為內(nèi)存讀指令.

4.3.2 基本塊和函數(shù)相關(guān)的特征

在程序執(zhí)行的過程中,指令所在的基本塊和函數(shù)相關(guān)的屬性都會(huì)對(duì)指令的SDC脆弱性造成影響.文獻(xiàn)[12]中的實(shí)驗(yàn)結(jié)果也表明了指令所在函數(shù)的執(zhí)行時(shí)間這個(gè)特征在訓(xùn)練脆弱性預(yù)測(cè)模型時(shí)重要性系數(shù)達(dá)到了0.55.因此,本文提取了指令所在的基本塊和函數(shù)相關(guān)的6個(gè)特征,如表 4所示.

圖6 指令類別對(duì)程序結(jié)果的影響Fig.6 Effect of instruction category on execution results

類 別特征名描述 基本塊函數(shù)bb_lengthis_within_loopbb_remaining_ins_numins_func_dynamic_count_ratiocall_numfun_remaining_ins_num指令所在基本塊的大小指令是否在循環(huán)中到基本塊結(jié)束還需執(zhí)行的指令數(shù)指令與函數(shù)執(zhí)行時(shí)間的比值指令所在函數(shù)被調(diào)用的次數(shù)到函數(shù)返回還需執(zhí)行的指令數(shù)

4.3.3 其它特征

文獻(xiàn)[2]中對(duì)影響全局內(nèi)存和函數(shù)參數(shù)的變量進(jìn)行了保護(hù);文獻(xiàn)[18]中提出使用變量的扇出值作為是否保護(hù)變量的依據(jù),具有高扇出的位置通常是堆棧或棧指針,這些位置的錯(cuò)誤可能會(huì)導(dǎo)致程序的崩潰.因此,我們選取了指令中變量是否是全局變量和變量的扇出值這兩個(gè)特征.

5 基于機(jī)器學(xué)習(xí)的指令SDC脆弱性分析

5.1 脆弱性分析流程

基于第4節(jié)提取的影響SDC脆弱性的指令特征,本文設(shè)計(jì)的指令SDC脆弱性分析流程如圖 7所示.主要分為數(shù)據(jù)集構(gòu)建和指令脆弱性預(yù)測(cè)兩個(gè)部分.下面對(duì)這兩個(gè)部分分別進(jìn)行介紹.

5.2 數(shù)據(jù)集構(gòu)建

首先,將訓(xùn)練程序和測(cè)試程序編譯為IR中間代碼;然后通過故障注入實(shí)驗(yàn)獲取IR中間代碼中指令的SDC脆弱性;最后,第4節(jié)的指令特征分析與提取部分為指令脆弱性分析所需要的指令特征庫的構(gòu)建提供了依據(jù),通過編寫LLVM流程對(duì)IR進(jìn)行分析提取我們關(guān)注的指令特征.

5.3 預(yù)測(cè)模型

文獻(xiàn)[12]中使用分類回歸樹模型對(duì)指令的SDC脆弱性進(jìn)行預(yù)測(cè),該模型在處理各類別樣本數(shù)量不一致的情況時(shí),信息的增益會(huì)偏向具有更多數(shù)值的特征,且這種模型忽略了數(shù)據(jù)集特征之間的相關(guān)性.在我們的實(shí)驗(yàn)中,需要在程序編譯的過程中直接獲取我們需要的指令特征并通過訓(xùn)練出的SDC脆弱性預(yù)測(cè)模型直接得出指令的脆弱性從而指導(dǎo)程序檢測(cè)機(jī)制的部署.因此,采用的訓(xùn)練模型需要對(duì)新樣本有較高的適應(yīng)能力,考慮到支持向量機(jī)模型較高的泛化性能且不需要調(diào)節(jié)過多的參數(shù),本文采用支持向量機(jī)(Support Vector Machine,SVM)來訓(xùn)練我們的脆弱性預(yù)測(cè)模型.

圖7 指令SDC脆弱分析流程圖Fig.7 Flow chart of instruction SDC vulnerability analysis

6 實(shí)驗(yàn)與結(jié)果分析

6.1 實(shí)驗(yàn)方法

為了驗(yàn)證所提出方法的有效性,本文進(jìn)行了相關(guān)的實(shí)驗(yàn).實(shí)驗(yàn)使用的環(huán)境如下:操作系統(tǒng)Ubuntu 16.04.1,CPU為Intel Core i5-4200H,內(nèi)存為8GB.我們使用LLVM 3.4來編譯源程序得到IR中間代碼,使用LLFI工具對(duì)其進(jìn)行故障注入實(shí)驗(yàn).考慮到多處理器平臺(tái)沒有在星上得到廣泛應(yīng)用且成本較高,而我們的容錯(cuò)系統(tǒng)主要應(yīng)用于空間的嵌入式系統(tǒng),本文僅討論單線程實(shí)現(xiàn)的程序.我們使用的基準(zhǔn)程序集為嵌入式基準(zhǔn)測(cè)試集合MiBench,圖 1中給出的程序?yàn)橛?xùn)練程序,選取qsort、dijkstra、susan作為測(cè)試程序來比較我們的方法的具體效果.

6.2 實(shí)驗(yàn)結(jié)果

本文從準(zhǔn)確率、相關(guān)性、時(shí)間代價(jià)3個(gè)方面來評(píng)價(jià)我們的基于機(jī)器學(xué)習(xí)的SDC脆弱性分析方法.

和之前的工作一樣,用得到的程序的SDC脆弱性來衡量脆弱性分析方法的準(zhǔn)確率[12,17].在我們的方法中,程序的SDC脆弱性的計(jì)算過程如式(4)所示,PSDC(Ii)為我們的預(yù)測(cè)模型預(yù)測(cè)出的指令I(lǐng)i的SDC脆弱性,Ni為指令I(lǐng)i的動(dòng)態(tài)執(zhí)行數(shù),NP為整個(gè)程序的動(dòng)態(tài)指令數(shù).通過將我們的方法得到的SDCrate、文獻(xiàn)[12]中的SDCTune方法得到的SDCrate、文獻(xiàn)[17]中的ePVF方法得到的程序SDC錯(cuò)誤率(通過崩潰模型計(jì)算得到)以及故障注入方法得到的程序SDC錯(cuò)誤率進(jìn)行對(duì)比,結(jié)果如圖 8所示.

(4)

圖8 準(zhǔn)確率比較Fig.8 Comparison of accuracy rate

由圖 8可知,三個(gè)測(cè)試程序的平均SDC脆弱性為21.3%,而通過故障注入實(shí)驗(yàn)得到的平均SDC脆弱性為19.1%.本文預(yù)測(cè)的SDCrate會(huì)略高于故障注入實(shí)驗(yàn)得到的值即真實(shí)的程序發(fā)生SDC錯(cuò)誤的概率.而ePVF方法是通過計(jì)算程序崩潰的概率反過來推算程序的SDC錯(cuò)誤率,會(huì)高出準(zhǔn)確的SDC錯(cuò)誤率,得到的平均脆弱性達(dá)到了23.8%.通過分析通過我們的方法得到的預(yù)測(cè)的結(jié)果,產(chǎn)生誤差的原因是故障在傳播的過程會(huì)被程序特定的性質(zhì)屏蔽,如浮點(diǎn)運(yùn)算中的正確性檢查、不會(huì)影響程序輸出的分支指令等.

相關(guān)性用來衡量我們的預(yù)測(cè)模型預(yù)測(cè)出的指令SDC脆弱性和實(shí)際由故障注入得到的準(zhǔn)確值之間的相關(guān)性.在對(duì)程序進(jìn)行選擇性保護(hù)時(shí)只需選擇相對(duì)較脆弱的指令,不需要對(duì)其脆弱性進(jìn)行完全準(zhǔn)確的預(yù)測(cè),因此相關(guān)性是衡量預(yù)測(cè)結(jié)果的重要指標(biāo).時(shí)間代價(jià)用來衡量特征提取所需要的時(shí)間.本文比較了本方法、SDCTune方法、故障注入方法以及ePVF方法在相同輸入下的預(yù)測(cè)相關(guān)性和時(shí)間代價(jià),如表 5所示.其中,由于故障注入方法得到的SDC脆弱性為準(zhǔn)確值,所以其相關(guān)性為1.同時(shí),由于故障注入方法的時(shí)間過長,在時(shí)間代價(jià)的比較中將其忽略.

表5 相關(guān)性和時(shí)間代價(jià)
Table 5 Comparison of correlation and time spent

程 序相關(guān)性時(shí)間代價(jià)/s本文方法SDCTuneFIePVF本文方法SDCTuneFIePVFqsort0.9120.84210.8035642-49dijkstra0.9030.87910.812132105-126susan0.9260.83710.793249204-237

由表5可知,本文的方法平均預(yù)測(cè)相關(guān)性為0.914,高于SDCTune方法的0.853以及ePVF方法的0.803.與ePVF方法相比,時(shí)間代價(jià)高出了6.1%,但我們的方法的預(yù)測(cè)相關(guān)性要高于ePVF方法.因?yàn)楸疚膶?duì)程序中所有的指令進(jìn)行了特征提取并預(yù)測(cè)了脆弱性,而SDCTune方法僅考慮了存儲(chǔ)指令和比較指令,其余指令是通過工具進(jìn)行依賴關(guān)系分析得到粗略的估計(jì),所以我們的方法在預(yù)測(cè)相關(guān)關(guān)系方面會(huì)優(yōu)于SDCTune方法.由于SDCTune方法僅需要對(duì)程序中的存儲(chǔ)和比較指令進(jìn)行特征提取,所需要的時(shí)間代價(jià)較小.我們的方法在特征提取是比它增加了平均24.5%的時(shí)間,但我們的方法不需要進(jìn)行額外的依賴關(guān)系分析,可以在程序編譯時(shí)完成指令特征的提取.

7 結(jié) 論

針對(duì)故障注入方法分析指令SDC脆弱性需要耗費(fèi)較大的代價(jià),本文提出了一種基于機(jī)器學(xué)習(xí)的指令脆弱性分析方法.該方法利用程序分析技術(shù)在程序編譯的中間代碼階段提取反映指令脆弱性的特征作為特征向量,訓(xùn)練基于支持向量機(jī)的指令脆弱性預(yù)測(cè)模型,定量的對(duì)指令的脆弱性進(jìn)行了分析,同時(shí)也通過實(shí)驗(yàn)說明了該方法的有效性.該方法可以得到程序中較為脆弱的指令,對(duì)研究檢測(cè)機(jī)制的部署以及檢測(cè)代價(jià)的優(yōu)化等內(nèi)容有重要的意義.

[1] Baumann R.Soft errors in commercial semiconductor technology:overview and scaling trends[C].IEEE 2002 Reliability Physics Tutorial Notes,Reliability Fundamentals,2002.

[2] Feng S,Gupta S,Ansari A,et al.Shoestring:probabilistic soft error reliability on the cheap[C].International Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS),2010:385-396.

[3] Wang N J,Patel S J.ReStore:symptom-based soft error detection in microprocessors[J].IEEE Transactions on Dependable and Secure Computing(TDSC),2006,3(3):188-201.

[4] Hari S K S,Adve S V,Naeimi H.Low-cost program-level detectors for reducing silent data corruptions[C].IEEE/IFIP International Conference on Dependable Systems and Networks(DSN),2012:1-12.

[5] Hari S K S,Adve S V,Naeimi H,et al.Relyzer:exploiting application-level fault equivalence to analyze application resiliency to transient faults[J].Computer Architecture News(CAN),2012,40(1):123-134.

[6] Li J,Tan Q.SmartInjector:exploiting intelligent fault injection for SDC rate analysis[C].IEEE International Symposium on Defect and Fault Tolerance in Vlsi and Nanotechnology Systems(DFT),2013:236-242.

[7] Xu X, Li M L. Understanding soft error propagation using efficient vulnerability-driven fault injection[C]. IEEE/IFIP International Conference on Dependable Systems and Networks(DSN),2012:1-12.

[8] Yang Xue-jun,Gao Long.Error flow model:modeling and analysis of software propagating hardware faults[J].Journal of Software,2007,18(4):808-820.

[9] Pattabiraman K,Nakka N,Kalbarczyk Z,et al.SymPLFIED:symbolic program-level fault injection and error detection framework[J].Computers IEEE Transactions on(TC),2013,62(11):2292-2307.

[10] Ma Jun-chi,Wang Yun,Cai Zhen-bo,et al.An approach for identifying SDC-causing instructions by fault propagation analysis[J].Journal of Computer Research and Development,2016,53(9):1943-1952.

[11] Bronevetsky G,de Supinski B,Schulz M.A foundation for the accurate prediction of the soft error vulnerability of scientific applications[R].Lawrence Livermore National Laboratory(LLNL),Livermore,CA,2009.

[12] Lu Q,Pattabiraman K,Gupta M S,et al.SDCTune:a model for predicting the SDC proneness of an application for configurable protection[C].International Conference on Compilers,Architecture and Synthesis for Embedded Systems(CASES),2014:1-10.

[13] Shivakumar P,Kistler M,Keckler S W,et al.Modeling the effect of technology trends on the soft error rate of combinational logic[C].IEEE/IFIP International Conference on Dependable Systems and Network(DSN),2002:389-398.

[14] Wang H,Wang H,Jin Z.Bipartite graph-based control flow checking for COTS-based small satellites[J].Chinese Journal of Aeronautics(CJA),2015,28(3):883-893.

[15] Wei J,Thomas A,Li G,et al.Quantifying the accuracy of high-level fault injection techniques for hardware faults[C].IEEE/IFIP International Conference on Dependable Systems and Networks(DSN),2014:375-382.

[16] Weiser M.Program slicing[C].International Conference on Software Engineering(ICSE),1981:439-449.

[17] Fang B,Lu Q,Pattabiraman K,et al.ePVF:an enhanced program vulnerability factor methodology for cross-layer resilience analysis[C].IEEE/IFIP International Conference on Dependable Systems and Networks(DSN),2016:168-179.

[18] Pattabiraman K,Kalbarczyk Z,Iyer R K.Application-based metrics for strategic placement of detectors[C].Pacific Rim International Symposium on Dependable Computing,IEEE Computer Society(PRDC),2005:75-82.

附中文參考文獻(xiàn)：

[8] 楊學(xué)軍,高 瓏.錯(cuò)誤流模型:硬件故障的軟件傳播建模與分析 [J].軟件學(xué)報(bào),2007,18(4):808-820.

[10] 馬駿馳,汪 蕓,蔡震波,等.基于錯(cuò)誤傳播分析的SDC脆弱指令識(shí)別方法 [J].計(jì)算機(jī)研究與發(fā)展,2016,53(9):1943-1952.