A large-scale hidden semi-Markov model for anomaly detection on user browsing behaviors

ABSTRACT

Many methods designed to create defenses against distributed denial of service (DDoS) attacks are focused on the IP and TCP layers instead of the high layer. They are not suitable for handling the new type of attack which is based on the application layer. In this paper, we introduce a new scheme to achieve early attack detection and filtering for the application-layer-based DDoS attack. An extended hidden semi-Markov model is proposed to describe the browsing behaviors of web surfers. In order to reduce the computational amount introduced by the model's large state space, a novel forward algorithm is derived for the online implementation of the model based on the M-algorithm. Entropy of the user's HTTP request sequence fitting to the model is used as a criterion to measure the user's normality. Finally, experiments are conducted to validate our model and algorithm.

REFERENCES

• 1: Christos Douligeris , Aikaterini Mitrokotsa, DDoS attacks and defense mechanisms: classification and state-of-the-art, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.5, p.643-666, 5 April 2004 [doi>10.1016/j.comnet.2003.10.003]
• 2: Jelena Mirkovic , Gregory Prier , Peter L. Reiher, Attacking DDoS at the Source, Proceedings of the 10th IEEE International Conference on Network Protocols, p.312-321, November 12-15, 2002
• 3: Cheng Jin , Haining Wang , Kang G. Shin, Hop-count filtering: an effective defense against spoofed DDoS traffic, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948116]
• 4: T. Peng, K. R. mohanarao, and C. Leckie, "Protection from distributed denial of service attacks using history-based IP filtering," in Proc. IEEE Int. Conf. Communications, May 2003, vol. 1, pp. 482-486.
• 5: J. B. D. Cabrera et al., "Proactive detection of distributed denial of service attacks using MIB traffic variables a feasibility study," in Proc. IEEE/IFIP Int. Symp. Integrated Network Management, May 2001, pp. 609-622.
• 6: L. Limwiwatkul and A. Rungsawangr, "Distributed denial of service detection using TCP/IP header and traffic measurement analysis," in Int. Symp. Communications and Information Technologies 2004 (ISCIT 2004), Sappom, Japan, Oct. 29, 2004.
• 7: S. Noh, C. Lee, K. Choi, and G. Jung, "Detecting distributed denial of service (DDoS) attacks through inductive learning," Lecture Notes in Computer Science, vol. 2690, pp. 286-295, 2003.
• 8: R. Basu, K. R. Cunningham, S. E. webster, and P. R. Lippmann, "Detecting low-profile probes and novel denial of service attacks," in Proc. 2001 IEEE Workshop on Information Assurance and Security, Jun. 2001, pp. 5-10.
• 9: S. Ranjan, R. Swaminathan, M. Uysal, and E. Knightly, "DDoS-resilient scheduling to counter application layer attacks under imperfect detection," in Proc. IEEE INFOCOM, Apr. 2006 [Online]. Available: http://www-ece.rice.edu/~networks/papers/dos-sched.pdf
• 10: S. Kandula, D. Katabi, M. Jacob, and A. W. Berger, Botz-4-Sale: Surviving organized DDoS attacks that mimic flash crowds Mass. Inst. Technol., Tech. Report TR-969, 2004 [Online]. Available: http://www. usenix.org/events/nsdi05/tech/kandula/kandula.pdf
• 11: R. K. C. Chang, "Defending against flooding-based distributed denial-of-service attacks: A tutorial," IEEE Commun. Mag., pp. 43-51, Oct. 2002.
• 12: MyDoom virus. [Online]. Available: http://www.us-cert.gov/cas/ techalerts/TA04-028A.html
• 13: S.-Z. Yu and H. Kobayashi, "An efficient forward-backward algorithm for an explicit duration hidden Markov model," IEEE Signal Process. Lett., vol. 10, no. 1, pp. 11-14, Jan. 2003.
• 14: Shun-Zheng Yu , Zhen Liu , M. S. Squillante , Cathy Xia , Li Zhang, A hidden semi-Markov model for web workload self-similarity, Proceedings of the Performance, Computing, and Communications Conference, 2002. on 21st IEEE International, p.65-72, April 03-05, 2002 [doi>10.1109/IPCCC.2002.995137]
• 15: J. B. Anderson and S. Mohan, "Sequential coding algorithms: A survey and cost analysis," IEEE Trans. Commun., vol. COM-32, pp. 169-176, Feb. 1984.
• 16: G. Mori and J. Malik, "Recognizing objects in adversarial clutter: Breaking a visual captcha," in Proc. IEEE Computer Society Conf. Computer Vision and Pattern Recognition, Jun. 2003, vol. 1, pp. 134-141.
• 17: Jaeyeon Jung , Balachander Krishnamurthy , Michael Rabinovich, Flash crowds and denial of service attacks: characterization and implications for CDNs and web sites, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511485]
• 18: Susanne Burklen , Pedro Jose Marron , Serena Fritsch , Kurt Rothermel, User Centric Walk: An Integrated Approach for Modeling the Browsing Behavior of Users on the Web, Proceedings of the 38th annual Symposium on Simulation, p.149-159, April 04-06, 2005 [doi>10.1109/ANSS.2005.44]
• 19: Juan Velásquez , Hiroshi Yasuda , Terumasa Aoki, Combining the web content and usage mining to understand the visitor behavior in a web site, Proceedings of the Third IEEE International Conference on Data Mining, p.669, November 19-22, 2003
• 20: Devanshu Dhyani , Sourav S. Bhowmick , Wee-Keong Ng, Modelling and Predicting Web Page Accesses Using Markov Processes, Proceedings of the 14th International Workshop on Database and Expert Systems Applications, p.332, September 01-05, 2003
• 21: X. D. Hoang, J. Hu, and P. Bertok, "A multi-layer model for anomaly intrusion detection using program sequences of system calls," in Proc. 11th IEEE Int. Conf. Networks, Oct. 2003, pp. 531-536.
• 22: Mehmed Kantardzic, Data Mining: Concepts, Models, Methods and Algorithms, John Wiley & Sons, Inc., New York, NY, 2002
• 23: J. Cao, W. S. Cleveland, Y. Gao, K. Jeffay, F. D. Smith, and M. Weigle, "Stochastic models for generating synthetic HTTP source traffic," in Proc. IEEE INFOCOM 2004, vol. 3, pp. 1546-1557.
• 24: A. Sarika, A. Saumya, and G. Bryon, "DDoS attack simulation, monitoring, and analysis," CS 590D: Security Topics in Networking and Distributed Systems Final Project Report, Apr. 29, 2004, Purdue University, West Lafayette, IN. [Online.] Available: http://www.cs.purdue. edu/homes/bgloden/DDoS_Attack_Simulation.pdf.
• 25: K. Jiejun et al., "Random flow network modeling and simulations for DDoS attack mitigation," in Proc. IEEE Int. Conf. Communications (ICC '03), May 2003, vol. 1, pp. 487-491.
• 26: X. Yi and Y. Shunzheng, "A dynamic anomaly detection model for web user behavior based on HsMM," in Proc. 10th Int. Conf. Computer Supported Cooperative Work in Design (CSCWD 2006), Nanjing, China, May 2006, vol. 2, pp. 811-816.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Information browsers
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.4 Hypertext/Hypermedia
          Subjects: Navigation

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Human Factors, Security, Theory

Keywords:
DDoS, M-algorithm, anomaly detection, browsing behaviors, hidden semi-Markov model