Fast discovery of VM-sensitive divergence points with basic block comparison

To evade VM-based malware analysis systems, VM-aware malware equipped with the ability to detect the presence of virtual machine has appeared. To cope with the problem, detecting VM-aware malware and locating VM-sensitive divergence points of VM-aware malware is in urgent need. In this paper, we propose a novel block-based divergence locator. In contrast to the conventional instruction-based schemes, the block-based divergence locator divides malware program into basic blocks, instead of binary instructions, and uses them as the analysis unit. The block-based divergence locator significantly decrease the cost of behavior logging and trace comparison, as well as the size of behavior traces. As the evaluation showed, behavior logging is 23.87-39.49 times faster than the conventional schemes. The total number of analysis unit, which is highly related to the cost of trace comparisons, is 11.95%-16.00% of the conventional schemes. Consequently, VM-sensitive divergence points can be discovered more efficiently. The correctness of our divergence point discovery algorithm is also proved formally in this paper.