<p>Serving more than one billion users around the world, today's online </p><p>social networks (OSNs) pervade our everyday life and change the way people </p><p>connect and communicate with each other. However, the open nature of </p><p>OSNs attracts a constant interest in attacking and exploiting them. </p><p>In particular, they are vulnerable to various attacks launched through </p><p>malicious accounts, including fake accounts and compromised real user </p><p>accounts. In those attacks, malicious accounts are used to send out </p><p>spam, spread malware, distort online voting, etc.</p><p>In this dissertation, we present practical systems that we have designed </p><p>and built to help OSNs effectively throttle malicious accounts. The overarching </p><p>contribution of this dissertation is the approaches that leverage the fundamental </p><p>weaknesses of attackers to defeat them. We have explored defense schemes along </p><p>two dimensions of an attacker's weaknesses: limited social relationships </p><p>and strict economic constraints.</p><p>The first part of this dissertation focuses on how to leverage social </p><p>relationship constraints to detect fake accounts. We present SybilRank, a novel </p><p>social-graph-based detection scheme that can scale up to OSNs with billions of </p><p>users. SybilRank is based on the observation that the social connections between </p><p>fake accounts and real users, called attack edges, are limited. It formulates </p><p>the detection as scalable user ranking according to the landing probability of </p><p>early-terminated random walks on the social graph. SybilRank generates an informative </p><p>user-ranked list with a substantial fraction of fake accounts at the bottom, </p><p>and bounds the number of fake accounts that are ranked higher than legitimate </p><p>users to O(log n) per attack edge, where n is the total number of users. We have </p><p>demonstrated the scalability of SybilRank via a prototype on Hadoop MapReduce, </p><p>and its effectiveness in the real world through a live deployment at Tuenti, </p><p>the largest OSN in Spain.</p><p>The second part of this dissertation focuses on how to exploit an attacker's </p><p>economic constraints to uncover malicious accounts. We present SynchroTrap, a system </p><p>that uncovers large groups of active malicious accounts, including both fake </p><p>accounts and compromised accounts, by detecting their loosely synchronized actions.</p><p>The design of SynchroTrap is based on the observation that malicious accounts usually </p><p>perform loosely synchronized actions to accomplish an attack mission, due to </p><p>limited budgets, specific mission goals, etc. SynchroTrap transforms the detection </p><p>into a scalable clustering algorithm. It uncovers large groups of accounts </p><p>that act similarly at around the same time for a sustained period of time. To </p><p>handle the enormous volume of user action data in large OSNs, we designed SynchroTrap</p><p>as an incremental processing system that processes small data chunks on a daily </p><p>basis but aggregates the computational results over the continuous data stream. </p><p>We implemented SynchroTrap on Hadoop and Giraph, and we deployed it on Facebook </p><p>and Instagram. This deployment has resulted in the unveiling of millions of malicious </p><p>accounts and thousands of large attack campaigns per month.</p> / Dissertation