改進的CFCSS控制流檢測算法

李靜梅，吳艷霞，沈晶，張健沛

(哈爾濱工程大學 計算機科學與技術學院，黑龍江 哈爾濱 150001)

空間輻射環境中，宇宙射線、地磁俘獲輻射帶、太陽質子事件都能導致航天器電子系統中的半導體器件發生單粒子效應，單粒子效應引發的瞬時故障嚴重影響航天器的可靠性和壽命.這些帶電粒子在航天器電子系統中產生的瞬時擾動即使持續時間很短，但對某些應用系統，可能是致命的破壞.1997年1月11日美國的Telstar401衛星，因太陽引起的空間環境擾動而損壞，導致北美的尋呼機和長途電話大面積發射中斷，不良影響甚至波及到了金融、股票市場的正常運行.研究表明在1992至2011年間，組合電路中的瞬時故障率將增加9個數量級［1］.

從上面的論述不難看出，微處理器瞬時故障問題正日益彰顯，是研究人員關注的熱點問題.單粒子翻轉(single event upset，SEU)［2-3］、單粒子瞬態脈沖效應(single event transient，SET)［4-5］等瞬時故障，會導致運行程序的數據流、指令流及控制流錯誤，但幾率最大、危害最大的是改變指令序列執行順序的控制流錯誤［6］.

文中首先分析總結了控制流檢測算法的原理，其次，分析CFCSS算法原理［7-8］，并簡述其中存在的檢測混淆和檢測出錯現象的原因;最后，根據CFCSS算法中存在的問題，修改了基礎基本塊的選擇方法和多調整簽名值賦值語句的插入位置，提出了改進的ICFCSS算法(improved CFCSS).

1 控制流圖與基本塊

為了方便描述控制流檢測算法，在此引入幾個定義.

定義1 控制流圖(control flow graph，CFG)可表示為G={V，E}，V={vi|vi為控制流基本塊，1≤i≤n，n為控制流基本塊號}，E={(vi，vj)|表示控制流從vi跳轉到vj，vi為源基本塊，vj為目的基本塊}.

定義2 e－(vi)為基本塊vi的輸入邊，即直接指向vi的邊.e+(vi)為基本塊vi的輸出邊，即從vi引出的邊.pred(vi)表示vi的e－(vi)集合.suc(vi)表示vi的e+(vi)集合.deg－(vi)(deg+(vi))為基本塊vi的入(出)度，即Pred(vi)(Suc(vi))集合中元素的個數.多扇入基本塊集VMI={vi|deg－(vi)＞1，i為控制流基本塊數}.多扇出基本塊集VMO= {vi|deg+(vi)＞1，i為控制流基本塊數}.

2 控制流檢測算法原理

將傳統的控制流錯誤檢測能力分析方法中的基本塊結構定義為圖1，稱為帶簽名檢測的基本塊(checking basic-block，CB).

圖1 帶簽名檢測的基本塊結構Fig.1 General basic block with inserted signatures

控制流錯誤檢測算法的一般過程為:首先，根據基本塊定義，以基本塊為單位生成程序的控制流圖;其次，根據簽名生成算法為每個基本塊生成編譯時簽名值;然后，分析源基本塊和目的基本塊之間關系，根據控制流檢測算法生成冗余檢測指令，將其插入源程序中，生成帶控制流檢測的程序;最后，在程序運行時通過冗余檢測指令判斷是否發生控制流錯誤.因此，控制流檢測算法主要描述以下4個方面的內容:

1)確定檢測基本單位.控制流檢測錯誤算法主要以基本塊為基本單位進行控制流檢測.

2)簽名生成算法(SIN_GEN).基于簽名的控制流檢測技術是將編譯時生成的簽名作為檢測算法的一個參數，根據簽名值的特征進行判斷.簽名值可以通過控制流圖中基本塊的位置信息表示，也可以通過編碼等方式表示.

3)簽名檢測算法(SIN_FUN).簽名檢測算法是控制流檢測技術的核心，通過簡單、有效的方法判斷是否發生控制流錯誤.

4)檢測指令插入位置.根據具體的檢測方法將控制流檢測指令插入到基本塊首部、中間或尾部，不同的控制流檢測方法其檢測指令插入的位置各不相同.

3 CFCSS算法原理及存在問題分析

3.1 CFCSS算法原理

CFCSS算法是基于匯編語言的控制流檢測算法，以基本塊為單位進行檢測，算法描述如下.

輸入:待加固的匯編語言.

1)根據基本塊定義方法對標準匯編程序劃分基本塊，構建程序流圖.為每個基本塊vj∈V分配唯一編譯時簽名值sj，si≠sj，其中if i≠j，i，j=1，2，…N，N是程序中總的基本塊數.

2)分析基本塊間關系，插入為G和D賦值的語句，G為運行時生成的源基本塊簽名值，D為編譯時生成調整簽名值.對于每個基本塊vj，j=1，2，…，N，判斷其deg－(vj)是否大于1.

1)如果deg－(vj)=1，pred(vj)={vi}，生成簽名差dj=si⊕sj;生成簽名檢測函數:G=G⊕dj，br(G≠sj)，將其插入到基本塊入口.

2)如果deg－(vj)＞1，pred(vj)={vi，vk，…，vn}，引入調整簽名值D.

①如果存在集合S={vi|deg+(vi)＞1，vi∈pred(vj)}，任選集合S中一個基本塊作為基礎基本塊，生成基本塊vj的簽名差dj=si⊕sj.對于基本塊vi，插入指令Dn=si⊕si，該指令必須位于br(G≠si) error指令之后.對其余基本塊vn∈pred(vj)－vi，插入指令Dn=si⊕sn，該指令必須位于br(G≠sn) error指令之后.生成簽名檢測函數:G=G⊕dj，G= G⊕D，br(G≠sj)error，將其插入到基本塊首部.

②如果不存在集合S={vi|deg+(vi)＞1，vi∈pred(vj)}，任選{vi，vk，…，vn}中一個基本塊作為基礎基本塊，生成基本塊vj的簽名差dj=si⊕sj，對其余基本塊vn∈pred(vj)－vi，插入指令Dn=si⊕sn，該指令必須位于br(G≠sn)error指令之后;生成簽名檢測函數:G=G⊕dj，G=G⊕D，br(G≠sj)error，將其插入到基本塊首部.

輸出:帶有控制流檢測指令的匯編語言，圖2為插入檢測指令后的基本塊.

圖2 帶檢測指令的基本塊Fig.2 The basic block with checking instructions

3.2 CFCSS算法中存在的問題

3.2.1 混淆現象

圖3中基本塊deg+(v1)＞1，優先選擇其為基礎基本塊，將調整簽名值設為0，即基本塊v1的D= 0，因此，基本塊v3、v4的簽名差d3=s1⊕s3、d4=s1⊕s4，基本塊v2中插入調整簽名D=s1⊕s2.此時如果發生從基本塊v2錯誤跳轉到v3，在基本塊v3首部進行控制流檢測，更新特殊寄存器G:

更新后的G等于s3，CFCSS算法無法檢測此類型的控制流錯誤跳轉.

圖3 混淆導致無法檢測的控制流錯誤Fig.3 An undetectable control flow error caused by aliasing

3.2.2 檢測出錯現象

圖4中，當deg－(vi)＞1時，優先選擇基本塊vi為基礎基本塊，將其調整簽名值設為0.根據算法，可選擇基本塊 v5作為簽名差 d5=s1⊕s5，同時deg－(v1)＞1，所以基本塊v5的源基本塊的調整簽名值分別為:D1=s1⊕s1，D2=s1⊕s2，D3=s1⊕s3，基本塊v6的簽名差是d6=s3⊕s6，那么從基本塊v3處跳轉到基本塊v6的正確控制流進行檢測，更新的G為G=G6=f(Gprev，d6)⊕D=(G3⊕d6)⊕(s1⊕s3)= (s3⊕(s3⊕s6))⊕(s1⊕s3)≠s6，CFCSS算法將正確的控制流檢測為發生錯誤跳轉.

圖4 控制流檢測錯誤Fig.4 Control flow checking error

上述闡述說明，CFCSS算法存在的檢測漏洞和檢測出錯現象都會導致算法檢測能力的降低.

4 ICFCSS算法原理

造成檢測漏洞和檢測出錯現象的主要原因是調整簽名D的生成算法存在問題，根據匯編語言結構特點，本文修改了CFCSS算法中調整簽名D的生成算法，提出了ICFCSS算法.

4.1 ICFCSS算法描述

匯編級控制流圖的基本塊滿足e+(vi)≤2，控制流圖由多(單)扇出、多扇入基本塊構成，如圖5所示.

圖5 匯編語言結構分類Fig.5 Classification of the assembly language structures

圖5中基本塊v1的deg－(v1)=1，為單扇入結構.通過分析得出:基本塊v1的結束標識為絕對跳轉指令或者為不改變程序控制流的順序指令.

圖5中基本塊v3的deg－(v3)＞1，為多扇出結構，通過分析得出:基本塊v3的結束標識為條件跳轉指令，suc(v3)={v2，v1}，基本塊v3跳轉執行到基本塊v2、v1中任一基本塊，順序執行另一基本塊.

圖5中基本塊v1的deg+(v1)＞1，為多扇入結構.通過分析得出:基本塊v1的開始標識一定為形如00106$的標號.

4.2 算法描述

Foreach 每個基本塊vj分配唯一編譯時簽名值sj，其中si≠sj，if i≠j，i、j=1，2，…，N，N為程序中基本塊總數.

End for

Foreach 每個基本塊vj，生成簽名差d、多調整簽名M及控制流檢測函數，其中檢測函數中的G、M為2個特殊寄存器

if pred(vj)只有一個基本塊vi，

生成基本塊vj的簽名差dj:dj=sj⊕sj，在基本塊vj首部插入控制流檢測函數:G=G⊕dj，br(G≠sj) error，dj為剛生成的立即數

elseif pred(vj)由一系列基本塊vi，vk，…，vm組成，引入多調整簽名M，

if存在集合 S={vi|deg－(vi)=1，vi∈pred(vj)}，

任選集合S中一基本塊vi作為基礎基本塊，生成基本塊vj的簽名差dj:dj=si⊕sj，由于deg－(vi)=1，則基本塊vi的結束標識為絕對跳轉指令或非跳轉指令.

if基本塊vi結束標識為絕對跳轉指令

在其之前插入指令Mn=0

elseif基本塊vi結束標識為非跳轉指令

在基本塊vi最后一條指令之后插入指令Mn=0

End if

Foreach 基本塊vn∈S－vi

if基本塊vn結束標識為絕對跳轉指令

在其之前插入指令Mn=si⊕sn

elseif基本塊vn結束標識為非跳轉指令

在基本塊vi最后一條指令之后插入指令Mn= si⊕sn

End if

End for

Foreach 基本塊 vm∈pred(vj)－S－vi，由于deg－(vm)＞1，則基本塊vm的結束標識為條件跳轉指令，基于匯編語言的條件跳轉指令可以理解為順序執行和跳轉指令的合體，設suc(vm)={vj，vk}

if基本塊vj為基本塊vm跳轉后執行的基本塊

在基本塊vm的條件跳轉指令之前插入指令

Mm=si⊕sm

elseif基本塊vj為基本塊vm順序執行后的基本塊

在基本塊vm的條件跳轉指令之后插入指令

Mm=si⊕sm

End if

End for

elseif如果不存在集合S={vi|deg－(vi)=1，vi∈pred(vj)}

任選{vi，vk，…，vn}中一基本塊vi作為基礎基本塊，生成基本塊vj的簽名差dj:dj=si⊕sjForeach 基本塊vn∈pred(vj)－vi，設suc(vn)= {vj，vk}

if基本塊vj為基本塊vn跳轉后執行的基本塊

在基本塊vn的條件跳轉指令之前插入指令

Mn=si⊕sn

elseif基本塊vj為基本塊vn順序執行后的基本塊

在基本塊vn的條件跳轉指令之后插入指令

Mn=si⊕sn

End if

End for

End if

在基本塊vj首部插入控制流檢測函數:G=G⊕dj，G=G⊕M，br(G≠sj)error

End if

End for

ICFCSS算法根據匯編語言結構特點，在編譯時分析基本塊結束指令類型，在基本塊相應位置插入多調整簽名M的賦值語句，具體示例如圖6.

圖6 修改后的帶多態調整簽名的基本塊Fig.6 Modified basic block with multi-adjusting signature

CFCSS算法和ICFCSS算法主要不同:

1)調整簽名D和多調整簽名M的賦值語句位置和數目不同.在編譯時CFCSS算法的調整簽名D的賦值語句插入到檢測判斷指令后的固定位置，而ICFCSS算法需要判斷基本塊結束指令類型，在相應指令的前后插入多調整簽名M的賦值語句.同時，根據CFCSS算法在每個基本塊中最多插入一條為調整簽名D賦值的語句，而ICFCSS算法在基本塊中最多插入2條為多調整簽名M賦值的語句.

2)基礎基本塊的選擇原則不同.設存在vi∈pred(vj)，CFCSS算法選擇原則:如果存在deg－(vi)＞1時，優先選擇基本塊vi作為基礎基本塊，將其調整簽名D設為0.ICFCSS算法選擇原則:如果存在deg－(vi)=1時，優先選擇基本塊vi作為基礎基本塊，將其多調整簽名M設為0.

4.3 ICFCSS算法示例分析

圖7和圖3具有相同的控制流結構，圖7中基本塊 v3的 pred(v3)={v1，v5}，基本塊 v4的pred(v4)={v1，v2}，基本塊v2的deg－(v2)=1，基本塊v5的deg－(v5)=1.根據ICFCSS算法，如果多扇入基本塊為 vj，存在基本塊 vi∈pred(vj)，當deg－(vi)=1時，優先選擇vi作為基礎基本塊，將基本塊vi的M設為0.因此設置基本塊v2、v5分別為基本塊v4、v3的基礎基本塊.通過分析基本塊v2、v5的出度數得出，基本塊v2、v5的結束標識為絕對跳轉指令或者是除跳轉指令以外的其他順序指令，因此在基本塊v2、v5的絕對跳轉指令之前或順序指令之后插入M=0.由于基本塊v1的deg－(v1)＞1，此基本塊結束標識一定為條件分支跳轉指令，即目的基本塊v4、v3中必有一個為順序執行的程序.設v3為順序執行的基本塊，因此在基本塊v1的條件跳轉指令之前插入對基本塊v4的多調整簽名M的賦值語句M=s1⊕s2，在基本塊v1的條件跳轉指令之后插入對基本塊v3的多調整簽名M的賦值語句M=s1⊕s5.此時發生如圖7虛線所示的控制流錯誤時，更新G為

G=G3=f(Gprev，d3)⊕M=(G3⊕d3)⊕0000= (s3⊕(s3⊕s5))≠s3

可以檢測出此種錯誤.

圖7 基于ICFCSS算法的控制流錯誤跳轉示例Fig.7 Example of control flow error jumping based on ICFCSS algorithm

圖4中，根據ICFCSS檢測算法，當deg－(vi)= 1時，優先選擇基本塊vi作為基礎基本塊，將其多調整簽名值設為0.基本塊v5的pred(v5)={v1，v2，v3}，根據算法選擇基本塊v2作為基礎基本塊，基本塊v5簽名差d5=s5⊕s2，那么對于基本塊v5而言其M=s2⊕s3.基本塊v6的pred(v6)={v7，v3}，此時基本塊v6的簽名差是d6=s7⊕s6，那么對于基本塊v6而言，其M=s7⊕s3.如果按基本塊v3跳轉到基本塊v6的正確控制流跳轉進行檢測，由于deg+(v3)＞1，所以基本塊v3的結束標識為條件判斷語句.經過判斷，基本塊v3順序執行到基本塊v6，那么在執行條件判斷語句之后插入M=s7⊕s3.如果基本塊v3跳轉執行到基本塊v6，那么在執行條件判斷語句之前插入M=s7⊕s3.更新的G為G=G6=f(Gprev，d6)⊕M=(G3⊕d6)⊕(s7⊕s3)=(s3⊕(s7⊕s6))⊕(s7⊕s3)=s6，ICFCSS算法沒有出現將正確的控制流檢測為錯誤情況.

5 實驗及分析

采用R80515微處理器作為實驗對象，通過源碼開放的SDCC編譯器將待加固的程序編譯成匯編代碼，采用Flex++詞法分析器編寫預處理程序，應用正則表達式方法分析生成的匯編語言，在此基礎上劃分基本塊，產生加入控制流檢測算法的控制流圖.最后，通過解釋器、鏈接器生成機器碼，通過軟件模擬器測試加固程序.通過二項分布的概率模型將錯誤灌入修改操作指令等信息的0、1代碼，造成分支消減、生成分支、改變分支操作等錯誤運行現象.對以下4種標準程序進行故障注入:初始數據為20 ×20的矩陣相乘(MM)、冒泡排序(BS)、快速排序(QS)及插入排序(IS).

在插入控制流檢測指令之后，程序執行結果可分為5種情況:

1)程序發生控制流錯誤，未檢測出控制流錯誤，程序運行結果正確，如:當指令之間存在WRW相關;

2)程序發生控制流錯誤，未檢測出控制流錯誤，程序運行結果錯誤;

3)程序發生控制流錯誤，檢測出控制流錯誤，程序運行結果正確;

4)程序未發生控制流錯誤，而檢測出控制流錯誤，程序運行結果正確;

5)程序未發生控制流錯誤，而檢測出控制流錯誤，程序運行結果錯誤.其中，第1、3、4種情況都不會影響程序的下一步運行，第2、5種情況會導致錯誤擴散，所以測試時比較算法的未檢測出錯誤情況.

表1 未檢測出錯誤比較Table 1 Result comparison of the undetected error %

表2 空間開銷比較Table 2 Memory overhead comparison %

表3 時間開銷比較Table 3 Performance overhead comparison %

從表1得出ICFCSS算法的未檢測出錯誤率明顯低于CFCSS算法，但從表2得出ICFCSS算法的代碼空間開銷和時間開銷略高于CFCSS算法.ICFCSS算法雖然略微增加了檢測代碼的空間和時間開銷，但很大程度提高了CFCSS算法的檢錯能力，且算法的時間復雜性是線性對數階的，空間復雜性是線性階的，實用性較強.

6 結束語

本文提出的ICFCSS控制流檢測方法，修改了CFCSS算法的基礎基本塊選擇方法和多調整簽名M賦值語句的插入位置，解決了CFCSS算法中存在的檢測混淆現象和檢測出錯現象.ICFCSSHS算法的平均未檢測出錯誤率僅為2.9%，生成的冗余代碼空間和執行時間開銷也較低，具有一定實用價值.但此方法只適用在目的基本塊首部判斷控制流跳轉情況，無法檢測基本塊內控制流錯誤跳轉，有待進一步改進檢測算法，降低未檢測出錯率.

［1］賀朝會，李永宏，楊海亮.單粒子效應輻射模擬實驗研究進展［J］.核技術，2007，30(4):347-350.

HE Chaohui，LI Yonghong，YANG Hailiang.Research progress in simulation experiment of single event effects［J］.Nuclear Technology，2007，30(4):347-350.

［2］IROM F，FARMANESH F H，JOHNSTON A H，SWIFT G M，MILLWARD D G.Single-event upset in commercial silicon-on-insulator PowerPC microprocessors［J］.IEEE Trans on Nuclear Science，2002，49(6):3148-3155.

［3］SWIFT G M，FANNANESH F F，GUERTIN S M，et al.Single-event upset in the PowerPC750 microprocessor［J］.IEEE Trans on Nuclear Science，2001，48(6):1822-1827.

［4］陳盤訓，周開明.模擬電路的單粒子瞬時效應［J］.核技術，2006，29(3):194-197.

CHEN Panxun，ZHOU Kaiming.Single particle transient effect of analog circuit［J］.Nuclear Technology，2006，29 (3):194-97.

［5］STERNBERG A L，MASSENGILL L M，SCHRIMPF R D，et al.Effect of amplifier parameters on single-event transients in an inverting operational amplifier［J］.IEEE Trans Nucl Sci，2002，49(3):1496-1501.

［6］王同權，戴宏毅，沈永平，等.宇宙高能質子致單粒子翻轉率的計算［J］.國防科技大學學報，2002，24(2):11-13.

WANG Tongquan，DAI Hongyi，SHEN Yongping，et al.Calculation of single particle turnover rate caused by cosmic high-energy proton［J］.Journal of National Defense University，2002，24(2):11-13.

［7］MITRA S.Diversity techniques for concurrent error detection［J］.Stanford:Stanford University，2000:21-36.

［8］PRATA P，SILVA J.Algorithm based fault tolerance versus result-checking for matrix computations［C］//Proc of 29th InternationalSymposium on FaultTolerantComputing (FTCS-29).Madison，USA，1999:4-11.