Can machine learning be secure?

ABSTRACT

Machine learning systems offer unparalled flexibility in dealing with evolving input in a variety of applications, such as intrusion detection systems and spam e-mail filtering. However, machine learning algorithms themselves can be a target of attack by a malicious adversary. This paper provides a framework for answering the question, "Can machine learning be secure?" Novel contributions of this paper include a taxonomy of different types of attacks on machine learning techniques and systems, a variety of defenses against those attacks, a discussion of ideas that are important to security for machine learning, an analytical model giving a lower bound on attacker's work function, and a list of open problems.

REFERENCES

• 1: I. Androutsopoulos, J. Koutsias, K. V. Chandrinos, G. Paliouras, and C. D. Spyropolous. An evaluation of naive Bayesian anti-spam filtering. Proceedings of the Workshop on Machine Learning in the New Information Age, pages 9--17, 2000.
• 2: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 3: Apache, http://spamassassin.apache.org/. Spam Assassin.
• 4: Peter Auer, Learning nested differences in the presence of malicious noise, Theoretical Computer Science, v.185 n.1, p.159-175, Oct. 10, 1997 [doi>10.1016/S0304-3975(97)00019-4 ]
• 5: V. J. Baston , F. A. Bostock, Deception games, International Journal of Game Theory, v.17 n.2, p.129-134, March, 1988 [doi>10.1007/BF01254543]
• 6: Nader H. Bshouty , Nadav Eiron , Eyal Kushilevitz, PAC learning with nasty noise, Theoretical Computer Science, v.288 n.2, p.255-275, 16 October 2002 [doi>10.1016/S0304-3975(01)00403-0 ]
• 7: Nicolò Cesa-Bianchi , Yoav Freund , David Haussler , David P. Helmbold , Robert E. Schapire , Manfred K. Warmuth, How to use expert advice, Journal of the ACM (JACM), v.44 n.3, p.427-485, May 1997 [doi>10.1145/258128.258179]
• 8: Nilesh Dalvi , Pedro Domingos , Mausam , Sumit Sanghai , Deepak Verma, Adversarial classification, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014066]
• 9: Bert Fristedt, The deceptive number changing game, in the absence of symmetry, International Journal of Game Theory, v.26 n.2, p.183-191, 1997 [doi>10.1007/s001820050024 ]
• 10: J. Graham-Cumming. How to beat an adaptive spam filter. Presentation at the MIT Spam Conference, Jan. 2004.
• 11: T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2003.
• 12: S. A. Heise and H. S. Morse. The DARPA JFACC program: Modeling and control of military operations. In Proceedings of the 39th IEEE Conference on Decision and Control, pages 2551--2555. IEEE, 2000.
• 13: Mark Herbster , Manfred K. Warmuth, Tracking the Best Expert, Machine Learning, v.32 n.2, p.151-178, Aug. 1998 [doi>10.1023/A:1007424614876 ]
• 14: J. P. Hespanha, Y. S. Ateskan, and H. H. Kizilocak. Deception in non-cooperative games with partial information. In Proceedings of the 2nd DARPA-JFACC Symposium on Advances in Enterprise Control, 2000.
• 15: Michael Kearns , Ming Li, Learning in the presence of malicious errors, SIAM Journal on Computing, v.22 n.4, p.807-837, Aug. 1993 [doi>10.1137/0222052]
• 16: A. Lazarevic, L. Ertöz, V. Kumar, A. Ozgur, and J. Srivastava. A comparative study of anomaly detection schemes in network intrusion detection. In D. Barbará and C. Kamath, editors, Proceedings of the Third SIAM International Conference on Data Mining, May 2003.
• 17: K.-T. Lee. On a deception game with three boxes. International Journal of Game Theory, 22:89--95, 1993.
• 18: Yihua Liao , V. Rao Vemuri, Using Text Categorization Techniques for Intrusion Detection, Proceedings of the 11th USENIX Security Symposium, p.51-59, August 05-09, 2002
• 19: Jean-Paul M. G. Linnartz , Marten van Dijk, Analysis of the Sensitivity Attack against Electronic Watermarks in Images, Proceedings of the Second International Workshop on Information Hiding, p.258-272, April 14-17, 1998
• 20: Nick Littlestone , Manfred K. Warmuth, The weighted majority algorithm, Information and Computation, v.108 n.2, p.212-261, Feb. 1, 1994 [doi>10.1006/inco.1994.1009 ]
• 21: Daniel Lowd , Christopher Meek, Adversarial learning, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081950]
• 22: D. Lowd and C. Meek. Good word attacks on statistical spam filters. In Proceedings of the Second Conference on Email and Anti-Spam (CEAS), 2005.
• 23: Matthew V. Mahoney , Philip K. Chan, Learning nonstationary models of normal network traffic for detecting novel attacks, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775102]
• 24: S. Mukkamala, G. Janoski, and A. Sung. Intrusion detection using neural networks and support vector machines. In Proceedings of the International Joint Conference on Neural Networks (IJCNN'02), pages 1702--1707, 2002.
• 25: B. Nelson. Designing, Implementing, and Analyzing a System for Virus Detection. Master's thesis, University of California at Berkeley, Dec. 2005.
• 26: Vern Paxson, Bro: a system for detecting network intruders in real-time, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.23-24, p.2435-2463, Dec. 1999 [doi>10.1016/S1389-1286(99)00112-7 ]
• 27: N. Provos. A virtual honeypot framework. In Proceedings of the 13th USENIX Security Symposium, 2004.
• 28: R. Raina, A. Y. Ng, and D. Koller. Transfer learning by constructing informative priors. In Neural Information Processing Systems Workshop on Inductive Transfer: 10 Years Later, 2005.
• 29: M. Sakaguchi. Effect of correlation in a simple deception game. Mathematica Japonica, 35(3):527--536, 1990.
• 30: Rocco A. Servedio, Smooth boosting and learning with malicious noise, The Journal of Machine Learning Research, 4, p.633-648, 12/1/2003
• 31: John Shawe-Taylor , Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press, New York, NY, 2004
• 32: J. Spencer. A deception game. American Math Monthly, 80:416--417, 1973.
• 33: S. J. Stolfo, S. Hershkop, K. Wang, O. Nimeskern, and C. W. Hu. A behavior-based approach to secure email systems. In Mathematical Methods, Models and Architectures for Computer Networks Security, 2003.
• 34: S. J. Stolfo, W. J. Li, S. Hershkop, K. Wang, C. W. Hu, and O. Nimeskern. Detecting viral propagations using email behavior profiles. In ACM Transactions on Internet Technology, 2004.
• 35: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• 36: L. G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the 9th International Joint Conference on Artificial Intelligence, pages 560--566, 1985.
• 37: Volodimir G. Vovk, Aggregating strategies, Proceedings of the third annual workshop on Computational learning theory, p.371-386, August 06-08, 1990, Rochester, New York, United States
• 38: Louis Wehenkel, Machine-Learning Approaches to Power-System Security Assessment, IEEE Expert: Intelligent Systems and Their Applications, v.12 n.5, p.60-72, September 1997 [doi>10.1109/64.621229 ]
• 39: G. L. Wittel and S. F. Wu. On attacking statistical spam filters. In Proceedings of the First Conference on Email and Anti-Spam (CEAS), 2004.
• 40: W. Xu, P. Bodik, and D. Patterson. A flexible architecture for statistical learning and data mining from system log streams. In Temporal Data Mining: Algorithms, Theory and Applications, Brighton, UK, Nov. 2004. The Fourth IEEE International Conference on Data Mining.
• 41: Calvin Chow, Parzen-Window Network Intrusion Detectors, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 4, p.40385, August 11-15, 2002
• 42: K. Yu and V. Tresp. Learning to learn and collaborative filtering. In Neural Information Processing Systems Workshop on Inductive Transfer: 10 Years Later, 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
      I.5.2 Design Methodology

General Terms:
Security

Keywords:
adversarial learning, computer networks, computer security, game theory, intrusion detection, machine learning, security metrics, spam filters, statistical learning