文献标识码： A
DOI：10.16157/j.issn.0258-7998.2015.10.004
中文引用格式： 周改云，张国平，吕琼帅，等. 利用智能控制流方法的嵌入式软件故障检测[J].电子技术应用，2015，41(10)：20-23.
英文引用格式： Zhou Gaiyun，Zhang Guoping，Lv Qiongshuai，et al. Error detection of embedded software using intelligent control flow method[J].Application of Electronic Technique，2015，41(10)：20-23.
0 引言
嵌入式系统[1]应用非常广泛，基本随处可见，如卫星、汽车和飞机等，这些系统的错误行为可能导致灾难性事故，所以这些设备必须在最短时间内检测到故障。一般故障分为三类：永久性故障、间歇性故障和瞬时性故障，在这些故障中，瞬时故障最为常见，如程序计数器和存储器元件故障，可能会导致控制流错误(Control Flow Errors，CFES)，多达70％的瞬时故障导致程序执行的CFES[2]。因而，用于检查和解决基于控制流的方法对内存和性能的优化非常重要[3，4]。
文献[5]是一种划分程序为基本块的方法，它利用签名查找块之间的关系。通过在运行时间签名和每个块开始和结尾有额外指令引导的当前块的位置信息之间“取与”操作进行控制流故障检测。控制流检查(RSCFC)的特点是在低内存和低性能开销下可以找到更多故障[6]。该方法的内存和性能开销都接近CFCSS技术，但它的故障覆盖率更高。RSCFC基本块的总数受机器字长限制。
本文提出一种提高控制流检测效率的新方法，即在运用控制流检查方法之前，先处理程序代码，运用基于内核概念的候选块选择重要基本块[7]。执行内核所有顶点的任一测试集即执行流程图的所有顶点。本文方法的创新之处有：所用变量的频率和基本块的执行频率用于选择重要变量和基本块的两个参数；内核块用于重要基本块的选择；开发人员可以权衡检测延迟和性能开销。
1 提出的方法
本文提出一种以智能方式选择检测点。在候选块集中插入控制流断言，基于内核块选择候选块集。定义候选块集如下：
定义1(候选块集)：候选块集是具有控制流检查更高优先级的基本块，该集合可以基于内核和基本块频率来创建。
1.1 基于内核的块选择算法
本文方法基于文献[5]创建程序图，利用算法1找到基本块执行频率。如果检测延迟，则向用户询问表示检测延迟所需百分比的DL值。然后，使用式(1)计算L：
式中，L是必须插入到控制流检测点的块数，若检测延迟并不重要，控制流检查点将插入候选块集合。找到候选块集合后，基于它们的分类插入断言分类为两组。
另一种方法是候选块查找算法，如算法1所示。该算法用于计算候选块。首先计算程序流图的前后支配树，表示为Tpre和Tpost。接着，比较树Lpre和Lpost的叶子数，选择其中具有最小块数的一个为候选块集合。
如果性能对于用户很重要，候选块集合将用于断言控制流检查点。但是，若检测延迟比较重要，L将与候选块数相比较，若候选块数小于L，则该方法从Lpost·Lpre选择高频块，并添加它们到候选块集合。若它们为空，将在Tpre或Tpost树的h-1级运用该方法。通过这种方法，块将添加到候选块集合。
如果候选块数比L大，第一高频率执行节点将选择为候选块集合，断言将插入这些块。候选块集合将从后支配和前支配树基于混合选择节点创建。优先级将给予具有高频率执行和100％分支覆盖的块。
第三种方法是节点执行频率计算方法，即算法2，该方法获取程序图作为输入，并在每个块的开头插入计数器。在源代码中运用这些改变后，程序将运行5n次，其中n为程序节点数。
(1)算法1：基于内核的候选块查找算法的核心代码
Nominee-block-set-find(V,E,entry，exit，L)
{ Tpre=PREDOMINATORTREE(V,E,entry)；
Lpre=Tpre的叶子集；
Tpost=POSTDOMINATORTREE(V,E,exit)；
While(L>Nominee-block-count) {
If(T=1) Then {/*第一个if*/
If(LpostLpre非空且Des=0)Then {
从LpostLpre选择高频节点；
添加到候选块集；} Else {
Des=1；
Lpre=添加Tpre的h-1级的所有节点到Lpre；
Lpost=添加Tpost的h-1级的所有节点到Lpost；
h=h-1； }
If(Lpre非空)Then {
从Lpre选择高频节点；添加到候选块集；}
Else Des=0；
If(LpostLpre非空且Des=0) Then{从LpostLpre选择高频节点；
添加到候选块集；
} Else { Des=1；
Lpre=添加Tpre的h-1级的所有节点到Lpre；
Lpost=添加Tpost的h-1级的所有节点到Lpost；
h=h-1；}
If(Lpost非空)Then{
从Lpost选择高频节点；
添加到候选块集；
}
}
(2)算法2：块执行频率计算算法Find-basic-block-frequency(V，E)
{ Static int block-frequency[n]；/*n是程序图节点*/
For 所有节点<>从控制流图开始{
在块开始处添加block-frequency[i]++； }
While(i<=5n)
运行程序并保存(节点数，block-frequency)；
}
1.2 数据流错误检查
在程序中应用定义-使用链算法[8]确定变量频率，该算法表明变量到达链程序中的不同点。找到变量的定义-使用频率后，使用频率进行分类。本文提出的智能块选择方法如算法3：
(3)算法3：变量选择算法
{ 运用Reaching-definition-algorithm()；
基于UF分类变量/*UF是使用频率*/
Read(VFP)；/*从用户获取变量频率参数*/
For 所有变量
If(UFVFP) then 复制变量
}
1.3 基本块签名生成
本文方法中，签名生成与RSCFC方法类似，succ(vi)={vf，…，vk，…，vm}定义为vi的后继节点集，类似地，pred(vi)定义为vi的前驱节点集，基于程序流图P(V，E)。当且仅当bri，j∈E，节点vj∈succ(vi)。类似地，仅当brj，i∈E，节点vj∈pred(vi)。P执行期间，如果bri，j?埸E，bri，j非法，即控制流错误。如图1所示，succ(v2)={v3}，pred(v2)={v1}。如果存在从v2到v5的跳，则br2，5为非法跳，因为v5不属于succ(v2)。假设程序有n个基本块，标记为v1，v2，…，vn，则设置块vi的签名Si如下：
式中，上标1、f、k、m和n+1分别表示从低位开始Si的第1、第f、第k、第m和第n+1位，即如果程序有n个基本块，则基本块的签名应该总共有n+1位，其最高位n+1通常设置为“1”，Si中每一位，除了第n+1位，第2位表示节点v2，第n位表示节点vn，如果P中节点是vi的后继节点，则Si的对应位设为“1”，否则，设为“0”。
1.4 基于块间控制流检测的候选块
本文使用专用全局变量S检查程序的控制器，包含程序流图中当前节点相关的运行时间签名，当在程序图上运用候选块寻找算法时，划分块为候选成员块和普通成员块。
识别这些集后，在块中插入断言，引入Kernel-test断言到每个基本块开头，引入set断言到每个基本块末尾。当该控制从一个块vj转移到一个如vi的内核块时，Kernel-test断言使用下列两个值检查该目的节点vi是否合法：
(1)前一个节点的签名(分支的源节点，vj)；
(2)程序流图中当前节点的位置信息Li。
Li的创建类似于Si，但是仅设置Li的一位为“1”，该位表示程序流图中vi的数量为i。如图1所示，L1=000001，L5=010000。基本块vi的Kernel-test和set语句设计如下：
Kernel-test:If(S=S&Li)=0 error
在非候选块成员的块中插入上述断言，引入Kernel-free-test断言到每个基本块开头，引入set断言到每个基本块末尾。当该控制从一个块vj转移到另一vi的块时，在S中保存Si的值，直到候选块中检查它。Kernel-free-test和set语句设计如下：
Kernel-free-test:S=S&Li
修改的代码如图2所示，在插入排序图中运用内核算法之后，块划分成两类，块3和5是内核块，必须在它们上插入Kernel-test断言，但是块1、2、4、6是普通块，则在它们上插入Kernel-free-test断言。当取set断言时，S和Li执行异或操作结果为“0”，“-”的逻辑非将变为“-1”，最终，用新运行时间签名Si &(-1)=Si更新S。另一方面，假设节点vi不是vj的后继，则S&Li应该为0，执行节点vi的Kernel-test断言之后将检测到控制流错误，该控制将转移到错误处理例程。
2 实验结果与评估
2.1 原型实现
修改代码的生成过程如图3所示，本文使用C++实现上述方法，并在代码中插入断言，执行该程序寻找瞬时错误。该工作首先使用过滤器还原标准C语句为伪代码语句，还原不改变控制流的语句为空分号。然后，扫描仪获取伪代码，并发送它到解析器，进行程序的控制流图提取。之后，解析器提取程序的前后支配树，并在其上运用候选块寻找算法，进行节点分类。解析器的输出是程序图表和候选块信息，在源节点上运用算法1，获得块断言和变量。最后，生成如图3所示的修改代码。
2.2 实验评估
为了评估本文方法的有效性，比较修改代码和原始代码的内存大小和性能开销，还评估了两种情况下本方法的故障检测能力，并与RSCFC方法进行了比较，为了实现该比较，选择下列3个基准：（1）插入排序(IN)；（2）快速排序(QS)；（3）矩阵乘法(MM)。所有程序均在2G内存，Win7的i3 PC上执行。
使用AQtime6[9]配置软件估计性能和内存开销，表1和表2分别表示基于原始代码的RSCFC方法和本文方法的内存率、性能开销和固化代码大小，各个指标表示基准程序的倍数。
比较表1和表2，可以得出在候选块上运用本文方法能够降低性能开销，检测延迟(DL)基于下列公式：
最大故障检测延迟是W，如果在候选块上运用本文方法，最大故障检测延迟将为(N/L)×W。
根据上述公式，增加候选块数能降低故障检测延迟，如果候选块数降低，检测延迟也会增加。从表1和表2的“性能”列中可以观察到，本方法中程序执行时间少于RSCFC方法，且从表2的“性能”列可以看出，执行时间比率接近1，即程序执行时间几乎保持相同，但是固化代码能检测瞬时错误。
3 结论
本文运用控制流检测方法检测嵌入式软件故障，预处理包括使用高频变量和重要基本块的检测，改进了RSCFC方法中关系签名的有效性。此外，使用本文方法，使嵌入式软件开发人员能权衡检测延迟和性能开销。使用3个基准的实验结果表明，固化代码中程序执行时间少于RSCFC方法，但是内存开销和代码开销几乎相同，本文方法产生的固化代码与原始代码的程序执行时间几乎相同。
未来，将测试和评估在固化程序中由专业故障工具插入的故障，研究基于程序语义在程序中插入断言的新方法。
参考文献
[1] 张海军，王艳军，刘海见，等.基于ADS2的嵌入式软件测
试仿真建模方法研究[J].电子技术应用，2014，40(6)：
17-19.
[2] MOHAMED A，ZULKERNINE M.A connection-based signature approach for control flow error detection[C].Dependable，Autonomic and Secure Computing(DASC)，2011IEEE Ninth International Conference on.IEEE，2011，24(7)：129-136.
[3] PRASAD K S S.Embeded technology for vehicle cabin safety monitoring and alerting system[J].Middle-East Journalof Scientific Research，2014，20(12)：2210-2212.
[4] 王超，傅忠传，陈红松，等.低代价锁步EDDI：处理器瞬时故障检测机制[J].计算机学报，2012，35(12)：2562-2572.
[5] ASGHARI S A，KAYNAK O，TAHERI H.An investigation into soft error detection efficiency at operating system level[J].The Scientific World Journal，2014，24(18)：1047-1053.
[6] 徐建军.面向寄存器软错误的容错编译技术研究[D].长沙：国防科学技术大学，2010.
[7] 朱雪梅.基于动态方法的嵌入式软件缺陷检测技术研究与实现[D].杭州：杭州电子科技大学，2013.
[8] LAM M，SETHI R，ULLMAN J D，et al.Compilers：princi-ples，techniques，and tools[J].2006，22(12)：852-857.
[9] Automated Q A.AQtime[EB/OL].(2010)[2015].http：//www.automatedqa.com/products/aqtime/.