基于代碼相似性的測試用例重用及生成方法

劉巧韻，楊秋輝，洪 玫，劉美英，劉盈盈

(四川大學 計算機學院，四川 成都 610065)

0 引 言

針對代碼重用現(xiàn)象[1-3]，引入測試用例重用技術[4]，通過普遍存在的測試用例相似現(xiàn)象，將現(xiàn)有測試用例信息重用到測試用例生成等領域中，以加快測試用例設計，減少后續(xù)測試用例編寫工作量，提高測試效率和質(zhì)量。然而，現(xiàn)有測試用例重用主要提供重用建議，且忽略了代碼間的語義相似信息；另外，大部分測試用例生成工作都需要人工介入。

本文提出了一種基于代碼相似性的測試用例重用及生成方法，包括相似性代碼檢索、測試用例重用及生成兩大步驟。首先使用基于文本和基于度量的代碼相似性檢測技術檢索被測代碼的語法和語義相似代碼，并將結果劃分為4種相似類型；然后針對不同相似類型，使用更名重用、補充重用兩種重用策略。在更名重用中，采用抽象語法樹信息替換方法對現(xiàn)有測試用例基本信息進行修改以生成新測試用例。在補充重用中，使用GumTree算法對現(xiàn)有測試用例補充測試語句，生成新測試用例。本文提出的方法能更有效地利用現(xiàn)有測試用例信息，自動化生成測試用例，從而提高測試效率，減少測試工作量。

1 相關工作

近年來，軟件測試重用技術發(fā)展愈加成熟，國內(nèi)外已有大量研究成果。其中，面向測試過程中的代碼重用技術是最主要的重用技術之一。

Mathias等[5]提出一種自動生成攜帶測試預言的測試克隆方法，并實現(xiàn)了工具TestClone通過提取使用相同邏輯的測試代碼，將現(xiàn)有測試用例進行轉換生成新的測試用例。Gang等[6]提出AppFlow測試系統(tǒng)，可用于合成健壯性強且可重用的UI測試。Werner等[7]提出一種自動化測試推薦方法，通過構建Junit測試文件儲存庫創(chuàng)建測試用例搜索引擎，可自動索引WEB開源項目中的測試用例。Yunwei等[8]提出一種基于測試覆蓋率準則的測試可重用性評價方法，通過研究測試用例的可重用性、重寫模式和測試覆蓋率之間的關系，總結了程序修改后的重寫模式，并研究了此類模式在修改程序測試中的作用，得出影響測試用例可重用性的覆蓋率準則。Ducasse等[9]提出了一種基于測試的可重用性特征組合重用測試的方法，該方法針對代碼中不同繼承層次結構中的類定義了測試方法的特性，根據(jù)不同特性組合測試用例形成新的測試類重用到測試過程中。Suriya等[10]實現(xiàn)了易于開發(fā)和進化的通用測試用例庫以用于測試用例重用，通過Android平臺框架項目中測試用例普遍存在的重復現(xiàn)象，總結了重復模式并使用通用形式表示，以便進一步重用測試用例。Robert等[11]設計了抽象框架RASHID，利用二部圖表示不同源碼、測試用例之間的關系，為開發(fā)人員推薦可重用的測試。Mostafa等[12]介紹了利用克隆檢測技術進行測試用例推薦模板實現(xiàn)方法，使用程序當前上下文挖掘儲存庫中相似代碼并為此推薦相匹配的單元測試用例。

本文提出了一種基于代碼相似性的測試用例重用及生成方法，通過代碼相似性檢測得到可重用測試用例，在進行一系列處理的基礎上生成新測試用例。該方法改進了現(xiàn)有測試用例生成方法的生成效率，節(jié)約了時間成本；同時，在代碼相似性檢測上，突破了已有測試用例重用技術僅考慮語法相似的局限，綜合了語法、語義等多個代碼相似因素，提升了代碼相似性檢測的準確性，擴大了測試用例重用范圍。

2 方法描述

本文提出了一種綜合語法和語義信息檢索相似代碼，并采用抽象語法樹信息替換算法和GumTree算法修改現(xiàn)有測試用例的測試用例重用及生成方法。整體流程如圖1所示。

圖1 方法流程

2.1 相似性代碼檢測

相似代碼也稱為克隆代碼[13]，即忽視源代碼中的注釋，只要連續(xù)代碼序列相似性達到一定閾值，便形成克隆關系。具有克隆關系的兩個代碼段稱為一個克隆對，多個代碼段稱為一個克隆類。

代碼相似類型主要分為兩類[14]：語法相似性和語義相似性。進一步細分，可分為4種類型[14-16]：屬于語法相似的Type-1、Type-2、Type-3和屬于語義相似的Type-4。其中，Type-1是精確克隆類型，指兩個相似代碼片段在代碼級別上沒有差別，互為精確副本；Type-2是改名克隆類型，指兩個相似代碼片段在代碼級別上存在變量名等名稱修改情況；Type-3是近距克隆類型，指兩個相似代碼片段共用同樣的語法結構，但存在語句增加或修改的情況；Type-4是語義克隆類型，指兩個相似代碼片段的語法結構可能不同，但語義和功能是相同的。

相似性代碼檢測根據(jù)相似度在源代碼中找到相似源碼，并以克隆對或克隆類的形式反饋結果。本文分別使用基于文本和基于度量的技術檢測不同類型的相似代碼。

2.1.1 基于文本的代碼相似性檢測

基于文本的代碼相似性檢測技術不受編程語言的限制，主要用于檢測代碼的語法相似性。

首先，對源代碼進行預處理。刪除源代碼中的注釋、空格、空行等，給定粒度級別(如方法級別)進行片段提取，生成候選克隆代碼序列；對提取出的代碼片段進行句法形式過濾或抽象，如對代碼片段中的聲明語句進行過濾，對表達式進行抽象等，并表示為字符串形式。該過程的目的在于提取有效數(shù)據(jù)，消除代碼中特定聲明或表達式等帶來的影響。

然后，進行克隆代碼的比較分析。首先選擇一個預處理后的代碼片段作為參照，然后對與其在給定差異大小范圍內(nèi)的所有代碼片段進行聚類，并對代碼片段進行成對線性比較，找到每對的最長公共子序列。該過程使用了優(yōu)化的最長公共子序列算法(LCS)[17]。

最后，計算候選克隆對的唯一子序列項百分比(UPI)[18]。如果UPI值低于設定的閾值，則認為該代碼對是彼此的克隆副本。設定不同閾值以區(qū)分不同相似類型，檢測Type-1、Type-2和Type-3。UPI計算公式如式(1)所示

(1)

式中：TotalItems表示總子序列數(shù)量；UniqueItems表示兩個字符串序列中不屬于最長公共子序列子串的子序列。

待比較類中所有代碼片段分析完成后，選擇下一個參照代碼段，重復該步驟，直到處理完所有候選代碼。

2.1.2 基于度量的代碼相似性檢測

基于度量的代碼相似性檢測技術能忽略代碼的語法信息，主要用于檢測代碼的語義相似性。

首先，對源代碼進行預處理并構建代碼指紋庫。使用Java環(huán)境命令生成源代碼的字節(jié)碼形式，以減少對語法結構的關注；使用松弛化的指紋提取方法[14]提取字節(jié)碼文件中的Java類名和方法名，并分別歸入類指紋庫和方法指紋庫。

然后，分別使用語法模式匹配和語義內(nèi)容匹配構建相似性度量。將兩個指紋庫中的指紋利用基于Semantic Web的技術進行模式匹配。該技術的思想是利用指紋順序判斷模式相似性，即分別判斷類指紋順序和方法指紋順序，如果指紋順序相同，則認為模式相似。這一過程可產(chǎn)生類模式相似性和方法模式相似性兩個度量準則。

同時，為了減少模式匹配中的假陽性結果，繼續(xù)進行內(nèi)容匹配。使用Jaccard指數(shù)衡量兩個方法塊之間的內(nèi)容相似性。Jaccard指數(shù)計算公式如式(2)所示

(2)

式中：S1和S2分別表示兩個代碼片段的類指紋集合和方法指紋集合。這一過程可產(chǎn)生類內(nèi)容相似性和方法內(nèi)容相似性兩個度量準則。

最后，結合上述4個度量準則計算兩個代碼片段的總體相似性，此處使用Keivanloo等[14]提出的計算公式，如式(3)所示

(3)

其中，Ca、Cb表示兩個候選克隆代碼段；ti、mi分別表示兩個代碼片段的類指紋集合和方法指紋集合；queryx表示對第x個模式相似值進行查詢，模式相似值的個數(shù)上限為q；Js函數(shù)表示兩個片段Ca和Cb在類級別或方法級別上的Jaccard值的布爾表達式；φ和ω分別為Java類內(nèi)容相似度閾值和方法內(nèi)容相似度閾值，如Js(ta，tb，φ) 為真則表示ta、tb在類內(nèi)容上相似度大于φ。根據(jù)該公式，若兩個代碼片段在4個度量上都有同一表現(xiàn)，則被視為互為克隆副本，否則丟棄。

2.2 測試用例重用及生成

測試用例重用及生成主要包含兩種方法：更名重用和補充重用。更名重用針對Type-1、Type-2及Type-4類型，該3種類型無語句增刪情況，僅需要對測試用例的參數(shù)類型等屬性進行修改即可；而補充重用則針對包含語句增刪情況的Type-3類型，即在更名重用的基礎上，還需對測試用例缺失語句進行補充。

對Type-1、Type-2及Type-4，使用更名重用方法。提取被測代碼的抽象語法樹(AST)，從AST中抽取源代碼的類名、方法名和參數(shù)類型，對現(xiàn)有測試用例的相應屬性進行修改，實現(xiàn)AST信息替換，生成新測試用例。該算法偽代碼如下：

算法1：抽象語法樹信息替換算法

輸入：要解析的Java源文件路徑sourcepath，現(xiàn)有測試用例文件TC及其路徑TCPath

輸出：新測試用例

Class JavaASTparser{

procedure GeneASTparser(sourcepath)

//獲取被解析文件

bindingKeys ← {"class", "interface",

"arraytypes", "primitive types", "field"}

result ← createASTs(sourcepath, encodings,

bindingKeys)

}

Class VisitAST{

procedure visit(field.node, type.node, method.node)

//訪問源代碼參數(shù)、類和方法屬性

fieldlist ← ("FieldName" = field.node.name)

typelist, fieldlist ←

("ClassName" = type.node.name)

methodlist ←

("MethodName" = method.node.name)

SimAST ← fieldlist + typelist + methodlist

//存儲屬性

procedure GetTCInfo(TC)

//獲取測試用例AST中的信息

GeneASTparser(TCpath)

visit(field.node, type.node, method.node)

tcinfo ← fieldlist + typelist + methodlist

GeneTCFromSimAST()

}

Class GeneTC{

procedure GeneTCFromSimAST()

//根據(jù)AST替換測試用例信息

if tcinfo.fieldname = tcinfo.typename

then oldtc.fieldname ← simAST.typename

else tcinfo.fieldname = tcinfo.classname

then oldtc.fieldname ←

simAST.classname

newtc ← oldtc //獲得新測試用例

}

對判斷為Type-3的類型，使用補充重用方法。按源代碼與被測代碼的相似性由高到低排列測試用例得到測試用例序列，選擇序列中相似性最高的測試用例進行更名重用，得到候選測試用例。然后使用GumTree算法[19]將測試用例序列中的其它測試用例分別逐一與該候選測試用例匹配，該過程對候選測試用例中缺失的語句進行補充生成新的測試用例序列。最后選擇生成序列中覆蓋率最高的測試用例作為生成的新測試用例。

3 實驗驗證

3.1 實驗對象

選擇Java開源數(shù)據(jù)集Defects4j中的3個項目：JFreeChart、Apache Commons Lang以及Apache Commons Math，每個項目都包含其不同迭代版本的源代碼及測試用例等信息，見表1。

表1 實驗項目信息

3.2 評估指標

評估指標選擇重用召回率和重用精度。重用召回率用于衡量測試用例成功重用的能力。如果生成的測試用例可以成功執(zhí)行，則認為該測試用例被成功召回，為有效測試用例。召回率越高表明測試用例重用效果越好。其計算方式如式(4)所示

(4)

其中，可重用測試用例數(shù)量表示通過代碼相似性檢測后的所有相似源碼對應的所有可重用測試用例數(shù)量。

重用精度用于衡量測試用例的重用質(zhì)量。如果生成測試用例的覆蓋率大于或基本等于項目中人工編寫的測試用例的覆蓋率(差值不超過1%)，則認為該測試用例的質(zhì)量較好，為正確測試用例。其計算方式如式(5)所示

(5)

3.3 實驗設計

驗證方案可行性，表明本文方法能夠成功對現(xiàn)有測試用例進行重用，生成有效測試用例。在語法相似性檢測中，根據(jù)已有研究[18]，分別取UPI為0.0、0.1和0.3檢測Type-1、Type-2和Type-3；在語義相似性檢測中，根據(jù)文獻[20]對重用精度和重用召回率的研究結果，將式(3)設置閾值q=20、φ=1.9、ω=5.3，進行測試用例重用及生成。

驗證方案有效性，表明本文方法有更好的重用效果，測試用例生成質(zhì)量更高且成本更低。首先，與現(xiàn)有測試用例重用方法比較測試用例重用效果：分別將本文方案與LANDHUSSER等提出的方案[5]、Mostafa等提出的方案[12]重用結果進行比較，計算重用召回率和重用精度；然后，與現(xiàn)有測試用例生成方法比較測試用例生成效率：分別將本文方案與目前廣泛使用的測試用例自動生成工具Randoop[21]、Evosuite[22]進行比較，在本文方法所需時間限制下，分別使用Randoop和Evosuite進行測試用例生成，比較3種方法在相同時間內(nèi)生成測試用例的覆蓋率。

3.4 實驗結果與分析

本文方案重用召回率見表2。

表2 測試用例重用召回結果

由表2可知，3個實驗項目的重用召回率均超過90%，其中最高的是JFreechart，生成有效測試用例2114個，重用召回率達到94.1%；最低的項目Apache Commons Lang也生成了1138個有效測試用例，重用率也達到了90.1%。

這說明本文方法能對現(xiàn)有測試用例進行有效的重用及生成。但也有少部分重用生成后的測試用例執(zhí)行失敗，究其原因主要是某些被測類的參數(shù)過于復雜并且要求非空參數(shù)數(shù)量較多導致新生成的測試用例不能成功執(zhí)行。例如測試類PeriodAxisLabelInfoTest中的testEquals()方法需要聲明參數(shù)info1=new PeriodAxisLabelInfo(c1，df1，sp1，lf1，lp1，b1，s1，dp1)，需要非空參數(shù)8個，而新測試用例只生成了6個參數(shù)，導致測試用例執(zhí)行失敗。

本文生成的測試用例與人工編寫的測試用例覆蓋率及重用精度見表3。

表3 測試用例重用精度結果

由表3可知，3個實驗項目的重用精度均達到84%以上，其中最高的是Apache Commons Math項目，包含2423個正確測試用例，重用精度達到88.0%；最低的項目JFreeChart也生成了1776個正確測試用例，重用精度達到84.0%。這說明本文方法能生成大于等于人工編寫的測試用例覆蓋率的正確測試用例，達到了較高的重用精度。

本文方法與文獻[5]及文獻[12]方法的重用召回率及重用精度見表4。

表4 3種測試用例重用方法的重用效果對比結果/%

由表4可知，本文方案在重用召回率和重用精度上都有更好的表現(xiàn)。在3個數(shù)據(jù)集上，與文獻[5]方法相比，本文的重用召回率提高了4.6%～10.2%，重用精度提高了2.5%～6.2%；與文獻[12]方法相比，本文的重用召回率提高了18.7%～23.1%，重用精度提高了17.3%～28%。實驗結果更佳的原因，一是本文方法考慮了語法、語義等多種代碼相似因素，而文獻[5]和文獻[12]都只考慮了語法相似一種因素；二是本文使用了兩種重用方法，對4種相似類型的測試用例均進行了重用生成，而文獻[5]只能對Type-1、Type-2的測試用例進行重用生成，文獻[12]只能對Type-1的測試用例進行重用生成。綜上所述，與現(xiàn)有測試用例重用方法相比，本文方法具有更好的重用效果。

本文方法與Randoop及Evosuite在相同時間成本下生成的測試用例覆蓋率結果見表5。

表5 3種測試用例生成方法的測試用例覆蓋率對比結果/%

由表5可知，在相同時間成本下，本文方案生成的測試用例覆蓋率更高。與Randoop相比，本文方法的測試用例覆蓋率提高了13.2%～32.1%；與Evosuite相比，本文方法的測試用例覆蓋率提高了3.5%～23.4%。實驗結果更佳的原因是，本文直接使用現(xiàn)有測試用例進行重用，提高了生成效率；而Randoop采用隨機生成技術，短時間內(nèi)只能為少部分被測類生成測試用例，導致生成的測試用例覆蓋率較低；Evosuite采用基于遺傳算法的搜索生成技術，其測試用例生成過程需要較長的搜索時間和一定的迭代次數(shù)，這也致使在相同時間內(nèi)該工具僅能為部分被測類生成測試用例。綜上所述，在相同時間成本下，相比現(xiàn)有測試用例生成方法，本文方法能生成質(zhì)量更好的測試用例，降低了測試時間成本。

4 結束語

為減少測試工作量、節(jié)省測試成本，本文提出了基于代碼相似性的測試用例重用及生成方法。該方法將代碼重用技術應用于測試用例生成，且對代碼相似性檢測方法進行了適應性改進。實驗結果表明，本文方法能有效生成測試用例，降低生成成本，且比現(xiàn)有方法在重用召回率和精度上、生成效率上均有明顯提升。

本文方法的進一步工作是：在相似性檢測階段，本文只使用了兩種檢測技術，未來可探究使用其它技術對本文方法效果的影響；在測試用例重用及生成階段，本文方法生成的測試用例有一部分不能很好地適應包含復雜參數(shù)的被測代碼，未來可改進生成算法以針對這些被測代碼；本文所選實驗數(shù)據(jù)集并不能完全代表工業(yè)中的實際項目，未來可在更多真實的大型工業(yè)項目中進一步驗證本文方法。