The automatic detection and accurate interpretation of suspicious graph patterns is one of the key issues in spotting malicious activities inside real-world systems, such as fake followers in Twitter, social network manipulation, and distributed denial-of-service (DoS) attacks. Most analysis techniques focus on synchronized and/or rare behaviors in large-scale systems. While in the former class synchronization is considered as a potential anomaly, in the latter class unusual patterns are recognized. Synchronized nodes may be detected because of their very similar behavior patterns, which are required by the tasks they are performing together. On the contrary, rare behaviors propose patterns significantly different from the majority.
CatchSync, the solution proposed in the paper, tries to detect both kinds of potential malicious behaviors, synchronized and rare, by adopting a parameter-free approach, which is also privacy-friendly as it works on the topology and does not need to know about sensitive details. The complexity of the adopted algorithm is linear in the graph size and, therefore, can work at a large scale. Indeed, CatchSync is evaluated on several real (for example, from Twitter) and synthetic big datasets, consisting of millions of nodes and billions of edges. The proposed method is shown to outperform, in terms of both accuracy and execution time, other solutions such as methods for graph-based anomaly detection, social spammer detection, and subgraph mining.
Assuming there are always new types of attacks, CatchSync works according to a realistic and effective approach to computer security. I definitely enjoyed reading this paper. Indeed, it deals with a very interesting topic and is, in general, well written and structured. The paper is suitable for a relatively wide audience.