基于控制流的软件树生成及其应用

何斌

(91404部队, 河北 秦皇岛 066000)

0 引言

软件故障树分析(Software Fault Tree Analysis,SFTA)主要用于软件的可靠性与安全性分析，也应用于软件测试的测试设计。软件故障树分析利用原因关系查找所有软件可能的失效点并画出故障树图，再定性、定量、重要度分析寻找可靠性安全性的薄弱环节，是指导设计改进、软件测试、装备维护的有效方法。故障树分析的成败取决于故障树图的完整性与准确性。然而在实施过程中软件故障树分析往往依赖于个人经验，没有一种全面定量的软件失效点分析方法，这导致了对软件系统进行分析时，会有很大的工作难度与强度，而结果却不近人意。当软件测试人员使用SFTA来进行测试设计时这一问题更加突显，原因是软件测试人员很难在测试周期内对被系统的失效点有全面的掌握。

为解决SFTA这一问题，研究采用基于控制流分析结果的软件故障树自动化分析技术，实现SFTA基于客观分析结果(控制流分析结果)，并可达到分析过程短周期及计算机自动化的目的。

1 软件故障树分析的基本理论

故障树分析(FTA)是产品(系统)可靠性和安全性分析的工具之一，用来寻找导致不希望的系统故障或灾难性危险事件(顶事件)发生的所在原因和原因组合，在具有基础数据时求出顶事件发生的概率及其他定量指标。FTA也是分析已经发生的事故的一种基本方法，在装备研发、维护等领域有广泛的应用。故障树分析也用在软件工程称之这软件故障树分析(SFTA)，在侦错时使用，和消除错误原因的技术很有关系。

故障树分析法是把系统不希望发生的故障状态定义为“顶事件”，通过分析寻找出导致顶事件故障发生的所有可能的直接原因，这些原因称之为“中间事件”。接着分析寻找一个中间事件发生的所在可能原因，经此类推，直到追踪到最后一级的原因事件，称之为“底事件”。

故障树分析就是从具体的故障出发，由上往下逐层寻找失效原因，分析结果采用图形化形式进行表示。故障树图是一种逻辑因果关系图，构图的元素是事件和逻辑门。事件用来描述系统和元、部件故障的状态，逻辑门把事件联系起来，表示事件之间的逻辑关系。

故障树图的具体构成,如图1所示。

对于一个稍微复杂的系统，将有数量较多的底事件，这不利于对系统可靠性、安全性定性、定量地分析。所以在确定故障树图后必须寻找最小割集。割集是故障树中一些底事件的集合，当这些同时发生时，顶事必然发生；最小割集就是若将割集中的含的底事件含意去掉一个就不再成为割集了，这样的割集就是最小算法。

图1 串口通信故障树图

求最小割集的方法有行列法、结构法、布尔代数法等，其中行列法最为常用。行列法是1972年福塞尔提出的方法，所以也称其福塞尔法。其理论依据是：“与门”使割集容量增，而不增加割集的数量；“或门”使割集的数量增，而不增加割集的容量。这种方法是从顶上事件开，用下一层事件代替上一层事件，把“与门”连接事件，按行横向排列；把“或门”连接的事件，按纵横向摆开。这样，逐层向下，直至各基本事件，出若干行，最后利用布尔代数化简。化简结果，就出若干最小割集。

2 基于控制流分析的软件故障树的实现原理

2.1 软件控制流分析

软件控制流分析是软件静态分析的主要内容，分析结果以控制流图表示。软件控制流图就是代码逻辑的图形化表示形式,图形圆绘制的代码,如图2所示。

图2 图形圆绘制的代码

图形圆绘制控制流图,如图3所示。

控制流图能表示一个过程内所有基本块执行的可能流向,也能反映一个过程的实时执行过程。控制流分析在软件测试中有助于测试人员寻找程序中的控制逻辑错误。有控制流图以后，可定量地获取程序的圈复杂度，而圈复杂度做一种为程序逻辑复杂性度量可有效指导进行编程质量改进，进而降低软件的故障风险。在软件测试中控制流分析一般由软件静态测试工具自动完成，常用测试工具有McCabe、Klocwork、LDRA_Testbed等。由于控制流图是由测试工具自动化完成，所以得到的控制图可以完整、准确地反应程序的内部逻辑结构。

图3 图形圆绘制控制流图

2.2 软件控制流到故障树图的实现原理

软件的故障树分析可沿软件控制流图的执行逻辑进行分析。软件控制流图中的执行单元可认为是一个中间事件，而引起这一的执行单元失效的所有可能就是底事件，所有底事件由“或门”连接而成。整个故障树的逻辑依从更高一层的控制流图逻辑结构。

依据控制流图的故障树图对应关系，如表1所示。

表1 故障树图与软件控制流图主要对应关系

3 “X型烟雾报警系统”从控制流图到故障树的分析过程

为进一步详述软件控制流图到故障树的分析过程，同时也为证明这一方法的可行性，本文以“X型烟雾报警系统”为例演绎这一过程。

“X型烟雾报警系统”主要用于封闭环境火灾的自动报警。系统通过温感与烟雾传感器对环境的温度和烟雾浓度进行实时监测，以超过设置温度、烟雾浓度判定是否发生火灾。当系统监测到超过预设温度、烟雾浓度时发出声光等形式的告警。开发方给出的系统流程图,如图4所示。

图4 “X型烟雾报警系统”流程图

很显然仅凭这一流程图进行故障分析将十分困难。基于控制流分析的软件故障树分析方法首先对系统源码进行控制流分析，得控制流图，如图5所示。

图5 “X型烟雾报警系统”控制流图

依从控制流图执行逻辑进行故障树分析，以控制流图逻辑结构为故障树图的结构，并充分考虑控制流图逻辑外的软件失效可能作为故障树的主要事件，具体步骤如下。

(1) 按流程图的基本块确定中间事件或底事件，同时根据软件实际功能补充可能的事件;

(2) 根据流程图的分支逻辑确定故障图树的逻辑门;

(3) 重复上述两个步骤直到整个流程图解读完成。

通过以上步骤构建“X型烟雾报警系统”的故障树图结构,如图6所示。

4 总结

通过演绎基于控制流分析的软件故障树分析是可行的。总结这一方法主要有以下几个优点。

(1) 故障树分析依赖于由工具软件获得的控制流图，分析过程更加客观、全面、高效。

图6 “X型烟雾报警系统”故障树图

(2) 基于控制流图的故障树分析不完全依赖于个人经验，有固定规律可循，工作难度将大大降低。

(3) 由于控制流图由工具软件自动生成且到故障树图的转换有模式可利于故障树分析计算机自动化的实现。

当然这一方法也有不足之处，如方法适合较为简小的嵌入式软件，不适应控制流图庞繁的系统软件；方法依赖代码的正确性，对设计、软件模式等故障无法触及。虽然这一方法有诸多局限性，但应用于周期要求短、覆盖率要求高的嵌入式软件测试的用例设计有较强的适用性。