Learning to control a structured-prediction decoder for detection of HTTP-layer DDoS attackers. (English) Zbl 1386.68128

Summary: We focus on the problem of detecting clients that attempt to exhaust server resources by flooding a service with protocol-compliant HTTP requests. Attacks are usually coordinated by an entity that controls many clients. Modeling the application as a structured-prediction problem allows the prediction model to jointly classify a multitude of clients based on their cohesion of otherwise inconspicuous features. Since the resulting output space is too vast to search exhaustively, we employ greedy search and techniques in which a parametric controller guides the search. We apply a known method that sequentially learns the controller and the structured-prediction model. We then derive an online policy-gradient method that finds the parameters of the controller and of the structured-prediction model in a joint optimization problem; we obtain a convergence guarantee for the latter method. We evaluate and compare the various methods based on a large collection of traffic data of a web-hosting service.


68T05 Learning and adaptive systems in artificial intelligence
62M20 Inference from stochastic processes and prediction
68M11 Internet topics


HMMPayl; HC-search
Full Text: DOI


[1] Amza, C., Cecchet, E., Chanda, A., Cox, A., Elnikety, S., Gil, R., Marguerite, J., Rajamani, K., & Zwaenepoel, W. (2002). Bottleneck characterization of dynamic web site benchmarks. Technical report TR-02-391, Rice University.
[2] Ariu, D; Tronci, R; Giacinto, G, Hmmpayl: an intrusion detection system based on hidden Markov models, Computers & Security, 30, 221-241, (2011)
[3] Borka, V. S. (2008). Stochastic approximation: A dynamical systems viewpoint. Cambridge: Cambridge University Press.
[4] Borkar, VS; Meyn, SP, The ODE method for convergence of stochastic approximation and reinforcement learning, SIAM Journal on Control and Optimization, 38, 447-469, (2000) · Zbl 0990.62071
[5] Doppa, JR; Fern, A; Tadepalli, P, HC-search: learning heuristics and cost functions for structured prediction, AAAI, 2, 4, (2013)
[6] Doppa, J. R., Fern, A., & Tadepalli, P. (2014a). HC-search: A learning framework for search-based structured prediction. Journal of Artificial Intelligence Research, 50(1), 369-407. · Zbl 1367.68263
[7] Doppa, J. R., Fern, A., & Tadepalli, P. (2014b). Structured prediction via output space search. The Journal of Machine Learning Research, 15(1), 1317-1350. · Zbl 1318.68140
[8] Düssel, P., Gehl, C., Laskov, P., & Rieck, K. (2008). Incorporation of application layer protocol syntax into anomaly detection. In International Conference on Information Systems Security, pages 188-202. Springer.
[9] Finley, T., & Joachims, T. (2008). Training structural SVMs when exact inference is intractable. In Proceedings of the International Conference on Machine Learning.
[10] Gharibian, F., & Ghorbani, A. A., (2007). Comparative study of supervised machine learning techniques for intrusion detection. In IEEE Annual Conference on Communication Networks and Services Research, pages 350-358.
[11] Görnitz, N; Kloft, M; Rieck, K; Brefeld, U, Toward supervised anomaly detection, Journal of Artificial Intelligence Research, 46, 235-262, (2013) · Zbl 1259.68170
[12] Greensmith, E; Bartlett, PL; Baxter, J, Variance reduction techniques for gradient estimates in reinforcement learning, The Journal of Machine Learning Research, 5, 1471-1530, (2004) · Zbl 1222.68207
[13] Hazan, T., & Urtasun. R. (2010). Approximated structured prediction for learning large scale graphical models. arxiv:1006.2899.
[14] Khan, L; Awad, M; Thuraisingham, B, A new intrusion detection system using support vector machines and hierarchical clustering, International Journal on Very Large Databases, 16, 507-521, (2007)
[15] Kloft, M; Laskov, P, Security analysis of online centroid anomaly detection, Journal of Machine Learning Research, 13, 3681-3724, (2012) · Zbl 1433.68357
[16] Koc, L; Mazzuchi, TA; Sarkani, S, A network intrusion detection system based on a hidden naïve Bayes multiclass classifier, Expert Systems with Applications, 39, 13492-13500, (2012)
[17] Lafferty, J., McCallum, A., & Pereira, F. (2001). Conditional random fields: probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning.
[18] Liu, H., & Chang, K. (2011). Defending systems against tilt DDoS attacks. In Proceedings of the International Conference on Telecommunication Systems, Services, and Applications.
[19] Li, Y; Xia, J; Zhang, S; Yan, J; Ai, X; Dai, K, An efficient intrusion detection system based on support vector machines and gradually feature removal method, Expert Systems with Applications, 39, 424-430, (2012)
[20] Mc Dowell, LK; Gupta, KM; Aha, DW, Cautious collective classification, The Journal of Machine Learning Research, 10, 2777-2836, (2009) · Zbl 1235.68175
[21] Neville, J., & Jensen, D. (2000). Iterative classification in relational data. In Proc. AAAI-2000 Workshop on Learning Statistical Models from Relational Data.
[22] Peddabachigari, S; Abraham, A; Grosan, C; Thomas, J, Modeling intrusion detection system using hybrid intelligent systems, Journal of Network and Computer Applications, 30, 114-132, (2007)
[23] Peng, T; Leckie, C; Ramamohanarao, K, Survey of network-based defense mechanisms countering the DoS and ddos problems, ACM Computing Surveys, 39, 3, (2007)
[24] Peters, J; Schaal, S, Reinforcement learning of motor skills with policy gradients, Neural networks, 21, 682-697, (2008)
[25] Ranjan, S., Swaminathan, R., Uysal, M., & Knightley, E. (2006). DDoS-resilient scheduling to counter application layer attacks under imperfect detection. In Proceedings of IEEE INFOCOM.
[26] Renuka Devi, S., & Yogesh, P. (2012). Detection of application layer DDsS attacks using information theory based metrics. Department of Information Science and Technology, College of Engineering Guindy doi:10.5121/csit.2012.2223.
[27] Robertson, W. K., & Maggi, F. (2010). Effective anomaly detection with scarce training data. In Network and Distributed System Security Symposium.
[28] Shi, T., Steinhardt, J., & Liang, P. (2015). Learning where to sample in structured prediction. In Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, pages 875-884.
[29] Sutton, R. S., Mcallester, D., Singh, S., Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In In Advances in Neural Information Processing Systems 12, pages 1057-1063. Cambridge, Massachusetts: MIT Press.
[30] Taskar, B., Abbeel, P., & Koller, D. (2002). Discriminative probabilistic models for relational data. In Eighteenth Conference on Uncertainty in Artificial Intelligence.
[31] Taskar, B., Guestrin, C., Koller, D. (2004). Max-margin markov networks. In Advances in Neural Information Processing Systems 16. Cambridge, Massachusetts: MIT Press.
[32] Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005). Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, \(6\), 1453-1484. · Zbl 1222.68321
[33] Weiss, D., & Taskar, B. (2010). Structured prediction cascades. In International Conference on Artificial Intelligence and Statistics, pages 916-923.
[34] Wick, M., Rohanimanesh, K., Bellare, K., Culotta, A., & McCallum, A. (2011). Samplerank: Training factor graphs with atomic gradients. In Proceedings of the 28th International Conference on Machine Learning, pages 777-784.
[35] Wressnegger, C., Schwenk, G., Arp, D., & Rieck, K. (2013). A close look on n-grams in intrusion detection: Anomaly detection versus classification. In Proceedings of the ACM Workshop on Artificial Intelligence and Security, pages 67-76.
[36] Xie, Y; Yu, SZ, A large-scale hidden semi-Markov model for anomaly detection on user browsing behaviors, IEEE/ACM Transactions on Networking, 17, 54-65, (2009)
[37] Zargar, ST; Joshi, J; Tipper, D, A survey of defense mechanisms against distributed denial of service (ddos) flooding attacks, IEEE Communications Surveys & Tutorials, 15, 2046-2069, (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.