面向開(kāi)源代碼復(fù)用的程序比對(duì)分析方法

許 福,郝 亮,陳飛翔,李冬梅,崔曉暉

(北京林業(yè)大學(xué) 信息學(xué)院,北京 100083)

0 概述

開(kāi)源軟件復(fù)用有助于縮減開(kāi)發(fā)成本,提高開(kāi)發(fā)效率。目前,80%以上IT企業(yè)的主要產(chǎn)品復(fù)用了開(kāi)源代碼,僅有低于3%的企業(yè)沒(méi)有使用任何開(kāi)源軟件[1]。截至2019年1月,GitHub上的開(kāi)源項(xiàng)目已達(dá)1 800萬(wàn)個(gè)[2],OpenHub索引的代碼已經(jīng)超過(guò)573億行[3],StackOverflow的軟件問(wèn)答數(shù)不低于1 300萬(wàn)條[4]。

盡管開(kāi)源軟件資源非常豐富,但要對(duì)其進(jìn)行有效復(fù)用將存在一定難度,主要原因有兩點(diǎn)。第一為開(kāi)源許可證侵權(quán)風(fēng)險(xiǎn)。開(kāi)源軟件通常附帶了相應(yīng)的許可證限制,常見(jiàn)的許可證有GPL[5]、LGPL[6]、Apache 2.0[7]和BSD-2-Clause[8]等110多種[9]。這些許可證的要求不盡相同,甚至相互沖突。例如,GPL許可證強(qiáng)制衍生品必須公開(kāi)源碼,而Apache 2.0許可證則無(wú)此限制。隨著開(kāi)源代碼復(fù)用的日益廣泛,許可證侵權(quán)風(fēng)險(xiǎn)也愈發(fā)突出。2009年,微軟未經(jīng)許可在其WUDT工具中使用了GPL許可協(xié)議下的開(kāi)源代碼,遭到了開(kāi)源社區(qū)的起訴[10]。2014年,Google的Android系統(tǒng)被訴侵權(quán)Java代碼,訴訟金達(dá)88億美元[11]。為規(guī)避許可證侵權(quán)風(fēng)險(xiǎn),企業(yè)通常不得不耗費(fèi)大量人力和資源來(lái)進(jìn)行手工鑒別。第二為已復(fù)用的代碼難以及時(shí)更新。開(kāi)源代碼復(fù)用后需要及時(shí)更新,否則可能帶來(lái)安全風(fēng)險(xiǎn)。2017年,由于復(fù)用的Apache Struts2 開(kāi)源組件存在漏洞,Equifax公司的1.43 億用戶信息被竊,經(jīng)濟(jì)損失高達(dá)35億美元[12]。在實(shí)踐中,某個(gè)開(kāi)源項(xiàng)目的代碼經(jīng)常會(huì)被其他項(xiàng)目復(fù)用,與原生項(xiàng)目相比,這些衍生項(xiàng)目可能開(kāi)發(fā)更活躍,問(wèn)題修正更及時(shí)。由于欠缺針對(duì)開(kāi)源生態(tài)系統(tǒng)的全局分析方法和工具,目前開(kāi)發(fā)者只能獲取到原生項(xiàng)目中的代碼更新,難以獲取到其衍生更新。此外,由于欠缺自動(dòng)化的比對(duì)工具,開(kāi)發(fā)者只能利用Diff[13]、Araxis Merge[14]等文本比對(duì)工具進(jìn)行手工代碼更新,當(dāng)復(fù)用的代碼來(lái)源很廣時(shí)將消耗大量人力。

以上兩點(diǎn)是影響開(kāi)源代碼復(fù)用的主要障礙,高效的程序比對(duì)分析技術(shù)是解決上述問(wèn)題的有效途徑。程序比對(duì)分析通常利用文本、語(yǔ)法和語(yǔ)義等指標(biāo)計(jì)算代碼相似度,據(jù)此進(jìn)行分析比對(duì)。文獻(xiàn)[15]將代碼相似度分為5個(gè)等級(jí):相似等級(jí)1中2份代碼完全一樣,相似等級(jí)2中除空白(含空格、回車、Tab等)與注釋外,其余部分完全相同,相似等級(jí)3在等級(jí)2的基礎(chǔ)上,2份代碼的變量名、類型名不同,其他部分相同,相似等級(jí)4在等級(jí)3的基礎(chǔ)上,改變、增加或刪除少量語(yǔ)句,其余大部分代碼相同,相似等級(jí)5中2份代碼的絕大部分均不相同。其中,等級(jí)1～等級(jí)3認(rèn)定為相同代碼,等級(jí)4認(rèn)定為高相似度代碼,等級(jí)5認(rèn)定為不同代碼。

本文通過(guò)程序比對(duì)分析技術(shù),以實(shí)現(xiàn)對(duì)海量開(kāi)源代碼的高效分析與檢索以及代碼相似度的有效判別。設(shè)計(jì)一種增量代碼函數(shù)提取算法,其僅對(duì)代碼快照間的增量部分進(jìn)行分析,并充分利用代碼快照間的高度相似性特點(diǎn)來(lái)有效降低代碼分析整體規(guī)模。提出基于Simhash的函數(shù)指紋構(gòu)造算法,將函數(shù)代碼轉(zhuǎn)化為函數(shù)指紋進(jìn)行存儲(chǔ)和檢索,從而降低分析結(jié)果的存儲(chǔ)空間并提高代碼函數(shù)的檢索效率。構(gòu)建一種代碼相似性判定方法,用于檢索函數(shù)更新出現(xiàn)的位置。在此基礎(chǔ)上,通過(guò)計(jì)算相同、相似函數(shù)數(shù)量之和占函數(shù)總數(shù)的百分比來(lái)獲得2個(gè)開(kāi)源工程的相似度,據(jù)此判定2個(gè)開(kāi)源工程間是否存在復(fù)用關(guān)系。

1 國(guó)內(nèi)外研究現(xiàn)狀

目前的程序比對(duì)分析理論大都來(lái)自編譯領(lǐng)域,主要采用LR(k)、LL(k)分析方法及其各種改進(jìn)方法,如SLR(k)、LALR(k)和SLL(k)等[16]。這些理論和方法在編譯領(lǐng)域的應(yīng)用已比較成熟,但不能有效滿足開(kāi)源代碼復(fù)用領(lǐng)域的分析需求,原因主要有以下兩點(diǎn):

1)缺乏高效的增量分析方法。目前的程序分析方法采用批處理模式,對(duì)程序進(jìn)行完整分析。這類方法分析速度慢,難以滿足海量開(kāi)源代碼的高效分析需求。Lucene[17]、SearchCode[18]等代碼搜索引擎將代碼當(dāng)普通文本處理,可檢索海量代碼,但未利用語(yǔ)法結(jié)構(gòu)信息,不能進(jìn)行相似等級(jí)為2和3的代碼比對(duì)。文獻(xiàn)[19]設(shè)計(jì)了一種基于抽象語(yǔ)法樹(shù)的代碼增量分析方法,其分析效率較高,但分析器構(gòu)建難度較大,且分析規(guī)模存在瓶頸。文獻(xiàn)[20]將連續(xù)的源程序映射成哈希值,借助倒排索引技術(shù)[21],設(shè)計(jì)了大規(guī)模代碼的增量分析算法,該算法性能較高,但是其不執(zhí)行語(yǔ)法分析,沒(méi)有充分利用語(yǔ)法結(jié)構(gòu)信息。

2)缺乏高效的代碼比對(duì)分析方法。為避免開(kāi)源許可證侵權(quán),近年來(lái)出現(xiàn)了一些關(guān)于許可證自動(dòng)偵測(cè)方面的研究成果[22-23],其核心思路是通過(guò)掃描特征文件或關(guān)鍵詞來(lái)判定開(kāi)源許可證類型。這類方法能夠自動(dòng)偵測(cè)部分許可證,但存在以下局限:這些特征文件或關(guān)鍵詞在很多開(kāi)源代碼中并未明確標(biāo)注;開(kāi)源項(xiàng)目通常也廣泛復(fù)用了其他的開(kāi)源代碼[24],復(fù)用過(guò)程本身就可能存在許可證沖突。統(tǒng)計(jì)數(shù)據(jù)顯示,高達(dá)85%的開(kāi)源項(xiàng)目都存在不同程度的許可證侵權(quán)問(wèn)題[25]。在這種情況下,即使偵測(cè)到了許可證文件或關(guān)鍵詞,結(jié)果也不準(zhǔn)確。Black Duck[26]和Palamida[27]公司提供開(kāi)源許可證侵權(quán)檢測(cè)服務(wù),但其內(nèi)部機(jī)制和算法并未公開(kāi)。此外,這類商業(yè)檢測(cè)服務(wù)收費(fèi)不菲,很多企業(yè)難以負(fù)擔(dān)。開(kāi)源許可證侵權(quán)檢測(cè)需要跨越項(xiàng)目邊界對(duì)開(kāi)源生態(tài)系統(tǒng)中的程序代碼進(jìn)行整體分析,據(jù)此識(shí)別出復(fù)用的代碼最早來(lái)自哪個(gè)項(xiàng)目,繼而判定其許可證類型,目前還較少有關(guān)于這方面的研究成果。

2 算法設(shè)計(jì)

本文設(shè)計(jì)一種以函數(shù)為檢測(cè)單元的開(kāi)源代碼比對(duì)分析方法。該分析方法將開(kāi)源工程視為代碼文件的集合,將代碼文件視為函數(shù)的集合。首先利用SVN、Git等命令行工具提取倉(cāng)庫(kù)代碼,然后設(shè)計(jì)語(yǔ)法分析器,以函數(shù)為單元對(duì)代碼文件進(jìn)行切分,提取函數(shù)特征信息。為便于數(shù)據(jù)存儲(chǔ)和比對(duì)分析,使用Simhash算法[28]將函數(shù)轉(zhuǎn)化為函數(shù)指紋,利用函數(shù)指紋進(jìn)行代碼比對(duì),確定函數(shù)的相似度關(guān)系。基于上述函數(shù)相似度計(jì)算2個(gè)工程的相似度,進(jìn)而判定兩者是否存在復(fù)用關(guān)系。在復(fù)用關(guān)系確立后,可通過(guò)查驗(yàn)工程中的“LICENSE”“readme”等文件人工判定是否存在開(kāi)源許可證侵權(quán)。在已復(fù)用代碼的更新檢測(cè)方面,利用函數(shù)指紋找到所有初始復(fù)用項(xiàng)目的衍生項(xiàng)目,以及這些項(xiàng)目中的相似函數(shù)指紋,結(jié)合函數(shù)的修改時(shí)間信息即可快速找到可用的函數(shù)更新。本文方法包含以下4個(gè)步驟:

1)獲取倉(cāng)庫(kù)代碼。利用SVN、Git等命令行工具獲取開(kāi)源倉(cāng)庫(kù)代碼,調(diào)用SVN Diff、Git Diff等接口獲取快照(Snapshot)間的差異代碼。為行文簡(jiǎn)潔,后文將上述快照間的差異代碼稱為“增量文本”。

2)進(jìn)行完整和增量語(yǔ)法分析,獲取函數(shù)特征信息列表。以函數(shù)為基本單位對(duì)待分析的代碼進(jìn)行切分,獲得文件中的所有函數(shù)。設(shè)計(jì)語(yǔ)法分析器對(duì)代碼倉(cāng)庫(kù)中的第1個(gè)版本快照?qǐng)?zhí)行完整語(yǔ)法分析,提取函數(shù)名、起止行號(hào)、參數(shù)和返回值等特征信息。本步驟的分析器可采用Bison、Antlr等分析器生成工具構(gòu)建,此處不再贅述。對(duì)于第2個(gè)及后續(xù)的版本快照,提取快照間的增量文本,設(shè)計(jì)增量函數(shù)提取算法(見(jiàn)2.1節(jié)),將增量文本識(shí)別為完整、可進(jìn)行語(yǔ)法分析的函數(shù),提取其中的函數(shù)名、起止行號(hào)等信息。

3)計(jì)算函數(shù)指紋。利用Simhash[28]、特征信息分詞賦權(quán)構(gòu)造與函數(shù)代碼對(duì)應(yīng)的哈希值,下文將該哈希值統(tǒng)稱為函數(shù)指紋(見(jiàn)2.2節(jié))。

4)相似度計(jì)算及比對(duì)分析。基于函數(shù)指紋比對(duì)分別獲得相同、相似、不同的函數(shù)個(gè)數(shù),根據(jù)上述數(shù)據(jù)計(jì)算代碼相似度,判斷代碼間是否存在復(fù)用關(guān)系。結(jié)合修訂時(shí)間信息構(gòu)建函數(shù)的“創(chuàng)建/引用/修改”歷史序列圖,據(jù)此進(jìn)行開(kāi)源代碼許可證侵權(quán)檢測(cè)及函數(shù)的更新偵測(cè)。

本文方法流程如圖1所示。

圖1 以函數(shù)為檢測(cè)單元的開(kāi)源代碼比對(duì)分析方法流程

2.1 增量函數(shù)提取算法

活躍的開(kāi)源項(xiàng)目通常存在大量的版本快照。例如,Hibernate的快照有9萬(wàn)個(gè)[29],Apache Web Server的快照高達(dá)110萬(wàn)個(gè)[30]。開(kāi)源項(xiàng)目普遍采用SVN 、Git等版本控制系統(tǒng),為避免提交時(shí)發(fā)生沖突,通常采用小規(guī)模、頻繁的代碼提交模式,這意味著相鄰快照間的代碼差異非常小,平均相似度高達(dá)98%[31]。傳統(tǒng)方法對(duì)代碼進(jìn)行完整分析,沒(méi)有利用快照間的高度相似性特點(diǎn),因而存在大量的冗余分析,時(shí)空效率較低。本文設(shè)計(jì)一種增量分析方法,只對(duì)快照間的修改部分(即增量文本)進(jìn)行分析,與傳統(tǒng)的完整分析相比,其具有明顯的時(shí)空效率優(yōu)勢(shì)。本文增量函數(shù)提取算法偽代碼如算法1所示。

算法1增量函數(shù)提取算法

輸入已分析的快照Ns,待分析的快照Nt,快照Ns中的函數(shù)特征信息列表Fs

輸出快照Nt中的函數(shù)特征信息列表Ft,每條信息包含函數(shù)名、起止行號(hào)等

1.FuncList GetFuncList ( Snapshot Ns,Snapshot Nt,FuncList Fs) {

2.使用Diff命令獲得Ns、Nt快照間的增量文本(IncreText)

3.掃描IncreText,查找其中是否包含完整函數(shù)

4.根據(jù)增加、刪除兩類編輯操作,計(jì)算新增的函數(shù)列表(Fa)和刪除的函數(shù)列表(Fd),將上述識(shí)別出的函數(shù)代碼從IncreText中剔除

5.解析IncreText中剩余的代碼,獲得修改代碼的起始行號(hào)(startL)。檢查startL是否位于Fs函數(shù)中,若是,從該函數(shù)體的起始標(biāo)記符所在行號(hào)開(kāi)始查找,找到函數(shù)體的結(jié)束標(biāo)記符所在行號(hào),得到修改的函數(shù)列表(Fm)。

6.更新Fs中的Fm,將Fa添加到Fs,將Fd從Fs中刪除

7.Ft= Fs//得到快照Nt中的函數(shù)特征信息列表Ft

8.Return Ft

9.}

在算法1中,輸入?yún)?shù)Ns和Nt通過(guò)調(diào)用版本控制工具中的“l(fā)og”命令獲得,如“SVN log”“Git log”。分析第1個(gè)快照時(shí),調(diào)用語(yǔ)法分析器進(jìn)行完整分析,獲得函數(shù)特征信息列表Fs。當(dāng)分析第2個(gè)及后續(xù)的快照時(shí),Ft可通過(guò)調(diào)用GetFuncList獲得。通過(guò)遍歷代碼倉(cāng)庫(kù)中所有的版本快照,并以其作為第2個(gè)參數(shù)循環(huán)調(diào)用算法1,即可實(shí)現(xiàn)對(duì)整個(gè)代碼倉(cāng)庫(kù)的遍歷。

算法1中的大部分代碼均直觀易懂,但需要解釋以下三點(diǎn):

1)在第2行中,增量文本可通過(guò)調(diào)用版本控制工具中的“Diff”命令獲得。例如,想要獲得版本快照N1與N2間的差異信息,可調(diào)用“SVN Diff-rN1N2”或“Git DiffN1N2”獲得。此外,不同版本控制工具的增量文本格式略有不同,以最常見(jiàn)的Unified Diff Format[32]為例,所有的修改都可以歸結(jié)為添加和刪除兩類操作,其中,以“+++”開(kāi)頭表示添加行,以“---”開(kāi)頭表示刪除行。通過(guò)解析增量文本可以定位出增加、刪除的行號(hào)位置及代碼塊,如圖 2所示。

圖2 增量文本格式

2)在第3行中,查找是否包含完整函數(shù)的思路如下:利用正則表達(dá)式抽取函數(shù)聲明并記錄下函數(shù)體起始符的位置,利用下推自動(dòng)機(jī)[33]匹配與起始符對(duì)應(yīng)的結(jié)束符,這樣即可找到函數(shù)的起止范圍。以Java語(yǔ)言為例,函數(shù)起始符為函數(shù)聲明后的第1個(gè)“{”,函數(shù)結(jié)束符為與之配對(duì)的“}”。圖 3給出了分析器識(shí)別完整函數(shù)體的語(yǔ)法匹配規(guī)則,根據(jù)該規(guī)則可以提取出函數(shù)名、起止行號(hào)等特征信息。

圖3 函數(shù)匹配規(guī)則

3)在第5行中,根據(jù)startL查找函數(shù)體的結(jié)束標(biāo)記符所在行號(hào),可以采用與第2步中類似的下推自動(dòng)機(jī)實(shí)現(xiàn)。

通過(guò)算法1可將增量文本轉(zhuǎn)換成完整的可進(jìn)行詞法、語(yǔ)法分析的函數(shù)。

2.2 函數(shù)指紋構(gòu)造與工程相似度計(jì)算

算法1提取出了每個(gè)快照中的函數(shù)特征信息,為了支持相似等級(jí)為2和3的代碼比對(duì),需要對(duì)每個(gè)函數(shù)進(jìn)行詞法分析,將函數(shù)轉(zhuǎn)為標(biāo)志符(Token)序列。為減小存儲(chǔ)空間,方便函數(shù)比對(duì),本文利用哈希算法將上述Token序列轉(zhuǎn)為函數(shù)指紋。在哈希算法選擇方面,需滿足3個(gè)直觀條件:1)相同的Token序列應(yīng)產(chǎn)生相同的哈希值,不同的序列應(yīng)產(chǎn)生不同的哈希值;2)具有較低的哈希碰撞率;3)相似的Token序列應(yīng)產(chǎn)生相似的哈希值,以滿足相似函數(shù)的判定需求。MD5、SHA256等傳統(tǒng)哈希算法滿足第1個(gè)和第2個(gè)條件,但不滿足第3個(gè)條件,即使原始內(nèi)容高度相似,生成的哈希值也可能差異很大。本文采用Simhash作為函數(shù)指紋構(gòu)造算法,該算法是一種低碰撞率的局部敏感哈希算法[34],以往主要用于相似網(wǎng)頁(yè)濾重。Simhash具備高容量的特征壓縮,且哈希值能反映原始輸入的相似性,當(dāng)2個(gè)哈希值的海明距離小于等于3時(shí)表明2段代碼相似。算法2給出了函數(shù)指紋構(gòu)造算法的偽代碼,算法3給出了以函數(shù)為基本分析單元的工程相似度計(jì)算算法的偽代碼。

算法2函數(shù)指紋構(gòu)造算法

輸入單一函數(shù)的函數(shù)體代碼F

輸出函數(shù)F對(duì)應(yīng)的函數(shù)指紋Fp

1.FuncFingerPrint CalFuncFingerPrint( Function F){

2.調(diào)用詞法分析器,將代碼轉(zhuǎn)為Token序列

3.調(diào)用語(yǔ)法分析器獲取函數(shù)特征信息

4.利用Simhash算法,結(jié)合函數(shù)特征信息計(jì)算函數(shù)指紋Fp

5.{//Simhash分為5個(gè)步驟

6.分詞//對(duì)內(nèi)容分詞,得到特征向量

7.哈希//將每個(gè)特征向量哈希為一組固定長(zhǎng)度的數(shù)列

8.賦權(quán)//對(duì)每個(gè)哈希值進(jìn)行加權(quán)

9.合并//將上述加權(quán)哈希值合并

10.降維//將合并后的值降維,得到最終的哈希值

11.}

12.Return Fp

13.}

算法3以函數(shù)為基本分析單元的工程相似度計(jì)算算法

輸入2個(gè)工程的源代碼FA、FB

輸出2個(gè)工程的代碼相似度S

1.Similarity CalSimilarity(FA,FB){

2.sameFuncCount=0;//相同函數(shù)數(shù)目

3.similarFuncCount=0;//相似函數(shù)數(shù)目

4.differentFuncCount=0;//不同函數(shù)數(shù)目

5.調(diào)用算法2將2個(gè)工程中的函數(shù)轉(zhuǎn)化為函數(shù)指紋

6.獲取2個(gè)工程的函數(shù)指紋列表,分別標(biāo)記為FpA、FpB

7.統(tǒng)計(jì)函數(shù)指紋數(shù),分別記為sumFuncCntA、sumFuncCntB

8.遍歷FpA中的每個(gè)函數(shù)指紋fa{

9.遍歷FpB中的每個(gè)函數(shù)指紋fb{

10.distance = fa和fb的海明距離

11.If (distance == 0)// 相同函數(shù)

12.sameFuncCount ++

13.Else If (0

14.similarFuncCount++

15.Else{//不同函數(shù)

16.differentFuncCount++

17.}

18.}

19.}

20.S=(sameFuncCount+similarFuncCount)/sumFuncCntA|B

21.Return S//返回相似度

22.}

算法2的輸入為單一函數(shù)的函數(shù)代碼F,輸出是與函數(shù)F對(duì)應(yīng)的指紋信息Fp,其對(duì)Simhash算法進(jìn)行了改進(jìn),首先對(duì)輸入的函數(shù)代碼進(jìn)行詞法分析,將代碼塊轉(zhuǎn)化為Token序列(第2行),然后調(diào)用語(yǔ)法分析器獲取函數(shù)特征信息(第3行),最后利用Simhash算法結(jié)合函數(shù)特征信息計(jì)算得到函數(shù)指紋(第4行～第11行)。Simhash算法在網(wǎng)頁(yè)去重中得到廣泛應(yīng)用[35],為使該算法能夠適用于程序分析的應(yīng)用場(chǎng)景,本文在原始Simhash算法的基礎(chǔ)上做了兩點(diǎn)改進(jìn),如圖4中加粗部分所示。

圖4 原始Simhash算法優(yōu)化

本文對(duì)Simhash算法的兩點(diǎn)改進(jìn)具體如下:

1)詞法分析:經(jīng)過(guò)詞法分析將源代碼轉(zhuǎn)為Token序列,濾去了代碼相似等級(jí)為2、3時(shí)無(wú)關(guān)項(xiàng)對(duì)分析結(jié)果的影響。

2)賦權(quán):賦權(quán)是Simhash算法中的重要環(huán)節(jié)。在原始Simhash算法用于網(wǎng)頁(yè)去重時(shí),每個(gè)分詞所賦的權(quán)值為該分詞在文本中出現(xiàn)的頻次。與網(wǎng)頁(yè)不同,源代碼均按編程語(yǔ)言語(yǔ)法編寫(xiě),具備嚴(yán)格的結(jié)構(gòu)化特征,函數(shù)名、參數(shù)、返回值能較好地體現(xiàn)上述結(jié)構(gòu)化特征,因此,本文對(duì)該類分詞加倍賦權(quán),其他分詞權(quán)值采用原始Simhash中的標(biāo)準(zhǔn)賦值策略。

算法3實(shí)現(xiàn)了函數(shù)相似度判定和工程相似度計(jì)算。首先,根據(jù)算法2獲取2個(gè)工程的函數(shù)指紋,并統(tǒng)計(jì)函數(shù)數(shù)目(第5行～第7行)。以海明距離3為閾值,對(duì)函數(shù)指紋進(jìn)行分類,找出相同、相似、不同的函數(shù)指紋,并統(tǒng)計(jì)三類函數(shù)的數(shù)目(第8行～第19行)。最后,以相同、相似函數(shù)數(shù)量之和占函數(shù)總數(shù)的百分比作為工程相似度(第20行)。需要注意的是,FA、FB包含的函數(shù)總數(shù)可能不同,因此,一次比對(duì)會(huì)獲得2個(gè)相似度。

通過(guò)算法1～算法3,可獲得函數(shù)指紋并進(jìn)行函數(shù)指紋比對(duì),進(jìn)而實(shí)現(xiàn)高效的代碼溯源。通過(guò)檢索函數(shù)指紋,可以確定每個(gè)函數(shù)及其相似函數(shù)在整個(gè)開(kāi)源生態(tài)系統(tǒng)中的項(xiàng)目、路徑和版本信息,據(jù)此進(jìn)行許可證侵權(quán)檢測(cè)和代碼同步更新。

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

本文設(shè)計(jì)了如下3組實(shí)驗(yàn),從分析時(shí)間和工程相似度2個(gè)角度進(jìn)行程序比對(duì)分析:

實(shí)驗(yàn)1通過(guò)對(duì)比傳統(tǒng)完整分析與增量分析所消耗的時(shí)間,驗(yàn)證增量分析方法具備更快的分析速度和更小的內(nèi)存空間。

實(shí)驗(yàn)2利用算法3對(duì)代碼相似度進(jìn)行判定,驗(yàn)證本文方法的正確性。

實(shí)驗(yàn)3對(duì)實(shí)驗(yàn)2進(jìn)行擴(kuò)展,驗(yàn)證函數(shù)溯源能力。

實(shí)驗(yàn)機(jī)配置:Windows 10 64 bit,內(nèi)存16 GB,CPU 6核Intel(R) Core(TM) i7-8700k。

3.1 完整分析與增量分析的速度對(duì)比

本文實(shí)驗(yàn)選取GitHub上的Hibernate開(kāi)源項(xiàng)目作為分析對(duì)象。截至2019年1月9日,該項(xiàng)目累計(jì)儲(chǔ)存了97 044個(gè)版本快照,其中,master分支上儲(chǔ)存了9 430個(gè)快照。選取master分支中最近提交的11個(gè)快照進(jìn)行分析,表1所示為增量分析與完整分析所消耗的時(shí)間(第1個(gè)版本快照只有完整分析時(shí)間、文件數(shù)和函數(shù)數(shù)目)。

表1 完整分析與增量分析對(duì)比

從實(shí)驗(yàn)數(shù)據(jù)可看出,相鄰版本快照間的代碼改動(dòng)量很小,平均改動(dòng)量約占總函數(shù)量的0.11%(增量函數(shù)數(shù)量/函數(shù)總量)。在時(shí)間對(duì)比上,增量分析相較于完整分析有明顯優(yōu)勢(shì),平均節(jié)約了94.85%的分析時(shí)間。此外,傳統(tǒng)分析方法需要加載工程內(nèi)的所有代碼文件,而增量分析只處理增量文本,因而只需要加載少部分文件,在內(nèi)存使用上也更加經(jīng)濟(jì)。從上述實(shí)驗(yàn)結(jié)果可看出,進(jìn)行一次完整分析平均需加載9 227個(gè)Java文件,而使用增量分析平均只需加載約11個(gè)Java文件,約占完整分析的0.12%。綜上,無(wú)論在分析效率還是在內(nèi)存使用上,增量分析方法都優(yōu)于傳統(tǒng)的完整分析方法。

3.2 工程相似度計(jì)算

本實(shí)驗(yàn)數(shù)據(jù)源采用GitHub上2個(gè)可能存在衍生關(guān)系的開(kāi)源ERP系統(tǒng),即RAINFLY_ERP和MEGAGAO_ERP。通過(guò)人工查驗(yàn),兩者都使用了Spring+Struct2+MyBatis架構(gòu)。分析結(jié)果包括兩部分,第一對(duì)工程代碼進(jìn)行分析,從表2可以看出,2個(gè)工程的代碼量類似,分別包含3 825個(gè)和4 092個(gè)函數(shù);第二對(duì)2個(gè)工程的函數(shù)指紋進(jìn)行對(duì)比分析,并計(jì)算2個(gè)工程的相似度。表3列出了相同函數(shù)、相似函數(shù)、不同函數(shù)的數(shù)量關(guān)系。

表2 2個(gè)項(xiàng)目的基本情況

表3 開(kāi)源項(xiàng)目函數(shù)比對(duì)結(jié)果

從上述實(shí)驗(yàn)結(jié)果可看出,2個(gè)工程的相似度非常高。雖然MEGAGAO_ERP與RAINFLY_ERP在界面上風(fēng)格迥異,但在函數(shù)層面它們都實(shí)現(xiàn)了相同的功能。比對(duì)2個(gè)工程中的函數(shù)指紋,相同函數(shù)為3 310對(duì),相似函數(shù)為114對(duì),不同函數(shù)分別有401個(gè)和668個(gè)。利用算法3計(jì)算可知,2個(gè)工程的相似度分別為83.7%和89.5%。

通過(guò)實(shí)驗(yàn)2可獲得2個(gè)工程在函數(shù)層面上的相似度,以此判定兩者是否存在復(fù)用關(guān)系。綜合代碼快照的提交時(shí)間可以獲知復(fù)用方和被復(fù)用方。例如,實(shí)驗(yàn)中MEGAGAO_ERP的提交時(shí)間段是2016年9月24日—2018年1月23日,而RAINFLY_ERP的提交時(shí)間段在2018年2月1日—2018年2月5日,據(jù)此可認(rèn)定RAINFLY_ERP是MEGAGAO_ERP的衍生項(xiàng)目,復(fù)用比例為89.5%。

實(shí)驗(yàn)2采用的分析方法可以從2個(gè)項(xiàng)目擴(kuò)展到整個(gè)開(kāi)源倉(cāng)庫(kù)。首先分析倉(cāng)庫(kù)代碼,把函數(shù)轉(zhuǎn)化成函數(shù)指紋并預(yù)先存儲(chǔ)好,之后通過(guò)函數(shù)指紋可以檢索出相同函數(shù)和相似函數(shù),結(jié)合文件的更新時(shí)間信息即可構(gòu)建出函數(shù)的“創(chuàng)建/復(fù)用/更新”時(shí)間鏈,借助該時(shí)間鏈可有效解決開(kāi)源許可證侵權(quán)檢測(cè)問(wèn)題。

3.3 復(fù)用代碼更新能力驗(yàn)證

本文實(shí)驗(yàn)數(shù)據(jù)通過(guò)關(guān)鍵詞檢索,得到GitHub上一組使用同一框架開(kāi)發(fā)的ERP系統(tǒng)。由于這些項(xiàng)目的開(kāi)發(fā)語(yǔ)言相同,實(shí)現(xiàn)的功能類似,因而猜測(cè)它們之間存在復(fù)用關(guān)系。分析上述工程的源代碼得到的實(shí)驗(yàn)數(shù)據(jù)見(jiàn)表4。

表4 同類開(kāi)源項(xiàng)目的分析結(jié)果

利用實(shí)驗(yàn)2中復(fù)用關(guān)系的判定方法發(fā)現(xiàn):在上述工程中,RAINFLY_ERP和KJF_ERP 都是MEGAGAO_ERP的衍生項(xiàng)目,復(fù)用比例分別為89.5%和80.2%。RAINFLY_ERP在復(fù)用MEGAGAO_ERP的基礎(chǔ)上,對(duì)getTypeHandler等114個(gè)函數(shù)做了更新;KJF_ERP在復(fù)用MEGAGAO_ERP的基礎(chǔ)上,對(duì)changeStatus等225個(gè)函數(shù)做了更新;deleteBatch等7個(gè)函數(shù)在2個(gè)衍生項(xiàng)目中都做了修改。綜合上述數(shù)據(jù)可以獲得所有的函數(shù)更新位置及其最新的更新時(shí)間。

以往開(kāi)發(fā)者只能通過(guò)原生項(xiàng)目獲得代碼更新。利用實(shí)驗(yàn)3中的方法,開(kāi)發(fā)者很容易找到維護(hù)更為活躍的衍生更新。例如,想要復(fù)用deleteBatch函數(shù),首先將該函數(shù)轉(zhuǎn)為函數(shù)指紋,之后通過(guò)檢索該指紋找到函數(shù)的初始版本及其所有更新。在代碼復(fù)用時(shí),上述方法不僅能很快定位到函數(shù)的最早來(lái)源,還可以更快地找到可用的代碼更新。

4 結(jié)束語(yǔ)

本文提出一種開(kāi)源代碼倉(cāng)庫(kù)增量分析方法,該方法充分利用代碼快照間的高度相似度特點(diǎn),有效縮減了分析時(shí)間和存儲(chǔ)規(guī)模。在此基礎(chǔ)上,利用Simhash算法將增量文本映射成函數(shù)指紋,并設(shè)計(jì)一種以函數(shù)指紋為基本單元的代碼相似度比對(duì)方法,該方法可滿足開(kāi)源代碼復(fù)用中常見(jiàn)的許可證侵權(quán)檢測(cè)及函數(shù)更新需求。利用本文方法可對(duì)開(kāi)源生態(tài)系統(tǒng)中的代碼進(jìn)行整體分析,通過(guò)構(gòu)建代碼索引庫(kù),建立針對(duì)開(kāi)源代碼復(fù)用的公共服務(wù)平臺(tái),可實(shí)現(xiàn)開(kāi)源資源的有效復(fù)用和管理,使開(kāi)發(fā)人員可以獲取可用、高質(zhì)量的代碼,并有效規(guī)避知識(shí)產(chǎn)權(quán)風(fēng)險(xiǎn),促進(jìn)我國(guó)軟件產(chǎn)業(yè)發(fā)展。下一步將結(jié)合大數(shù)據(jù)分析方法,研究如何改進(jìn)代碼的檢索效率,以提升本文方法的代碼溯源能力。