• 1.Tutorial on Robustness of Recommender Systems Tutorial on Robustness of RecommenderSystems Neil HurleyComplex Adaptive System Laboratory Computer Science and Informatics University College DublinClique Strategic Research Cluster clique.ucd.ieOctober 2011RecSys 2011: Tutorial on Recommender Robustness
  • 2. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring RobustnessRecSys 2011: Tutorial on Recommender Robustness
  • 3. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 4. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit AnalysisRecSys 2011: Tutorial on Recommender Robustness
  • 5. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4 Robustness of Model-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 6. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 7. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 8. Tutorial on Robustness of Recommender SystemsWhat is Robustness?Outline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 9. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4Robustness of Model-based Algorithms 5Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant Algorithms 6Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 10. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksDefining the ProblemRecommender Systems use personal information aboutend-users to make useful personalised recommendations.When ratings are provided explicitly, recommender algorithmshave been designed on the assumption that the providedinformation is correct.However . . .“One can have, some claim, as many electronic per-sonas as one has time and energy to create”–Judith Donath (1998) as quoted in Douceur (2002)How does the system perform if multiple identities are used totry to deliberately bias the recommender output?RecSys 2011: Tutorial on Recommender Robustness
  • 11. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksDefining the ProblemIn 2002, John Douceur of Microsoft Research coined the termSybil Attack to refer to an attack against identity onpeer-to-peer systems in which an individual entitymasquerades as multiple separate entities“If the local entity has no direct physical knowledge of remote entities, it perceives them onlyas informational abstractions that we call identities. The system must ensure that distinctidentities refer to distinct entities; otherwise, when the local entity selects a subset of identitiesto redundantly perform a remote operation, it can be duped into selecting a single remoteentity multiple times, thereby defeating the redundancy”In the same year, the first paper (O’Mahony et al. 2002)appeared on the vulnerability of Recommender Systems tomalicious strategies for “recommendation promotion” – laterdubbed profile injection attacks.RecSys 2011: Tutorial on Recommender Robustness
  • 12. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksDefining the ProblemRobustness refers to the ability of a system to operate understressful conditions.While there are many possible stresses that can be applied toRecommender Systems, research on RS robustness hasfocused on performance when the dataset is stressedspecifically whenthe dataset is full of noisy, erroneous data;typically, imagined to have been corrupted through a concertedsybil attack, with an aim of biasing the recommender output.RecSys 2011: Tutorial on Recommender Robustness
  • 13. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackRecSys 2011: Tutorial on Recommender Robustness
  • 14. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.RecSys 2011: Tutorial on Recommender Robustness
  • 15. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.RecSys 2011: Tutorial on Recommender Robustness
  • 16. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeRecSys 2011: Tutorial on Recommender Robustness
  • 17. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeA Product Push attack: attempt to secure positiverecommendations for an item or items;RecSys 2011: Tutorial on Recommender Robustness
  • 18. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeA Product Push attack: attempt to secure positiverecommendations for an item or items;A Product Nuke attack: attempt to secure negativerecommendations for an item or items.RecSys 2011: Tutorial on Recommender Robustness
  • 19. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeA Product Push attack: attempt to secure positiverecommendations for an item or items;A Product Nuke attack: attempt to secure negativerecommendations for an item or items.We can also think of attacks that aim to simply destroy theaccuracy of the system.RecSys 2011: Tutorial on Recommender Robustness
  • 20. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.RecSys 2011: Tutorial on Recommender Robustness
  • 21. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsRecSys 2011: Tutorial on Recommender Robustness
  • 22. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsFocus is on the recommendation algorithm’s ability to resistmanipulation either byRecSys 2011: Tutorial on Recommender Robustness
  • 23. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsFocus is on the recommendation algorithm’s ability to resistmanipulation either byIdentifying false profiles from their statistical properties andignoring or lessening their impact on the generation ofrecommendations;RecSys 2011: Tutorial on Recommender Robustness
  • 24. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsFocus is on the recommendation algorithm’s ability to resistmanipulation either byIdentifying false profiles from their statistical properties andignoring or lessening their impact on the generation ofrecommendations; orGenerating recommendations in a manner that is inherentlyinsensitive to manipulation.RecSys 2011: Tutorial on Recommender Robustness
  • 25. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness
  • 26. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness
  • 27. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness
  • 28. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThreats to Reputation Systems IIt is interesting to compare the scenario studied in RS researchwith the threats identified for reputation systems in the 2007ENISA report (Carrara and Hogben 2007):1 Whitewashing attack: reseting a poor reputation byrejoining the system with a new identity.2 Sybil attack or pseudospoofing: the attacker uses multipleidentities (sybils) in order to manipulate a reputation score.3 Impersonation and reputation theft: acquiring the identityof another and stealing her reputation.4 Bootstrap issues and related threats: the initial reputationof a newcomer may be particularly vulnerable to attack.RecSys 2011: Tutorial on Recommender Robustness
  • 29. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThreats to Reputation Systems II5 Extortion: co-ordinated campaigns aimed at blackmail bydamaging an individual’s reputation for malicious motives.6 Denial-of-reputation: attack designed to damage reputationand create an opportunity for blackmail in order to have thereputation cleaned.7 Ballot stuffing and bad mouthing: reporting of a falsereputation score; the attackers collude to givepositive/negative feedback, to increase or lower a reputation.8 Collusion: multiple users conspire to influence a givenreputation.9 Repudiation of data and transaction: denial that atransaction occurred, or denial of the existence of data forwhich individual is responsible.RecSys 2011: Tutorial on Recommender Robustness
  • 30. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThreats to Reputation Systems III 10 Recommender dishonesty: dishonest reputation scoring. 11 Privacy threats for voters and reputation owners: forexample, anonymity improves the accuracy of votes. 12 Social threats: Discriminatory behaviour, herd behaviour,penalisation of innovative, controversial opinions, vocalminority effect etc. 13 Threats to the underlying networks: e.g. denial of serviceattack. 14 Trust topology threats: e.g.targeting most highly influentialnodes. 15 Threats to ratings: exploiting features of metrics used bythe system to calculate the aggregate reputation ratingRecSys 2011: Tutorial on Recommender Robustness
  • 31. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costRecSys 2011: Tutorial on Recommender Robustness
  • 32. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;RecSys 2011: Tutorial on Recommender Robustness
  • 33. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;RecSys 2011: Tutorial on Recommender Robustness
  • 34. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;RecSys 2011: Tutorial on Recommender Robustness
  • 35. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toRecSys 2011: Tutorial on Recommender Robustness
  • 36. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toThe number of sybil profiles created ;RecSys 2011: Tutorial on Recommender Robustness
  • 37. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toThe number of sybil profiles created ;the total number of constituent ratings within the sybil profiles.RecSys 2011: Tutorial on Recommender Robustness
  • 38. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksImpact Curve Figure: Impact curve from Burke et al. (2011)RecSys 2011: Tutorial on Recommender Robustness
  • 39. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationConsider R to be an n × m database of ratings provided by aset of n genuine users for m items in a system catalogue.RecSys 2011: Tutorial on Recommender Robustness
  • 40. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet G be the set of n genuine users, and letra = (ra,1 , . . . , ra,m )T represent the set of ratings provided byuser a for each item.ra,i ∈ L, some quality label, typically a numerical value oversome discrete range. Write ra,i = ∅ if user a has not rateditem i.RecSys 2011: Tutorial on Recommender Robustness
  • 41. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet A be the set of attack profiles of size nA = number ofprofiles and mA = number of ratings. Let ai denote a singleattack profile 1 ≤ i ≤ nA .RecSys 2011: Tutorial on Recommender Robustness
  • 42. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet R be the (n + nA ) × m database of genuine and attackprofiles available to the recommendation algorithmpost-attack.RecSys 2011: Tutorial on Recommender Robustness
  • 43. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.RecSys 2011: Tutorial on Recommender Robustness
  • 44. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.RecSys 2011: Tutorial on Recommender Robustness
  • 45. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.RecSys 2011: Tutorial on Recommender Robustness
  • 46. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.Let l(φ(., R , .), φ(., R, .)) be a loss function representing thequality loss of the recommendation process due to an attack.RecSys 2011: Tutorial on Recommender Robustness
  • 47. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.Let l(φ(., R , .), φ(., R, .)) be a loss function representing thequality loss of the recommendation process due to an attack.This function may depend on the goal of the attack e.g. theoverall loss in accuracy, if the attack seeks to distort generalrecommendation performance,RecSys 2011: Tutorial on Recommender Robustness
  • 48. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.Let l(φ(., R , .), φ(., R, .)) be a loss function representing thequality loss of the recommendation process due to an attack.This function may depend on the goal of the attack e.g. theoverall loss in accuracy, if the attack seeks to distort generalrecommendation performance,or the shift in ratings for some targeted set of items over sometargeted set of users, in a focused attack.RecSys 2011: Tutorial on Recommender Robustness
  • 49. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommender Attack GameThen the manipulation game, from the attacker’s point ofview is to choose the attack A∗ that maximises the loss for agiven cost bound cmax .Attack GoalA∗ = arg max{A|cA ≤cmax } minφ l(φ(R ), φ(R))RecSys 2011: Tutorial on Recommender Robustness
  • 50. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommender Attack GameThen the manipulation game, from the attacker’s point ofview is to choose the attack A∗ that maximises the loss for agiven cost bound cmax .Attack GoalA∗ = arg max{A|cA ≤cmax } minφ l(φ(R ), φ(R))While the system designer strives to find a recommendationalgorithm that militates against attackDefense Goalφ∗ = arg minφ max{A|cA ≤cmax } l(φ(R ), φ(R))RecSys 2011: Tutorial on Recommender Robustness
  • 51. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 52. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessOur Original MotivationInspired by Work in Digital Watermarking . . .RecSys 2011: Tutorial on Recommender Robustness
  • 53. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessOur Original MotivationInspired by Work in Digital Watermarking . . .RecSys 2011: Tutorial on Recommender Robustness
  • 54. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?news.bbc.co.uk/2/hi/4741259.stm (2001) “ ... ads for films including Hollow Man and A Knight’s Tale quotedpraise from a reviewer called David Manning, who was exposed as being invented ...”RecSys 2011: Tutorial on Recommender Robustness
  • 55. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/3d6d969 (Sept. 2003) “AuctionBytes conducted a reader survey to find out how seriousthese problems were. According to the survey, 39% of respondents felt that feedback retaliation was a very bigproblem on eBay. Nineteen percent of respondents had received retaliatory feedback within the previous 6months, and 16% had been a victim of feedback extortion within the previous 6 months.”RecSys 2011: Tutorial on Recommender Robustness
  • 56. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/n3d5lp (June 2009) “Elsevier officials said Monday that it was a mistake for the publishinggiant’s marketing division to offer $25 Amazon gift cards to anyone who would give a new textbook five stars in areview posted on Amazon or Barnes & Noble. While those popular Web sites’ customer reviews have long beenknown to be something less than scientific, and prone to manipulation if an author has friends write on behalf ofa new work, the idea that a major academic publisher would attempt to pay for good reviews angered someprofessors who received the e-mail pitch..”RecSys 2011: Tutorial on Recommender Robustness
  • 57. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/cfmqce (2009) Paul Lamere cites an example of “precision hacking” of a Time Poll.RecSys 2011: Tutorial on Recommender Robustness
  • 58. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/mupy7d (2009) Hotel review manipulationRecSys 2011: Tutorial on Recommender Robustness
  • 59. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?Lang et al. (2010) Social Manipulation in Buzznet “...Hey, I know you don’t know me, but could you do me ahuge fav and vote for me in this contest? All you have to do is buzz me...”RecSys 2011: Tutorial on Recommender Robustness
  • 60. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?All examples of types of manipulation attacks onrecommender systems.No hard evidence of automated shilling attacks by sybilinsertion bots.RecSys 2011: Tutorial on Recommender Robustness
  • 61. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 62. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessSimple Measures of Attack ImpactAverage Prediction ShiftThe change in an item’s predicted rating before and after attack,averaged over all predictions or over predictions that are targettedby the attack.pshift (u, i) = φ(i, R , ru ) − φ(i, R, ru )RecSys 2011: Tutorial on Recommender Robustness
  • 63. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessSimple Measures of Attack ImpactAverage Prediction ShiftThe change in an item’s predicted rating before and after attack,averaged over all predictions or over predictions that are targettedby the attack.pshift (u, i) = φ(i, R , ru ) − φ(i, R, ru )Average Hit RatioThe average likelihood over tested users that a top-Nrecommendation will recommend an item that is the target of anattack. For each such item i and each tested user, u, in a test setof t users, let h(u, i) = 1 if i ∈ Ru , the recommended set. Then,H(i) = 1 u∈U h(u, i) tRecSys 2011: Tutorial on Recommender Robustness
  • 64. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessOther Measures of Attack ImpactConsidering φ(i, R, ru ) as a pmf over L, attack impact can bemeasured in terms of the change in this distribution as aresult of the attack.For instance (Yan and Roy 2009), measure impact in terms ofthe average Kullback-Liebler distance between φ(i, R, ru ) andφ(i, R , ru ) over the set of inspected items.Resnick and Sami (2007) propose loss functions L(l, q) wherel ∈ L, q = φ(i, R, ru ) where the true label of item i is lRecSys 2011: Tutorial on Recommender Robustness
  • 65. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessOther Measures of Attack ImpactConsidering φ(i, R, ru ) as a pmf over L, attack impact can bemeasured in terms of the change in this distribution as aresult of the attack.For instance (Yan and Roy 2009), measure impact in terms ofthe average Kullback-Liebler distance between φ(i, R, ru ) andφ(i, R , ru ) over the set of inspected items.Resnick and Sami (2007) propose loss functions L(l, q) wherel ∈ L, q = φ(i, R, ru ) where the true label of item i is l e.g. the quadratic loss over a two rating scale [HI, LO], with q the probability of HI is given by L(HI, q) = (1 − q)2 ; L(LO, q) = q 2RecSys 2011: Tutorial on Recommender Robustness
  • 66. Tutorial on Robustness of Recommender SystemsAttack StrategiesOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 67. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:RecSys 2011: Tutorial on Recommender Robustness
  • 68. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:IT , the target item(s) receive typically the maximum (resp.minimum) rating for a push (resp. nuke) attack.RecSys 2011: Tutorial on Recommender Robustness
  • 69. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:IS , the selected item(s) are chosen and rated in a manner tosupport the attack.RecSys 2011: Tutorial on Recommender Robustness
  • 70. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:IF , the filler items(s) fill out the remainder of the ratings inthe attack profile.RecSys 2011: Tutorial on Recommender Robustness
  • 71. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;RecSys 2011: Tutorial on Recommender Robustness
  • 72. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .RecSys 2011: Tutorial on Recommender Robustness
  • 73. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerRecSys 2011: Tutorial on Recommender Robustness
  • 74. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerTypically assume some knowledge of the statistics of the ratingdatabase is available;RecSys 2011: Tutorial on Recommender Robustness
  • 75. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerTypically assume some knowledge of the statistics of the ratingdatabase is available;May also have knowledge of the recommendation algorithm –an informed attack.RecSys 2011: Tutorial on Recommender Robustness
  • 76. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerTypically assume some knowledge of the statistics of the ratingdatabase is available;May also have knowledge of the recommendation algorithm –an informed attack.Note Kerkchoff’s principal – avoid “security throughobscurity”.RecSys 2011: Tutorial on Recommender Robustness
  • 77. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 78. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackThe first CF profile insertion attack (O’Mahony et al. 2002),was an informed attack that exploited a particular weakness inthe basic version of Resnick’s user-based kNN algorithm.RecSys 2011: Tutorial on Recommender Robustness
  • 79. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackThe first CF profile insertion attack (O’Mahony et al. 2002),was an informed attack that exploited a particular weakness inthe basic version of Resnick’s user-based kNN algorithm.User-based CF predicts a rating pa,j for item j, user a asfollows:RecSys 2011: Tutorial on Recommender Robustness
  • 80. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackThe first CF profile insertion attack (O’Mahony et al. 2002),was an informed attack that exploited a particular weakness inthe basic version of Resnick’s user-based kNN algorithm.User-based CF predicts a rating pa,j for item j, user a asfollows:– Form a neighbourhood by picking the top-k most similar usersto a– Pearson CorrelationP j (ra,j −¯a )(ri,j −¯i )rr wa,i = √P 2 P2 j∈Na ∩Ni (ra,j −¯a ) rj (ri,j −¯i ) r– Make a prediction by taking a weighted average of nneighbours ratings using: pa,j = ra + κ i=1 wa,i (ri,j − ri ) ¯ ¯where κ is a normalising factorRecSys 2011: Tutorial on Recommender Robustness
  • 81. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.RecSys 2011: Tutorial on Recommender Robustness
  • 82. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.Therefore a small profile of popular items will have a largecorrelation with users who have rated these itemsRecSys 2011: Tutorial on Recommender Robustness
  • 83. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.Therefore a small profile of popular items will have a largecorrelation with users who have rated these itemsImplies a low-cost, effective attack on a large proportion ofthe userbase.RecSys 2011: Tutorial on Recommender Robustness
  • 84. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.Therefore a small profile of popular items will have a largecorrelation with users who have rated these itemsImplies a low-cost, effective attack on a large proportion ofthe userbase.However, not at all unobtrusive.RecSys 2011: Tutorial on Recommender Robustness
  • 85. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Random Attack Randomly chosen filler items get randomlydrawn rating values.RecSys 2011: Tutorial on Recommender Robustness
  • 86. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Average Attack Randomly chosen filler items. Ratings drawn from normal distribution with item means set to those of rating database.RecSys 2011: Tutorial on Recommender Robustness
  • 87. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Probe Attack Filler items filled by starting with a set of seed ratings, querying the recommender system to fill the ratings of the remaining items.RecSys 2011: Tutorial on Recommender Robustness
  • 88. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows: Segment Attack Identifying popular items in a particular usersegment, these are given maximum ratingand remaining filler items are given minimumrating.RecSys 2011: Tutorial on Recommender Robustness
  • 89. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Bandwagon Attack A set of popular items is given the maximum rating, while remaining filler items are given random ratings.RecSys 2011: Tutorial on Recommender Robustness
  • 90. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsEvaluation User-based kNNToward Trustworthy Recommender Systems• 23:21Fig. 8. Comparison of attacks against user-based algorithm, prediction shift (left) and hit ratio(right). The baseline in the right panel indicatesMovielens 100K dataset. User-based kNN algorithm withResults from (Mobasher et al. 2007) on the the hit ratio results prior to attack.k = 20. All users who have rated at least 20 items.target item. The fillerasize, in as a percentagenumber total numberof the remaining items shown Attack Size given as percentage of the total for different filler sizes, written this case, is the proportionthe dataset on the x-axis. Results of theof users inof items.that are assigned random ratings based on the overall data distribution across Bandwagon attack uses a single popular item and 3% filler size.the whole database (see Figure 4). In the case of the MovieLens data, thesefrequently-ratedto hit-ratio pre-attack Baseline refersitems are predictable box office successes including such titlesas Star Wars, Return of Jedi, Titanic, etc. The attack profiles consist of highratings given to these popular titles in conjunction with high ratings for thepushed movie. Figure 7 shows the effect of filler size on the effectiveness ofRecSys 2011: Tutorial on Recommender Robustness
  • 91. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsEvaluation Item-based kNNResults from (Mobasher et al. 2007) on the Movielens 100K dataset. Item-based kNN algorithm withk = 20.RecSys 2011: Tutorial on Recommender Robustness
  • 92. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsEvaluation Item-based kNNToward Trustworthy Recommender Systems• 23:23Fig. 10. Prediction shift and hit 2007) resultsMovielenshorror dataset.segment in kNN item-basedResults from (Mobasher et al. ratio on the for the 100K movie Item-based the algorithm withalgorithm. 20.k=Prediction shift and hit ratio results for the Horror Movie Segment.the target item for use as the segment portion of the attack profile IS . In therealm of movies, we might imagine selecting movies of a similar genre or moviescontaining the same actors. If we evaluate the segmented attack based on its average impact on all users,there is nothing remarkable. The attack has an effect but does not approach thenumbers reached by the average attack. However, we must recall our marketsegment assumption: namely, that recommendations made to in-segment usersare much more useful to the attacker than recommendations to other users. Ourfocus must therefore be with the “in-segment” users, those users who have ratedRecSys 2011: Tutorial on Recommender Robustness
  • 93. Tutorial on Robustness of Recommender SystemsAttack DetectionOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 94. Tutorial on Robustness of Recommender SystemsAttack DetectionProfile Injection Attacks Two well-studied attacks : Construct spam profile with max (or min) rating for targeted item. Choose a set of filler items at randomRandom Attack – insert ratings in filler items according to N (µ, σ)Average Attack – insert ratings in filler item i according to N (µi , σi )For evaluations, genuine profiles are drawn from 1,000,000rating Movielens dataset.RecSys 2011: Tutorial on Recommender Robustness
  • 95. Tutorial on Robustness of Recommender SystemsAttack DetectionDetection FlowRecSys 2011: Tutorial on Recommender Robustness
  • 96. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 97. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)A method of identifying and removing a cluster ofhighly-correlated attack profiles. A cluster C defined by an indicator vector x such that xi = 1 if user ui ∈ C and xi = 0 otherwise. S a profile similarity matrix, with eigenvectors/values ei , λi Quadratic form mT x Sx =S(i, j) = (x.ei )2 λi . i∈C,j∈C i=1Find x that correlates most with first few eigenvectors of S.RecSys 2011: Tutorial on Recommender Robustness
  • 98. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)Success of PCA depends on how S is calculated.S = Z0 , covariance of profiles ignoring missing values.RecSys 2011: Tutorial on Recommender Robustness
  • 99. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)Success of PCA depends on how S is calculated.S = Z1 , covariance of profiles treating missing values as 0.RecSys 2011: Tutorial on Recommender Robustness
  • 100. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)Success of PCA depends on how S is calculated.Small Overlap → low genuine/attack covariance.RecSys 2011: Tutorial on Recommender Robustness
  • 101. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4Robustness of Model-based Algorithms 5Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant Algorithms 6Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 102. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionNeyman-Pearson Statistical Detectiony ∈ Y be an observation i.e. a user profile over all possibleprofiles YTwo hypotheses H0 – that y is a genuine profile, associated pdf fY|H1 (y) H1 – that y is an attack profile, associated pdf fY|H0 (y)N-P criterion sets a bound α on false alarm probability pf andmaximises the good detection probability pDH1 if l(y) > η fY|H1 (y) ψ ∗ (y) =where l(y) = fY|H0 (y)H0 if l(y) < η (likelihood ratio)RecSys 2011: Tutorial on Recommender Robustness
  • 103. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Attack ProfilesAs attacks follow well-defined construction, easy to constructmodel: mPr[Yi = yi ] i=1m= Pr[Yi = φ]θi (Pr[Yi = yi |Yi = φ]Pr[Yi = φ])1−θi i=1Which items are rated?RecSys 2011: Tutorial on Recommender Robustness
  • 104. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Attack ProfilesAs attacks follow well-defined construction, easy to constructmodel: mPr[Yi = yi ] i=1m= Pr[Yi = φ]θi (Pr[Yi = yi |Yi = φ]Pr[Yi = φ])1−θi i=1What ratings used?RecSys 2011: Tutorial on Recommender Robustness
  • 105. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Attack ProfilesAs attacks follow well-defined construction, easy to constructmodel:m Pr[Yi = yi ] i=1m 1 1 1−θiθi yi − 2− µiyi + 2− µi=Pr[Yi = φ]Q−Qσiσi i=1Q(.) = Gaussian Q-functionRecSys 2011: Tutorial on Recommender Robustness
  • 106. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Genuine ProfilesSimple model – identical to attack model except thatprobability of selecting a filler item is estimated aspi Pr[Yi = φ] from a dataset of genuine profiles.ˆ mPr[Yi = yi ]i=1 m= pi θi (Pr[Yi = yi |Yi = φ](1 − pi ))1−θiˆˆi=1Not a realistic model of genuine ratings – assumes user’sratings are all independentBut sufficient (almost) to distinguish from attack profiles.RecSys 2011: Tutorial on Recommender Robustness
  • 107. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionRandom Attack (Filler Size=5%)RecSys 2011: Tutorial on Recommender Robustness
  • 108. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAverage Attack (Filler Size=5%)RecSys 2011: Tutorial on Recommender Robustness
  • 109. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionLesson LearnedFiller item selection is key to the success of the standardattacks on k-NN user-based algorithm. Low (attack profile / genuine profile) overlap (few common ratings) makes extreme correlations possible – hence attack profiles are unusually influential. (Basis of original attack proposed in O’Mahony et al. (2002).) But also allows for successful detection – also highly perceptible.RecSys 2011: Tutorial on Recommender Robustness
  • 110. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAttack ObfuscationSeveral obfuscation strategies evaluated previously (Williamset al. 2006).Effective obfuscation must try to reduce the statisticaldifferences between genuine and attack profiles.RecSys 2011: Tutorial on Recommender Robustness
  • 111. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAverage over Popular (AoP) attackIt is clear that a major weakness of the average and randomattacks is their unrealistic selection of filler items.To be imperceptible an attacker must choose items to rate ina similar fashion to genuine users. Average Over Popular Attack – identical to averageattack, but filler items are chosen from x-% most popularitems.AoP is a less perceptible but also less effective attack onkNN user-based algorithm.Nevertheless it does work . . .RecSys 2011: Tutorial on Recommender Robustness
  • 112. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Prediction Shift (Attack Size=3%)RecSys 2011: Tutorial on Recommender Robustness
  • 113. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Hits (rating of ≥ 4) (Attack Size=3%)RecSys 2011: Tutorial on Recommender Robustness
  • 114. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP PCA DetectionRecSys 2011: Tutorial on Recommender Robustness
  • 115. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionImproved Genuine Profile ModelAdopt model that takes account of correlations betweenratings. Assume ratings follow multivariate normal distribution – parameters: µ0 , m-dimensional vector of mean-ratings for each item; and Σ0 , m × m matrix of item correlations. Assume attack profiles also multivariate gaussian with parameters µ1 , Σ1Hence, attacked database can be modelled as a GaussianMixture Model.RecSys 2011: Tutorial on Recommender Robustness
  • 116. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionImproved Genuine Profile ModelDifficulty Very high dimensional vectors Missing values Factor Model : Assume that the rating matrix can berepresented by the linear modelYT = AXT + N , X : n × k matrix, xu,j = extent user u likes category j A : m × k matrix ai,j = extent item i belongs in category j N : independent noise X(i, :) assumed independent normal.Expectation maximisation to learn A from dataset ([Canny,2002]).RecSys 2011: Tutorial on Recommender Robustness
  • 117. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionImproved Genuine Profile ModelN-P test on multivariate normal k-dimensional vectorobtained by projection with A w = AT YT = AT (AXT + N) X : n × k matrix, xu,j = extent user u likes category j A : m × k matrix ai,j = extent item i belongs in category j N : independent noise X(i, :) assumed independent normal.RecSys 2011: Tutorial on Recommender Robustness
  • 118. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionProjection by ClusteringN-P test on multivariate normal k-dimensional vectorobtained by projection with Pw = PT YT Obtain a clustering of item-set into k clusters of similar items. P : n × k projection matrix sums all ratings belonging to a cluster.RecSys 2011: Tutorial on Recommender Robustness
  • 119. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionSupervised AoP DetectionN-P test reduces to(w−µw 0 )T Σw0 −1 (w−µw 0 )−(w−µw 1 )T Σw1 −1 (w−µw 1 ) ηNeed Database of genuine profiles and Database of attack profilesto train the detector.RecSys 2011: Tutorial on Recommender Robustness
  • 120. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Detection (Factor Analysis)Actual attack=20% AoP Attack. Plot shows training ondifferent attack types.RecSys 2011: Tutorial on Recommender Robustness
  • 121. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Detection (Clustering)Actual attack=20% AoP Attack. Plot shows training ondifferent attack types.RecSys 2011: Tutorial on Recommender Robustness
  • 122. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionUnsupervised AoP DetectionUnsupervised Gaussian mixture model to learn modelparameters µw 0 , Σw0 , µw 1 , Σw1 , a0 and a1 , where ai is the probability that a profile belongs in cluster i.Implementation from William Wong, Purdue University,http://web.ics.purdue.edu/~wong17/.RecSys 2011: Tutorial on Recommender Robustness
  • 123. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP DetectionRecSys 2011: Tutorial on Recommender Robustness
  • 124. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 125. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisCost-Benefit AnalysisIn O’Mahony et al. (2006), we examined a simple cost-benefitmodel The ROI for an attack on item j given by: P cj N (nj −nj ) − k∈Ij ck ROIj = P ckk∈Ij Simplify by assuming cp = cq , ∀ p, q ∈ I N (nj −nj ) − sj ROIj = sj sj – total number of ratings inserted in an attack on item j Approximated the fractions nj & nj using count of good predictions and browser-to-buyer conversion probabilityRecSys 2011: Tutorial on Recommender Robustness
  • 126. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisResultsProfitj = c αj (GPj − GPj ) − sj ; c = $10, α = 10%600400 Profit ($)2002 r = 0.98940−2000 200040006000 8000 10000NRecSys 2011: Tutorial on Recommender Robustness
  • 127. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisCost-benefit AnalysisVu et al. (2010) examines the adversarial cost to attacking aranking system in terms of nA = number of profiles andmA =number of ratings.They assume a rating function r(u, i) ∈ {−1, 0, 1} and aquality-popularity score for each itemf (i) = r(u, i)u∈GRecSys 2011: Tutorial on Recommender Robustness
  • 128. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisCost-benefit AnalysisUsing a trust mechanism that can detect a malicious ratingwith probability γ, they show that a ranking function of theform f (i) =r(u, i)t(u, i)u∈G∪Acan be used to design a ranking system in which the minimumadversarial cost in expectation to boost the rank of an itemfrom k to 1 includes the cost of posting mA =nA ratings, with1−2 + γ nA = (x1 + xk )1−γwhere xi denotes the number of honest ratings for item i and is the probability of an erroneous rating.RecSys 2011: Tutorial on Recommender Robustness
  • 129. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 130. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 131. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 132. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 133. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 134. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 135. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 136. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsAttack takes effect when model is re-trained, using corruptedratings database.RecSys 2011: Tutorial on Recommender Robustness
  • 137. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.RecSys 2011: Tutorial on Recommender Robustness
  • 138. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.RecSys 2011: Tutorial on Recommender Robustness
  • 139. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.The user-base is clustered into segments using k-means orPLSA clustering and users matched to closest segmentprofiles.RecSys 2011: Tutorial on Recommender Robustness
  • 140. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.Sybil profiles tend to be clustered into same segment, therebyreducing power of attack.RecSys 2011: Tutorial on Recommender Robustness
  • 141. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.However, as shown in Cheng and Hurley (2009a), a diversifiedattack can create less similar but yet still effective attackprofiles.RecSys 2011: Tutorial on Recommender Robustness
  • 142. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsFrom Mobasher et al. (2006): Evaluation on MovieLens 100K datasetRecSys 2011: Tutorial on Recommender Robustness
  • 143. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based Algorithms From Cheng and Hurley (2009a): Evaluation on MovieLens 1MdatasetRecSys 2011: Tutorial on Recommender Robustness
  • 144. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Matrix FactorisationModern matrix factorization algorithms use a least squaresstep to find the factors. This is known to be sensitive tooutliers.RecSys 2011: Tutorial on Recommender Robustness
  • 145. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Matrix FactorisationCheng and Hurley (2010) Prediction shift of basic Bellkoralgorithm kNN for a single randomly chosen unpopular item.RecSys 2011: Tutorial on Recommender Robustness
  • 146. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsSummary of Robustness Results on Standard AlgorithmsA number of general attack strategies have been proposedthat work effectively in particular on memory-basedalgorithms.RecSys 2011: Tutorial on Recommender Robustness
  • 147. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsSummary of Robustness Results on Standard AlgorithmsA number of general attack strategies have been proposedthat work effectively in particular on memory-basedalgorithms.Standard attacks are generally detectable:RecSys 2011: Tutorial on Recommender Robustness
  • 148. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsSummary of Robustness Results on Standard AlgorithmsA number of general attack strategies have been proposedthat work effectively in particular on memory-basedalgorithms.Standard attacks are generally detectable: Cost effectiveness implies that a sybil profile should be unusually influential.Special purpose (informed) attacks can be tailored towardsparticular CF algorithms e.g. a high diversity attack proved effective against the k-means clustering algorithm.Sybil profiles can be obfuscated to make them less detectable Selection of filler items is Achille’s heal of standard average attack, but also explains its power. Obfuscation reduces the effectiveness of attacks but memory-based algorithms are still vulnerable.RecSys 2011: Tutorial on Recommender Robustness
  • 149. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 150. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.RecSys 2011: Tutorial on Recommender Robustness
  • 151. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account.RecSys 2011: Tutorial on Recommender Robustness
  • 152. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account. An SVD factorization of the rating matrix R requires the following to be solved:arg min R − GHG,HRecSys 2011: Tutorial on Recommender Robustness
  • 153. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account. An SVD factorization of the rating matrix R requires the following to be solved:arg min R − GHG,H Users are flagged as suspicious using PCA clustering.RecSys 2011: Tutorial on Recommender Robustness
  • 154. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account. An SVD factorization of the rating matrix R requires the following to be solved:arg min R − GHG,H Users are flagged as suspicious using PCA clustering. Flagged users do not contribute to the update of right eigenvector – they do not contribute to the model.RecSys 2011: Tutorial on Recommender Robustness
  • 155. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDRecSys 2011: Tutorial on Recommender Robustness
  • 156. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVD ResultsMAE, Prediction Shift and Hit Ratio for 5% Average Attack,7% Filler on Movielens 1MRecSys 2011: Tutorial on Recommender Robustness
  • 157. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsManipulation Resistance Through Robust StatisticsRobust statistics describes an alternative approach to classicalstatistics where the motivation is to produce estimators thatare not unduly affected by small departures from the model.Robust regression uses a bounded cost function which limitsthe effect of outliers.Two ApproachesRecSys 2011: Tutorial on Recommender Robustness
  • 158. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsManipulation Resistance Through Robust StatisticsRobust statistics describes an alternative approach to classicalstatistics where the motivation is to produce estimators thatare not unduly affected by small departures from the model.Robust regression uses a bounded cost function which limitsthe effect of outliers.Two Approaches1 M-estimators – 1 22γ r |r| ≤ γarg min ρ(rij −gi hj ) where ρ(r) =G,H |r| − γ2 |r| > γ rij =0RecSys 2011: Tutorial on Recommender Robustness
  • 159. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsManipulation Resistance Through Robust StatisticsRobust statistics describes an alternative approach to classicalstatistics where the motivation is to produce estimators thatare not unduly affected by small departures from the model.Robust regression uses a bounded cost function which limitsthe effect of outliers.Two Approaches2 Least Trimmed Squares –h arg mine2 (i)where e2 ≤ e2 ≤ · · · ≤ e2 (1)(2)(n)G,Hi=1RecSys 2011: Tutorial on Recommender Robustness
  • 160. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsRobust Statistics Results on Bellkor MethodRecSys 2011: Tutorial on Recommender Robustness
  • 161. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 162. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsThe Influence Limiter (Resnick and Sami 2007)Output of recommendation systemqj passes through aninfluence-limiting process toproduce a modified output qj .˜qj is a weighted average of qj−1˜ ˜and qjThe weighting depends on thereputation that user j hasaccumulated with respect to thetarget.RecSys 2011: Tutorial on Recommender Robustness
  • 163. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsThe Influence Limiter (Resnick and Sami 2007)A scoring function assignsreputation to j based on whetheror not the target actually likes theitem.Tuned so that honest users canreach full credibility after O(log n)steps.The main result states that thetotal impact of n sybils in terms ofperformance reduction is boundedby −neλ .RecSys 2011: Tutorial on Recommender Robustness
  • 164. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmA class of CF algorithms – which the authors’ call linear CFalgorithms – is presented in which the manipulationdistortion is bounded above by1 1n 1−r .where r is the fraction of the data that is generated bymanipulators and n is the number of products that havealready been rated by a user whose future ratings are to bepredicted.“Suppose a CF system that accepts binary ratings predictsfuture ratings correctly 80% of the time in the absence ofmanipulation. If 10% of all ratings are provided bymanipulators, according to our bound, the system can maintaina 75% rate of correct predictions by requiring each new user torate at least 21 products before receiving recommendations.”RecSys 2011: Tutorial on Recommender Robustness
  • 165. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described asRecSys 2011: Tutorial on Recommender Robustness
  • 166. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) aRecSys 2011: Tutorial on Recommender Robustness
  • 167. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) aA PMF over the rating that the active user gives for the νnitem.RecSys 2011: Tutorial on Recommender Robustness
  • 168. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) aDepending on the active user’s current profileRecSys 2011: Tutorial on Recommender Robustness
  • 169. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) athe training set, RRecSys 2011: Tutorial on Recommender Robustness
  • 170. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) athe order in which the user rates items.RecSys 2011: Tutorial on Recommender Robustness
  • 171. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmA probabilistic CF algorithm predicts independently of theorder ν.Let R = (R, Y) be a database divided in proportion (1 − r)to r between R and Y.Then a linear probabilistic CF algorithm is one in whichP (.|rn−1 , (R, Y)) = (1 − r)P (.|rn−1 , R) + rP (.|ra , Y)aa n−1As the active user rates more and more products, his ratings n−1will tend to be distinguished as sampled from P (.|ra , R)and hence the influence of P (.|ran−1 , Y) diminishes as n grows.RecSys 2011: Tutorial on Recommender Robustness
  • 172. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmThe kNN algorithm is not linear and does not satisfy theboundThe Naive Bayes (NB) algorithm is an asymptotically linearCF algorithm.Kernel Density Estimation (KDE) is a linear CF algorithm.RecSys 2011: Tutorial on Recommender Robustness
  • 173. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4Robustness of Model-based Algorithms 5Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant Algorithms 6Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 174. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendationsRecSys 2011: Tutorial on Recommender Robustness
  • 175. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendations in the face of noise in the dataset.RecSys 2011: Tutorial on Recommender Robustness
  • 176. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendations in the face of noise in the dataset. using different training sample;RecSys 2011: Tutorial on Recommender Robustness
  • 177. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendations in the face of noise in the dataset. using different training sample; over time, if new ratings ‘agree’ with past ratingsAdomavicius and Zhang (2010), explores stability from thepoint of view of adding a CF algorithm’s predictions to thedataset as new ratings, and measuring the prediction shiftthat is incurred.RecSys 2011: Tutorial on Recommender Robustness
  • 178. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsAmatriain et al. (2009) carries out a user study of test re-testreliability and shows that inconsistencies negatively impact thequality of the predictions.RecSys 2011: Tutorial on Recommender Robustness
  • 179. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative filteringRecSys 2011: Tutorial on Recommender Robustness
  • 180. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative filtering . . . avoid manipulation by only using rating of trusted users or build trust based on user behaviour (c.f. the Influence Limiter)RecSys 2011: Tutorial on Recommender Robustness
  • 181. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative filtering . . . avoid manipulation by only using rating of trusted users or build trust based on user behaviour (c.f. the Influence Limiter) . . . nevertheless systems based on trust are still manipulatable – tinyurl.com/6z6k6kr two fictitious Facebook users successfully made friends with 95 users within two weeks.RecSys 2011: Tutorial on Recommender Robustness
  • 182. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsPrivacy is an important security concern from thepoint-of-view of the end-userRecSys 2011: Tutorial on Recommender Robustness
  • 183. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsPrivacy is an important security concern from thepoint-of-view of the end-user In Cheng and Hurley (2009b), we demonstrate that a system architecture to support privacy can provide new opportunities for manipulation attacks.RecSys 2011: Tutorial on Recommender Robustness
  • 184. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsPrivacy is an important security concern from thepoint-of-view of the end-user In Cheng and Hurley (2009b), we demonstrate that a system architecture to support privacy can provide new opportunities for manipulation attacks. Differential privacy has been studied in the context of recommender systems by a number of researchers. One approach to differential privacy is the use of robust statistics. The connection to manipulation resistance may be worth pursuing.RecSys 2011: Tutorial on Recommender Robustness
  • 185. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyMore complicated shilling scenariosWe have focused in this tutorial on rating manipulation – thecreation of sybil profiles and ratings that distort arecommendation system’s output.However, in the real world, shilling can have a morecomplicated form. e.g. The text of hotel reviews can be used to persuade users to select certain hotels. Wu et al. (2010) has carried out work on identifying suspicious reviews in TripAdvisor.RecSys 2011: Tutorial on Recommender Robustness
  • 186. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyConclusionWe’ve reviewed research that has been carried out in lastnumber of years on robustness of RS.The conclusions are quite positive from system managers’points-of-view: If desired, recommendation algorithms that are largely manipulation-resistant may be adopted. Filtering strategies can effectively find unusual rating patterns. Obfuscating attack profiles to avoid filtering generally results in less effective attacks.Good recommendation systems are personalised and hence,should be sensitive to the peculiarities of each user’s ratingbehaviour.A system designer needs to find the right balance betweensensitivity to the melting pot of human behaviour andavoiding easy manipulation.RecSys 2011: Tutorial on Recommender Robustness
  • 187. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyThank You My research is sponsored by Science Foundation Ireland under grant 08/SRC/I1407: Clique: Graph and Network Analysis ClusterRecSys 2011: Tutorial on Recommender Robustness
  • 188. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IAdomavicius, G. and Zhang, J.: 2010, On the stability ofrecommendation algorithms, Proceedings of the fourth ACMconference on Recommender systems, RecSys ’10, ACM, NewYork, NY, USA, pp. 47–54.URL: http://doi.acm.org/10.1145/1864708.1864722Amatriain, X., Pujol, J. M. and Oliver, N.: 2009, I like it . . . I like it not: Evaluating user ratings noise in recommender systems, Proceedings of the 17th International Conference on User Modeling, Adaptation, and Personalization: formerly UM and AH, UMAP ’09, Springer-Verlag, Berlin, Heidelberg, pp. 247–258. URL: http://dx.doi.org/10.1007/978-3-642-02247-0 24RecSys 2011: Tutorial on Recommender Robustness
  • 189. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IIBurke, R., O’Mahony, M. P. and Hurley, N. J.: 2011, Robustcollaborative recommendation, in F. Ricci, L. Rokach, B. Shapiraand P. B. Kantor (eds), Recommender Systems Handbook,Springer, pp. 805–835.Carrara, E. and Hogben, G.: 2007, Enisa position paper no.2,reputation-based systems: a security analysis, Technical report,ENISA.Cheng, Z. and Hurley, N.: 2009a, Effective diverse and obfuscatedattacks on model-based recommender systems, in L. D.Bergman, A. Tuzhilin, R. D. Burke, A. Felfernig andL. Schmidt-Thieme (eds), RecSys, ACM, pp. 141–148.RecSys 2011: Tutorial on Recommender Robustness
  • 190. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IIICheng, Z. and Hurley, N.: 2009b, Trading robustness for privacy indecentralized recommender systems, in K. Z. Haigh andN. Rychtyckyj (eds), IAAI, AAAI.Cheng, Z. and Hurley, N.: 2010, Robust collaborative filtering byleast trimmed squares matrix factorisation, Proceedings of theInternational Conference on Tools in Artificial Intelligence.Donath, J.: 1998, Communities in Cyberspace, Routledge, chapterIdentity and Deception in the Virtual Community.Douceur, J.: 2002, The sybil attack, Proceedings of the FirstInternational Workshop on Peer-to-Peer Systems.Lam, S. K. and Riedl, J.: 2004, Shilling recommender systems forfun and profit, In Proceedings of the 13th International WorldWide Web Conference pp. 393–402.RecSys 2011: Tutorial on Recommender Robustness
  • 191. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IVLang, J., Spear, M. and Wu, S. F.: 2010, Social manipulation ofonline recommender systems, Proceedings of the Secondinternational conference on Social informatics, SocInfo’10,Springer-Verlag, Berlin, Heidelberg, pp. 125–139.URL: http://dl.acm.org/citation.cfm?id=1929326.1929336Mehta, B., Hofmann, T. and Fankhauser, P.: 2007, Lies and propaganda: Detecting spam users in collaborative filtering, Proceedings of the 12th international conference on Intelligent user interfaces, pp. 14–21.Mehta, B. and Nejdl, W.: 2008, Attack resistant collaborative filtering, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’08, ACM, New York, NY, USA, pp. 75–82. URL: http://doi.acm.org/10.1145/1390334.1390350RecSys 2011: Tutorial on Recommender Robustness
  • 192. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VMobasher, B., Burke, R., Bhaumik, R. and Williams, C.: 2007, Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness, ACM Transactions on Internet Technology 7(4).Mobasher, B., Burke, R. D. and Sandvig, J. J.: 2006, Model-based collaborative filtering as a defense against profile injection attacks, AAAI, AAAI Press.O’Mahony, M. P., Hurley, N. J. and Silvestre, C. C. M.: 2004, Anevaluation of neighbourhood formation on the performance ofcollaborative filtering, Artificial Intelligence Review21(1), 215–228.RecSys 2011: Tutorial on Recommender Robustness
  • 193. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VIO’Mahony, M. P., Hurley, N. J. and Silvestre, G. C. M.: 2002,Promoting recommendations: An attack on collaborativefiltering, in A. Hameurlain, R. Cicchetti and R. Traunm¨ller u(eds), DEXA, Vol. 2453 of Lecture Notes in Computer Science,Springer, pp. 494–503.O’Mahony, M. P., Hurley, N. J. and Silvestre, G. C. M.: 2006,Attacking recommender systems: The cost of promotion,Workshop on Recommender Systems at the 17th EuropeanConference on Artificial Intelligence (ECAI’06), 28th–29th, Rivadel Garda, Italy.RecSys 2011: Tutorial on Recommender Robustness
  • 194. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VIIResnick, P. and Sami, R.: 2007, The influence limiter: provablymanipulation-resistant recommender systems, RecSys ’07:Proceedings of the 2007 ACM conference on Recommendersystems, ACM, New York, NY, USA, pp. 25–32.Vu, L.-H., Papaioannou, T. and Aberer, K.: 2010, Impact of trustmanagement and information sharing to adversarial cost inranking systems, in M. Nishigaki, A. Jsang, Y. Murayama andS. Marsh (eds), Trust Management IV, Vol. 321 of IFIPAdvances in Information and Communication Technology,Springer Boston, pp. 108–124.RecSys 2011: Tutorial on Recommender Robustness
  • 195. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VIIIWilliams, C., Mobasher, B., Burke, R., Bhaumik, R. and Sandvig, J.: 2006, Detection of obfuscated attacks in collaborative recommender systems, In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI’06) .Wu, G., Greene, D. and Cunningham, P.: 2010, Merging multiple criteria to identify suspicious reviews, in X. Amatriain, M. Torrens, P. Resnick and M. Zanker (eds), RecSys, ACM, pp. 241–244.Yan, X. and Roy, B. V.: 2009, Manipulation robustness ofcollaborative filtering systems, CoRR abs/0903.0064.RecSys 2011: Tutorial on Recommender Robustness
    Please download to view
  • All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
    ...

    Tutorial on Robustness of Recommender Systems

    by neilhurley

    on

    Report

    Download: 0

    Comment: 0

    2,966

    views

    Comments

    Description

    Tutorial given at ACM RecSys 2011 on robustness of recommender algorithms to profile injection / sybil attacks.
    Download Tutorial on Robustness of Recommender Systems

    Transcript

    • 1.Tutorial on Robustness of Recommender Systems Tutorial on Robustness of RecommenderSystems Neil HurleyComplex Adaptive System Laboratory Computer Science and Informatics University College DublinClique Strategic Research Cluster clique.ucd.ieOctober 2011RecSys 2011: Tutorial on Recommender Robustness
  • 2. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring RobustnessRecSys 2011: Tutorial on Recommender Robustness
  • 3. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 4. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit AnalysisRecSys 2011: Tutorial on Recommender Robustness
  • 5. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4 Robustness of Model-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 6. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 7. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 8. Tutorial on Robustness of Recommender SystemsWhat is Robustness?Outline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 9. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4Robustness of Model-based Algorithms 5Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant Algorithms 6Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 10. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksDefining the ProblemRecommender Systems use personal information aboutend-users to make useful personalised recommendations.When ratings are provided explicitly, recommender algorithmshave been designed on the assumption that the providedinformation is correct.However . . .“One can have, some claim, as many electronic per-sonas as one has time and energy to create”–Judith Donath (1998) as quoted in Douceur (2002)How does the system perform if multiple identities are used totry to deliberately bias the recommender output?RecSys 2011: Tutorial on Recommender Robustness
  • 11. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksDefining the ProblemIn 2002, John Douceur of Microsoft Research coined the termSybil Attack to refer to an attack against identity onpeer-to-peer systems in which an individual entitymasquerades as multiple separate entities“If the local entity has no direct physical knowledge of remote entities, it perceives them onlyas informational abstractions that we call identities. The system must ensure that distinctidentities refer to distinct entities; otherwise, when the local entity selects a subset of identitiesto redundantly perform a remote operation, it can be duped into selecting a single remoteentity multiple times, thereby defeating the redundancy”In the same year, the first paper (O’Mahony et al. 2002)appeared on the vulnerability of Recommender Systems tomalicious strategies for “recommendation promotion” – laterdubbed profile injection attacks.RecSys 2011: Tutorial on Recommender Robustness
  • 12. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksDefining the ProblemRobustness refers to the ability of a system to operate understressful conditions.While there are many possible stresses that can be applied toRecommender Systems, research on RS robustness hasfocused on performance when the dataset is stressedspecifically whenthe dataset is full of noisy, erroneous data;typically, imagined to have been corrupted through a concertedsybil attack, with an aim of biasing the recommender output.RecSys 2011: Tutorial on Recommender Robustness
  • 13. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackRecSys 2011: Tutorial on Recommender Robustness
  • 14. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.RecSys 2011: Tutorial on Recommender Robustness
  • 15. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.RecSys 2011: Tutorial on Recommender Robustness
  • 16. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeRecSys 2011: Tutorial on Recommender Robustness
  • 17. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeA Product Push attack: attempt to secure positiverecommendations for an item or items;RecSys 2011: Tutorial on Recommender Robustness
  • 18. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeA Product Push attack: attempt to secure positiverecommendations for an item or items;A Product Nuke attack: attempt to secure negativerecommendations for an item or items.RecSys 2011: Tutorial on Recommender Robustness
  • 19. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser profiles: a profile injection attackAn attack is a concerted effort to bias the results of arecommender system by the insertion of a large number ofprofiles using false identities or sybils.Each identity is referred to as an attack profile.Research has concentrated on attacks designed to achieve aparticular recommendation outcomeA Product Push attack: attempt to secure positiverecommendations for an item or items;A Product Nuke attack: attempt to secure negativerecommendations for an item or items.We can also think of attacks that aim to simply destroy theaccuracy of the system.RecSys 2011: Tutorial on Recommender Robustness
  • 20. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.RecSys 2011: Tutorial on Recommender Robustness
  • 21. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsRecSys 2011: Tutorial on Recommender Robustness
  • 22. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsFocus is on the recommendation algorithm’s ability to resistmanipulation either byRecSys 2011: Tutorial on Recommender Robustness
  • 23. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsFocus is on the recommendation algorithm’s ability to resistmanipulation either byIdentifying false profiles from their statistical properties andignoring or lessening their impact on the generation ofrecommendations;RecSys 2011: Tutorial on Recommender Robustness
  • 24. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse profiles only.We ignore system-level methods (e.g. Captchas) forpreventing the generation of false identities or ratingsFocus is on the recommendation algorithm’s ability to resistmanipulation either byIdentifying false profiles from their statistical properties andignoring or lessening their impact on the generation ofrecommendations; orGenerating recommendations in a manner that is inherentlyinsensitive to manipulation.RecSys 2011: Tutorial on Recommender Robustness
  • 25. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness
  • 26. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness
  • 27. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness
  • 28. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThreats to Reputation Systems IIt is interesting to compare the scenario studied in RS researchwith the threats identified for reputation systems in the 2007ENISA report (Carrara and Hogben 2007):1 Whitewashing attack: reseting a poor reputation byrejoining the system with a new identity.2 Sybil attack or pseudospoofing: the attacker uses multipleidentities (sybils) in order to manipulate a reputation score.3 Impersonation and reputation theft: acquiring the identityof another and stealing her reputation.4 Bootstrap issues and related threats: the initial reputationof a newcomer may be particularly vulnerable to attack.RecSys 2011: Tutorial on Recommender Robustness
  • 29. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThreats to Reputation Systems II5 Extortion: co-ordinated campaigns aimed at blackmail bydamaging an individual’s reputation for malicious motives.6 Denial-of-reputation: attack designed to damage reputationand create an opportunity for blackmail in order to have thereputation cleaned.7 Ballot stuffing and bad mouthing: reporting of a falsereputation score; the attackers collude to givepositive/negative feedback, to increase or lower a reputation.8 Collusion: multiple users conspire to influence a givenreputation.9 Repudiation of data and transaction: denial that atransaction occurred, or denial of the existence of data forwhich individual is responsible.RecSys 2011: Tutorial on Recommender Robustness
  • 30. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThreats to Reputation Systems III 10 Recommender dishonesty: dishonest reputation scoring. 11 Privacy threats for voters and reputation owners: forexample, anonymity improves the accuracy of votes. 12 Social threats: Discriminatory behaviour, herd behaviour,penalisation of innovative, controversial opinions, vocalminority effect etc. 13 Threats to the underlying networks: e.g. denial of serviceattack. 14 Trust topology threats: e.g.targeting most highly influentialnodes. 15 Threats to ratings: exploiting features of metrics used bythe system to calculate the aggregate reputation ratingRecSys 2011: Tutorial on Recommender Robustness
  • 31. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costRecSys 2011: Tutorial on Recommender Robustness
  • 32. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;RecSys 2011: Tutorial on Recommender Robustness
  • 33. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;RecSys 2011: Tutorial on Recommender Robustness
  • 34. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;RecSys 2011: Tutorial on Recommender Robustness
  • 35. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toRecSys 2011: Tutorial on Recommender Robustness
  • 36. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toThe number of sybil profiles created ;RecSys 2011: Tutorial on Recommender Robustness
  • 37. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommendation Attack GameAn attack has an associated context-dependent costreal dollar cost if the insertion of a sybil rating requires thepurchase of the corresponding item;time/effort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toThe number of sybil profiles created ;the total number of constituent ratings within the sybil profiles.RecSys 2011: Tutorial on Recommender Robustness
  • 38. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksImpact Curve Figure: Impact curve from Burke et al. (2011)RecSys 2011: Tutorial on Recommender Robustness
  • 39. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationConsider R to be an n × m database of ratings provided by aset of n genuine users for m items in a system catalogue.RecSys 2011: Tutorial on Recommender Robustness
  • 40. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet G be the set of n genuine users, and letra = (ra,1 , . . . , ra,m )T represent the set of ratings provided byuser a for each item.ra,i ∈ L, some quality label, typically a numerical value oversome discrete range. Write ra,i = ∅ if user a has not rateditem i.RecSys 2011: Tutorial on Recommender Robustness
  • 41. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet A be the set of attack profiles of size nA = number ofprofiles and mA = number of ratings. Let ai denote a singleattack profile 1 ≤ i ≤ nA .RecSys 2011: Tutorial on Recommender Robustness
  • 42. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet R be the (n + nA ) × m database of genuine and attackprofiles available to the recommendation algorithmpost-attack.RecSys 2011: Tutorial on Recommender Robustness
  • 43. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.RecSys 2011: Tutorial on Recommender Robustness
  • 44. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.RecSys 2011: Tutorial on Recommender Robustness
  • 45. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.RecSys 2011: Tutorial on Recommender Robustness
  • 46. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.Let l(φ(., R , .), φ(., R, .)) be a loss function representing thequality loss of the recommendation process due to an attack.RecSys 2011: Tutorial on Recommender Robustness
  • 47. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.Let l(φ(., R , .), φ(., R, .)) be a loss function representing thequality loss of the recommendation process due to an attack.This function may depend on the goal of the attack e.g. theoverall loss in accuracy, if the attack seeks to distort generalrecommendation performance,RecSys 2011: Tutorial on Recommender Robustness
  • 48. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksNotationLet cA = cA (nA , mA ) denote the cost of mounting an attack.The recommendation algorithm may be represented as afunction φ, that uses the rating database R and a user’shistory of previous ratings, ru , to make a set of predictionsp(u, i) = φ(i, R, ru ) ∈ L on the set of items.More generally, φ(.) results in a probability mass function overthe label space L for each predicted item.Let l(φ(., R , .), φ(., R, .)) be a loss function representing thequality loss of the recommendation process due to an attack.This function may depend on the goal of the attack e.g. theoverall loss in accuracy, if the attack seeks to distort generalrecommendation performance,or the shift in ratings for some targeted set of items over sometargeted set of users, in a focused attack.RecSys 2011: Tutorial on Recommender Robustness
  • 49. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommender Attack GameThen the manipulation game, from the attacker’s point ofview is to choose the attack A∗ that maximises the loss for agiven cost bound cmax .Attack GoalA∗ = arg max{A|cA ≤cmax } minφ l(φ(R ), φ(R))RecSys 2011: Tutorial on Recommender Robustness
  • 50. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Profile Injection AttacksThe Recommender Attack GameThen the manipulation game, from the attacker’s point ofview is to choose the attack A∗ that maximises the loss for agiven cost bound cmax .Attack GoalA∗ = arg max{A|cA ≤cmax } minφ l(φ(R ), φ(R))While the system designer strives to find a recommendationalgorithm that militates against attackDefense Goalφ∗ = arg minφ max{A|cA ≤cmax } l(φ(R ), φ(R))RecSys 2011: Tutorial on Recommender Robustness
  • 51. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 52. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessOur Original MotivationInspired by Work in Digital Watermarking . . .RecSys 2011: Tutorial on Recommender Robustness
  • 53. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessOur Original MotivationInspired by Work in Digital Watermarking . . .RecSys 2011: Tutorial on Recommender Robustness
  • 54. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?news.bbc.co.uk/2/hi/4741259.stm (2001) “ ... ads for films including Hollow Man and A Knight’s Tale quotedpraise from a reviewer called David Manning, who was exposed as being invented ...”RecSys 2011: Tutorial on Recommender Robustness
  • 55. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/3d6d969 (Sept. 2003) “AuctionBytes conducted a reader survey to find out how seriousthese problems were. According to the survey, 39% of respondents felt that feedback retaliation was a very bigproblem on eBay. Nineteen percent of respondents had received retaliatory feedback within the previous 6months, and 16% had been a victim of feedback extortion within the previous 6 months.”RecSys 2011: Tutorial on Recommender Robustness
  • 56. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/n3d5lp (June 2009) “Elsevier officials said Monday that it was a mistake for the publishinggiant’s marketing division to offer $25 Amazon gift cards to anyone who would give a new textbook five stars in areview posted on Amazon or Barnes & Noble. While those popular Web sites’ customer reviews have long beenknown to be something less than scientific, and prone to manipulation if an author has friends write on behalf ofa new work, the idea that a major academic publisher would attempt to pay for good reviews angered someprofessors who received the e-mail pitch..”RecSys 2011: Tutorial on Recommender Robustness
  • 57. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/cfmqce (2009) Paul Lamere cites an example of “precision hacking” of a Time Poll.RecSys 2011: Tutorial on Recommender Robustness
  • 58. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?http://tinyurl.com/mupy7d (2009) Hotel review manipulationRecSys 2011: Tutorial on Recommender Robustness
  • 59. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?Lang et al. (2010) Social Manipulation in Buzznet “...Hey, I know you don’t know me, but could you do me ahuge fav and vote for me in this contest? All you have to do is buzz me...”RecSys 2011: Tutorial on Recommender Robustness
  • 60. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Relevance of RobustnessHow Realistic Is this Scenario?All examples of types of manipulation attacks onrecommender systems.No hard evidence of automated shilling attacks by sybilinsertion bots.RecSys 2011: Tutorial on Recommender Robustness
  • 61. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 62. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessSimple Measures of Attack ImpactAverage Prediction ShiftThe change in an item’s predicted rating before and after attack,averaged over all predictions or over predictions that are targettedby the attack.pshift (u, i) = φ(i, R , ru ) − φ(i, R, ru )RecSys 2011: Tutorial on Recommender Robustness
  • 63. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessSimple Measures of Attack ImpactAverage Prediction ShiftThe change in an item’s predicted rating before and after attack,averaged over all predictions or over predictions that are targettedby the attack.pshift (u, i) = φ(i, R , ru ) − φ(i, R, ru )Average Hit RatioThe average likelihood over tested users that a top-Nrecommendation will recommend an item that is the target of anattack. For each such item i and each tested user, u, in a test setof t users, let h(u, i) = 1 if i ∈ Ru , the recommended set. Then,H(i) = 1 u∈U h(u, i) tRecSys 2011: Tutorial on Recommender Robustness
  • 64. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessOther Measures of Attack ImpactConsidering φ(i, R, ru ) as a pmf over L, attack impact can bemeasured in terms of the change in this distribution as aresult of the attack.For instance (Yan and Roy 2009), measure impact in terms ofthe average Kullback-Liebler distance between φ(i, R, ru ) andφ(i, R , ru ) over the set of inspected items.Resnick and Sami (2007) propose loss functions L(l, q) wherel ∈ L, q = φ(i, R, ru ) where the true label of item i is lRecSys 2011: Tutorial on Recommender Robustness
  • 65. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Measuring RobustnessOther Measures of Attack ImpactConsidering φ(i, R, ru ) as a pmf over L, attack impact can bemeasured in terms of the change in this distribution as aresult of the attack.For instance (Yan and Roy 2009), measure impact in terms ofthe average Kullback-Liebler distance between φ(i, R, ru ) andφ(i, R , ru ) over the set of inspected items.Resnick and Sami (2007) propose loss functions L(l, q) wherel ∈ L, q = φ(i, R, ru ) where the true label of item i is l e.g. the quadratic loss over a two rating scale [HI, LO], with q the probability of HI is given by L(HI, q) = (1 − q)2 ; L(LO, q) = q 2RecSys 2011: Tutorial on Recommender Robustness
  • 66. Tutorial on Robustness of Recommender SystemsAttack StrategiesOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 67. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:RecSys 2011: Tutorial on Recommender Robustness
  • 68. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:IT , the target item(s) receive typically the maximum (resp.minimum) rating for a push (resp. nuke) attack.RecSys 2011: Tutorial on Recommender Robustness
  • 69. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:IS , the selected item(s) are chosen and rated in a manner tosupport the attack.RecSys 2011: Tutorial on Recommender Robustness
  • 70. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Profiles(Mobasher et al. 2007) introduce the following notation forthe components of an attack profile:IF , the filler items(s) fill out the remainder of the ratings inthe attack profile.RecSys 2011: Tutorial on Recommender Robustness
  • 71. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;RecSys 2011: Tutorial on Recommender Robustness
  • 72. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .RecSys 2011: Tutorial on Recommender Robustness
  • 73. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerRecSys 2011: Tutorial on Recommender Robustness
  • 74. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerTypically assume some knowledge of the statistics of the ratingdatabase is available;RecSys 2011: Tutorial on Recommender Robustness
  • 75. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerTypically assume some knowledge of the statistics of the ratingdatabase is available;May also have knowledge of the recommendation algorithm –an informed attack.RecSys 2011: Tutorial on Recommender Robustness
  • 76. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProfilesThe goal of attack profile creation must be toEffectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and filtering– selection of the filler items IF .Must also consider what information is available to theattackerTypically assume some knowledge of the statistics of the ratingdatabase is available;May also have knowledge of the recommendation algorithm –an informed attack.Note Kerkchoff’s principal – avoid “security throughobscurity”.RecSys 2011: Tutorial on Recommender Robustness
  • 77. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 78. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackThe first CF profile insertion attack (O’Mahony et al. 2002),was an informed attack that exploited a particular weakness inthe basic version of Resnick’s user-based kNN algorithm.RecSys 2011: Tutorial on Recommender Robustness
  • 79. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackThe first CF profile insertion attack (O’Mahony et al. 2002),was an informed attack that exploited a particular weakness inthe basic version of Resnick’s user-based kNN algorithm.User-based CF predicts a rating pa,j for item j, user a asfollows:RecSys 2011: Tutorial on Recommender Robustness
  • 80. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackThe first CF profile insertion attack (O’Mahony et al. 2002),was an informed attack that exploited a particular weakness inthe basic version of Resnick’s user-based kNN algorithm.User-based CF predicts a rating pa,j for item j, user a asfollows:– Form a neighbourhood by picking the top-k most similar usersto a– Pearson CorrelationP j (ra,j −¯a )(ri,j −¯i )rr wa,i = √P 2 P2 j∈Na ∩Ni (ra,j −¯a ) rj (ri,j −¯i ) r– Make a prediction by taking a weighted average of nneighbours ratings using: pa,j = ra + κ i=1 wa,i (ri,j − ri ) ¯ ¯where κ is a normalising factorRecSys 2011: Tutorial on Recommender Robustness
  • 81. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.RecSys 2011: Tutorial on Recommender Robustness
  • 82. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.Therefore a small profile of popular items will have a largecorrelation with users who have rated these itemsRecSys 2011: Tutorial on Recommender Robustness
  • 83. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.Therefore a small profile of popular items will have a largecorrelation with users who have rated these itemsImplies a low-cost, effective attack on a large proportion ofthe userbase.RecSys 2011: Tutorial on Recommender Robustness
  • 84. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsUser-based kNN AttackCorrelation calculated over the items which the target userand attack profile have in common. A small intersection setcan lead to high correlations.Therefore a small profile of popular items will have a largecorrelation with users who have rated these itemsImplies a low-cost, effective attack on a large proportion ofthe userbase.However, not at all unobtrusive.RecSys 2011: Tutorial on Recommender Robustness
  • 85. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Random Attack Randomly chosen filler items get randomlydrawn rating values.RecSys 2011: Tutorial on Recommender Robustness
  • 86. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Average Attack Randomly chosen filler items. Ratings drawn from normal distribution with item means set to those of rating database.RecSys 2011: Tutorial on Recommender Robustness
  • 87. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Probe Attack Filler items filled by starting with a set of seed ratings, querying the recommender system to fill the ratings of the remaining items.RecSys 2011: Tutorial on Recommender Robustness
  • 88. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows: Segment Attack Identifying popular items in a particular usersegment, these are given maximum ratingand remaining filler items are given minimumrating.RecSys 2011: Tutorial on Recommender Robustness
  • 89. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsOther Attacks StrategiesMany other attack variants proposed by (Lam and Riedl 2004) and(Mobasher et al. 2007). Assuming a push attack – a target item isgiven the maximum rating and the attack profile is filled out asfollows:Bandwagon Attack A set of popular items is given the maximum rating, while remaining filler items are given random ratings.RecSys 2011: Tutorial on Recommender Robustness
  • 90. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsEvaluation User-based kNNToward Trustworthy Recommender Systems• 23:21Fig. 8. Comparison of attacks against user-based algorithm, prediction shift (left) and hit ratio(right). The baseline in the right panel indicatesMovielens 100K dataset. User-based kNN algorithm withResults from (Mobasher et al. 2007) on the the hit ratio results prior to attack.k = 20. All users who have rated at least 20 items.target item. The fillerasize, in as a percentagenumber total numberof the remaining items shown Attack Size given as percentage of the total for different filler sizes, written this case, is the proportionthe dataset on the x-axis. Results of theof users inof items.that are assigned random ratings based on the overall data distribution across Bandwagon attack uses a single popular item and 3% filler size.the whole database (see Figure 4). In the case of the MovieLens data, thesefrequently-ratedto hit-ratio pre-attack Baseline refersitems are predictable box office successes including such titlesas Star Wars, Return of Jedi, Titanic, etc. The attack profiles consist of highratings given to these popular titles in conjunction with high ratings for thepushed movie. Figure 7 shows the effect of filler size on the effectiveness ofRecSys 2011: Tutorial on Recommender Robustness
  • 91. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsEvaluation Item-based kNNResults from (Mobasher et al. 2007) on the Movielens 100K dataset. Item-based kNN algorithm withk = 20.RecSys 2011: Tutorial on Recommender Robustness
  • 92. Tutorial on Robustness of Recommender SystemsAttack Strategies Attacking kNN AlgorithmsEvaluation Item-based kNNToward Trustworthy Recommender Systems• 23:23Fig. 10. Prediction shift and hit 2007) resultsMovielenshorror dataset.segment in kNN item-basedResults from (Mobasher et al. ratio on the for the 100K movie Item-based the algorithm withalgorithm. 20.k=Prediction shift and hit ratio results for the Horror Movie Segment.the target item for use as the segment portion of the attack profile IS . In therealm of movies, we might imagine selecting movies of a similar genre or moviescontaining the same actors. If we evaluate the segmented attack based on its average impact on all users,there is nothing remarkable. The attack has an effect but does not approach thenumbers reached by the average attack. However, we must recall our marketsegment assumption: namely, that recommendations made to in-segment usersare much more useful to the attacker than recommendations to other users. Ourfocus must therefore be with the “in-segment” users, those users who have ratedRecSys 2011: Tutorial on Recommender Robustness
  • 93. Tutorial on Robustness of Recommender SystemsAttack DetectionOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 94. Tutorial on Robustness of Recommender SystemsAttack DetectionProfile Injection Attacks Two well-studied attacks : Construct spam profile with max (or min) rating for targeted item. Choose a set of filler items at randomRandom Attack – insert ratings in filler items according to N (µ, σ)Average Attack – insert ratings in filler item i according to N (µi , σi )For evaluations, genuine profiles are drawn from 1,000,000rating Movielens dataset.RecSys 2011: Tutorial on Recommender Robustness
  • 95. Tutorial on Robustness of Recommender SystemsAttack DetectionDetection FlowRecSys 2011: Tutorial on Recommender Robustness
  • 96. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 97. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)A method of identifying and removing a cluster ofhighly-correlated attack profiles. A cluster C defined by an indicator vector x such that xi = 1 if user ui ∈ C and xi = 0 otherwise. S a profile similarity matrix, with eigenvectors/values ei , λi Quadratic form mT x Sx =S(i, j) = (x.ei )2 λi . i∈C,j∈C i=1Find x that correlates most with first few eigenvectors of S.RecSys 2011: Tutorial on Recommender Robustness
  • 98. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)Success of PCA depends on how S is calculated.S = Z0 , covariance of profiles ignoring missing values.RecSys 2011: Tutorial on Recommender Robustness
  • 99. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)Success of PCA depends on how S is calculated.S = Z1 , covariance of profiles treating missing values as 0.RecSys 2011: Tutorial on Recommender Robustness
  • 100. Tutorial on Robustness of Recommender SystemsAttack Detection PCA-based Attack DetectionPCA Detector (Mehta et al. 2007)Success of PCA depends on how S is calculated.Small Overlap → low genuine/attack covariance.RecSys 2011: Tutorial on Recommender Robustness
  • 101. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4Robustness of Model-based Algorithms 5Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant Algorithms 6Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 102. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionNeyman-Pearson Statistical Detectiony ∈ Y be an observation i.e. a user profile over all possibleprofiles YTwo hypotheses H0 – that y is a genuine profile, associated pdf fY|H1 (y) H1 – that y is an attack profile, associated pdf fY|H0 (y)N-P criterion sets a bound α on false alarm probability pf andmaximises the good detection probability pDH1 if l(y) > η fY|H1 (y) ψ ∗ (y) =where l(y) = fY|H0 (y)H0 if l(y) < η (likelihood ratio)RecSys 2011: Tutorial on Recommender Robustness
  • 103. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Attack ProfilesAs attacks follow well-defined construction, easy to constructmodel: mPr[Yi = yi ] i=1m= Pr[Yi = φ]θi (Pr[Yi = yi |Yi = φ]Pr[Yi = φ])1−θi i=1Which items are rated?RecSys 2011: Tutorial on Recommender Robustness
  • 104. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Attack ProfilesAs attacks follow well-defined construction, easy to constructmodel: mPr[Yi = yi ] i=1m= Pr[Yi = φ]θi (Pr[Yi = yi |Yi = φ]Pr[Yi = φ])1−θi i=1What ratings used?RecSys 2011: Tutorial on Recommender Robustness
  • 105. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Attack ProfilesAs attacks follow well-defined construction, easy to constructmodel:m Pr[Yi = yi ] i=1m 1 1 1−θiθi yi − 2− µiyi + 2− µi=Pr[Yi = φ]Q−Qσiσi i=1Q(.) = Gaussian Q-functionRecSys 2011: Tutorial on Recommender Robustness
  • 106. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionModelling Genuine ProfilesSimple model – identical to attack model except thatprobability of selecting a filler item is estimated aspi Pr[Yi = φ] from a dataset of genuine profiles.ˆ mPr[Yi = yi ]i=1 m= pi θi (Pr[Yi = yi |Yi = φ](1 − pi ))1−θiˆˆi=1Not a realistic model of genuine ratings – assumes user’sratings are all independentBut sufficient (almost) to distinguish from attack profiles.RecSys 2011: Tutorial on Recommender Robustness
  • 107. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionRandom Attack (Filler Size=5%)RecSys 2011: Tutorial on Recommender Robustness
  • 108. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAverage Attack (Filler Size=5%)RecSys 2011: Tutorial on Recommender Robustness
  • 109. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionLesson LearnedFiller item selection is key to the success of the standardattacks on k-NN user-based algorithm. Low (attack profile / genuine profile) overlap (few common ratings) makes extreme correlations possible – hence attack profiles are unusually influential. (Basis of original attack proposed in O’Mahony et al. (2002).) But also allows for successful detection – also highly perceptible.RecSys 2011: Tutorial on Recommender Robustness
  • 110. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAttack ObfuscationSeveral obfuscation strategies evaluated previously (Williamset al. 2006).Effective obfuscation must try to reduce the statisticaldifferences between genuine and attack profiles.RecSys 2011: Tutorial on Recommender Robustness
  • 111. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAverage over Popular (AoP) attackIt is clear that a major weakness of the average and randomattacks is their unrealistic selection of filler items.To be imperceptible an attacker must choose items to rate ina similar fashion to genuine users. Average Over Popular Attack – identical to averageattack, but filler items are chosen from x-% most popularitems.AoP is a less perceptible but also less effective attack onkNN user-based algorithm.Nevertheless it does work . . .RecSys 2011: Tutorial on Recommender Robustness
  • 112. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Prediction Shift (Attack Size=3%)RecSys 2011: Tutorial on Recommender Robustness
  • 113. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Hits (rating of ≥ 4) (Attack Size=3%)RecSys 2011: Tutorial on Recommender Robustness
  • 114. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP PCA DetectionRecSys 2011: Tutorial on Recommender Robustness
  • 115. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionImproved Genuine Profile ModelAdopt model that takes account of correlations betweenratings. Assume ratings follow multivariate normal distribution – parameters: µ0 , m-dimensional vector of mean-ratings for each item; and Σ0 , m × m matrix of item correlations. Assume attack profiles also multivariate gaussian with parameters µ1 , Σ1Hence, attacked database can be modelled as a GaussianMixture Model.RecSys 2011: Tutorial on Recommender Robustness
  • 116. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionImproved Genuine Profile ModelDifficulty Very high dimensional vectors Missing values Factor Model : Assume that the rating matrix can berepresented by the linear modelYT = AXT + N , X : n × k matrix, xu,j = extent user u likes category j A : m × k matrix ai,j = extent item i belongs in category j N : independent noise X(i, :) assumed independent normal.Expectation maximisation to learn A from dataset ([Canny,2002]).RecSys 2011: Tutorial on Recommender Robustness
  • 117. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionImproved Genuine Profile ModelN-P test on multivariate normal k-dimensional vectorobtained by projection with A w = AT YT = AT (AXT + N) X : n × k matrix, xu,j = extent user u likes category j A : m × k matrix ai,j = extent item i belongs in category j N : independent noise X(i, :) assumed independent normal.RecSys 2011: Tutorial on Recommender Robustness
  • 118. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionProjection by ClusteringN-P test on multivariate normal k-dimensional vectorobtained by projection with Pw = PT YT Obtain a clustering of item-set into k clusters of similar items. P : n × k projection matrix sums all ratings belonging to a cluster.RecSys 2011: Tutorial on Recommender Robustness
  • 119. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionSupervised AoP DetectionN-P test reduces to(w−µw 0 )T Σw0 −1 (w−µw 0 )−(w−µw 1 )T Σw1 −1 (w−µw 1 ) ηNeed Database of genuine profiles and Database of attack profilesto train the detector.RecSys 2011: Tutorial on Recommender Robustness
  • 120. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Detection (Factor Analysis)Actual attack=20% AoP Attack. Plot shows training ondifferent attack types.RecSys 2011: Tutorial on Recommender Robustness
  • 121. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP Detection (Clustering)Actual attack=20% AoP Attack. Plot shows training ondifferent attack types.RecSys 2011: Tutorial on Recommender Robustness
  • 122. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionUnsupervised AoP DetectionUnsupervised Gaussian mixture model to learn modelparameters µw 0 , Σw0 , µw 1 , Σw1 , a0 and a1 , where ai is the probability that a profile belongs in cluster i.Implementation from William Wong, Purdue University,http://web.ics.purdue.edu/~wong17/.RecSys 2011: Tutorial on Recommender Robustness
  • 123. Tutorial on Robustness of Recommender SystemsAttack Detection Statistical Attack DetectionAoP DetectionRecSys 2011: Tutorial on Recommender Robustness
  • 124. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 125. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisCost-Benefit AnalysisIn O’Mahony et al. (2006), we examined a simple cost-benefitmodel The ROI for an attack on item j given by: P cj N (nj −nj ) − k∈Ij ck ROIj = P ckk∈Ij Simplify by assuming cp = cq , ∀ p, q ∈ I N (nj −nj ) − sj ROIj = sj sj – total number of ratings inserted in an attack on item j Approximated the fractions nj & nj using count of good predictions and browser-to-buyer conversion probabilityRecSys 2011: Tutorial on Recommender Robustness
  • 126. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisResultsProfitj = c αj (GPj − GPj ) − sj ; c = $10, α = 10%600400 Profit ($)2002 r = 0.98940−2000 200040006000 8000 10000NRecSys 2011: Tutorial on Recommender Robustness
  • 127. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisCost-benefit AnalysisVu et al. (2010) examines the adversarial cost to attacking aranking system in terms of nA = number of profiles andmA =number of ratings.They assume a rating function r(u, i) ∈ {−1, 0, 1} and aquality-popularity score for each itemf (i) = r(u, i)u∈GRecSys 2011: Tutorial on Recommender Robustness
  • 128. Tutorial on Robustness of Recommender SystemsAttack Detection Cost-Benefit AnalysisCost-benefit AnalysisUsing a trust mechanism that can detect a malicious ratingwith probability γ, they show that a ranking function of theform f (i) =r(u, i)t(u, i)u∈G∪Acan be used to design a ranking system in which the minimumadversarial cost in expectation to boost the rank of an itemfrom k to 1 includes the cost of posting mA =nA ratings, with1−2 + γ nA = (x1 + xk )1−γwhere xi denotes the number of honest ratings for item i and is the probability of an erroneous rating.RecSys 2011: Tutorial on Recommender Robustness
  • 129. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 130. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 131. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 132. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 133. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 134. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 135. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness
  • 136. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsModel-based AlgorithmsAttack takes effect when model is re-trained, using corruptedratings database.RecSys 2011: Tutorial on Recommender Robustness
  • 137. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.RecSys 2011: Tutorial on Recommender Robustness
  • 138. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.RecSys 2011: Tutorial on Recommender Robustness
  • 139. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.The user-base is clustered into segments using k-means orPLSA clustering and users matched to closest segmentprofiles.RecSys 2011: Tutorial on Recommender Robustness
  • 140. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.Sybil profiles tend to be clustered into same segment, therebyreducing power of attack.RecSys 2011: Tutorial on Recommender Robustness
  • 141. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsInitial work such as Mobasher et al. (2006) showed thatmodel-based algorithms are more resistant to manipulationthan memory-based algorithms.However, as shown in Cheng and Hurley (2009a), a diversifiedattack can create less similar but yet still effective attackprofiles.RecSys 2011: Tutorial on Recommender Robustness
  • 142. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based AlgorithmsFrom Mobasher et al. (2006): Evaluation on MovieLens 100K datasetRecSys 2011: Tutorial on Recommender Robustness
  • 143. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Model-based Algorithms From Cheng and Hurley (2009a): Evaluation on MovieLens 1MdatasetRecSys 2011: Tutorial on Recommender Robustness
  • 144. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Matrix FactorisationModern matrix factorization algorithms use a least squaresstep to find the factors. This is known to be sensitive tooutliers.RecSys 2011: Tutorial on Recommender Robustness
  • 145. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsManipulation-resistance of Matrix FactorisationCheng and Hurley (2010) Prediction shift of basic Bellkoralgorithm kNN for a single randomly chosen unpopular item.RecSys 2011: Tutorial on Recommender Robustness
  • 146. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsSummary of Robustness Results on Standard AlgorithmsA number of general attack strategies have been proposedthat work effectively in particular on memory-basedalgorithms.RecSys 2011: Tutorial on Recommender Robustness
  • 147. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsSummary of Robustness Results on Standard AlgorithmsA number of general attack strategies have been proposedthat work effectively in particular on memory-basedalgorithms.Standard attacks are generally detectable:RecSys 2011: Tutorial on Recommender Robustness
  • 148. Tutorial on Robustness of Recommender SystemsRobustness of Model-based AlgorithmsSummary of Robustness Results on Standard AlgorithmsA number of general attack strategies have been proposedthat work effectively in particular on memory-basedalgorithms.Standard attacks are generally detectable: Cost effectiveness implies that a sybil profile should be unusually influential.Special purpose (informed) attacks can be tailored towardsparticular CF algorithms e.g. a high diversity attack proved effective against the k-means clustering algorithm.Sybil profiles can be obfuscated to make them less detectable Selection of filler items is Achille’s heal of standard average attack, but also explains its power. Obfuscation reduces the effectiveness of attacks but memory-based algorithms are still vulnerable.RecSys 2011: Tutorial on Recommender Robustness
  • 149. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 150. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.RecSys 2011: Tutorial on Recommender Robustness
  • 151. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account.RecSys 2011: Tutorial on Recommender Robustness
  • 152. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account. An SVD factorization of the rating matrix R requires the following to be solved:arg min R − GHG,HRecSys 2011: Tutorial on Recommender Robustness
  • 153. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account. An SVD factorization of the rating matrix R requires the following to be solved:arg min R − GHG,H Users are flagged as suspicious using PCA clustering.RecSys 2011: Tutorial on Recommender Robustness
  • 154. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDSome early work (O’Mahony et al. 2004) appliedneighbourhood filtering to the standard user-based algorithm,to cluster and filter suspicious neighbours.Mehta and Nejdl (2008) introduces the the VarSelectSVDmethod – a matrix factorisation strategy taking robustnessinto account. An SVD factorization of the rating matrix R requires the following to be solved:arg min R − GHG,H Users are flagged as suspicious using PCA clustering. Flagged users do not contribute to the update of right eigenvector – they do not contribute to the model.RecSys 2011: Tutorial on Recommender Robustness
  • 155. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVDRecSys 2011: Tutorial on Recommender Robustness
  • 156. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsVarSelectSVD ResultsMAE, Prediction Shift and Hit Ratio for 5% Average Attack,7% Filler on Movielens 1MRecSys 2011: Tutorial on Recommender Robustness
  • 157. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsManipulation Resistance Through Robust StatisticsRobust statistics describes an alternative approach to classicalstatistics where the motivation is to produce estimators thatare not unduly affected by small departures from the model.Robust regression uses a bounded cost function which limitsthe effect of outliers.Two ApproachesRecSys 2011: Tutorial on Recommender Robustness
  • 158. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsManipulation Resistance Through Robust StatisticsRobust statistics describes an alternative approach to classicalstatistics where the motivation is to produce estimators thatare not unduly affected by small departures from the model.Robust regression uses a bounded cost function which limitsthe effect of outliers.Two Approaches1 M-estimators – 1 22γ r |r| ≤ γarg min ρ(rij −gi hj ) where ρ(r) =G,H |r| − γ2 |r| > γ rij =0RecSys 2011: Tutorial on Recommender Robustness
  • 159. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsManipulation Resistance Through Robust StatisticsRobust statistics describes an alternative approach to classicalstatistics where the motivation is to produce estimators thatare not unduly affected by small departures from the model.Robust regression uses a bounded cost function which limitsthe effect of outliers.Two Approaches2 Least Trimmed Squares –h arg mine2 (i)where e2 ≤ e2 ≤ · · · ≤ e2 (1)(2)(n)G,Hi=1RecSys 2011: Tutorial on Recommender Robustness
  • 160. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation AlgorithmsRobust Statistics Results on Bellkor MethodRecSys 2011: Tutorial on Recommender Robustness
  • 161. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsOutline 1 What is Robustness? Profile Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Benefit Analysis 4 Robustness of Model-based Algorithms 5 Attack Resistant Recommendation Algorithms Provably Manipulation Resistant Algorithms 6 Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 162. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsThe Influence Limiter (Resnick and Sami 2007)Output of recommendation systemqj passes through aninfluence-limiting process toproduce a modified output qj .˜qj is a weighted average of qj−1˜ ˜and qjThe weighting depends on thereputation that user j hasaccumulated with respect to thetarget.RecSys 2011: Tutorial on Recommender Robustness
  • 163. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsThe Influence Limiter (Resnick and Sami 2007)A scoring function assignsreputation to j based on whetheror not the target actually likes theitem.Tuned so that honest users canreach full credibility after O(log n)steps.The main result states that thetotal impact of n sybils in terms ofperformance reduction is boundedby −neλ .RecSys 2011: Tutorial on Recommender Robustness
  • 164. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmA class of CF algorithms – which the authors’ call linear CFalgorithms – is presented in which the manipulationdistortion is bounded above by1 1n 1−r .where r is the fraction of the data that is generated bymanipulators and n is the number of products that havealready been rated by a user whose future ratings are to bepredicted.“Suppose a CF system that accepts binary ratings predictsfuture ratings correctly 80% of the time in the absence ofmanipulation. If 10% of all ratings are provided bymanipulators, according to our bound, the system can maintaina 75% rate of correct predictions by requiring each new user torate at least 21 products before receiving recommendations.”RecSys 2011: Tutorial on Recommender Robustness
  • 165. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described asRecSys 2011: Tutorial on Recommender Robustness
  • 166. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) aRecSys 2011: Tutorial on Recommender Robustness
  • 167. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) aA PMF over the rating that the active user gives for the νnitem.RecSys 2011: Tutorial on Recommender Robustness
  • 168. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) aDepending on the active user’s current profileRecSys 2011: Tutorial on Recommender Robustness
  • 169. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) athe training set, RRecSys 2011: Tutorial on Recommender Robustness
  • 170. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmLet r ∈ L be a rating in the label space.Let ν be a permutation of the items such that νn is the nthitem rated by an active user, a.Let rn−1 be the active user’s profile after rating n − 1 items. aThen a CF algorithm may be described as P (ra,νn = r|rn−1 , R, ν) athe order in which the user rates items.RecSys 2011: Tutorial on Recommender Robustness
  • 171. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmA probabilistic CF algorithm predicts independently of theorder ν.Let R = (R, Y) be a database divided in proportion (1 − r)to r between R and Y.Then a linear probabilistic CF algorithm is one in whichP (.|rn−1 , (R, Y)) = (1 − r)P (.|rn−1 , R) + rP (.|ra , Y)aa n−1As the active user rates more and more products, his ratings n−1will tend to be distinguished as sampled from P (.|ra , R)and hence the influence of P (.|ran−1 , Y) diminishes as n grows.RecSys 2011: Tutorial on Recommender Robustness
  • 172. Tutorial on Robustness of Recommender SystemsAttack Resistant Recommendation Algorithms Provably Manipulation Resistant AlgorithmsYan and Roy (2009)’s Manipulation Robust AlgorithmThe kNN algorithm is not linear and does not satisfy theboundThe Naive Bayes (NB) algorithm is an asymptotically linearCF algorithm.Kernel Density Estimation (KDE) is a linear CF algorithm.RecSys 2011: Tutorial on Recommender Robustness
  • 173. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyOutline 1 What is Robustness?Profile Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Benefit Analysis 4Robustness of Model-based Algorithms 5Attack Resistant Recommendation AlgorithmsProvably Manipulation Resistant Algorithms 6Stability, Trust and PrivacyRecSys 2011: Tutorial on Recommender Robustness
  • 174. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendationsRecSys 2011: Tutorial on Recommender Robustness
  • 175. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendations in the face of noise in the dataset.RecSys 2011: Tutorial on Recommender Robustness
  • 176. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendations in the face of noise in the dataset. using different training sample;RecSys 2011: Tutorial on Recommender Robustness
  • 177. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsStability refers to a recommender system’s ability to provideconsistent recommendations in the face of noise in the dataset. using different training sample; over time, if new ratings ‘agree’ with past ratingsAdomavicius and Zhang (2010), explores stability from thepoint of view of adding a CF algorithm’s predictions to thedataset as new ratings, and measuring the prediction shiftthat is incurred.RecSys 2011: Tutorial on Recommender Robustness
  • 178. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsAmatriain et al. (2009) carries out a user study of test re-testreliability and shows that inconsistencies negatively impact thequality of the predictions.RecSys 2011: Tutorial on Recommender Robustness
  • 179. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative filteringRecSys 2011: Tutorial on Recommender Robustness
  • 180. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative filtering . . . avoid manipulation by only using rating of trusted users or build trust based on user behaviour (c.f. the Influence Limiter)RecSys 2011: Tutorial on Recommender Robustness
  • 181. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative filtering . . . avoid manipulation by only using rating of trusted users or build trust based on user behaviour (c.f. the Influence Limiter) . . . nevertheless systems based on trust are still manipulatable – tinyurl.com/6z6k6kr two fictitious Facebook users successfully made friends with 95 users within two weeks.RecSys 2011: Tutorial on Recommender Robustness
  • 182. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsPrivacy is an important security concern from thepoint-of-view of the end-userRecSys 2011: Tutorial on Recommender Robustness
  • 183. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsPrivacy is an important security concern from thepoint-of-view of the end-user In Cheng and Hurley (2009b), we demonstrate that a system architecture to support privacy can provide new opportunities for manipulation attacks.RecSys 2011: Tutorial on Recommender Robustness
  • 184. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsPrivacy is an important security concern from thepoint-of-view of the end-user In Cheng and Hurley (2009b), we demonstrate that a system architecture to support privacy can provide new opportunities for manipulation attacks. Differential privacy has been studied in the context of recommender systems by a number of researchers. One approach to differential privacy is the use of robust statistics. The connection to manipulation resistance may be worth pursuing.RecSys 2011: Tutorial on Recommender Robustness
  • 185. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyMore complicated shilling scenariosWe have focused in this tutorial on rating manipulation – thecreation of sybil profiles and ratings that distort arecommendation system’s output.However, in the real world, shilling can have a morecomplicated form. e.g. The text of hotel reviews can be used to persuade users to select certain hotels. Wu et al. (2010) has carried out work on identifying suspicious reviews in TripAdvisor.RecSys 2011: Tutorial on Recommender Robustness
  • 186. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyConclusionWe’ve reviewed research that has been carried out in lastnumber of years on robustness of RS.The conclusions are quite positive from system managers’points-of-view: If desired, recommendation algorithms that are largely manipulation-resistant may be adopted. Filtering strategies can effectively find unusual rating patterns. Obfuscating attack profiles to avoid filtering generally results in less effective attacks.Good recommendation systems are personalised and hence,should be sensitive to the peculiarities of each user’s ratingbehaviour.A system designer needs to find the right balance betweensensitivity to the melting pot of human behaviour andavoiding easy manipulation.RecSys 2011: Tutorial on Recommender Robustness
  • 187. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyThank You My research is sponsored by Science Foundation Ireland under grant 08/SRC/I1407: Clique: Graph and Network Analysis ClusterRecSys 2011: Tutorial on Recommender Robustness
  • 188. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IAdomavicius, G. and Zhang, J.: 2010, On the stability ofrecommendation algorithms, Proceedings of the fourth ACMconference on Recommender systems, RecSys ’10, ACM, NewYork, NY, USA, pp. 47–54.URL: http://doi.acm.org/10.1145/1864708.1864722Amatriain, X., Pujol, J. M. and Oliver, N.: 2009, I like it . . . I like it not: Evaluating user ratings noise in recommender systems, Proceedings of the 17th International Conference on User Modeling, Adaptation, and Personalization: formerly UM and AH, UMAP ’09, Springer-Verlag, Berlin, Heidelberg, pp. 247–258. URL: http://dx.doi.org/10.1007/978-3-642-02247-0 24RecSys 2011: Tutorial on Recommender Robustness
  • 189. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IIBurke, R., O’Mahony, M. P. and Hurley, N. J.: 2011, Robustcollaborative recommendation, in F. Ricci, L. Rokach, B. Shapiraand P. B. Kantor (eds), Recommender Systems Handbook,Springer, pp. 805–835.Carrara, E. and Hogben, G.: 2007, Enisa position paper no.2,reputation-based systems: a security analysis, Technical report,ENISA.Cheng, Z. and Hurley, N.: 2009a, Effective diverse and obfuscatedattacks on model-based recommender systems, in L. D.Bergman, A. Tuzhilin, R. D. Burke, A. Felfernig andL. Schmidt-Thieme (eds), RecSys, ACM, pp. 141–148.RecSys 2011: Tutorial on Recommender Robustness
  • 190. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IIICheng, Z. and Hurley, N.: 2009b, Trading robustness for privacy indecentralized recommender systems, in K. Z. Haigh andN. Rychtyckyj (eds), IAAI, AAAI.Cheng, Z. and Hurley, N.: 2010, Robust collaborative filtering byleast trimmed squares matrix factorisation, Proceedings of theInternational Conference on Tools in Artificial Intelligence.Donath, J.: 1998, Communities in Cyberspace, Routledge, chapterIdentity and Deception in the Virtual Community.Douceur, J.: 2002, The sybil attack, Proceedings of the FirstInternational Workshop on Peer-to-Peer Systems.Lam, S. K. and Riedl, J.: 2004, Shilling recommender systems forfun and profit, In Proceedings of the 13th International WorldWide Web Conference pp. 393–402.RecSys 2011: Tutorial on Recommender Robustness
  • 191. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences IVLang, J., Spear, M. and Wu, S. F.: 2010, Social manipulation ofonline recommender systems, Proceedings of the Secondinternational conference on Social informatics, SocInfo’10,Springer-Verlag, Berlin, Heidelberg, pp. 125–139.URL: http://dl.acm.org/citation.cfm?id=1929326.1929336Mehta, B., Hofmann, T. and Fankhauser, P.: 2007, Lies and propaganda: Detecting spam users in collaborative filtering, Proceedings of the 12th international conference on Intelligent user interfaces, pp. 14–21.Mehta, B. and Nejdl, W.: 2008, Attack resistant collaborative filtering, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR ’08, ACM, New York, NY, USA, pp. 75–82. URL: http://doi.acm.org/10.1145/1390334.1390350RecSys 2011: Tutorial on Recommender Robustness
  • 192. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VMobasher, B., Burke, R., Bhaumik, R. and Williams, C.: 2007, Toward trustworthy recommender systems: An analysis of attack models and algorithm robustness, ACM Transactions on Internet Technology 7(4).Mobasher, B., Burke, R. D. and Sandvig, J. J.: 2006, Model-based collaborative filtering as a defense against profile injection attacks, AAAI, AAAI Press.O’Mahony, M. P., Hurley, N. J. and Silvestre, C. C. M.: 2004, Anevaluation of neighbourhood formation on the performance ofcollaborative filtering, Artificial Intelligence Review21(1), 215–228.RecSys 2011: Tutorial on Recommender Robustness
  • 193. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VIO’Mahony, M. P., Hurley, N. J. and Silvestre, G. C. M.: 2002,Promoting recommendations: An attack on collaborativefiltering, in A. Hameurlain, R. Cicchetti and R. Traunm¨ller u(eds), DEXA, Vol. 2453 of Lecture Notes in Computer Science,Springer, pp. 494–503.O’Mahony, M. P., Hurley, N. J. and Silvestre, G. C. M.: 2006,Attacking recommender systems: The cost of promotion,Workshop on Recommender Systems at the 17th EuropeanConference on Artificial Intelligence (ECAI’06), 28th–29th, Rivadel Garda, Italy.RecSys 2011: Tutorial on Recommender Robustness
  • 194. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VIIResnick, P. and Sami, R.: 2007, The influence limiter: provablymanipulation-resistant recommender systems, RecSys ’07:Proceedings of the 2007 ACM conference on Recommendersystems, ACM, New York, NY, USA, pp. 25–32.Vu, L.-H., Papaioannou, T. and Aberer, K.: 2010, Impact of trustmanagement and information sharing to adversarial cost inranking systems, in M. Nishigaki, A. Jsang, Y. Murayama andS. Marsh (eds), Trust Management IV, Vol. 321 of IFIPAdvances in Information and Communication Technology,Springer Boston, pp. 108–124.RecSys 2011: Tutorial on Recommender Robustness
  • 195. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyReferences VIIIWilliams, C., Mobasher, B., Burke, R., Bhaumik, R. and Sandvig, J.: 2006, Detection of obfuscated attacks in collaborative recommender systems, In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI’06) .Wu, G., Greene, D. and Cunningham, P.: 2010, Merging multiple criteria to identify suspicious reviews, in X. Amatriain, M. Torrens, P. Resnick and M. Zanker (eds), RecSys, ACM, pp. 241–244.Yan, X. and Roy, B. V.: 2009, Manipulation robustness ofcollaborative filtering systems, CoRR abs/0903.0064.RecSys 2011: Tutorial on Recommender Robustness
  • Fly UP