由入侵偵測系統所產生出來的警報序列，除了能紀錄到惡意的行為外，也會夾雜許多的誤報。而大量的背景雜訊會增加管理者的負擔以及潛在的風險。除此之外，隨著環境、時間的不同，亦會產生出不同的背景雜訊。在這篇論文中，我們提出一個透過統計模型量測序列之間的不相似度，以偵測惡意行為的方法。
我們的論文中，主要是在警報序列的萃取，以及序列之間的不相似度量測。首先，警報序列會先透過時間和主機位置的資料進行萃取；再利用統計模型描述對應到的序列並量測兩兩序列之間的不相似度。我們則是做用了馬克夫鏈模型，以及隱藏式馬克夫模型。馬克夫鏈模型可以直接的描述警報間觸發的因果關係，而隱藏式馬克夫模型則是試圖去描述狀態之間的變化，也就是警報觸發的背後意圖之間的因果關係。最後再利用流形學習的方式計算出這些序列在新的維度空間的座標，並進行分類。
我們提出的架構有以下幾點貢獻：(1) 提出一個量測事件序列之間不相似度的新方法。 (2) 以一個真實世界的資料來驗證我們的方法。 (3) 將事件序列形象化在低維度空間中，讓使用者可以容易的去判別序列中是否含有惡意行為。

The sequence of alerts generated by Network Intrusion Detection System (NIDS) contains malicious behavior come with a lot of false alarms (back-ground noise). A large proportion of background noise increases the cost of inspection from network administrator and raises the potential risks. In additional, the background noise is different in different time and environment. In this thesis, we propose a framework that measures the dissimilarity between alert sequences via statistic model for detection the malicious behavior.

Our studying is focus on alert sequence extraction and pair-wise dissimilarity measurement. Firstly, the alert sequences are extracted according to the specified time-interval and IP (source and target) information. Then, we use the statistic model to describe each alert sequence for measure the dissimilarity. We employ the Markov chain model (MCM) and Hidden Markov model (HMM) to profile the extracted alert sequences. MCM can describe the causal relation among alert types directly. In addition, HMM is capable to describe the causal relation among states that behind the observation, and alerts’ trigger is depend on the state ordering. Finally, the manifold learning is used to compute the coordinate of instances in a new dimensional space for any effective classification methods to detect the malicious behavior.

The proposed framework makes the following contributions: (a) propose a novel dissimilarity measure for event sequences; (b) justified by real case study; and (c) provide visualization for easily understanding the properties of different malicious or normal behavior of event sequences. We evaluated our framework on mainly two sequential alert datasets, DARPA99 and Acer07, a public dataset and a private dataset gathered from a Security Operation Center respectively. Series of experiments have been designed for evaluation of our proposed framework, including (1) the comparison of different profiling methods, (2) the effectiveness in intrusion detection and (3) compare the performance with characteristics' method.

[1] DARPA intrusion detection evaluation. In http://www.ll.mit.edu/mission/ communications/ist/corpora/ideval/index.html.
[2] Rakesh Agrawal, Tomasz Imielinski, and Arun Swami. Database mining: a performance perspective. IEEE Trans. on Knowledge and Data Engineering, 5(6):914–925, 1993.
[3] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (2nd Ed.). Wiley-Interscience, July 2006.
[4] O. Dain and R. Cunningham. Fusing heterogeneous alert streams into scenarios. In Proceedings of the 2001 ACM workshop on Data Mining for Security Applications, pages 1–12, December 2001.
[5] D. Donoho and C. Grimes. Hessian eigenmaps: locally linear embedding techniques for high-dimensional data. In Proceedings of the National Academy of Sciences, pages 5591–5596, 2003.
[6] K. Julisch. Clustering intrusion detection alarms to support root cause analysis. ACM Trans. Inf. Sys. Secur., 6(4):443–471, November 2003.
[7] Eamonn Keogh, Stefano Lonardi, and Chotirat Ann Ratanamahatana. Towards parameter-free data mining. In KDD ’04: Proc. of the 10th ACM SIGKDD inter. conf. on Knowledge discovery and data mining, pages 206–215, 2004.
[8] Martin H. C. Law, Nan Zhang 0002, and Anil K. Jain. Nonlinear manifold learning for data stream. In SDM, 2004.
[9] V. I. LEVENSHTEIN. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10:707–710, 1966.
[10] M. Li, J. H. Badger, X. Chen, S. Kwong, P. Kearney, and H. Zhang. An information-based sequence distance and its application to whole mitochondrial genome phylogeny. Bioinformatics, 17(2):149–154, 2001.
[11] M. Li and P. Vit′anyi. An Introduction to Kolmogorov Complexity and Its Applications (2nd Ed.). Springer, New York, 1997.
[12] Jessica Lin, Eamonn Keogh, Stefano Lonardi, and Bill Chiu. A symbolic representation of time series, with implications for streaming algorithms. In Proc. of the 8th ACM SIGMOD Workshop on Res. Issues in Data Mining and Knowledge Discovery, pages 2–11, 2003.
[13] H. Mannila, H. Toivonen, and A. I. Verkamo. Discovering Frequent Episodes in Sequences. In Proc. of the 1st Inter, Conf. on Knowledge Discovery and Data Mining, Montreal, Canada, 1995. AAAI Press.
[14] P. Ning, Y. Cui, D.S. Reeves, and D. Xu. Techniques and tools for analyzing intrusion alerts. ACM Trans. Inf. Sys. Secur., 7(2):274–318, May 2004.
[15] Hsing-Kuo Pao and John Case. Computing entropy for ortholog detection. In International Conference on Computational Intelligence, pages 89–92, 2004.
[16] Lawrence R. Rabiner. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE,77(2):257–87, 1989.
[17] O. Sheyner, J. Haines, S. Jha, R. Lippmann, and J. M. Wing. Automated generation and analysis of attack graphs. In Proceedings of the 2002 IEEE Symposium on Security and Privacy, pages 273–284, May 2002.
[18] J. B. Tenenbaum, V. D. Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. SCIENCE, 290(5500):2319–2323, December 2000.
[19] A. Valdes and K. Skinner. Probabilistic alert correlation. In Lecture Notes in Computer Science, pages 54–68, 2001.
[20] B. Zhu and A. A. Ghorbani. Alert correlation for extracting attack strategies. International Journal of Network Security, 3(3):244–258, November 2006.