鄭偉寧，莊 毅，顧浩為

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

0 引 言

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

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

1 研究現(xiàn)狀

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

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

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

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

2.1 相關(guān)定義

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

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

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

定義3任意一個(gè)程序均可表示為程序控制流程圖(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來(lái)表示，如果eij∈E，則bi∈pred(bj)。與前驅(qū)集合不同，前驅(qū)序列是一種基本塊有序集合。某基本塊的前驅(qū)序列是指在程序的某一條控制流中，按照?qǐng)?zhí)行順序所有處于該基本塊前方的基本塊集合，并依照與該基本塊的距離從近至遠(yuǎn)排序。如控制流{b1→b2→b3→b4}中，b4的前驅(qū)序列為{b3,b2,b1}。

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

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

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

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

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

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

定義11層級(jí)是一組非空基本塊的集合，記為L(zhǎng)v。以M型基本塊為核心，所有該M型基本塊的前驅(qū)序列中從頭至尾連續(xù)的O型基本塊和該M型基本塊處于同一層級(jí)，直至遇到另一個(gè)M型基本塊為止?；緣K可以同時(shí)屬于多個(gè)層級(jí)。

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

圖1以數(shù)據(jù)管理系統(tǒng)的部分邏輯代碼為例，給出上述程序控制流相關(guān)定義的進(jìn)一步說(shuō)明。圖1(a)為由if語(yǔ)句實(shí)現(xiàn)跳轉(zhuǎn)的示例代碼。圖1(b)為源代碼級(jí)基本塊劃分圖。圖1(c)為程序控制流程圖PG，整個(gè)程序由%0、%9、%10和%11這4個(gè)基本塊構(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í)行過(guò)程中受軟錯(cuò)誤影響發(fā)生錯(cuò)誤跳轉(zhuǎn)，如圖1(b)中由b1跳至b4，此時(shí)變量c的值仍為0，發(fā)生控制流錯(cuò)誤。

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

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

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

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

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

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

證明:對(duì)?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ò)規(guī)則1調(diào)整后的程序，一定不存在可以連續(xù)執(zhí)行2個(gè)M型基本塊的控制流。

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

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

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

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

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

1位&1位集合：1位是指本文所設(shè)計(jì)的二進(jìn)制標(biāo)簽中數(shù)值為1的位置(位數(shù)從1開(kāi)始，并且從右向左計(jì)算)，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è)計(jì)的多層分段標(biāo)簽通過(guò)分段設(shè)計(jì)使其具備了雙標(biāo)簽的功效。標(biāo)簽共分為前后2段，分別為層號(hào)段與標(biāo)簽值段。層號(hào)段標(biāo)識(shí)基本塊所屬層次，記為BS1。標(biāo)簽值段則在同層內(nèi)標(biāo)識(shí)不同的基本塊，記為BS2。

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

規(guī)則3程序執(zhí)行時(shí)，全局動(dòng)態(tài)標(biāo)簽GS的更新語(yǔ)句在基本塊入口位置，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ù)層號(hào)段為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)簽層號(hào)段標(biāo)識(shí)層號(hào)。層號(hào)具備唯一性，且互相滿足1位不包含原則。一般來(lái)說(shuō)，層號(hào)僅取標(biāo)簽層號(hà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)控制流，即某一基本塊同時(shí)處于多個(gè)層級(jí)中，則該基本塊必為M型基本塊，且其層號(hào)為其所有前驅(qū)基本塊層號(hào)or運(yùn)算的結(jié)果。即：?bi∈B,bj1,…,bjn∈pred(bi),則BS2(bi)=BS1(bj1) or BS1(bj2) or…or BS1(bjn)。

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

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

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

(a) (b)

(c) (d)

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

(a)

(b)

(c)

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

引理2通過(guò)規(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í)行時(shí)，若標(biāo)簽在進(jìn)入基本塊前滿足GS=BS，則無(wú)論程序執(zhí)行至基本塊內(nèi)任何位置，仍滿足GS=BS。

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

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

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

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

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

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

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

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

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

證明：設(shè)?bi,bj∈B，程序發(fā)生錯(cuò)誤跳轉(zhuǎn)bj→bi，且程序運(yùn)行至bj前均正確執(zhí)行。因發(fā)生的是錯(cuò)誤跳轉(zhuǎn)，則bj?pred(bi)，根據(jù)規(guī)則6～規(guī)則9，BS(bj)≠BS(pred(bi))。程序運(yùn)行在至bj前均為正確執(zhí)行，故此時(shí)全局動(dòng)態(tài)標(biāo)簽與其期望值相等，即GS=BS(bj)。跳轉(zhuǎn)后，全局動(dòng)態(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)不相等，均會(huì)被檢測(cè)出來(lái)。

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

證明：?bi,bj∈B，程序發(fā)生錯(cuò)誤跳轉(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)簽更新語(yǔ)句，此時(shí)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，層號(hào)段的錯(cuò)誤會(huì)被檢測(cè)出來(lái)。

若bj與bi屬于相同層次，則錯(cuò)誤跳轉(zhuǎn)不會(huì)引發(fā)層號(hào)錯(cuò)誤。根據(jù)規(guī)則9，GS在錯(cuò)誤抵達(dá)bi前GS2=BS2(bj)≠BS2(bi)。據(jù)M型基本塊標(biāo)簽更新語(yǔ)句，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，無(wú)論bj是O型還是M型基本塊，BS1(bj)與BS1(bj)互相1位不包含。故GS2=BS2(bj) or BS2(bi)≠BS2(bi)，根據(jù)引理4，標(biāo)簽值段的錯(cuò)誤會(huì)被檢測(cè)出來(lái)。

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

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

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

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

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

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

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

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

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

Step3根據(jù)規(guī)則2按層劃分基本塊，根據(jù)規(guī)則7、規(guī)則8分配基本塊標(biāo)簽層號(hà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í)行時(shí)，指令進(jìn)行跳轉(zhuǎn)的目標(biāo)地址受軟錯(cuò)誤影響而改變，這會(huì)導(dǎo)致2種結(jié)果：

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

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

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

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

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

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

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

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

Step4使用GDB重新加載程序。

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

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

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

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

Step1啟動(dòng)GDB并加載要注入控制流跳出錯(cuò)誤的程序。

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

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

Step4使用GDB重新加載程序。

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

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

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

3.2 方法評(píng)估

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

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

圖6 不同加固方法錯(cuò)誤檢測(cè)性能

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

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

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

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

圖7 各方法的時(shí)空開(kāi)銷

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

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

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

4 結(jié)束語(yǔ)

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