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

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

0 概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 以函數(shù)為檢測單元的開源代碼比對分析方法流程

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

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

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

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

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

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ù)代碼從IncreText中剔除

5.解析IncreText中剩余的代碼,獲得修改代碼的起始行號(startL)。檢查startL是否位于Fs函數(shù)中,若是,從該函數(shù)體的起始標(biāo)記符所在行號開始查找,找到函數(shù)體的結(jié)束標(biā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通過調(diào)用版本控制工具中的“l(fā)og”命令獲得,如“SVN log”“Git log”。分析第1個快照時,調(diào)用語法分析器進(jìn)行完整分析,獲得函數(shù)特征信息列表Fs。當(dāng)分析第2個及后續(xù)的快照時,Ft可通過調(diào)用GetFuncList獲得。通過遍歷代碼倉庫中所有的版本快照,并以其作為第2個參數(shù)循環(huán)調(diào)用算法1,即可實(shí)現(xiàn)對整個代碼倉庫的遍歷。

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

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

圖2 增量文本格式

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

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

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

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

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

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

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

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

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

1.FuncFingerPrint CalFuncFingerPrint( Function F){

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

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

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

5.{//Simhash分為5個步驟

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

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

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

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

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

11.}

12.Return Fp

13.}

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

輸入2個工程的源代碼FA、FB

輸出2個工程的代碼相似度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個工程中的函數(shù)轉(zhuǎn)化為函數(shù)指紋

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

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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)驗(yàn)3對實(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 完整分析與增量分析的速度對比

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

表1 完整分析與增量分析對比

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

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

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

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

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

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

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

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

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

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

表4 同類開源項(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ǔ)上,對getTypeHandler等114個函數(shù)做了更新;KJF_ERP在復(fù)用MEGAGAO_ERP的基礎(chǔ)上,對changeStatus等225個函數(shù)做了更新;deleteBatch等7個函數(shù)在2個衍生項(xiàng)目中都做了修改。綜合上述數(shù)據(jù)可以獲得所有的函數(shù)更新位置及其最新的更新時間。

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

4 結(jié)束語

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