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

李 震 張 勇

（江蘇科技大學(xué) 鎮(zhèn)江 212000）

1 引言

計(jì)算機(jī)的廣泛使用促進(jìn)了軟件產(chǎn)業(yè)的飛速發(fā)展，使其規(guī)模在不斷擴(kuò)大，復(fù)雜性不斷地增加［2～3］。隨之而來(lái)是軟件的安全性問(wèn)題也越來(lái)越突出，軟件質(zhì)量安全問(wèn)題日益受到人們的關(guān)注。軟件安全性測(cè)試是提高軟件安全的有效手段之一，在軟件投入運(yùn)行之前，盡可能多地發(fā)現(xiàn)并排除軟件中導(dǎo)致安全的情況，即盡可能多地設(shè)計(jì)并執(zhí)行軟件安全性測(cè)試用例。發(fā)現(xiàn)軟件中存在的缺陷，并進(jìn)行改正，以快速降低由于軟件的失效而導(dǎo)致系統(tǒng)事故的風(fēng)險(xiǎn)。如果能夠分析出導(dǎo)致系統(tǒng)的安全的因子所在，并增加對(duì)這些導(dǎo)致系統(tǒng)安全因子的測(cè)試，既可以最大程度地保持系統(tǒng)的安全性又可以整體提高測(cè)試的效率［4］。

最終也能為用戶提供一個(gè)安全可靠的軟件產(chǎn)品。在軟件安全性測(cè)試過(guò)程中最關(guān)鍵的環(huán)節(jié)是軟件安全性測(cè)試用例的設(shè)計(jì)。安全性測(cè)試用例設(shè)計(jì)就是確定一組最有可能發(fā)現(xiàn)某個(gè)安全問(wèn)題或某類(lèi)安全問(wèn)題的測(cè)試數(shù)據(jù)。鑒于此，我們將故障樹(shù)分析技術(shù)引入軟件安全性測(cè)試中，它是分析系統(tǒng)安全性的一種重要方法，在許多領(lǐng)域都有廣泛的使用。通過(guò)構(gòu)建系統(tǒng)模塊的故障樹(shù)模型，由整體到部分、自下向上地進(jìn)行定性和定量分析，然后尋找導(dǎo)致危險(xiǎn)的發(fā)生的全部可能原因。首先介紹了故障樹(shù)與最小割集的基本原理，然后給出了最小割集的生成方法，最后設(shè)計(jì)出了基于最小割集的軟件安全性測(cè)試用例，能夠提高測(cè)試用例的質(zhì)量和安全性測(cè)試效率與質(zhì)量。

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

2.1 故障樹(shù)原理

故障樹(shù)分析法（Fault Tree Analysis，F(xiàn)TA）是安全系統(tǒng)工程可靠性和安全分析最重要的的一種分析方法［5～7］。它采用邏輯的方法進(jìn)行定性和定量分析，展現(xiàn)了以系統(tǒng)工程方法研究安全問(wèn)題的系統(tǒng)性、準(zhǔn)確性和預(yù)測(cè)性。故障樹(shù)分析法是把系統(tǒng)不期望發(fā)生的導(dǎo)致安全事故的故障故障事件定義為“頂事件”，通過(guò)分析查找導(dǎo)致安全事故發(fā)生的頂事件發(fā)生的所有可能的直接因素，這些因素被稱之為“中間事件”［8］。接著這些導(dǎo)致危險(xiǎn)發(fā)生的因素分析查找每一個(gè)“中間事件”發(fā)生的所有可能因素，以此方法查找出導(dǎo)致危險(xiǎn)發(fā)生的這些因素，直至追索到最后一級(jí)基本事件，也即“底事件”。故障樹(shù)分析法從可能導(dǎo)致安全事件發(fā)生的具體故障結(jié)果出發(fā)，以自上而下的分支結(jié)構(gòu)和層層細(xì)化的方式，查找出所有導(dǎo)致該事件發(fā)生的直接因素和間接因素，直到基本的原因事件［9］。通過(guò)最終分析結(jié)果，采用邏輯圖把這些事件之間的邏輯關(guān)系形化表示出來(lái)，也即是故障樹(shù)圖。它根據(jù)元部件狀態(tài)（基本事件）來(lái)顯示系統(tǒng)的狀態(tài)（頂事件）。故障樹(shù)圖的基礎(chǔ)構(gòu)造單元為事件，每一個(gè)基本事件由與（AND）、或（OR）等邏輯門(mén)連接接入上一級(jí)的原因事件。故障樹(shù)圖構(gòu)造過(guò)程如圖1 所示。

圖1 故障樹(shù)的構(gòu)造過(guò)程

為了對(duì)其分析，一般用結(jié)構(gòu)函數(shù)來(lái)對(duì)故障樹(shù)描述，若一個(gè)故障樹(shù)由n 個(gè)底事件，其頂事件記為T(mén)，底事件記為 Bi（i=1，2，…n），其狀態(tài)記為 Si，并且對(duì)頂事件和底事件都只考慮發(fā)生或者不發(fā)生兩種情況，那么底事件可表示為

那么頂事件T 的狀態(tài)用ST表示，由于頂事件發(fā)生與否與底事件的狀態(tài)直接有關(guān)，那么ST必然是底事件SB的函數(shù)，即

由故障樹(shù)中導(dǎo)致頂事件發(fā)生的邏輯關(guān)系，利用布爾代數(shù)有關(guān)知識(shí)知，可得出對(duì)于不用邏輯關(guān)系導(dǎo)致頂事件發(fā)生的ST:

那么ST的結(jié)構(gòu)函數(shù)可表示為

2.2 最小割集原理及其生成

定義1:由故障樹(shù)的某些底事件所組成的集合中，該集合中的每個(gè)事件同時(shí)發(fā)生時(shí)就會(huì)引起頂事件的發(fā)生，那么這個(gè)集合就叫做割集（CS）［10］。

定義2:若故障數(shù)中存在這樣的割集，若去掉該割集的任意一個(gè)事件后，該割集就不再是一個(gè)割集，那么就可稱為該割集是一個(gè)最小割集（MCS）。

由上述定義可知，一個(gè)割集表示了一種發(fā)生故障的可能性，也即是一種軟件失效模式。

假設(shè)故障樹(shù)圖中存在m 個(gè)最小割集C=（C1,C2,…Cm），只要最小割集的底事件di全部發(fā)生時(shí)，故障樹(shù)頂事件T 必定發(fā)生，那么最小割集可表示為

在m 個(gè)最小割集中只要有一個(gè)發(fā)生就會(huì)導(dǎo)致頂事件T發(fā)生，那么故障樹(shù)的結(jié)構(gòu)函數(shù)可以表示為

由故障樹(shù)最小割集的定義，使用下行法從上到下，對(duì)事件進(jìn)行置換，利用事件之間的邏輯關(guān)系式進(jìn)行轉(zhuǎn)化，依次寫(xiě)出，直到全部的事件置換為底事件為止。最后得到全部的最小割集（如圖2）為｛b8｝｛b7｝｛b5，b6｝｛b9，b11｝｛b10，b11｝｛b1，b3，b4｝｛b2，b3，b4｝。

圖2 最小割集

3 故障分析

3.1 定性分析

從定性的角度，可知d7和d8兩個(gè)模塊獨(dú)立構(gòu)成最小割集，事件的發(fā)生導(dǎo)致安全事故的發(fā)生的概率也就比較大，那么它們就屬于安全關(guān)鍵模塊，其模塊事件的發(fā)生將直接導(dǎo)致系統(tǒng)的安全故障，應(yīng)在安全測(cè)試中對(duì)其重點(diǎn)測(cè)試。從故障樹(shù)中可以看出越低級(jí)的故障事件對(duì)其頂事件的影響就越大，所以也應(yīng)該重點(diǎn)測(cè)試。結(jié)合故障樹(shù)以及最小割集故障樹(shù)可以看出，同一個(gè)故障底事件對(duì)應(yīng)的模塊可能會(huì)通過(guò)不同的途徑導(dǎo)致頂事件的發(fā)生，所以在安全性測(cè)試以及用例設(shè)計(jì)時(shí)候要注意，以及后續(xù)的用例設(shè)計(jì)及其安全性測(cè)試中也應(yīng)該注意?？偟膩?lái)說(shuō)，也就是

1）對(duì)于整個(gè)軟件系統(tǒng)安全性來(lái)說(shuō)，故障樹(shù)的分支越少系統(tǒng)故障的可能性就越小，即最小割集的個(gè)數(shù)越少系統(tǒng)越安全，越多故障風(fēng)險(xiǎn)越大［11～12］；2）通常低階最小割集對(duì)系統(tǒng)的影響度大，更容易使系統(tǒng)發(fā)生故障；3）在低階最小割集中出現(xiàn)的底事件比高階最小割集中的底事件重要；4）在階數(shù)相同的最小割集中重復(fù)出現(xiàn)的次數(shù)越多的底事件越重要。

3.2 定量分析

從定量角度分析，利用可靠性預(yù)計(jì)模型或可靠性分析模型就可初步得出系統(tǒng)功能模塊的故障情況，如表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 系統(tǒng)模塊故障

表2 最小割集的故障率

由上可知，同階數(shù)的最小割集的故障概率存在數(shù)量級(jí)的差異，同時(shí)低階割集的故障概率明顯高于高階割集，這個(gè)規(guī)律與定性分析的結(jié)果相吻合。因此軟件安全性測(cè)試用例設(shè)計(jì)的過(guò)程中，必須對(duì)系統(tǒng)中低階最小割集的用例的設(shè)計(jì)加以注意［13］。

4 安全性測(cè)試用例的生成

由軟件安全設(shè)計(jì)的故障樹(shù)（如圖1）的生成，利用下行法經(jīng)過(guò)一系列的轉(zhuǎn)化生成故障樹(shù)的最小割集（如圖2）。這都是在為軟件安全性測(cè)試用例的設(shè)計(jì)做準(zhǔn)備工作，在進(jìn)行設(shè)計(jì)生成測(cè)試用例的時(shí)，依據(jù)生成的故障樹(shù)最小割集來(lái)設(shè)計(jì)每一個(gè)安全用例，也就是每一個(gè)最小割集就是一個(gè)安全性測(cè)試用例［14～15］。在設(shè)計(jì)功能正確性測(cè)試用例時(shí)，不僅要考慮正確判決出故障的情況，同時(shí)也要考慮到對(duì)誤判情況的測(cè)試（比如說(shuō)將圖2 中的“與門(mén)”換成“或門(mén)”，將“或門(mén)”換成“與門(mén)”）。在設(shè)計(jì)測(cè)試用例時(shí)，最佳方案為每個(gè)測(cè)試需求至少設(shè)計(jì)一個(gè)正確的測(cè)試用例［16］，一個(gè)異常的測(cè)試用例，對(duì)于只有一個(gè)割集的情況，基于對(duì)系統(tǒng)的整體影響安全性較大，應(yīng)該使用窮舉法測(cè)試來(lái)提高系統(tǒng)的安全性，盡量保證模塊功能的安全；對(duì)于多參數(shù)的參數(shù)割集，應(yīng)確保所有參數(shù)都分別進(jìn)行用例設(shè)計(jì)。

5 結(jié)語(yǔ)

本文運(yùn)用故障樹(shù)模型的最小割集思想分析了導(dǎo)致安全問(wèn)題各個(gè)因素，運(yùn)用最小割集思想在得到統(tǒng)最小割集以后，計(jì)算出了故障樹(shù)頂事件發(fā)生的概率精確值，即對(duì)最小割集定量分析?？梢栽谲浖O(shè)計(jì)的初期階段就對(duì)各軟件模塊的用例進(jìn)行分析設(shè)計(jì)，找出可能發(fā)生故障原因，對(duì)其用例設(shè)計(jì)查找出導(dǎo)致安全問(wèn)題的因素，避免在設(shè)計(jì)后期的安全性測(cè)試才發(fā)現(xiàn)嚴(yán)重的安全問(wèn)題以及出現(xiàn)問(wèn)題后大量資源的耗費(fèi)，提高了軟件安全性測(cè)試的效率和軟件的安全質(zhì)量。