臺灣博碩士論文加值系統

在現今的社會裡，網路的使用已經是很普遍的。然而，隨著網路的不斷發展，
我們所要承受的潛在危險也隨之增加。因此，我們需要利用一些機制來避免
遭遇到這些攻擊。入侵偵測系統-通常用來偵測電腦網路系統是否遭受到異
常的行為，一旦發現便會立即對系統管理者發出警訊。在本論文中，我們提
出了利用時間依存度來建立一個有效的入侵偵測系統。除此之外，我們還利
用半監督式學習的概念來調整我們的模組參數。然而，為了考慮資料的時間
性關係，我們利用隱藏式馬可夫模型的特性來實作我們的模組。由於隱藏式
馬可夫模型並不適用於處理多維度的資料。所以，我們結合簡易貝氏分類器
的特性來解決這個問題。此外，我們利用高階隱藏式馬可夫模型以及混合模
型(支撐向量機+滑動式視窗)來考慮更多的時間依存關係。從結果中，我們
可以看到提高時間依存度能有效的幫助我們提高偵測率。最後，我們再利用
半監督式學習的概念來調整我們的模組參數。藉由這樣的概念，我們便能針
對各式各樣的環境建立一個有效的入侵偵測系統。

In society nowadays, the use of Internet becomes more prevalent. However,
as the Internet developed, it also has a growing number of potential risks.
We need some mechanisms to help us protecting our systems from these
risks. An Intrusion Detection System (IDS) is generally used to detect
anomalous behaviors and give system administrators alarms if it detects
suspicious behaviors.
We design an intrusion detection system by considering temporal
relationships among them, and then use semi-supervised learning with
EM algorithm to update our model. To consider temporal relationships
among data, we use a Hidden Markov Model (HMM). To deal with high
dimensional data, so we combine HMM with Naive Bayes. Also, to consider
temporal interaction of order higher than one, we adopt high-order
Markov model and the detection result shows us better performance than
the result from one-order Markov model. On the other hand, we use the
result of support vector machine with temporal consideration to compare
with our experiment result. By the results, we can observe that the temporal
relationships can really help us to achieve higher detection accuracy.
Finally, as an adaptive version of our model, we use semi-supervised learning
with EM algorithm to tune our parameters. By this way, we can train
a model which can fit to the real environment with adaptive manner.

1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Our Main Work . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Organization of Thesis . . . . . . . . . . . . . . . . . . . . 5
2 Intrusion Detection Systems 6
2.1 Overview of Intrusion Detection Systems . . . . . . . . . . 6
2.2 Categories of Attacks . . . . . . . . . . . . . . . . . . . . . 7
2.3 Category of Intrusion Detection Systems . . . . . . . . . . 10
2.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . 14
3 HMM, Naive Bayes, and Graphical Model Formulations 16
3.1 Hidden Markov Model . . . . . . . . . . . . . . . . . . . . 16
3.1.1 Viterbi Algorithm . . . . . . . . . . . . . . . . . . . 19
3.1.2 Forward and Backward Algorithms . . . . . . . . . 21
3.1.3 Baum-Welch Algorithm . . . . . . . . . . . . . . . 25
3.2 Naive Bayes . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 Introduction to Naive Bayes . . . . . . . . . . . . . 30
3.2.2 Parameter Estimated for Naive Bayes . . . . . . . . 31
3.3 Hybrid Naive Bayes Hidden Markov Model . . . . . . . . . 32
3.3.1 Extended Baum-Welch Algorithm . . . . . . . . . . 33
3.4 High-Order Hidden Markov Model (HO-HMM) . . . . . . 35
3.5 SVM and SVM with temporal relationship . . . . . . . . . 37
4 Experimental Work 40
4.1 Description for The KDD’99 Dataset . . . . . . . . . . . . 40
4.2 Data Preprocessing . . . . . . . . . . . . . . . . . . . . . . 43
4.3 Experiment Results and Discussions . . . . . . . . . . . . . 46
5 Conclusion and Future Work 55
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 56

[1] http://www.cert.org/stats/fullstats.html.
[2] http://www.securityfocus.com/infocus/1514.
[3] http://www.ll.mit.edu/mission/communications/ist/corpora/ideval/
docs/attackDB.html.
[4] http://setminuswww.symantec.com/region/tw/enterprise/article/
why intrusion detection.html.
[5] http://www.symantec.com/region/tw/enterprise/article/intrusion
detection.html.
[6] http://kdd.ics.uci.edu//databases/kddcup99/kddcup99.html.
[7] http://kdd.ics.uci.edu/databases/kddcup99/task.html.
[8] N. Abouzakhar, A. Gani, G. Manson, M. Abuitbel, and D. King.
Bayesian learning networks approach to cybercrime detection. Post-
Graduate Networking Conference, 2003.
[9] N.B. Amor, S. Benferhat, and Z. Eliuedi. Naive bayes vs decision
trees in intrusion detection systems. Proceedings of the 2004 ACM
symposium ib Applied computing, pages 420–424, 2004.
[10] J.P. Anderson. Computer Security Threat Monitoring and Surveil-
lance. James P Anderson Co., April 1980.
[11] L.E. Baum. A maximization technique occurring in the statistical
analysis of probabilistic functions of markov chains. The Annals of
Mathematical Statistics, 41(1):164–171, 1970.
[12] L.E. Baum. An inequality and associated maximization technique in
statistical estimation for probabilistic functions of markov processes.
In In:Oved SHISHA, ed. Inequalities III: Proceedings of the Third
Symposium on Inequalities, volume 41, pages 1–8, 1972.
[13] L.E. Baum and J.A. EAGON. An inequality with applications to
statistical estimation for probabilistic functions of a markov process
and to a model for ecology. Bulletin of the American Mathematical
Society, 73:360–363, 1967.
[14] L.E. Baum and T. Petrie. Statistical inference for probabilistic functions
of finite state markov chains. The Annals of Mathematical
Statistics, 37(6):1554–1563, 1966.
[15] J. Boreczky and L. Wilcox. A hidden markov model framework for
video segmentation using audio an image features. In Proc. IEEE
ICASSP, 1998.
[16] C.J.C. Burges. A tutorial on support vector machines for pattern
recognition. Data Mining and Knowledge Discovery, 2:121–167, 1998.
[17] C.C. Chang. Smooth support vector machine for multi-class classification.
Master’s thesis, National Taiwan University of science and
Technology, 2007.
[18] C. Cortes and V. Vapnik. Support vector networks. Machine Learn-
ing, 20:273–297, 1995.
[19] D.E. Denning. A intrusion detection model. IEEE Transactions on
Software Engineer, SE-13(2):222–232, 1987.
[20] D. Durbin, S. Eddy, A. Krogh, and G.Mitchison. Biological sequence
analysis. The press syndicate of the university of Cambridge, 1998.
[21] P. Frasconi, G. Soda, and A. Vullo. Text categorization for multipage
documents: A hybrid naive bayes hmm approach. Proceeding
of the 1st ACM/IEEE-CS joint conference on Digital libraries, pages
11–20, 2001.
[22] L.T. Heberlein, G.V. Dias, K.N. Levitt, B. Mukherjee, J. Wood, and
D. Wolber. A network security monitor. Proc. Symp.on Research in
Security and Privacy, IEEE Computer Society Press, pages 296–304,
1990.
[23] Y.S. Hsu. A hybrid ids framework via decision trees and svms. Master’s
thesis, National Taiwan University of science and Technology,
2007.
[24] T.S. Hwang. A three-tier ids via data mining approach. Master’s
thesis, National Taiwan University of science and Technology, 2007.
[25] K. Karplus, C. Barrett, and R. Hughey. Hidden markov models for
detecting remote protein homologies. Bioinformatics, 14:846–856,
1998.
[26] K. Kendall. A database of computer attacks for the evaluation of
intrusion detection systems. Master’s thesis, Massachusetts Institute
of Technology, Dept. of Electrical Engineering and Computer Science,
1999.
[27] R. Lippmann, D. Fried, I. Graf, J. Haines, K. Kendall, D. McClung,
D. Weber, S. Webster, D. Wyschogrod, R. Cunningham, and M. Zissman.
Evaluating intrusion detection systems: The 1998 DARPA offline
intrusion detection evaluation. In Proceedings of the DARPA
Information Survivability Conference and Exposition, Los Alamitos,
CA, 2000. IEEE Computer Society Press.
[28] R. Lippmann, J. Haines, D. Fried, J. Korba, and K. Das. Analysis
and results of the 1999 darpa off-line intrusion detection evaluation.
In RAID ’00: Proceedings of the Third International Workshop on
Recent Advances in Intrusion Detection, pages 162–182, London, UK,
2000. Springer-Verlag.
[29] R. Mag, K. Wong, and F. Fallside. Script recognition using hidden
markov models. Acoustics, Speech, and Signal Processing, IEEE In-
ternational Conference on ICASSP ’86, 11:2071–2074, 2003.
[30] T. Mitchell. Machine Learning. McGraw-Hill Companies,Inc, 1997.
[31] E.M. Nel, J.A. du Preez, and B.M. Herbst. Estimating the pen trajectories
of static signatures using hidden markov models. IEEE Trans-
actions on Pattern Analysis and Machine Intelligence, 27:1733–1746,
2005.
[32] L.R. Rabiner. A tutorial on hidden markov models and selected applications
in speech recognition. Proceedings of the IEEE, 77(2):257–286,
1989.
[33] M. Sabhnani and G. Serpen. An application of machine learning
algorithms to KDD intrusion detection dataset within misuse detection
context. In Proceedings of the International Conference on
Machine Learning, Models, Technologies and Applications (MLMTA
2003), pages 209–215, 2003.
[34] C.Y. Suen, C.C. Tappert, and T. Wakahara. The state of the art
in on-line handwriting recognition. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 8:787–808, 1990.