Introduction and motivation
Mixed Boolean-Arithmetic (MBA) expressions play a major role in the current state-of-the-art code obfuscation mechanisms.
In a nutshell, an MBA expression is composed of integer arithmetic operators, e.g. $(+, -, \times)$ and bitwise operators, e.g. $(\land, \lor, \oplus, \neg)$. MBA expressions can be leveraged to obfuscate the data-flow of code by iteratively applying rewriting rules and function identities that complicate (obfuscate) the initial expression while preserving its semantic behavior. This obfuscation approach is motivated by the fact that the combination of operators from these different fields do not interact well together: we have no rules (distributivity, factorization…) or general theory to deal with this mixing of operators.
Studying MBA expressions is exciting and terrifying at the same time. It offers a wide range of research paths to follow, many of which are barely explored yet. Academic literature is pretty scarce and not always approachable without a strong mathematics background. We aim to pave the ground, so more researchers get seduced with this field of study and make it advance both through theoretical contributions and practical tools.
While this MBA tour is mainly targeted to low-level security researchers and reverse engineers, anyone interested in software protection and the intersection of mathematics and computer science will benefit from it as well.