Polonium: Tera-Scale Graph Mining for Malware Detection
Duen Horng Chau, Carey Nachenberg, Jeffrey Wilhelm, Adam T. Wright, Christos Faloutsos · 2013
We present Polonium, a scalable and e↵ective technology for detecting malware. We evaluated it with the largest anonymized file submissions dataset ever published, which spans over 60 terabytes of disk space. We formulated the problem of detecting malware as a large-scale graph mining and inference task, for which we construct a huge bipartite graph of almost 1 billion nodes from our data, 48 million of which are users, and 903 million are files. Edges, each denoting a file appearing on a machine, exceeds 37 billion. Our method for identifying malware is to locate files with low reputation. Our Polonium algorithm computes file reputation based on the fast and scalable Belief Propagation algorithm (O(|E|)), which iteratively improves inference quality. With one iteration, our method attained 85% true positive rate (in detecting malware). With more iterations, the true positive rate further improves for an additional 2%, which is a significant improvement given the baseline performance is already very good. We detail important design and implementation features of our method which enable its successful application on our dataset. We also present empirical observations on characteristics and patterns in our large billion-node graph.