基于最小割集的軟件安全性測試用例生成?

李 震 張 勇

（江蘇科技大學 鎮江 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 結語

本文運用故障樹模型的最小割集思想分析了導致安全問題各個因素，運用最小割集思想在得到統最小割集以后，計算出了故障樹頂事件發生的概率精確值，即對最小割集定量分析。可以在軟件設計的初期階段就對各軟件模塊的用例進行分析設計，找出可能發生故障原因，對其用例設計查找出導致安全問題的因素，避免在設計后期的安全性測試才發現嚴重的安全問題以及出現問題后大量資源的耗費，提高了軟件安全性測試的效率和軟件的安全質量。