基于抽象語法樹和改進粒子群算法的代碼同源性分析.pdf

1、隨著計算機和互聯網的發(fā)展，社會對軟件開發(fā)人員的需求量逐年增加，但龐大的代碼量使得人工審核代碼變得不可能，同時便捷的互聯網使得代碼抄襲情況越來越嚴重，而源代碼的同源性分析能比較兩個軟件從源代碼到軟件功能之間的差別，找出它們之間的相似之處或相同之處，從而有效分辨代碼抄襲情況，因此源代碼的同源性分析對于代碼的知識產權保護顯得特別重要。常見的同源性分析主要有三種:基于文本的同源性分析、基于令牌(token)的同源性分析以及基于語法樹的同源性分析

2、。其中基于語法樹的同源性分析被廣泛采用。
　　本文提出一種基于抽象語法樹和改進粒子群算法的代碼同源性分析方法。該方法先對程序代碼進行預處理得到中間代碼，然后進行詞法語法分析并利用抽象語法樹存儲語法結構信息，最后利用改進后的粒子群算法進行迭代優(yōu)化。具體做了以下幾個方面的工作。
　　一、基于ANTLRV4工具，研究了ANTLRV4構造詞法分析器和語法分析器的過程。詞法分析主要讀入源代碼，把構成源程序的字符流進行識別并轉化成記號流

3、作為語法分析的輸入。語法分析主要接受來自詞法分析器輸出的記號流并將其轉化為抽象語法樹。
　　二、針對C++語言特性，進行了表達式抽象語法樹結構的描述以及語句的抽象語法樹結構的描述。為了避免語法分析時匹配失敗提出了增加虛擬節(jié)點的改進思路，利用ANTLR自帶的Listener監(jiān)聽器進行語法樹的遍歷以及遍歷完將其寫入文件進行存儲，從而為粒子群算法的應用提供了數據來源。
　　三、針對基本粒子群算法容易陷入局部最優(yōu)的缺點提出了三點改進

4、思路，即粒子編碼方式的改進、通過變異策略增加粒子的多樣性以及收斂因子的優(yōu)化。
　　四、建立和分析了反抄襲檢測系統(tǒng)的開發(fā)環(huán)境和開發(fā)平臺，該系統(tǒng)主要是由輸入模塊、預處理模塊、AST分析模塊、相似度計算模塊和輸出模塊構成。輸入模塊主要實現源文件和對比文件的輸入;預處理模塊的主要功能是刪除程序代碼中不影響程序代碼生成AST的部分;AST分析結果模塊是將所有樹節(jié)點信息，包括哈希值，節(jié)點類型，節(jié)點名稱，節(jié)點信息量輸出出來;相似度計算模塊是將每