一种多轴联动的指令级控制流检测方法

一种多轴联动的指令级控制流检测方法

1控制流错误检测随着电路特征尺寸的减小、晶体密度的增加、电源电压的降低和频率的增加，祖母的pn结越来越容易被高速带受控颗粒损坏，并且容易立即负载。例如，旧存储的第一个传输被拆分为0。处理器和计算机系统内部发生一位信息翻转的情况通常称为瞬时故障,又称单事件翻转(SingleEventUpset,SEU)。在程序执行过程中,当SEU故障对指令的操作码产生影响时,瞬时故障会造成程序的控制流错误。在航天计算和交通实时控制等对安全性要求很高的应用中,计算机的可靠性至关重要,因此,需要用容错技术对硬件系统进行加固。目前对控制流错误进行检测的方法主要包括硬件实现和软件实现2种。硬件实现方法通常基于硬件看门狗技术,通过从指令计算实时标记并与预先计算的标记进行比较来发现故障,其缺点是需要额外硬件或改造现有硬件,且不具有可移植性。目前用软件实现的控制流错误检测方法一般将程序代码分成各个基本块,每个基本块由一系列指令构成,除最后一条指令外,其他指令不能是分支指令。即基本块内部指令只能顺序执行,除第1条指令外,其他指令不能是分支指令的目标。因此,一个程序的控制流可以由各基本块以及连接基本块之间的边所构成的控制流程图表示。应用上述方法可以把一个程序原代码表示成由一个节点集V和一个边集E组成的程序控制流程图P={V,E},V={v1,v2,…,vi,…,vn},E={e1,e2,…,ei,…,em}。其中,节点vi表示第i个基本块;边ei表示一个从vi到vj的分支bri,j。对于程序控制流程图中的每个节点vi,可以定义其后续节点集suc(vi)和前趋节点集pred(vi),vj属于suc(vi),E中必须有一条从vi到vj的边bri,j。vj属于pred(vi),E中必须有一条从vj到vi的边brj,i。Stanford大学CRC实验室提出的CFCSS(ControlFlowCheckingbySoftwareSignatures)是具有代表性的控制流检测算法。CFCSS算法在程序编译时为每个基本块分配一个各不相同的数字标签S并生成控制流程图中各个分支对应的源节点和目标节点之间的差异d。CFCSS算法用一个称为GSR(GeneralSignatureRegister)的通用寄存器来存放程序执行时生成的动态节点标签G。在程序执行过程中把当前节点动态标签G和编译时存放在节点中的静态节点标签S进行比较,相等则说明无控制流错误发生,不相等则跳转到错误处理例程。CFCSS是一个纯软件的指令级方法,具有较好的控制流故障检错能力,但CFCSS存在匿名问题。法国TIMA实验室提出的DSM算法为每个合法分支分配一个标签,DSM可以检测SEU引发的所有控制流错误,但与未采用该算法加固的程序相比,性能下降了3倍,内存消耗增加4倍。本文提出一种基于路径跟踪的控制流检测(ControlFlowCheckingbasedonPathTracking,CFCPT)算法,在算法执行过程中用2个变量M,N对程序在控制流程图中经过的路径进行跟踪,以此来判断是否发生控制流错误。2节点上的控制流错误CFCPT算法在程序编译时为程序控制流程图的每个节点设置一个各不相同的数字标签S,当程序执行到控制流程图中的一个节点Vi时,用变量N(用专用寄存器N存储)记住当前节点的数字标签Si,在程序执行跳转前把变量N的值赋给变量M(用专用寄存器M存储)。跳转发生并到达目标节点Vj后,如果这次跳转合法,那么此时变量M的值应该是节点Vj某个前趋节点的数字标签,否则变量M的值不是节点Vj某个前趋节点的数字标签,因此,此时可以通过把变量M的值和节点Vj前趋节点的数字标签逐个进行比较,看是否有匹配发生,以此判断是否发生控制流错误。随着程序的不断执行,变量M,N的值不断被更新为程序执行所经过节点的数字标签,从而实现对程序执行路径的跟踪。在程序执行前,把变量N,M初始化成程序控制流程图中第1个节点的数字标签S0。CFCPT基本块结构如图1所示,SET断言和TEST断言的作用如下:SET1断言:N=Si,用变量N记住当前节点的数字标签。TEST1断言:brM≠pred(Vi)error,把变量M的值与当前节点所有前趋节点的数字标签进行比较,如果有匹配发生,则说明跳转合法,否则说明发生了控制流错误,执行转到错误处理例程。SET2断言:M=N,把变量N的值赋给变量M,从而实现对程序执行路径的跟踪。TEST2断言:brM≠Sierror,通过比较变量M和当前节点数字标签的值来检测非法分支跳入原基本块内部的情况。如图2所示,各节点的数字标签分别为S1=1011,S2=0010,S3=1000,S4=0110。当程序执行从节点V1跳转到节点V2的合法分支时,在执行离开节点V1后和到达节点V2前,变量M和N的值分别为M=1011,N=1011。跳转到节点V2后执行SET1断言,N的值被更新为N=0010,M的值不变,节点V2的前趋节点为V1,此时M=S1,因此,M=pred(V2),在TEST1断言处没有发现控制流错误。执行完原基本块内部的指令后执行SET2断言,此时M的值被更新为M=N=0010,最后执行TEST2断言,因为此时M=S2,所以在TEST2断言处没有发现控制流错误,说明此次分支跳转合法。发生非法分支从节点V1跳转到节点V4,当执行离开节点V1之后和到达节点V4之前,变量M和N的值分别为M=1011,N=1011。到达节点V4后,执行SET1断言,N的值被更新为N=0110,M的值不变。节点V4的前趋节点为V3且S3=1000,执行TEST1断言时发现M的值与S3不相等,检测出控制流错误。发生单个控制流错误的情况可以归纳为以下3类:(1)目标节点是源节点的后续节点。(2)目标节点不是源节点的后续节点。(3)基本块内指令跳转。如图3(a)所示的是当Vj∈suc(Vi)时的情况,图3(b)是当Vj∉suc(Vi)时的情况,8种分支中只有编号为0的情况是正确的,用CFCPT检测其他7种控制流错误:(1)当Vj∈suc(Vi)时编号1错误:因为跳过了节点Vj中的SET1断言和TEST1断言,所以寄存器N没有得到更新,仍然为Si。程序执行完原基本块的指令后,执行SET2断言把N的值Si赋给寄存器M,此时,当执行到TEST2断言处时,由于M≠Sj,因此检测出错误。编号2错误:从节点Vi原基本块内部跳转到节点Vj时,节点Vi内的SET2断言和TEST2断言都被跳过,因此,寄存器M没有得到更新仍然为Si,跳转发生后执行节点Vj内的TEST1断言时,由于此时寄存器M存储的值仍然是节点Vi某个前趋节点的数字标签,而不是节点Vj的某个前趋节点的数字标签,因此检测出错误。编号3错误:从节点Vi的原基本块内部跳转到节点Vj的原基本块内部时,节点Vi内的SET2断言和TEST2断言被跳过,节点Vj内的SET1断言和TEST1断言被跳过,因此,跳转发生后,M=Sh,Vh∈pred(Vi),执行节点Vj内的SET2断言时,M=N=Si,执行TEST2断言时,由于M≠Sj,因此可以检测到错误。(2)当Vj∉suc(Vi)时编号4错误:发生跳转时位于Vi节点后面的SET2断言和TEST2断言被跳过,M的值没有得到更新,仍然为Sh,Vh∈pred(Vi),由于Sh不是节点Vj某个前趋节点的数字标签,因此执行节点Vj内的TEST1断言时检测到错误。编号5错误:从节点Vi发生非法跳转到节点Vj时,由于M=Si不是节点Vj某个前趋节点的数字标签,因此执行节点Vj内的TEST1断言时检测到错误。编号6错误:发生非法分支时,节点Vj中的SET1断言和TEST1断言被跳过,执行节点Vj内的SET2断言时M=N=Si≠Sj,因此,执行节点Vj内的TEST2断言时检测到错误。编号7错误:与编号3错误类似。通过以上证明可以得出,在CFCPT算法中,如果SET1断言和TEST1断言是原子执行且SET2和TEST2是原子执行,那么CFCPT算法就能检测出节点间的所有控制流错误。但因为当节点间的非法分支直接跳转到TEST2断言时,N的值没有更新成Sj,所以M的值不会更新成Sj,被TEST2断言检测出错误。因此,在CFCPT算法中,只要SET1断言和TEST1断言是原子执行,就能检测出节点间的所有控制流错误。3程序结果的分析通过错误注入实验考查CFCPT的效率。本文采用LZW压缩算法、矩阵乘法、快速排序、汉诺塔4个基准程序来测试CFCPT的可行性和性能。实验中在基准程序汇编代码的各个基本块中插入检测指令并随机注入分支错误,然后汇编修改后的代码产生相应的机器代码,最后重复执行得到的机器代码400次。分别对以下4种情况进行实验:未采用检错措施,用CFCSS算法,用DSM算法以及用CFCPT算法。应用CFCSS,DSM,CFCPT技术之后,程序执行结果分为5种情况:(1)故障没有影响程序运算的最终结果;(2)故障被硬件错误检测机制检测出来,如除法运算中分母为0;(3)故障被采用的技术检测出来;(4)故障未被检测出,且程序运算的最终结果是错误的;(5)程序运行超时。采取CFCPT检测技术后,内存消耗和性能损耗数据如表1所示。从表1可以看出,CFCPT消耗的内存和性能比文献得到的实验数据略高,但比DSM消耗的内存和性能少很多。通过错误注入实验,采取不同检测策略得到的实验结果如表2所示。表2主要关注随机注入的分支错误在程序执行过程中没有被检测出来且影响程序结果的百分比,其他4种情况的结果对程序最终执行结果没有影响。可以看出,在采取CFCPT技术的情况下,注入的错误没有被检测出来且影响最终结果的百分比明显比CFCSS中的低。虽然DSM算法在理