基于合約逐級求解的系統測試用例生成

曹 源，劉 杰+，肖安洪，吳志強，陳 智，曾 輝

(1.南華大學 計算機學院，湖南 衡陽 421001；2.中國核動力研究設計院 核反應堆系統設計技術重點實驗室，四川 成都 610041)

0 引 言

為保障核電DCS軟件系統可靠性[1]，降低人力成本，提升系統研發效率，研究測試用例自動生成方法。核電DCS軟件系統在高安全性應用開發環境SCADE(safety-critical application development environment)平臺上，基于基礎組件開發，由SCADE平臺自動生成系統的源代碼。源代碼將被燒錄到芯片中，在軟件系統使用、維護過程中，未按照標準操作，會使模型與代碼之間偏離[2]。導致軟件系統未能實現模型預期功能。為此需要對源代碼生成的軟件系統進行測試。常用的方法是根據反映整個系統行為特征的系統合約模型的求解[3,4]，生成系統的測試用例。但合約模型應用到工程軟件系統時，存在求解難度大、耗時多的問題。

針對此類問題，本文提出通過分析組件間依賴關系，得到組件處理順序，從而逐級計算組件合約的方法。具有如下優勢：①軟件系統模型基于具備可靠性的基礎組件組裝，結合合約模型可以實現在無源碼的情況下生成測試用例集，方法適用范圍廣。②方法采用逐級計算基礎組件合約的方法，依照組件計算順序逐級求解，規避了系統合約求解NP難問題。③方法應用于核電廠DCS軟件的系統級的測試用例生成，降低當前人工設計測試用例由于個人因素制約產生的測試充分性影響，降低測試人員負擔，且增加了自動化測試程度。將方法應用于核電反應堆堆芯測量系統，驗證方法的可行性。

1 基于合約的測試用例生成方法

1.1 應用背景概述

核電DCS軟件系統在SCADE平臺上，采用基于組件的開發方法進行開發。SCADE的基礎組件是實現數據和信號處理的基本單位，如量程轉換組件MRC，就完成了對滿足界定上限和下限的輸入信號進行線性轉換，并按參數要求限值輸出的工作。這些組件包括輸入信號、輸出信號以及模塊設定參數等輸入輸出接口，例如MRC的輸入信號確定了實際信號輸入并進行故障設定，輸出信號確定了實際信號輸出并監測信號值域等，參數確定了量程轉換組件的工作模式。

組件被正確執行的特征可通過組件的前置條件、后置條件及不變式予以限定[5]。調用方按照前置條件生成合法輸入。執行方依照后置條件保證輸出數據符合預期要求。不變式是系統生命周期中應始終滿足的條件。這些前置條件、后置條件及不變式與組件合約存在對應關系。組件合約即為反應組件正確執行時輸入信號、輸出信號及參數接口的邏輯關系。邏輯關系采用的是命題邏輯公式進行描述。根據軟件系統模型生成組件合約，通過對命題邏輯公式的求解，從而得到正確的輸入樣例和期望輸出值，即測試用例。根據測試用例驗證源代碼生成后的軟件系統是否存在錯誤。在前期的研究過程中分析軟件系統模型生成了基礎組件的合約模型[6]。

完整的DCS軟件系統模型是由這些基礎組件通過連接組件間的輸入、輸出等信號線搭建而成。通過基礎組件間連接信號變量的映射轉換，可由基礎組件合約構建出完整的系統合約。當組件間存在依賴關系時，則合約關系更為復雜，命題邏輯公式求解難度增大[7]。如果系統由成百上千個基礎組件構成，則系統合約公式巨大，求解是一個NP完全問題。因此一個有效的方法就是依據信號處理過程，逐級分析基礎組件合約，計算單個組件的期望輸入輸出，最后得到系統的輸入輸出。逐級分析組件的基本要求就是要不違背組件的依賴關系。DCS軟件系統的組件依賴就是對組件信號處理的先后次序。如在第3章的反應堆堆芯測量系統中的計算“溫差值”的SUM組件執行，需要求最大值組件MAX和求最小值組件MIN。這說明SUM組件依賴組件MAX和組件MIN。

因此組件測試用例生成需要確認組件的測試順序。對于復雜系統的測試順序確認已經有許多的研究方案，張艷梅等[8]提出基于圖論和基于搜索兩大類別的測試順序確認方法。基于圖論的方法是通過分析依賴關系生成有向結構圖，再對圖中的節點進行排序，進而生成測試順序的過程。其中一個重要的研究方向就是針對有向結構圖中存在的閉環問題，進行破除環路的處理，再進一步進行測試順序確認[9]。Zhang等[10]提出，刪除弱依賴關系破除環路的處理方案。其中基于搜索的方法是制定期望測試順序標準，通過智能優化算法，不斷進化初始種群，進而得到測試順序的過程。這兩類測試順序確認方法被廣泛的應用于各個領域。現今大多數研究方向是針對于復雜的軟件系統，通過減少測試樁數目及降低測試樁復雜度來降低測試成本。而開發測試樁本身耗費大量成本，且開發過程中樁模塊可能會產生新的錯誤。

核電DCS軟件系統的組件模型具有線性化、無環性、參數控制等特點。對于測試順序確認問題，設計出一種本身具備簡潔、高效、省時特點，并能夠保證測試順序準確無誤的基于拓撲的組件計算順序算法。

因此針對核電廠DCS系統，提出了一種基于組件合約的自動化測試用例生成方法。主要內容包括組件間的依賴關系分析及組件計算順序確認算法，逐級結合基礎組件合約要求，生成部分符合前置條件的測試用例輸入、及正確的參數，按照組件計算順序執行生成符合方法后置條件的期望輸出，通過判定是否滿足不變式，約簡測試用例，從而自動化生成符合所有合約的測試用例集。

1.2 測試用例生成流程

DCS軟件系統的設計圖通過組件定義系統功能實現。組件是一些獨立、可重用的功能的模塊[11]。設計圖可以得到由組件定義的DCS軟件系統的結構模型。

DCS軟件系統的設計圖描述了系統功能通過基礎組件實現的基本結構。由此可以分析出，組件之間的依賴關系。這些依賴關系決定了，測試用例生成的順序關系。組件計算順序結合單個組件的基礎合約，使用組合測試工具(PICT)生成初始數據，逐步計算出系統的測試用例。測試用例生成流程如圖1所示。

圖1 測試用例生成流程

定義1 結構模型由<組件集合，組件依賴圖>構成。組件集合構造系統的基本功能模塊集合，組件依賴圖說明組件調用依賴關系。

定義2 組件是一個<組件接口集，組件參數集，組件合約集>三元組。

(1)組件接口集::<輸入接口集，輸出接口集>，每個組件存在一個組件接口集，組件接口集中存在若干個輸入接口和輸出接口。

輸入/輸出參數::，組件接口集中存在若干個輸入、輸出參數，其中value表示其值，可以是浮點數模擬量，也可以是二進制值量；state表示狀態，有且只有無故障和有故障兩種狀態。

(2)組件參數集：每個組件存在一個組件參數集，參數集內的不同參數值協助劃分組件不同的工作模式。如在第3章給出的報警信號跳變閾值SVAL，取值 {190,40,50,300}, 當組件THC接收組件SUM輸出值value后，可根據value與SVAL值進行比較，確認溫差是否超越閾值，能否產生報警信號。

(3)組件合約集::<參數合約，值合約，狀態合約>，每個組件具備一個組件合約集，組件合約集中有參數合約、值合約、狀態合約3種合約。

參數合約是組件參數值(value)及組件參數間的約束條件；值合約是組件接口輸入數據、輸出數據值(value)的約束條件；狀態合約是組件接口輸入數據、輸出數據狀態(state)的約束條件。

本文采用合約化理驗證組件執行的正確性。通過求解合約的命題邏輯公式得到期望測試用例集。組件合約集與前置條件、后置條件及不變式存在對應關系。其中前置條件對應輸入值合約及輸入狀態合約及參數合約中的參數值合約部分，輸入值合約通常將數據同參數值比較、或數值相互比較決定當前數據滿足何種工作模式；后置條件對應輸出值合約及輸出狀態；不變式條件通常對應參數合約中的參數值及參數間合約部分，組件合約對應關系如圖2所示。

圖2 組件合約對應關系

軟件系統中各組件成員間存在關系，當組件需要借助另一個組件提供服務時，稱組件間存在依賴關系[12]。組件之間的依賴關系導致信號變化產生連鎖反應，系統穩定性受到組件間依賴關系的制約[13]。

定義3 組件依賴：設CA、CB分別是DCS軟件系統中的兩個組件，CB依賴于CA，組件CA必須在組件CB前執行，稱為存在組件依賴關系，則組件CA存在輸出接口OA，組件CB存在輸入接口IB。接口IB會接收到由接口OA中傳遞的信號，并對信號進行處理。前后組件主要傳遞兩種類型的信號：

(1)組件轉換狀態：接口IB接收到接口OA中傳遞的信號后，僅發生狀態傳遞，由組件CA運行至組件CB，則稱發生組件轉換狀態。

(2)數據傳遞狀態：組件CB中存在方法P，接口IB接收到接口OA中傳遞的信號，其中包含方法P所需要使用的數據，則稱發生數據傳遞狀態。

根據這種依賴關系中的兩種狀態，結合系統設計圖進行靜態分析，構建組件依賴圖。根據組件依賴圖使用基于拓撲的組件計算順序算法，來進行組件計算順序確認。

根據軟件系統模型的靜態分析生成基礎組件合約模型。基礎組件合約模型提供了系統需要滿足的合約。依照組件合約對應關系，給出包括組件輸入接口需要滿足的前置條件，組件輸出接口需要滿足的后置條件，以及在整個系統測試過程中需要滿足的不變式條件。

通過確認的組件計算順序來依次判定測試用例是否符合接口合約。使用PICT工具依照合約需求中的前置條件生成部分測試用例輸入及組件參數值。針對每個組件，依次根據滿足不同輸入接口前置條件的輸入數據，選擇不同工作模式，對應不同輸出接口后置條件計算輸出值。再對測試用例進行不變式條件判定，不滿足不變式條件則約簡測試用例，即從表中刪除該組測試用例，均滿足則保留測試用例，并執行至測試順序中下一個組件，直至執行至最后一個組件。最終獲得滿足所有合約的測試用例集。

1.3 測試用例覆蓋準則

測試覆蓋準則是對軟件測試充分性的度量[14]。由于基于合約化理論生成測試用例集，因此采用合約覆蓋率作為測試充分性的度量標準。組件的工作模式由前置條件的輸入值合約部分，結合組件參數進行劃分，工作模式與后置條件存在一一對應關系，因此將后置條件的覆蓋情況作為測試用例覆蓋標準能夠很好反映出軟件系統工作模式的覆蓋情況，給出合約覆蓋率作為測試用例覆蓋準則：

定義4 合約覆蓋率CC

(1)

2 組件合約逐級求解技術

合約逐級求解技術可分為兩大部分工作。第一部分是組件計算順序生成算法，根據分析得到的組件依賴圖，使用組件計算順序算法對組件進行排序處理，最終得到組件計算順序；第二部分是合約逐級求解測試用例生成算法，分為組件初始數據生成算法和組件處理算法，組件初始數據生成算法依照合約需求中的前置條件生成具有非數據傳遞狀態的輸入值、輸入狀態及組件參數值；組件處理算法則通過前置條件、后置條件和不變式條件按照組件計算順序，對組件逐級處理，求解輸出值，約簡測試用例，最終生成滿足所有合約的測試用例集。

2.1 組件計算順序生成算法

為了確保SCADE系統組件間生成的測試數據的準確性，需要對組件的測試順序進行確認。根據所構建的組件依賴圖，來對組件計算順序進行排序。針對組件依賴圖為有向無環圖的情況下進行討論。拓撲排序能夠由集合中的偏序得到全序。而有向無環圖能夠表示具有依賴關系的頂點集。有向無環圖通過拓撲排序能夠生成一組序列。我們僅保證具有依賴關系的組件，被依賴的組件需在依賴組件前執行，由此提出一種基于拓撲的組件計算順序算法。

設G(C，E) 為某有向無環圖，圖中一個頂點代表一個組件， C={C1，C2，…Cn}，E={e1，e2，…em}， 某個頂點的出度表示該組件的輸入接口共連接了多少個組件(組件數≥0)的輸出接口，表明這個組件所依賴的組件數量。某個頂點的入度表示該組件的輸出接口共連接了多少個組件(組件數≥0)的輸入接口，表明這個組件被依賴數量。頂點CA，CB∈C， 若存在有向邊ek=， 則表示組件CA與組件CB存在組件依賴關系，組件CA必須在組件CB前執行。

具體流程如下：

(1)輸入所有組件對象及組件依賴圖G；

(2)建立數組deg記錄圖中每個組件節點出度數；

(3)建立隊列que添加出度數為0的組件節點；

(4)建立空序列order，在隊列不為空時從隊列中取出頭節點放入序列末尾，并將此組件節點的后繼節點出度數均減1；

(5)后繼節點出度數為0時，排入隊列末尾，等待序列召喚，直至將所有組件計算順序排列完畢，輸出組件計算順序。算法偽代碼如下：

算法1：組件計算順序算法

輸入：組件依賴圖G

輸出：組件計算順序

(1)建立新圖G

(2)建立數組初始化

(3)for依賴圖中組件對象間存在信號輸入do

(4) CA:=被依賴組件

(5) CB:=當前組件

(6) If組件CA、CB存在有向邊ekthen:

(7) 組件CB的出度數+1

(8) end if

(9)end for

(10)建立隊列

(11)建立空序列

(12)while隊列不為空do

(13) 從隊列中取出頭結點(出度為0的節點)CA添加至序列末尾

(14) for CA存在后繼節點CBdo

(15) 數組中后繼結點CB出度-1

(16) if 后繼結點CB出度為0 then

(17) 隊列隊尾添加CB

(18) end if

(19) end for

(20)end while

(21)return 輸出組件計算順序 end

2.2 合約逐級求解測試用例生成算法

根據得到的組件計算順序，進行合約逐級求解工作，具體流程如下：

(1)根據系統設計圖的分析確認需要測試的內容及基礎組件合約模型，通過基礎組件合約模型得到需要滿足的合約；

(2)根據前置條件預先生成部分組件的輸入數據及組件參數，根據數據名稱和值建立映射表；

(3)按照確認的組件計算順序依次處理組件，每次從表中取出組件的輸入數據，或獲取被依賴組件(上一個組件)的輸出值，作為當前組件的輸入參數名與值添加進映射表并進行前置條件判定，符合前置條件，根據結果內容及映射表計算對應輸出值，并根據后置條件確定輸出狀態；

(4)最后進行一次不變式條件判定，拋棄不符合條件的測試用例，將符合條件的輸出值及狀態存入合法數據表中，得到最終滿足所有合約的測試用例集。組件處理偽代碼如下：

算法2：組件初始數據生成算法

輸入：組件序列，組件參數組合，組件合約

輸出：組件初始輸入數據

(1)For 前置條件 do:

(2) If 條件滿足 then:

(3) 生成部分組件的輸入數據及組件參數，根據數據名稱和值建立映射表

(4) End if

(5)End for

算法3：組件處理算法

輸入:組件計算順序，組件合約，組件初始輸入數據

輸出:合法測試用例

(1)For 每組參數組合輸入數據 do:

(2) For 組件 in 組件序列:

(3) For 引用輸入 do:

(4) 獲取被依賴組件(上一個組件)的輸出值，將它作為輸入參數名與值添加進映射表

(5) End for

(6) For 前置條件 do:

(7) If 條件滿足 then:

(8) 根據對應后置條件結合結果內容及映射表計算得到輸出值和狀態

(9) End if

(10) End for

(11) For 該組件不變式條件 do:

(12) If條件不滿足 then:

(13) Goto 1

(14) End if

(15) End for

(16) 將輸出值與狀態寫入合法數據表

(17) End for

(18) 輸出合法測試用例

3 應用研究

針對使用合約化理論的基于基礎組件組裝的系統，構建了一個自動化生成測試用例的工具。工具開發平臺為PyCharm，采用Python語言編譯，并使用開發框架QT進行設計，運行界面如圖3所示。

圖3 測試用例生成工具運行界面

反應堆堆芯測量系統是對堆芯溫度進行檢測，保證防止由于堆內溫度熱分布不平衡產生的安全性事故。反應堆堆芯測量系統將堆芯分為4個區域，每個區域都設置了不同數量的溫度傳感器。反應堆堆芯測量系統的報警功能實現過程是由每個區域的溫度測量信號到報警信號的轉換過程。區域內通過對采樣信號進行去噪處理后對最大最小溫度值求差，再通過對溫度信號與報警信號閾值的比較，從而產生報警信息，分為溫度信號去噪、溫度值求差、閾值檢測三階段工作，以區域P1內溫度值求差及閾值檢測階段工作過程為例說明基于合約的組件集成自動化測試用例集生成過程。

溫度值求差：通過溫度信號去噪階段傳遞而來的溫度數值信號，使用組件MAX、MIN分別求出5個溫度傳感器的最大、最小溫度值，再使用MUL組件分別對最大、最小溫度值進行符號設定及數值補償，再通過SUM組件求溫度差，此過程共使用5個組件。

閾值檢測：通過溫度值求差子系統傳遞而來的溫差信號，使用THC組件檢查閾值以產生報警信號。此過程中共使用1個組件。

暫時忽略溫度信號去噪階段VSB組件與溫度值求差階段MAX、MIN組件之間存在的數據傳遞狀態，僅考慮MAX、MIN組件與MUL組件、MUL組件與SUM組件、SUM組件與THC組件之間存在數據傳遞狀態。靜態分析組件間的依賴關系，生成組件依賴如圖4所示。

根據組件依賴圖，使用算法1中組件計算順序算法進行排序，生成組件計算順序。

使用微軟公司開發的組合測試工具(PICT)，結合二維組合覆蓋準則，根據合約模型的前置條件使用算法2中組件初始數據生成算法，生成滿足邏輯公式的MAX、MIN組件的測試用例輸入、狀態及MUL_1-2、THC的參數值，即進行布爾表達式判別，生成滿足布爾表達式為“真”時的數據，并根據數據名稱和值建立映射表。

根據組件計算順序，使用算法3中組件處理算法來對組件進行處理，依次取出映射表中存儲的組件初始輸入數據，及接收的被依賴組件傳遞而來的數據，對組件逐級計算求解。

圖4 溫度值求差階段及閾值檢測階段組件依賴

首先獲取MAX組件映射表中的測試用例輸入及狀態，輸入數據見表1。

根據不同的前置條件劃分不同工作模式，即進行布爾表達式的判別，獲取布爾表達式為“真”時對應的工作模式。此處判別5個接口，接收到溫度信號去噪階段，5個組件傳遞而來的數據中(此處使用PICT模擬生成)，哪個接口接收到的數據，是狀態為無故障前提條件下的最大溫度，MAX組件前置條件見表2。

MIN組件結構類于MAX組件，得到輸出O2(最小溫度)，此處不再贅述。

MUL_1組件接口見表3，具備參數G1(模擬信號、最大溫度增幅)，輸入接口I1獲取被依賴組件MAX的輸出值及狀態，并作為自己的輸入數據，即最大溫度添加進映射表。根據不同工作模式，對應后置條件輸出增幅后的最大溫度，MUL_1組件前置及后置條件見表4。

MUL_2組件結構類似于MUL_1組件，具備參數G2(模擬信號、最小溫度增幅)得到輸出O2_min(增幅后的最小溫度)，此處不再贅述。

SUM組件在接收MUL_1、2組件傳遞的數據及狀態后，作為輸入添加進映射表，并計算溫差，其中SUM輸入數據見表5。

THC組件接口見表6，具備參數SVAL(模擬信號、報警信號跳變閾值)、參數HYST(模擬信號、遲滯參數)，組件參數見表7。輸入接口I1獲取被依賴組件SUM組件傳遞來的溫差值及狀態，作為輸入添加進映射表，并從映射表中取出PICT生成的SVAL及HYST的參數值。根據當前不同工作模式，選擇輸出不同信號。例，當輸入數據值大于SVAL，則超出閾值上限，信號從“0”跳變至“1”，輸出報警信號。并根據不變式條件，約簡布爾表達式為“假”時的測試用例，最終得到滿足所有合約的測試用例集，THC組件條件見表8。

表2 MAX組件前置條件

表3 MUL_1組件接口

表4 MUL_1組件前置條件及后置條件

表5 SUM組件輸入數據

表6 THC組件接口

表7 THC組件參數

表8 THC組件條件

根據測試用例生成方法生成測試用例實例，見表9。

在滿足組件合約的情況下使用生成了15組測試數據，測試用例覆蓋率見表10。

測試用例平均覆蓋率達到97.27%。在解決了問題的同時保證了較高的合約覆蓋率。

4 結束語

核電廠DCS軟件的系統級的測試用例生成，與系統的性質特征密切相關。目前還沒有通用的自動化測試用例生成方法，通常根據有經驗的測試人員來進行人工設計測試用例，并結合自動化測試工具進行測試，效率較低。受到人員經驗、習慣等人為因素的制約，測試充分度會產生一定的影響，導致生成的測試用例不具備足夠的客觀性與通用性；且復雜的DCS軟件系統求解系統合約是一個NP難問題，在進行測試用例分析設計時成本高、難度大。因此提出一種基于合約的組件逐級測試用例生成方法。這種自動化測試用例生成方法可以使用組合測試策略生成充分多的符合組件合約的測試用例集。根據實驗結果表明，生成的測試用例的合約覆蓋度達到97.27%。后續工作應加強算法對難覆蓋節點的處理，實現工作模式的全覆蓋。

表9 測試用例實例

表10 測試用例覆蓋率