基于最小割集的软件安全性测试用例生成∗

李 震 张 勇

（江苏科技大学 镇江 212000）

1 引言

计算机的广泛使用促进了软件产业的飞速发展，使其规模在不断扩大，复杂性不断地增加［2～3］。随之而来是软件的安全性问题也越来越突出，软件质量安全问题日益受到人们的关注。软件安全性测试是提高软件安全的有效手段之一，在软件投入运行之前，尽可能多地发现并排除软件中导致安全的情况，即尽可能多地设计并执行软件安全性测试用例。发现软件中存在的缺陷，并进行改正，以快速降低由于软件的失效而导致系统事故的风险。如果能够分析出导致系统的安全的因子所在，并增加对这些导致系统安全因子的测试，既可以最大程度地保持系统的安全性又可以整体提高测试的效率［4］。

最终也能为用户提供一个安全可靠的软件产品。在软件安全性测试过程中最关键的环节是软件安全性测试用例的设计。安全性测试用例设计就是确定一组最有可能发现某个安全问题或某类安全问题的测试数据。鉴于此，我们将故障树分析技术引入软件安全性测试中，它是分析系统安全性的一种重要方法，在许多领域都有广泛的使用。通过构建系统模块的故障树模型，由整体到部分、自下向上地进行定性和定量分析，然后寻找导致危险的发生的全部可能原因。首先介绍了故障树与最小割集的基本原理，然后给出了最小割集的生成方法，最后设计出了基于最小割集的软件安全性测试用例，能够提高测试用例的质量和安全性测试效率与质量。

2 基本原理及最小割集生成

2.1 故障树原理

故障树分析法（Fault Tree Analysis，FTA）是安全系统工程可靠性和安全分析最重要的的一种分析方法［5～7］。它采用逻辑的方法进行定性和定量分析，展现了以系统工程方法研究安全问题的系统性、准确性和预测性。故障树分析法是把系统不期望发生的导致安全事故的故障故障事件定义为“顶事件”，通过分析查找导致安全事故发生的顶事件发生的所有可能的直接因素，这些因素被称之为“中间事件”［8］。接着这些导致危险发生的因素分析查找每一个“中间事件”发生的所有可能因素，以此方法查找出导致危险发生的这些因素，直至追索到最后一级基本事件，也即“底事件”。故障树分析法从可能导致安全事件发生的具体故障结果出发，以自上而下的分支结构和层层细化的方式，查找出所有导致该事件发生的直接因素和间接因素，直到基本的原因事件［9］。通过最终分析结果，采用逻辑图把这些事件之间的逻辑关系形化表示出来，也即是故障树图。它根据元部件状态（基本事件）来显示系统的状态（顶事件）。故障树图的基础构造单元为事件，每一个基本事件由与（AND）、或（OR）等逻辑门连接接入上一级的原因事件。故障树图构造过程如图1 所示。

图1 故障树的构造过程

为了对其分析，一般用结构函数来对故障树描述，若一个故障树由n 个底事件，其顶事件记为T，底事件记为 Bi（i=1，2，…n），其状态记为 Si，并且对顶事件和底事件都只考虑发生或者不发生两种情况，那么底事件可表示为

那么顶事件T 的状态用ST表示，由于顶事件发生与否与底事件的状态直接有关，那么ST必然是底事件SB的函数，即

由故障树中导致顶事件发生的逻辑关系，利用布尔代数有关知识知，可得出对于不用逻辑关系导致顶事件发生的ST:

那么ST的结构函数可表示为

2.2 最小割集原理及其生成

定义1:由故障树的某些底事件所组成的集合中，该集合中的每个事件同时发生时就会引起顶事件的发生，那么这个集合就叫做割集（CS）［10］。

定义2:若故障数中存在这样的割集，若去掉该割集的任意一个事件后，该割集就不再是一个割集，那么就可称为该割集是一个最小割集（MCS）。

由上述定义可知，一个割集表示了一种发生故障的可能性，也即是一种软件失效模式。

假设故障树图中存在m 个最小割集C=（C1,C2,…Cm），只要最小割集的底事件di全部发生时，故障树顶事件T 必定发生，那么最小割集可表示为

在m 个最小割集中只要有一个发生就会导致顶事件T发生，那么故障树的结构函数可以表示为

由故障树最小割集的定义，使用下行法从上到下，对事件进行置换，利用事件之间的逻辑关系式进行转化，依次写出，直到全部的事件置换为底事件为止。最后得到全部的最小割集（如图2）为｛b8｝｛b7｝｛b5，b6｝｛b9，b11｝｛b10，b11｝｛b1，b3，b4｝｛b2，b3，b4｝。

图2 最小割集

3 故障分析

3.1 定性分析

从定性的角度，可知d7和d8两个模块独立构成最小割集，事件的发生导致安全事故的发生的概率也就比较大，那么它们就属于安全关键模块，其模块事件的发生将直接导致系统的安全故障，应在安全测试中对其重点测试。从故障树中可以看出越低级的故障事件对其顶事件的影响就越大，所以也应该重点测试。结合故障树以及最小割集故障树可以看出，同一个故障底事件对应的模块可能会通过不同的途径导致顶事件的发生，所以在安全性测试以及用例设计时候要注意，以及后续的用例设计及其安全性测试中也应该注意。总的来说，也就是

1）对于整个软件系统安全性来说，故障树的分支越少系统故障的可能性就越小，即最小割集的个数越少系统越安全，越多故障风险越大［11～12］；2）通常低阶最小割集对系统的影响度大，更容易使系统发生故障；3）在低阶最小割集中出现的底事件比高阶最小割集中的底事件重要；4）在阶数相同的最小割集中重复出现的次数越多的底事件越重要。

3.2 定量分析

从定量角度分析，利用可靠性预计模型或可靠性分析模型就可初步得出系统功能模块的故障情况，如表1；由模块的故障率和最小割集的分割为例，由式（1）可以得到最小割集的故障率分别为:P（K1）=PM7；P（K2）=PM7；P（K3）=PM7；P（K4）=PM7；P（K5）=PM7；P（K6）=PM7；P（K7）=PM。如表2。

表1 系统模块故障

表2 最小割集的故障率

由上可知，同阶数的最小割集的故障概率存在数量级的差异，同时低阶割集的故障概率明显高于高阶割集，这个规律与定性分析的结果相吻合。因此软件安全性测试用例设计的过程中，必须对系统中低阶最小割集的用例的设计加以注意［13］。

4 安全性测试用例的生成

由软件安全设计的故障树（如图1）的生成，利用下行法经过一系列的转化生成故障树的最小割集（如图2）。这都是在为软件安全性测试用例的设计做准备工作，在进行设计生成测试用例的时，依据生成的故障树最小割集来设计每一个安全用例，也就是每一个最小割集就是一个安全性测试用例［14～15］。在设计功能正确性测试用例时，不仅要考虑正确判决出故障的情况，同时也要考虑到对误判情况的测试（比如说将图2 中的“与门”换成“或门”，将“或门”换成“与门”）。在设计测试用例时，最佳方案为每个测试需求至少设计一个正确的测试用例［16］，一个异常的测试用例，对于只有一个割集的情况，基于对系统的整体影响安全性较大，应该使用穷举法测试来提高系统的安全性，尽量保证模块功能的安全；对于多参数的参数割集，应确保所有参数都分别进行用例设计。

5 结语

本文运用故障树模型的最小割集思想分析了导致安全问题各个因素，运用最小割集思想在得到统最小割集以后，计算出了故障树顶事件发生的概率精确值，即对最小割集定量分析。可以在软件设计的初期阶段就对各软件模块的用例进行分析设计，找出可能发生故障原因，对其用例设计查找出导致安全问题的因素，避免在设计后期的安全性测试才发现严重的安全问题以及出现问题后大量资源的耗费，提高了软件安全性测试的效率和软件的安全质量。