Functional polymorphic engines: Formalisation, implementation and use cases

With regards to the known shortcomings suffered by form-based detection, an increasing number of antivirus products considers behavioral detection. Following this trend, form-based mutations could become function-based with the apparition of functional polymorphism: a third generation of mutation mechanism, specially designed to address behavioral detection. In effect, a same global behavior or purpose (replication, propagation, residency, etc.) can be achieved through different functional solutions, thus leaving space for possible mutations. Whereas actual form-based mutation techniques mainly modify the code structure of malware, functional mutations modify the code functionality, and more particularly the resulting interaction scheme with the operating system and other software. These functional mutations could not be achieved without reaching a semantic level of interpretation, higher than actual techniques remaining purely syntactic. Drawing a parallel, this article underlines the consequent relation existing between functional polymorphic engines and compilers. By studying the associated mutation properties, we prove that these engines exhibit logarithmic entropy and result in a NP-complete complexity for behavioral detection. The implementation of a prototype is finally addressed as well as its possible use for antivirus testing and software protection.