由程式動態行為偵測所使用之演算法

Detect Algorithm Used From Program Execution Trace

時丕勳(Pi-Hsun Shih)

指導教授 ： 鄭卜壬

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2015年)

https://doi.org/10.6342/NTU.2015.10920

摘要

本論文主要目的在於處理競賽程式中，程式碼在演算法層面的相似度的問題。計算程式間演算法層面的相似度可以被用在程式碼的檢索以及分類，但過去相關的方法多半不能被用在找出演算法層面的相似度上。為了解決這問題，我們在程式執行時的變數數值變化中，找出一些我們稱為 “核心值” (core values) 的，與其使用的演算法有強烈相關的數值。本論文提出了四種不同的方法來找出這些核心值，並且提出了在這些核心值序列上加上權重的方法。我們標記了一個有十八個演算法，約四百五十個程式的測試資料集，並且用此資料集測試了提出的方法的性能。測試結果顯示我們找到的相似度，確實能反映出程式是否使用相同的演算法。

關鍵字

程式碼 ； 演算法相似度

並列摘要

This thesis address the problem of detecting algorithm similarity of source codes from competitive programming. Detecting algorithm similarity can be applied to retrieval and clustering task for codes on algorithm level, and most past works can’t be applied to finding algorithm level similarity of programs. We solve the problem by extracting some important runtime value that characterise the algorithm used, called core values. We proposed four different methods to extract core values, and a scheme of adding weight to core values. We have labelled a dataset consist of 18 algorithms and about 450 programs, and evaluate the proposed schemes on this dataset. The results show that our approaches are effective to detect similar algorithm.

並列關鍵字

Source code ； Algorithm level similarity

參考文獻

[2] B. Cleary, C. Exton, J. Buckley, and M. English. An empirical analysis of information retrieval based concept location techniques in software comprehension. Empirical Softw. Engg., 14(1):93–130, Feb. 2009.

[11] P. van der Spek, S. Klusener, and P. van de Laar. Towards recovering architectural concepts using latent semantic indexing. In Software Maintenance and Reengineering, 2008. CSMR 2008. 12th European Conference on, pages 253–257, April 2008. 25

[13] NTU Online Judge. http://acm.csie.org/ntujudge/index.php. Accessed: 2015-07-31.

[15] UVa Online Judge. https://uva.onlinejudge.org/. Accessed: 2015-07-31.

[17] F. Zhang, D. Wu, P. Liu, and S. Zhu. Program logic based software plagiarism detection. In Proceedings of the 2014 IEEE 25th International Symposium on Software Reliability Engineering, ISSRE ’14, pages 66–77, Washington, DC, USA, 2014. IEEE Computer Society.