Adversarial machine learning

ABSTRACT

In this paper (expanded from an invited talk at AISEC 2010), we discuss an emerging field of study: adversarial machine learning---the study of effective machine learning techniques against an adversarial opponent. In this paper, we: give a taxonomy for classifying attacks against online machine learning algorithms; discuss application-specific factors that limit an adversary's capabilities; introduce two models for modeling an adversary's capabilities; explore the limits of an adversary's knowledge about the algorithm, feature space, training, and input data; explore vulnerabilities in machine learning algorithms; discuss countermeasures against attacks; introduce the evasion challenge; and discuss privacy-preserving learning techniques.

References

1. B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In PODS'07, pages 273--282, 2007.
2. M. Barreno, B. Nelson, R. Sears, A. D. Joseph, and J. D. Tygar. Can machine learning be secure? In ASIACCS'06, pages 16--25, 2006.
3. A. Beimel, S. Kasiviswanathan, and K. Nissim. Bounds on the sample complexity for private learning and private data release. In Theory of Crypto., volume 5978 of LNCS, pages 437--454. 2010.
4. B. Biggio, G. Fumera, and F. Roli. Multiple classifier systems under attack. In Proc. Int. Workshop Multiple Classifier Systems, volume 5997, pages 74--83, 2010.
5. C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.
6. A. Blum, C. Dwork, F. McSherry, and K. Nissim. Practical privacy: the SuLQ framework. In PODS'05, pages 128--138, 2005.
7. A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In STOC'08, pages 609--618, 2008.
8. M. Bruckner and T. Scheffer. Nash equilibria of static prediction games. In NIPS, pages 171--179. 2009.
9. N. Cesa-Bianchi and G. Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
10. K. Chaudhuri and C. Monteleoni. Privacy-preserving logistic regression. In NIPS, pages 289--296, 2009.
11. K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk minimization. JMLR, 12:1069--1109, 2011.
12. S. P. Chung and A. K. Mok. Allergy attack against automatic signature generation. In RAID'09, volume 4219 of LNCS, pages 61--80, 2006.
13. S. P. Chung and A. K. Mok. Advanced allergy attacks: Does a corpus really help? In RAID'07, volume 4637 of LNCS, pages 236--255, 2007.
14. N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge University Press, 2000.
15. C. Croux, P. Filzmoser, and M. R. Oliveira. Algorithms for projection-pursuit robust principal component analysis. Chemometrics and Intelligent Laboratory Systems, 87(2):218--225, 2007.
16. N. Dalvi, P. Domingos, Mausam, S. Sanghai, and D. Verma. Adversarial classification. In KDD'04, pages 99--108, 2004.
17. I. Dinur and K. Nissim. Revealing information while preserving privacy. In PODS'03, pages 202--210, 2003.
18. Y. Duan, J. Canny, and J. Zhan. P4P: Practical large-scale privacy-preserving distributed computation robust against malicious users. In USENIX Security, pages 207--222, 2010.
19. C. Dwork. Differential privacy. In ICALP'06, pages 1--12, 2006.
20. C. Dwork. A firm foundation for private data analysis. Comms. ACM, 54(1):86--95, 2011.
21. C. Dwork and J. Lei. Differential privacy and robust statistics. In STOC'09, pages 371--380, 2009.
22. C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In TCC'06, pages 265--284, 2006.
23. C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of LP decoding. In STOC'07, pages 85--94, 2007.
24. C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC'09, pages 381--390, 2009.
25. C. Dwork and S. Yekhanin. New efficient attacks on statistical disclosure control mechanisms. In CRYPTO'08, pages 469--480, 2008.
26. R. A. Fisher. Question 14: Combining independent tests of significance. American Statistician, 2(5):30--31, 1948.
27. P. Fogla and W. Lee. Evading network anomaly detection systems: Formal reasoning and practical techniques. In CCS'06, pages 59--68, 2006.
28. A. Globerson and S. Roweis. Nightmare at test time: Robust learning by feature deletion. In ICML'06, pages 353--360, 2006.
29. R. Hall, S. Fienberg, and Y. Nardi. Secure multiparty linear regression based on homomorphic encryption. J. Official Statistics, 2011. To appear.
30. F. R. Hampel, E. M. Ronchetti, P. J. Rousseeuw, and W. A. Stahel. Robust Statistics: The Approach Based on Influence Functions. Probability and Mathematical Statistics. John Wiley and Sons, 1986.
31. M. Hardt and K. Talwar. On the geometry of differential privacy. In STOC'10, pages 705--714, 2010.
32. M. Kantarcioglu, B. Xi, and C. Clifton. Classifier evaluation and attribute selection against active adversaries. Technical Report 09-01, Purdue University, February 2009.
33. S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In FOCS'08, pages 531--540, 2008.
34. A. Kerckhoffs. La cryptographie militaire. Journal des Sciences Militaires, 9:5--83, January 1883.
35. M. Kloft and P. Laskov. Online anomaly detection under adversarial impact. In AISTATS'10, 2010.
36. A. Lakhina, M. Crovella, and C. Diot. Diagnosing network-wide traffic anomalies. In SIGCOMM'04, pages 219--230, 2004.
37. P. Laskov and M. Kloft. A framework for quantitative security analysis of machine learning. In AISec'09, pages 1--4, 2009.
38. C. Liu and S. Stamm. Fighting unicode-obfuscated spam. In Proceedings of the Anti-Phishing Working Groups 2nd Annual eCrime Researchers Summit, pages 45--59, 2007.
39. D. Lowd and C. Meek. Adversarial learning. In KDD'05, pages 641--647, 2005.
40. D. Lowd and C. Meek. Good word attacks on statistical spam filters. In CEAS'05, 2005.
41. A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. ACM Trans. KDD, 1(1), 2007.
42. M. V. Mahoney and P. K. Chan. An analysis of the 1999 DARPA/Lincoln Laboratory evaluation data for network anomaly detection. In RAID'03, volume 2820 of LNCS, pages 220--237, 2003.
43. F. McSherry and I. Mironov. Differentially private recommender systems: building privacy into the net. In KDD'09, pages 627--636, 2009.
44. F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS'07, pages 94--103, 2007.
45. T. A. Meyer and B. Whateley. SpamBayes: Effective open-source, Bayesian based, email classification system. In CEAS'04, 2004.
46. T. Mitchell. Machine Learning. McGraw Hill, 1997.
47. B. Nelson, M. Barreno, F. J. Chi, A. D. Joseph, B. I. P. Rubinstein, U. Saini, C. Sutton, J. D. Tygar, and K. Xia. Exploiting machine learning to subvert your spam filter. In LEET'08, pages 1--9, 2008.
48. B. Nelson, M. Barreno, F. J. Chi, A. D. Joseph, B. I. P. Rubinstein, U. Saini, C. Sutton, J. D. Tygar, and K. Xia. Misleading learners: Co-opting your spam filter. In J. J. P. Tsai and P. S. Yu, editors, Machine Learning in Cyber Trust: Security, Privacy, Reliability, pages 17--51. Springer, 2009.
49. B. Nelson and A. D. Joseph. Bounding an attack's complexity for a simple learning model. In Proc. Workshop on Tackling Computer Systems Problems with Machine Learning Techniques, 2006.
50. B. Nelson, B. I. P. Rubinstein, L. Huang, A. D. Joseph, S. hon Lau, S. Lee, S. Rao, A. Tran, and J. D. Tygar. Near-optimal evasion of convex-inducing classifiers. In AISTATS, 2010.
51. B. Nelson, B. I. P. Rubinstein, L. Huang, A. D. Joseph, and J. D. Tygar. Classifier evasion: Models and open problems (position paper). In Proc. Workshop on Privacy & Security issues in Data Mining and Machine Learning, 2010.
52. J. Newsome, B. Karp, and D. Song. Paragraph: Thwarting signature learning by training maliciously. In RAID, volume 4219 of LNCS, pages 81--105, 2006.
53. L. Rademacher and N. Goyal. Learning convex bodies is hard. In COLT, pages 303--308, 2009.
54. H. Ringberg, A. Soule, J. Rexford, and C. Diot. Sensitivity of PCA for traffic anomaly detection. In SIGMETRICS, pages 109--120, 2007.
55. G. Robinson. A statistical approach to the spam problem. Linux Journal, Mar. 2003.
56. B. I. P. Rubinstein, P. L. Bartlett, L. Huang, and N. Taft. Learning in a large function space: Privacy-preserving mechanisms for SVM learning, 2009. In submission; http://arxiv.org/abs/0911.5708v1.
57. B. I. P. Rubinstein, B. Nelson, L. Huang, A. D. Joseph, S. hon Lau, S. Rao, N. Taft, and J. D. Tygar. ANTIDOTE: Understanding and defending against poisoning of anomaly detectors. In A. Feldmann and L. Mathy, editors, IMC'09, pages 1--14, New York, NY, USA, November 2009. ACM.
58. D. Sculley, G. M. Wachman, and C. E. Brodley. Spam filtering using inexact string matching in explicit feature space with on-line linear classifiers. In TREC'06, 2006.
59. A. Smith. Privacy-preserving statistical estimation with optimal convergence rates. In STOC'2011, pages 813--822, 2011.
60. S. J. Stolfo, W. jen Li, S. Hershkop, K. Wang, C. wei Hu, and O. Nimeskern. Detecting viral propagations using email behavior profiles. In ACM Trans. Internet Technology, May 2004.
61. L. Sweeney. k-anonymity: a model for protecting privacy. Int. J. Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):557--570, 2002.
62. K. M. C. Tan, K. S. Killourhy, and R. A. Maxion. Undermining an anomaly-based intrusion detection system using common exploits. In RAID'02, volume 2516 of LNCS, pages 54--73, 2002.
63. S. Venkataraman, A. Blum, and D. Song. Limits of learning-based signature generation with adversaries. In NDSS'08, 2008.
64. D. Wagner and P. Soto. Mimicry attacks on host-based intrusion detection systems. In CCS'02, pages 255--264, 2002.
65. G. L. Wittel and S. F. Wu. On attacking statistical spam filters. In CEAS'04, 2004.

Index Terms

• Security and privacy

  • Intrusion/anomaly detection and malware mitigation

  • Systems security

    • Operating systems security