report us to resolve them. We are always happy to assist you.
2. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness? Proﬁle Injection Attacks Relevance of Robustness Measuring RobustnessRecSys 2011: Tutorial on Recommender Robustness 3. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Proﬁle 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?Proﬁle Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Beneﬁt AnalysisRecSys 2011: Tutorial on Recommender Robustness 5. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Proﬁle Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Beneﬁt Analysis 4 Robustness of Model-based AlgorithmsRecSys 2011: Tutorial on Recommender Robustness 6. Tutorial on Robustness of Recommender SystemsOutline 1 What is Robustness?Proﬁle Injection AttacksRelevance of RobustnessMeasuring Robustness 2 Attack StrategiesAttacking kNN Algorithms 3 Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Beneﬁt 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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? Proﬁle Injection AttacksOutline 1 What is Robustness?Proﬁle Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Beneﬁt 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? Proﬁle Injection AttacksDeﬁning 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? Proﬁle Injection AttacksDeﬁning 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 ﬁrst paper (O’Mahony et al. 2002)appeared on the vulnerability of Recommender Systems tomalicious strategies for “recommendation promotion” – laterdubbed proﬁle injection attacks.RecSys 2011: Tutorial on Recommender Robustness 12. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksDeﬁning 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 stressedspeciﬁcally 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? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackRecSys 2011: Tutorial on Recommender Robustness 14. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackAn attack is a concerted eﬀort to bias the results of arecommender system by the insertion of a large number ofproﬁles using false identities or sybils.RecSys 2011: Tutorial on Recommender Robustness 15. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackAn attack is a concerted eﬀort to bias the results of arecommender system by the insertion of a large number ofproﬁles using false identities or sybils.Each identity is referred to as an attack proﬁle.RecSys 2011: Tutorial on Recommender Robustness 16. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackAn attack is a concerted eﬀort to bias the results of arecommender system by the insertion of a large number ofproﬁles using false identities or sybils.Each identity is referred to as an attack proﬁle.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? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackAn attack is a concerted eﬀort to bias the results of arecommender system by the insertion of a large number ofproﬁles using false identities or sybils.Each identity is referred to as an attack proﬁle.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? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackAn attack is a concerted eﬀort to bias the results of arecommender system by the insertion of a large number ofproﬁles using false identities or sybils.Each identity is referred to as an attack proﬁle.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? Proﬁle Injection AttacksRobust RS ResearchThe goal of robust recommendation is to prevent attackersfrom manipulating an RS through large-scale insertion of falseuser proﬁles: a proﬁle injection attackAn attack is a concerted eﬀort to bias the results of arecommender system by the insertion of a large number ofproﬁles using false identities or sybils.Each identity is referred to as an attack proﬁle.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? Proﬁle Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse proﬁles only.RecSys 2011: Tutorial on Recommender Robustness 21. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse proﬁles 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? Proﬁle Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse proﬁles 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? Proﬁle Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse proﬁles 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 proﬁles 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? Proﬁle Injection AttacksRobust RS ResearchWe assume that the attacker has no direct access to theratings database – manipulation achieved via the creation offalse proﬁles 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 proﬁles 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? Proﬁle Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness 26. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness 27. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksExampleRecSys 2011: Tutorial on Recommender Robustness 28. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksThreats to Reputation Systems IIt is interesting to compare the scenario studied in RS researchwith the threats identiﬁed 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 pseudospooﬁng: 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? Proﬁle 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 stuﬃng 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 inﬂuence 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? Proﬁle 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 eﬀect etc. 13 Threats to the underlying networks: e.g. denial of serviceattack. 14 Trust topology threats: e.g.targeting most highly inﬂuentialnodes. 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? Proﬁle 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? Proﬁle 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? Proﬁle 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/eﬀort cost;RecSys 2011: Tutorial on Recommender Robustness 34. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle 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/eﬀort 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? Proﬁle 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/eﬀort 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? Proﬁle 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/eﬀort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toThe number of sybil proﬁles created ;RecSys 2011: Tutorial on Recommender Robustness 37. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle 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/eﬀort cost;risk cost, associated with the likelihood of being detected;In any case, we may model the cost as proportional toThe number of sybil proﬁles created ;the total number of constituent ratings within the sybil proﬁles.RecSys 2011: Tutorial on Recommender Robustness 38. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle 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? Proﬁle 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? Proﬁle 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? Proﬁle Injection AttacksNotationLet A be the set of attack proﬁles of size nA = number ofproﬁles and mA = number of ratings. Let ai denote a singleattack proﬁle 1 ≤ i ≤ nA .RecSys 2011: Tutorial on Recommender Robustness 42. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle Injection AttacksNotationLet R be the (n + nA ) × m database of genuine and attackproﬁles available to the recommendation algorithmpost-attack.RecSys 2011: Tutorial on Recommender Robustness 43. Tutorial on Robustness of Recommender SystemsWhat is Robustness? Proﬁle 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? Proﬁle 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? Proﬁle 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? Proﬁle 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? Proﬁle 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? Proﬁle 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? Proﬁle 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? Proﬁle 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 ﬁnd 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 ﬁlms 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 ﬁnd 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 oﬃcials said Monday that it was a mistake for the publishinggiant’s marketing division to oﬀer $25 Amazon gift cards to anyone who would give a new textbook ﬁve stars in areview posted on Amazon or Barnes & Noble. While those popular Web sites’ customer reviews have long beenknown to be something less than scientiﬁc, 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 Proﬁles(Mobasher et al. 2007) introduce the following notation forthe components of an attack proﬁle:RecSys 2011: Tutorial on Recommender Robustness 68. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack Proﬁles(Mobasher et al. 2007) introduce the following notation forthe components of an attack proﬁle: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 Proﬁles(Mobasher et al. 2007) introduce the following notation forthe components of an attack proﬁle: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 Proﬁles(Mobasher et al. 2007) introduce the following notation forthe components of an attack proﬁle:IF , the ﬁller items(s) ﬁll out the remainder of the ratings inthe attack proﬁle.RecSys 2011: Tutorial on Recommender Robustness 71. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProﬁlesThe goal of attack proﬁle creation must be toEﬀectively 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 ProﬁlesThe goal of attack proﬁle creation must be toEﬀectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and ﬁltering– selection of the ﬁller items IF .RecSys 2011: Tutorial on Recommender Robustness 73. Tutorial on Robustness of Recommender SystemsAttack StrategiesForming Attack ProﬁlesThe goal of attack proﬁle creation must be toEﬀectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and ﬁltering– selection of the ﬁller 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 ProﬁlesThe goal of attack proﬁle creation must be toEﬀectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and ﬁltering– selection of the ﬁller 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 ProﬁlesThe goal of attack proﬁle creation must be toEﬀectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and ﬁltering– selection of the ﬁller 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 ProﬁlesThe goal of attack proﬁle creation must be toEﬀectively support the purpose of the attack – selection oftarget rating and IS ;But, remain unobtrusive so as to avoid detection and ﬁltering– selection of the ﬁller 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 Kerkchoﬀ’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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 ﬁrst CF proﬁle 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 ﬁrst CF proﬁle 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 ﬁrst CF proﬁle 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 proﬁle 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 proﬁle have in common. A small intersection setcan lead to high correlations.Therefore a small proﬁle 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 proﬁle have in common. A small intersection setcan lead to high correlations.Therefore a small proﬁle of popular items will have a largecorrelation with users who have rated these itemsImplies a low-cost, eﬀective 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 proﬁle have in common. A small intersection setcan lead to high correlations.Therefore a small proﬁle of popular items will have a largecorrelation with users who have rated these itemsImplies a low-cost, eﬀective 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 proﬁle is ﬁlled out asfollows:Random Attack Randomly chosen ﬁller 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 proﬁle is ﬁlled out asfollows:Average Attack Randomly chosen ﬁller 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 proﬁle is ﬁlled out asfollows:Probe Attack Filler items ﬁlled by starting with a set of seed ratings, querying the recommender system to ﬁll 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 proﬁle is ﬁlled out asfollows: Segment Attack Identifying popular items in a particular usersegment, these are given maximum ratingand remaining ﬁller 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 proﬁle is ﬁlled out asfollows:Bandwagon Attack A set of popular items is given the maximum rating, while remaining ﬁller 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 ﬁllerasize, in as a percentagenumber total numberof the remaining items shown Attack Size given as percentage of the total for diﬀerent ﬁller 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% ﬁller 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 ofﬁce successes including such titlesas Star Wars, Return of Jedi, Titanic, etc. The attack proﬁles consist of highratings given to these popular titles in conjunction with high ratings for thepushed movie. Figure 7 shows the effect of ﬁller 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 proﬁle 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 DetectionProﬁle Injection Attacks Two well-studied attacks : Construct spam proﬁle with max (or min) rating for targeted item. Choose a set of ﬁller items at randomRandom Attack – insert ratings in ﬁller items according to N (µ, σ)Average Attack – insert ratings in ﬁller item i according to N (µi , σi )For evaluations, genuine proﬁles 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 proﬁles. A cluster C deﬁned by an indicator vector x such that xi = 1 if user ui ∈ C and xi = 0 otherwise. S a proﬁle 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 ﬁrst 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 proﬁles 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 proﬁles 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?Proﬁle Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Beneﬁt 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 proﬁle over all possibleproﬁles YTwo hypotheses H0 – that y is a genuine proﬁle, associated pdf fY|H1 (y) H1 – that y is an attack proﬁle, 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 ProﬁlesAs attacks follow well-deﬁned 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 ProﬁlesAs attacks follow well-deﬁned 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 ProﬁlesAs attacks follow well-deﬁned 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 ProﬁlesSimple model – identical to attack model except thatprobability of selecting a ﬁller item is estimated aspi Pr[Yi = φ] from a dataset of genuine proﬁles.ˆ 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 suﬃcient (almost) to distinguish from attack proﬁles.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 proﬁle / genuine proﬁle) overlap (few common ratings) makes extreme correlations possible – hence attack proﬁles are unusually inﬂuential. (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).Eﬀective obfuscation must try to reduce the statisticaldiﬀerences between genuine and attack proﬁles.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 ﬁller 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 ﬁller items are chosen from x-% most popularitems.AoP is a less perceptible but also less eﬀective 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 Proﬁle 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 proﬁles 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 Proﬁle ModelDiﬃculty 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 Proﬁle 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 proﬁles and Database of attack proﬁlesto 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 ondiﬀerent 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 ondiﬀerent 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 proﬁle 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-Beneﬁt AnalysisOutline 1 What is Robustness? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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-Beneﬁt AnalysisCost-Beneﬁt AnalysisIn O’Mahony et al. (2006), we examined a simple cost-beneﬁtmodel 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-Beneﬁt AnalysisResultsProﬁtj = 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-Beneﬁt AnalysisCost-beneﬁt AnalysisVu et al. (2010) examines the adversarial cost to attacking aranking system in terms of nA = number of proﬁles 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-Beneﬁt AnalysisCost-beneﬁt 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 eﬀect 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 segmentproﬁles.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 proﬁles 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 diversiﬁedattack can create less similar but yet still eﬀective attackproﬁles.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 ﬁnd 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 eﬀectively 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 eﬀectively 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 eﬀectively in particular on memory-basedalgorithms.Standard attacks are generally detectable: Cost eﬀectiveness implies that a sybil proﬁle should be unusually inﬂuential.Special purpose (informed) attacks can be tailored towardsparticular CF algorithms e.g. a high diversity attack proved eﬀective against the k-means clustering algorithm.Sybil proﬁles can be obfuscated to make them less detectable Selection of ﬁller items is Achille’s heal of standard average attack, but also explains its power. Obfuscation reduces the eﬀectiveness 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 ﬁltering to the standard user-based algorithm,to cluster and ﬁlter 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 ﬁltering to the standard user-based algorithm,to cluster and ﬁlter 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 ﬁltering to the standard user-based algorithm,to cluster and ﬁlter 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 ﬁltering to the standard user-based algorithm,to cluster and ﬁlter 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 ﬂagged 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 ﬁltering to the standard user-based algorithm,to cluster and ﬁlter 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 ﬂagged 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 aﬀected by small departures from the model.Robust regression uses a bounded cost function which limitsthe eﬀect 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 aﬀected by small departures from the model.Robust regression uses a bounded cost function which limitsthe eﬀect 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 aﬀected by small departures from the model.Robust regression uses a bounded cost function which limitsthe eﬀect 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? Proﬁle Injection Attacks Relevance of Robustness Measuring Robustness 2 Attack Strategies Attacking kNN Algorithms 3 Attack Detection PCA-based Attack Detection Statistical Attack Detection Cost-Beneﬁt 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 Inﬂuence Limiter (Resnick and Sami 2007)Output of recommendation systemqj passes through aninﬂuence-limiting process toproduce a modiﬁed 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 Inﬂuence 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 proﬁle 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 proﬁle 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 proﬁle 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 proﬁle 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 proﬁleRecSys 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 proﬁle 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 proﬁle 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 inﬂuence 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?Proﬁle Injection AttacksRelevance of RobustnessMeasuring Robustness 2Attack StrategiesAttacking kNN Algorithms 3Attack DetectionPCA-based Attack DetectionStatistical Attack DetectionCost-Beneﬁt 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 diﬀerent 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 diﬀerent 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 ﬁlteringRecSys 2011: Tutorial on Recommender Robustness 180. Tutorial on Robustness of Recommender SystemsStability, Trust and PrivacyRobustness and Related ConceptsTrust has been widely explored in collaborative ﬁltering . . . avoid manipulation by only using rating of trusted users or build trust based on user behaviour (c.f. the Inﬂuence 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 ﬁltering . . . avoid manipulation by only using rating of trusted users or build trust based on user behaviour (c.f. the Inﬂuence Limiter) . . . nevertheless systems based on trust are still manipulatable – tinyurl.com/6z6k6kr two ﬁctitious 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. Diﬀerential privacy has been studied in the context of recommender systems by a number of researchers. One approach to diﬀerential 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 proﬁles 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 eﬀectively ﬁnd unusual rating patterns. Obfuscating attack proﬁles to avoid ﬁltering generally results in less eﬀective attacks.Good recommendation systems are personalised and hence,should be sensitive to the peculiarities of each user’s ratingbehaviour.A system designer needs to ﬁnd 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, Eﬀective 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 ﬁltering byleast trimmed squares matrix factorisation, Proceedings of theInternational Conference on Tools in Artiﬁcial 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 proﬁt, 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 ﬁltering, Proceedings of the 12th international conference on Intelligent user interfaces, pp. 14–21.Mehta, B. and Nejdl, W.: 2008, Attack resistant collaborative ﬁltering, 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 ﬁltering as a defense against proﬁle 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 ﬁltering, Artiﬁcial 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 collaborativeﬁltering, 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 Artiﬁcial 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 inﬂuence 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 Artiﬁcial 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 ﬁltering systems, CoRR abs/0903.0064.RecSys 2011: Tutorial on Recommender Robustness

All materials on our website are shared by users. If you have any questions about copyright issues, please # Tutorial on Robustness of Recommender Systems

by neilhurley

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