李 鎖 吳毅堅(jiān) 趙文耘

(復(fù)旦大學(xué)軟件學(xué)院 上海 201203) (上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室 上海 201203)

0 引 言

隨著互聯(lián)網(wǎng)的迅速發(fā)展以及開源代碼生態(tài)系統(tǒng)的日益繁榮，網(wǎng)絡(luò)上各種開源項(xiàng)目越來越多樣化并且獲取也更加便利。許多軟件企業(yè)內(nèi)部也通過軟件資源庫、外部開源軟件、軟件產(chǎn)品線及開發(fā)框架等方式建立了多種多樣的軟件復(fù)用開發(fā)方法，同時(shí)開發(fā)人員自身也會通過多種方式大量復(fù)用已有的軟件資源。在這些軟件復(fù)用方法和資源的支持下，軟件系統(tǒng)和軟件產(chǎn)品大量引入了開源軟件、網(wǎng)絡(luò)資源、商業(yè)軟件等外部代碼成分。近年來，如何自動化查找分析軟件系統(tǒng)中的外部來源代碼，已成為當(dāng)前非常重要的研究方向。

代碼成分隨著軟件項(xiàng)目之間的派生以及項(xiàng)目自身的持續(xù)演化而不斷發(fā)展變化，并與自有代碼成分不斷融合。由此造成的問題是，大量關(guān)鍵性軟件系統(tǒng)和產(chǎn)品中的代碼來源成分復(fù)雜，其中許多源自外部的代碼成分都存在安全漏洞、潛在缺陷或知識產(chǎn)權(quán)問題[1]。有些外部依賴還會導(dǎo)致軟件研制和開發(fā)方無法完全掌握軟件的持續(xù)演進(jìn)方向[2]。外部引入的代碼也使項(xiàng)目代碼過于冗余，增加了系統(tǒng)的復(fù)雜度和軟件維護(hù)成本，降低了代碼的可理解性[3]。

本文提出一種基于代碼克隆檢測的代碼來源分析方法，將待分析代碼以方法為單位建模為Hash詞袋，之后利用并行化Hash詞袋模型算法找出目標(biāo)系統(tǒng)代碼在代碼庫中不同項(xiàng)目間的來源關(guān)系，最后生成代碼來源報(bào)告。其目標(biāo)在于，為軟件從業(yè)者和普通用戶提供一種代碼來源分析方法。而用戶所輸入的代碼數(shù)據(jù)可能是多種多樣的，存在著多種不同的情況。因此，代碼來源分析工具需要具備處理不同情況下用戶所輸入的代碼，并對不同情況的代碼提供統(tǒng)一的處理流程，同時(shí)提供統(tǒng)一的交互式圖形化操作工具，使得用戶無需關(guān)心工具的數(shù)據(jù)處理方式和流程，只需要進(jìn)行目標(biāo)系統(tǒng)代碼的輸入，執(zhí)行簡單的操作步驟便能夠得到直觀的結(jié)果。

1 相關(guān)工作

代碼來源分析是指，針對特定目標(biāo)軟件系統(tǒng)，分析該系統(tǒng)中各部分組件與其他項(xiàng)目之間的關(guān)系，其目的是找出該系統(tǒng)中組件的可能外部來源，這些系統(tǒng)組件包括源代碼文件、依賴庫、類、方法、代碼塊等。代碼來源分析旨在回答以下問題[4]：目標(biāo)系統(tǒng)中某一特定組成部分可能來源于何處？

當(dāng)前的代碼來源分析主要基于代碼克隆的研究。例如，Steidl等[5]針對開源系統(tǒng)中高達(dá)38.9%的文件具有不完整的歷史，提出了一種基于提交(commit)的增量方法，以基于克隆信息和名稱相似性重建代碼歷史。代碼克隆，即相同或相似的代碼片段[6]，是軟件開發(fā)中的常見現(xiàn)象。開發(fā)人員經(jīng)常利用代碼克隆簡化程序的編寫，在提升程序開發(fā)速度的同時(shí)也帶來了一些維護(hù)隱患。多年來，已經(jīng)有大量研究專注于如何高效檢測程序中的不同種類的代碼克隆，從而對克隆代碼有了更加清晰的認(rèn)識。目前對克隆代碼最普遍的分類是Bellon等[7]提出的，他們把克隆分為了以下四類：第一類是完全相同的代碼片段；第二類是只有變量名、類型或其他名稱、類型、格式等不同的代碼片段；第三類是在第二類的基礎(chǔ)上，增加、刪除或修改過少量語句的代碼片段；第四類是邏輯功能完全相同而實(shí)現(xiàn)方式不同的代碼片段。

軟件代碼克隆檢測在軟件維護(hù)、軟件結(jié)構(gòu)優(yōu)化等方面具有重要價(jià)值和意義。代碼克隆有多種檢測的方法，基于的不同的對象、不同的語言都有不同檢測的方法?？寺〈a檢測使用的技術(shù)主要包括：文本檢測法(text-based)[8]、符號檢測法(token-based)[9]、抽象語法樹檢測法(AST-based)[10]、程序依賴圖檢測法(PDG-based)[11]、度量檢測法(metric-based)[12]和深度學(xué)習(xí)檢測法(Deep Learning-Based)[13]。

基于代碼來源分析結(jié)果， 研究人員又提出了許多應(yīng)用，其中主要包括軟件譜系和演化分析。例如，張久杰等[14]基于軟件多版本演化，根據(jù)克隆代碼主題信息構(gòu)建版本間克隆代碼的映射關(guān)系，為演化過程中的克隆代碼添加演化模式，分析演化特征并構(gòu)建克隆譜系。Nguyen等[15]針對軟件復(fù)用庫中構(gòu)件演化帶來的客戶代碼同步演化問題，提出了一種基于圖的API使用代碼適應(yīng)性演化方法。另外一些研究工作進(jìn)一步提出了對演化中的克隆代碼進(jìn)行科學(xué)、有效的管理[16]，以及缺陷檢測等[17]。

從現(xiàn)有技術(shù)基礎(chǔ)來看，相關(guān)的研究工作主要集中在克隆檢測和克隆代碼的管理上，即使開展了對軟件代碼來源和演化歷史的研究分析工作，其應(yīng)用目標(biāo)也主要是對項(xiàng)目內(nèi)不同版本之間代碼的演化軌跡進(jìn)行描述。然而，如何全面、充分地對海量軟件代碼資源和其他相關(guān)資源，如代碼項(xiàng)目信息、版本信息等，全方位地建立目標(biāo)系統(tǒng)的代碼來源關(guān)系，是本文關(guān)注的核心問題。

2 代碼來源分析方法

代碼來源分析對于軟件開發(fā)人員和軟件維護(hù)人員具有重要意義。軟件產(chǎn)品上線與更新的速度加快，以及互聯(lián)網(wǎng)的網(wǎng)絡(luò)資源的高速發(fā)展，為軟件開發(fā)與維護(hù)人員提供了大量可利用資源。因此，現(xiàn)在軟件開發(fā)人員在開發(fā)軟件系統(tǒng)時(shí)往往會參考一些開源項(xiàng)目的代碼，而分析這些代碼的來源對理解和維護(hù)軟件系統(tǒng)的代碼具有重要意義。

在本項(xiàng)目中代碼來源是指給定代碼塊，基于代碼克隆檢測，找出該代碼塊在代碼資源庫中的可能來源。當(dāng)有多個(gè)克隆代碼實(shí)例時(shí)，代碼來源根據(jù)項(xiàng)目和時(shí)間進(jìn)行串接，會形成“來源鏈”。來源鏈?zhǔn)侵父鶕?jù)一定來源相似性閾值，代碼庫中與該代碼塊具有克隆關(guān)系的代碼實(shí)例。因?yàn)榉治龀鰜淼拇a來源有不同的置信度(來自克隆代碼的相似度)，因此來源報(bào)告中會給出多個(gè)可能的來源。

代碼來源分析過程如圖1所示，主要分為：(1) 解析源代碼文件，創(chuàng)建代碼塊詞袋；(2) 詞袋Hash化；(3) 創(chuàng)建代碼塊索引Hash表；(4)并行化克隆檢測，得到目標(biāo)系統(tǒng)代碼來源對；(5)生成目標(biāo)系統(tǒng)代碼來源鏈，得到來源報(bào)告。

圖1 代碼來源分析過程

2.1 代碼塊的詞袋化方法

任意一個(gè)軟件項(xiàng)目P，可表示為一系列的代碼塊：{B1，B2，…，Bn}。代碼塊是任意一段具有特定起止邊界的代碼，有不同的粒度。常見的粒度包括文件、類、方法以及語言相關(guān)的多種亞方法粒度。一個(gè)代碼塊B由有限多個(gè)詞構(gòu)成。根據(jù)自然語言處理的機(jī)制，這樣的一個(gè)代碼塊相當(dāng)于一個(gè)文本片段，可進(jìn)一步表示成詞袋(bag-of-words)。詞袋模型最早出現(xiàn)在自然語言處理(Natural Language Processing，NLP)和信息檢索(Information Retrieval，IR)領(lǐng)域。該模型忽略文本的語法和語序等要素，將其僅僅看作是若干個(gè)詞匯的集合，文檔中每個(gè)單詞的出現(xiàn)都是獨(dú)立的。詞袋模型使用一組無序的單詞(words)來表達(dá)一段文字或一個(gè)文檔。同時(shí)，由于代碼的特殊性，可將代碼中的關(guān)鍵詞、標(biāo)識符、運(yùn)算符等符號以詞為單位進(jìn)行以對代碼進(jìn)行Token化(Tokenization)，表示為一串Token。因此，經(jīng)過Token化后的代碼塊即表示為一個(gè)Token袋(bag-of-tokens)：B{T1，T2，…，Tk}，其中Ti是代碼塊B中的Token。由于Token可能出現(xiàn)重復(fù)，因此將Token與它在該代碼塊中的出現(xiàn)次數(shù)Frequency記作一個(gè)二元組(Token，F(xiàn)requency)，作為代碼塊的Token袋組成元素。這種(Token，F(xiàn)requency)表示法大大縮減了代碼塊的表示長度，也有助于提高檢測相似代碼片段的效率。

為了定量推斷兩個(gè)代碼塊是否是克隆，使用相似性函數(shù)來度量代碼塊之間的相似度，并返回一個(gè)非負(fù)值。該值越高，表示代碼塊之間的相似性越大。最終，具有高于指定閾值的相似度值的代碼塊被識別為克隆。

給定兩個(gè)項(xiàng)目Px和Py，相似性函數(shù)f和一個(gè)閾值θ，目標(biāo)是找到所有的代碼克隆對(或者克隆組)Px.B和Py.B，使:

f(Px.B,Py.B)≥「θ·max(|Px.B|,|Py.B|)?

(1)

盡管相似性函數(shù)有很多選擇，為了簡單方便，計(jì)算使用重疊(Overlap)相似性函數(shù)，因?yàn)樗庇^地捕獲了代碼塊之間重疊的概念。重疊相似性函數(shù)計(jì)算兩個(gè)代碼塊共有的Token數(shù)，包含計(jì)算每個(gè)Token的頻數(shù)。例如給定兩個(gè)代碼塊Bx和By，重疊相似性函數(shù)OS(Bx,By)計(jì)算代碼塊Bx和By中重復(fù)Token的數(shù)量，即：

OS(Bx,By)=|Bx∩By|

(2)

具體地，如果指定等于0.8，并且max(|Px.B|,|Py.B|)為t，當(dāng)Bx和By共有至少「θ·|t|?個(gè)Token重復(fù)時(shí)認(rèn)為Bx和By是克隆對。注意，如果Token a在Bx中出現(xiàn)兩次并在By三次出現(xiàn)，則由于Token a而導(dǎo)致的Bx和By之間的匹配為2。

本項(xiàng)目使用詞法分析程序(例如TXL[18])對源代碼文件進(jìn)行掃描遍歷，構(gòu)建代碼塊詞袋。通過詞法分析程序給定語言的標(biāo)記和塊語義，識別并提取出源代碼文件中的代碼塊，并為每個(gè)代碼塊分配一個(gè)整數(shù)標(biāo)識，從而在后續(xù)處理中能夠唯一標(biāo)識每個(gè)代碼塊。

2.2 基于Hash詞袋模型的克隆檢測算法

2.2.1創(chuàng)建Hash詞袋

本節(jié)將創(chuàng)建Hash詞袋，也就是統(tǒng)計(jì)解析后的代碼塊(如方法)中每個(gè)詞出現(xiàn)的頻率，組成，以Token為鍵，F(xiàn)requency為值創(chuàng)建該代碼塊的Hash詞袋。

在傳統(tǒng)的克隆檢測算法中，所有Token都會被一一比較。但是，基于詞袋模型的克隆檢測算法將相同的Token只創(chuàng)建一個(gè)分別對應(yīng)于 。這樣詞袋模型中的Token只需比較一次，如果該Token在該代碼塊中出現(xiàn)多次，也只創(chuàng)建該Token的一個(gè)索引，并將該Token出現(xiàn)的頻率索引到該代碼塊Token的Hash表中，即將Token與該Token出現(xiàn)的頻率索引到一個(gè)Hash表中。這不僅節(jié)省了空間，而且大大減少了索引數(shù)量，因此可以更快地進(jìn)行后續(xù)匹配檢索。目前已經(jīng)能夠?qū)ava、C/C++、Python等語言進(jìn)行源代碼解析，創(chuàng)建Hash詞袋。

2.2.2創(chuàng)建代碼塊索引Hash表

上一小節(jié)將代碼塊中Token和頻率索引到Hash表中，接下來將以代碼塊為單位，將代碼塊索引到代碼塊Hash表中。源代碼解析文件中包含多個(gè)代碼塊特征序列，不同的特征序列有不同或相同的Token數(shù)量，在此，將相同Token總量的序列索引到同一Hash表中。這樣，在后面克隆檢測的時(shí)候，可以利用性質(zhì)1過濾掉許多無關(guān)代碼塊，大大減少候選集。

性質(zhì)1：給定兩個(gè)代碼塊Bx和By分別包含Nx和Ny個(gè)Token，對于給定相似度閾值為sim(0

Nx·sim≤Ny≤Nx/sim

(3)

創(chuàng)建代碼塊索引Hash表算法如算法1所示。該算法輸入是解析后的源代碼文件路徑，也就是Hash詞袋路徑，輸出是代碼塊索引Hash表。算法根據(jù)路徑讀取源代碼解析文件并初始化數(shù)據(jù)(2-3行)，然后逐行讀取文件中的代碼塊詞袋序列，將代碼塊Token總量相同的詞袋序列索引到同一Hash單元中(4-7行)。如果Hash表中已經(jīng)存在該總量的詞袋序列，則直接將詞袋序列附件到該單元中，否則新建以該詞袋序列為key的Hash單元，并將該詞袋序列添加到該單元中(8-16行)。

算法1創(chuàng)建代碼塊索引Hash表算法

1: function GetHashTable(parseFilePath){

2: file = parseFilePath

3: while((line = file.readLine()) != null){

4: blockID = getBlockID(line)

5: blockSize = getBlockSize(line)

6: tokenMap = getTokenMap(line)

7: node = Node(blockID, tokenMap)

8: if(sizeMap.containsKey(blockSize)){

9: blockList = sizeMap.get(blockSize)

10: blockList.add(node)

11: }else{

12: blockList = newLinkedList

13: blockList.add(node)

14: sizeMap.put(blockSize,blockList)

15: }

16: }

17: return sizeMap

18: }

2.2.3并行化代碼來源關(guān)系檢測

并行化來源關(guān)系檢測算法根據(jù)性質(zhì)1，計(jì)算出目標(biāo)代碼塊的Token總量的上限和下限，即upSize和lowSize，將上限和下限之外的其他代碼庫中的代碼塊直接排除，大大減少候選代碼塊的數(shù)量。算法偽代碼如算法2所示。

算法2并行化代碼來源檢測算法

1: function ConcurrentDetection(sim, lines, sizeMap)

2: doubleCore 2*Runtime.availableProcessors()

3: exec = Executors.newFixedThreadPool(doubleCore)

4: for(int i=0; i

5: increment = lines.length / doubleCore + 1

6: start = increment ? i

7: end = increment ? (i + 1)

8: if(lines.length < end){

9: end = lines.length

10: }

11: subPairs = Calculator(lines; start; end; sim; sizeMap)

13: tasks.add(subPairs)

14: if(!exec.isShutdown()){

15: exec.submit(task)

16: }

17: }

18: return getResult()

19: }

20:

21: function Calculator(lines, start, end, sim, sizeMap){

22: for(int iline=0; iline

23: for(int i=lowSize; i

24: cList = sizeMap.get(i)

25: if(cList != null){

26: for(cNode in cList){

27: cID = cNode.blockID

28: cMap = cNode.map

29: for(wBag in mBag){

30: mWord = getWord(wBag)

31: mFreq = getFrequency(wBag)

32: if(cMap.containsKey(mWord)){

33: canFreq = getFrequency(mWord)

34: wordC = min(mFreq, canFreq)

35: }

36: }

37: if(wordC / mSize >= sim){

38: subPairs = subPairs + mID + cID

39: }

40: }

41: }

42: }

43: }

44: }

該算法輸入是來源相似性閾值、目標(biāo)項(xiàng)目詞袋路徑、代碼庫索引Hash表，輸出是目標(biāo)項(xiàng)目代碼來源關(guān)系對。算法首先根據(jù)主機(jī)CPU核心數(shù)創(chuàng)建相應(yīng)數(shù)量的線程，接著根據(jù)不同線程拆分任務(wù)，使來源關(guān)系檢測并行化運(yùn)行(1-19行)。Calculator函數(shù)根據(jù)線程參數(shù)，執(zhí)行具體的克隆檢測(21-44行)。首先獲取待檢測代碼塊詞袋(參數(shù)lines)，并逐行讀取詞袋并進(jìn)行克隆檢測(22-44行)；然后計(jì)算出目標(biāo)代碼塊的Token數(shù)量的上限和下限(22-23行)，從下限Token數(shù)量開始循環(huán)遍歷代碼塊索引Hash表(23-44行)。如果已經(jīng)匹配的Token總數(shù)大于等于相似性閾值，則將目標(biāo)代碼ID與候選代碼ID加入到克隆對中，表示這兩個(gè)代碼塊是克隆代碼，結(jié)束匹配(37-38)。

2.3 構(gòu)建代碼來源鏈

由于我們的系統(tǒng)的輸入對象是多項(xiàng)目多版本的，不管是演化圖譜的提取還是跨項(xiàng)目的檢測對比時(shí)都會面臨時(shí)間線不一致的情況，故采取對項(xiàng)目演化歷史時(shí)間進(jìn)行對齊的方案：對于大量的項(xiàng)目，按照不同項(xiàng)目release的時(shí)間先后版本對齊，接著執(zhí)行基于Hash詞袋模型的克隆檢測算法找到待檢測項(xiàng)目中的代碼塊在代碼庫中不同項(xiàng)目的來源關(guān)系，利用不同項(xiàng)目內(nèi)release版本的時(shí)間先后順序，找到待檢測項(xiàng)目中代碼塊在代碼庫中不同項(xiàng)目的來源關(guān)系，時(shí)間最早的release代碼塊作為目標(biāo)系統(tǒng)代碼的來源，其他的代碼塊根據(jù)不同置信度作為可能來源信息。

3 實(shí)驗(yàn)與案例分析

3.1 性 能

為了檢測工具效率，我們從開源代碼庫中隨機(jī)選擇文件來構(gòu)建不同大小代碼行數(shù)的輸入。使用Unix工具cloc[19]測量代碼行數(shù)，并且僅包含代碼，不包含注釋或空行。我們選擇的目標(biāo)項(xiàng)目代碼行數(shù)為1.27 MLOC，代碼庫中選擇的代碼行數(shù)從6.75 MLOC到120 MLOC不等。環(huán)境和設(shè)置：所有實(shí)驗(yàn)均在配備Intel i7-7820X CPU(8核，16線程)、SAMSUNG 970 EVO 1T SSD和SAMSUNG DDR4 2400 RECC 32GB RAM的單個(gè)服務(wù)器上運(yùn)行。工具配置為檢測長于10行的代碼行數(shù)。相似性設(shè)定為0.6，相對較低的閾值可能產(chǎn)生更多的產(chǎn)出，因此執(zhí)行時(shí)間應(yīng)該接近上限。如果將相似度設(shè)置得更高以獲得更好的精度，則執(zhí)行時(shí)間會更短。

執(zhí)行時(shí)間結(jié)果如表1所示。實(shí)驗(yàn)結(jié)果表明，當(dāng)目標(biāo)系統(tǒng)代碼為1.27 MLOC(百萬行)，代碼庫中選取代碼行數(shù)為10 MLOC的來源關(guān)系檢測用時(shí)1小時(shí)14分鐘，相同的目標(biāo)系統(tǒng)代碼，在代碼庫中選取代碼行數(shù)為100 MLOC的來源關(guān)系檢測用時(shí)16小時(shí)27分鐘。

表1 執(zhí)行時(shí)間

3.2 召回率與準(zhǔn)確率

由于到目前為止并沒有代碼來源的基準(zhǔn)庫，我們參考了代碼克隆中用于評估召回率的The Mutation and Injection Framework[20]框架，這是一種綜合基準(zhǔn)框架，用于評估工具在突變分析程序中對數(shù)千個(gè)細(xì)粒度人工代碼克隆的召回率。

以Java語言編寫的kubernetes-clint項(xiàng)目為例，這是一個(gè)開源的kubernetes客戶端軟件項(xiàng)目。我們在目標(biāo)軟件項(xiàng)目中隨機(jī)選擇了10個(gè)不同的方法級代碼片段；然后將這10個(gè)代碼片段分別手動修改50%和70%，再將這些修改后的變異代碼片段隨機(jī)注入小規(guī)模代碼庫中；最后利用我們的工具檢測目標(biāo)項(xiàng)目kubernetes-clint在注入變異代碼片段的代碼庫中進(jìn)行來源檢測。檢測來源相似度閾值設(shè)置為70%，進(jìn)行多次檢測取其平均值。其他編程語言也做類似的處理，最終檢測結(jié)果如表2所示。

表2 召回率

傳統(tǒng)的克隆代碼召回率主要評估某段或者某些代碼在整個(gè)數(shù)據(jù)集中的查全率問題。與傳統(tǒng)克隆代碼召回率相比，代碼來源的召回率主要評估目標(biāo)系統(tǒng)中代碼片段在代碼庫中其他項(xiàng)目的來源關(guān)系。其中不僅包含了相似性代碼片段的檢測，還包含了該段代碼所在的代碼庫信息、項(xiàng)目信息、結(jié)構(gòu)信息等。

通過手動驗(yàn)證其輸出的隨機(jī)樣本來估計(jì)工具的準(zhǔn)確率，這是典型的方法。我們從工具的結(jié)果中隨機(jī)選擇了實(shí)驗(yàn)中檢測到的200個(gè)代碼來源關(guān)系對。每個(gè)克隆對由兩位評委獨(dú)立驗(yàn)證，如果存在沖突，則在與第三位評委討論后做出最終決定。最終在函數(shù)粒度的檢測上，我們的工具準(zhǔn)確率達(dá)到95%，誤報(bào)主要存在于非常短的函數(shù)片段中，因?yàn)楹瘮?shù)片段越小，單個(gè)詞的相對權(quán)重就越大，對結(jié)果又比較大的影響。而在代碼塊粒度的檢測上，我們的工具準(zhǔn)確率為85%，誤報(bào)的原因與函數(shù)片段類似。

3.3 案例分析

針對單個(gè)項(xiàng)目不同的release版本中的代碼來源關(guān)系，我們以Linux內(nèi)核中包含的arch模塊代碼為例，研究arch模塊中部分代碼在Linux和FreeBSD不同發(fā)布版本之間的來源關(guān)系。我們在arch模塊中選取了長度大小適中的void acct_process(void)函數(shù)，目的是研究該段代碼在不同Linux和FreeBSD發(fā)布版本中的來源關(guān)系，也就是要找出該段代碼在哪些Linux內(nèi)核版本中出現(xiàn)過。void acct_process(void)函數(shù)只是static void do_acct_process(struct file *file)函數(shù)的包裝器，而static void do_acct_process(struct file *file)函數(shù)的主要功能是調(diào)用者保存對文件的引用。void acct_process(void)函數(shù)代碼片段如下：

void acct_process(void){

struct file *file = NULL;

//accelerate the common fastpath:

if (!acct_globals.file)

return;

spin_lock(&acct_globals.lock);

file = acct_globals.file;

if (unlikely(!file)) {

spin_unlock(&acct_globals.lock);

return;

}

get_file(file);

spin_unlock(&acct_globals.lock);

do_acct_process(file);

fput(file);

}

由于Linux和FreeBSD中release版本眾多，我們選取了具有代表性的Linux-2.5.75、Linux-2.6.0、Linux-3.2.3、Linux-3.10.1版本和FreeBSD-7.3、FreeBSD-9.1、FreeBSD-11.0版本。結(jié)果顯示arch模塊中void acct_process(void)函數(shù)在Linux-2.6.0、Linux-3.2.3和FreeBSD-9.1中出現(xiàn)過，在Linux-3.10.1和FreeBSD-11.0其他版本中并未出現(xiàn)，結(jié)果如圖2所示。

圖2 arch模塊在Linux和FreeBSD中代碼來源

針對多個(gè)項(xiàng)目的代碼來源關(guān)系，我們分析了android-xbmcremote項(xiàng)目在不同來源項(xiàng)目中的來源關(guān)系。android-xbmcremote 是GitHub上Android開源項(xiàng)目，我們的代碼庫選取了50個(gè)開源項(xiàng)目。其中android-xbmcremote中public boolean equals(Object o)函數(shù)代碼在當(dāng)前代碼資源庫中，來自5個(gè)項(xiàng)目，完全相同的代碼最早出現(xiàn)在Spring-Framework項(xiàng)目的3.2.18版本中，有70%相似的代碼最早出現(xiàn)在ElasticSearch項(xiàng)目，因此我們認(rèn)為它可能來自Spring-Framework項(xiàng)目、ElasticSearc項(xiàng)目、Spring-boot項(xiàng)目。由于代碼資源庫中的項(xiàng)目和版本有限，因此所得到的結(jié)論僅能參考。但本文所提的方法是通用的，并且可以通過并行化方式在更大規(guī)模的代碼資源庫中使用。

3.4 有效性威脅

內(nèi)部有效性威脅：所提的方法目前僅是以代碼克隆為手段的，由于代碼可能會發(fā)生持續(xù)演化，因此對演化的分析可能是本方法的弱點(diǎn)，難以找到由于持續(xù)演化而不再是克隆的可能來源片段。但是由于本方法對克隆檢測是逐版本進(jìn)行的，因此一定程度上緩解了版本演化的矛盾，可以在一定的置信度內(nèi)找到演化的代碼來源關(guān)系。

外部有效性威脅：目前只對兩個(gè)待測系統(tǒng)進(jìn)行了來源分析，并且代碼資源庫中的代碼量也只有千萬行級，因此本方法對于其他類型或語言的項(xiàng)目的來源檢測效果仍有待考量。但我們在選擇項(xiàng)目時(shí)考慮了不同時(shí)間、不同規(guī)模的項(xiàng)目，從而所選項(xiàng)目具有一定的代表性，這表明在符合特定條件的情況下，本方法具有通用性。

4 結(jié) 語

本文提出了一種基于Hash詞袋模型的跨項(xiàng)目的大規(guī)模代碼來源分析方法，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)大規(guī)模代碼庫的代碼來源追蹤系統(tǒng)。該系統(tǒng)首先提取代碼詞袋模型，然后利用詞袋模型設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)并行化的代碼來源算法，找出目標(biāo)項(xiàng)目在代碼庫中的來源關(guān)系。該系統(tǒng)能夠在多個(gè)項(xiàng)目之間找到不同克隆代碼的來源關(guān)系，輔助軟件維護(hù)人員作出相應(yīng)的軟件維護(hù)決策。實(shí)驗(yàn)結(jié)果表明，該系統(tǒng)能夠有效地找出目標(biāo)項(xiàng)目在大規(guī)模代碼庫中的代碼來源信息。

本文下一步工作將考慮代碼演化，進(jìn)一步細(xì)分置信度，使來源分析更精確；同時(shí)也將擴(kuò)展數(shù)據(jù)規(guī)模，優(yōu)化算法，提升效率。