Scrambler: Mixed Boolean Arithmetic Obfuscation Tool Using E-graph and Equality Expansion

Ce papier présente Scrambler, un outil d'obfuscation arithmétique booléenne mixte basé sur les graphes d'égalité et l'expansion d'égalité, qui génère efficacement des expressions complexes et diversifiées tout en garantissant leur équivalence par construction.

L'essentiel

🕵️‍♂️ Le Secret de Scrambler : Comment transformer un secret en labyrinthe

Imaginez que vous avez un message secret très simple, comme "2 + 2". Si vous le donnez à un espion (un hacker), il le comprendra en une seconde. Pour protéger ce message, vous devez le transformer en quelque chose de compliqué, mais qui donne exactement le même résultat (toujours 4). C'est ce qu'on appelle l'obfuscation.

Jusqu'à présent, les outils pour faire cela étaient comme des cuisiniers avec une recette très limitée : ils ne pouvaient mélanger que quelques épices spécifiques. Résultat ? Le plat final était compliqué, mais pas assez pour tromper un vrai chef.

Les auteurs de cet article (Seoksu Lee, Sangjun An et Eun-Sun Cho) ont créé un nouvel outil nommé Scrambler. Voici comment il fonctionne, sans jargon technique.

1. Le Problème : Les vieux outils sont comme des Lego cassés

Les outils actuels utilisent des règles fixes (des "briques" prédéfinies) pour transformer les maths.

• L'outil "MBA Obfuscator" : C'est comme un jeu de construction où vous avez 3 types de briques. Vous pouvez faire une tour, mais elle sera toujours un peu banale.
• L'outil "Loki" : Il essaie de faire des tours très hautes, mais il est lent et utilise toujours les mêmes briques.
• Le gros défaut : Pour vérifier si leur tour est stable (si le résultat est toujours 4), ils doivent appeler un "expert" (un solveur informatique) à chaque fois. C'est lent et ça consomme beaucoup d'énergie.

2. La Solution : Scrambler et le "Miroir Magique"

Scrambler utilise une nouvelle technique basée sur deux concepts clés : les E-graphs et l'Expansion d'Égalité.

L'analogie du Miroir Magique (l'E-graph) :
Imaginez un miroir magique qui ne montre pas juste une image, mais toutes les façons possibles de voir cette image en même temps.

• Si vous avez 2 + 2, ce miroir vous montre aussi 4, (1 + 1) + 2, (3 + 1), etc., tous liés ensemble.
• Dans le monde informatique, on appelle cela un "E-graph". Au lieu de faire une seule transformation, Scrambler crée un réseau géant où toutes les versions équivalentes de votre calcul coexistent.

L'Expansion d'Égalité (Le jeu de l'escalade) :
Normalement, les ordinateurs utilisent ce miroir pour trouver la version la plus simple d'un calcul (pour aller vite).
Scrambler fait l'inverse ! Il utilise ce miroir pour compliquer le calcul à l'infini.

• Il prend une règle simple (ex: "tu peux remplacer x par x + 0").
• Il l'applique, puis réapplique, puis réapplique encore, comme si vous empiliez des couches de pâte à modeler autour d'une bille.
• Il s'arrête seulement quand la "tour" est assez haute (par exemple, quand elle a plus de 3 000 pièces).

3. Pourquoi Scrambler est un super-héros ?

Voici les trois avantages majeurs expliqués simplement :

• 🚀 Une complexité folle :
  Dans les tests, les autres outils ont créé des expressions avec environ 200 à 300 pièces. Scrambler, lui, a créé des monstres avec plus de 34 000 pièces ! C'est comme passer d'une petite maison en carton à un gratte-ciel de Lego. Pour un hacker, c'est impossible à lire.

• ✅ La garantie de sécurité (Pas besoin de vérification) :
  C'est le point le plus important. Comme Scrambler construit sa tour en utilisant des règles qui sont mathématiquement sûres (si A = B, alors remplacer A par B ne change rien), il n'a jamais besoin de demander à l'expert si le résultat est bon.

  • Analogie : Si vous construisez un pont avec des règles de physique parfaites, vous savez qu'il tiendra. Vous n'avez pas besoin de le tester avec un camion à chaque brique posée. Scrambler gagne un temps précieux.

• 🎨 Une créativité illimitée :
  Les vieux outils étaient limités à quelques types de maths. Scrambler peut utiliser presque n'importe quelle règle que vous lui donnez. Il peut créer des mélanges de maths et de logique (booléens) très bizarres et imprévisibles.

4. Le Résultat en Bref

Les chercheurs ont comparé Scrambler aux meilleurs outils existants.

• Taille de l'expression : Scrambler gagne haut la main (34 000 contre 235 pour le meilleur concurrent).
• Temps : Il est plus rapide car il ne perd pas de temps à vérifier le résultat à la fin.
• Sécurité : Le résultat est garanti mathématiquement grâce à la structure du miroir magique.

En conclusion

Scrambler est comme un artiste qui prend une simple esquisse et la transforme en une fresque murale complexe et illisible, tout en s'assurant que l'image de fond reste exactement la même. Grâce à une technique intelligente qui évite les vérifications inutiles, il rend le piratage de logiciels beaucoup plus difficile, tout en allant plus vite que les méthodes traditionnelles.

C'est une avancée majeure pour protéger les secrets numériques dans un monde où tout le monde essaie de les voler.

Résumé technique

Voici un résumé technique détaillé de l'article de recherche « SCRAMBLER: MIXED BOOLEAN ARITHMETIC OBFUSCATION TOOL USING E-GRAPH AND EQUALITY EXPANSION », rédigé en français.

1. Problématique

L'obfuscation de programme vise à transformer un code en une forme fonctionnellement équivalente mais difficile à lire pour entraver l'analyse et le reverse engineering. Parmi les techniques existantes, l'obfuscation par Arithmétique Booléenne Mixte (MBA) est largement utilisée en raison de son faible coût d'application et de sa résistance élevée.

Cependant, les outils d'obfuscation MBA actuels présentent plusieurs limitations majeures :

• Diversité limitée : Ils reposent sur des règles MBA prédéfinies et des informations matricielles spécifiques (tables de vérité, algèbre linéaire), ce qui restreint la variété des expressions générables.
• Complexité et Scalabilité : Des outils comme MBA Obfuscator, NeuReduce et Loki souffrent de contraintes sur les opérateurs supportés, de temps de génération élevés et d'une difficulté à créer des expressions de grande échelle.
• Vérification coûteuse : La plupart de ces outils nécessitent l'utilisation de solveurs SMT (comme Z3) pour vérifier l'équivalence sémantique des expressions générées, ce qui dégrade les performances sur des expressions complexes.

2. Méthodologie

Les auteurs proposent Scrambler, un nouvel outil d'obfuscation qui surmonte ces limites en combinant deux concepts clés : les E-graphs (graphes d'équivalence) et l'Expansion d'Égalité (Equality Expansion).

• Structure de données E-graph : Contrairement aux arbres de syntaxe abstraite (AST) classiques, un E-graph permet de représenter simultanément plusieurs expressions équivalentes au sein d'une même structure de graphe. Les classes d'équivalence (e-classes) regroupent les nœuds ayant la même signification sémantique, éliminant ainsi les redondances.
• Expansion d'Égalité (Equality Expansion) : C'est une adaptation de l'algorithme d'Équivalence de Saturation (Equality Saturation).
  • Saturation classique : Cherche l'expression la plus simple en explorant toutes les règles possibles.
  • Expansion proposée : Inverse le but. Elle utilise les règles de réécriture fournies par l'utilisateur pour complexifier l'expression jusqu'à ce qu'une condition d'arrêt soit atteinte (par exemple, une taille d'AST supérieure à 1000 nœuds).
• Implémentation : Scrambler est développé en Rust en utilisant le framework egg. Il prend en entrée un ensemble de règles de réécriture, une expression à obfuser et des conditions d'arrêt (taille, temps, nombre de nœuds).

3. Contributions Clés

1. Génération d'expressions complexes et diversifiées : Scrambler est capable de générer des expressions MBA linéaires, polynomiales et non polynomiales avec une complexité structurelle bien supérieure à celle des outils existants.
2. Garantie d'équivalence sans vérification externe : Grâce à la nature intrinsèque des E-graphs et des règles de réécriture préservant la sémantique, l'équivalence entre l'expression originale et l'expression obfusquée est garantie par construction. Cela élimine le besoin d'étapes de vérification coûteuses via des solveurs SMT.
3. Flexibilité des opérateurs : Contrairement aux outils basés sur des tables de vérité rigides, Scrambler peut intégrer une large gamme d'opérateurs tant que les règles de réécriture sont correctement définies.
4. Efficacité de génération : L'outil génère des expressions massives (plus de 23 000 opérateurs dans les tests) en quelques secondes, surpassant les temps de génération des concurrents.

4. Résultats Expérimentaux

Les auteurs ont comparé Scrambler à trois outils de référence (NeuReduce, Loki, MBA Obfuscator) sur plusieurs métriques : taille de l'AST, nombre de variables/constantes/opérateurs, alternance MBA et entropie.

• Complexité Structurelle : Scrambler a généré des expressions avec une taille d'AST moyenne de 34 786 nœuds et 23 373 opérateurs, contre respectivement ~216 et ~142 pour Loki, et ~235 et ~136 pour l'obfuscateur MBA.
• Alternance MBA : Le score d'alternance MBA de Scrambler atteint 6 387,58, dépassant largement les autres outils (Loki : 38,26 ; MBA Obfuscator : 31,83).
• Équivalence : Aucune vérification SMT n'a été nécessaire pour Scrambler, confirmant l'efficacité de l'approche par E-graph.
• Évolutivité : Les résultats montrent que la complexité augmente avec le nombre de règles appliquées et les limites de nœuds configurées, permettant de générer des obfuscations robustes tant que la mémoire et les contraintes de règles le permettent.

5. Signification et Perspectives

Ce travail marque une avancée significative dans le domaine de l'obfuscation logicielle en démontrant que les techniques d'optimisation de compilateurs (E-graphs) peuvent être détournées avec succès pour la génération d'expressions complexes destinées à la protection du code.

• Impact : Scrambler offre une méthode plus rapide, plus flexible et intrinsèquement sûre (sémantiquement) pour créer des barrières contre le reverse engineering.
• Limites et Futur : La validité des règles de réécriture appliquées doit être rigoureusement validée manuellement avant l'utilisation, car une règle incorrecte briserait l'équivalence. De plus, les performances dépendent fortement du choix des règles et des contraintes de ressources (mémoire). La recherche future devra se concentrer sur l'automatisation de la validation des règles et l'optimisation de la gestion de la mémoire pour des expansions encore plus massives.

En résumé, Scrambler redéfinit les standards de l'obfuscation MBA en remplaçant les approches basées sur la recherche et la vérification par une approche constructive basée sur l'expansion d'équivalence.