改进的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.