一種檢測控制流錯誤的多層分段標(biāo)簽方法

鄭偉寧，莊 毅，顧浩為

(1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211106； 2.中華中學(xué)，江蘇 南京 211106)

0 引 言

在計算機(jī)運(yùn)行過程中，因?yàn)樾盘柣蛘邤?shù)據(jù)不正確造成的故障被稱為軟錯誤[1]。導(dǎo)致軟錯誤的原因有多種，從電路設(shè)計出現(xiàn)問題到元件之間相互干擾，乃至于空間輻射均有可能造成軟錯誤[2]。軟錯誤會改變寄存器或數(shù)據(jù)存儲器中的值，從而導(dǎo)致處理器將程序帶入錯誤循環(huán)或者直接進(jìn)入死循環(huán)無法跳出。雖然軟錯誤通常不會對硬件電路造成永久性損壞，但仍會造成嚴(yán)重的后果。比如，2000年，美國SUN UNIX因緩存出現(xiàn)軟錯誤而影響了全美數(shù)十個服務(wù)器的正常工作，造成了數(shù)百萬美元的經(jīng)濟(jì)損失；2011年，我國首顆火星探測衛(wèi)星“螢火一號”升空后，由于負(fù)責(zé)運(yùn)載的俄方Fregat上級控制系統(tǒng)遭受空間粒子輻射誘發(fā)軟錯誤，致使火星探測失敗。在其他領(lǐng)域，如工業(yè)生產(chǎn)、民用設(shè)施，軟錯誤也在不同程度上影響了電子設(shè)備的正常運(yùn)行，降低了系統(tǒng)的可靠性。而根據(jù)應(yīng)用場景的不同，對計算機(jī)的可靠性要求也不相同。例如發(fā)生在衛(wèi)星控制系統(tǒng)上的錯誤比發(fā)生在視頻游戲中的錯誤造成的后果更加嚴(yán)重。因此，在設(shè)計加固方案時需要綜合考慮應(yīng)用場景、加固效果、需求成本等多方面因素。所以在性能受限的平臺上，及時有效地對軟錯誤進(jìn)行檢測恢復(fù)，針對計算機(jī)系統(tǒng)進(jìn)行軟錯誤加固，減少故障的發(fā)生以提高系統(tǒng)的可靠性具有重要的意義。開發(fā)一種能夠有效檢測軟件中軟錯誤，同時檢測成本較低，可以被接受的檢測系統(tǒng)，也是目前的研究重點(diǎn)。

本文著眼于解決軟錯誤中控制流錯誤的檢測問題。程序控制流錯誤是軟錯誤的一大類型，根據(jù)Zhu等人[3]和Ohlsson等人[4]的實(shí)驗(yàn)結(jié)果可知，在程序發(fā)生的軟錯誤中，有33%～77%的可能性造成程序的控制流錯誤。當(dāng)高能粒子在與程序調(diào)用地址相關(guān)的位置引發(fā)故障時，就有可能造成控制流錯誤[5]。對于任何計算機(jī)程序，只要給程序輸入，其內(nèi)部執(zhí)行指令的順序就是固定的，但是控制流錯誤會改變這種順序，從而影響程序的正確執(zhí)行[6]。目前檢測控制流錯誤的軟件技術(shù)通常是維護(hù)并更新一個全局的動態(tài)變量，通過監(jiān)測變量的變化間接監(jiān)控程序的控制流，這一變量也就是標(biāo)簽。這種技術(shù)也被稱為基于標(biāo)簽實(shí)現(xiàn)的控制流錯誤檢測技術(shù)[7]。

1 研究現(xiàn)狀

目前國內(nèi)外對控制流檢測技術(shù)已經(jīng)有了許多研究成果。Yau等人[8]在1980年提過一種使用數(shù)據(jù)庫來記錄程序控制流的方法，但是這種方法需要維護(hù)一個數(shù)據(jù)庫且不同程序控制流信息不同，最終會導(dǎo)致數(shù)據(jù)庫不斷擴(kuò)充，開銷太高。該方法雖然本身存在著局限性，但是它提出了一種程序無循環(huán)間隔的概念，這一概念就是程序基本塊劃分的前身。ECCA(Enhanced Control-flow Checking using Assertions)也屬于早期軟件實(shí)現(xiàn)的控制流錯誤檢測方法，該方法通過在程序無分支間隔的入口和出口處插樁斷言來檢測錯誤[9]。此文獻(xiàn)中的無分支間隔和斷言與后來的基本塊和標(biāo)簽已經(jīng)非常接近了，但是由于更新操作采用乘除法，并且插樁的斷言本身較為復(fù)雜，會產(chǎn)生較大的開銷。CFCSS(Control-Flow Checking by Software Signatures)是基于標(biāo)簽實(shí)現(xiàn)的控制流錯誤檢測方法中最為經(jīng)典的方法，它將程序執(zhí)行的指令劃分為眾多集合，并以此正式提出了基本塊的概念。CFCSS將程序劃分為基本塊后，通過對每一基本塊分配唯一的標(biāo)簽并添加錯誤檢測指令來實(shí)現(xiàn)控制流錯誤檢測。作為早期以純軟件方法實(shí)現(xiàn)的控制流錯誤檢測技術(shù)之一，它有著重要的參考比較價值[10]。

目前主流的控制流錯誤檢測方法大多是基于標(biāo)簽實(shí)現(xiàn)的方法，不同方法之間的主要區(qū)別在于標(biāo)簽設(shè)置的數(shù)量、標(biāo)簽更新的方式以及標(biāo)簽比較的位置。Vemu等人[11]提出的CEDA(Control-flow Error Detection using Assertions)就屬于標(biāo)簽控制流錯誤檢測技術(shù)中表現(xiàn)出色的一種。CEDA繼承了部分CFCSS的特性，在每一基本塊的入口和出口處添加了標(biāo)簽更新與驗(yàn)證體系，展現(xiàn)出了不錯的性能。Chielle等人在CEDA和一種偏硬件的方法HETA[12]的基礎(chǔ)上提出了S-SETA[13](Selective Software-only Error-detection Technique using Assertions)方法。S-SETA和CEDA較為相似，利用雙層標(biāo)簽機(jī)制，通過基本塊之間的關(guān)聯(lián)性來計算更新運(yùn)行時的標(biāo)簽。Zhu等人[14]提出了一種雙標(biāo)簽的控制流錯誤檢測方法RCFC (Regularized Control Flow Checking algorithm)。該方法無論是開銷還是檢測性能上均不太理想，但是其提出的雙標(biāo)簽機(jī)制卻提供了一種新的思路。在檢測性能要求較高但開銷可以放松限制的情況下，雙標(biāo)簽機(jī)制就是一種能有效提高錯誤檢測率的手段。國內(nèi)對基于標(biāo)簽的控制流錯誤檢測方法也有了較為深入的研究。張鵬等人[15]提出了一種使用雙指令環(huán)設(shè)計標(biāo)簽的SSCFC(Structural Signatures for Control Flow Checking)技術(shù)，該技術(shù)通過引入的雙指令環(huán)可以有效地解決塊間滯后性和配置不靈活的缺點(diǎn)。李愛國等人[16]提出了能夠記錄基本塊關(guān)系的RSCFC(Relationship Signatures for Control Flow Checking)技術(shù)。RSCFC和其他的標(biāo)簽控制流檢測技術(shù)不同，它的基本塊在設(shè)計上可以將基跳轉(zhuǎn)關(guān)系直接編碼進(jìn)來，間接地節(jié)省了標(biāo)簽更新語句和標(biāo)簽檢查語句的開銷。但是該方法對于基本塊總數(shù)有要求，嚴(yán)格受到了機(jī)器字長的限制，使算法的靈活性受到了極大的影響，難以在大體量程序上使用。張倩雯[17]提出了名為CEDBR(Control-flow Error Detection based on Basic-block Repartition)的雙標(biāo)簽控制流錯誤檢測技術(shù)，該方法有完善的規(guī)則和算法設(shè)計，有效地提高了錯誤檢錯率，是一種較為成熟的雙標(biāo)簽算法。帕爾哈提江·斯迪克等人[18]通過分析程序控制流，限制間接調(diào)用函數(shù)的方法來降低調(diào)用指令的數(shù)量，再加上一種二進(jìn)制的檢查代碼，從而達(dá)到檢測目的。姬秀娟等人[19]基于程序控制流程圖設(shè)計了一種基于投影的模型檢測靜態(tài)分析算法，來提高錯誤檢測的有效性和準(zhǔn)確率。

目前大部分基于標(biāo)簽的控制流錯誤檢測方法的原理大體相似，只是標(biāo)簽設(shè)計的結(jié)構(gòu)、規(guī)則和位置有所不同，各個方法的檢測率與時空開銷的差異也來源于此，就目前而言，基于標(biāo)簽的控制流檢測算法普遍存在著開銷與漏檢率矛盾的問題，如何權(quán)衡兩者以達(dá)到最好的檢測效果，是本文研究的重點(diǎn)。本文對已有的控制流方法進(jìn)行改進(jìn)，提出一種多層分段標(biāo)簽控制流檢測方法CFMSL(Control Flow detection method based on Muti-layer Segmented Labels)。

2 多層分段標(biāo)簽方法

2.1 相關(guān)定義

目前已有的面向軟件的控制流錯誤檢測方法大多需要依靠程序控制流程圖[20]，它由基本塊及基本塊之間跳轉(zhuǎn)關(guān)系構(gòu)成的二元組組成。本文借用LLVM[21](Low Level Virtual Machine)平臺及相關(guān)圖片生成工具，實(shí)現(xiàn)程序控制流程實(shí)體化，并成功嵌入到程序加固系統(tǒng)中。相關(guān)定義如下：

定義1基本塊(Basicblock, b)是一組滿足特定條件的最小有序指令集合，記為b={Iin,…,Ii,…,Ibra}?；緣K內(nèi)部除去最后一條指令外，沒有其它的跳轉(zhuǎn)指令。

定義2控制流(Control-flow, CF)為軟件運(yùn)行時基本塊之間的跳轉(zhuǎn)順序。一般來說，這種跳轉(zhuǎn)順序是固定不變的，一旦發(fā)生改變就有可能產(chǎn)生控制流錯誤。本文定義控制流為E={eij|1i,jn}，其中eij為bi到bj之間的跳轉(zhuǎn)邊，n代表了整個程序中基本塊的總數(shù)量。

定義3任意一個程序均可表示為程序控制流程圖(Program control-flow Graph, PG)，由二元組PG=〈B,E〉表示。其中B={bin,…,bi,…,bend}代表程序基本塊的集合，E={eij|1i,jn}則代表了程序的控制流。

定義4前驅(qū)是指程序控制流中任意一段跳轉(zhuǎn)關(guān)系的起點(diǎn)基本塊，前驅(qū)集合是指基本塊所有前驅(qū)基本塊的集合，本文使用pred來表示，如果eij∈E，則bi∈pred(bj)。與前驅(qū)集合不同，前驅(qū)序列是一種基本塊有序集合。某基本塊的前驅(qū)序列是指在程序的某一條控制流中，按照執(zhí)行順序所有處于該基本塊前方的基本塊集合，并依照與該基本塊的距離從近至遠(yuǎn)排序。如控制流{b1→b2→b3→b4}中，b4的前驅(qū)序列為{b3,b2,b1}。

定義5與前驅(qū)對應(yīng)，后繼是指程序控制流跳轉(zhuǎn)時的終點(diǎn)基本塊。后繼集合是指基本塊所有后繼基本塊的集合，本文使用succ來表示。如果eij∈E，則bj∈succ(bi)。

定義6軟件運(yùn)行時因軟錯誤導(dǎo)致軟件發(fā)生錯誤跳轉(zhuǎn)，這種軟件錯誤被稱為控制流錯誤。設(shè)指令I(lǐng)i∈bi={Ii1,Ii2,…,Iiend}，在程序中存在指令I(lǐng)i→Ij之間的合法跳轉(zhuǎn)，則指令I(lǐng)j需滿足以下2個條件：1)若i

定義7至多只有一個前驅(qū)且至多只有一個后繼的基本塊為O型基本塊，記為TO?；緣K若不是O型，則為M型，記為TM。

定義8本文為每一個基本塊匹配一個具有唯一性的標(biāo)簽，稱為基本塊標(biāo)簽，記為BS。當(dāng)程序正確執(zhí)行時，動態(tài)全局標(biāo)簽需要與其相等。

定義9程序運(yùn)行時有一個全局動態(tài)標(biāo)簽，會根據(jù)相應(yīng)的標(biāo)簽規(guī)則進(jìn)行動態(tài)更新，記為GS。當(dāng)程序正確執(zhí)行時，更新后的GS要與BS相等。

定義10差值參數(shù)主要用于更新全局動態(tài)標(biāo)簽GS，使程序在正確執(zhí)行時，GS能更新成期望值BS。本文使用d來表示差值參數(shù)，如d(bi)代表的是基本塊bi的差值參數(shù)。

定義11層級是一組非空基本塊的集合，記為Lv。以M型基本塊為核心，所有該M型基本塊的前驅(qū)序列中從頭至尾連續(xù)的O型基本塊和該M型基本塊處于同一層級，直至遇到另一個M型基本塊為止。基本塊可以同時屬于多個層級。

定義12基本塊多前驅(qū)矛盾是指當(dāng)一個基本塊同時具備多個前驅(qū)時，不同前驅(qū)跳轉(zhuǎn)至同一基本塊需要讓不同標(biāo)簽值通過同一更新語句獲得同一標(biāo)簽值。但標(biāo)簽具有唯一性，標(biāo)簽更新語句也大多結(jié)果唯一，這種唯一性與上述要求產(chǎn)生了矛盾。

圖1以數(shù)據(jù)管理系統(tǒng)的部分邏輯代碼為例，給出上述程序控制流相關(guān)定義的進(jìn)一步說明。圖1(a)為由if語句實(shí)現(xiàn)跳轉(zhuǎn)的示例代碼。圖1(b)為源代碼級基本塊劃分圖。圖1(c)為程序控制流程圖PG，整個程序由%0、%9、%10和%11這4個基本塊構(gòu)成，分別記為b1、b2、b3、b4，其中b1、b4為M型基本塊，b2、b3為O型基本塊。依照程序正常執(zhí)行流程，基本塊b1的后繼為b2和b3。由于程序內(nèi)變量b為0～3之間的隨機(jī)數(shù)，與a之間的比較結(jié)果隨機(jī)，故跳轉(zhuǎn)至b2或b3均為正?？刂屏?。若程序執(zhí)行過程中受軟錯誤影響發(fā)生錯誤跳轉(zhuǎn)，如圖1(b)中由b1跳至b4，此時變量c的值仍為0，發(fā)生控制流錯誤。

(d) 程序控制流相關(guān)定義

2.2 基本塊按層次劃分規(guī)則

依照定義7將基本塊分為2類，M型基本塊與O型基本塊。本文設(shè)計的分層標(biāo)簽需要程序滿足一種特定的控制流跳轉(zhuǎn)規(guī)律：2個M型基本塊不可連續(xù)執(zhí)行，后文將這條規(guī)律稱為M不連續(xù)原則。以此為基礎(chǔ)設(shè)計標(biāo)簽生成、更新及校驗(yàn)規(guī)則。不滿足跳轉(zhuǎn)規(guī)律的程序，需要使用基本塊按層次劃分規(guī)則來改變程序控制流結(jié)構(gòu)。

規(guī)則1若程序中存在一條控制流，其中有2個M型基本塊連在一起，則替換其原本跳轉(zhuǎn)路徑，在二者之間插入1個空基本塊。

規(guī)則2以M型基本塊為核心，所有該M型基本塊的前驅(qū)序列中從頭至尾連續(xù)的O型基本塊和該M型基本劃分為同一層，直至遇到另一個M型基本塊為止。對于任意一個程序，若入口基本塊為M型基本塊，則將其單獨(dú)劃分為一個層級。若入口基本塊為O型基本塊，則將之歸入程序流中的第一個M型基本塊所處的層級。

引理1通過規(guī)則1對程序控制流重構(gòu)后，得到的新程序控制流程圖中，不存在可以連續(xù)執(zhí)行2個M型基本塊的控制流。即：?bi∈B，若bi∈TM，則(succ(bi)?TO)∨(pred(bi)?TO)。

證明:對?bi∈TM，若?bj∈succ(bi)?TM，則根據(jù)規(guī)則1調(diào)整，必?bp∈TO，使得bp∈pred(bj),bp∈succ(bi)且bi?pred(bj),bj?succ(bi)，這與bj∈succ(bi)產(chǎn)生矛盾。因此，任何經(jīng)過規(guī)則1調(diào)整后的程序，一定不存在可以連續(xù)執(zhí)行2個M型基本塊的控制流。

圖2為基本塊層次劃分規(guī)則應(yīng)用的典型情況。其中，圖2(a)和圖2(b)分別對應(yīng)規(guī)則1與規(guī)則2。虛線所代表的基本塊表示新插入的空基本塊。圖2(a)中b1和b2均為M型基本塊，整個程序有2條控制流{b1→b2}與{b1→b3→b2}，前者不滿足M不連續(xù)原則，故根據(jù)規(guī)則1插入空基本塊bp以重構(gòu)控制流。圖2(b)中有一條控制流從b4又跳回了b1，導(dǎo)致b1同時歸屬2個層級Lv1和Lv3。

圖2 基本塊按層次劃分示例

2.3 多層分段標(biāo)簽規(guī)則

本文采用靜態(tài)標(biāo)簽[22]插樁技術(shù)，插樁全局動態(tài)標(biāo)簽GS(Global Signature)，使程序執(zhí)行時連續(xù)地更新GS，并隨時檢查標(biāo)簽以監(jiān)視程序的運(yùn)行狀態(tài)。這一過程可以被概括地分成3個階段：標(biāo)簽分配階段、標(biāo)簽更新階段以及標(biāo)簽檢查階段。標(biāo)簽分配階段會為程序中的每一基本塊靜態(tài)地計算并分配基本塊標(biāo)簽值；標(biāo)簽更新階段根據(jù)標(biāo)簽分配規(guī)則為每一基本塊添加標(biāo)簽更新語句，使程序正確運(yùn)行時得到正確的標(biāo)簽。標(biāo)簽檢查階段在基本塊內(nèi)部添加檢查指令，以保證發(fā)生標(biāo)簽錯誤時可以盡早檢測出來。

本文設(shè)計了用于標(biāo)簽分配的具體規(guī)則，給出了相關(guān)定理，為了方便描述，引入下列術(shù)語：

1位&1位集合：1位是指本文所設(shè)計的二進(jìn)制標(biāo)簽中數(shù)值為1的位置(位數(shù)從1開始，并且從右向左計算)，1位集合是指標(biāo)簽中所有1位的集合，本文中將1位集合表示為1set。如：011的1位集合為{1,2}，110的1位集合為{2,3}，即1set(011)={1,2},1set(110)={2,3}。

1位包含：1位包含是指某一標(biāo)簽的1位集合包含于另一標(biāo)簽的1位集合。如：010的1位集合包含于011的1位集合，即{2}?{1,2}。

多層分段標(biāo)簽：本文所設(shè)計的多層分段標(biāo)簽通過分段設(shè)計使其具備了雙標(biāo)簽的功效。標(biāo)簽共分為前后2段，分別為層號段與標(biāo)簽值段。層號段標(biāo)識基本塊所屬層次，記為BS1。標(biāo)簽值段則在同層內(nèi)標(biāo)識不同的基本塊，記為BS2。

作為標(biāo)簽檢錯技術(shù)的一種，多層分段標(biāo)簽控制流錯誤檢測方法也不可避免地遇到了一個問題：基本塊多前驅(qū)矛盾。CFCSS為了解決這一問題增加開銷引入了變量D，RCFC為了解決這一問題放棄了標(biāo)簽唯一性從而造成了檢錯率的下降。多層分段標(biāo)簽控制流錯誤檢測方法利用特殊的標(biāo)簽機(jī)制及更新規(guī)則，在解決這一矛盾的同時未增加任何開銷，同時也保證了標(biāo)簽的唯一性，具體規(guī)則如下。

規(guī)則3程序執(zhí)行時，全局動態(tài)標(biāo)簽GS的更新語句在基本塊入口位置，O型基本塊執(zhí)行異或運(yùn)算，M型基本塊執(zhí)行或運(yùn)算。即：

規(guī)則4程序內(nèi)所有O型基本塊標(biāo)簽的1位集合包含于其后繼M型基本塊標(biāo)簽的1位集合。即：?bi,bj∈B,若bi=pred(bj),bi∈TO且bj∈TM,則1set(BS(bi))?1set(BS(bj))。

若基本塊為O型基本塊，分段差值參數(shù)為基本塊分配標(biāo)簽與其前驅(qū)基本塊分配標(biāo)簽異或運(yùn)算的結(jié)果。即：?bi,bj∈B，若bi∈TO,bj∈pred(bi)且bi∈succ(bj)，則d(bi)=BS(bi)xor BS(bj)。

規(guī)則5若基本塊為M型基本塊，其分段差值參數(shù)層號段為0，標(biāo)簽值段為該基本塊所有前驅(qū)標(biāo)簽值段或運(yùn)算的結(jié)果。即：?bi,bj1,…,bjn∈B,若?bi∈TM,bj1,…,bjn∈pred(bi),則d(bi)=BS(bj1) or BS(bj2) or…or BS(bjn)。

規(guī)則6所有M型基本塊標(biāo)簽中標(biāo)簽值段為該基本塊所有前驅(qū)基本塊標(biāo)簽中標(biāo)簽值段或運(yùn)算的結(jié)果。即：?bi,bj1,…,bjn∈B,若?bi∈TM,bj1,…,bjn∈pred(bi),則BS2(bi)=BS2(bj1) or BS2(bj2) or…or BS2(bjn)。

規(guī)則7將程序所有基本塊按層次劃分，并在標(biāo)簽層號段標(biāo)識層號。層號具備唯一性，且互相滿足1位不包含原則。一般來說，層號僅取標(biāo)簽層號段的某一位為1。即：?bi,bj∈B,若Lv(bi)≠Lv(bj),則(1set(BS1(bi))?1set(BS1(bj)))∪(1set(BS1(bj))?1set(BS1(bi)))。

規(guī)則8若程序中存在循環(huán)控制流，即某一基本塊同時處于多個層級中，則該基本塊必為M型基本塊，且其層號為其所有前驅(qū)基本塊層號or運(yùn)算的結(jié)果。即：?bi∈B,bj1,…,bjn∈pred(bi),則BS2(bi)=BS1(bj1) or BS1(bj2) or…or BS1(bjn)。

規(guī)則9不同層級間基本塊標(biāo)簽值段可重復(fù)，但同一層基本塊間標(biāo)簽值段必須唯一，且該層所有O型基本塊之間互相滿足1位不包含原則，M型基本塊之間也互相滿足1位不包含原則，非前驅(qū)后繼關(guān)系的O型基本塊與M型基本塊也互相滿足1位不包含原則。

規(guī)則10程序內(nèi)每一個基本塊均要有標(biāo)簽檢查指令，位置在標(biāo)簽更新指令之后，用于比較全局動態(tài)標(biāo)簽GS與基本塊標(biāo)簽BS的值以檢測控制流錯誤。

上述規(guī)則為多層分段標(biāo)簽控制流錯誤檢測方法的基本規(guī)則，也是必要規(guī)則。規(guī)則3～規(guī)則6是多層分段標(biāo)簽控制流錯誤檢測方法可以獲得較低開銷的基礎(chǔ)，本文將基本塊劃分為2種類型：O型與M型。由于O型基本塊至多只有一個前驅(qū)，故基本塊多前驅(qū)矛盾都集中發(fā)生在M型基本塊中。多層分段標(biāo)簽控制流錯誤檢測方法在M型基本塊的標(biāo)簽更新語句中使用or運(yùn)算來替換xor運(yùn)算。但or運(yùn)算本身不具備唯一性，有可能導(dǎo)致某些控制流錯誤無法檢測。如圖3(a)所示，依照規(guī)則3～規(guī)則6分配標(biāo)簽，通過or運(yùn)算解決了b2→b4和b3→b4的基本塊多前驅(qū)矛盾問題，但發(fā)生b1→b4的控制流錯誤跳轉(zhuǎn)時，就無法檢測出來。為了解決該問題，本文引入了層號的概念，并在標(biāo)簽的設(shè)計上做出了調(diào)整。如圖3(b)所示，層號可以檢測出程序中發(fā)生的b1→b4控制流錯誤。層號在設(shè)計時也要遵循一定規(guī)則，否則如圖3(c)所示，層號未解決問題。因此，本文提出了規(guī)則7。對于整個程序而言，層號之間必須有所區(qū)分且唯一。在此基礎(chǔ)上，也不允許存在1位集合包含的情況，即任意的2個不同層號之間，1位集合互不包含。層號不允許設(shè)置為0，一般層號僅取標(biāo)簽中的某一位為1即可。如程序共分為3層，則層號可分別設(shè)為：001，010，100。程序的循環(huán)結(jié)構(gòu)是一種較為常見的結(jié)構(gòu)，體現(xiàn)到程序控制流程圖中就代表會出現(xiàn)如圖3(d)中b1的結(jié)構(gòu)。這種情況下使得基本塊b4同時處于010層和100層中，故層號也包含了010和100。為了解決這一現(xiàn)象，本文引入了規(guī)則8，依照此規(guī)則此時基本塊b4的所屬層號為010 or 100=110,同時兼顧了b2→b4、b3→b4和b5→b4的控制流跳轉(zhuǎn)。

(a) (b)

(c) (d)

規(guī)則3～規(guī)則8解決了控制流跨層錯誤跳轉(zhuǎn)的問題，但未顧及同層錯誤跳轉(zhuǎn)問題，尤其是當(dāng)同一層含有2個或2個以上的M型基本塊的情況。如圖4(a)所示，b2、b4和b5均為M型基本塊，在程序中存在2條控制流b2→b4和b2→b5，依照規(guī)則1在上述2條控制流中插入了空基本塊bp1和bp2，按照規(guī)則2劃分層次。如圖4(b)所示，在僅考慮規(guī)則3～規(guī)則8的情況下，本文設(shè)計了一款樣例標(biāo)簽?？梢钥闯鰣D4(b)中，標(biāo)簽無法檢測出b1→b5或b4→b5的控制流錯誤跳轉(zhuǎn)。故此設(shè)計了規(guī)則9。同一層的O型基本塊間標(biāo)簽值段必須唯一，且滿足互相1位不包含原則，M型基本塊同理。圖4(b)程序中的O型基本塊b1的1位集合被同層O型基本塊b2和b3所包含，M型基本塊b4的1位集合被同層M型基本塊b5所包含，故產(chǎn)生了上述2條無法被檢測的控制流錯誤。依據(jù)規(guī)則10可插入檢查指令，考慮所有規(guī)則重新設(shè)計了如圖4(c)所示的標(biāo)簽方案，解決了上述問題。

(a)

(b)

(c)

接下來，本文引入一些定理來證明本文提出CFMSL的安全性及完備性。安全性是指當(dāng)程序正確執(zhí)行時，多層分段標(biāo)簽方法所分配的標(biāo)簽不會檢測出錯誤。完備性則是指若程序在執(zhí)行過程中發(fā)生了基本塊間錯誤跳轉(zhuǎn)，多層分段標(biāo)簽方法可以將其檢測出來。

引理2通過規(guī)則1重構(gòu)后，得到的程序控制流任意M型基本塊均與其前驅(qū)基本塊處于同一層次。

證明：若存在一基本塊為M型基本塊前驅(qū)，且和該基本塊不屬于同一層次。根據(jù)規(guī)則2，所有M型基本塊的前驅(qū)序列中的O型基本塊和該M型基本劃分為同一層，可知該前驅(qū)基本塊只能為M型基本塊。根據(jù)引理1，M型基本塊的前驅(qū)不可為M型基本塊，產(chǎn)生矛盾。因此，不存在這樣的基本塊前驅(qū)，即任意M型基本塊均與其前驅(qū)基本塊處于同一層次。

定理1當(dāng)程序正確執(zhí)行時，若標(biāo)簽在進(jìn)入基本塊前滿足GS=BS，則無論程序執(zhí)行至基本塊內(nèi)任何位置，仍滿足GS=BS。

證明：設(shè)?bi,bj∈B，且程序中存在控制流eji，即bi∈succ(bj)且bj∈pred(bi)。當(dāng)全局動態(tài)標(biāo)簽GS到達(dá)基本塊bi時GS=BS(bj)，所執(zhí)行的標(biāo)簽更新語句取決于此時基本塊的類型。根據(jù)定義，程序中任意基本塊均屬于O型或者M(jìn)型，故分2種情況討論：

1)bi∈TO。根據(jù)規(guī)則3，此時基本塊的更新語句為GS=GS xord(bi)=BS(bj) xor BS(bi) xor BS(bj)=BS(bi)。

2)bi∈TM。根據(jù)規(guī)則3，此時基本塊的更新語句為GS=GS ord(bi)。根據(jù)規(guī)則6和規(guī)則8,GS更新語句為GS=GS or d(bi)=BS(bj) or BS(bj1) or … or BS(bjn)=BS(bi)。

綜上所述，此時的全局動態(tài)標(biāo)簽在基本塊任何位置均滿足GS=BS。

引理3若因程序發(fā)生錯誤跳轉(zhuǎn)而導(dǎo)致全局動態(tài)標(biāo)簽層號段在程序中任何一處與基本塊標(biāo)簽層號段不同，則此錯誤會被檢查出來。

證明：若層號與期望值不同，證明此時發(fā)生了跨層錯誤跳轉(zhuǎn)。錯誤產(chǎn)生后，GS會在基本塊入口處進(jìn)行標(biāo)簽更新。GS抵達(dá)不同類型的基本塊，會遇到不同的標(biāo)簽更新運(yùn)算。若抵達(dá)O型基本塊，則更新語句為GS=GS xord。異或運(yùn)算的結(jié)果具備唯一性，已有的層號段錯誤不會被掩蓋，故此錯誤可以被檢查出來。若抵達(dá)M型基本塊，則更新語句為GS=GS ord。根據(jù)規(guī)則7，此時層號段與期望值不同，但也滿足1位互不包含原則。根據(jù)規(guī)則8，更新語句中的差值參數(shù)d層號段1位與基本塊所處層次1位相同，即d1和GS的1位不同。顯然，1位是無法被或運(yùn)算掩蓋的，故此錯誤也能被檢查出來。

引理4若因程序發(fā)生錯誤跳轉(zhuǎn)而導(dǎo)致全局動態(tài)標(biāo)簽值段在程序中任何一處與基本塊標(biāo)簽值段不同，則此錯誤會被檢查出來。

證明：根據(jù)引理3，層號段出現(xiàn)錯誤會被檢查出來，所以現(xiàn)在考慮層號段未出錯，標(biāo)簽值段出錯的情形。層號段未出錯，證明程序發(fā)生的是同層錯誤跳轉(zhuǎn)。根據(jù)GS抵達(dá)基本塊的類型進(jìn)行分類討論。若抵達(dá)O型基本塊，則更新語句為GS=GS xord。異或運(yùn)算結(jié)果具備唯一性，根據(jù)規(guī)則9同層基本塊標(biāo)簽值段也具備唯一性，故此時的標(biāo)簽值段錯誤不會被掩蓋。若抵達(dá)M型基本塊，則更新語句為GS=GS ord。因發(fā)生同層錯誤跳轉(zhuǎn)且跳到M型基本塊，故此時也有2種情況：1)O型基本塊錯誤跳轉(zhuǎn)到M型基本塊，由于是同層錯誤跳轉(zhuǎn)，此O型基本塊和M型基本塊不是前驅(qū)后繼關(guān)系；2)M型基本塊錯誤跳轉(zhuǎn)到M型基本塊，此時也是同層錯誤跳轉(zhuǎn)。根據(jù)規(guī)則9，無論是上述哪種情況，起點(diǎn)基本塊和錯誤跳轉(zhuǎn)基本塊的標(biāo)簽值段均滿足1位不包含原則，故二者標(biāo)簽值段有不同的1位，或運(yùn)算無法掩蓋，故此錯誤可以被檢查出來。

引理5所有抵達(dá)O型基本塊的錯誤跳轉(zhuǎn)，均會被該基本塊內(nèi)的檢查語句檢測出來。

證明：設(shè)?bi,bj∈B，程序發(fā)生錯誤跳轉(zhuǎn)bj→bi，且程序運(yùn)行至bj前均正確執(zhí)行。因發(fā)生的是錯誤跳轉(zhuǎn)，則bj?pred(bi)，根據(jù)規(guī)則6～規(guī)則9，BS(bj)≠BS(pred(bi))。程序運(yùn)行在至bj前均為正確執(zhí)行，故此時全局動態(tài)標(biāo)簽與其期望值相等，即GS=BS(bj)。跳轉(zhuǎn)后，全局動態(tài)標(biāo)簽GS立刻進(jìn)行更新操作，則GS=GS xord(bi)=BS(bj) xor BS(bi) xor BS(pred(bi))≠BS(pred(bi)) xor BS(bi) xor BS(pred(bi))?GS≠BS(bi)。根據(jù)引理3與引理4，GS任意一位與BS(bi)不相等，均會被檢測出來。

引理6所有抵達(dá)M型基本塊的錯誤跳轉(zhuǎn)，均會被該基本塊內(nèi)的檢查語句檢測出來。

證明：?bi,bj∈B，程序發(fā)生錯誤跳轉(zhuǎn)bj→bi且至bj前均為正確執(zhí)行。bj?pred(bi)，BS(bj)≠BS(pred(bi))，GS=BS(bj)，分情況討論。

若bj與bi屬于不同層次，則GS1=BS1(bj)≠BS1(bi)。據(jù)M型基本塊標(biāo)簽更新語句，此時GS1=GS1xord1(bi)=BS1(bj) or BS1(bj1) or … or BS1(bjn),其中bj1,…,bjn∈pred(bi)。根據(jù)規(guī)則2，BS1(bj1)=BS1(bj1)=…=BS1(bjn)=BS1(bi)，故GS1=BS1(bj) or BS1(bi)。根據(jù)規(guī)則7，BS1(bj)與BS1(bj)互相1位不包含，故GS1=BS1(bj) or BS1(bi)≠BS1(bi)。據(jù)引理3，層號段的錯誤會被檢測出來。

若bj與bi屬于相同層次，則錯誤跳轉(zhuǎn)不會引發(fā)層號錯誤。根據(jù)規(guī)則9，GS在錯誤抵達(dá)bi前GS2=BS2(bj)≠BS2(bi)。據(jù)M型基本塊標(biāo)簽更新語句，GS2=GS2or d2(bi)=BS2(bj) or BS2(bj1) or…or BS2(bjn)=BS2(bj) or BS2(bi)，其中bj1,…,bjn∈pred(bi)。據(jù)規(guī)則9，無論bj是O型還是M型基本塊，BS1(bj)與BS1(bj)互相1位不包含。故GS2=BS2(bj) or BS2(bi)≠BS2(bi)，根據(jù)引理4，標(biāo)簽值段的錯誤會被檢測出來。

定理2多層分段標(biāo)簽控制流錯誤檢測技術(shù)是完備的。在程序中任何違反正確控制流的基本塊間錯誤跳轉(zhuǎn)均可被檢測出來。

證明：程序中的控制流錯誤會導(dǎo)致2種情況，程序非法跳轉(zhuǎn)至程序基本塊內(nèi)部或跳出程序至非代碼部分。跳轉(zhuǎn)至非代碼部分代表程序進(jìn)入了數(shù)據(jù)部分或者未經(jīng)初始化的存儲區(qū)域，根據(jù)參考文獻(xiàn)[11]，若跳轉(zhuǎn)至這一部分，處理器在嘗試執(zhí)行數(shù)據(jù)或未初始化的存儲區(qū)域時會引發(fā)指令異常而導(dǎo)致系統(tǒng)報錯。如果跳轉(zhuǎn)至程序內(nèi)部，則將跳轉(zhuǎn)至O型基本塊或者M(jìn)型基本快。根據(jù)引理5與引理6，無論跳轉(zhuǎn)至哪種類型的基本塊，均會在檢查指令中檢測出錯誤。

根據(jù)上述定理可知，CFMSL方法是完備的，為了進(jìn)一步說明定理2，本文給出了控制流非法跳轉(zhuǎn)示例，如圖5所示。

圖5 控制流非法跳轉(zhuǎn)示例圖

如圖5所示，灰色為M型基本塊，白色為O型基本塊，圖中共給出了8種控制流錯誤的示例。err1與err2為M型基本塊跳轉(zhuǎn)至M型基本塊，由于b1、b4和b6三者層級不同，err1/err2跳轉(zhuǎn)時層號段出錯，根據(jù)引理3和引理6，2個錯誤均會被檢查出來。err3/err4為O型基本塊跳轉(zhuǎn)至O型基本塊，b2、b3和b5處于不同層次，根據(jù)引理3和引理5，2個錯誤均會被檢查出來。err5/err6為M型基本塊跳轉(zhuǎn)至O型基本塊，b1與b5不同層，故err5可根據(jù)引理3和引理5檢查出來。b5與b6處于同一層次，但由于逆向跳轉(zhuǎn)，導(dǎo)致標(biāo)簽值段發(fā)生了錯誤，故根據(jù)引理4和引理5可將err6檢查出來。err7/err8為O型基本塊跳轉(zhuǎn)至M型基本塊，此時b1與b3處于不同層級，b2與b6處于不同層級，故根據(jù)引理3與引理6可知，2個錯誤均會被檢查出來。

2.4 多層分段標(biāo)簽控制流錯誤檢測算法描述

本文設(shè)計了多層分段標(biāo)簽控制流錯誤檢測算法，針對以C語言編程的數(shù)據(jù)庫管理系統(tǒng)，通過相應(yīng)規(guī)則進(jìn)行基本塊層次劃分，并分配基本塊標(biāo)簽層號段及標(biāo)簽值段。插樁標(biāo)簽更新指令和標(biāo)簽檢查指令，最終生成具有檢錯能力的目標(biāo)程序。具體的步驟如下：

Step1將目標(biāo)程序編譯成中間代碼，以進(jìn)行控制流分析。

Step2分析程序控制流關(guān)系，根據(jù)規(guī)則1重構(gòu)程序基本塊，使整個程序滿足M不連續(xù)原則。

Step3根據(jù)規(guī)則2按層劃分基本塊，根據(jù)規(guī)則7、規(guī)則8分配基本塊標(biāo)簽層號。

Step4依照基本塊層次遍歷基本塊，同層基本塊依照規(guī)則6、規(guī)則8和9分配基本塊標(biāo)簽值段。

Step5遍歷所有基本塊，依照規(guī)則3、規(guī)則4和規(guī)則5插樁基本塊更新指令。

Step6根據(jù)規(guī)則10插樁標(biāo)簽檢查指令。

3 實(shí)驗(yàn)及結(jié)果分析

3.1 故障注入工具

在程序執(zhí)行時，指令進(jìn)行跳轉(zhuǎn)的目標(biāo)地址受軟錯誤影響而改變，這會導(dǎo)致2種結(jié)果：

1)改變后的目標(biāo)地址仍在程序代碼區(qū)內(nèi)。此時程序計數(shù)器的值雖然發(fā)生了變化，但是并沒有跳出程序，只是在程序內(nèi)部的基本塊間互相跳轉(zhuǎn)。

2)程序計數(shù)器發(fā)生改變后，指向了程序代碼區(qū)以外的地址。

根據(jù)上述控制流錯誤結(jié)果，使用2種錯誤類型來模擬軟件控制流錯誤：控制流錯誤跳轉(zhuǎn)和控制流錯誤跳出?？刂屏麇e誤跳轉(zhuǎn)是指程序控制流執(zhí)行時發(fā)生控制流錯誤，控制流發(fā)生錯誤跳轉(zhuǎn)，但仍然在程序內(nèi)部?？刂屏麇e誤跳出是指程序控制流執(zhí)行時發(fā)生控制流錯誤，使控制流錯誤跳出至程序外。

本文使用的故障注入工具是基于GDB(GNU Project Debugger)[23]二次開發(fā)實(shí)現(xiàn)的。工具分為2種類型：控制流錯誤跳轉(zhuǎn)故障注入工具和控制流錯誤跳出故障注入工具，分別對應(yīng)上述2種控制流錯誤類型。

1)控制流跳轉(zhuǎn)故障注入工具。

Step1啟動GDB并加載要注入控制流跳轉(zhuǎn)錯誤的程序。

Step2完整運(yùn)行一次程序，記錄所有程序指令跳轉(zhuǎn)的PC值。

Step3隨機(jī)選擇一條PC值，記錄下來，作為控制流錯誤跳轉(zhuǎn)的起點(diǎn)。。

Step4使用GDB重新加載程序。

Step5運(yùn)行程序，至Step3所選起點(diǎn)指令PC值處設(shè)置斷點(diǎn)。

Step6在剩余PC值中隨機(jī)選擇1條，控制程序跳轉(zhuǎn)過去。

Step7根據(jù)程序的輸出來統(tǒng)計故障注入的結(jié)果。

2)控制流跳出故障注入工具。

Step1啟動GDB并加載要注入控制流跳出錯誤的程序。

Step2完整運(yùn)行一次程序，記錄所有程序指令跳轉(zhuǎn)的PC(Program Counter)值。

Step3隨機(jī)選擇一條PC值，記錄下來，作為控制流錯誤跳出的起點(diǎn)。

Step4使用GDB重新加載程序。

Step5運(yùn)行程序，至Step3所選起點(diǎn)指令PC值處設(shè)置斷點(diǎn)。

Step6在程序計數(shù)器內(nèi)的地址隨機(jī)選擇一位或者多位進(jìn)行翻轉(zhuǎn)，同時保證翻轉(zhuǎn)后的地址不在Step2記錄的程序內(nèi)部PC值中，將程序跳轉(zhuǎn)至翻轉(zhuǎn)后的地址。

Step7根據(jù)程序的輸出來統(tǒng)計故障注入的結(jié)果。

3.2 方法評估

本文使用錯誤檢錯率來評估CFMSL方法的錯誤檢測能力。CFMSL方法可以通過標(biāo)簽檢測控制流錯誤。本文對測試程序注入控制流跳轉(zhuǎn)錯誤與控制流跳出錯誤，以此來模擬程序發(fā)生控制流錯誤時的狀態(tài)。為了驗(yàn)證CFMSL方法的性能，本文另外選擇3種控制流錯誤檢測加固方法CFCSS、CEDBR和RCFC來進(jìn)行橫向?qū)Ρ?。CFCSS為2002年的方法，盡管年代較為久遠(yuǎn)，但是作為最具代表性的單標(biāo)簽控制流方法，仍然具有較高的參考價值。RCFC是2016年提出的一種雙標(biāo)簽方法，盡管標(biāo)簽設(shè)計有一定的缺陷，卻也提供了一種新思路。CEDBR是2018年提出的雙標(biāo)簽方法，相比于RCFC，CEDBR已經(jīng)有了較好的標(biāo)簽設(shè)計和詳細(xì)的規(guī)則，屬于雙標(biāo)簽方法中較為優(yōu)秀的方法。分別使用這3種方法和CFMSL對快速排序算法、最短路徑算法和數(shù)據(jù)管理系統(tǒng)3個程序進(jìn)行加固，得到了12個加固后的程序。為了體現(xiàn)魯棒性和有效性，本文對每個加固后程序分別注入了2500次控制流跳出錯誤和2500次控制流跳轉(zhuǎn)錯誤,共60000次故障來驗(yàn)證CFMSL方法的性能。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6給出采用不同的加固方法下，錯誤檢測性能的對比。漏檢率與檢錯率的統(tǒng)計是綜合了控制流錯誤跳轉(zhuǎn)與控制流跳出2種故障注入實(shí)驗(yàn)數(shù)據(jù)的綜合結(jié)果。其中CEDBR和RCFC是基于雙標(biāo)簽的控制流加固方法，CFMSL和CFCSS則是單標(biāo)簽多規(guī)則的加固方法。

圖6 不同加固方法錯誤檢測性能

本文對使用方法加固后的每一個程序，注入了2500次控制流跳出錯誤和2500次控制流跳轉(zhuǎn)錯誤。即本文對每一個加固后的程序進(jìn)行了5000次故障注入實(shí)驗(yàn)。系統(tǒng)報錯率為這5000次實(shí)驗(yàn)中系統(tǒng)報錯次數(shù)所占的比率。方法報錯率為實(shí)驗(yàn)次數(shù)中由檢錯方法報錯次數(shù)所占的比率。無錯誤率為向程序注入故障，但未出現(xiàn)錯誤次數(shù)所占的比率。漏檢率為程序出現(xiàn)異常，但是方法和系統(tǒng)均未檢測出錯誤次數(shù)所占的比率。1減去漏檢率，即為錯誤檢測率。

表1 故障注入實(shí)驗(yàn)數(shù)據(jù)

表1給出了具體實(shí)驗(yàn)數(shù)據(jù)，SYS表示系統(tǒng)錯誤的次數(shù)，F(xiàn)ind_err表示方法發(fā)現(xiàn)錯誤的次數(shù)，Correct表示程序盡管注入了錯誤，但仍正確執(zhí)行的次數(shù)。從實(shí)驗(yàn)結(jié)果可以看出，控制流錯誤跳出故障類型大部分可以通過系統(tǒng)直接檢測出來，小部分對程序沒有影響，只有極少的一部分錯誤會漏檢。與之相反的是，控制流錯誤跳轉(zhuǎn)故障中方法檢測出的錯誤占據(jù)了大部分。與圖6相同，表1中最后2欄的錯誤檢測率與錯誤漏檢率是綜合了控制流錯誤跳轉(zhuǎn)與跳出2種故障的實(shí)驗(yàn)結(jié)果。根據(jù)圖6和表1，所有的加固方法中CFMSL具有最高的錯誤檢測率和最低的錯誤漏檢率。

各方法的時空開銷如圖7所示，具體實(shí)驗(yàn)數(shù)據(jù)如表2所示。從中可以看出CEDBR方法的開銷是最高的，RCFC方法比它稍低一些，CFCSS和CFMSL方法比上2種方法開銷要低。

圖7 各方法的時空開銷

表2 方法開銷數(shù)據(jù)

綜合圖6和圖7的實(shí)驗(yàn)結(jié)果，可以發(fā)現(xiàn)基于雙標(biāo)簽的方法成本一般要比單標(biāo)簽多規(guī)則的方法高，而且只要規(guī)則設(shè)置得合適，單標(biāo)簽的方法錯誤漏檢率也可降低。而在上述4種方法中，單標(biāo)簽的CFMSL開銷最低，漏檢率也是最低的。

RCFC是一種雙標(biāo)簽算法，在O型基本塊插樁標(biāo)簽G1，在M型基本塊插樁G2。其G2標(biāo)簽僅使用1和0這2個數(shù)來區(qū)分標(biāo)簽類型，不具備唯一性。且標(biāo)簽更新函數(shù)為“store”賦值語句而非運(yùn)算，容易將標(biāo)簽錯誤掩蓋，故存在著較高的漏檢率。CEDBR是基于RCFC的改進(jìn)算法，在標(biāo)簽更新上進(jìn)行了改進(jìn)。CEDBR在基本塊內(nèi)部使用加減運(yùn)算進(jìn)行G1標(biāo)簽更新，盡管開銷增加，但顯著提高了檢錯率。另一方面，CEDBR的G2標(biāo)簽仍使用1和0，只能區(qū)分基本塊類型，不具備唯一性，這導(dǎo)致CEDBR仍然存在漏檢情況。CFCSS則是一種傳統(tǒng)的單標(biāo)簽方法，但是為了解決基本塊多前驅(qū)矛盾，引入了變量D來對標(biāo)簽進(jìn)行更新，導(dǎo)致開銷增大。CFMSL作為一種單標(biāo)簽方法，卻通過分段的形式起到了雙標(biāo)簽的作用。將基本塊劃分層級后，跨層的錯誤跳轉(zhuǎn)可以通過層號段檢測出來，同層的錯誤跳轉(zhuǎn)可以通過標(biāo)簽值段進(jìn)行檢測。CFMSL使用XOR和OR運(yùn)算的組合，在不添加任何指令和標(biāo)簽的情況下成功解決了基本塊多前驅(qū)矛盾問題，最后又使用標(biāo)簽更新規(guī)則保證了標(biāo)簽更新過程的唯一性。這使得CFMSL在具備較高檢錯率的同時具有較低的開銷。

4 結(jié)束語

本文提出了一種多層分段標(biāo)簽控制流錯誤檢測方法CFMSL。通過分析程序中的控制流信息和基本塊結(jié)構(gòu)，按層次重新劃分基本塊。對重構(gòu)后的基本塊，分配多層分段標(biāo)簽，插樁標(biāo)簽更新指令和標(biāo)簽檢查指令，最終可得到控制流檢錯加固后的程序。本文設(shè)計了基本塊按層劃分規(guī)則、基本塊標(biāo)簽更新規(guī)則、基本塊標(biāo)簽檢查規(guī)則。通過定理證明和邏輯分析證實(shí)了本文方法的正確性和完備性。最終通過控制流故障注入工具對程序進(jìn)行故障注入實(shí)驗(yàn)，通過實(shí)驗(yàn)結(jié)果驗(yàn)證了方法的有效性。