  Code obfuscation aims at protecting Intellectual Property and other secrets
embedded into software from being retrieved. Recent works leverage advances in
artificial intelligence with the hope of getting blackbox deobfuscators
completely immune to standard (whitebox) protection mechanisms. While
promising, this new field of AI-based blackbox deobfuscation is still in its
infancy. In this article we deepen the state of AI-based blackbox deobfuscation
in three key directions: understand the current state-of-the-art, improve over
it and design dedicated protection mechanisms. In particular, we define a novel
generic framework for AI-based blackbox deobfuscation encompassing prior work
and highlighting key components; we are the first to point out that the search
space underlying code deobfuscation is too unstable for simulation-based
methods (e.g., Monte Carlo Tres Search used in prior work) and advocate the use
of robust methods such as S-metaheuritics; we propose the new optimized
AI-based blackbox deobfuscator Xyntia which significantly outperforms prior
work in terms of success rate (especially with small time budget) while being
completely immune to the most recent anti-analysis code obfuscation methods;
and finally we propose two novel protections against AI-based blackbox
deobfuscation, allowing to counter Xyntia's powerful attacks.
