利用權重字尾樹中頻繁事件序改善入侵偵測系統

Exploiting Frequent Episodes in Weighted Suffix Tree to Improve Intrusion Detection System

吳彥慶(Yen-Ching Wu)

指導教授 ： 蔡孟峰

國立中央大學/資訊電機學院/資訊工程學系/碩士(2007年)

摘要

現今電腦的發展越來越普遍，而網際網路的應用也無所不在。在這樣子的環境下，電腦的資訊安全議題也就變得日趨重要；入侵偵測系統 (IDS) 的重要性也因此越來越被重視。
我們著眼於電腦的核心系統呼叫上進行分析，試圖在看似雜亂無章的系統呼叫序列中找出值得參考的資訊，以便建立出有用的規則提升入侵偵測的準確性。字串比對在入侵偵測系統中扮演相當重要的角色，我們設計了一種自字尾樹演算法的概念而衍伸出來的權重字尾樹演算法來進行字串比對。而在大量未明的資料中資料探勘技術可以適時的幫助我們從中得到隱含在其中的資訊，利用頻繁事件序探勘找出具有順序性的頻繁樣本。進而利用這些規則來偵測惡意攻擊。
權重字尾樹演算法可以提升入侵偵測系統 (IDS) 在規則集合選擇上的能力。在此我們強調在我們的方法中我們僅需要掃描全部的紀錄一次，然後我們就可以較以前更簡單的得到不同長度之規則集合。頻繁事件序探勘可以過濾掉那些沒有超過門檻條件較少出現的規則，因此可以提升入侵偵測系統 (IDS) 之決策引擎的運算速度。在本篇論文的最後，我們將指出當我們使用較少的規則時，我們的入侵偵測系統 (IDS) 仍具有不錯的能力偵測入侵。

關鍵字

字串比對 ； 入侵偵測系統 (IDS) ； 關聯式規則 ； 字尾樹 ； 資料探勘

並列摘要

Today the application of computer softwares is getting more popular than before, and the usage of Internet is everyday’s activity. Security issue of computer information has become important in this environment; hence Intrusion Detection System (IDS) deserves more inspection and efforts.
We focus on the analysis of computer kernel system call, and try to find out some meaningful information from the unorganized system call sequences. Then we use the derived information to construct useful rules to improve the accuracy of intrusion detection. String matching plays an important role in the intrusion detection system, and we design a Weighted Suffix Tree algorithm which comes from the concept of suffix tree algorithm for string matching. Data Mining technique could help us finding out meaningful information from large amount of implicit records. Then we exploit Frequent Episodes Mining to get ordered frequent patterns. We therefore apply these rules to detect malicious attacks.
Weighted Suffix Tree algorithm could improve the ability of rule set selection of IDS. We need to emphasize that whole traces only be scanned once in our method. And we could select different length of rule set much easier than before. Frequent Episodes Mining could prune those rare rules that don’t exceed the threshold. Hence the decision engine of IDS could speed up. At the end of this paper, we will show that our IDS still has well ability to detect intrusion when we used fewer rules.

並列關鍵字

String Matching ； Suffix Tree ； Data Mining ； Association Rule ； Intrusion Detection System (IDS)

參考文獻

[IKP95] K. Ilgun, R. A. Kemmerer, P. A. Porras, “State transition analysis: A rule-based intrusion detection approach,” IEEE Transactions on Software Engineering, 1995.

[HFS98] S. A. Hofmeyr, S. Forrest, A. Somayaji, “Intrusion detection using sequences of system calls,” Journal of Computer Security, Volume 6 pages 151-180, 1998.

[FPSS96] U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, “The KDD process of extracting useful knowledge from volumes of data,” Communication of the ACM, 39(11): 27-34, 1996.

[LP05] Tian-rui Li, Wu-ming Pan, “Intrusion Detection System Based on New Association Rule Mining Model,” 2005 IEEE International Conference on Granular Computing, Beijing, China, Volume 2 pages 512-515, 2005.

[AS94] R. Agrawal, A. Swami, “Fast algorithms for mining association rules,” In Proceedings of the 20th VLDB Conference, Santiago, Chile, 1994.