利用類神經網路做程式行為之分析研究

Abstract

快取記憶體置換策略 (replacement policy) 執行效能的好壞通常決定於 各種不同程式的執行行為。其中，局部性 (locality) 現象更被視為是程 式行為的重要指標。在另一方面，類神經網路近幾年來廣泛的使用在各種 不同領域的應用如分類、預測等方面。此篇論文的主要目的即在於利用類 神經網路的自我學習和記憶的能力，自動地找出程式行為的特性，並根據 不同形態的程式行為將程式予以分類。在這篇論文中我們提出四種改良 的 SOM 學習規則，使其適合於程式行為分類的應用。學習規則的設計精 神是利用連續執行到的兩位址間的距離大小作為判斷局部性程度的指標， 另外，也加入程式行為中 working set 的概念。實驗結果顯示這種改良 自 SOM 的學習規則的確可以將不同執行樣式的程式予以分類。對研究程 式行為的分析有更進一步的幫助與了解。 In this research, an unsupervised neural model named self- organization map (SOM) is used to classify programs based on the behavior of these programs. The SOM model can map a high- dimensional input space into a two-dimensional output space. Such a mapping could be used to measure the relationship be- tween various types of input vector. The locality phenomenon has been regarded as the most important characteristic of program behavior. Therefore, the locality information is embedded in the learning rule of the neural model based on the SOM. This thesis presents four modified learning rules based upon SOM algorithm. The design principle of algorithm 1, 2 and 3 lies in the location difference of neighboring referenced blocks since the location difference could be regarded as a characteristic of locality degree. However, in algorithm 4, the working set concept of a program is adopted in our learning rule for classifying programs. Algorithm 1 employs the minimum difference, among a fixed number of contiguous blocks, as an element of the input vector. On the contrary, algorithm 2 uses the maximum value to represent an element of the input vector. Algorithm 3 is a special case of algorithm 1 and algorithm 2, which uses the difference value of only two contiguous referenced blocks as the element. Simulation results show that these modified learning rules based upon SOM indeed can effectively classify programs. Detailed analysis of the simulation results is also provided. This research could be useful in the analysis of program behavior.