Detectives: detecting coalition hit inflation attacks in advertising networks streams

ABSTRACT

Click fraud is jeopardizing the industry of Internet advertising. Internet advertising is crucial for the thriving of the entire Internet, since it allows producers to advertise their products, and hence contributes to the well being of e-commerce. Moreover, advertising supports the intellectual value of the Internet by covering the running expenses of publishing content. Some content publishers are dishonest, and use automation to generate traffic to defraud the advertisers. Similarly, some advertisers automate clicks on the advertisements of their competitors to deplete their competitors' advertising budgets. This paper describes the advertising network model, and focuses on the most sophisticated type of fraud, which involves coalitions among fraudsters. We build on several published theoretical results to devise the Similarity-Seeker algorithm that discovers coalitions made by pairs of fraudsters. We then generalize the solution to coalitions of arbitrary sizes. Before deploying our system on a real network, we conducted comprehensive experiments on data samples for proof of concept. The results were very accurate. We detected several coalitions, formed using various techniques, and spanning numerous sites. This reveals the generality of our model and approach.

REFERENCES

• 1: James Abello , Mauricio G. C. Resende , Sandra Sudarsky, Massive Quasi-Clique Detection, Proceedings of the 5th Latin American Symposium on Theoretical Informatics, p.598-612, April 03-06, 2002
• 2: E. Akkoyunlu. The Enumeration of Maximal Cliques of Large Graphs. SIAM Journal on Computing, 2(1):1--6, 1973.
• 3: Vinod Anupam , Alain Mayer , Kobbi Nissim , Benny Pinkas , Michael K. Reiter, On the security of pay-per-click and other Web advertising schemes, Proceeding of the eighth international conference on World Wide Web, p.1091-1100, May 1999, Toronto, Canada
• 4: Burton H. Bloom, Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, v.13 n.7, p.422-426, July 1970 [doi>10.1145/362686.362692]
• 5: Carlo Blundo , Stelvio Cimato, SAWM: a tool for secure and authenticated web metering, Proceedings of the 14th international conference on Software engineering and knowledge engineering, July 15-19, 2002, Ischia, Italy [doi>10.1145/568760.568871]
• 6: T. Bohman, C. Cooper, and A. Frieze. Min-Wise Independent Linear Permutations. Electronic Journal of Combinatorics, 7:R26, 2000.
• 7: A. Bowker and G. Lieberman. Engineering Statistics, 2nd Edition. Prentice Hall, 1972.
• 8: U. Brandes, M. Gaertler, and D. Wagner. Experiments on Graph Clustering Algorithms. In Proceedings of the 11th ESA European Symposium on Algorithms, pages 568--579, 2003.
• 9: A. Broder, On the Resemblance and Containment of Documents, Proceedings of the Compression and Complexity of Sequences 1997, p.21, June 11-13, 1997
• 10: Andrei Z. Broder, Identifying and Filtering Near-Duplicate Documents, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.1-10, June 21-23, 2000
• 11: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 12: Andrei Z. Broder , Uriel Feige, Min-Wise versus linear independence (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.147-154, January 09-11, 2000, San Francisco, California, United States
• 13: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 14: Coen Bron , Joep Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, v.16 n.9, p.575-577, Sept. 1973 [doi>10.1145/362342.362367]
• 15: CERT Coordination Center. CERT Advisory CA-1996-21 TCP SYN Flooding and IP Spoofing Attacks. http://www.cert.org/advisories/CA-1996-21.html, September 19 1996.
• 16: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 17: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 18: David Cheng , Santosh Vempala , Ravi Kannan , Grant Wang, A divide-and-merge methodology for clustering, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065192]
• 19: Norishige Chiba , Takao Nishizeki, Arboricity and subgraph listing algorithms, SIAM Journal on Computing, v.14 n.1, p.210-223, Feb. 1985 [doi>10.1137/0214017]
• 20: L. Gerhards and W. Lindenberg. Clique Detection for Nondirected Graphs: Two New Algorithms. Computing, Volume 21(4):295--322, 1979.
• 21: David Gibson , Ravi Kumar , Andrew Tomkins, Discovering large dense subgraphs in massive graphs, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 22: Christos Gkantsidis , Milena Mihail , Amin Saberi, Conductance and congestion in power law graphs, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 23: K. Holzapfel, S. Kosub, M. Maaß, and H. Täubig. The Complexity of Detecting Fixed-Density Clusters. In Proceedings of the 5th CIAC Italian Conference on Algorithms and Complexity, pages 201--212, 2003.
• 24: Piotr Indyk, A small approximately min-wise independent family of hash functions, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.454-456, January 17-19, 1999, Baltimore, Maryland, United States
• 25: Markus Jakobsson , Philip D. MacKenzie , Julien P. Stern, Secure and lightweight advertising on the Web, Proceeding of the eighth international conference on World Wide Web, p.1101-1109, May 1999, Toronto, Canada
• 26: H. Johnston. Cliques of a Graph-Variations on the Bron-Kerbosch Algorithm. International Journal of Computer and Information Sciences, 5(3):209--238, 1976.
• 27: R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
• 28: Daniel V. Klein, Defending Against the Wily Surfer-Web-based Attacks and Defenses, Proceedings of the Workshop on Intrusion Detection and Network Monitoring, p.81-92, April 09-12, 1999
• 29: M. Liedtke. Google to Pay $90M in `Click Fraud' Case. Washington Post Magazine, March 9 2006.
• 30: M. Liedtke. Yahoo Settles `Click Fraud' Lawsuit. MSNBC News, June 28 2006.
• 31: E. Loukakis. A New Backtracking Algorithm for Generating the Family of Maximal Independent Sets of a Graph. Computers & Mathematics with Applications, 9(4):583--589, 1983.
• 32: C. Mann. How Click Fraud Could Swallow the Internet. Wired Magazine, January 2006.
• 33: R. McGann. Study: Consumers Delete Cookies at Surprising Rate. ClickZ News, March 14 2005.
• 34: Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Duplicate detection in click streams, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060753]
• 35: Ahmed Metwally , Divyakant Agrawal , Amr El Abbadi, Using association rules for fraud detection in web advertising networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 36: A. Metwally, D. Agrawal, and A. El Abbadi. Hide and Seek: Detecting Hit Inflation Fraud in Streams of Web Advertising Networks. Technical Report 2006-06, University of California, Santa Barbara, Department of Computer Science, 2006.
• 37: J. Moon and L. Moser. On cliques in graphs. Israel journal of Mathematics, 3:23--28, 1965.
• 38: M. Naor and B. Pinkas. Secure and Efficient Metering. In Proceedings EUROCRYPT International Conference on the Theory and Application of Cryptographic Techniques, pages 576--590, 1998.
• 39: S. Olsen. Click Fraud Roils Search Advertisers. CNET News, March 4 2005.
• 40: Michael K. Reiter , Vinod Anupam , Alain Mayer, Detecting hit shaving in click-through payment schemes, Proceedings of the 3rd conference on USENIX Workshop on Electronic Commerce, p.13-13, August 31-September 03, 1998, Boston, Massachusetts
• 41: Ron Shamir , Roded Sharan , Dekel Tsur, Cluster graph modification problems, Discrete Applied Mathematics, v.144 n.1-2, p.173-182, 30 November 2004 [doi>10.1016/j.dam.2004.01.007]
• 42: J. Sima and S. Schaeffer. On the NP-Completeness of Some Graph Cluster Measures. In Proceedings of the 32nd SOFSEM Conference on Current Trends in Theory and Practice of Informatics, pages 530--537, 2006.
• 43: E. Tomita, A. Tanaka, and H. Takahashi. The Worst-Case Time Complexity for Generating All Maximal Cliques. In Proceedings of the 10th COCOON Annual International Conference on Computing and Combinatorics, pages 161--170, 2004.
• 44: S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa. A New Algorithm for Generating All the Maximal Independent Sets. SIAM Journal on Computing, 6(3):505--517, 1977.
• 45: D. Vise. Clicking To Steal. Washington Post Magazine, page F01, April 17 2005.
• 46: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 47: T. Zeller Jr. With Each Technology Advance, a Scourge. The New York Times, October 18 2004.

INDEX TERMS

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

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security; Payment schemes

General Terms:
Algorithms, Experimentation, Performance, Security

Keywords:
approximate set similarity, click spam detection, cliques enumeration, coalition fraud attacks, real data experiments, similarity-sensitive sampling