You are hereBlogs / root's blog / Malware Variant Detection Using Similarity Search over Sets of Control Flow Graphs

Malware Variant Detection Using Similarity Search over Sets of Control Flow Graphs


By root - Posted on 18 January 2012

I have published a new paper on Malware variant detection, "Malware Variant Detection Using Similarity Search over Sets of Control Flow Graphs".

This work is built ontop of Malwise, and is the basis for my Ruxcon talk, "Faster, More Effective Flowgraph-based Malware Classification".

Abstract - Static detection of polymorphic malware variantsplays an important role to improve system security. Control flow has shown to be an effective characteristic that represents polymorphic malware instances. In our research, we propose a similarity search of malware using novel distance metrics of malware signatures. We describe a malware signature by the set of control flow graphs the malware contains. We propose two approaches and use the first to perform pre-filtering.Firstly, we use a distance metric based on the distance between feature vectors. The feature vector is a decomposition of the set of graphs into either fixed size k-subgraphs, or q-gram strings of the high-level source after decompilation. We also propose a more effective but less computationally efficient distance metric based on the minimum matching distance. The minimum matching distance uses the string edit distances between programs’ decompiled flow graphs, and the linear sum assignment problem to construct a minimum sum weight matching between two sets of graphs. We implement the distance metrics in a complete malware variant detection system. The evaluation shows that our approach is highly effective in terms of a limited false positive rate and our system detects more malware variants when compared to the detection rates of other algorithms.

[ slides and paper ]