[發(fā)明專利]一種基于串匹配和特征匹配的開源代碼檢測方法

在審

• 申請?zhí)枺?/td>: 201810807404.X
• 申請日: 2018-07-21
• 公開（公告）號: CN109062792A
• 公開（公告）日: 2018-12-21
• 發(fā)明（設(shè)計(jì)）人: 李必信;楊安奇;周穎;王璐璐;廖力
• 申請（專利權(quán)）人: 東南大學(xué)
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 南京眾聯(lián)專利代理有限公司 32206
• 代理人: 杜靜靜

本發(fā)明提出了一種基于串匹配和特征匹配的開源代碼檢測方法，用于檢測混源軟件中的開源代碼，從而有助于開發(fā)者進(jìn)一步的重用與再開發(fā)。該方法綜合了屬性計(jì)數(shù)法和結(jié)構(gòu)度量法各自的優(yōu)缺點(diǎn)，首先通過特征匹配的方式來縮小數(shù)據(jù)庫的搜索空間，然后依據(jù)token串的方式，基于字符串匹配算法的思想，來匹配出最大公共子串，從而在應(yīng)用于大規(guī)模軟件開發(fā)項(xiàng)目的開源代碼檢測時(shí)，使匹配時(shí)間和內(nèi)存消耗得到進(jìn)一步優(yōu)化。

技術(shù)領(lǐng)域

本發(fā)明涉及一種檢測方法，具體涉及一種基于串匹配和特征匹配的開源代碼檢測方法，屬于模式匹配和數(shù)據(jù)挖掘技術(shù)領(lǐng)域。

背景技術(shù)

隨著開源代碼的日益增長，對開源代碼的檢測技術(shù)研究越來越多，在現(xiàn)有技術(shù)中，相關(guān)的方法如下：1.基于文本的比較，其將程序劃分成字符串，通過比較字符串來查找重復(fù)的字符串序列，這種方法的優(yōu)點(diǎn)是匹配與具體語言無關(guān)，實(shí)現(xiàn)簡單方便，具有很強(qiáng)的靈活性和適應(yīng)性，缺點(diǎn)是這種簡單的行匹配方法檢測空間巨大，對大型系統(tǒng)適應(yīng)有限。同時(shí)，當(dāng)代碼有細(xì)微改變時(shí)，這種技術(shù)就檢測不出來了，也就是說它只能檢測出完全一致的代碼。2.基于參數(shù)化匹配的檢測技術(shù)，其主要思想是抓住程序中固定不變的內(nèi)容，例如運(yùn)算符、表達(dá)式等。其優(yōu)點(diǎn)就是解決了變量名不同的代碼重復(fù)性檢測問題，而缺點(diǎn)在于它將代碼拆分，從而使得被檢測到的重復(fù)代碼塊很小，同時(shí)其空間復(fù)雜度也過高。3.基于抽象語法樹的方法對語言進(jìn)行語法分析，建立完整的抽象語法樹，應(yīng)用標(biāo)準(zhǔn)算法檢測重復(fù)子樹。考慮到大型軟件系統(tǒng)中可能存在著大量的子樹，搜索空間會非常大，因此采用了hash容器存放所有的子樹，并只對hash容器進(jìn)行比較。與基于文本的方法類似，基于抽象語法樹的檢測技術(shù)對細(xì)微修改過的重復(fù)代碼的檢測效果不夠理想。由此產(chǎn)生了。4.基于依賴圖(PDG)中同構(gòu)子圖檢測重復(fù)代碼的方法，雖然這種方法能夠檢測出重新排序后的代碼，但是該方法的算法時(shí)間復(fù)雜度高達(dá)O(n⁴),依舊不適合應(yīng)用于大型軟件的檢測。因此，迫切的需要一種新的方案解決該技術(shù)問題。

發(fā)明內(nèi)容

為了提高代碼匹配在大型軟件項(xiàng)目中的匹配速度，本發(fā)明運(yùn)用了token序列匹配的思想，同時(shí)提出了一種基于代碼統(tǒng)計(jì)特征的快速匹配方式，將兩種方法結(jié)合起來，進(jìn)一步優(yōu)化匹配的時(shí)間和空間復(fù)雜度，該方案基于token串匹配重復(fù)代碼的方法，該方法先將程序劃分成token流，然后通過識別重復(fù)的token序列來找到對應(yīng)的重復(fù)代碼。由于此方法使用了源代碼的語法信息，因而分析更準(zhǔn)確，并且算法的時(shí)間復(fù)雜度相對較低，適用于分析大型的軟件代碼。

為了實(shí)現(xiàn)上述目的，本發(fā)明的技術(shù)方案如下：一種基于串匹配和特征匹配的開源代碼檢測方法，其特征在于，所述方法包括以下步驟：步驟一：代碼特征提取；步驟二：基于特征匹配的開源代碼檢測；步驟三：基于串匹配的開源代碼檢測。

作為本發(fā)明的一種改進(jìn)，所述步驟一：代碼特征提取，具體操作如下，獲取源代碼文件、解析源代碼文件、將源代碼文件依據(jù)函數(shù)進(jìn)行切分、提取相應(yīng)代碼文件中的統(tǒng)計(jì)特征和函數(shù)級別的結(jié)構(gòu)特征、將相應(yīng)的基本統(tǒng)計(jì)特征存入相應(yīng)代碼文件的特征庫中。

作為本發(fā)明的一種改進(jìn)，所述步驟一的獲取源代碼文件包括從開源代碼庫中獲取源代碼文件。

作為本發(fā)明的一種改進(jìn)，所述步驟二基于特征匹配的開源代碼檢測，具體如下，

獲取待匹配的代碼文件；

搜索其特征庫獲取相應(yīng)的特征信息；

基于迭代計(jì)算與人工比對的方法進(jìn)行特征篩選；

將篩選后的特征組成特征向量與特征庫中相應(yīng)的特征向量做歐氏距離度量；

選取度量值小于設(shè)定閾值的文件代碼作為搜索的候選集。

作為本發(fā)明的一種改進(jìn)，所述步驟三基于串匹配的開源代碼檢測，具體如下，以候選集為搜索空間，

步驟1：將源程序進(jìn)行詞法分析，將其轉(zhuǎn)化成token串標(biāo)識；