程 義,莊 毅,曹子寧

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

1 引 言

隨著嵌入式應(yīng)用程序領(lǐng)域內(nèi)技術(shù)的迅速發(fā)展,計(jì)算機(jī)應(yīng)用程序在復(fù)雜性和規(guī)模都在不斷增長(zhǎng).同時(shí),嚴(yán)格的功率限制和元器件冗余的減少促使半導(dǎo)體行業(yè)從業(yè)者在設(shè)計(jì)集成電路時(shí)繼續(xù)精簡(jiǎn)結(jié)構(gòu)降低電壓.這種趨勢(shì)一方面使硬件元器件高度集成化,另一方面提高了其對(duì)外部硬件故障的敏感性,如輻射效應(yīng)或電磁干擾等[1]引發(fā)的硬件故障.這對(duì)嵌入式系統(tǒng)的設(shè)計(jì)和開(kāi)發(fā)提出了新的挑戰(zhàn).

航空航天領(lǐng)域的工作環(huán)境中存在著大量的高能粒子,這些高能粒子會(huì)引發(fā)一系列的單粒子效應(yīng),影響相關(guān)計(jì)算機(jī)設(shè)備的正常運(yùn)行.單粒子效應(yīng)(Single Event Effect)是指高能帶電粒子穿過(guò)微電子器件的靈敏結(jié)構(gòu)時(shí),造成器件邏輯狀態(tài)的非正常改變或器件損壞的現(xiàn)象[2].單粒子翻轉(zhuǎn)是高能帶電粒子使元器件的邏輯狀態(tài)發(fā)生翻轉(zhuǎn)的一種單粒子效應(yīng)[3].

為了提高嵌入式系統(tǒng)的可靠性,在設(shè)計(jì)時(shí)就需要對(duì)系統(tǒng)中潛在故障進(jìn)行分析并采取一系列手段對(duì)相應(yīng)的故障進(jìn)行檢測(cè)、恢復(fù)或補(bǔ)償.隨機(jī)或永久性的硬件故障都會(huì)對(duì)系統(tǒng)運(yùn)行的各個(gè)層面產(chǎn)生不同的影響.相較于永久性的硬件故障,計(jì)算機(jī)硬件的瞬時(shí)故障存在時(shí)間和空間的隨機(jī)性和不可預(yù)測(cè)性.這使得該類瞬時(shí)故障問(wèn)題更加難以應(yīng)對(duì),并提高了應(yīng)對(duì)瞬時(shí)故障能力在設(shè)計(jì)可靠性系統(tǒng)時(shí)的重要性.故障注入技術(shù)是現(xiàn)行可靠性評(píng)估技術(shù)的主要方法之一,被廣泛應(yīng)用在各個(gè)領(lǐng)域[4-6].相關(guān)安全標(biāo)準(zhǔn)(如ISO 26262[7])也強(qiáng)烈建議在驗(yàn)證嵌入式系統(tǒng)的可靠性時(shí)應(yīng)用故障注入技術(shù).主流的故障注入技術(shù)按照所注入故障的方式分為硬件故障注入和軟件故障注入兩類[8].硬件故障注入技術(shù)存在成本高、自動(dòng)化水平低等缺陷;而軟件故障注入技術(shù),不僅可以較好地模擬硬件故障,而且可以對(duì)應(yīng)用程序產(chǎn)生直接影響,更受到研究者與開(kāi)發(fā)人員的青睞.

故障按照對(duì)應(yīng)用程序產(chǎn)生的影響分為:控制流錯(cuò)誤和數(shù)據(jù)流錯(cuò)誤兩大類[5].目前這兩種故障的軟件注入技術(shù)都得到了長(zhǎng)足研究和廣泛應(yīng)用.但是同時(shí)兼顧控制流錯(cuò)誤和數(shù)據(jù)流錯(cuò)誤的軟件故障注入研究和工具較少.另一方面?zhèn)鹘y(tǒng)的故障注入工具注入故障的方案較為簡(jiǎn)單,一般是僅在某條指令處隨機(jī)的注入單粒子翻轉(zhuǎn)故障[2,9,10].事實(shí)上這些注入的故障不一定能引發(fā)程序的控制流錯(cuò)誤和數(shù)據(jù)流錯(cuò)誤,有些甚至屬于無(wú)效故障,即故障注入前后程序運(yùn)行和執(zhí)行結(jié)果沒(méi)有發(fā)生變化.因此設(shè)計(jì)能夠同時(shí)兼顧控制流錯(cuò)誤和數(shù)據(jù)流錯(cuò)誤,且能夠通過(guò)智能決策注入有效故障的故障注入工具成為當(dāng)下亟需探索的研究方向.

本文主要貢獻(xiàn)如下:在通用嵌入式計(jì)算機(jī)硬件架構(gòu)的基礎(chǔ)上,討論了主要硬件器件能否產(chǎn)生控制流和數(shù)據(jù)流錯(cuò)誤及其對(duì)程序運(yùn)行的影響;并在此基礎(chǔ)上提出了一種基于隨機(jī)森林的故障注入方法,設(shè)計(jì)并且實(shí)現(xiàn)了該系統(tǒng).該系統(tǒng)使用隨機(jī)森林方法,根據(jù)被注入程序的指令的各項(xiàng)特征,對(duì)程序指令各個(gè)器件發(fā)生單粒子翻轉(zhuǎn)故障的敏感性預(yù)測(cè),生成故障序列,最后在程序運(yùn)行時(shí)根據(jù)故障序列,對(duì)程序進(jìn)行自動(dòng)故障注入.相比已有方法,本文所提出的基于隨機(jī)森林的單粒子翻轉(zhuǎn)模擬軟件故障注入方法具有實(shí)施成本低、自動(dòng)化水平高、故障覆蓋率高、故障有效率高等優(yōu)點(diǎn).相關(guān)實(shí)驗(yàn)證明了本文所提出方法的有效性和優(yōu)越性.

2 相關(guān)工作

目前程序故障注入的方法主要分為兩大類:硬件故障注入與軟件故障注入.其中軟件故障注入還分為傳統(tǒng)的軟件故障注入和基于機(jī)器學(xué)習(xí)的軟件故障注入.

2.1 硬件故障注入

基于硬件的故障注入方法通常在附加硬件設(shè)備的輔助下,將故障注入到系統(tǒng)中[8].這類故障注入的方法往往需要定制的硬件設(shè)備,具有實(shí)施成本高、設(shè)備特異性、耗時(shí)時(shí)間長(zhǎng)、無(wú)法自動(dòng)化、結(jié)果難觀察、降低硬件使用壽命等問(wèn)題.現(xiàn)階段的主要研究工作是通過(guò)一些硬件調(diào)試設(shè)備對(duì)硬件設(shè)備進(jìn)行故障注入,或者通過(guò)軟件仿真模擬硬件設(shè)備的方式來(lái)實(shí)現(xiàn)自動(dòng)化故障注入.Zhang等人提出了基于管道的故障注入技術(shù)[11],通過(guò)該技術(shù)可以加快故障注入的流程,從而能夠?qū)赟RAM的FPGA中發(fā)生的單粒子翻轉(zhuǎn)故障進(jìn)行模擬.Bhattacharya提出一種基于FPGA的故障仿真技術(shù)[12],可在設(shè)計(jì)的早期階段設(shè)計(jì)和開(kāi)發(fā)測(cè)試資源,驗(yàn)證測(cè)試臺(tái)以及互連電路.Khosrowjerdi等人提出了一種虛擬化故障注入方法[13],該方法集成了QEMU、GDB和LBTest,能夠自動(dòng)化的生成故障并注入到嵌入式系統(tǒng)中.Coelho等人設(shè)計(jì)了一種名為NETFI-2的故障注入平臺(tái)[14],該故障注入平臺(tái)能夠在FPGA中模擬單粒子翻轉(zhuǎn)故障并注入到集成電路中.Moorthi基于FPGA設(shè)計(jì)了一套可編程的硬件故障注入框架[15],使用該框架可以將模擬生成單粒子翻轉(zhuǎn)故障,并將該故障注入到指定的元器件.這些硬件故障注入方法可以較好的模擬單粒子翻轉(zhuǎn)故障現(xiàn)場(chǎng),但是存在故障注入方案泛化性差、實(shí)施成本高和單次故障注入開(kāi)銷(xiāo)大等缺點(diǎn).

2.2 傳統(tǒng)的軟件故障注入

除了用物理手段進(jìn)行故障注入的方法,基于軟件的故障注入技術(shù)也是一類常見(jiàn)的故障注入技術(shù).軟件故障注入通過(guò)特定的程序?qū)ο到y(tǒng)軟件、硬件錯(cuò)誤狀態(tài)進(jìn)行仿真[16].較之硬件故障注入方法,軟件方法具有實(shí)施成本低、能夠針對(duì)特定的程序、易于觀察故障注入效果、可以對(duì)注入故障進(jìn)行追蹤、可特定針對(duì)控制流或者數(shù)據(jù)流錯(cuò)誤進(jìn)行故障注入、故障注入開(kāi)銷(xiāo)小的特點(diǎn).現(xiàn)有的研究工作一般針對(duì)數(shù)據(jù)流或者控制流錯(cuò)誤,來(lái)研究發(fā)生相應(yīng)故障對(duì)程序的影響,進(jìn)而提出了相應(yīng)故障的容錯(cuò)算法.如Porpodas設(shè)計(jì)了一種基于時(shí)序的故障注入工具ZOFI[17],這種故障注入工具能夠模擬發(fā)生在寄存器上的瞬態(tài)故障并注入.Ahmad等設(shè)計(jì)了一種純軟件的故障注入技術(shù)LDSFI[18],該技術(shù)可以在程序運(yùn)行時(shí)自動(dòng)的將單粒子翻轉(zhuǎn)故障注入到二進(jìn)制代碼中.Osinski等人通過(guò)考慮微體系結(jié)構(gòu)和應(yīng)用程序級(jí)別的單個(gè)故障的假設(shè)[19],討論分析了不同策略下注入控制流錯(cuò)誤以及相應(yīng)的差異.Zhang等人基于LLFI設(shè)計(jì)了一種模擬分析瞬時(shí)故障的方法[20],并使用該方法研究了指令SDC脆弱性.這些軟件故障注入方法在故障注入時(shí)一般采用隨機(jī)的方式,極易注入無(wú)效故障.并且這些故障注入方法由于使用的場(chǎng)景僅限于數(shù)據(jù)流或者控制流錯(cuò)誤,存在泛用性較差等問(wèn)題.

2.3 基于機(jī)器學(xué)習(xí)的軟件故障注入

為了減少軟件故障注入的成本和增加故障注入技術(shù)的泛用性,一些機(jī)器學(xué)習(xí)算法被運(yùn)用到了軟件故障注入技術(shù)中.如Yang等人基于SVM提出了PVInsiden[21],該技術(shù)使用SVM來(lái)識(shí)別指令是否是易導(dǎo)致數(shù)據(jù)靜默錯(cuò)誤(Silent Data Corruption,SDC)的指令,但是這種方案仍然只適用于數(shù)據(jù)流錯(cuò)誤,對(duì)控制流錯(cuò)誤無(wú)效.Jha等人提出了一種基于機(jī)器學(xué)習(xí)的故障注入引擎DriverFI[22],能夠挖掘自動(dòng)駕駛汽車(chē)的影音系統(tǒng)的安全性和故障.該引擎主要針對(duì)內(nèi)存中的單粒子翻轉(zhuǎn)引發(fā)的數(shù)據(jù)流錯(cuò)誤,不能注入CPU中器件的單粒子翻轉(zhuǎn)故障和一些控制流錯(cuò)誤.

2.4 小結(jié)

綜上所述,基于硬件故障注入方法雖然具有貼近單粒子翻轉(zhuǎn)現(xiàn)場(chǎng)優(yōu)點(diǎn),但存在成本高,注入位置隨機(jī)、不能指定程序進(jìn)行故障注入,難以觀察故障注入的結(jié)果、易對(duì)硬件造成損壞等問(wèn)題.傳統(tǒng)的基于軟件的故障注入方法存在注入故障的有效性難以保證,并且只針對(duì)控制流錯(cuò)誤或數(shù)據(jù)流錯(cuò)誤,存在故障覆蓋率低等問(wèn)題.但是基于軟件的故障注入技術(shù)實(shí)施成本低,能夠指定注入故障的程序,還具有易于追蹤注入的故障、觀察注入故障的結(jié)果等優(yōu)點(diǎn).而基于機(jī)器學(xué)習(xí)的故障注入技術(shù)能夠有效的對(duì)故障空間進(jìn)行剪枝,增加注入故障的有效性,但是目前缺少能夠同時(shí)兼顧數(shù)據(jù)流和控制流的故障注入技術(shù).本文在使用傳統(tǒng)的故障注入技術(shù)注入形成的原始故障集的基礎(chǔ)上,使用隨機(jī)森林算法生成指令脆弱性預(yù)測(cè)模型,使用該模型能夠預(yù)測(cè)程序指令對(duì)各個(gè)部件單粒子翻轉(zhuǎn)的脆弱性;進(jìn)而在此基礎(chǔ)上形成被注入故障程序的故障序列,即故障注入時(shí)在指令對(duì)應(yīng)的故障序列中選取較為脆弱的故障進(jìn)行故障注入,提高故障注入的有效性.

3 單粒子翻轉(zhuǎn)故障

硬件級(jí)別的單粒子翻轉(zhuǎn)故障會(huì)影響程序行為,例如內(nèi)存或者寄存器中的數(shù)據(jù)錯(cuò)誤會(huì)影響程序的控制流和數(shù)據(jù)流錯(cuò)誤.分析計(jì)算機(jī)的體系結(jié)構(gòu),單粒子翻轉(zhuǎn)故障可以在系統(tǒng)中的任何抽象層次傳播.星載、機(jī)載等嵌入式計(jì)算機(jī)的硬件架構(gòu)如圖1[23]所示.

圖1 星載嵌入式計(jì)算機(jī)通用系統(tǒng)架構(gòu)

單粒子翻轉(zhuǎn)故障主要發(fā)生在處理器和存儲(chǔ)部件或者非標(biāo)準(zhǔn)的設(shè)備(如搖桿、打印機(jī))中[5],其他的硬件器件發(fā)生單粒子翻轉(zhuǎn)的概率較低.其他部件的單粒子故障最終都可以映射為處理器和內(nèi)存中的單粒子翻轉(zhuǎn)故障.按照故障發(fā)生的硬件位置,單粒子翻轉(zhuǎn)故障可以分為處理器故障、存儲(chǔ)器故障等.其中處理器故障又可以劃分為寄存器和運(yùn)算單元故障,而存儲(chǔ)故障又可以分為內(nèi)存故障和外存故障.表1總結(jié)并描述了硬件故障類型,并列舉了對(duì)應(yīng)的數(shù)據(jù)/控制流錯(cuò)誤類型.由于大部分外部設(shè)備通過(guò)總線傳輸數(shù)據(jù),因此將這些外部設(shè)備的故障歸類為總線錯(cuò)誤.從表1中我們不難看出指令譯碼器、內(nèi)存、外存中同時(shí)存在控制流錯(cuò)誤和數(shù)據(jù)流錯(cuò)誤.

表1 硬件故障類型

指令譯碼器負(fù)責(zé)將復(fù)雜的機(jī)器語(yǔ)言指令解譯成運(yùn)算邏輯單元(ALU)和寄存器能夠理解的格式即相應(yīng)的電氣信號(hào).因此當(dāng)指令譯碼器中發(fā)生單粒子翻轉(zhuǎn)故障時(shí),可能導(dǎo)致非跳轉(zhuǎn)指令翻轉(zhuǎn)為跳轉(zhuǎn)指令,繼而引起程序跳出正常的執(zhí)行順序,表現(xiàn)為控制流錯(cuò)誤;當(dāng)指令譯碼器遇到跳轉(zhuǎn)指令,跳轉(zhuǎn)的目的地址因?yàn)槲环D(zhuǎn)而程序跳出正常的執(zhí)行順序,也表現(xiàn)為控制流錯(cuò)誤.一般以上兩種情況較為少見(jiàn),發(fā)生在該元件中的更多的是數(shù)據(jù)流錯(cuò)誤.

發(fā)生在內(nèi)存中控制流錯(cuò)誤主要是發(fā)生在代碼區(qū).與指令譯碼器中的類似,出現(xiàn)非跳轉(zhuǎn)指令翻轉(zhuǎn)為跳轉(zhuǎn)指令和跳轉(zhuǎn)指令的目的地址發(fā)生翻轉(zhuǎn),而表現(xiàn)出的控制流錯(cuò)誤.該類錯(cuò)誤屬于瞬態(tài)錯(cuò)誤,當(dāng)重新讀入程序時(shí),即可糾正該類錯(cuò)誤.外存中控制流錯(cuò)誤出現(xiàn)的原因與內(nèi)存中出現(xiàn)的原因一致.此外發(fā)生在內(nèi)存和外存中的位翻轉(zhuǎn)而導(dǎo)致的程序故障是持續(xù)性的,這種持續(xù)性體現(xiàn)在內(nèi)存和外存中的單粒子翻轉(zhuǎn)故障不像是指令寄存器、指令譯碼器中的故障屬于“一次性”的:指令寄存器、指令譯碼器中的單粒子翻轉(zhuǎn)不會(huì)影響到下次執(zhí)行本條指令.但是內(nèi)存和外存中的單粒子翻轉(zhuǎn)故障下次執(zhí)行同樣的指令,相同的故障仍會(huì)發(fā)生.這是因?yàn)閮?nèi)外存中保存的指令一旦發(fā)生單粒子翻轉(zhuǎn),程序執(zhí)行時(shí)在取指令階段讀取到的指令都是翻轉(zhuǎn)后的指令.這種持續(xù)性的故障可以通過(guò)重新載入/編譯程序來(lái)解決.

下面以圖2中的匯編代碼為例,分析各個(gè)硬件設(shè)備可能導(dǎo)致的數(shù)據(jù)流錯(cuò)誤:1)若在指令寄存器保存指令2時(shí)發(fā)生單粒子翻轉(zhuǎn),翻轉(zhuǎn)后的機(jī)器碼為:8b 45 fb,則對(duì)應(yīng)的匯編代碼為:mov-0x5(%rbp),%eax,則寄存器eax中的數(shù)據(jù)保存向錯(cuò)誤的內(nèi)存地址,發(fā)生數(shù)據(jù)流錯(cuò)誤;2)指令譯碼器發(fā)生數(shù)據(jù)流錯(cuò)誤的情形和指令寄存器類似,但是故障發(fā)生在指令譯碼時(shí),指令譯碼器的單粒子翻轉(zhuǎn)故障可以等效為指令寄存器中的指令在同位置發(fā)生單粒子翻轉(zhuǎn)故障;3)操作控制器主要負(fù)責(zé)決策寄存器之間建立數(shù)據(jù)通路的任務(wù),若在執(zhí)行指令1時(shí)發(fā)生單粒子翻轉(zhuǎn),本該保存到寄存器edx中的數(shù)據(jù)保存到其他寄存器中,則會(huì)影響到指令3的執(zhí)行結(jié)果造成數(shù)據(jù)流錯(cuò)誤,可以等效為指令寄存器中的指令在同一位置發(fā)生單粒子翻轉(zhuǎn)故障;4)若執(zhí)行指令2時(shí),CPU中的寄存器edx發(fā)生單粒子翻轉(zhuǎn)故障導(dǎo)致數(shù)據(jù)流錯(cuò)誤,會(huì)對(duì)指令3執(zhí)行的數(shù)據(jù)結(jié)果為錯(cuò)誤結(jié)果;5)邏輯運(yùn)算單元、總線單元、數(shù)據(jù)高速緩存中發(fā)生單粒子翻轉(zhuǎn)故障,都是通過(guò)寄存器簡(jiǎn)介造成數(shù)據(jù)流錯(cuò)誤,他們中數(shù)據(jù)的來(lái)源和去向都是寄存器,一般可以視為寄存器單粒子翻轉(zhuǎn)故障;6)指令4屬于訪存指令,通過(guò)變址寄存器rbp和偏移地址-0x14訪問(wèn)內(nèi)存,并將內(nèi)存中的數(shù)據(jù)存儲(chǔ)到寄存器eax中,若執(zhí)行指令4時(shí),要訪問(wèn)的內(nèi)存發(fā)生單粒子翻轉(zhuǎn)故障,則存儲(chǔ)到寄存器eax中的數(shù)據(jù)就出現(xiàn)錯(cuò)誤,導(dǎo)致數(shù)據(jù)流錯(cuò)誤;7)外存中的單粒子翻轉(zhuǎn)故障更多的是影響保存在外存中的程序,如1)指令2翻轉(zhuǎn)為8b 45 fb,也會(huì)造成數(shù)據(jù)流錯(cuò)誤,可以視為程序載入內(nèi)存時(shí)發(fā)生在內(nèi)存中的單粒子翻轉(zhuǎn)故障.

圖2 x86-64匯編代碼示例

下面分析圖2中可能發(fā)生的控制流錯(cuò)誤:1)程序計(jì)數(shù)器中保存的當(dāng)前執(zhí)行指令的下一個(gè)指令,如執(zhí)行指令1時(shí),此時(shí)程序計(jì)數(shù)器中的內(nèi)容應(yīng)為:0x1004010b0,即為指令2的內(nèi)存地址,若程序計(jì)數(shù)器發(fā)生單粒子翻轉(zhuǎn)故障,使得程序計(jì)數(shù)器中的內(nèi)容翻轉(zhuǎn)為0x1004010b3,則執(zhí)行完指令1后程序執(zhí)行指令3,程序出現(xiàn)控制流錯(cuò)誤;2)指令寄存器、指令譯碼器發(fā)生控制流錯(cuò)誤,通常是單粒子翻轉(zhuǎn)故障發(fā)生在跳轉(zhuǎn)指令使得跳轉(zhuǎn)指令變?yōu)槠渌噶?或者更改程序跳轉(zhuǎn)的目的地址,使得程序發(fā)生控制流錯(cuò)誤,比如指令9發(fā)生單粒子翻轉(zhuǎn)故障je指令變成jne指令或者跳轉(zhuǎn)的目的地址變?yōu)?x1004010ae,可以等效為指令寄存器中的指令在同位置發(fā)生單粒子翻轉(zhuǎn)故障;3)內(nèi)存、外存中的控制流錯(cuò)誤與指令寄存器、指令譯碼器類似,都是由于位翻轉(zhuǎn)瞬時(shí)故障發(fā)生在跳轉(zhuǎn)指令或者更改目的地址時(shí),使得程序發(fā)生控制流錯(cuò)誤.

從上面可以看出各類硬件的單粒子翻轉(zhuǎn)故障都可以等效的看作寄存器單粒子翻轉(zhuǎn)故障和內(nèi)存單粒子翻轉(zhuǎn)故障;并且同一指令發(fā)生單粒子翻轉(zhuǎn)的硬件器件不同,發(fā)生在同一硬件器件上翻轉(zhuǎn)的位置不同對(duì)程序造成的影響也不同;同時(shí)單粒子翻轉(zhuǎn)故障注入時(shí)需要的參數(shù)為翻轉(zhuǎn)的部件和翻轉(zhuǎn)的位置.因此在設(shè)計(jì)故障注入系統(tǒng)的故障注入決策時(shí),必須掌握被注入故障的指令對(duì)器件發(fā)生單粒子翻轉(zhuǎn)故障和翻轉(zhuǎn)位置的敏感性,以及被注入故障的指令發(fā)生數(shù)據(jù)流/控制流錯(cuò)誤與注入故障器件和翻轉(zhuǎn)位置的相關(guān)性,以達(dá)到單粒子翻轉(zhuǎn)故障的高效注入.

4 指令單粒子翻轉(zhuǎn)脆弱性特征提取

從第3節(jié)可知在某些指令處注入寄存器單粒子翻轉(zhuǎn)故障不會(huì)引發(fā)程序故障,有些指令對(duì)注入的內(nèi)存單粒子翻轉(zhuǎn)故障不敏感.因此研究指令單粒子翻轉(zhuǎn)脆弱性,是提高故障注入有效性的關(guān)鍵.為了研究指令對(duì)器件發(fā)生單粒子翻轉(zhuǎn)故障和翻轉(zhuǎn)位置的敏感性,以及被注入故障的指令發(fā)生數(shù)據(jù)流/控制流錯(cuò)誤與注入故障器件和翻轉(zhuǎn)位置的相關(guān)性,我們定義指令單粒子翻轉(zhuǎn)的脆弱性為發(fā)生單粒子翻轉(zhuǎn)后導(dǎo)致程序發(fā)生故障的概率,指令數(shù)據(jù)流脆弱性為發(fā)生單粒子翻轉(zhuǎn)后導(dǎo)致程序發(fā)生數(shù)據(jù)流錯(cuò)誤的概率,指令控制流脆弱性為發(fā)生單粒子翻轉(zhuǎn)后導(dǎo)致程序發(fā)生控制流錯(cuò)誤的概率.為了注入故障的有效性,必須在故障注入時(shí)根據(jù)注入故障的類別(數(shù)據(jù)流錯(cuò)誤、控制流錯(cuò)誤和兩者兼有之的故障),在相應(yīng)的脆弱性中選擇最高的故障選擇注入.下面對(duì)影響程序的脆弱性的指令特征進(jìn)行分析,為指令脆弱性的預(yù)測(cè)提供依據(jù).

4.1 寄存器單粒子翻轉(zhuǎn)脆弱性特征

本節(jié)討論發(fā)生在寄存器上的單粒子翻轉(zhuǎn).指令的單粒子翻轉(zhuǎn)脆弱性與下面幾個(gè)因素有關(guān):1)指令類型;2)指令操作數(shù)個(gè)數(shù);3)寄存器類型.首先指令類型與指令單粒子翻轉(zhuǎn)的數(shù)據(jù)流/控制流脆弱性相關(guān),在保持其他條件不變的情況下執(zhí)行周期長(zhǎng)的指令容易發(fā)生單粒子翻轉(zhuǎn),從而引發(fā)程序發(fā)生數(shù)據(jù)流/控制流錯(cuò)誤.跳轉(zhuǎn)指令與其他指令相比更不容易發(fā)生數(shù)據(jù)流錯(cuò)誤,這是因?yàn)樘D(zhuǎn)指令不使用數(shù)據(jù)寄存器,所以跳轉(zhuǎn)指令對(duì)通用寄存器中的單粒子翻轉(zhuǎn)瞬時(shí)故障有天然的屏蔽作用;其次指令操作數(shù)的個(gè)數(shù)與指令單粒子翻轉(zhuǎn)的數(shù)據(jù)流脆弱性相關(guān),在保持其他變量不變的情況下,操作數(shù)數(shù)量越多單粒子翻轉(zhuǎn)命中使用的寄存器的概率越高.最后,發(fā)生單粒子翻轉(zhuǎn)的寄存器類型與指令的數(shù)據(jù)流/控制流脆弱性相關(guān).在保持其他條件不變的情況下,顯然程序計(jì)數(shù)器發(fā)生單粒子翻轉(zhuǎn)故障時(shí)必然會(huì)導(dǎo)致控制流錯(cuò)誤.而指令寄存器較大概率導(dǎo)致控制流錯(cuò)誤.而一些通用寄存器由于使用頻率較低,即使發(fā)生單粒子翻轉(zhuǎn),也不一定會(huì)導(dǎo)致程序發(fā)生故障.

4.2 內(nèi)存單粒子翻轉(zhuǎn)脆弱性特征

本節(jié)討論了發(fā)生在內(nèi)存中的單粒子翻轉(zhuǎn).指令的單粒子翻轉(zhuǎn)脆弱性與下面幾個(gè)因素有關(guān):1)指令在程序執(zhí)行序列中的位置;2)發(fā)生單粒子翻轉(zhuǎn)的內(nèi)存地址.

指令有效故障空間是指:程序在執(zhí)行到對(duì)應(yīng)指令時(shí)發(fā)生單粒子翻轉(zhuǎn)會(huì)導(dǎo)致程序故障的內(nèi)存地址范圍.執(zhí)行到某些指令時(shí),部分內(nèi)存單元在本程序結(jié)束前都不會(huì)再使用,所以這片地址空間發(fā)生的單粒子翻轉(zhuǎn)故障不會(huì)引起程序故障.程序執(zhí)行序列中不同指令有效故障空間不同;發(fā)生在數(shù)據(jù)區(qū)、堆棧區(qū)的單粒子翻轉(zhuǎn)故障只會(huì)導(dǎo)致程序出現(xiàn)數(shù)據(jù)流錯(cuò)誤;代碼區(qū)的單粒子翻轉(zhuǎn)故障,僅在操作碼由非跳轉(zhuǎn)指令翻轉(zhuǎn)轉(zhuǎn)為跳轉(zhuǎn)指令或跳轉(zhuǎn)指令翻轉(zhuǎn)為非跳轉(zhuǎn)指令時(shí)才會(huì)造成控制流錯(cuò)誤.而指令操作碼在一個(gè)指令中占比較小,因此發(fā)生在代碼區(qū)的單粒子翻轉(zhuǎn)在多數(shù)情況下仍屬于數(shù)據(jù)流錯(cuò)誤.

5 基于隨機(jī)森林的故障注入框架

基于上述影響指令數(shù)據(jù)流/控制流的脆弱性的特征分析,本文提出了基于隨機(jī)森林的故障注入的基于隨機(jī)森林的故障注入框架.本文設(shè)計(jì)的基于隨機(jī)森林的故障注入框架整體流程如圖3所示.包含指令脆弱性預(yù)測(cè)模型建立、故障序列生成和故障注入3個(gè)部分.下面對(duì)3個(gè)部分分別進(jìn)行介紹.

圖3 基于隨機(jī)森林的故障注入

5.1 指令脆弱性預(yù)測(cè)模型

要使用隨機(jī)森林算法對(duì)指令的脆弱性進(jìn)行預(yù)測(cè),需要收集相關(guān)的特征和對(duì)應(yīng)的結(jié)果從而形成數(shù)據(jù)集.

首先使用傳統(tǒng)的故障注入程序針對(duì)目標(biāo)程序注入故障,然后收集故障結(jié)果和注入故障時(shí)執(zhí)行指令的相關(guān)特征,形成數(shù)據(jù)集;然后將數(shù)據(jù)集分為訓(xùn)練集和測(cè)試集,使用訓(xùn)練集建立基于隨機(jī)森林算法的故障注入指令脆弱性預(yù)測(cè)模型.隨機(jī)森林算法具有精度高、抗過(guò)擬合能力強(qiáng)、屬于非線性模型等優(yōu)點(diǎn)[24],本文采用隨機(jī)森林算法來(lái)訓(xùn)練得出指令脆弱性預(yù)測(cè)模型.

隨機(jī)森林算法是由Breiman等提出的[24],隨機(jī)森林是一種結(jié)構(gòu)簡(jiǎn)單的組合型分類算法,使用隨機(jī)的方式從多個(gè)分類回歸樹(shù)中構(gòu)建分類模型,并且分類回歸樹(shù)之間沒(méi)有關(guān)聯(lián).本文采用隨機(jī)森林算法來(lái)生成指令脆弱性預(yù)測(cè)模型.

5.2 生成故障序列

首先從被注入故障的程序中提取指令序列,然后對(duì)提取出的指令序列中的每一個(gè)指令提取相應(yīng)的指令特征,將提取的指令特征輸入到上一步中得到的基于隨機(jī)森林的指令脆弱性分類器中,從而預(yù)測(cè)處指令對(duì)發(fā)生在寄存器和內(nèi)存上的單粒子翻轉(zhuǎn)故障的脆弱性,最后根據(jù)每條指令對(duì)寄存器和內(nèi)存中的單粒子翻轉(zhuǎn)故障的脆弱性形成故障序列.故障序列由3個(gè)寄存器和1個(gè)地址范圍構(gòu)成,其中3個(gè)寄存器是使用隨機(jī)森林預(yù)測(cè)出的指令寄存器單粒子翻轉(zhuǎn)脆弱性最高的3個(gè)相關(guān)寄存器,地址范圍是使用隨機(jī)森林預(yù)測(cè)出的指令故障空間.與圖2中的指令序列對(duì)應(yīng)的故障序列如表2所示.

表2 指令(圖2)對(duì)應(yīng)的故障序列

5.3 故障注入

故障注入的步驟如下:

步驟1.提取被注入故障程序的指令序列;

步驟2.使用指令脆弱性預(yù)測(cè)模型預(yù)測(cè)出指令序列中的每一條指令的故障序列;

步驟3.根據(jù)用戶設(shè)定的單粒子翻轉(zhuǎn)故障的數(shù)量,從指令序列中隨機(jī)選取對(duì)應(yīng)數(shù)量的指令;

步驟4.使用gdb運(yùn)行被注入故障的程序,在選定的注入故障的指令處插入斷點(diǎn),當(dāng)程序運(yùn)行到插入的斷點(diǎn)時(shí),根據(jù)斷點(diǎn)所在的指令位置查詢故障序列,得到該指令處的單粒子翻轉(zhuǎn)故障敏感寄存器和有效故障空間.

學(xué)生在語(yǔ)文學(xué)習(xí)中的障礙主要是由于缺乏對(duì)所學(xué)內(nèi)容了解不夠而沒(méi)有產(chǎn)生學(xué)習(xí)興趣?，F(xiàn)在我們可以用多媒體幫助學(xué)生由抽象變?yōu)榫唧w，加上教師恰到好處的點(diǎn)撥講解使學(xué)生更容易理解和把握所學(xué)內(nèi)容。

步驟5.根據(jù)工作模式選擇故障注入的方式:若處于自動(dòng)故障注入故障模式中時(shí),從單粒子翻轉(zhuǎn)故障敏感寄存器或有效故障空間中隨機(jī)選取一個(gè)注入單粒子翻轉(zhuǎn)故障;若故障注入程序處于手動(dòng)控制模式,則提供該指令處的單粒子翻轉(zhuǎn)故障敏感寄存器和有效故障空間.

6 實(shí)驗(yàn)與分析

為了驗(yàn)證本文提出的基于隨機(jī)森林的故障注入方法的有效性,本文進(jìn)行了相關(guān)實(shí)驗(yàn).實(shí)驗(yàn)的硬件環(huán)境:CPU為i5-3470,內(nèi)存為8G;使用的操作系統(tǒng)為Ubuntu-16.04.1 i686,Linux內(nèi)核版本為4.15.0-106,編譯器使用的是gcc-5.4.0.為了收集訓(xùn)練數(shù)據(jù)和測(cè)試的數(shù)據(jù)集,本文從GitHub上爬取72個(gè)使用C語(yǔ)言編寫(xiě)的程序,這些程序的類型包括b-tree、bfs、dijksra和fibonacci等49種類型,然后使用gcc 編譯作為被故障注入的程序,然后針對(duì)寄存器故障和內(nèi)存故障分別進(jìn)行了故障注入實(shí)驗(yàn).

6.1 寄存器單粒子翻轉(zhuǎn)故障注入實(shí)驗(yàn)

本部分的實(shí)驗(yàn)首先收集被注入寄存器單粒子翻轉(zhuǎn)故障程序的所有可能執(zhí)行的指令序列和計(jì)算機(jī)所有的寄存器.為了減少故障之間的影響,假設(shè)程序一次執(zhí)行僅發(fā)生一次單粒子翻轉(zhuǎn)故障,即僅在一條指令處注入一個(gè)寄存器單粒子翻轉(zhuǎn)故障.按照程序指令的執(zhí)行序列和寄存器列表依次注入故障.圖4給出了4種注入方法故障有效率的箱線圖,故障有效率為注入故障后引發(fā)程序出現(xiàn)數(shù)據(jù)流/控制流錯(cuò)誤的故障注入次數(shù)占總故障注入次數(shù)的比率.圖5給出了控制流注入和基于隨機(jī)森林注入故障覆蓋率的箱線圖,故障覆蓋率為注入有效故障占程序所有有效故障中的比.

圖4 4種注入故障有效率

圖4中可以看到隨機(jī)注入故障的有效率在40%以下,僅有兩個(gè)程序故障有效率超過(guò)40%,72個(gè)程序的平均故障率為28.90%.即采用隨機(jī)故障注入的方式,故障注入的有效率不到30%,使用隨機(jī)注入的方式注入故障的有效率低于三分之一.數(shù)據(jù)流注入故障的有效率和隨機(jī)故障注入有效率略低于隨機(jī)注入,平均故障有效率為23.57%,數(shù)據(jù)流注入由于指令的覆寫(xiě)作用而導(dǎo)致故障有效率低.而本文提出的基于隨機(jī)森林的故障注入方法,是將上述故障注入的結(jié)果隨機(jī)選取70%作為訓(xùn)練數(shù)據(jù)集,30%作為測(cè)試數(shù)據(jù)集,使用訓(xùn)練數(shù)據(jù)集訓(xùn)練指令寄存器故障預(yù)測(cè)器,然后使用測(cè)試數(shù)據(jù)測(cè)試訓(xùn)練的效果.而基于隨機(jī)森林的故障注入方法在測(cè)試集中的故障有效率大多數(shù)在80%左右,最高為 96%.經(jīng)過(guò)計(jì)算,基于隨機(jī)森林的故障注入平均故障預(yù)測(cè)準(zhǔn)確率為80.42%.因此與隨機(jī)注入的方式相比,使用隨機(jī)森林的方法實(shí)有效的提高了注入故障的有效率.

從圖4中可知控制流注入故障有效率與本文提出的方法接近;但是控制流注入會(huì)極大的降低有效故障的覆蓋率.控制流注入和本文方法的有效故障覆蓋率如圖5所示,控制流注入的有效故障覆蓋率在40%-50%之間,對(duì)有效故障的覆蓋率不足,而基于隨機(jī)森林的故障覆蓋率均在70%以上,故障覆蓋率分布在75%到90%之間,72個(gè)程序的平均故障覆蓋率為82.72%.隨機(jī)注入是在指令和寄存的全體集合中隨機(jī)選取,所以隨機(jī)注入的方式故障覆蓋率為100%;基于隨機(jī)森林的注入方式由于使用了隨機(jī)森林算法對(duì)故障進(jìn)行預(yù)測(cè),不能覆蓋所有的有效故障,所以與隨機(jī)注入的方式相比故障覆蓋率有所下降.

圖5 故障覆蓋率箱線圖

6.2 內(nèi)存單粒子翻轉(zhuǎn)故障注入實(shí)驗(yàn)

與離散的寄存器不同,一個(gè)程序內(nèi)存既是離散又是連續(xù)的,程序內(nèi)存的離散性體現(xiàn)在:程序不同的部分(動(dòng)態(tài)庫(kù))的內(nèi)存地址是離散的、程序動(dòng)態(tài)申請(qǐng)的內(nèi)存是離散的,但是程序模塊內(nèi)部的地址又是連續(xù)的.本文首先將獲取程序各個(gè)部分的內(nèi)存地址范圍,再將它們拼接成一個(gè)整體;然后采用定長(zhǎng)的方式將內(nèi)存分成幾個(gè)故障注入?yún)^(qū),這些故障注入?yún)^(qū)可以根據(jù)內(nèi)存拼接的方式重新映射到原有的程序部分中.為了避免注入故障之間的影響,并且本問(wèn)題出的注入方法針對(duì)的是單粒子翻轉(zhuǎn)故障,假設(shè)程序中的內(nèi)存單粒子翻轉(zhuǎn)故障僅發(fā)生在執(zhí)行某個(gè)指令時(shí)翻轉(zhuǎn)內(nèi)存中的某比特位上.因此,在收集內(nèi)存單粒子翻轉(zhuǎn)故障注入數(shù)據(jù)時(shí),本文按照指令序列和內(nèi)存故障注入?yún)^(qū),采用一次僅在一條指令處中的一個(gè)內(nèi)存故障注入?yún)^(qū)注入一個(gè)單粒子翻轉(zhuǎn)故障.表3給出了按照0.5kb、0.7kb、0.8kb和1kb的方式劃分故障注入?yún)^(qū)的平均故障有效率.從表3中不難看出隨著故障區(qū)劃分的粒度越來(lái)越粗糙,注入故障的有效率迅速降低,最后僅有個(gè)位數(shù)的有效故障率,也就是說(shuō)在內(nèi)存單粒子故障上,使用隨機(jī)的故障注入方式故障注入的有效率極低.

表3 不同大小故障注入?yún)^(qū)的平均故障有效率

基于隨機(jī)森林故障注入的實(shí)驗(yàn)使用0.5kb的故障區(qū)劃分方式的收集到的數(shù)據(jù).隨機(jī)選取70%作為訓(xùn)練數(shù)據(jù)集,30%作為測(cè)試數(shù)據(jù)集,使用訓(xùn)練數(shù)據(jù)集訓(xùn)練內(nèi)存單粒子翻轉(zhuǎn)故障預(yù)測(cè)器,然后使用測(cè)試數(shù)據(jù)測(cè)試訓(xùn)練的效果.最終基于隨機(jī)森林的預(yù)測(cè)器在測(cè)試集上的故障有效率平均為74.52%,有效的提高了內(nèi)存單粒子翻轉(zhuǎn)故障注入的有效率.此外,本框架中的內(nèi)存單粒子翻轉(zhuǎn)故障注入預(yù)測(cè)器故障注入的有效率和數(shù)據(jù)收集時(shí)內(nèi)存故障注入?yún)^(qū)劃分的細(xì)粒度有關(guān),1kb的故障注入?yún)^(qū)的劃分方式訓(xùn)練出的預(yù)測(cè)器有效率僅為10.48%,故障注入的有效率接近隨機(jī)注入的故障有效率.

實(shí)驗(yàn)結(jié)果表明當(dāng)劃分的注入故障區(qū)域越小時(shí),本文所提出的基于隨機(jī)森林的故障注入方法對(duì)故障注入的有效率提高的越明顯;當(dāng)劃分的故障區(qū)域越大時(shí),隨機(jī)注入的故障有效率和本文的大致相同,使用機(jī)器學(xué)習(xí)算法對(duì)故障有效率提高效果不明顯.

7 結(jié) 論

針對(duì)傳統(tǒng)故障注入方法有效性不足、有些僅注入控制流錯(cuò)誤和有些僅注入數(shù)據(jù)流錯(cuò)誤的問(wèn)題,本文提出了一種基于隨機(jī)森林的故障注入方法,該方法根據(jù)基于傳統(tǒng)故障注入方法的獲取程序指令的各項(xiàng)特征和故障注入結(jié)果,然后將收集的數(shù)據(jù)分為訓(xùn)練數(shù)據(jù)集和測(cè)試數(shù)據(jù)集,在訓(xùn)練數(shù)據(jù)集上使用隨機(jī)森林算法訓(xùn)練出指令脆弱性預(yù)測(cè)模型,根據(jù)該預(yù)測(cè)模型對(duì)被注入程序的各指令不同部件單粒子翻轉(zhuǎn)故障的脆弱性進(jìn)行預(yù)測(cè),選取每個(gè)指令寄存器脆弱性最強(qiáng)的3個(gè)故障和有效故障空間形成故障序列,故障注入時(shí)從故障序列中選取對(duì)應(yīng)的項(xiàng)中隨機(jī)選取一個(gè)故障進(jìn)行注入.最后通過(guò)實(shí)驗(yàn),與傳統(tǒng)的故障注入方法進(jìn)行對(duì)比,分析了該故障注入方法的有效性,該故障注入方法相比同類故障注入方法,可以極大的避免注入不能引起程序故障的無(wú)效單粒子翻轉(zhuǎn)故障,并且與單純的注入數(shù)據(jù)流錯(cuò)誤和控制流錯(cuò)誤的故障注入方法相比,這種方法能夠兼顧兩種故障注入,也可以側(cè)重于一種故障,應(yīng)用更具有泛化性.