A Formal Grammar Approach to Metamorphic Binary Transformation

Simone Bauco and Alessandro Pellegrini

Abstract:
We present a declarative reformulation of metamorphic binary transformation using translational attribute grammars. Rather than introducing new transformation families, we reformulate well-known metamorphic techniques (instruction substitution, register remapping, expansion and reduction) as grammar productions with associated semantic attributes, yielding composability, stochastic diversity, and formally checkable semantic constraints. We demonstrate the feasibility of this approach through a metamorphic engine for x86-64 ELF binaries and evaluate it against signature scanners (VirusTotal), image-based Convolutional Neural Networks (CNNs), and feature-guided tree-based models. Using \textttMetaMe as a baseline, our grammar-based engine achieves higher evasion rates across all evaluated classifiers. We further show that grammar-generated variants are effective for adversarial training, enabling detection models to learn invariant features that resist structural evasion. The declarative structure of the grammar also enables a rule-by-rule validation methodology, allowing individual transformations to be isolated and verified via bounded translation validation.

BibTeX Entry: