程序代碼相似度比較的研究與實現(xiàn) 摘 要 計算機程序設計課程是計算機及其相關專業(yè)中非常重要的 一門 專業(yè)基礎課程 ,因而程序設計課程 的教學 也 顯得尤為重要。 為了提高學生的編程能力及為后續(xù)課程的學習打下堅實的基礎，這就要求學生能夠獨立的完成編程設計作業(yè)。但由于 互聯(lián)網 搜索的便利性及計算機數據的易復制性，導致 部分 學生在完成程序設計作業(yè)時采取搜索、抄襲他人代碼的行為 ,該行為不但對學生 的 成長不利，同時也影響成績考核的公平性 。本 系統(tǒng)不但能夠 幫助教師檢測學生的程序作業(yè) 是否存在 抄襲情況 ,同時對軟件版權的鑒定也具有好的現(xiàn)實意義。 程序 代碼相似度比較是 通過 利用一定的檢測識別手段，判斷兩個程序 的源碼之間所存在 的相似性， 以及 度量兩者之間的相似程度 ，并根據相似程度判別兩個程序的源碼是否存在抄襲行為 。 針對 序源碼相似性問題的檢測方法，通過分析及研究相似代碼的特點和類型、源程序的屬性類型、源程序預處理以及相似度評價標準，采用 法來比較兩個源程序文件在結構上的相似性。 同時設計出用于 檢測 代碼 相似度 的 軟件，以提高教學考核的工作效率。 本 系統(tǒng)軟件設計基于 發(fā)平臺，采用面向對象的功能模塊化設計思想，在結構度量的基礎上，設計開發(fā)了文件讀 取模塊、預處理模塊、相似度檢測和結果輸出模塊等四大功能模塊。界面簡潔友好，檢測結果按相似度高低排列并保存在指定的文件中。 關鍵詞： 代碼相似性 ;預處理過程 ;結構度量 ;相似度檢測 is in is In to to a to of of to in to of an on of of is at of is of of to to of is of of of CS is to in At of in to of on of is so on to of in a 目 錄 摘 要 . 1 章 緒論 .開發(fā)背景 .研究目的及研究意義 .程序代碼相似度檢測技術的研究現(xiàn)狀 . 國外研究情況 . 國內研究情況 . 目前主流的代碼抄襲檢測系統(tǒng) .論文組織簡介 .章小結 . 2 章 程序代碼相似度檢測的理論基礎 . 11 相關概念的引入 . 11 序抄襲描述 . 11 碼相似度定義 .程序相似代碼的分類和掩飾性行為 . 從源代碼單個語句方面討論相似代碼的分類 . 從功能和內容方面討論相似代碼的分類 .識別相似代碼的一般方法 . 已被成功運用的識別方法 . 從整體上判斷代碼相似的方法 .相似度度量算法的研究 . 屬性計數技術 . 結構度量技術 . 散列值匹配算法 .章小結 . 3章 程序代碼相似性識別方法的研究 .標代碼相似性的識別 .于 法的識別方法 . 于加權屬性相似性的識別 方法 . 加權屬性識別方法的理論依據 . 源代碼相似度計算 .章小結 . 4 章 程 序代碼相似度檢測系統(tǒng)的分析與設計 .運行流程 .流程說明 .軟件架構 . 文件讀取模塊 . 預處理模塊 . 似代碼檢測模塊 . 相似度計算模塊 . 結果輸出模塊 .章小結 . 5 章 程序代碼相似度檢測系統(tǒng)的實現(xiàn) .開發(fā)環(huán)境與開發(fā)平臺 . 開發(fā)環(huán)境 . 開發(fā)平臺 .程序代碼相似度檢測的實現(xiàn)技術 . 術的優(yōu)點 . 術的開發(fā)框架 . 三種常用的 程工具包 .程序代碼相似度檢測系統(tǒng)各功能模塊的實現(xiàn) . 文件讀 取模塊 . 程序代碼預處理模塊 . 相似代碼檢測模塊 . 相似度計算模塊 . 結果輸出模塊 .章小結 . 6 章 程序代碼相似度檢測系統(tǒng)的測試與運行 . 代碼預處理的測試 .法的檢測 .直接遞歸法和動態(tài)規(guī)劃法求最長公共子序列的效率分析 .檢測結果分析 . 檢測精度分析 . 系統(tǒng)界面 . 測試結果綜合分析 .章小結 . 7 章 結論與展望 .論 .望 .章小結 . 謝 . 錯誤 !未定義書簽。 參 考 文 獻 . 第 1 章 緒論 開發(fā)背景 隨著信息技術的高速發(fā)展 ,信息技術與教育相結合已經越來越應用到現(xiàn)代教學上 ,針對計算機科學與技術專業(yè)的各類程序設計課程 ,就有統(tǒng)一的程序語言支撐平臺來幫助教學 ,程序語言支撐平臺為學生提供了一個綜合統(tǒng)一在線練習平臺 ,幫助學生提供編程能力 ,同時也幫助教師布置程序設計課程的作業(yè)和考試 ,這種利用信息技術實現(xiàn)教學自動化大大提高了教師批改作業(yè)和考試的效率。然而也正是因為信息技術的發(fā)展 ,從互聯(lián)網上獲取程序資源也越來越方便和快捷 ,有些 學生可能偷懶 ,直接從網上查找相關程序或者從同學那里 復制程序提交給程序語言支撐平臺。教師如果去手工檢查每個程序 ,需要進行兩兩對比 ,這樣會耗費大量的時間和精力 ,而且學生通過將程序稍微修改 ,讓人工檢查變得更加困難。 這就要求我們提出一種新的 檢測機制 ， 通過綜合考慮程序抄襲時所采用的各種作弊手段，并結合現(xiàn)有抄襲檢測技術，尋求一種快速的算法，并最終完成具有實際應用價值的軟件 。 研究 本課題的目的就是 ： 根據程序語言的特性 ,實現(xiàn)一個 用于檢測 程序 源代碼相似度 的軟件系統(tǒng) ,并且 該系統(tǒng)通過與程序語言支撐平臺進行整合 ,對每個學生提交的作 業(yè)與 相同題目的 其他 程序 進行 相似度值 的計算。本 系統(tǒng) 針對 代碼 抄襲 行為的鑒定方法的原理 是： 首先 計算 給出的兩段程序 源 代碼之間的相似度值 ,并根據該值 判斷兩個程序 之 間是否 存在可能的 抄襲 行為 ,若該相似度 值越大 ,說明存在抄襲的可能性越高。 與 自然語言相比 ，程序語言 有其獨特的特點。自然語言 的特點是 靈活多變 ,構成語言的詞匯很多 ,且同一詞匯在不同的語義環(huán)境下存在不同的含義，即使 具有 同一含義的詞匯 組成也 是 多種多樣 ,因而 檢測自然語言的相似度會 非常困難 。 而程序語言由于 具 有固定的關鍵字 及 語法規(guī)則 ,因而所編寫的程序的 結構 相對簡單 ,所以對程序語言進行 源代碼檢測要 相對 容易 些 ,針對該問題，國內外對其 相似度檢測也做了不少研究 ,一些系統(tǒng)也比較成熟。 當前 程序 源代碼的 相似度檢測主要 采用兩大類技術 :屬性計數技術和結構度量技術 。 屬性計數技術主要是 通過統(tǒng)計程序源代碼 的一些屬性計數 ,并不考慮程序 的設計 流程結構 , 因而該方法對于檢測兩源碼文件是否為存在拷貝問題最為有效，而一旦對拷貝的程序源碼進行修改，例如添加一些無用變量、無用的注釋代碼等，其檢測準確性 就會大大降低。 且隨著程序抄襲或復制程度的 提高 ,很難做出正確的判斷。 而 結構度量技術則 通過 分析 并計 算 程序 源碼 結構信息 的類似性 ,因而 得到的檢測結果更 能真實地反映程序源碼 之間存在抄襲行為的可能性 。 現(xiàn) 屬性計數技術基本 上 不再 應 用于 源碼 相似度檢測 ,且 成熟的程序代碼抄襲檢測系統(tǒng) 大 都采用了結構度量技術。 使用 結構度量技術 進行源碼相似度檢測 的 工作流程 大多 為：首先對程序代碼做 預處理 ,去掉對相似度度量結果沒有影響的部分 ,例如無用 空格、空行、注釋語句等 ,然后根據一定轉換規(guī)則對預處理后的代碼文件進行語法分析 ,將其轉換為表示程序結構信息的標記字符串 ,最后對標記字符串通過字符串串匹配算法 （ 例 如 法）進行 比較 處理 。所以轉換規(guī)則 非常重要 ,轉換規(guī)則必須能夠將程序語言一些結構化信息體現(xiàn)出來 ,但值得注意的是 串匹配算法并不能體現(xiàn)程序源碼 的全部 結構信息。 現(xiàn)比較成熟的程序源碼 相似度檢測系統(tǒng) 大都 采用串匹配算法來 進行 程序源代碼的 相似度 的檢測 ,該方法僅能夠檢測部分完全獨立編寫的程序 ,但對于一些代碼抄襲的投機行為卻不能進行正確的識別，例如在程序中添加一些無用結構（在程序源碼中添加一些無用變量 ,無用賦值代碼），或對控制流程 進行修改。這 些 修改 有時 并 沒有 花費抄襲者大量時間和精力 ,但很成功的混靖代碼段 ,使得串匹配算法計算出來的相似度很小 ,達 不 到相似 度檢測的目的。 本研究將依據程序代碼相似度檢測基本理論 ,并從何利用屬性計數 、結構度量計數和散列值匹配算法來計算相似度。 研究目的及研究意義 在計算機教學過程中，負責批閱作業(yè)的老師在批閱過程中總是要面對大量的程序代碼，工作相當的繁重，而且人工校對效率非常低下，同時在檢查中也會因為疲勞等原因出現(xiàn)很多疏漏。 部分學生 可能 因為 沒有學好 該 課程或者 其他目的， 在完成程序設計作業(yè)時采取搜索、抄襲他人代碼的行為 ,該行為不但對學生的成長不利，同時也會影響成績考核的公平性 。 本 課題 旨在實現(xiàn)一個程序源碼 相似度 檢測的系統(tǒng) ， 通過 該系統(tǒng)檢測學生提交的編碼課程作業(yè) 與給定答案的接近程度，并顯示檢測 結果。 同時 ，還可以根據度量值判斷學生所寫程序代碼的標準化程度，從而輔助實現(xiàn)作業(yè)批改的自動化或試卷評閱的自動化。 程序代碼相似度檢測技術的研究現(xiàn)狀 國外研究情況 程序代碼相似性檢測最早是處于重復代碼的檢測及優(yōu)化而提出的， 在 20 世紀 70年代 ， 針對代碼 重復及剽竊 行為， 出 了基于 屬性計數法 工作原理的 軟 件科學度量檢測方法 。 量方法 的工作原理是： 以程序中出現(xiàn)的操作符和操作數為計數對象，以它們的出現(xiàn)次數 作為計數目標來計算程序容量和工作量。 而 根據 性計數法的工作原理 實現(xiàn)了第一個針對 碼的剽竊檢測系統(tǒng)。但由于屬性計數法拋棄了太多的程序結構信息， 從而 導致檢測 錯誤率太高。 針對該問題， 出了 結構度量法，其工作原理是 通過 增加程序 結構信息 的 檢測 機制 ， 并 結合結構度量來檢測剽竊 的 。 結構度量法的典型是 出的圈復雜度方法， 其工作原理是： 通過計算執(zhí)行路徑的數量來衡 量一個程序中的控制流。 由于 圈復雜度只給出了程序的一個結構特征即控制流， 在編寫代碼 相似度檢測系統(tǒng)時，如果僅僅只是依據該原理則會導致檢測正確率極低，因而在使用時 需要與其它特征結合使用， 其常在 屬性計數法中 作為 一個度量指標 而存在 。 在實際應用中，往往是將結構度量法與屬性計數法綜合使用，例如 統(tǒng) 就是通過 結合屬性計數法和結構度量法來實現(xiàn)對 序代碼的剽竊檢測。 而最近 開發(fā)的代碼反剽竊 系統(tǒng)大都是通過對表達源程序結構的字符串進行比較 的工作原理實現(xiàn)的 ，如： 列等。 國內研究情況 在 1998 年 ，中國人民警官大學 就 研制了 序抄襲判定系統(tǒng)，能夠檢測序的相似度。 這個程序判定系統(tǒng) 將 言結構分為 ：控制類、變量類、運算符類及標準過程類 的四大類屬性 。該系統(tǒng)的統(tǒng)計模塊接受 程序，并統(tǒng)計程序的各種屬性。在 其中的 比較模塊中，首先比較所有程序的四個總屬性值，如果兩個程序有相似 的 可能 性 ，標上“可能相似” 的 標記，其次比較有相似可能的程序的各個屬性值，如果 哪 個程序的相應屬性之差的絕對值小于該屬性的標準偏差，則將該屬性值與其對應權值求和。比較完兩個程序的所有屬性 值 ，計算出最后的屬性值 以 比較的屬性的個數，便得到 不同 程序 之 間 的 相似程度。 2006 年，內蒙古師范大學在程序代碼屬性方法的 程序 代碼相似度識別 與比較 的研究中，通過統(tǒng)計 和比較 兩個程序代碼的多種屬性特征 及數值 ，運用空間向量之間的距離計算公式來得到程序代碼的相似度。但是，在研究過程中沒有考慮到各個屬性之間的關系以及由于 程序屬性 重要性不同 而導致權重不同的影響因素，舍棄甚至無視了 許多有用的信息，降低了 程序 識別 過程中 的準確度和精度，因此 在程序代碼的相似度檢測上仍然 有待于進一步 的改進和完善 。 從 目前 的 研究現(xiàn)狀可以發(fā)現(xiàn)，國內自 1998 年應用屬性檢測程 序相似度以后，對這個課題所做得研究 相對 較 少。近年來，程序代碼相似度的檢測都是用各種方法綜合程序的 屬性計數和程序 的 結構度量 的 。最近 ，出現(xiàn)了從程序設計角度進行度量的方法。此外，也有人提出用神經網絡來對 程序的相似度 進行檢測 。 總之，目前 對程序 以源代碼相似性識別方法研究進展并不明顯，更多的是提出和討論關于 程序中 重復代碼 的 檢測和優(yōu)化 的 方法，這對代碼相似性識別的研究有 較大的借鑒價值，在此基礎上，尚未出現(xiàn)能夠 針對程序 源代碼相似度的具體或部分檢測識別方法 的實現(xiàn) 。 目前主流的代碼抄襲檢測系統(tǒng) (1)系統(tǒng)的作者是 以檢測的程序語言有 C、 C+、 ，用戶可以將 程序文件提交給系統(tǒng)，系統(tǒng)在檢測完之后以網頁的形式返回給用戶。但由于作者并沒有說明 該系統(tǒng)所使用的技術，因此對其實現(xiàn)細節(jié)我們一無所知。 (2)系統(tǒng)的作者是 理程序時，首先去除注釋，隨后 統(tǒng)一大小寫，然后對 同義詞 進行 替換，最 后進行相似度匹配。 不同版本的 使用的 代碼 匹配 檢測算法 也不 相 同， 本 僅僅只是 使用了 命令， 本使用的檢測算法 則 是 法， 而 本 則是使用了法。 (3)系統(tǒng)的作者是 、 和 其對代碼的相似度 檢測也是使用了 法 ，而在使用形式上 同，它 的實現(xiàn)是使用 言編寫，目前 僅 支持 C、 C+等 編程語言的檢測 。 (4)系統(tǒng)的作者是 系統(tǒng) 則是通過使用 檢測 字符串排列的 列相似性 算法 進行實現(xiàn)的 。 首先將程序源代碼進行處理，使其通過一 種緊縮的格式 進行排列，隨后系統(tǒng)將其中的一個 緊縮串 拆分 為若干份， 然后將拆分后的若干份的 每一部分到另一個程序的緊縮串中進行 匹配 ，由于這種處理方式與編程語言的語法規(guī)則及結構無關，因而這種處理算法使其能夠支持大多數語言 。 論文組織簡介 本論文共分為五個章節(jié)。 第一章主要 介紹 了程序 源代碼 相似度檢測系統(tǒng)的開發(fā)背景，研究目的及 實際使用意義，并介紹了當前主流 代碼抄襲檢測系統(tǒng) 的 基本 工作 原理及 所使用的 算法 。 第二章主要介紹 程序代碼相似度檢測 的工作理論 ，分析 了 程序相似代碼的 特點并對其進行不同的 分類及 代碼 抄襲 者 常用的 掩飾性行為， 列舉了 檢測 相似代碼的一般方法 及工作原理 ，并 針 對程序代碼相似度檢測的度量方法 的不同特點進行詳細的分析與介紹 。 第 三章給出了程序代碼相似度檢測系統(tǒng)的分析與設計，對該系統(tǒng)的功能模塊作了概要分析。 第四章主要是關于程序代碼相似度檢測系統(tǒng)的實現(xiàn)，分析了系統(tǒng)各功能模塊之間的聯(lián)系，并對每個功能模塊作了詳細的介紹。 第五章給出了該系統(tǒng)的運行界面和測試結果，并對各算法的運行效率作了比較。 章小結 本章是緒論章節(jié)，本章主要是對本課題的研究背景進行闡述，并且根據本課題開發(fā)背景明確了本課題的研究意義，在此基礎上分析了程序代碼相似度檢測技術的國內外研究現(xiàn)狀，通過分析本課題國內外研究現(xiàn)狀為本課題的研究提供研究方法和思路借鑒。本章的分 析對本課題后續(xù)的研究具有重要的指導意義。 第 2 章 程序代碼相似度檢測的理論基礎 相關概念的引入 序抄襲描述 程序語言課程隨計算機技術的發(fā)展在高校越來越重視 ,不僅計算機專業(yè)的學生學習程序語言 ,其他專業(yè) ,甚至是非工科專業(yè)也開展了程序語言的課程 ,比如應用非常廣泛的 C 語言程序課程。除了 C 語言程序設計課程外 ,C+,C#等高級程序語言課程也非常流行。程序語言課程的作業(yè)主要是以編程的方式來鍛煉學生的程序思維能力 ,這就不可避免的出現(xiàn)了代碼抄襲的問題。 程序代碼的運行必須嚴格遵守程序 語言的規(guī)范 ,必須通過編譯器的檢測 ,這就使得程序代碼源文件一般都是以電子稿形式進行提交與檢測 ,互聯(lián)網技術的普及 ,電子資料下載的快捷性 ,讓許多學生能夠輕而易舉的從網上搜索到相關代碼 ,進而抄襲。抄襲代碼不僅讓老師的教學事倍功半 ,更讓學生失去了自己學習程序語言的一個途徑。很多學生進行抄襲的時候會或多或少的修改一部分文字來迷惑老師 ,同樣 ,程序代碼的抄襲也是如此。同時 ,由于程序代碼不像普通文本那樣沒有特別的規(guī)范 ,程序代碼的修改必須保證代碼正確運行的前提下才有作用。這就造成了代碼抄襲過程中抄襲程度的不同和檢測難度級別的不 同。 修改他人程序分成了七個難度級別。如下圖 示。 圖 襲程序代碼修改的難度等級圖 示不對源程序進行任何修改 ,這種抄襲最簡單 ,不用費事 ,所以有不少抄襲屬于這種情況。 示只修改了源程序的注釋 ,這種抄襲也簡單 ,因為修改注釋肯定不會影響源程序的結果。 示修改了源程序的部分標示符 ,比如函數 ,宏 ,變量的名字 ,這種修改需要注意其他使用了這個標示符的地方也要做同樣的修改 ,通過計算機的查找替換功能也較容易做到。 示修改程序變量聲明的位置 ,這種修改需要注 意的是修改了變量的位置后要保持程序的編譯正確并且結果也正確。 示用函數體代替函數調用 ,相當于減少函數 ,這種修改也需要驗證編譯和結果。 示修改程序語句 ,比如 i+變成 i+=l 這種等價替換。 示修改程序的控制邏輯 ,這種修改比較難 ,一般人也難以做到 ,抄襲者也很少這樣去修改。 6這兩種抄襲手段比較復雜 ,如果抄襲者做到這個級別 ,基本對程序語言有較深的掌握了。 . 襲程度也給出了 10 個難度級別 ,基本和 蓋的范圍一樣 ,只是給出了更細分 的標準。 4*析了抄襲的一般規(guī)律 ,總結出抄襲轉換基本是由兩類轉換構成 :一個是跟程序機構無關的詞匯級修改 ,另一個是較復雜的結構級修改。 出的 屬于詞匯級修改 , 于結構級修改。 在實際的教學實踐中 ,學生一般都是初學者 ,大多抄襲的學生僅僅在詞匯上下工夫 ,如果說去修改程序的結構 ,往往費時又費力 ,閱讀別人的程序也不是件容易的事情 ,這樣結構級修改還不如自己動手寫新的程序。也有一種情況就是 ,通過參考別人寫的程序再通過自己理解寫出的程序可能和原來 的程序