Normalizing Metamorphic Malware Using Term Rewriting

Metamorphic malware - including certain viruses and worms - rewrite their code during propagation. This paper presents a method for normalizing multiple variants of metamorphic programs that perform their transformations using finite sets of instruction-sequence substitutions. The paper shows that the problem of constructing a normalizer can, in specific contexts, be formalized as a term rewriting problem. A general method is proposed for constructing normalizers. It involves modeling the metamorphic program¿s transformations as rewrite rules, and then modifying these rules to create a normalizing rule set. Casting the problem in terms of term rewriting exposes key challenges for constructing effective normalizers. In cases where the challenges cannot be met, approximations are proposed. The normalizer construction method is applied in a case study involving the virus called"W32.Evolt". The results demonstrate that both the overall approach and the approximation schemes may have practical use on realistic malware, and may thus have the potential to improve signature-based malware scanners.