Adversarial classification

ABSTRACT

Essentially all data mining algorithms assume that the data-generating process is independent of the data miner's activities. However, in many domains, including spam detection, intrusion detection, fraud detection, surveillance and counter-terrorism, this is far from the case: the data is actively manipulated by an adversary seeking to make the classifier produce false negatives. In these domains, the performance of a classifier can degrade rapidly after it is deployed, as the adversary learns to defeat it. Currently the only solution to this is repeated, manual, ad hoc reconstruction of the classifier. In this paper we develop a formal framework and algorithms for this problem. We view classification as a game between the classifier and the adversary, and produce a classifier that is optimal given the adversary's optimal strategy. Experiments in a spam detection domain show that this approach can greatly outperform a classifier learned in the standard way, and (within the parameters of the problem) automatically adapt the classifier to the adversary's evolving manipulations.

REFERENCES

• 1: Pedro Domingos, MetaCost: a general method for making classifiers cost-sensitive, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.155-164, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312220]
• 2: Pedro Domingos , Michael Pazzani, On the Optimality of the Simple Bayesian Classifier under Zero-One Loss, Machine Learning, v.29 n.2-3, p.103-130, Nov./Dec. 1997 [doi>10.1023/A:1007413511361]
• 3: Robert B. Doorenbos , Oren Etzioni , Daniel S. Weld, A scalable comparison-shopping agent for the World-Wide Web, Proceedings of the first international conference on Autonomous agents, p.39-48, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267666]
• 4: Tom Fawcett, "In vivo" spam filtering: a challenge problem for KDD, ACM SIGKDD Explorations Newsletter, v.5 n.2, December 2003 [doi>10.1145/980972.980990]
• 5: Tom Fawcett , Foster Provost, Adaptive Fraud Detection, Data Mining and Knowledge Discovery, v.1 n.3, p.291-316, 1997 [doi>10.1023/A:1009700419189]
• 6: D. Fudenberg and D. Levine. The Theory of Learning in Games. MIT Press, Cambridge, MA, 1999.
• 7: D. Fudenberg and J. Tirole. Game Theory. MIT Press, Cambridge, MA, 1991.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: L. Guernsey. Retailers rise in Google rankings as rivals cry foul. New York Times, November 20, 2003.
• 10: Geoff Hulten , Laurie Spencer , Pedro Domingos, Mining time-changing data streams, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.97-106, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502529]
• 11: David Jensen , Matthew Rattigan , Hannah Blau, Information awareness: a prospective technical assessment, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956794]
• 12: M. Kearns. Computational game theory. Tutorial, Department of Computer and Information Sciences, University of Pennsylvania, Philadelphia, PA, 2002. http://www.cis.upenn.edu/~mkearns/nips02tutorial/.
• 13: Ron Kohavi , George H. John, Wrappers for feature subset selection, Artificial Intelligence, v.97 n.1-2, p.273-324, Dec. 1997 [doi>10.1016/S0004-3702(97)00043-X]
• 14: B. Krebs. Online piracy spurs high-tech arms race. Washington Post, June 26, 2003.
• 15: M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the Eleventh International Conference on Machine Learning, pages 157--163, New Brunswick, NJ, 1994. Morgan Kaufmann.
• 16: B. Lloyd. Been gazumped by Google? Trying to make sense of the "Florida" update. Search Engine Guide, November 25, 2003.
• 17: 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]
• 18: A. McCallum and K. Nigam. A comparison of event models for Naive Bayes text classification. In Proceedings of the AAAI-98 Workshop on Learning for Text Categorization, Madison, WI, 1998. AAAI Press.
• 19: F. Nielsen. Email data, 2003. http://www.imm.dtu.dk/~rem/datasets/.
• 20: Foster Provost , Tom Fawcett, Robust Classification for Imprecise Environments, Machine Learning, v.42 n.3, p.203-231, March 2001 [doi>10.1023/A:1007601015854]
• 21: J. Rennie. Ifile spam classifier, 2003. http://www.nongnu.org/ifile/.
• 22: Paul Robertson , J. Michael Brady, Adaptive Image Analysis for Aerial Surveillance, IEEE Intelligent Systems, v.14 n.3, p.30-36, May 1999 [doi>10.1109/5254.769882]
• 23: M. Sahami, S. Dumais, D. Heckerman, and E. Horvitz. A Bayesian approach to filtering junk e-mail. In Proceedings of the AAAI-98 Workshop on Learning for Text Categorization, Madison, WI, 1998. AAAI Press.
• 24: Georgios Sakkis , Ion Androutsopoulos , Georgios Paliouras , Vangelis Karkaletsis , Constantine D. Spyropoulos , Panagiotis Stamatopoulos, A Memory-Based Approach to Anti-Spam Filtering for Mailing Lists, Information Retrieval, v.6 n.1, p.49-73, January 2003 [doi>10.1023/A:1022948414856]
• 25: Ted E. Senator, Ongoing management and application of discovered knowledge in a large regulatory organization: a case study of the use and impact of NASD Regulation's Advanced Detection System (RADS), Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.44-53, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347102]
• 26: J. M. Smith. Evolution and the Theory of Games. Cambridge University Press, Cambridge, UK, 1982.
• 27: P. Turney. Cost-sensitive learning bibliography. Online bibliography, NRC Institute for Information Technology, Ottawa, Canada, 1998. http://members.rogers.com/peter.turney/bibliographies/cost-sensitive.html.
• 28: WordNet 2.0: A lexical database for the English language, 2003. http://www.cogsci.princeton.edu/~wn/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Multivariate statistics

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Induction; Concept learning; Parameter learning
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection; Classifier design and evaluation

General Terms:
Algorithms

Keywords:
cost-sensitive learning, game theory, integer linear programming, naive Bayes, spam detection