[發(fā)明專利]程序相似性檢測的方法和裝置

在審

• 申請?zhí)枺?/td>: 201810241076.1
• 申請日: 2018-03-22
• 公開（公告）號(hào): CN110297750A
• 公開（公告）日: 2019-10-01
• 發(fā)明（設(shè)計(jì)）人: 張亞芹
• 申請（專利權(quán)）人: 北京京東尚科信息技術(shù)有限公司;北京京東世紀(jì)貿(mào)易有限公司
• 主分類號(hào): G06F11/36
• 分類號(hào): G06F11/36;G06K9/62
• 代理公司: 中原信達(dá)知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11219
• 代理人: 張一軍;張效榮

本發(fā)明公開了程序相似性檢測的方法和裝置，涉及計(jì)算機(jī)技術(shù)領(lǐng)域。該方法的一具體實(shí)施方式包括：對待檢測的各個(gè)程序進(jìn)行聚類；對于每個(gè)類，確定該類中任意兩個(gè)程序之間的匹配度；基于所述匹配度，確定所述任意兩個(gè)程序之間的相似性。該實(shí)施方式能夠在保證效率的基礎(chǔ)上提高程序相似性檢測的準(zhǔn)確率。

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

本發(fā)明涉及計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及一種程序相似性檢測的方法和裝置。

背景技術(shù)

程序設(shè)計(jì)課程是計(jì)算機(jī)軟件相關(guān)專業(yè)的重要課程，編程能力是該課程的考察重點(diǎn)。以前大都通過人工審查的方式檢測各個(gè)程序之間的相似性。但是，人工審查的效率極低。為了提高審查效率，程序相似性的自動(dòng)檢測應(yīng)運(yùn)而生。

目前，已有的程序相似性自動(dòng)檢測主要通過度量程序之間的相似性來實(shí)現(xiàn)。度量程序相似性的方法分為兩類：屬性計(jì)數(shù)法和結(jié)構(gòu)度量法。

在實(shí)現(xiàn)本發(fā)明過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)中至少存在如下問題：

屬性計(jì)數(shù)法雖然快速，但在準(zhǔn)確性上還有很大提升空間。結(jié)構(gòu)度量法準(zhǔn)確率高，但算法復(fù)雜、時(shí)間復(fù)雜度高。

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

有鑒于此，本發(fā)明實(shí)施例提供一種程序相似性檢測的方法和裝置，能夠在保證效率的基礎(chǔ)上提高程序相似性檢測的準(zhǔn)確率。

為實(shí)現(xiàn)上述目的，根據(jù)本發(fā)明實(shí)施例的一個(gè)方面，提供了一種程序相似性檢測的方法。

根據(jù)本發(fā)明實(shí)施例的程序相似性檢測的方法，包括：

對待檢測的各個(gè)程序進(jìn)行聚類；

對于每個(gè)類，確定該類中任意兩個(gè)程序之間的匹配度；

基于所述匹配度，確定所述任意兩個(gè)程序之間的相似性。

可選地，對待檢測的各個(gè)程序進(jìn)行聚類，包括：

對于每個(gè)待檢測的程序，獲取該程序的多個(gè)屬性信息，基于所述多個(gè)屬性信息構(gòu)造該程序的特征向量；

根據(jù)每個(gè)待檢測的程序的特征向量進(jìn)行聚類；

其中，所述多個(gè)屬性信息包括以下至少之一：詞匯數(shù)，程序長度，程序大小，控制流、控制結(jié)構(gòu)、數(shù)據(jù)依賴、嵌套深度和結(jié)構(gòu)。

可選地，采用模糊聚類法對待檢測的各個(gè)程序進(jìn)行聚類。

可選地，確定該類中任意兩個(gè)程序之間的匹配度，包括：

對于所述任意兩個(gè)程序中的每一個(gè)：將該程序輸入詞法分析器中生成token串，再把token串輸入到語法分析器中生成語法樹；

采用Zhang-Shasha算法確定兩棵語法樹之間的距離和相似度；

基于所述距離和相似度確定所述任意兩個(gè)程序之間的匹配度。

根據(jù)本發(fā)明實(shí)施例的再一個(gè)方面，提供了一種程序相似性檢測的裝置。

根據(jù)本發(fā)明實(shí)施例的程序相似性檢測的裝置，包括：

聚類模塊，對待檢測的各個(gè)程序進(jìn)行聚類；

匹配模塊，對于每個(gè)類，確定該類中任意兩個(gè)程序之間的匹配度；

判斷模塊，基于所述匹配度，確定所述任意兩個(gè)程序之間的相似性。

可選地，所述聚類模塊還用于：

對于每個(gè)待檢測的程序，獲取該程序的多個(gè)屬性信息，基于所述多個(gè)屬性信息構(gòu)造該程序的特征向量；

根據(jù)每個(gè)待檢測的程序的特征向量進(jìn)行聚類；

其中，所述多個(gè)屬性信息包括以下至少之一：詞匯數(shù)，程序長度，程序大小，控制流、控制結(jié)構(gòu)、數(shù)據(jù)依賴、嵌套深度和結(jié)構(gòu)。