構建軟件測試領域不確定性知識圖譜

羅浩榕，朱衛星，史涯晴，萬進勇

(陸軍工程大學 指揮控制工程學院，江蘇 南京 210001)

0 引 言

軟件測試通過動態和靜態的測試技術發現軟件缺陷，是軟件質量保證的關鍵活動。在實際軟件測試過程中，由于軟件測試分析、設計和執行技術的不足，測試用例幾乎不可能做到輸入域的全部覆蓋，因此軟件測試的結果并不總是處于可預知的范圍內，從歷史軟件測試資產中獲取的軟件測試知識具有一定的不確定性。因此，建立軟件測試復用系統必須考慮如何表達不確定性知識和求解不確定性問題，盡可能消除測試不確定性。傳統的軟件測試復用通常基于1991年提出的軟件復用3C模型[1]，即被復用工件的概念(concept)、內容(content)、上下文(context)。由于時間和成本的限制，這三個維度的確定性假設可能很難成立，精確且完整的描述軟件測試的概念、內容和上下文是非常困難的[2]。2012谷歌提出了知識圖譜的概念，對現實世界中的實體、概念、屬性及其關系進行建模，與傳統的專家知識系統相比有更強的語義表達能力和建模靈活性，在知識存儲、檢索和推理方面有更大優勢。建立專業領域知識圖譜通常采用“自上而下”的方式，根據建模需求和業務領域構建領域本體作為知識圖譜的模式層，再通過業務數據對本體實例化。為了表達知識的不確定性，模糊知識圖譜結合不確定性建模方法擴展經典本體[3-4]，建立不確定性知識的表示和推理機制，在軟件測試中不確定性建模方法包括貝葉斯信念網絡、粗糙集、模糊邏輯、隱馬爾可夫模型等[5]。其中粗糙集可以表示不確定性信息空間中的多屬性決策函數，而軟件測試過程需要考慮多種屬性是典型的多屬性決策過程，因此考慮基于粗糙集擴展軟件測試資產本體。

1 軟件測試中的不確定性

2014年，在SWEBOK 3.0發布的軟件工程知識體系中，將軟件測試定義為“從一個通常是無限的執行域(集合)中選擇合適的、有限的測試用例，對程序所期望的行為進行動態驗證的活動過程”。因此用三元組〈I,S,O〉表示軟件測試用例T，其中I是被測件輸入域，O是被測件輸出域，S是被測件的起始狀態，另有函數f表示輸入域到輸出域的映射。那么，對于測試用例任一測試輸入都有一個在已知輸出域的結果，即預期結果：

T〈I,S,O〉:[?i∈I→?f(i)=o∧o∈O]

(1)

當測試結果和缺陷分布未知時，認為軟件測試存在不確定性，即對于給定的輸入和起始狀態，可能出現在已知輸出域之外的結果。

UncertaintyT〈I,S,O〉:[?i∈I→?f(i)=

r∧r?O]

(2)

造成軟件測試中存在不確定性的主要原因有[5-6]：

●在測試需求分析階段，由于軟件開發階段，需求建模與真實的用戶需求和相應問題領域存在一定差異，軟件測試繼承了軟件需求的差異性。

●測試設計階段，由于經濟成本和時間成本的限制，遍歷輸入域的詳盡測試無法實現。因此，對于每一個被測件都必須選擇有限的測試用例子集，這可能無法檢測所有的缺陷，造成了一定的不確定性。

●對于許多軟件系統例如嵌入式軟件，完整地復現用戶場景并不現實，因此軟件測試通常在模擬測試環境中實施，測試環境與真實環境的差異也引入了不確定性。

2 軟件測試模糊知識圖譜

具有較大復用價值的軟件測試資產主要包括三類：測試需求、測試用例、問題報告。這三類測試資產涵蓋了軟件測試分析、設計、執行、質量估計的全生命周期，是軟件測試知識的集中體現。首先依據本體從三類測試資產中提取軟件測試知識實體，形成測試資產知識圖譜，結合行業標準中的領域知識形成領域術語圖譜，再建立測試資產與領域特征的關聯關系，采用基于知識粒度的方法為資產-特征賦予關系置信度。該文面向軟件測試資產建立不確定性知識圖譜的總體框架如圖1所示。

圖1 軟件測試資產不確定性知識圖譜建立總體框架

基于上述總體框架，對測試資產本體、領域術語圖譜構建方法、模糊關系置信度計算3個方面進行闡述。

2.1 測試資產本體

軟件測試資產中包含大量信息，這些信息可能通過正確的表示和處理轉化為適用的知識，應用知識管理方法和原則管理測試資產，可以促進測試過程中的復用[7-8]。軟件測試資產主要有三個對象類，即測試需求、測試用例和問題報告。

定義1：測試需求。測試需求確定測試目標、測試內容和質量特性，確定測試充分性要求，提出測試活動應當遵循的基本原則和要求，確定測試資源和技術需求。測試需求(Test Requirement，TR)包括七元組：測試目標(Target，Ta)、被測件描述(Description，De)、測試階段(Phase，Ph)、測試類型(Type，Ty)、測試環境(Environment，En)、測試方法(Method，Me)、判斷規則(Evaluate，Ev)，記為：

TR=〈Ta,De,Ph,Ty,En,Me,Ev〉

(3)

經驗表明，同一領域的測試項目往往遵循相同的行業規范、標準等，同一類型軟件的使用場景、功能結構、性能要求等存在很大相似性，因此具備了知識復用的基礎。

定義2：測試用例。測試用例是指測試人員根據軟件需求規格說明和程序內部結構，精心設計出的一組測試輸入、執行條件以及預期結果，用于核實軟件是否滿足某個特定需求。測試用例(Test Case，TC)包括五元組：需求追蹤項(Required Trace，Rt)、前提條件(Precondition，Pr)、輸入數據(Input Data，In)、執行步驟(Operation Step，Ops)、預期結果(Except Result，Er)，記為：

TC=〈Rt,Pr,In,Ops,Er〉

(4)

測試用例設計是軟件測試的核心工作，對測試用例的復用是目前研究最多的，除了查找相似的測試用例直接獲取歷史經驗，還可以歸納形成測試設計模式。

定義3：問題報告。問題報告是對未通過的測試用例進行記錄和總結，提出復現軟件缺陷的最短路徑，分析定位錯誤。問題報告(Bug Report，BR)包括五元組：用例追蹤項(Case Trace，Ct)、實際結果(Actual Result，Ar)、缺陷特征(Bug Character，Bc)、缺陷定位(Bug Location，Bl)、嚴重程度(Bug Severity，Bs)，記為：

BR=〈Ct,Ar,Bc,Bl,Bs〉

(5)

問題報告中蘊含了測試人員對軟件缺陷的總結，可以獲取軟件缺陷模式知識幫助后續開發人員定位缺陷，對于修復問題具有重要意義。從測試資產原始數據中獲取以上三類對象的實例，每條實例作為知識圖譜中的一個節點，這些節點按照固有的繼承和關聯關系相連接，這部分關系由原數據直接得到，不賦予模糊置信度。

2.2 領域術語圖譜

軟件測試的決策因素主要包括被測件本身的特征、行業特征和軟件測試本身特征。因此，將軟件資產中的概念分為三類〈Wd,Wt,Ws〉，其中行業概念Wd指被測件應用的問題領域相關概念；軟件測試概念Wt指軟件測試本身特有概念詞匯；軟件概念Ws指描述被測軟件的特征概念，包括軟件架構、接口協議、編程語言等，每一類概念包括若干棵領域術語樹。

領域術語樹中每個節點代表一條領域術語，節點間存在兩類關系：子術語關系、近似術語關系。

3 領域術語圖譜構建

領域術語圖譜構建過程如圖2所示。

圖2 領域術語圖譜構建過程

①基本術語樹構建，基于行業標準等權威數據建立領域概念結構。

根據國標、國軍標等行業標準中關于行業領域、軟件測試、軟件系統的相關定義，構建層次化的術語樹。

②候選詞提取，基于互信息和左右熵從測試資產語料中發現候選詞集[9]。

行業領域的術語詞往往與一般詞匯不同，通用分詞工具的結果可能遺漏一些固有搭配，例如，指揮信息系統可能被分解為三個詞：指揮、信息、系統。互信息和左右熵分別計算詞的內部凝和度和邊界自由度。

詞語x和詞語y的互信息MI(x,y)體現了兩個詞之間的依賴程度，其計算方法如下：

(6)

其中，P(x,y)是詞語x、y的共現詞頻，P(x)、P(y)定義類似。互信息越高，說明詞語x、y相關性越高，組成術語短語的可能性越大。

詞語x的左右熵H(x)指該詞左右邊界的信息熵，其計算方法如下：

log2P(xb|x))

(7)

其中，A是x的前序詞語集，B是x的后序詞語集。x的左右熵越大，說明該詞的周邊詞越豐富，自由程度越高，x獨立成為一個詞的可能性越大。

通過計算互信息和左右熵進一步處理通用分詞工具的分詞結果，可以發現行業領域的特有詞語搭配，這些特有搭配往往就是行業術語。

③規則過濾，篩選去除非詞。

由于語料中噪聲和算法的誤差，前述無監督的候選詞抽取結果中可能含有少量的非詞，需要通過專家規則進行篩選。

④新詞發現，對比軟件測試資產語料和背景語料，進一步篩選特征詞[10]。

前述通過詞頻提取的候選詞集中除了特有的術語還包括通用的詞匯和短語。 因此，對于候選詞x，通過對比該詞在不同語料中的信息量進行打分，其打分函數定義如下：

(8)

其中，平滑參數μ是一個較小的正數，為了避免在背景語料中x詞頻為0的情況下得分為無窮大。在該打分函數中，如果詞語x在軟件測試資產語料中詞頻PD(x)比在背景語料集中語料Ti的詞頻PTi(x)更高，那么會得到更高的分數，選擇得分前50%的候選詞作為特征詞。

⑤語義聚類，通過詞向量聚類獲取近似領域詞集[11]。

結合特征詞表，在軟件測試資產和行業標準語料進行分詞并訓練一個Word2Vec模型，根據Word2Vec得到的詞向量來對詞進行聚類。算法以術語樹中的節點作為種子詞，利用相似的傳遞性計算近似詞集。為了盡量避免迭代過程中的指數偏移，以指數衰減的方式迭代計算詞向量余弦相似度，將近似詞聚為一類，每一類包含且僅包含一個種子詞，連接到基本術語樹中的相應節點形成完整的領域術語圖譜。相似度計算方法如下：

(9)

(10)

參數α>0是指數衰減常數，決定相似度隨迭代的衰減速度。第一輪迭代時，將所有與種子詞k相似度N0(x,k)超過閾值的特征詞x加入集合；之后每輪迭代將與集合中特征詞x相似度Nt(x,y)超過閾值的特征詞y加入集合；直到集合元素不再增加時，得到x的近似詞集合，將該集合所有元素加入術語樹，并與種子詞k建立相似關系，最終得到領域術語圖譜。

4 基于知識粒度的模糊置信度計算

經典模糊知識系統中，模糊置信度由專家根據先驗知識賦予，這種方法較為主觀，且在實例較多的知識系統中工作量十分龐大。粗糙集理論是一種處理不精確、不完全數據的數學理論，目前已經廣泛應用于機器學習、知識發現、數據挖掘等場景。在經典Pawlak粗糙集理論中，知識指根據特征對論域進行分類所得的子集，知識庫定義為一個粗糙近似空間AS=(U,R)，其中U是論域，R是在U上的一族等價關系。

定義4：知識粒度[12]。設AS=(U,R)是一個知識庫，R∈R是一個等價關系，R對U劃分的等價類集U/R={X1,X2,…,Xn}，那么知識R的知識粒度為：

(11)

知識粒度可以描述知識的分類能力，知識粒度越小，其劃分的等價類越精細，那么知識的分類能力越強。軟件測試知識的不確定性可以歸為兩類，一是概率性，即軟件測試知識本身具有概率性；二是模糊性，即在知識圖譜中用于描述知識的術語不清晰或不準確。以模糊置信度建模特征術語對軟件測試資產的影響程度。每一條軟件測試資產數據都涉及若干特征術語，這些特征術語體現了該軟件測試資產的決策因素，將知識的概率性和模糊性統一以置信度的形式表示。置信度越高表示特征術語w對測試資產A的代表性越強。文中特征術語和軟件測試資產的模糊置信度實質上即通過特征術語區分軟件測試資產的能力[13-14]，有研究表明決策屬性的知識粒度越小則其信息熵越大[15-16]，基于知識粒度計算模糊置信度，評價相應特征對軟件測試資產的信息熵影響，也即其決策影響程度是有效可行的。對于每一條資產A，通過三類概念特征集合{wd,wt,ws}表征，這里wd表示資產A中涉及的問題領域概念子集wd∈Wd，wt,ws類似。在圖譜中搜索與資產A相關的所有概念，相似概念則合并為一項，通過概念特征集{w1,w2,…,wn}表示一條資產數據。計算術語wi作為資產A特征的模糊置信度分為兩步：粗糙近似空間構造、模糊置信度計算。

4.1 粗糙近似空間構造

構造粗糙近似空間AS=(U,R)，即確定論域U和等價關系族R，由于R中的等價關系實際上指特征屬性相同或近似而不可區分的論域對象集。因此構造Pawlak粗糙近似空間等價于確定一個知識表達系統S=(U,P,V,f)，其中U為對象的非空有限集合，P是屬性的非空有限集合，V是P的值域，f:U×P→V是信息函數為每個對象的每個屬性賦值，有?a∈A,?x∈U,f(x,a)∈Va。文中特征術語相同的測試資產是不可區分的對象，論域UA為軟件測試資產實例集，V為論域中所有測試資產的特征術語全集，P為V的父概念集。若以模糊知識圖譜中的測試資產全集為論域，存在兩個問題：一是搜索空間過大，計算效率低；二是大部分測試資產與資產A特征無關，大量無關測試資產被分為一類使得知識粒度接近于1，不能有效區分特征術語wi對資產A的分類能力。因此，需要篩選論域，構造與資產A和特征術語wi粗糙近似空間，在軟件測試模糊知識圖譜GF中確定測試資產實例A與其特征術語wa相關的粗糙近似空間方法如下：

算法 1：軟件特征粗糙近似空間構造。

Input：軟件測試模糊知識圖譜GF、測試資產實例A、A的一個特征術語wa

Output：資產A相關的知識表達系統SA

#搜索特征wi的中心特征k及其父概念K

1 searchk,KfromGF, whichwa≈k∧k∈K

#搜索概念K相關的所有A同類測試資產集UA作為論域

2 for everyk∈K:

3 search allAifromGF, whichAi∽k∧type(Ai)=type(A),

putAiinUA

#搜索條件屬性集P及其值域V，信息函數f

4 forAiinUA:

5 searchkij,Kij, whichAij∽kij∧kij∈Kij

6 putKijinP

7 put((Aij,Kij)→kij) inf

8 searchk∈Kij, putkinV

#輸出粗糙近似空間

9 output:(UA,P,V,f)

4.2 模糊關系置信度計算

通過概念類K的知識粒度刻畫資產A對術語wi(wi∈K)的置信程度，K的知識粒度越小即認為這一類概念對測試資產的劃分描述能力越強，是有效的分類特征[15-16]，通過z型模糊器計算得出的A與wi的模糊關系置信度越高。

定義5：概念K的決策能力。以概念K作為條件屬性對論域做劃分，K的若干子概念{wk1,wk2,…,wkl}，將論域劃分為l個等價類。那么K的分類能力CK計算如下：

(12)

定義6：模糊關系置信度。設有測試資產A，wi是表征A的一個概念特征，根據前述粗糙近似空間構造方法得到論域UA和條件屬性集P={K,K1,…,Km′}，那么wi與A的模糊關系隸屬度為：

μ(A,wi)=zmf(CK)=(1+eρ(CK-θ))-1

(13)

參數ρ、θ決定模糊函數的平滑程度。模糊關系置信度μ(A,wi)∈(0,1)描述了在產生資產A的軟件測試活動中，術語wi所代表的領域知識對決策過程的影響程度，置信度越高則影響力越強，在對資產A進行知識推理時，該特征的重要性越高。

5 實例驗證

本節通過一個實例驗證了該方法的可行性

5.1 實驗條件

采用neo4j圖形數據庫構建實例知識圖譜，數據來源于作者所在單位承擔的軟件測評任務和網絡搜集的行業標準等數據，具體見表1。

表1 實驗條件

5.2 結果分析

軟件測試資產知識圖譜中知識實體、關系的情況如表2和表3所示。

表2 知識實體統計

表3 資產知識關系情況

從表2、表3可以發現軟件測試資產知識圖譜實體關系較為稀疏，知識實體多且分散，如果用關系數據庫存儲知識實體，一方面不便于建立實體-實體、實體-特征的關聯關系，進行復雜條件查詢時大量鏈接操作會極大影響查詢效率。另一方面，知識圖譜比關系數據庫更有利于后續知識推理任務。

領域術語圖譜情況如表4所示。

從表4可以看出，由于測試人員撰寫不規范，軟件測試資產中的領域術語存在大量近似詞，模糊化的知識表述對知識復用造成了嚴重阻礙，直接進行關鍵詞查詢可能造成錯誤或遺漏。領域術語圖譜可以視為一種結構化的近義詞典，通過先驗知識提高了知識實體查詢的準確率和查全率，大大減弱了測試知識復用中由測試資產模糊性帶來的知識錯漏問題。

表4 領域術語圖譜實體關系

表5對比了使用關鍵詞查詢測試知識實體時，有、無領域術語圖譜輔助的兩種情況。

表5 準確率/召回率對比

6 結束語

該文設計了一種可以表達不確定性知識的軟件測試知識圖譜構建框架，能夠利用測試需求、測試用例、問題報告三類軟件測試資產和行業標準等領域知識建立軟件測試知識圖譜，提出了一種基于信息量的領域術語挖掘方法，在此基礎上構建了領域術語圖譜作為軟件測試資產的特征。為了強調軟件測試中的不確定性，使用通過特征術語的知識粒度建模計算其在軟件測試過程中的決策影響程度。通過為軟件測試資產的特征賦予模糊置信度，構建了軟件測試模糊知識圖譜，為后續軟件測試不確定知識推理做鋪墊。