Attack detection in time series for recommender systems

ABSTRACT

Recent research has identified significant vulnerabilities in recommender systems. Shilling attacks, in which attackers introduce biased ratings in order to influence future recommendations, have been shown to be effective against collaborative filtering algorithms. We postulate that the distribution of item ratings in time can reveal the presence of a wide range of shilling attacks given reasonable assumptions about their duration. To construct a time series of ratings for an item, we use a window size of k to group consecutive ratings for the item into disjoint windows and compute the sample average and sample entropy in each window. We derive a theoretically optimal window size to best detect an attack event if the number of attack profiles is known. For practical applications where this number is unknown, we propose a heuristic algorithm that adaptively changes the window size. Our experimental results demonstrate that monitoring rating distributions in time series is an effective approach for detecting shilling attacks.

REFERENCES

• 1: András Antos , Ioannis Kontoyiannis, Convergence properties of functional estimates for discrete distributions, Random Structures & Algorithms, v.19 n.3-4, p.163-193, October-December 2001 [doi>10.1002/rsa.10019]
• 2: G. Basarin. On a statistical estimate for the entropy of a sequence of independent random variables. Theory of Probability and Its Applications, 4(3):333--336, 1959.
• 3: P. J. Brockwell and R. A. Davis. Introduction to Time Series and Forecasting. Springer, 2nd edition, 2002.
• 4: Jake D. Brutlag, Aberrant Behavior Detection in Time Series for Network Monitoring, Proceedings of the 14th USENIX conference on System administration, December 03-08, 2000, New Orleans, Louisiana
• 5: Robin Burke , Bamshad Mobasher , Runa Bhaumik , Chad Williams, Segment-Based Injection Attacks against Collaborative Filtering Recommender Systems, Proceedings of the Fifth IEEE International Conference on Data Mining, p.577-580, November 27-30, 2005 [doi>10.1109/ICDM.2005.127]
• 6: Paul-Alexandru Chirita , Wolfgang Nejdl , Cristian Zamfir, Preventing shilling attacks in online recommender systems, Proceedings of the 7th annual ACM international workshop on Web information and data management, November 04-04, 2005, Bremen, Germany [doi>10.1145/1097047.1097061]
• 7: Eamonn Keogh , Jessica Lin , Ada Fu, HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence, Proceedings of the Fifth IEEE International Conference on Data Mining, p.226-233, November 27-30, 2005 [doi>10.1109/ICDM.2005.79]
• 8: Anukool Lakhina , Mark Crovella , Christophe Diot, Mining anomalies using traffic feature distributions, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 9: Shyong K. Lam , John Riedl, Shilling recommender systems for fun and profit, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988726]
• 10: B. Mobasher, R. Burke, C. Williams, and R. Bhaumik. Analysis and detection of segment-focused attacks against collaborative recommendation. In Proceedings of the 2005 WebKDD Workshop (Lecture Notes in Computer Science), 2006.
• 11: Michael O'Mahony , Neil Hurley , Nicholas Kushmerick , Guénolé Silvestre, Collaborative recommendation: A robustness analysis, ACM Transactions on Internet Technology (TOIT), v.4 n.4, p.344-377, November 2004 [doi>10.1145/1031114.1031116]
• 12: L. Wasserman. All of Statistics: A Concise Course in Statistical Inference. Springer, 2004.
• 13: Sheng Zhang , Yi Ouyang , James Ford , Fillia Makedon, Analysis of a low-dimensional linear model under recommendation attacks, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148259]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Commercial services

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

General Terms:
Algorithms, Security

Keywords:
anomaly detection, recommender systems, shilling attacks, time series