11/17/10%1%L-23 Trust and Reputation + Worms Trust Trust involves human activities We share the same interests. We had a satisfactory transaction. We are friends. After trust is established Can bootstrap other forms of security using crypto 2 Overview SybilGuard: trust in people Credence: trust in objects based on people Wi-Fi reports: trust in objects based on people with privacy Perspectives: trust in objects based on independent views 3 Overview SybilGuard: trust in people Credence Wi-Fi reports Perspectives 411/17/10%2%Background: Sybil Attack Sybil attack: Single user pretends many fake/sybil identities Creating multiple accounts from different IP addresses Sybil identities can become a large fraction of all identities Out-vote honest users in collaborative tasks launch sybil attack honest malicious 5 Background: Defending Against Sybil Attack Using a trusted central authority Tie identities to actual human beings Not always desirable Can be hard to find such authority Sensitive info may scare away users Potential bottleneck and target of attack Without a trusted central authority Impossible unless using special assumptions [Douceur’02] Resource challenges not sufficient -- adversary can have much more resources than typical user 6 SybilGuard Basic Insight: Leveraging Social Networks Undirected graph Nodes = identities Edges = strong trust E.g., colleagues, relatives Our Social Network Definition 7 SybilGuard Basic Insight malicious user honest nodes sybil nodes Observation: Adversary cannot create extra edges between honest nodes and sybil nodes attack edges n honest users: One identity/node each Malicious users: Multiple identities each (sybil nodes) Sybil nodes may collude – the adversary 811/17/10%3%SybilGuard Basic Insight honest nodes sybil nodes Dis-proportionally small cut disconnecting a large number of identities But cannot search for such cut brute-force… 9 Goal of Sybil Defense Goal: Enable a verifier node to decide whether to accept another suspect node Accept: Provide service to / receive service from Idealized guarantee: An honest node accepts and only accepts other honest nodes SybilGuard: Bounds the number of sybil nodes accepted Guarantees are with high probability Approach: Acceptance based on random route intersection between verifier and suspect 10 Random Walk Review pick random edge d pick random edge c pick random edge e a b d e f c 11 Random 1 to 1 mapping between incoming edge and outgoing edge Random Route: Convergence Using routing table gives Convergence Property Routes merge if crossing the same edge 12 a → d b → a c → b d → c d → e e → d f → f a b c d e f randomized routing table11/17/10%4%Random Route: Back-traceable Using 1-1 mapping gives Back-traceable Property Routes may be back-traced 13 a → d b → a c → b d → c d → e e → d f → f a b c d e f If we know the route traverses edge e, then we know the whole route Random Route Intersection: Honest Nodes Verifier accepts a suspect if the two routes intersect Route length w: W.h.p., verifier’s route stays within honest region W.h.p., routes from two honest nodes intersect sybil nodes honest nodes Verifier Suspect 14 € ~ n lognRandom Route Intersection: Sybil Nodes SybilGuard bounds the number of accepted sybil nodes within g*w g: Number of attack edges w: Length of random routes Next … Convergence property to bound the number of intersections within g Back-traceable property to bound the number of accepted sybil nodes per intersection within w 15 Bound # Intersections Within g Convergence: Each attack edge gives one intersection ⇒ at most g intersections with g attack edges sybil nodes honest nodes Verifier Suspect must cross attack edge to intersect even if sybil nodes do not follow the protocol same intersection Intersection = (node, incoming edge 1611/17/10%5%Bound # Sybil Nodes Accepted per Intersection within w Back-traceable: Each intersection should correspond to routes from at most w honest nodes Verifier accepts at most w nodes per intersection Will not hurt honest nodes Verifier for a given intersection 17 Summary of SybilGuard Guarantees Power of the adversary: Unlimited number of colluding sybil nodes Sybil nodes may not follow SybilGuard protocol W.h.p., honest node accepts ≤ g*w sybil nodes g: # of attack edges w: Length of random route If SybilGuard bounds # accepted sybil nodes within Then apps can do n/2 byzantine consensus n majority voting not much larger than n effective replication 18 Overview SybilGuard Credence: trust in objects based on people Wi-Fi reports Perspectives 19 Problem: Pollution P2P pollution Non-authentic content Corrupted or missing contents Viruses What are the solutions? Ranked by popularity Ranked by submitter (how many filed submitted) 2011/17/10%6%Credence: Reputation based on Voting 21 Is the file authentic? Credence: Reputation based on Voting 22 Randomly choose peers to collect votes Is the file authentic? Is the file authentic? Is the file authentic? Credence: Reputation based on Voting 23 Randomly choose peers to collect votes No Yes! Yes! Credence: Reputation based on Voting 24 What is the reputation of each response? (correlation coefficient) No Yes! Yes!11/17/10%7%Credence: Reputation based on Voting 25 Probably not authentic… No Yes! Yes! Credence Reputation Graph 26 Overview SybilGuard Credence Wi-Fi reports: trust in objects based on people with privacy Perspectives 27 Problem: Commercial AP Selection tmobile attwifi (ap 1) attwifi (ap 2) seattlewifi linksys Free Public Wifi $3.99 $9.99 Free! Free! Which networks will run my applications? "Which ones have good performance? Quality = ??? We often have many choices of wireless access points (APs), but little information about each Jiwire.com Hotspot database 2811/17/10%8%Goal: Provide More Information tmobile attwifi (ap 1) attwifi (ap 2) seattlewifi linksys Free Public Wifi
View Full Document
Unlocking...