软件故障树算法建模的研究

段明璐

（华北计算技术研究所 软件测评中心，北京 100083）

0 引言

科技在发展，软件已经渐渐随着信息化的普及而与我们的生活密不可分，然而，它的生产过程又和其他产品有很大不同。不管是国家级的软件项目还是个人开发的共享软件，都或多或少地存在各种各样的缺陷，我们不可能对所有缺陷都进行关注和修复，但有的缺陷带来的恶劣后果是大到我们无法接受的，甚至会造成诸如人员伤亡、财产损失的重大事故，比如 1996年欧洲的 Ariane火箭，由于程序溢出引起了爆炸，又如90年代美国Therac25型放射治疗仪软件，由于设计缺陷导致了群体死亡事件的发生，我们必须想办法尽量避免此类问题的产生[1]。

很多软件公司试图在软件交付用户之前找到所有的缺陷进行修复，但这是不现实的，因为这依赖于成本、进度、资源等诸多因素。因此开发者应该对缺陷进行分析，依据分析结果来确定可能导致严重问题的因素和模块，这样就可以有针对性的调整准则规范、测试范围和测试程度，以此来杜绝同类缺陷的再次发生，在成本进度与质量之间找寻一个相对合理的平衡点，由此判断何时软件可以相对成熟的交付给用户使用[2]。

本文的主要目的是依据笔者经历过的大型项目中出现过的典型重要缺陷类别，结合故障树建模方式构建一个基于贝叶斯算法的典型软件故障树算法分析模型，在缺陷数据的基础上，探索出适合大型软件测试使用的、质量要求高的、基于贝叶斯网络的软件故障树建模及分析方法。用于降低国内软件企业在大型项目中对重要缺陷分析的难度和成本，为其他单位使用软件故障树分析的方法进行缺陷分析开拓思路、提供参考。

1 软件故障树模型的研究

1.1 软件故障树的相关概念

1.1.1 基本概念

软件故障树分析法是把软件系统及其应用环境看成一个整体来考量的分析方法，其最终目的是为了找到包含在软件设计和实现中的可能导致软件系统发生故障的错误，并且会导致软件系统功能失效的环境条件[3]。

软件故障树分析方法一般有以下两种应用情况：

（a）对软件系统已发现的重大缺陷进行分析，以便找到导致其产生的根本原因，及时制定纠正措施；

（b）在项目前期，针对用户使用中可能造成严重后果的情况或是用户最在意最担心出现的情况进行分析，在可能导致这种情况产生的模块中加强设计规范检查或是测试，从根本上扼杀出现这些情况的可能性。

软件故障树分析法使用的基本符号与一般故障树是一样的，具体符号及其意义[4]如表1所示。

用简化的方式来描述，软件故障树分析法就是把软件使用中最不希望出现的严重缺陷作为软件系统故障的分析对象，然后寻找会直接导致此类缺陷发生的全部因素，再继续找出直接造成下一级事件发生的全部因素，直到跟踪到无需再探明其发生原因的因素为止。

产生这个最不希望出现的严重缺陷的事件，我们称之为“顶事件”，也就是软件故障树的“树根”，用规定的逻辑符号表示。而最终无需再探明其发生原因的因素事件称为“底事件”，也叫“基本事件”。在找出所有可能导致这一缺陷产生的直接因素和原因的过程中，那些介于顶事件与底事件之间的事件称为“中间事件”。

表1 故障树的基本图元表Tab.1 The basic sign of fault tree

对于所有的故障树而言，不管它的层次有多深，包含的因素有多复杂，它都只有三个逻辑层次，即顶事件-最小割集-底事件[5]。

1.1.2 建模方法

故障树建模的最初流程是要确定故障树的分析范围，包括可能产生的事件，也包含所分析的问题、系统设计的水平、系统的使用层面、其它的运行环境条件等细节。故障树应以能清晰地表示导致顶事件发生的各结构事件的形式构建。

当明确定义了顶事件、系统的类型和分析的范围后，故障树就可自上而下的进行构建了。从顶事件开始分析其导致发生的直接事件，并通过适当的门建模和表示。然后这些事件又成为起因，逐层地展开各自的原因事件。每个事件分别自上而下地发展各自的故障树，当达到最底事件时，故障树的构建就完成了[6]。

故障树分析随着事件自顶向下逐步展开，并确定事件的原因。故障树分析可采用定性的分析或定量的分析，或者两者混合使用。应用故障树分析的定量分析可确定哪些事件对顶事件有较大影响及一些高概率事件发生的原因。例如，若系统中某一模块的故障发生概率较高，对系统故障的影响较大，那么便可对其原因进行调查分析，找出其明确的原因，减小其失效模式的影响。举例简单说明，未在界面中对特殊字符做校验这个问题对界面系统故障概率有较大影响，那么编写相应的测试用例校验界面可减小保存操作的故障概率，系统的故障概率也随之减小。

1.2 贝叶斯网络的相关概念

1.2.1 基本概念

贝叶斯网络[7-9]是一种结合图论和概率论来阐述知识的方法，通过这种方法建立的模型是可以进行概率计算的。从直观上描述，贝叶斯网络就是一个赋值的复杂因果关系网络图，网络中的每个节点代表了一个事件，各事件之间的弧表示事件发生的因果关系。

下面介绍贝叶斯网络的基本概念：

（1）随机变量的属性

包括两类属性，即变量的状态和概率。

（2）条件概率

假设事件A和事件B之间不是相互独立的，且已知事件B发生，我们可以得到 P （ A）的相关信息，即A在B中的条件概率 P （ A | B）：

（3）先验概率和后验概率

无条件概率 P （ A）被称为先验概率，它一般是根据之前的经验数据分析得到的概率，在全概率公式中是“持因求果”问题中的因；而条件概率 P （ A |B ）则被称为后验概率，是在已知结果信息的情况下对概率的修正，是“由果寻因”问题中的因，相比先验概率，后验概率是基于最新信息对原概率估计的更接近实际情况的修正。

（4）联合概率

假设事件 A和事件 B同时发生，那这个概率P（ A ∩ B）就被叫做A和B的联合概率。

（5）相关公理

1. 所有事件A的概率均满足0<= P （ A）<=1；

2. P（ Ω ）=1；

3. 假设事件A和事件B相互独立，则

（6）条件独立性

如果 P （ AB）= P （ A ） P（ B），则可判断事件A和事件B之间是相互独立的。

（7）乘法规则

（8）贝叶斯定理

假设空间S包含有n个互斥事件，每个事件被称为S的一个划分：

对于 S中的任意一个事件B，可以描述为由 n个不相交事件1BA,2BA,3BA,...,nBA组成，即：

转化为全概率定律可以表示为：

进一步结合条件概率就可以得到贝叶斯公式[10]：

其中 P (A1), P ( A2),..., P ( An)是在初始就知道得到它们以概率分布的形式，这就是先验分布。假设在求果的过程中事件 B发生了，这就导致事件A1,A2,A3,…,An产生的概率出现变化，也就是P（ Ai | B），这个概率由式6可以得出，它是在发生变化之后对原先估计修正得出的，因此是后验概率。P( A1|B)，P( A2|B)，…， P ( An|B)形成了一类分布，也就是后验分布。它结合了先验概率和求果过程中的新变化，形成了关于事件A发生概率的最新信息。这个由先验概率向后验概率的转化，就是贝叶斯统计方法最主要的特征。

1.2.2 贝叶斯网络的建立方法

贝叶斯网络是由有向无环图和条件概率表[11]两部分组成的，图1就是一个简单的贝叶斯网络。

图1 典型贝叶斯网络图Fig.1 The classic bayesian network

（1）有向无环图：Directed Acyclic Gragh，简称DAG，属于贝叶斯网络的定性部分，其中节点代表随机变量，可以解释为任何事物的抽象，节点具有以下特点：

1. 所有节点可以是连续或是离散的；

2. 所有节点可以有两个或者更多的状态；

3. 所有节点可以是确定型的或是可能型的。

而节点之间的有向边则代表了节点的因果关系，贝叶斯网络规定了图中每个节点 X i与由其父节点给定的非 X i后代节点构建的节点子集条件独立，也就是说如果用 M ( X i)表示非 X i后代节点构建的节点子集，用 P a( X i ) 表示 X i的父节点，则可得出条件独立性假设公式[12]：

（2）条件概率分布：CPD，属于贝叶斯网络的定量部分。

条件概率表：Conditional Probability Table，简称CPT，是反映变量间是否存在关联的概率分布集合，可以用式（8）中的 P a( X i | P a( X i) )来表示，它表达了节点同其父节点间的条件概率，而没有父节点的条件概率就是先验概率。每个节点的条件概率一般都在条件概率表中进行存放。

邱兵兵(1989—)，男，山东潍坊人，博士生，研究方向为非线性船舶运动控制。E-mail：bbqiu.dmu@gmail.com

当已知节点及其相互关系（有向边）和条件概率表，通过贝叶斯网络就可以表达出组成网络所有节点的联合概率，而且可以通过先验概率或是某些节点的概率，计算出其他任意节点的概率。联合概率的计算公式如下：

由此可得出图1中贝叶斯网络的联合概率分布公式为：

贝叶斯网络可以表达出节点的联合概率分布，并且可以使节点的联合概率求解大大简化。

以下给出一个工程实例来对贝叶斯网络的结构做具体说明，如图2所示。

贝叶斯网络的构建主要包括以下四个步骤[13]：

（1）首先我们需要定义待解决的问题，也就是确定构建模型所需的X和Y，即网络模型的起始节点和终止节点。

（2）然后开始构建贝叶斯网络结构。因为网络结构是一个有着多节点的有向无环图，因此第一步是添加图中的节点，把全部X设为起始节点，全部Y设置为总结节点。如果发现X会直接影响Y，则将该X节点直接指向Y节点。如果只是间接影响到Y，则需要在网络中添加中间节点，先将X节点指向中间节点，然后该中间节点经过指向后最终要连接到Y节点上。通过上述方法就构建出贝叶斯网络的初步架构。在这个步骤中，如果要确定两个节点之间是否存在推理关系，往往需要依赖于大量历史数据和领域专家的经验，主观性较高。

图2 软件输入异常案例Fig.2 The case of software inputting exception

（3）计算每个节点的概率表，即各节点对其他节点影响程度的概率。这个步骤同样需要依赖于专家经验和历史数据确定两个节点的条件概率，然后依据贝叶斯定理公式（7）来构建两个节点之间的推理关系。

（4）对贝叶斯网络进行验证。因为贝叶斯网络的构建过程毕竟有很多因素是主观性较强的，构建后应该通过实际案例进行校验，查看网络模型是否与实际情况一致，并不断进行调整完善。

1.3 故障树向贝叶斯网络的转换

从图形表示方式来看，故障树与贝叶斯网络有很多相似处，两者均通过推理建立图形内部联系[14]。故障树从顶至下逐步探索问题原因，贝叶斯网络从底至上计算问题在某种情况下的发生概率。两者定性定量的结合可以更好的解决问题。故障树的推理过程是逻辑性较强的过程，并且有多种逻辑门的支持，而贝叶斯网络的节点和有向边建立的连接性更灵活，运用范围更为广泛，更易于表示更丰富的信息内容，加上贝叶斯网络节点概率值依赖于构建专家的经验数据，使问题的解决更切合实际。

为软件测试问题找最终原因是一个相对主观又复杂的过程，为了使这个过程的因果分析更严密，采用故障树分析技术可以起到很好的理论支撑作用。而由于测试的软件领域不同，软件开发的人员团队特点，每类问题的原因又有一定的差别，这种差别的量化表示就需要贝叶斯网络这种建立在某种条件下的概率来更为清晰的描述。因此，建立起同一软件问题的故障树模型和贝叶斯模型，并将两者转换结合共同使用就显得尤为重要。具体怎样建立起事件与节点的转换，逻辑门与有向边的转换在文章的算法建模研究中会进一步探讨。

2 软件故障树建模实例分析

2.1 软件测试缺陷数据分析

软件行业的产品质量因素受软件组织所处的成熟度阶段、软件领域等诸多因素的影响，所以软件组织测试所产生的缺陷问题也是千差万别的，缺陷的相关信息以及原因也不尽相同，这就要求软件缺陷分析的基础数据在特定范围进行采集。收集并分析的统计数据有实时性及行业相关性，还受开发团队、开发进度要求等条件的限定，所以采集的项目测试数据的分析结果为采集对象服务，也就是说通过数据分析出的问题的纠正措施和解决方案是为数据来源企业量身定制的，不能适用于所有企业单位，这也是软件工程不同于其他传统学科的原因，没有任何一个模型可以全面覆盖所有的软件工程过程，实现数据的通用，实现完全的自动化，甚至在某种特定情况下还需要统计人员根据实际情况结合经验数据作出主观判断。

根据业界成熟的缺陷分类方法 ODC及缺陷分析方法根本原因（Root Cause）方法对历史数据进行分析分类，收集缺陷不同维度的属性信息进行整理，从中挖掘出有用的信息作为对缺陷原因进行逐层分析直至最终确定缺陷产生原因数据集。最终整理信息表《缺陷分类表》、《缺陷溯源表》，如表2、表3所示。

《缺陷分类表》是根据测试项目数据分析总结而成的典型缺陷集，未涵盖所有缺陷，只是重点测试类型重点项目出现频度较高的测试问题的部分范例。

《缺陷溯源表》本文也只列出了18类错误中的4类作为范例。针对《缺陷分类表》中的问题，结合《缺陷溯源表》中数据采用故障树建模方法可较快速地找出缺陷问题的原因。

表2 缺陷分类表Tab.2 The classification of software defect

表3 缺陷溯源表Tab.3 The tracing of software defect

2.2 软件故障树快速建模

按照故障树的建造流程分析建造软件故障树，首先确定建模的范围，也就是确定顶事件。在《缺陷分类表》中选取第16个问题“点击报表打印按钮，按钮点击后，页面跳转到一空页面”作为此次建树的顶事件，将这个顶事件简称为“打印无效”。确定了顶事件后，开始寻找导致其发生的直接事件，然后这些事件又成为起因，逐层地展开各自的原因事件，此时结合表格《缺陷溯源表》可得出表4如下：

这个顶事件被确认为级别为“二级”的测试问题，对二级问题的定义为“严重问题，系统需求未实现或欠缺、不完整、没有达到要求”，使用故障树建模方式解决此类问题会更方便。

此表中数据为从《缺陷溯源表》中逐步分析选取的原因，根据历史数据及建表人的经验信息最终找到问题根本原因，此时将这个表格的各个事件自上而下地以故障树的形式表示出来，当表示完最后一个底事件节点后，这颗软件故障树就快速的构建完成了，如图3所示。

2.3 软件故障树向贝叶斯网络的转换

从表示故障树和贝叶斯网络的图形组成结构看，故障树由两大要素事件（顶事件、中间事件和底事件）和各种逻辑门组成，它们分别对应到贝叶斯网络就是节点和有向边。

由于故障树中假定各种事件均可用正常和故障两种状态表示，可将故障树中的事件看作是贝叶斯网络中节点的某种特殊状态。

故障树中的逻辑门描述的是上一级事件与下一级事件之间的故障逻辑关系，该节只分析两个最常用的重要逻辑门与门和或门。对于与门，表示当所有下一级事件都发生时，上一级事件才发生；对于或门，表示至少有一个下一级事件发生时，上一级事件就发生。这种逻辑关系与贝叶斯网络中有向边的概念是相对应的。

表4 打印无效缺陷分析表Tab.4 The analysis of software print exception

图3 打印无效故障树Fig.3 The fault tree of software print exception

假设当软件中的缺陷Z发生时，用Z＝1表示；未发生时，用Z＝0表示。软件缺陷状态在贝叶斯网络中可以用变量的取值来表示。如图4所示，故障树中逻辑或门、与门的贝叶斯网络表达形式。故障树底事件的先验概率与其对应贝叶斯网络父节点的先验概率是同等概念，条件概率表达式表现了节点为某种状态时其条件概率的值。具体的转换步骤如下：

1. 把故障树中全部底事件逐一转换为贝叶斯网络中的节点，在故障树中的节点重复出现多次的情况下，可以在贝叶斯网络中将其简化为一个节点；

2. 将故障树中全部底事件的概率值对应到贝叶斯网络中相应节点；

3. 故障树中的全部逻辑门可以转化为贝叶斯网络中的某个节点，故障树中逻辑门的上一级事件状态与该节点状态取值保持一致；

4. 依据故障树中逻辑门与底事件之间关系链接贝叶斯网络中的各节点，通过有向边的方向来表达故障树中逻辑门的关系；

5. 将故障树中不同逻辑门的逻辑关系表达为贝叶斯网络中对应节点的条件概率表。

图4 故障树向贝叶斯网络转换图Fig.4 The transition graph of fault tree to bayesian networks

根据此转换建模方法对图3“打印无效故障树”进行转换，如图5“打印无效贝叶斯网络表示”：

如上图所示，T为顶事件，表示“打印无效”；其他节点的名称用表4打印无效缺陷分析表中的原因标号表示，也就是打印无效故障树中事件的名称，其中中间事件包括节点 1、4、1.1、4.2、1.1.1；底事件包括节点，1.2、4.3、1.1.3、1.1.4、1.3.3、4.1.3、4.2.1、4.2.2、1.1.1.1、1.1.1.2、1.1.2.1、1.4.1.2。这些节点名称的含义可在表4中对应找出。图5中的一些中间事件可以在图中省略，在建造贝叶斯网络模型时与其他节点合并，如节点1.4、4.1。

2.4 软件故障树缺陷分析

根据对笔者单位的大量项目测试数据的统计和对样本数据的观察分析，结合领域专家知识和用户的反馈，考虑测试过程中各种可能影响软件测试缺陷产生的因素及之间的相互关系及相互影响程度的大小，确定贝叶斯网络中各节点的条件概率。为使分析更实用，我们尽量精确的分析出每一个节点的概率值，决定其在某种特定情况下可能的状态。最终分析得出“打印无效贝叶斯网络”中各个节点的条件概率如表5、表6所示：

如表 5、表 6所示，根据历史数据可进行不同节点概率的赋值[15]，对于底事件节点，其概率包含发生的概率和不发生的概率两种值；对于中间事件节点，需要考虑在不同输入节点的概率下的节点概率，表6中用节点4.2作为一个例子解释节点M的概率受节点J、节点K影响制约的情况，并给出了发生概率表示方式。

顶事件T的状态有两种，“打印无效”事件发生或不发生，在贝叶斯网络公式中，可规定T＝0的项乘以 0，T＝1的项乘以 1，这样可根据公式计算出任意底事件发生对顶事件发生的影响概率。计算出所有底事件发生对顶事件发生影响的概率，便可比较分析问题产生的各种直接原因的重要程度，根据分析结果指导开发和测试。具体可按照底事件的重要程度对整个开发测试环境的各种因素进行分析诊断，包括开发团队的能力、产品的提交进度、对产品质量目标要求的高低，硬件资源等等。对分析出的关键因素的关键问题采取纠正措施进行缺陷预防，达到减少问题产生，提高软件开发效率及测试效率的目的，最终提升整个软件工程过程和产品的质量。

图5 打印无效贝叶斯网络表示Fig.5 The bayesian networks of software print exception

表5 打印无效底事件概率表Tab.5 The bottom events probability of software print exception

表6 打印无效中间事件概率表Tab.6 The middle events probability of software print exception

3 结论

本文针对目前国内软件企业对提升软件质量的需要，研究了结合贝叶斯网络的软件故障树缺陷分析建模技术，构建了模型，并在实践中得以应用，形成了包括缺陷数据收集和分类、软件故障树建模、基于贝叶斯网络的缺陷分析在内的一套完整的软件故障树建模分析流程。对于同类的软件企业用来进行缺陷预防提高软件质量具有借鉴和指导作用。

[1] 单锦辉, 徐克俊. 软件故障诊断探讨[J]. 北京化工大学学报, 2007.SHAN J H, XU K J. A Diagnose and discuss of software defect[J]. Journal of Beijing University of chemical Technology,2007. (in Chinese)

[2] 朱少民. 软件质量保证和管理[M]. 北京: 清华大学出版社, 2007.ZHU S M.Software Quality Assurance and Management[M].Beijing: Tsinghua University Press, 2007. (in Chinese)

[3] 周凯, 王璞. 软件故障树分析技术[J]. 航空计算技术,1997, (3): 54-57.ZHOU K, WANG P. Software fault tree analysis technology[J]. Aeronautical Computing Technique, 1997, (3): 54-57.(in Chinese)

[4] 蔡一平, 王玉玺. 软件故障树分析实施指南[M]. 北京: 中国国防科技信息中心, 2000.CAI Y P, WANG Y X. Software fault tree analysis and implementation guide[M]. Beijing: China Defense Science and Technology Information Center, 2000. (in Chinese)

[5] 侯安华, 秦红磊. 基于故障树和规则的故障诊断专家系统[J]. 微计算机信息, 2008, 7(1): 191-193.HOU A H, QIN H L. The expert system based on fault tree and rule[J]. Microcomputer Information, 2008, 7(1): 191-193.(in Chinese)

[6] 胡中伟, 吴芳美. 形式化故障树分析建模和软件安全性测试[J]. 同济大学学报, 2001, 11.HU Z W, WU F M. Formal Fault Tree Modeling and software security testing[J]. Journal of Tongji University, 2001, 11. (in Chinese)

[7] PEARLl J, Graphical Models for Probabilistic and Causal Reasoning[J]. The Computer Science and Engineering Handbook, Kluwer Academic Publishers, 1997: 697-714.

[8] KRAUSE P J. Learing Probabilistic Networks[J]. Knowledge Engineering Review, 1998, 13: 321-351.

[9] Hong G.Y, Xie M. A Statistical Method For Controlling Software Defect Detection Process[J]. Computers & Industrial Engineering, 1999, 37: 137-140.

[10] 张金槐, 唐雪梅. Bayes方法[M]. 长沙: 国防科技大学出版社, 1989.ZHANG J K, TANG X M. Bayes method[M]. Changsha: National Defense University Press, 1989. (in Chinese)

[11] AMASAKI S, TAKAGI Y, MIZUNO O, et al. A Bayesian Belief Network for Assessing the Likelihood of Fault Content[R]. Proceedings of the 14th International Symposium on Software Reliability Engineering, 2003.

[12] 王朔. 基于贝叶斯网络的舰艇导弹防御系统决策模型算法研究[D]. 长沙: 国防科学技术大学, 2005.WANG S. Research of naval vessels and guided missile defense system based on bayesian network decision Algorithm Modeling[D]. Changsha:National University of Defense Technology, 2005. (in Chinese)

[13] 林士敏, 田凤占, 陆玉昌. 贝叶斯网络的建造及其在数据采掘中的应用[J]. 清华大学学报(自然科学版), 2001, 41(l):l～2.LIN S M, TIAN F Z, LU Y C. The construct and application of Bayesian network in data mining[J]. Journal of Tsinghua University (Science and Technology), 2001, 41(l): l-2. (in Chinese)

[14] 张少中. 基于贝叶斯网络的知识发现与决策应用研究[D].大连: 大连理工大学, 2003.ZHANG S Z. Research of knowledge discovery and decision application based on bayesian network[D]. Dalian:Dalian University of Technology, 2003. (in Chinese)

[15] 白成刚. 基于Bayes网的软件残留错误数度量[J]. 计算机工程, 2003, 10: 39～40.BAI C G. Software residual errors measurement based on bayesian network[J]. Computer Engineering, 2003, 10: 39-40.(in Chinese)

[16] ChANG C P, CHU P P. Defect Prevention in Software Processes: An Action-Based Approach[J]. Journal of Systems and Software, 2007.

[17] LEE S F, BAI X Y, CHEN Y N. Automatic Mutation Testing and Simulation on OWL-S Specified Web Services[R]. 41st Annual Simulation Symposium (ANSS-41), IEEE Computer Society, 2008.

[18] NIAZI M, BABARC M A, VERNERD J M. Software Process Improvement barriers: A cross-cultural comparison[J]. Information and Software Technology, 2010, 52(11): 1204-1216.

[19] WALT C, BARNARD E. Data characteristics that determine classifier performance[J]. SAIEE Africa Research Journal, 2007.