結(jié)構(gòu)語義相似的程序識(shí)別方法研究.pdf

1、程序識(shí)別使用一個(gè)已知模式分析給定程序，從而識(shí)別給定程序的意圖。程序識(shí)別在程序理解、軟件系統(tǒng)分析、編譯器優(yōu)化、重復(fù)代碼檢查和軟件缺陷檢測(cè)等領(lǐng)域中有著廣泛的應(yīng)用。
　　本文提出結(jié)構(gòu)語義相似的程序識(shí)別方法。主要研究內(nèi)容包括以下四部分：
　　針對(duì)代碼多樣化給程序分析帶來困難的問題，提出基于系統(tǒng)依賴圖的程序標(biāo)準(zhǔn)化方法。改進(jìn)了傳統(tǒng)的系統(tǒng)依賴圖表示，使其充分表示程序的語法結(jié)構(gòu)與語義。并針對(duì)已有的指針分析算法不適合于程序標(biāo)準(zhǔn)化的問題，基于控

2、制依賴樹和改進(jìn)的指向表示方法提出流敏感和上下文敏感的指針分析算法，提高指針分析和數(shù)據(jù)流分析的準(zhǔn)確性，并使得指針分析結(jié)果可直接應(yīng)用于程序標(biāo)準(zhǔn)化轉(zhuǎn)換中。最后將改進(jìn)的系統(tǒng)依賴圖、指針分析算法與程序標(biāo)準(zhǔn)化過程有機(jī)結(jié)合，提出基于系統(tǒng)依賴圖的程序標(biāo)準(zhǔn)化模型，根據(jù)程序標(biāo)準(zhǔn)化轉(zhuǎn)換規(guī)則，對(duì)系統(tǒng)依賴圖進(jìn)行語義不變的轉(zhuǎn)換，從而消除代碼多樣化。實(shí)驗(yàn)結(jié)果表明，本文提出的指針分析算法準(zhǔn)確性高于已有的Emami指針分析算法的準(zhǔn)確性，并且應(yīng)用于程序標(biāo)準(zhǔn)化時(shí)可顯著提高代

3、碼多樣化消除率。本文的程序標(biāo)準(zhǔn)化方法的代碼多樣化消除率高于已有的Hattori與Ishi方法的代碼多樣化消除率，可以有效地消除代碼多樣化，提高程序分析的靈活性，為判定程序的結(jié)構(gòu)語義相似奠定良好的基礎(chǔ)。
　　針對(duì)基于圖提取子程序時(shí)間與空間開銷巨大的問題，提出結(jié)構(gòu)度量相似的候選子程序提取方法。在已有的代碼相似度及編輯距離的定理和推論的基礎(chǔ)上提出新的推論，將特征向量聚類應(yīng)用于候選子程序提取中。首先，將代碼表示為控制依賴樹，通過基本代碼標(biāo)

4、準(zhǔn)化，消除影響度量值計(jì)算的代碼多樣化。然后，采用特征向量描述程序的結(jié)構(gòu)信息，將復(fù)雜的圖的相似度求解問題轉(zhuǎn)換為簡單的相似向量的聚類問題，快速提取可能與給定模式相似的候選子程序。實(shí)驗(yàn)結(jié)果表明，該方法能夠過濾掉大部分不相似代碼，并且可以識(shí)別含有代碼多樣化的代碼，為大規(guī)模軟件在語義級(jí)別上的程序識(shí)別奠定基礎(chǔ)。
　　針對(duì)已有的程序識(shí)別方法不能較好地在語義級(jí)別上識(shí)別程序，并且不能定量地衡量代碼的語義相似度的問題，提出基于系統(tǒng)依賴圖的語義級(jí)別的程

5、序識(shí)別方法。在此基礎(chǔ)上提出基于程序轉(zhuǎn)換和語義分析的編程題自動(dòng)評(píng)分方法，克服了傳統(tǒng)的基于動(dòng)態(tài)測(cè)試自動(dòng)評(píng)分和基于軟件度量分析的自動(dòng)評(píng)分方法沒有考慮學(xué)生程序是怎樣實(shí)現(xiàn)編程任務(wù)的缺陷，為編程題自動(dòng)評(píng)分提供新思路。實(shí)驗(yàn)結(jié)果表明，基于系統(tǒng)依賴圖的語義級(jí)別的程序識(shí)別方法能夠準(zhǔn)確計(jì)算代碼的語義相似度，較好地解決程序識(shí)別結(jié)果的表示和準(zhǔn)確性問題。
　　針對(duì)傳統(tǒng)基于度量值的程序識(shí)別方法準(zhǔn)確率低和基于圖的程序識(shí)別方法復(fù)雜度高的問題，在上述研究的基礎(chǔ)上，提

6、出度量值和圖相結(jié)合的程序識(shí)別方法。首先，將模式程序和用戶程序表示為改進(jìn)的系統(tǒng)依賴圖。然后，以模塊為單位，采用結(jié)構(gòu)度量相似的候選子程序提取方法，縮小語義級(jí)別程序識(shí)別的搜索空間，提高算法的效率。最后，對(duì)可能相似的候選子程序進(jìn)行高級(jí)代碼多樣化和精確的語義級(jí)別的程序匹配，識(shí)別語義相似的子程序。在此基礎(chǔ)上提出語義級(jí)別的相似代碼檢測(cè)方法，為相似代碼檢測(cè)提供新思路。實(shí)驗(yàn)結(jié)果表明，度量值和圖相結(jié)合的程序識(shí)別方法可以有效地處理大規(guī)模代碼，不但能識(shí)別完全相