Biblio

A frequent problem of Internet services are Sybil attacks, i.e., malicious users create numerous fake identities for themselves. To avoid this, many services employ obstacles like Captchas to force (potentially malicious) users to invest human attention in creating new identities for the service. However, this only makes it more difficult but not impossible to create fake identities. Sybil attacks are especially encountered as a problem in decentralized systems since no single trust anchor is available to judge new users as honest or malicious. The avoidance of a single centralized trust-anchor, however, is desirable in many cases. As a consequence, various decentralized Sybil detection approaches have been proposed. The most promising ones are based on leveraging the trust relationships embedded within social graphs. While most of these approaches are focusing on detecting large existing groups of Sybil identities, our approach Detasyr instead restricts the creation of numerous Sybil identities. For that, tickets are distributed through the social graph and have to be collected, allowing for decentralized and privacy preserving authorization. Additionally, it offers a proof of authorization to users that are considered to be honest, allowing them to display their authorization towards others.

In assessing privacy on online social networks, it is important to investigate their vulnerability to reconnaissance strategies, in which attackers lure targets into being their friends by exploiting the social graph in order to extract victims' sensitive information. As the network topology is only partially revealed after each successful friend request, attackers need to employ an adaptive strategy. Existing work only considered a simple strategy in which attackers sequentially acquire one friend at a time, which causes tremendous delay in waiting for responses before sending the next request, and which lack the ability to retry failed requests after the network has changed. In contrast, we investigate an adaptive and parallel strategy, of which attackers can simultaneously send multiple friend requests in batch and recover from failed requests by retrying after topology changes, thereby significantly reducing the time to reach the targets and greatly improving robustness. We cast this approach as an optimization problem, Max-Crawling, and show it inapproximable within (1 - 1/e + $ε$). We first design our core algorithm PM-AReST which has an approximation ratio of (1 - e-(1-1/e)) using adaptive monotonic submodular properties. We next tighten our algorithm to provide a nearoptimal solution, i.e. having a ratio of (1 - 1/e), via a two-stage stochastic programming approach. We further establish the gap bound of (1 - e-(1-1/e)2) between batch strategies versus the optimal sequential one. We experimentally validate our theoretical results, finding that our algorithm performs nearoptimally in practice and that this is robust under a variety of problem settings.