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

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

(四川大學(xué) 計(jì)算機(jī)學(xué)院，四川 成都 610065)

0 引 言

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

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

1 相關(guān)工作

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

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

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

2 方法描述

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

圖1 方法流程

2.1 相似性代碼檢測(cè)

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

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

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

2.1.1 基于文本的代碼相似性檢測(cè)

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

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

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

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

(1)

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

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

2.1.2 基于度量的代碼相似性檢測(cè)

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

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

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

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

(2)

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

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

(3)

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

2.2 測(cè)試用例重用及生成

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

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

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

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

輸出：新測(cè)試用例

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

//存儲(chǔ)屬性

procedure GetTCInfo(TC)

//獲取測(cè)試用例AST中的信息

GeneASTparser(TCpath)

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

tcinfo ← fieldlist + typelist + methodlist

GeneTCFromSimAST()

}

Class GeneTC{

procedure GeneTCFromSimAST()

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

if tcinfo.fieldname = tcinfo.typename

then oldtc.fieldname ← simAST.typename

else tcinfo.fieldname = tcinfo.classname

then oldtc.fieldname ←

simAST.classname

newtc ← oldtc //獲得新測(cè)試用例

}

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

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)對(duì)象

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

表1 實(shí)驗(yàn)項(xiàng)目信息

3.2 評(píng)估指標(biāo)

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

(4)

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

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

(5)

3.3 實(shí)驗(yàn)設(shè)計(jì)

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

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

3.4 實(shí)驗(yàn)結(jié)果與分析

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

表2 測(cè)試用例重用召回結(jié)果

由表2可知，3個(gè)實(shí)驗(yàn)項(xiàng)目的重用召回率均超過90%，其中最高的是JFreechart，生成有效測(cè)試用例2114個(gè)，重用召回率達(dá)到94.1%；最低的項(xiàng)目Apache Commons Lang也生成了1138個(gè)有效測(cè)試用例，重用率也達(dá)到了90.1%。

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

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

表3 測(cè)試用例重用精度結(jié)果

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

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

表4 3種測(cè)試用例重用方法的重用效果對(duì)比結(jié)果/%

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

本文方法與Randoop及Evosuite在相同時(shí)間成本下生成的測(cè)試用例覆蓋率結(jié)果見表5。

表5 3種測(cè)試用例生成方法的測(cè)試用例覆蓋率對(duì)比結(jié)果/%

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

4 結(jié)束語

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

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