jmlr jmlr2012 jmlr2012-94 jmlr2012-94-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Steven J. Lee, Satish Rao, J. D. Tygar
Abstract: Classifiers are often used to detect miscreant activities. We study how an adversary can systematically query a classifier to elicit information that allows the attacker to evade detection while incurring a near-minimal cost of modifying their intended malfeasance. We generalize the theory of Lowd and Meek (2005) to the family of convex-inducing classifiers that partition their feature space into two sets, one of which is convex. We present query algorithms for this family that construct undetected instances of approximately minimal cost using only polynomially-many queries in the dimension of the space and in the level of approximation. Our results demonstrate that nearoptimal evasion can be accomplished for this family without reverse engineering the classifier’s decision boundary. We also consider general ℓ p costs and show that near-optimal evasion on the family of convex-inducing classifiers is generally efficient for both positive and negative convexity for all levels of approximation if p = 1. Keywords: query algorithms, evasion, reverse engineering, adversarial learning
Dana Angluin. Queries and concept learning. Machine Learning, 2:319–342, 1988. Keith Ball. An elementary introduction to modern convex geometry. In Flavors of Geometry, volume 31 of MSRI Publications, pages 1–58. Cambridge University Press, 1997. Dimitris Bertsimas and Santosh Vempala. Solving convex programs by random walks. Journal of the ACM, 51(4):540–556, 2004. Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Richard P. Brent. Algorithms for Minimization without Derivatives. Prentice-Hall, 1973. Michael Br¨ ckner and Tobias Scheffer. Nash equilibria of static prediction games. In Advances in u Neural Information Processing Systems (NIPS), volume 22, pages 171–179. 2009. Richard L. Burden and J. Douglas Faires. Numerical Analysis. Brooks Cole, 7th edition, 2000. Nilesh Dalvi, Pedro Domingos, Mausam, Sumit Sanghai, and Deepak Verma. Adversarial classification. In Proceedings of the 10th International Conference on Knowledge Discovery and Data Mining, pages 99–108, 2004. Sanjoy Dasgupta, Adam Tauman Kalai, and Claire Monteleoni. Analysis of perceptron-based active learning. Journal of Machine Learning Research, 10:281–299, 2009. Vitaly Feldman. On the power of membership queries in agnostic learning. Journal of Machine Learning Research, 10:163–182, 2009. J¨ rg Flum and Martin Grohe. Parameterized Complexity Theory. Texts in Theoretical Computer o Science. An EATCS Series. Springer-Verlag, Secaucus, NJ, USA, 2006. Lee-Ad Gottlieb, Aryeh Kontorovich, and Elchanan Mossel. VC bounds on the cardinality of nearly orthogonal function classes. Technical Report arXiv:1007.4915v2 [math.CO], arXiv, 2011. Donald R. Jones. A taxonomy of global optimization methods based on response surfaces. Journal of Global Optimization, 21(4):345–383, 2001. 1330 Q UERY S TRATEGIES FOR E VADING C ONVEX -I NDUCING C LASSIFIERS Donald R. Jones, Cary D. Perttunen, and Bruce E. Stuckman. Lipschitzian optimization without the Lipschitz constant. Journal Optimization Theory and Application, 79(1):157–181, 1993. Murat Kantarcioglu, Bowei Xi, and Chris Clifton. Classifier evaluation and attribute selection against active adversaries. Technical Report 09-01, Purdue University, 2009. Tamara G. Kolda, Robert Michael Lewis, and Virginia Torczon. Optimization by direct search: New perspectives on some classical and modern methods. SIAM Review, 45(3):385–482, 2003. Anukool Lakhina, Mark Crovella, and Christophe Diot. Diagnosing network-wide traffic anomalies. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), pages 219–230, 2004. L´ szl´ Lov´ sz and Santosh Vempala. Simulated annealing in convex bodies and an O∗ (n4 ) volume a o a algorithm. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’03), pages 650–659, 2003. L´ szl´ Lov´ sz and Santosh Vempala. Hit-and-run from a corner. In Proceedings of the 36th Annual a o a ACM Symposium on Theory of Computing (STOC), pages 310–314, 2004. Daniel Lowd and Christopher Meek. Adversarial learning. In Proceedings of the 11th International Conference on Knowledge Discovery in Data Mining, pages 641–647, 2005. John A. Nelder and Roger Mead. A simplex method for function minimization. The Computer Journal, 7(4):308–313, 1965. Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Shing hon Lau, Steven Lee, Satish Rao, Anthony Tran, and J. D. Tygar. Near-optimal evasion of convex-inducing classifiers. In Proceedings of the 13th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 549–556, 2010a. Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, Steven Lee, Satish Rao, and J. D. Tygar. Query strategies for evading convex-inducing classifiers. Technical Report arXiv:1007.0484v1 [cs.LG], arXiv, 2010b. Blaine Nelson, Benjamin I. P. Rubinstein, Ling Huang, Anthony D. Joseph, and J. D. Tygar. Classifier evasion: Models and open problems. In Privacy and Security Issues in Data Mining and Machine Learning, volume 6549 of Lecture Notes in Computer Science, pages 92–98. 2011. Luis Rademacher and Navin Goyal. Learning convex bodies is hard. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT), pages 303–308, 2009. Greg Schohn and David Cohn. Less is more: Active learning with support vector machines. In Proceedings of the 17th International Conference on Machine Learning (ICML), pages 839–846, 2000. Burr Settles. Active learning literature survey. Computer Sciences Technical Report 1648, University of Wisconsin–Madison, 2009. 1331 N ELSON , RUBINSTEIN , H UANG , J OSEPH , L EE , R AO AND T YGAR Robert L. Smith. The hit-and-run sampler: A globally reaching Markov chain sampler for generating arbitrary multivariate distributions. In Proceedings of the 28th Conference on Winter Simulation (WSC ’96), pages 260–264, 1996. Kymie M. C. Tan, Kevin S. Killourhy, and Roy A. Maxion. Undermining an anomaly-based intrusion detection system using common exploits. In Proceedings of the 5th International Conference on Recent Advances in Intrusion Detection (RAID), volume 2516 of Lecture Notes in Computer Science, pages 54–73, 2002. David Wagner and Paolo Soto. Mimicry attacks on host-based intrusion detection systems. In Proceedings of the 9th ACM Conference on Computer and Communications Security, pages 255– 264, 2002. Ke Wang and Salvatore J. Stolfo. Anomalous payload-based network intrusion detection. In Proceedings of the 7th International Conference on Recent Advances in Intrusion Detection (RAID), volume 3224 of Lecture Notes in Computer Science, pages 203–222, 2004. Ke Wang, Janak J. Parekh, and Salvatore J. Stolfo. Anagram: A content anomaly detector resistant to mimicry attack. In Proceedings of the 9th International Conference on Recent Advances in Intrusion Detection (RAID), volume 4219 of Lecture Notes in Computer Science, pages 226– 248, 2006. Aaron D. Wyner. Capabilities of bounded discrepancy decoding. The Bell System Technical Journal, 44:1061–1122, 1965. 1332