以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數:23 、訪客IP:3.133.140.122
姓名 吳尉誠(Wei-Cheng Wu) 查詢紙本館藏 畢業系所 資訊工程學系 論文名稱 基於抽象語法樹和編碼的程式碼抄襲檢測器之實作與方法
(The Implementation and Method of a Code Plagiarism Checker based on Abstract Syntax Tree and Encoding)相關論文 檔案 [Endnote RIS 格式] [Bibtex 格式] [相關文章] [文章引用] [完整記錄] [館藏目錄] 至系統瀏覽論文 (2031-8-1以後開放) 摘要(中) 程式碼抄襲檢測技術對於程式設計課程是相當重要的,現在的比對技術以屬性、結構以及混合為主。本研究使用基於抽象語法樹和編碼的比對方式。我們針對抽象語法樹的節點給予自定義編碼符號,以及針對每個程式碼區塊括號,例如:函式、迴圈等,給予不同的括號編碼符號,並針對各種程式抄襲行為進行條件處理,經過此條件處理,原始程式碼輸出的編碼格式可與抄襲程式碼輸出的編碼格式完全一致,便可以有效檢測出相似型態、行為相似以及位置順序調換問題。最後,透過本研究使用的演算法便可計算出相似度數值,使用者可透過此相似度數值來評斷兩方程式之間的抄襲可能性。只要知道某抄襲行為與程式碼之間的對應條件,透過本研究的方法便可以檢測出該程式碼抄襲行為。本研究將這個工具稱為PASTE (Plagiarism checker by Abstract Syntax Tree and Encoding)。 摘要(英) The code plagiarism detection technology is very important for programming assignments. And, the current matching technology is mainly based on attribute, structure, and hybrid. In this paper, we encode the nodes of the abstract syntax tree. We define customized encoding symbols for the nodes of the abstract syntax tree. And, we define different bracket encoding symbols for each code block, such as functions, loops, etc., In addition, we use conditional encoding for various code plagiarism behaviors. After conditional encoding, the encoding format from the source code can be exactly the same as the encoding format from the plagiarism code. With this method, we can effectively detect similar types, similar behaviors, and position order exchange problems. Finally, by using the algorithm we proposed in this paper, we can calculate the similarity value, and users can judge the possibility of plagiarism from this similarity value. As long as we know the relationship between a certain plagiarism behavior and the source code, the code plagiarism behavior can be detected by our method. We name this tool PASTE (Plagiarism checker by Abstract Syntax Tree and Encoding). 關鍵字(中) ★ 抄襲偵測
★ 抽象語法樹
★ 程式比對關鍵字(英) ★ plagiarism detection
★ abstract syntax tree
★ code comparison論文目次 摘要v
Abstract vi
誌謝vii
目錄viii
圖目錄xi
表目錄xii
一、緒論1
1.1 程式碼抄襲行為......................................................... 1
1.2 早期程式碼抄襲檢測方法............................................. 2
1.3 現有程式碼抄襲檢測方法............................................. 3
1.4 字串相似度演算法...................................................... 8
二、動機12
2.1 範例........................................................................ 12
2.2 現有工具的分析......................................................... 14
2.2.1 MOSS ............................................................. 14
2.2.2 JPlag .............................................................. 14
2.2.3 SPDS.............................................................. 15
2.3 問題總結.................................................................. 15
viii
目錄
三、方法16
3.1 資料前處理............................................................... 18
3.1.1 抽象語法樹...................................................... 18
3.1.2 編碼............................................................... 19
3.2 相似度計算............................................................... 23
3.2.1 最長共同子字串................................................ 24
3.2.2 演算法............................................................ 24
四、實作28
4.1 特定節點條件編碼...................................................... 28
4.1.1 相似型態檢測................................................... 28
4.1.2 行為相似檢測................................................... 29
4.1.3 if-else 順序調換檢測........................................... 30
4.2 實作限制.................................................................. 32
五、評估33
5.1 多項抄襲偽裝實驗測試結果.......................................... 33
5.2 分析與解釋............................................................... 36
5.2.1 改寫變數型態................................................... 36
5.2.2 改寫變數名稱................................................... 36
5.2.3 程式碼位置調換................................................ 37
5.2.4 改寫迴圈類型................................................... 37
5.2.5 改寫函數型態................................................... 38
5.2.6 改寫函數名稱................................................... 38
5.2.7 刪除原始註解................................................... 39
5.2.8 插入註解......................................................... 40
5.2.9 插入空白行...................................................... 40
5.2.10 插入變數......................................................... 41
ix
目錄
5.2.11 插入非相關程式碼............................................. 42
5.3 False Positive 實驗與結果............................................. 43
5.4 評估總結.................................................................. 50
六、相關研究51
6.1 CCFinder: a multilinguistic token-based code clone detection
system for large scale source code .................................... 51
6.2 Plagiarism in Programming Assignments.......................... 52
七、未來展望53
八、總結54
參考文獻55參考文獻 [1] A. Parker and J. O. Hamblen, “Computer algorithms for plagiarism detection,” IEEE
Transactions on Education, vol. 32, no. 2, pp. 94–99, 1989.
[2] G. Whale, “Identification of program similarity in large populations,” The Computer
Journal, vol. 33, no. 2, pp. 140–146, 1990.
[3] P. Clough, “Plagiarism in natural and programming languages: an overview of
current tools and technologies,” Department of Computer Science, University of
Sheffield, 2000.
[4] O. Karnalim, W. Chivers, et al., “Similarity detection techniques for academic source
code plagiarism and collusion: A review,” in 2019 IEEE International Conference
on Engineering, Technology and Education (TALE), pp. 1–8, IEEE, 2019.
[5] P. Sallis, A. Aakjaer, and S. MacDonell, “Software forensics: old methods for a
new science,” in Proceedings 1996 International Conference Software Engineering:
Education and Practice, pp. 481–485, IEEE, 1996.
[6] S. Schleimer, D. S. Wilkerson, and A. Aiken, “Winnowing: local algorithms for
document fingerprinting,” in Proceedings of the 2003 ACM SIGMOD international
conference on Management of data, pp. 76–85, 2003.
[7] L. Prechelt, G. Malpohl, M. Philippsen, et al., “Finding plagiarisms among a set of
programs with jplag,” J. UCS, vol. 8, no. 11, p. 1016, 2002.
[8] J. Feng, B. Cui, and K. Xia, “A code comparison algorithm based on ast for plagiarism
detection,” in 2013 Fourth International Conference on Emerging Intelligent
Data and Web Technologies, pp. 393–397, IEEE, 2013.
[9] W. Yang, “Identifying syntactic differences between two programs,” Software: Practice
and Experience, vol. 21, no. 7, pp. 739–755, 1991.
[10] F. Tip, “A survey of program slicing techniques,” 1994.
[11] C. Liu, C. Chen, J. Han, and P. S. Yu, “Gplag: detection of software plagiarism
by program dependence graph analysis,” in Proceedings of the 12th ACM SIGKDD
international conference on Knowledge discovery and data mining, pp. 872–881, 2006.
[12] 許聖泉, “程式碼動態結構抄襲鑑定,” Master’s thesis, 國立臺北科技大學資訊工程
系研究所, 2017. https://hdl.handle.net/11296/b3ksvu.
[13] R. Gao, L. Hu, W. E. Wong, H.-L. Lu, and S.-K. Huang, “Effective test generation
for combinatorial decision coverage,” in 2016 IEEE International Conference on
Software Quality, Reliability and Security Companion (QRS-C), pp. 47–54, IEEE,
2016.
[14] R. Santelices and M. J. Harrold, “Efficiently monitoring data-flow test coverage,” in
Proceedings of the twenty-second IEEE/ACM international conference on Automated
software engineering, pp. 343–352, 2007.
[15] M. J. Wise, “String similarity via greedy string tiling and running karp-rabin matching,”
Online Preprint, Dec, vol. 119, no. 1, pp. 1–17, 1993.
[16] M. J. Wise, “Detection of similarities in student programs: Yap’ing may be preferable
to plague’ing,” Acm Sigcse Bulletin, vol. 24, no. 1, pp. 268–271, 1992.
[17] A. T. Wibowo, K. W. Sudarmadi, and A. M. Barmawi, “Comparison between fingerprint
and winnowing algorithm to detect plagiarism fraud on bahasa indonesia
documents,” in 2013 International Conference of Information and Communication
Technology (ICoICT), pp. 128–133, IEEE, 2013.
[18] A. Jadalla and A. Elnagar, “A fingerprinting-based plagiarism detection system for
arabic text-based documents,” in 2012 8th International Conference on Computing
Technology and Information Management (NCM and ICNIT), vol. 1, pp. 477–482,
IEEE, 2012.
[19] N. Heintze et al., “Scalable document fingerprinting,” in 1996 USENIX workshop on
electronic commerce, vol. 3, 1996.
[20] U. Manber et al., “Finding similar files in a large file system.,” in Usenix Winter,
vol. 94, pp. 1–10, 1994.
[21] T. Kamiya, S. Kusumoto, and K. Inoue, “Ccfinder: A multilinguistic token-based
code clone detection system for large scale source code,” IEEE Transactions on
Software Engineering, vol. 28, no. 7, pp. 654–670, 2002.
[22] M. Joy and M. Luck, “Plagiarism in programming assignments,” IEEE Transactions
on education, vol. 42, no. 2, pp. 129–133, 1999.
[23] R. Sedgewick and K. Wayne, Algorithms. 4th Edition, Pearson, 2011.
[24] W. B. Croft, D. Metzler, and T. Strohman, Search engines: Information retrieval in
practice, vol. 520. Addison-Wesley Reading, 2010.指導教授 莊永裕(Yung-Yu Zhuang) 審核日期 2021-7-21 推文 facebook plurk twitter funp google live udn HD myshare reddit netvibes friend youpush delicious baidu 網路書籤 Google bookmarks del.icio.us hemidemi myshare