利用智能控制流方法的嵌入式软件故障检测*

周改云，张国平，吕琼帅，黎远松

（1.平顶山学院 软件学院，河南 平顶山 467000；2.四川理工学院 计算机学院，四川 自贡 643000）

利用智能控制流方法的嵌入式软件故障检测*

周改云1，张国平1，吕琼帅1，黎远松2

（1.平顶山学院 软件学院，河南 平顶山 467000；2.四川理工学院 计算机学院，四川 自贡 643000）

针对现有的嵌入式软件故障检测方法性能低、开销大的缺点，提出一种智能选择检测点的控制流方法，其创新之处主要为：使用变量的频率和基本块的执行频率用作选择重要变量和基本块的两个参数。检测的基本流程是首先过滤器还原标准C语句为伪代码语句，然后扫描仪获取伪代码，并发送它到解析器，进行程序的控制流图提取。最后，解析器提取程序的前后支配树，运用候选块寻找算法进行节点分类，获得块断言和变量。实验结果表明，固化代码中程序执行时间少于RSCFC方法，但是内存开销和代码开销几乎相同，执行时间比率接近1，显著提高故障检测率。

嵌入式软件；智能选择；控制流；内核块；基本块

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：基于内核的候选块查找算法的核心代码

(2)算法 2：块执行频率计算算法 Find－basic－blockfrequency(V，E)

1.2数据流错误检查

在程序中应用定义－使用链算法[8]确定变量频率，该算法表明变量到达链程序中的不同点。找到变量的定义－使用频率后，使用频率进行分类。本文提出的智能块选择方法如算法3：

(3)算法3：变量选择算法

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　插入排序函数的控制流图

式中，上标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语句设计如下：

在非候选块成员的块中插入上述断言，引入Kernelfree-test断言到每个基本块开头，引入set断言到每个基本块末尾。当该控制从一个块vj转移到另一vi的块时，在S中保存Si的值，直到候选块中检查它。Kernel-freetest和set语句设计如下：

修改的代码如图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　实验结果与评估

2.1原型实现

修改代码的生成过程如图3所示，本文使用C++实现上述方法，并在代码中插入断言，执行该程序寻找瞬时错误。该工作首先使用过滤器还原标准C语句为伪代码语句，还原不改变控制流的语句为空分号。然后，扫描仪获取伪代码，并发送它到解析器，进行程序的控制流图提取。之后，解析器提取程序的前后支配树，并在其上运用候选块寻找算法，进行节点分类。解析器的输出是程序图表和候选块信息，在源节点上运用算法1，获得块断言和变量。最后，生成如图3所示的修改代码。

图3　修改代码生成的过程

2.2实验评估

为了评估本文方法的有效性，比较修改代码和原始代码的内存大小和性能开销，还评估了两种情况下本方法的故障检测能力，并与 RSCFC方法进行了比较，为了实现该比较，选择下列 3个基准：（1）插入排序(IN)；（2）快速排序(QS)；（3）矩阵乘法(MM)。所有程序均在2G内存，Win7的i3 PC上执行。

使用AQtime6[9]配置软件估计性能和内存开销，表1和表2分别表示基于原始代码的 RSCFC方法和本文方法的内存率、性能开销和固化代码大小，各个指标表示基准程序的倍数。

比较表1和表2，可以得出在候选块上运用本文方法能够降低性能开销，检测延迟(DL)基于下列公式：

表1　运用RSCFC方法后的内存和性能开销

表2　运用本方法后的内存和性能开销

最大故障检测延迟是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)，2011 IEEE 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 Journal of 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：principles，techniques，and tools[J].2006，22(12)：852-857.

[9]Automated Q A.AQtime[EB/OL].(2010)[2015].http：//www. automatedqa.com/products/aqtime/.

Error detection of embedded software using intelligent control flow method

Zhou Gaiyun1，Zhang Guoping1，Lv Qiongshuai1，Li Yuansong2
(1.School of Software，Pingdingshan University，Pingdingshan 467000，China；(2.School of Computer Science，Sichuan University of Science&Engineering，Zigong 643000，China)

As the existing embedded software error detection method has low performance and big cost,a control flow method of intelligent selection of detection point is proposed.The ruain innovation is that variable frequency and fundamental frequency for blocks are used as two important variables.The basic process is to detect filter restore the standard C code statement to the pseudo-code statement firstly.Then,the pseudo-code is obtained by scanners,and the code is send to the parser,and the control flow graph is extracted.Finally,the before-after dominant tree parser is extracted by procedures,and the node classification is done by the algorithm of finding candidate block.And the block assertions and variables are obtained.Experimental results show that the running time of the proposed method is less than that of RSCFC method in curing codes,but the memory cost and code cost are almost the same,and the execution time ratio is close to 1.The error detection rate is remarkably improved.

embedded software；intelligent selection；control flow；core block

TP391

A

10.16157/j.issn.0258-7998.2015.10.004

平顶山学院青年基金重点项目(PDSU-QNJJ-2013002)；企业信息化与物联网测控技术四川省高校重点实验室项目(2014WZY05)

2015-06-01)

周改云（1980－），女，硕士，讲师，主要研究方向：嵌入式、软件工程等。

张国平（1980-），男，硕士，讲师，主要研究方向：软件工程、嵌入式与软件开发，移动通信应用等。

吕琼帅（1985-），男，硕士，讲师，主要研究方向：软件工程、智能算法等。

中文引用格式：周改云，张国平，吕琼帅，等.利用智能控制流方法的嵌入式软件故障检测[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.