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

本文介绍了 Scrambler,这是一种基于 e-graph 和等式扩展技术的混合布尔算术混淆工具,能够高效生成等价性由构造保证的复杂且多样的表达式,并在表达力和复杂度上优于现有工具。

Seoksu Lee, Sangjun An, Eun-Sun Cho

发布于 Mon, 09 Ma
📖 1 分钟阅读☕ 轻松阅读

Each language version is independently generated for its own context, not a direct translation.

这篇论文介绍了一个名为 Scrambler(搅拌机) 的新工具,它的任务是给计算机代码“化妆”,让代码变得极其复杂、难以理解,但功能却完全不变。

为了让你轻松理解,我们可以把这段技术内容想象成一场**“魔术表演”“乐高积木游戏”**。

1. 为什么要“搅拌”代码?(背景)

想象一下,你写了一个简单的食谱(代码),比如“把苹果和香蕉混合”。

  • 普通状态苹果 + 香蕉。这太简单了,任何人看一眼就知道你在做什么。
  • 黑客/竞争对手:他们想偷看你的食谱,或者破解你的程序。

为了保护自己,我们需要把食谱改写得极其复杂,比如变成:“取苹果的一半,加上香蕉的三倍,再减去苹果和香蕉的交集,最后加上一个常数……"
虽然写法变了,但结果还是“苹果和香蕉混合”。这就是**代码混淆(Obfuscation)**的目的:让外人看不懂,但机器运行起来和原来一模一样。

以前的工具(如 MBA Obfuscator, NeuReduce 等)就像是一些老式厨师

  • 他们手里只有几本固定的“菜谱”(预设规则)。
  • 他们只能做几种特定的菜(线性、多项式等)。
  • 如果想做更复杂的菜,他们得手动查表、算半天,效率很低,而且做出来的菜花样不多。

2. Scrambler 是怎么工作的?(核心魔法)

这篇论文提出的 Scrambler 就像是一个拥有无限可能性的“乐高大师”。它用了两个核心魔法:

魔法一:e-graph(等价图)—— “多重宇宙”的积木盒

想象你有一个神奇的积木盒(e-graph)。

  • 在普通世界里,苹果 + 香蕉香蕉 + 苹果 是两个不同的积木堆。
  • 但在 Scrambler 的“多重宇宙”积木盒里,它知道这两个其实是一回事(等价)。它把这两个积木堆用一根虚线连起来,告诉系统:“看,这两个虽然长得不一样,但意思完全一样。”
  • 这样,系统就不需要重复存储,而是把所有长得像、意思一样的积木都放在同一个“家族”里。

魔法二:Equality Expansion(等式扩展)—— “疯狂生长”的藤蔓

以前的工具是“寻找最简单的解”(就像想怎么把积木搭得最省)。
但 Scrambler 反其道而行之,它玩的是**“等式扩展”**。

  • 规则:它手里有一堆“变形咒语”(比如:x + y 可以变成 (x | y) + (x & y))。
  • 过程:它不断对这些咒语念咒。每念一次,积木就分裂、生长一次。
  • 目标:它不追求“简单”,而是追求**“复杂”**。它会一直念咒,直到积木堆变得像一座巨大的迷宫(比如节点数超过 3000 个),或者时间到了为止。

比喻
想象你在揉面团。以前的工具揉几下就停了,怕面团太硬。
Scrambler 则是把面团扔进一个自动搅拌机,不停地加料、折叠、拉伸,直到面团变成了一团纠缠不清、极其复杂的“意大利面”,但你咬一口,味道(功能)和原来那块面团完全一样。

3. 它有什么厉害之处?(实验结果)

论文里的实验就像是一场**“谁变出的迷宫更复杂”**的比赛。

  • 对手们
    • NeuReduce:变出来的迷宫大概只有 20 步长。
    • Loki:能变到 200 步长。
    • MBA Obfuscator:能变到 200 多步长。
  • Scrambler(主角)
    • 它变出来的迷宫竟然有 34,000 多步长
    • 它的复杂度(Entropy)和混乱程度(MBA Alternation)是其他工具的几十倍甚至上千倍。

最关键的优势
以前的工具变完菜后,还得请一个“美食鉴定家”(SMT 求解器,如 Z3)来尝一尝,确认味道没变。这很花时间。
而 Scrambler 因为是在“多重宇宙积木盒”里生长的,只要它用的“变形咒语”是对的,长出来的东西就自动保证味道不变。它不需要请鉴定家,天生就是对的。这让它速度快得多,也能造出更复杂的结构。

4. 总结

Scrambler 就是一个利用**“等价关系”“无限生长”**策略的超级代码搅拌机。

  • 它做了什么:把简单的代码变成了极其复杂、像迷宫一样的代码。
  • 它怎么做的:利用一种叫 e-graph 的数据结构,像滚雪球一样不断把代码“膨胀”变大,而不是像以前那样死板地套用公式。
  • 结果:它生成的代码比现有工具复杂得多,更难被破解,而且因为它自带“正确性保证”,所以生成速度更快,不需要额外的验证步骤。

简单来说,如果以前的混淆工具是**“把字写得潦草一点”,那 Scrambler 就是“把整句话翻译成一种没人看得懂、但逻辑严密的加密语言”**,而且它保证你读出来(运行)的时候,意思一点都没变。