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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：47

、訪客IP：52.14.130.13

姓名

吳彥慶(Yen-Ching Wu) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

利用權重字尾樹中頻繁事件序改善入侵偵測系統
(Exploiting Frequent Episodes in Weighted Suffix Tree to Improve Intrusion Detection System)

相關論文

★ 應用自組織映射圖網路及倒傳遞網路於探勘通信資料庫之潛在用戶	★ 基於社群網路特徵之企業電子郵件分類
★ 行動網路用戶時序行為分析	★ 社群網路中多階層影響力傳播探勘之研究
★ 以點對點技術為基礎之整合性資訊管理及分析系統	★ 在分散式雲端平台上對不同巨量天文應用之資料區域性適用策略研究
★ 應用資料倉儲技術探索點對點網路環境知識之研究	★ 從交易資料庫中以自我推導方式探勘具有多層次FP-tree
★ 建構儲存體容量被動遷徙政策於生命週期管理系統之研究	★ 應用服務探勘於發現複合服務之研究
★ 有效率的處理在資料倉儲上連續的聚合查詢	★ 入侵偵測系統：使用以函數為基礎的系統呼叫序列
★ 有效率的在資料方體上進行多維度及多層次的關聯規則探勘	★ 在網路學習上的社群關聯及權重之課程建議
★ 在社群網路服務中找出不活躍的使用者	★ 利用階層式權重字尾樹找出在天文觀測紀錄中變化相似的序列

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

現今電腦的發展越來越普遍，而網際網路的應用也無所不在。在這樣子的環境下，電腦的資訊安全議題也就變得日趨重要；入侵偵測系統 (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.

關鍵字(中)

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

關鍵字(英)

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

論文目次

Chinese Abstract……………………………………………… i
English Abstract……………………………………………… ii
Table of Contents …………………………………………… iv
List of Figures…………………………………………………vi
List of Tables ……………………………………………… viii
Chapter 1 Introduction ……………………………………… 1
1-1 Motivation……………………………………………………………… 4
1-2 Overview of this desertation………………………………………………7
Chapter 2 Related Work……………………………………… 8
Chapter 3 Background and Problem Definition……………… 9
3-1 String Matching……………………………………………………………9
3-2 Suffix Tree…………………………………………………………………11
3-3 Data Mining………………………………………………………………12
3-4 Association Rules…………………………………………………………13
3-5 Frequent Episodes…………………………………………………………15
3-6 Problem Definition…………………………………………………………16
Chapter 4 Methodology …………………………………… 19
4-1 Architecture………………………………………………………………19
4-2 Weighted Suffix Tree………………………………………………………21
4-3 Frequent Episodes Mining…………………………………………………38
4-4 Intrusion Detection Model…………………………………………………43
Chapter 5 Experiments……………………………………… 46
5-1 Comparison of Execution Time during Rules Checking………………… 47
5-2 Experiment Results………………………………………………………49
Chapter 6 Conclusions……………………………………… 54
Chapter 7 Acknowledgments ……………………………… 56
Reference…………………………………………………… 57
Appendix A……………………………………………………63

參考文獻

[HLMS90] R. Heady, G. Luger, A. Maccabe, M. Servilla, “The architecture of a network level intrusion detection system,” Technical report, Computer Science Department, University of New Mexico, August 1990.
[HBV03] Mahmood Hossain, Susan M. Bridges, Rayford B. Vaughn, “Adaptive Intrusion Detection with Data Mining,” In Proceedings of IEEE International Conference on Systems, Man and Cybernetics, 2003.
[KS95] S. Kumar, E. H. Spafford, “A software architecture to support misuse intrusion detection,” In Proceedings of the 18th National Information Security Conference, pages 194-204, 1995.
[IKP95] K. Ilgun, R. A. Kemmerer, P. A. Porras, “State transition analysis: A rule-based intrusion detection approach,” IEEE Transactions on Software Engineering, 1995.
[LTG+92] T. Lunt, A. Tamaru, F. Gilham, R. Jagannathan, P. Neumann, H. Javitz, A. Valdes, T. Garvey, ”A real-time intrusion detection expert system (IDES) – final technical report,” Technical report, Computer Science Laboratory, SRI International, Menlo Park, California, 1992.
[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.
[LS98] Wenke Lee, Salvatore J. Stolfo, “Data Mining Approaches for Intrusion Detection,” In Proceedings of the 7th USENIX Security Symposium, San Antonio, Texas, January 26-29, 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.
[XG04] Man-Jiang Xu, Gang Gu, “Method and Usage of Mining Association Rules in System Call Serial,” In the 4th Computer Systems & Applications 2004, 2004.
[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.
[LSC97] Wenke Lee, Salvatore J. Stolfo, Philip K. Chan, “Learning patterns from unix process execution traces for intrusion detection,” In AAAI Workshop: AI Approaches to Fraud Detection and Risk Management, pages 50-56, AAAI Press, July 1997.
[LSM99] Wenke Lee, Salvatore J. Stolfo, Kui W. Mok, “A Data Mining Framework for Building Intrusion Detection Model,” In Proceedings of the 1999 IEEE Symposium on Security and Privacy, Oakland, CA, May 1999.
[Lee99] Wenke Lee, “A Data Mining Framework for Constructing Features and Model for Intrusion Detection System,” Ph.D Dissertations, Columbia University, New York, USA 1999.
[LS00] Wenke Lee, Salvatore J. Stolfo, “A framework for constructing features and models for intrusion detection systems,” ACM Transactions on Information and System Security, Volume 3, Number 4, 2000.
[SLCFE01] Salvatore J. Stolfo, Wenke Lee, Philip K. Chan, Wei Fan, Eleazar Eskin, “Special section on data mining for intrusion detection and threat analysis: Data mining-based intrusion detectors: an overview of the columbia IDS project,” ACM SIGMOD Record, Volume 30 No 4, December 2001.
[WHX06] Xuren Wang, Famei He, Rongsheng Xu, “Modeling Intrusion Detection System by Discovering Association Rule in Rough Set Theory Framework,” In Proceedings of IEEE International Conference on Computational Intelligence for Modeling Control and Automation, and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), page 24, 2006.
[KFH05] Dae-Ki Kang, Doug Fuller, Vasant Honavar, ”Learning Classifiers for Misuse Detection Using a Bag of System Calls Representation,” In Proceedings of IEEE International Conference on Intelligence and Security Informatics (ISI-2005), Atlanta, GA, USA, May 19-20, 2005; Lecture Notes in Computer Science, Vol. 3495, pages 511-516, 2005.
[LBM05] Chang-Tien Lu, Arnold P. Boedihardjo, Prajwal Manalwar, “Exploiting Efficient Data Mining Techniques to Enhance Intrusion Detection Systems,” In Proceedings of IEEE International Conference on Information Reuse and Integration, pages 512-517, Las Vegas, Nevada, 2005.
[YA04] M. M. Yasin, Awais A. Awan, ”A study of host-based IDS using system calls,” In IEEE International Conference on Networking and Communication, 2004.
[BK03] Yuebin Bai, Hidetsune Kobayashi, “Intrusion Detection Systems: Technology and Development,” In Proceedings of the 17th IEEE International Conference on Advanced Information Networking and Applications (AINA’03), 2003.
[KMP77] Donald E. Knuth, James H. Morris Jr., Vaughan R. Pratt, ”Fast pattern matching in strings,” SIAM Journal on Computing, 6(2): 323-350, 1977.
[KR81] Richard M. Karp, Michael O. Rabin, “Efficient randomized pattern-matching algorithms,” Technical Report TR-31-81, Aiken Computation Laboratory, Harvard University, 1981.
[BM77] Robert S. Boyer, J. Strother Moore, “A fast string-searching algorithm,” Communications of the ACM, 20(10): 762-772, 1977.
[Wei73] P. Weiner, “Linear pattern matching algorithm,” In 14th Annual IEEE Symposium on Switching and Automata Theory, pages 1-11, 1973.
[McC76] Edward M. McCreight, “A Space-Economical Suffix Tree Construction Algorithm,” Journal of ACM 23, pages 262-272, 1976.
[Ukk95] Esko Ukkonen, “On-line construction of suffix trees,” Algorithmica, I4:249-60, 1995.
[AIS93] R.Agrawal, T. Imielinski, A. Swami, “Mining association rules between sets of items in large databases,” In Proceedings of the SIGMOD Conference on Management of Data, pages 207-216, Washington, D.C., 1993.
[SA95] R. Srikant, R. Agrawal, “Mining generalized association rules,” In Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1995.
[MTV95] H. Mannila, H. Toivonen, A. I. Verkamo, “Discovering frequent episodes in sequences,” In Proceedings of the 1st International Conference on Knowledge Discovery in Databases and Data Mining, Montreal, Canada, 1995.
[KFL94] C. Ko, G. Fink, K. Levitt, “Automated detection of vulnerabilities in privileged programs by execution monitoring,” In Proceedings of the 10th Annual Computer Security Applications Conference, pages 134-144, December 1994.
[FHSL96] S. Forrest, S. A. Hofmeyr, A. Somayaji, T. A. Longstaff, “A Sense of Self for Unix Processes,” In Proceedings of the 1996 IEEE Symposium on Security and Privacy, pages 120-128, Los Alamitos, 1996.
[WFP99] Christina Warrender, Stephanie Forrest, Barak Pearlmutter, “Detecting Intrusion Using System Calls: Alternative Data Models,” 1999 IEEE Symposium on Security and Privacy, 1999.

指導教授

蔡孟峰(Meng-Feng Tsai)

審核日期

2007-7-18

推文