Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article
Public Access

Evasion-Robust Classification on Binary Domains

Published: 08 June 2018 Publication History

Abstract

The success of classification learning has led to numerous attempts to apply it in adversarial settings such as spam and malware detection. The core challenge in this class of applications is that adversaries are not static, but make a deliberate effort to evade the classifiers. We investigate both the problem of modeling the objectives of such adversaries, as well as the algorithmic problem of accounting for rational, objective-driven adversaries. We first present a general approach based on mixed-integer linear programming (MILP) with constraint generation. This approach is the first to compute an optimal solution to adversarial loss minimization for two general classes of adversarial evasion models in the context of binary feature spaces. To further improve scalability and significantly generalize the scope of the MILP-based method, we propose a principled iterative retraining framework, which can be used with arbitrary classifiers and essentially arbitrary attack models. We show that the retraining approach, when it converges, minimizes an upper bound on adversarial loss. Extensive experiments demonstrate that the mixed-integer programming approach significantly outperforms several state-of-the-art adversarial learning alternatives. Moreover, the retraining framework performs nearly as well, but scales significantly better. Finally, we show that our approach is robust to misspecifications of the adversarial model.

References

[1]
Vikas P. Deshpande, Robert F. Erbacher, and Chris Harris. 2007. An evaluation of Naïve Bayesian anti-spam filtering techniques. Information Assurance and Security Workshop (IAW'07). IEEE SMC, IEEE.
[2]
Ion Androutsopoulos, Evangelos F. Magirou, and Dimitrios K. Vassilakis. 2005. A game theoretic model of spam e-mailing. In Proceedings of the 2nd Conference on Email and Anti-Spam (CEAS’05).
[3]
Marco Barreno, Peter L. Bartlett, Fuching Jack Chi, Anthony D. Joseph, Blaine Nelson, Benjamin I. P. Rubinstein, Udam Saini, and J. Doug Tygar. 2008. Open problems in the security of learning. In Proceedings of the 1st ACM Workshop on Workshop on AISec. ACM, 19--26.
[4]
Marco Barreno, Blaine Nelson, Anthony D. Joseph, and J. D. Tygar. 2010. The security of machine learning. Machine Learning 81, 2 (2010), 121--148.
[5]
Battista Biggio, Giorgio Fumera, and Fabio Roli. 2014. Security evaluation of pattern classifiers under attack. IEEE Transactions on Knowledge and Data Engineering 26, 4 (2014), 984--996.
[6]
Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press.
[7]
Michael Brückner and Tobias Scheffer. 2009. Nash equilibria of static prediction games. In Proceedings of the Advances in Neural Information Processing Systems. 171--179.
[8]
Michael Brückner and Tobias Scheffer. 2011. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 547--555.
[9]
Xavier Carreras and Lluis Marquez. 2001. Boosting trees for anti-spam email filtering. arxiv cs/0109015.
[10]
William W. Cohen. 2009. Enron email dataset. (2009).
[11]
Nilesh Dalvi, Pedro Domingos, Sumit Sanghai, Deepak Verma, and others. 2004. Adversarial classification. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 99--108.
[12]
Laurent El Ghaoui, Gert René Georges Lanckriet, Georges Natsoulis, and others. 2003. Robust Classification with Interval Data. Computer Science Division, University of California.
[13]
Tom Fawcett. 2003. In vivo spam filtering: A challenge problem for KDD. ACM SIGKDD Explorations Newsletter 5, 2 (2003), 140--148.
[14]
Tom Fawcett and Foster Provost. 1997. Adaptive fraud detection. Data Mining and Knowledge Discovery 1, 3 (1997), 291--316.
[15]
Amir Globerson and Sam Roweis. 2006. Nightmare at test time: Robust learning by feature deletion. In Proceedings of the 23rd International Conference on Machine Learning. ACM, 353--360.
[16]
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. 2014. Explaining and harnessing adversarial examples. arxiv:1412.6572.
[17]
Joshua Goodman, Gordon V. Cormack, and David Heckerman. 2007. Spam and the ongoing battle for the inbox. Communications of the ACM 50, 2 (2007), 25--33.
[18]
Zoltan Gyongi and Hector Garcia-Molina. 2005. Spam: It’s not just for inboxes anymore. Computer 38, 10 (2005), 28--34.
[19]
Stephen Hinde. 2003. Spam: The evolution of a nuisance. Computers 8 Security 22, 6 (2003), 474--478.
[20]
Peter J. Huber. 2011. Robust Statistics. Springer.
[21]
A. Kantchelian, J. D. Tygar, and A. D. Joseph. 2015. Evasion and hardening of tree ensemble classifiers. arXiv.
[22]
Christoph Karlberger, Günther Bayler, Christopher Kruegel, and Engin Kirda. 2007. Exploiting redundancy in natural language to penetrate bayesian spam filters.In Proceedings of the Workshop on Offensive Technologies (WOOT’07) 7 (2007), 1--7.
[23]
Liyiming Ke, Bo Li, and Yevgeniy Vorobeychik. 2016. Behavioral experiments in email filter evasion. In Proceedings of the AAAI Conference on Artificial Intelligence.
[24]
Michael Kearns and Ming Li. 1993. Learning in the presence of malicious errors. SIAM Journal on Computing 22, 4 (1993), 807--837.
[25]
Bryan Klimt and Yiming Yang. 2004. The enron corpus: A new dataset for email classification research. In Proceedings of the European Conference on Machine Learning (ECML’04). Springer, 217--226.
[26]
Marius Kloft and Pavel Laskov. 2012. Security analysis of online centroid anomaly detection. The Journal of Machine Learning Research 13, 1 (2012), 3681--3724.
[27]
Alexey Kurakin, Ian J. Goodfellow, and Samy Bengio. 2017. Adversarial machine learning at scale. In Proceedings of the International Conference on Learning Representations.
[28]
Anukool Lakhina, Mark Crovella, and Christophe Diot. 2004. Diagnosing network-wide traffic anomalies. In Proceedings of the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM’04), 34. ACM, 219--230.
[29]
Pavel Laskov and Richard Lippmann. 2010. Machine learning in adversarial environments. Machine Learning 81, 2 (2010), 115--119.
[30]
Yann LeCun and Corinna Cortes. 2010. MNIST Handwritten Digit Database. Retrieved from http://yann.lecun.com/exdb/mnist.
[31]
Bo Li and Yevgeniy Vorobeychik. 2014. Feature cross-substitution in adversarial classification. In Proceedings of the Advances in Neural Information Processing Systems. 2087--2095.
[32]
Bo Li and Yevgeniy Vorobeychik. 2015. Scalable optimization of randomized operational decisions in adversarial classification settings. In Proceedings of the 18th International Conference on Artificial Intelligence and Statistics. 599--607.
[33]
M. Lichman. 2013. UCI Machine Learning Repository. (2013). Retrieved from http://archive.ics.uci.edu/ml
[34]
Wei Liu and Sanjay Chawla. 2009. A game theoretical model for adversarial learning. In Proceedings of the IEEE International Conference on Data Mining Workshops (ICDMW’09). IEEE, 25--30.
[35]
Wei Liu and Sanjay Chawla. 2010. Mining adversarial patterns via regularized loss minimization. Machine Learning 81, 1 (2010), 69--83.
[36]
Daniel Lowd and Christopher Meek. 2005. Adversarial learning. In Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. ACM, 641--647.
[37]
Matthew V. Mahoney and Philip K. Chan. 2002. Learning nonstationary models of normal network traffic for detecting novel attacks. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 376--385.
[38]
Garth P. McCormick. 1976. Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems. Mathematical Programming 10, 1 (1976), 147--175.
[39]
Vangelis Metsis, Ion Androutsopoulos, and Georgios Paliouras. 2006. Spam filtering with naive Bayes-which naive bayes? In Proceedings of the 3rd Conference on Email and Anti-Spam (CEAS’06). 27--28.
[40]
B. Nelson, B. Rubinstein, L. Huang, A. Joseph, S. Lee, S. Rao, and J. D. Tygar. 2012a. Query strategies for evading convex-inducing classifiers. Journal of Machine Learning Research 13 (2012), 1293--1332.
[41]
Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Steven J. Lee, Satish Rao, and J. D. Tygar. 2012b. Query strategies for evading convex-inducing classifiers. The Journal of Machine Learning Research 13, 1 (2012), 1293--1332.
[42]
Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, and J. D. Tygar. 2011. Classifier evasion: Models and open problems. In Proceedings of the International Workshop on Privacy and Security Issues in Data Mining and Machine Learning. Springer, 92--98.
[43]
James Newsome, Brad Karp, and Dawn Song. 2006. Paragraph: Thwarting signature learning by training maliciously. In Proceedings of the International Workshop on Recent Advances in Intrusion Detection. Springer, 81--105.
[44]
Anh Nguyen, Jason Yosinski, and Jeff Clune. 2015. Deep neural networks are easily fooled: High confidence predictions for unrecognizable images. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR’15). IEEE, 427--436.
[45]
Nicolas Papernot, Patrick McDaniel, and Ian Goodfellow. 2016a. Transferability in machine learning: From Phenomena to black-box attacks using adversarial samples. arxiv:1605.07277.
[46]
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z. Berkay Celik, and Ananthram Swami. 2016b. Practical black-box attacks against deep learning systems using adversarial examples. arxiv:1602.02697.
[47]
Nicolas Papernot, Patrick McDaniel, Somesh Jha, Matt Fredrikson, Z. Berkay Celik, and Ananthram Swami. 2016c. The limitations of deep learning in adversarial settings. In Prceedings of the IEEE European Symposium on Security and Privacy (EuroS8P’16). IEEE, 372--387.
[48]
Manoj Parameswaran, Huaxia Rui, and S. Sayin. 2010. A game theoretic model and empirical analysis of spammer strategies. In Proceedings of the 7th Annual Collaboration, Electronic Messaging, AntiAbuse and Spam Conference, vol. 7.
[49]
Leif E. Peterson. 2009. K-nearest neighbor. Scholarpedia 4, 2 (2009), 1883.
[50]
James Pita, Milind Tambe, Chris Kiekintveld, Shane Cullen, and Erin Steigerwald. 2011. GUARDS: Game theoretic security allocation on a national scale. In Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems-Volume 1. International Foundation for Autonomous Agents and Multiagent Systems, 37--44.
[51]
Anirudh Ramachandran and Nick Feamster. 2006. Understanding the network-level behavior of spammers. In Proceedings of the ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications 36, 4 (2006), 291--302.
[52]
Anirudh Ramachandran, Nick Feamster, and Santosh Vempala. 2007. Filtering spam with behavioral blacklisting. In Proceedings of the ACM Conference on Computer and Communications Security. 342--351.
[53]
Justin M. Rao and David H. Reiley. 2012. The economics of spam. Journal of Economic Perspectives 26, 3 (2012), 87--110.
[54]
Eran Reshef and Eilon Solan. 2006. The effects of anti-spam methods on spam mail. In Proceedings of the Conference on Email and Anti-Spam.
[55]
Benjamin I. P. Rubinstein, Blaine Nelson, Ling Huang, Anthony D. Joseph, Shing-Hon Lau, Satish Rao, Nina Taft, and J. D. Tygar. 2009. Antidote: Understanding and defending against poisoning of anomaly detectors. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference. ACM, 1--14.
[56]
Sara Sabour, Yanshuai Cao, Fartash Faghri, and David J. Fleet. 2015. Adversarial manipulation of deep representations. arxiv:1511.05122.
[57]
Mehran Sahami, Susan Dumais, David Heckerman, and Eric Horvitz. 1998. A Bayesian approach to filtering junk e-mail. In Proceedings of the Papers from the Workshop on Learning for Text Categorization, vol. 62. 98--105.
[58]
C. Smutz and A. Stavrou. 2012. Malicious PDF detection using metadata and structural features. In Proceedings of the Annual Computer Security Applications Conference. 239--248.
[59]
Nedim Srndic and Pavel Laskov. 2013. Detection of malicious PDF files based on hierarchical document structure. In Proceedings of the Annual Network 8 Distributed System Security Symposium.
[60]
Pedro Tabacof and Eduardo Valle. 2015. Exploring the space of adversarial images. arxiv:1510.05328.
[61]
Choon Hui Teo, Amir Globerson, Sam T. Roweis, and Alex J. Smola. 2007. Convex learning with invariances. In Proceedings of the 21st Annual Conference on Neural Information Processing Systems (NIPS’07), vol. 20. 1489--1496.
[62]
MohamadAli Torkamani and Daniel Lowd. 2013. Convex adversarial collective classification. In Proceedings of the 30th International Conference on Machine Learning. 642--650.
[63]
David E. Tyler. 2008. Robust statistics: Theory and methods. Journal of the American Statistical Association 103, 482 (2008), 888--889.
[64]
Dimitrios K. Vassilakis, Ion Androutsopoulos, and Evangelos F. Magirou. 2007. A game-theoretic investigation of the effect of human interactive proofs on spam e-mail. In Proceedings of the Conference on Email and Anti-Spam.
[65]
Shobha Venkataraman, Avrim Blum, and Dawn Song. 2008. Limits of learning-based signature generation with adversaries. (2008).
[66]
Yevgeniy Vorobeychik and Bo Li. 2014. Optimal randomized classification in adversarial settings. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems.
[67]
David Wagner. 2004. Resilient aggregation in sensor networks. In Proceedings of the 2nd ACM Workshop on Security of ad hoc and Sensor Networks. ACM, 78--87.
[68]
Huan Xu, Constantine Caramanis, and Shie Mannor. 2009. Robustness and regularization of support vector machines. Journal of Machine Learning Research 10, (Jul. 2009), 1485--1510.
[69]
Kong Ying and Zhao Jie. 2012. Learning to filter unsolicited commercial e-mail. In International Proceedings of Computer Science 8 Information Technology 49 (2012).
[70]
Fei Zhang, Patrick P. K. Chan, Battista Biggio, Daniel S. Yeung, and Fabio Roli. 2015. Adversarial feature selection against evasion attacks. (2015).
[71]
Yan Zhou and Murat Kantarcioglu. 2014. Adversarial learning with Bayesian hierarchical mixtures of experts. In Proceedings of the SIAM International Conference on Data Mining. 929--937.
[72]
Yan Zhou, Murat Kantarcioglu, Bhavani Thuraisingham, and Bowei Xi. 2012. Adversarial support vector machine learning. In Proceedings of the SIGKDD International Conference on Knowledge Discovery and Data Mining. 1059--1067.

Cited By

View all
  • (2022)Role of Logistic Regression in Malware Detection: A Systematic Literature ReviewVFAST Transactions on Software Engineering10.21015/vtse.v10i2.96310:2(36-46)Online publication date: 15-May-2022
  • (2022)DACHA: A Dual Graph Convolution Based Temporal Knowledge Graph Representation Learning Method Using Historical RelationACM Transactions on Knowledge Discovery from Data10.1145/347705116:3(1-18)Online publication date: 30-Jun-2022
  • (2022)Adversarial Defense Mechanisms for Supervised LearningAdversarial Machine Learning10.1007/978-3-030-99772-4_5(151-238)Online publication date: 26-Aug-2022
  • Show More Cited By

Index Terms

  1. Evasion-Robust Classification on Binary Domains

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Knowledge Discovery from Data
    ACM Transactions on Knowledge Discovery from Data  Volume 12, Issue 4
    August 2018
    354 pages
    ISSN:1556-4681
    EISSN:1556-472X
    DOI:10.1145/3208362
    Issue’s Table of Contents
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 08 June 2018
    Accepted: 01 February 2018
    Revised: 01 January 2018
    Received: 01 April 2017
    Published in TKDD Volume 12, Issue 4

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Adversarial classification
    2. adversarial examples
    3. classifier evasion
    4. mixed-integer linear programming
    5. robust learning

    Qualifiers

    • Research-article
    • Research
    • Refereed

    Funding Sources

    • Office of Naval Research
    • National Science Foundation
    • National Institutes of Health
    • Air Force Research Laboratory
    • Army Research Office
    • Symantec Research Labs Graduate Fellowship, and Sandia National Laboratories

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)109
    • Downloads (Last 6 weeks)9
    Reflects downloads up to 19 Dec 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)Role of Logistic Regression in Malware Detection: A Systematic Literature ReviewVFAST Transactions on Software Engineering10.21015/vtse.v10i2.96310:2(36-46)Online publication date: 15-May-2022
    • (2022)DACHA: A Dual Graph Convolution Based Temporal Knowledge Graph Representation Learning Method Using Historical RelationACM Transactions on Knowledge Discovery from Data10.1145/347705116:3(1-18)Online publication date: 30-Jun-2022
    • (2022)Adversarial Defense Mechanisms for Supervised LearningAdversarial Machine Learning10.1007/978-3-030-99772-4_5(151-238)Online publication date: 26-Aug-2022
    • (2021)Oriole: Thwarting Privacy Against Trustworthy Deep Learning ModelsInformation Security and Privacy10.1007/978-3-030-90567-5_28(550-568)Online publication date: 1-Dec-2021
    • (2020)A System-Driven Taxonomy of Attacks and Defenses in Adversarial Machine LearningIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2020.29689334:4(450-467)Online publication date: Aug-2020
    • (2020)Feature-Based Adversarial Attacks Against Machine Learnt Mobile Malware Detectors2020 30th International Telecommunication Networks and Applications Conference (ITNAC)10.1109/ITNAC50341.2020.9315144(1-8)Online publication date: 25-Nov-2020
    • (2020)Machine Learning Security: Threats, Countermeasures, and EvaluationsIEEE Access10.1109/ACCESS.2020.29874358(74720-74742)Online publication date: 2020
    • (2019)Improving robustness of ML classifiers against realizable evasion attacks using conserved featuresProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361359(285-302)Online publication date: 14-Aug-2019
    • (2018)Adversarial regression for detecting attacks in cyber-physical systemsProceedings of the 27th International Joint Conference on Artificial Intelligence10.5555/3304222.3304293(3769-3775)Online publication date: 13-Jul-2018
    • (2018)Adversarial Machine LearningSynthesis Lectures on Artificial Intelligence and Machine Learning10.2200/S00861ED1V01Y201806AIM03912:3(1-169)Online publication date: 8-Aug-2018
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Full Access

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media