Using Markov chains to filter machine-morphed variants of malicious programs

Of the enormous quantity of malicious programs seen in the wild, most are variations of previously seen programs. Automated program transformation tools-i.e., code morphers-are one of the ways of making such variants in volume. This paper proposes a Markov chain-based framework for fast, approximate detection of variants of known morphers wherein every morphing operation independently and predictably alters quickly-checked global program properties. Specifically, identities from Markov chain theory are applied to approximately determine whether a given program may be a variant created from some given previous program, or whether it definitely is not. The framework is used to define a method for finding telltale signs of the use of closed-world, instruction-substituting transformers within the frequencies of instruction forms found in a program. This decision method may yield a fast technique to aid malware detection.