Current malware detection approaches (i.e. anti-virus software) deployed at end hosts utilize features of a specic malware instance. These approaches suer from poor accuracy because such features are easily evaded by trivial obfuscation such as garbage insertion and re-ordering of instruction or call sequences. In this paper,we introduce a novel graph theoretic approach to detect malware from instruction or call sequences. In our approach, we map the instruction or call sequence of an executable program to a graph. We then extract features from the constructed graphs at three levels: (1) vertex level, (2) sub-graph level, and (3) graph level. These features act as footprints of the behavior of an executable program and are leveraged to dierentiate between benign and malware programs. The results of our experiments show that our graph-theoretic approach differentiate between benign and malware programs with 100% accuracy.
Read
