基于知識圖譜的測試用例復用方法

夏傳林，鄭 巍，譚莉娟，王小良

(1.南昌航空大學 軟件學院，江西 南昌 330063； 2.南昌航空大學 軟件測評中心，江西 南昌 330063)

0 引 言

測試用例復用是從已有的多個項目中尋找相似的測試用例，故而這些項目的測試場景要相似，而本文所有項目中的測試用例大部分是對硬件接口的測試，所以具有復用的可行性。測試用例是保證軟件測試質量的關鍵，一個好的測試用例有利于發現更多的軟件缺陷[1-4]，從而縮短軟件開發周期，提高測試效率。在軟件測試過程中，可以修改高度相似的測試用例，以減少測試用例設計的工作量[5,6]。測試用例復用成功的關鍵就是找到用戶真實需要的測試用例，并推薦給用戶。目前，涉及測試用例復用的研究較少，大部分工作都集中在構建測試用例庫，以此達到測試用例復用的目的。但是，此類方法僅使用了基于關鍵字的檢索模型，在靈活性和復用率方面仍有所欠缺。

針對上述問題，本文提出了一種基于知識圖譜的測試用例復用方法(test case reuse based on knowledge graph，TCRKG)，TCRKG通過對項目測試文檔數據進行處理，抽取出和測試用例有關的項目、測試項、測試用例、測試記錄、問題報告單等基礎特征。本文主要包括3個核心內容：構建測試用例知識圖譜、改進樸素貝葉斯分類模型、測試用例相似度計算。根據專家經驗和測試文檔對本體進行設計，構建測試用例圖譜，替換傳統的測試用例庫。為了使測試用例復用模型更加靈活，對改進的樸素貝葉斯分類器設置了常用的多種問題模板，相比于決策樹、邏輯回歸、支持向量機等分類方法，樸素貝葉斯在時間花費、泛化性能上更適合本文的應用場景。最后在實驗中驗證了該方法能夠有效提高測試用例復用，找到軟件缺陷。

1 相關工作

本文主要是通過構建知識圖譜的方法來對測試用例復用進行研究，因此相關工作主要分為測試用例復用研究和知識圖譜。

1.1 測試用例復用研究

測試用例的設計和編寫需要花費大量的時間，而測試用例復用能夠大大節約時間，提高效率[7,8]。從本質上來講，測試用例復用就是從已有的測試用例中找出用戶真實需要的測試用例。

近年來，出現了一些新的針對測試用例的方法研究，Zhang等提出了一種基于控件遍歷的測試方法，能夠基于深度優先算法自動生成測試用例，并且該方法能夠增強測試用例的復用性[9]。Ge等提出了一種基于線性融合和項目結合的用戶協同過濾算法[10]，該算法雖然可以更有效地提高測試用例推薦精度，但存在計算成本高，泛化性能差的問題。Tong等利用本體對測試用例進行復用，提供了靈活的查詢需求[11]，卻缺少測試用例相關的上下文內容，沒有對問題報告單、測試記錄等和測試用例極其相關的內容進行研究。綜上所述，以上方法很難從海量數據中挖掘測試用例的特征以達到精準復用的目的，不能獲得測試用例的上下文環境。

1.2 知識圖譜

知識圖譜是由谷歌(Google)公司正式向外界發布，自此，知識圖譜正式走入大眾視野。知識圖譜本質上是語義網的知識庫，由節點和邊組成，節點表示實體，邊表示實體與實體之間的關系。知識圖譜可以分為通用知識圖譜和領域知識圖譜。例如通用知識圖譜有DBpedia、YAGO、Freebase等；領域知識圖譜有地理信息領域知識圖譜[12]、中醫藥知識圖譜等。

知識圖譜的應用場景主要有智能搜索、智能問答、智能推薦、情報分析。Pedro Szekely等利用網絡數據構建知識圖譜[13]，用來打擊人口販賣。Feng-Lin Li等將知識圖譜應用到電子商務領域[14]，有助于理解用戶需求，回答售前問題和生成解釋文本。Sen Hu等通過子圖匹配知識圖譜來回答自然語言問題[15]，可以有效地解決歧義問題。測試用例復用也可以看成是一種智能推薦，用戶提出問題，通過知識圖譜來找尋答案。基于知識圖譜的智能搜索可以直接給出知識卡片而不是給出相關的鏈接序列。在知識圖譜的幫助下，檢索引擎可以將搜索關鍵詞映射到知識圖譜中匹配度較高的一個測試用例上，最后以知識卡片的形式展現給用戶。

2 基于知識圖譜的測試用例復用方法

在本節中，首先介紹整個測試用例復用模型框架流程，然后對本文3個核心內容：構建知識圖譜、改進樸素貝葉斯分類模型、相似度計算依次進行介紹。

2.1 模型框架

圖1展示了測試用例復用的整個流程，包括3個核心部分。

圖1 測試用例復用模型

(1)構建測試用例知識圖譜：構建測試用例知識圖譜是本文方法的前提，其過程主要是依據專家經驗結合項目文檔數據對本體進行設計，從半結構化的文檔數據中提取出測試用例、測試記錄、問題報告單等相關的數據，最后填充實體構建知識圖譜。

(2)改進樸素貝葉斯分類模型：本文設計了常用的多種問題模板，每種問題模板都有很多問題樣例。首先同種問題模板中的問題樣例高度相似，不同種類的問題模板也有一定的相似度，這就會引發一種情況，如果某種問題模板的問題樣例數量特別多，那么其所對應的特征也很多，最后通過樸素貝葉斯分類器來計算概率就會出現特征多的類別概率偏大，所占特征少的類別概率偏小。為了解決上述問題，本文提出了兩種方式來提高樸素貝葉斯分類的準確率。其一，通過設置測試用例自定義的詞典；其二，通過給每種問題類別設置一個權值，從而提高模型分類的準確率。

(3)測試用例相似度計算：通過樸素貝葉斯分類之后可以確定問題模板類別，然后就是通過知識圖譜尋找用戶需要的答案。問題模板分為兩類，一種是可以直接從知識圖譜中找到答案，例如，功能測試有多少測試用例；一種是需要通過相似度計算才可以得到答案。用戶可以輸入一個或多個測試用例屬性的內容、關鍵字等，通過這些與知識圖譜中的測試用例進行相似度比較，具體計算方法在2.4節中闡述。

2.2 構建知識圖譜

構建知識圖譜主要包括3個步驟：

(1)特征提取：本文構建知識圖譜的數據來源主要是項目測試文檔，屬于半結構化數據，依據專家經驗和測試用例的特征，從半結構化數據中提取出和測試用例相關的特征數據[16,17]，最終將數據轉為結構化數據，測試用例設計樣例見表1。

表1 測試用例設計樣例

(2)本體構建：本體是用于描述一個領域的數據集合，屬于知識圖譜的模式層。在測試用例的本體設計中，本文采用七步法進行構建。圖2中展示了核心本體，包括測試用例信息、項目、測試項、測試項明細、測試記錄和問題報告單等數據，能夠更加全面覆蓋測試用例的關鍵信息。

圖2 測試用例核心本體

(3)生成圖譜：圖3為部分測試用例知識圖譜，圖中共有5種顏色的圓，每一種顏色表示一種實體，實體與實體之間的連線表示兩者的關系，實體的屬性在圖中沒有顯示出來。通過測試用例知識圖譜，可以很清晰看到項目、測試項、測試用例、問題報告單之間的關聯，以及測試用例的分布、缺陷的分布。在測試用例復用中，就能夠優先匹配到那些能夠發現軟件缺陷的測試用例。

圖3 部分測試用例知識圖譜

2.3 基于樸素貝葉斯的分類模型

測試用例復用模型不僅應該能夠檢索到用戶需要的測試用例，還能夠找到和測試用例相關聯的信息。針對這個問題，本文通過使用樸素貝葉斯分類模型，來更好滿足用戶各種問題需求。

為了提高樸素貝葉斯的準確率，本文通過兩種方式對其進行改進：設置測試用例自定義的詞典，來提升關鍵詞的識別；對類別進行加權，減少模型過擬合。

在訓練樸素貝葉斯分類模型之前，需要自定義詞典和設置好問題模板。如表2所示列出了自定義詞典添加的內容，詞典中添加的每種內容都必需有唯一的詞性。如此，利用分詞工具才能準確的將用戶輸入的內容進行分詞，并且能夠識別出自定義詞典中的內容。

表2 自定義詞典

本文設置了14種常用問題模板，每種問題模板都有很多問題樣例，用來模型訓練。經過樸素貝葉斯分類確定輸入的是哪種問題模板后，其中有13種是可以直接生成查詢語句從知識圖譜中檢索答案，而另一種則需要通過測試用例相似度計算來匹配。

問題模板集合C={y1,y2,…,y14}， 表示14種問題模板，I={I1,I2,…,In} 是輸入集合，每一個元素是一個待分類項，Ii={x1,x2,…,xm} (i=1,2,…,n)，Ii表示當前用戶輸入的內容，每個x為一個特征屬性。對Ii分詞后會得到每個Ii的特征屬性x， 不同的Ii對應x的數量也不相同。

首先通過分詞將所有問題模板中的樣例進行分詞得到k維向量，然后開始訓練模型。根據條件概率可得到式(1)

(1)

為得到當前Ii所屬類別，需要對每種類別設置一個權值w={w1,w2,…,w14}，w∈(0,1)， 通過式(2)來計算

P(yt|Ii)=max{P(y1|Ii)w1,P(y2|Ii)w2,…,P(y14|Ii)w14}

(2)

式(2)中為當前Ii屬于哪種類別，則求出Ii在14種問題模板當中的所有概率，對每個類別計算P(yt)， 選擇概率最大的類別作為Ii的類別。式(1)中，因為分母對于所有類別為常數，所以只需將分子最大化即可

P(Ii|yt)P(yt)=P(x1|yt)P(x2|yt)…P(xm|yt)P(yt)

(3)

對每個類別計算P(Ii|yt)P(yt)， 以P(Ii|yt)P(yt) 作為Ii所屬的類別。

2.4 相似度計算

Mu等提出了基于文本相似性對測試用例復用進行研究[18]，但沒有考慮將輸入內容分解對應到每個屬性上。本文經過改進的樸素貝葉斯分類模型處理后，會從14種問題模板中找到概率最高的一個作為其真實類別。用戶可以輸入測試用例的多種屬性內容，根據這些屬性在知識圖譜中找到一個大致范圍的測試用例集，最終計算相似度來確定結果。

測試用例集合M={M1,M2,…,Mn}， 測試用例屬性Sk，S={S1,S2,…,Sk}， 屬性對應的權重w={w1,w2,…,wk}。 將測試用例所有屬性進行分詞，然后進行onehot編碼，則tik表示測試用例Mi在屬性Sk上onehot編碼為1的數量，從而可以將相似度計算轉化為式(4)中的相似值

(4)

N(Mr,Mi)是指測試用例Mr(用戶輸入的內容)和測試用例集合中的Mi的相似值

N=max{N(Mr,M1),N(Mr,M2),…,N(Mr,Mi)}

(5)

N就是測試用例集合M中N(Mr,Mi) 的最大值，此時的Mi就是找到相似度最大的測試用例。例如，圖4顯示了測試用例相似度計算的一個例子，其中圖4(b)是用戶輸入的數據，可以根據用例標識、用例描述、測試類型、需求追溯等多種屬性來計算測試用例的相似度。根據圖4(b)中的信息，找到用戶需要的測試用例，也就是從知識圖譜中找出相似度最大的測試用例。從圖4(b)中可以看出用例描述屬性中的關鍵字“指令”、“故障”、“命令”的多個屬性特征都與圖4(a)相同，雖然關鍵字“發送”在圖4(a)和圖4(b)中的用例描述中都能找到，但是該關鍵字是無效關鍵字，因為其上下文明顯不一致，所以在計算相似度時不會考慮該關鍵字。根據式(4)和式(5)，求得圖4(b)、圖4(a)之間的相似度為12.34%，大于圖4(b)、圖4(c)之間的相似度4.98%。

圖4 測試用例相似度計算示例

3 實 驗

在本節中，首先對實驗數據進行介紹，然后描述實驗的評價指標，最后對實驗結果進行分析。

3.1 數據描述

本文實驗中的所有數據來源均為南昌航空大學軟件學院軟件測評中心，擁有64個軟件項目，23 212個測試用例。數據格式為半結構化的測試文檔，最終將半結構化的數據轉為結構化的數據。

3.2 評價指標

為了更加全面的評價TCRKG，本文從3個方面對模型進行評價。首先是模型的準確度，要精準找到用戶想要復用的測試用例，問題模板的精度就非常重要，因為那是找到好的測試用例的關鍵，因此本文通過3個廣泛使用的指標：精確度(Precision)、召回率(Recall)和F1測量標準來對問題模板匹配的精度進行評價，并將改進后的樸素貝葉斯與改進前的樸素貝葉斯進行性能對比。其次，為了檢測知識圖譜的效率，通過和傳統構建測試用例庫的方法進行比較，通過檢索時間，和搜索復雜度兩個指標來進行評價。最后，為了檢驗本文中TCRKG在實踐中的有效性，設置A、B兩個對照組，分別對4個軟件S1，S2，S3，S4進行軟件測試，A組使用本文中的測試用例復用方法，作為對照組，B組使用傳統測試用例庫的方法。最終以測試用例復用數量，和找到缺陷的個數作為評價指標。

3.3 實驗結果

3.3.1 模型精度

圖5、圖6、圖7顯示了樸素貝葉斯分類模型改進前和改進后的Precision、Recall、F1值的對比。就精確度而言，從圖5中可以看出樸素貝葉斯改進后的精確度都要優于改進前的精確度，樸素貝葉斯分類改進前精確度平均為90.05%，改進后為94.09%，精確度平均提高了4%。圖6中樸素貝葉斯改進后的召回率都要大于改進前的召回率，樸素貝葉斯分類改進前召回率平均為76.60%，改進后為83.76%，召回率平均提高了7%。圖7中樸素貝葉斯改進后的F1都要大于改進前的F1，樸素貝葉斯分類改進前召回率平均為82.84%，改進后為88.51%，F1值平均提高了6%。從整體上來看，模板5和模板12的Precision、Recall、F1值都偏低，其原因是因為模板5和模板12的樣例數量相比于其它模板的數量要少很多，所以導致這兩種問題模板所占特征偏少。因此本文通過自定義詞典和給問題類別加權值的方法對樸素貝葉斯進行改進，有效改善了此類問題對分類結果的影響，并且整體性的提高了樸素貝葉斯的分類性能。

圖5 精確度對比

圖6 召回率對比

圖7 F1值對比

綜上所述，通過添加自定義詞典和給問題類別設置權值的方法可以有效解決問題模板樣例數量相差較大所帶來的影響，并且可以有效提高樸素貝葉斯分類模型的準確率，為提高測試用例復用奠定了基礎。

3.3.2 檢索效率

為了驗證知識圖譜的檢索效率，本文從復雜度和時間消耗兩個方面進行對比，復雜度是指兩種方案解決同一個問題數據庫需要進行多少步驟。對14種問題模板分別進行5次實驗，將5次實驗的平均數據作為時間消耗值。

圖8和圖9展示了傳統用例庫與知識圖譜檢索復雜度比較，為了更加直觀比較兩種方法復雜度的大小，本文將傳統用例庫每種問題模板的復雜度都歸一化到1，然后知識圖譜的復雜度以傳統用例庫復雜度大小為基準，復雜度越大，表示執行步驟越多，效率越低。可以看出，傳統測試用例庫的復雜度都比知識圖譜的復雜度大，這就間接表明通過知識圖譜進行檢索的效率高。

圖8 傳統用例庫復雜度

圖9 知識圖譜復雜度

圖10 傳統用例庫與知識圖譜檢索時間消耗比較

綜上所述，無論是從復雜度還是從時間消耗來看，基于知識圖譜的方法檢索效率都要優于基于傳統測試用例庫的方法。

3.3.3 實踐對比

為了檢測TCRKG在實際中的使用效果，由軟件測評中心組織測試人員測試4個軟件S1，S2，S3，S4，設置A、B對照組對4個軟件進行測試。為了盡可能排除測試人員所帶來的影響，A、B兩組人員都是同年級學生，本科接受課程教育相同。A組為使用基于知識圖譜復用方法，作為對照組，B組是基于傳統用例庫的方法。

圖11顯示了兩種方法測試用例復用數量的對比，A組明顯比B組復用的測試用例要多，平均高于B組20%～30%。

圖11 測試用例復用數量

如圖12所示，展示了S1，S2，S3，S4這4個軟件的真實缺陷數量和基于傳統用例庫、基于知識圖譜復用方法測試到正確的缺陷數量。4個軟件的缺陷類型主要為接口問題和功能問題缺陷，其中90%的缺陷都在以往的測試中被典型測試用例發現過。A組測試出將近2/3的真實缺陷數量，而B組測試出的數量在1/3～2/3之間。不僅如此，由于A組使用的是基于本文中的復用模型，可以更加準確復用需要的測試用例，而B組只能根據少量關鍵字進行匹配，不能精準找到用戶需要的測試用例，所以在耗時方面，A組大約只使用了B組一半的時間。通過實踐對比，驗證了本文的測試用例復用方法確實能夠減少測試人員花費的時間，并且提高了軟件缺陷的發現率。

圖12 缺陷數量對比

綜上所述，通過A、B兩組對4個軟件S1，S2，S3，S4進行測試的對照實驗來看，A組也就是本文中基于知識圖譜的測試用例復用方法能夠復用更多的測試用例，發現更多的軟件缺陷。

4 結束語

針對傳統測試用例復用方法的不足，本文提出了一種基于知識圖譜的測試用例復用方法。該方法首先利用已有文檔提取結構化數據，構建知識圖譜，從而獲得了與測試用例相關的上下文信息；然后在測試用例匹配過程中，基于樸素貝葉斯分類模型和問題模板，明確用戶的檢索意圖；最后利用相似度計算確定最佳的測試用例。實驗結果表明，TCRKG比傳統測試用例復用方法具有更高的推薦準確度。TCRKG不僅能夠挖掘測試用例的潛在信息，還能將傳統用例庫中孤立的測試用例進行關聯，達到“1+1>2”的效果。而本研究的不足點就是沒有考慮測試用例的語義信息，在進行相似度計算的時候沒有將測試用例的語義信息考慮在內。所以我們下一步工作就是將測試用例的語義信息加入到知識圖譜中。