基于表驱动的纯软件签名错误检测算法

,,,,

(1.国家电网浙江省电力公司信息通信分公司,杭州 310007; 2.华东师范大学 计算机科学与软件工程学院,上海 200062)

0 概述

随着技术的发展,微处理器性能的改善将越来越依赖于体积更小、速度更快的晶体管,不同于制造与设计性错误等频繁产生的错误,临时性错误(也常被称作软错误),常常会导致不可预测的行为。最典型的软错误是单粒子翻转(Single Event Upset,SEU),该错误指的是发生在顺序逻辑以及单粒子瞬变(Single Event Transient,SET)中的位翻转,容忍这些错误的首要步骤就是检测出这些错误,目前已有相当多的错误检测技术。

错误检测可以通过纯硬件方式、软硬件结合方式以及纯软件方式得以实现。一种常用的纯硬件检错方式运用了MOTOROLA M68040微处理器[1],该处理器通过监测外部总线和主处理器的行为,实现并发的系统级错误检测,但却导致了时间和面积开销的增大,并且随着具有内部高速缓存和现代流水线技术的微处理器的广泛应用,这种纯硬件检错方式已经显得不必要了。当前用于错误检测的软硬件混合型的检错方式也有很多,例如Argus[2]和CRAFT[3]。Argus基于冯诺依曼型处理器核,可检测出核中除输入输出、异常、中断部分的其他错误。然而,包括通过纯软件签名的控制流检测(CFDSS)[4-5]、通过断言的控制流检测(ACFC)[6]、运用断言的增强型控制流检测(ECCA)[7]、通过冗余指令[8]的错误检测(EDDI)[9-11]等在内的纯软件处理方法,比上述这2种概念运用得更加广泛,因为这些纯软件检错方式不要求特定的硬件设备提供支持。ACFC在执行过程中赋予每一个基本块一个奇偶校验位,可检测出奇偶性错误;EDDI采用复制指令,并通过插入合适的检测指令进行验证,但这种方法易导致代码容量增加近100%以及性能方面的损失[12-13]。本文在研究CFDSS算法的基础上,提出一种基于表驱动[14-15]的控制流错误检测算法,使用一张二维表和签名来监测目标程序的控制流。

1 相关研究工作

文献[4,7]中关于软件签名和断言算法,提出的最重要的解决办法就是CFDSS技术和ECCA技术。这2种技术能实现很高的错误检测覆盖率,但也存在一些不足,以下进行简要的介绍和分析。

CFDSS是一项纯软件错误检测技术,该技术中涉及的每一个基本块都被赋予一个特殊的签名。一个全局变量(记为G)包含动态签名,被初始化为程序中第一个基本块的签名。如果程序执行过程中没有出现控制流错误,G应等于当前程序执行基本块中存储的签名。

两个基本块间的跳转发生之后,结合前驱节点和后继节点(当前节点)的签名,G通过异或运算进行更新。如果控制流来源于多个块,则每一个源块被赋予一个调整的签名,这些签名将被用于目标块中动态签名的计算。

ECCA赋予每一个基本块2个标示符:

1)块标示符(Block Identifier,BID):用不同的素数值表征每一个基本块。

2)控制流标示符(Control Flow Indicator,CFID):通过存储与下个基本块的BID的乘积值来表示控制流。

CFID被存储在初始化值为第一个基本块的CFID的二元队列中。当控制流进入一个基本块时,该基本块的CFID就被压入队列,在该基本块的出口处被弹出队列,并且将CFID与该基本块的BID相除。因为每个BID均由素数组成,CFID与BID相除后总是返回一个零值,除非程序执行了一个错误的控制流跳转。当存储CFID的队列出现上溢或下溢时,错误也将会被检测出。

因为CFDSS是一项纯软件检测方式,所以不需要额外的硬件支持。然而,同样的签名必须被赋予多个节点,即共享扇入节点的情况同样会发生。如果多个基本块共享同样的基本块目标地址,CFDSS就无法检测出其中发生的跳转错误,这是该项技术的不足之处。

ECCA在算法中采用取余和除法运算,增加了算法本身的开销。另外ECCA通过除法中分母为0引起异常来检测控制流错误,与系统错误混淆,同时异常开销也非常大。

基于上述2种算法的优缺点,提出EDSS算法的关键在于使用了一个被称为CFID表的二维表存储基本块和控制流的全部信息。本文在文献[14]研究的基础上,进一步优化了算法,能更好地运用CFID表检测出控制流图中非法跳转错误。

2 控制流错误检测技术

2.1 控制流图

本文提出的控制流错误检测方法采用了基本块的概念。基本块指的是一串连续的指令,程序从基本块中的第一条指令开始执行,在执行完最后一条指令后离开基本块。除了基本块中的最后一条指令不做要求外,基本块中的其余指令均不允许为分支指令、跳转指令或者调用指令。

控制流图由节点集合V={v1,v2,…,vi,…,vn}和路径集合E={e1,e2,…,ei,…,em}组成,使用控制流图,能准确描述程序P的控制流,即程序P可表示为P={V,E}。一个节点vi表示一个基本块,其中i为正整数,表示基本块在程序中的位置。一条路径表示从vi到vj的分支bri,j。路径bri,j不一定总代表分支指令,也可表示跳转、子程序和返回指令等。

suc(vi)定义为后继节点的集合,pred(vi)定义为前驱节点的集合。这表示如果vj属于集合suc(vi),则bri,j就一定包含在E中,如果vj是pred(vi)中的一个元素,则brj,i就包含在E中。如果bri,j未被包含在E中,则该跳转指令就是非法的,即当一个非法指令分支被执行时,控制流错误就会发生。若pred(vi)中的元素个数大于2,则vi就是一个分支扇入节点。在本文中后继节点即为当前节点。

2.2 控制流图及其CFID表

签名监测技术在编译时将签名赋给控制流图中一个或多个节点构成的目标基本块,并在动态执行时生成同样的签名,再与静态存储的签名进行比较。CFDSS通过异或操作并运用已赋值的签名对程序控制流进行检测。就像在CFDSS中提及的,如果多个节点共享多个分支扇入节点作为目标节点,非法与合法的分支间将会发生混淆,从而导致不可检测的控制流错误的产生。

本文结合有限状态自动机(Finite State Machine,FSM)理论和控制流图的基本原理,提出基于编译时生成的控制流图(对应于CFID表)及应用软件签名的错误检测技术(Error Detection of Software Signature,EDSS),这与先前在CFDSS中使用的方法完全不同。运用EDSS的技术,多于2个分支扇入节点中产生的非法指令分支错误也将被检测出。EDSS的检测技术的另一大优势在于它的简洁性,在本文的检测指令中,无需按位异或操作指令来计算动态签名,而仅需要在每个基本块上进行比较操作。

以图1中的样例路径所示,每一个圆圈为一个节点,代表一个基本块,且基本块被赋予一系列递增的正整数值作为标志符,即v1,v2,…,接着编译时,软件签名SSi被赋给对应节点vi。为使算法的赋值规则便于运用在实现和检测中,SSi就等于相应的节点vi的标志符值,即如图1所示,SS1=0001,SS2=0002…将在之后部分进一步说明这个规则为查找二维表带来的极大便利。

图1 控制流图及其节点签名

签名在编译时被赋给各基本块。同样地,在程序控制流图的基础上用于存储签名的二维表也是在编译时建立的。EDSS技术的核心特点之一就是这张本文称为CFID表的二维表的建立。这张CFID表本质上就是一个二维数组,对应i行j列位置上的数值即为CFID[i,j],这代表控制流中的位置标识和跳转路径。行数值i表示前驱节点的标识号,列数值j表示当前节点的标识号。以二维表中的一个元素CFID[i,j]为例,它表示从节点vi到节点vj的一条分支。如果bri,j是一条允许的分支,即SSj被存储在CFID[i,j]中,且SSj不等于0。否则,如果0被存储在CFID[i,j]中相应位置上,就表示bri,j不是一条合法的指令。当程序首次执行时,值为0的元素CFID[0,0]被读入,CFID表由此从主存被载入到高速缓存器cache中以提高查表速度。

图2就是与图1中表示的控制流图相对应的CFID表。该CFID表中的空格默认为已填入了0值。同时由于br1,3、br2,4、br2,5…均为合法的分支,后继节点的签名SS3、SS4、SS5…就相应地按照前述规则被分别存入CFID[1,3]、CFID[2,4]、CFID[2,5]…中。

图2 存储签名的CFID表

2.3 控制流检测机制

本节将基于3种可能情况运用3个具有代表性的例子阐释提出的软件签名检测技术EDSS的具体功能:合法的分支,不合法的分支以及带有2个共享分支扇入节点的非法分支等的错误检测机制。

图3是对不带共享扇入节点的允许执行分支的检测,图中所有基本块都已被标识且编号。如图3左边所示,每一个基本块都被赋予了不同的且与它们自身位置标识相等的数值。图3右边表明了检测指令是如何进行错误检测的。当程序执行到v3时,在接着执行v3中的指令之前,先执行SS3与CFID[Reg,SS3]的比较。Reg是一个用于存储动态签名的全局变量,该全局变量被储存在分配好的寄存器中。如果SS3与CFID[Reg,SS3]的相等关系成立,即若brReg,3是一条合法的分支,则Reg将被更新为SS3,且该基本块中的原指令将被继续执行,直到程序执行到下一基本块v6。接下去SS6与CFID[Reg,SS6]的比较同上个基本块一样被执行。如果brReg,6是一条非法的分支,则CFID[Reg,SS6]对应的值一定为0而不是SS6,错误语句被执行,从而控制流错误被检测出。

图3 合法指令跳转的检测

图4表示一条非法跳转指令的执行以及该错误是如何被检测出的。这种情况下的控制流错误可分为2种情况:一种指向if条件语句的非法跳转;另一种指向下一基本块中间位置的非法跳转。在非法跳转br1,4被执行前,Reg有原值SS1。前一种情况下,当程序执行到v4的if 语句时,CFID[Reg,SS4]从存储在缓存器cache中的二维CFID表中读出,并且由于br1,4是不被允许的,CFID[Reg,SS4]对应的值为0。因此,这种不匹配导致接下去的error指令将控制流转移到出错处理程序中。

图4 非法指令跳转的检测

而在后一种情况下,跳转到基本块中间部分的非法跳转在EDSS的支持下也可被检测出来。但是由于分支跳过了v4的检测指令,检测产生延迟。从v1到v4的非法跳转产生,程序控制转移到v4中的一条指令。Reg保持v1中的签名不变,直到程序在执行了v4中的指令后运行到v7。显然,这种情况下CFID[Reg,v7]的对应值为0,这与SS7不同,所以,条件分支指令“ifSS7≠CFID[Reg,SS7] error elseReg=SS7”应跳转到出错处理程序。

图5显示了多个节点共享多个分支扇入节点作为目标节点的情况。在CFDSS技术下易发生指令跳转混淆的问题,但EDSS技术为该相对复杂的问题提供了简单的解决办法,避免了混淆问题的出现。在图5中,v7为一个有3个前驱节点v3、v4、v5(pred(v7)={v3,v4,v5})的分支扇入节点。根据上文讨论的算法,SS7被分别填入CFID[3,7]、CFID[4,7]和CFID[5,7]中。节点v8也是一个分支扇入节点,但只有2个前驱节点v4、v5,不包括v3,即pred(v8)={v4,v5}。因此,CFID[4,8]和CFID[5,8]中均存储着SS8,而CFID[3,8]中存储着0值。程序允许的跳转指令br4,7、br5,8以图3中显示的相同方式被检测和执行。假设一条非法跳转br3,8出现,并执行到v8的检测指令位置,在该位置进行CFID[Reg,8]与SS8的比较。Reg在该非法跳转执行前的值为SS3,且CFID[3,8]在二维CFID表中的对应值为0,因此该控制流错误就被检测出来了。

图5 2个共享分支扇入节点的非法指令跳转的检测

如果非法的指令分支指向目标基本块中除if-else检测指令之外的其他位置,其中产生的控制流错误一样可通过未在v8中进行更新的全局变量Reg被检测出。由此得出只要各个节点被赋予了签名,建立了基于EDSS算法的二维CFID表,EDSS的技术就可避免CFDSS中新产生的无法检测出的非法指令跳转错误。

为了获得对本文所做的为改善软件签名监测技术的整体工作的理解,将在下一部分总结表述EDSS算法。

2.4 EDSS算法

类似CFDSS的算法设计,EDSS的算法相比之下更加简洁和高效。节点中没有嵌入指令来计算动态运行时的签名,同样,也没有多余的指令在运行过程中调整签名。当一个程序进行编译时,EDSS算法给程序控制流图中的每一个节点赋予了一个签名,N等于程序中的节点总数。

EDSS算法设计步骤如下:

步骤1确定所有基本块,建立程序的控制流图,为每一个节点编号,即基本块标识号,在控制流图中以自然数开始,即vi,i=1,2,…,N。

步骤2对每一个节点vi都赋予一个签名SSi,如果i≠j,则SSi≠SSj,其中i,j=1,2,…,N。每一个签名SSi都与相应的基本块的标识号相等。

步骤3对每一个vi,j=1,2,…,执行:

1)对每一个分支bri,j,它的前驱节点为vi,后继节点为vj。这些分支由一个二维表表示,该二维表称为CFID[i,j]。在该表中,行i表示前驱节点,列j表示后继节点。

2)如果分支bri,j在控制流图中,SSj填入CFID[i,j]对应的位置。否则CFID[i,j]位置应填入0值。

3)Reg寄存器中存储的全局变量在基本块每一次执行其检测指令时都更新一次,以跟踪程序执行过程中签名的变化。

4)在基本块的初始位置插入指令“ifSSi≠CFID[Reg,SSi] error elseReg=SSi”。

3 仿真实验结果

考虑到本文提出的EDSS算法是一项增强型的签名监测技术,但采用了与CFDSS相比完全不同的错误检测方式,因此,对EDSS及CFDSS中错误检测的覆盖率、开销代价等进行缜密的分析是不可或缺的。相应地,这一部分就集中于对仿真实验结果的评估分析。在导入实验之前主要将射入的错误分为2类:一类为不带共享分支扇入节点程序中生成的错误;另一类为在包含2个或更多共享扇入节点程序中产生的错误。对应不同的程序,执行过程中本文的目的在于比较这2种技术的行为与错误检测能力。

为了评估本文提出的基于表驱动的控制流检测技术EDSS的可行性和有效性,用C程序分别实现了EDSS算法和CFDSS算法,并分别实施了一系列错误射入实验,测试了这2种技术的错误覆盖率和开销代价。相比之下,实验结果证实这2项技术中的错误检测能力在被用于检测带有第1类错误的程序时是相类似的,但当程序中射入第2类错误时,EDSS技术就拥有了绝对优势。

聚焦于不带共享扇入节点的程序中出现的第1类错误,为比较EDSS和CFDSS,实验中选择了4个基准测试程序:1)LZW(压缩程序);2)FFT(快速傅里叶变换程序);3)矩阵乘法运算程序;4)快速排序。其中,LZW和FFT是相对较大的基准测试程序。EDSS和CFDSS这2个算法都是用C语言实现的,通过比较应用EDSS技术写出的程序以及参照应用CFDSS写出的程序的检错覆盖率,结果记录在表1中。从表1中的数据可以看出,EDSS在FFT和快速排序上的检错覆盖率比CFDSS高出约1.5%,在LZW和矩阵乘法上与CFDSS几乎具有相同的检错覆盖率。由此可知,EDSS具备比CFDSS更好的错误检测能力,满足错误检测的要求。

表1 CFDSS和EDSS的检错覆盖率 %

需要注意的是无法应用上述基准测试程序检测出EDSS和CFDSS在带有2个或多个共享分支扇入节点的程序中的表现,因为有2个或多个共享分支扇入节点的构造产生的可能性很小,在这些基准测试程序中均很难找到。因此,表1的数据并不能全面评价EDSS的检错覆盖率。

鉴于上述原因,本文决定根据图5所示的控制流图构造测试的程序。对有多扇入节点程序的检错能力的评估如表2所示,实验中获得的数据极好地证实了EDSS的错误检测能力,在具有1个共享分支扇入节点和2个嵌套的共享分支扇入节点,以及1个共享分支扇入节点的循环测试程序中,EDSS算法的检错率比CFDSS算法平均高出约1.9个百分点,原因是有些分支跳转错误只能通过EDSS技术检测出而无法通过CFDSS技术检测出,而这恰好与在前述讨论过的算法中提出的分析相符合。

表2 多扇入节点问题中的检错率 %

在算法增加的代码空间开销方面,EDSS算法略优于CFDSS算法。EDSS算法在对签名的计算方面不要求在程序中插入计算动态签名的指令,这就相应地减少了插入指令的数目。在这方面,CFDSS技术给每个基本块设置了3条指令,而EDSS技术给每个基本块仅设置2条指令。但EDSS算法需要在内存中存储CFID表,这需要一定的代码空间开销。

除代码空间开销以外,其他影响系统开销的关键性因素也是值得关注的。系统开销是通过检测技术中额外指令的使用数量计算得到的,因此这是一个与编译时插入的多余指令相关的问题。由于EDSS算法较CFDSS算法所需要插入的指令数量更少,对于性能代价,EDSS与CFDSS相比具有相对更高的性能优势。同时也考虑到,在EDSS算法中,错误检测指令需要从CFID表中读取后继节点的签名,这将直接影响指令的执行效率。对于这个问题的解决办法为,在程序初始化时,在初始化用于存储动态签名的全局变量Reg的同时,通过将CFID[0,0]赋值给Reg,达到使CFID表装载到高速缓存cache中,实现表1中数据的高速读取。因此,EDSS算法检测指令的减少有助于提高程序执行的速度,并有助于改善EDSS技术的性能指标。

因此,实验结果表明,从错误检测覆盖率、代码空间开销以及对程序性能影响等方面,EDSS算法是一种具有优势的纯软件签名错误检测技术,对比于已有的CFDSS错误检测技术,在不增加代码空间开销和对程序性能影响更小的前提下,解决了CFDSS算法不能检测的2个或多个共享扇入节点非法跳转的问题,提高了控制流错误检测的覆盖率。

4 结束语

在纯软件签名的控制流检测技术(CFDSS)的基础上,基于有限状态自动机原理,本文提出了基于表驱动的纯软件签名错误检测算法(EDSS)。编译时,控制流图中的信息,包括各节点之间的关系,都是通过构建一张二维CFID表表达的。表中存储着控制流图合法路径中目标节点的签名。当出现非法跳转时,通过检测赋予变量Reg的签名和表中存储的目标节点的签名,控制流错误能被可靠地检测出。根据这种方法,共享多于2个扇入节点导致的非法指令跳转错误也可由本文提出的算法得以检测。实验结果显示,EDSS算法平均错误检测覆盖率为98.1%,比CFDSS算法高出1.3%,在共享分支扇入节点的测试程序中,EDSS算法的检错率比CFDSS算法平均高出约1.9个百分点,并且EDSS技术在每个基本块中为错误检测插入的指令数相对更少。

[1] BENSO A,CARLO S D,Natale G D,et al.A watchdog processor to detect data and control flow errors[C]//Proceedings of the 9th IEEE International On-line Testing Symposium.Washington D.C.,USA:IEEE Press,2003:144-148.

[2] NATHAN R,SORIN D J.Argus-G:comprehensive,low-cost error detection for GPGPU cores[J].IEEE Computer Architecture Letters,2015,14(1):13-16.

[3] REIS G A,CHANG J,VACHHARAJANI N,et al.Design and evaluation of hybrid fault-detection systems[J].ACM Sigarch Computer Architecture News,2005,33(2):148-159.

[4] SEVERINOVA H,ABAFFY J,KRAJCOVIC T.Control-flow checking using binary encoded software signatures[C]//Proceedings of Innovations and Advances in Computing,Informatics,Systems Sciences,Networking and Engineering.Berlin,Germany:Springer,2015:345-347.

[5] 李静梅,吴艳霞,沈 晶,等.改进的CFDSS控制流检测算法[J].哈尔滨工程大学学报,2011,32(6):814-819.

[6] NAZARIAN G,RODRIGUES D G,MOREIRA A,et al.Bit-flip aware control-flow error detection[C]//Proceedings of Euromicro International Conference on Parallel,Distributed and Network-based Processing.Berlin,Germany:Springer,2015:215-221.

[7] LI Aiguo,HONG Bingrong.On-line control flow error detection using relationship signatures among basic blocks[J].Computers and Electrical Engineering,2010,36(1):132-141.

[8] 张 鹏,朱 利,杜小智,等.基于结构化标签的控制流错误检测算法[J].计算机工程,2016,42(6):37-42.

[9] ALWI H,EDWARDS C,TAN C P.Fault detection and fault-tolerant control using sliding modes[M].Berlin,Germany:Springer,2015.

[10] 高 星,廖明宏,吴翔虎.空间机器人高可信软件检错技术[J].计算机工程,2009,35(16):56-58.

[11] MIAO S,DOU W,LI Y.An error-detecting approach for fault tolerance parallel recomputing with parallel digital terrain analysis[J].Journal of Algorithms & Computational Technology,2016,34(10):539-542.

[12] 李剑明,谭庆平,徐建军,等.基于路径跟踪的控制流检测[J].计算机工程,2009,35(20):68-70.

[13] 杨 挺,孙雨耕,张志东,等.无线传感器网络异构驱动路由算法[J].计算机工程,2016,42(3):7-12.

[14] JU Xiaoming,ZHANG Helen,WANG Aoran.Error detection by software signatures based on control flow graph[C]//Proceedings of International Conference on Future Computer and Information Technology.Berlin,Germany:Springer,2013:51-63.

[15] 谷晓钢,江荣安,赵铭伟.无线传感器网络异构驱动路由算法[J].计算机工程,2008,34(19):12-14.