Software Obfuscation with Non-Linear Mixed Boolean-Arithmetic Expressions
Software Obfuscation with Non-Linear Mixed Boolean-Arithmetic Expressions
复制标题
DOI：
10.1007/978-3-030-86890-1_16
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Binbin Liu;Weijie Feng;Qilong Zheng;Jing Li;Dongpeng Xu
中科院分区：
文献类型：
--
作者：
Binbin Liu;Weijie Feng;Qilong Zheng;Jing Li;Dongpeng Xu
混合布尔算术 (MBA) 表达式混合了按位运算（例如 AND、OR 和 NOT）和算术运算（例如 ADD 和 IMUL）。它支持语义保留程序转换，将简单的表达式转换为难以理解但等效的形式。 MBA表达式作为一种高效、低成本的混淆方案已被广泛采用。然而，最先进的反混淆研究对 MBA 混淆技术提出了重大挑战。位爆破、模式匹配、程序综合、深度学习和数学变换等攻击方法可以成功地简化 MBA 表达式的特定类别。现有的 MBA 混淆必须得到增强，以克服这些新出现的挑战。在本文中，我们首先回顾现有的 MBA 混淆方法，并揭示现有的 MBA 混淆是基于“线性 MBA”，即 MBA 转换的一个简单子集。这使得更复杂的“非线性 MBA”仍处于起步阶段。因此，我们提出了一种新的混淆方法来释放非线性 MBA 的力量。非线性 MBA 表达式是基于坚实的理论基础，通过线性 MBA 规则的组合或转换而生成的。与现有的 MBA 混淆相比，我们的方法可以生成更加复杂的 MBA 表达式。为了展示非线性 MBA 混淆方案的实用性，我们将非线性 MBA 混淆应用于 Tiny 加密算法（TEA）。我们已经将该方法实现为原型工具，名为 MBA-Obfuscator，以生成大规模数据集。我们在数据集上运行所有现有的 MBA 简化工具，最多可以成功简化 1,000 个非线性 MBA 表达式中的 147 个。我们的评估表明MBA-Obfuscator是一个具有坚实理论基石的实用混淆方案。
Mixed Boolean-Arithmetic (MBA) expression mixes bitwise operations (e.g., AND, OR, and NOT) and arithmetic operations (e.g., ADD and IMUL). It enables a semantic-preserving program transformation to convert a simple expression to a difficult-to-understand but equivalent form. MBA expression has been widely adopted as a highly effective and low-cost obfuscation scheme. However, state-of-the-art deobfuscation research proposes substantial challenges to the MBA obfuscation technique. Attacking methods such as bit-blasting, pattern matching, program synthesis, deep learning, and mathematical transformation can successfully simplify specific categories of MBA expressions. Existing MBA obfuscation must be enhanced to overcome these emerging challenges.In this paper, we first review existing MBA obfuscation methods and reveal that existing MBA obfuscation is based on “linear MBA”, a simple subset of MBA transformation. This leaves the more complex “non-linear MBA” in its infancy. Therefore, we propose a new obfuscation method to unleash the power of non-linear MBA. Non-linear MBA expressions are generated from the combination or transformation of linear MBA rules based on a solid theoretical underpinning. Comparing to existing MBA obfuscation, our method can generate significantly more complex MBA expressions. To present the practicability of the non-linear MBA obfuscation scheme, we apply non-linear MBA obfuscation to the Tiny Encryption Algorithm (TEA). We have implemented the method as a prototype tool, namedMBA-Obfuscator, to produce a large-scale dataset. We run all existing MBA simplification tools on the dataset, and at most 147 out of 1,000 non-linear MBA expressions can be successfully simplified. Our evaluation showsMBA-Obfuscatoris a practical obfuscation scheme with a solid theoretical cornerstone.