臺灣博碩士論文加值系統

隨著 NIDS (network intrusion detection systems) 還有 NIPS (network intrusion preven- tion systems) 的出現,例如 Bro (BSD license) 還有 Snort (GPL license),在本地端安裝 NIPS/NIDS 不再是夢想。現在,基於更多層的保護能夠提供更深入的安全性,NIPS 被考 量安裝於擁有 Android/Linux 作業系統的行動裝置上。但是在行動裝置上應用 NIPS 之 前,有一些基於行動裝置而存在的問題必須先解決。行動裝置的運算能力比通用型電腦 的運算能力還要不足,因此,合理地分配運算資源顯得格外重要。有一些研究著重在改善 以誤用偵測 (misuse detection) 為基礎的 NIPS 的相關核心演算法,例如樣式比對 (pattern matching) 演算法,以減少 NIPS 整體的時間複雜度。但是無論 NIPS 的核心演算法的時 間複雜度被降低多少,NIPS 的時間複雜度仍然還是比作業系統核心的網路程序的時間複 雜度還要高。如同一句諺語所說:『一條鐵鍊只跟它最弱的一環一樣強。』當 NIPS 被應用 在行動裝置上時,便造成一個封包流動路徑中的瓶頸。因此,這篇研究論文的貢獻著重 在減少此一瓶頸對行動裝置用戶造成的影響。這篇論文的工作首先為確定 Android/Linux 的網路內部與 NIPS 之間的關聯性,並依照此關聯性,使用一個分析性排隊理論模型來 代表流動於此兩物件間的封包流。根據此一分析性排隊理論模型,此論文提出了兩個方 法:基於排隊理論之入侵防禦機制 —靜態資源分配 (QIP-S) 以及其改良版 —動態資源分 配 (QIP-D)。本論文為提出的方法設計了一系列模擬並且分析模擬結果,結果顯示出,當 排隊系統逼近於飽和的狀態時,本論文提出的兩個方法表現優於基於優先權之非搶先分配 方法 (non-preemptive priority based allocation methods) 。

Along with the emergence of open source software of network intrusion detection sys- tems (NIDS) and network intrusion prevention systems (NIPS) like Bro (BSD license) and Snort (GPL license), installing NIPS/NIDS in localhost is not a dream and can be feasible. Now it is considered to apply NIPS on Android/Linux powered mobile devices in the perspec- tive that more layers of protection provides more security. Before applying NIPS on mobile devices, there exist some problems that needs to be solved first. Computational power of mobile devices is less than that of general purpose computers; therefore reasonably allocating computational power appeals to be particularly important. Some researches target at per- fecting the underlying algorithms of misuse-detection-based NIPS such as pattern matching algorithm in order to reduce the time complexity. But no matter how much the complexity of the underlying algorithm is reduced, the job of NIPS still appears to be more complex than that of operating system kernel network routines. As a proverb goes, “A chain is only as strong as its weakest link.” There exists a bottleneck when the NIPS is applied. Therefore, this research does a work that aims at reducing the influences affected by the bottleneck. This work is to firstly identify the relationship between Android/Linux network internals and NIPS, and use an analytical queueing model to represent packet flows between them. Based on the analytical queueing model, a Queueing-based Intrusion Prevention mechanism—Static resource allocation (QIP-S) and its enhancement—Dynamic resource allocation (QIP-D) are proposed. Simulations for the proposed methods are conducted and it shows that it performs well than non-preemptive priority based allocation methods when the state of the queueing system approaches saturation.

Chinese Abstract i
English Abstract ii
Acknowledgement iii
Contents iv
List of Tables vi
List of Figures vii
1 Introduction 1
2 Comparison of Existing Security Technologies 5
3 System Model and Problem Formulation 9
3.1 Queueing Model 9
3.2 Problem Formulation 12
4 Proposed Queueing-Based Intrusion Prevention Mechanisms 15
4.1 ProposedQIP-SScheme 15
4.2 Proposed QIP-D Scheme 17
5 Performance Validation and Comparison 19
5.1 PerformanceValidation 19
5.1.1 AnalyticalFormulavs.SimulationResults19
5.1.2 RealizationofAnalyticalFormula(3.2) 20
5.2 ObservationsonProposedQIP-DProtocol 22
5.2.1 CPUIdlePercentageandComplexityofNIPS 22
5.2.2 InfluenceofMaximumServiceRates 22
5.3 PerformanceComparison 23
5.3.1 IdealServiceTimeDistribution 23
5.3.2 RealisticServiceTimeDistribution 26
6 Conclusions Bibliography27
Bibliography 28

[1] M. Satyanarayanan, “Pervasive Computing: Vision and Challenges,” IEEE Pers. Com- mun. Mag., vol. 8, pp. 10–17, August 2001.
[2] Martin Roesch, “Snort-lightweight intrusion detection for networks,” in USENIX Sys- tems Administration Conference Proceedings, November 1999, pp. 229–238.
[3] Vern Paxson, “Bro : a system for detecting network intruders in real-time,” Computer Networks, vol. 31, pp. 2435–2463, 1999.
[4] Ricardo Koller, Raju Rangaswami, Joseph Marrero, Igor Hernandez, Geoffrey Smith, Mandy Barsilai, Silviu Necula, S. Masoud Sadjadi, Tao Li, and Krista Merrill, “Anatomy of a Real-time Intrusion Prevention System,” in International Conference on Autonomic Computing, June 2008, pp. 151–160.
[5] Zachary K. Baker and Viktor K. Prasanna, “Time and Area Efficient Pattern Matching on FPGAs,” in international symposium on Field programmable gate arrays, February 2004, pp. 223–232.
[6] Chris Clark, Wenke Lee, David Schimmel, Didier Contis, Mohamed Kone, and Ashley Thomas, “A Hardware Platform for Network Intrusion Detection and Prevention,” in Proceedings of Workshop on Network Processors and Applications (NP3), 2004, pp. 136–145.
[7] Zachary K. Baker and Viktor K. Prasanna, “High-throughput Linked-Pattern Matching for Intrusion Detection Systems,” in Symposium on Architecture for networking and communications systems, October 2005, pp. 193–202.
[8] Sarang Dharmapurikar and John Lockwood, “Fast and Scalable Pattern Matching for Content Filtering,” in Symposium on Architecture for networking and communications systems, October 2005, pp. 183–192.
[9] Abhishek Mitra,Walid Najjar and Laxmi Bhuyan, “Compiling PCRE to FPGA for Accel- erating SNORT IDS,” in Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, 2007, pp. 127–136.
[10] Yaron Weinsberg, Shimrit Tzur-David, Danny Dolev and Tal Anker, “One Algorithm to Match Them All: On a Generic NIPS Pattern Matching Algorithm,” in Workshop on High Performance Switching and Routing, June 2007, pp. 1–6.
[11] Young H. Cho and William H. Mangione-Simth, “Deep Network Packet Filter Design for Reconfigurable Devices,” ACM Transactions on Embedded Computing Systems, vol. 7, February 2008.
[12] Robin Sommer, Vern Paxson and Nicholas Weaver, “An architecture for exploiting multi- core processors to parallelize network intrusion prevention,” in Proceedings of the IEEE Sarnoff Symposium, May 2007.
[13] Chun-Ying Huang, Chi-Ming Chen, Shu-Ping Yu, Sheng-Yao Hsu and Chih-Hung Lin, “Accelerate In-Line Packet Processing Using Fast Queue,” in TENCON, 2010, pp. 1048–1052.
[14] K. Salah and A. Kahtani, “Improving Snort performance under Linux,” IET Commu- nications, vol. 3, pp. 1883–1895, December 2009.
[15] Edgar Reich, “Waiting Times When Queues are in Tandem,” Annals of Mathematical Statistics, vol. 28, pp. 768–773, 1957.
[16] S.M.R. Iravani, M.J.M. Posner and J.A. Buzacott, “A two-stage tandem queue attended by a moving server with holding and switching costs,” Queueing Systems, vol. 26, no. 3-4, pp. 203–228, 1997.
[17] Izak Duenyas, Diwakar Gupta and Tava Lennon Olsen, “Control of a Single-Server Tandem Queueing System with Setups,” Operations Research, vol. 46, no. 2, pp. 218–230, Mar. - Apr. 1998.
[18] Werner Sandmann, “Delays in a Series of Queues: Independent versus Identical Service Times,” in IEEE Symposium on Computers and Communications (ISCC), June 2010, pp. 32–37.
[19] Orathai Sukwong, Hyong Kim and James Hoe, “Commercial Antivirus Software Effec- tiveness: An Empirical Study,” Computer, vol. 44, no. 3, pp. 63–70, March 2011.
[20] Deepak Venugopal and Guoning Hu, “Efficient signature based malware detection on mobile devices,” Mobile Information Systems, vol. 4, no. 1, pp. 33–49, 2008.
[21] Liu, Alex X. and Gouda, Mohamed G., “Diverse Firewall Design,” IEEE Transactions on Parallel and Distributed Systems, vol. 19, pp. 1237–1251, September 2008.
[22] Huazhong, Li Zhitang and Wu Junqi, “A Novel Network Intrusion Detection System (NIDS) Based on Signatures Search of Data Mining,” in First International Workshop on Knowledge Discovery and Data Mining, January 2008, pp. 10–16.
[23] P. Garcia-Teodoro, J. Diaz-Verdejo, G. Macia-Fernandez and E. Vazquez, “Anomaly- based Network Intrusion Detection: Techniques, Systems and Challenges,” Computers and Security, vol. 28, pp. 18–28, 2009.
[24] Leland, W.E., Taqqu, M.S., Willinger, W. and Wilson, D.V., “On the self-similar nature of Ethernet traffic (extended version),” IEEE/ACM Transactions on Networking, vol. 2, pp. 1–15, February 1994.
[25] Vern Paxson and Sally Floyd, “Wide area traffic: the failure of Poisson modeling,” IEEE/ACM Transactions on Networking (TON), vol. 3, pp. 226–244, June 1995.
[26] Crovella, M.E. and Bestavros, A., “Self-similarity in World Wide Web traffic: evidence and possible causes,” IEEE/ACM Transactions on Networking, vol. 5, pp. 835–846, December 1997.
[27] Donald Gross, John F. Shortle, James M. Thompson, and Carl M. Harris, Fundamentals of Queueing Theory (Fourth Edition). WILEY, 2008.