Detect Algorithm Used From Program Execution Trace

本論文主要目的在於處理競賽程式中，程式碼在演算法層面的相似度的問題。計算程式間演算法層面的相似度可以被用在程式碼的檢索以及分類，但過去相關的方法多半不能被用在找出演算法層面的相似度上。為了解決這問題，我們在程式執行時的變數數值變化中，找出一些我們稱為 “核心值” (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