基于抽象語(yǔ)法樹(shù)和改進(jìn)粒子群算法的代碼同源性分析.pdf

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

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

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

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