从零开始的MBA混淆(1)

MBA运算

MBA运算（Mixed Boolean-Arithmetic）是一种定义在模$2^n$下的混合了布尔逻辑运算（与&、或|、非~、异或^）和代数运算（+、-、*、/）的运算系统。以下为一个C语言实现的MBA运算示例：

int a, b;
int c = (a & b) + (a | b); // 等价于c=a+b

线性MBA

线性MBA常用于运算混淆中，它的定义如下： $$ \sum_{i \in I}a_i e_i (x_1,x_2,…,x_t) $$ 其中$a_i$为整数，$e_i(x_1,x_2,…,x_n)$为只含有布尔逻辑运算的表达式，简单举几个例子，以下的表达式都属于线性MBA： $$ f(x,y) = (x \lor y) - (x \land y) - (x \oplus y) \newline f(x,y) = x-3*(x \land y)-(x \oplus y)+(\lnot y)-(\lnot(x \land y)) + 2*y $$

位独立性

线性MBA的特点是具有位独立性，即由加号相连接的每一项，只含有布尔逻辑运算，变量的每一位的运算不会影响到前一位或后一位，这就是位独立性。以int类型的变量举例来说：

int x = 1, y = 1
int z = x + y // 01 + 01 = 10 低位向高位进位
int t = x & y // 01 & 01 = 01 不会存在进位

位独立性保证了每一位的运算规律相同，使得我们可以将变量的取值空间由32bit缩小至1bit，在1bit空间对变量的取值进行枚举来构造线性MBA等式，例如：

记上述矩阵为M，每一项的系数记作C，解下列线性方程，即可得到一个MBA恒等式: $$ Mc = 0 \newline c = [1,1,-1,-1]^{T} \newline 1*x + 1*y + (-1)*(x\land y)+(-1)*(x\lor y)=0 \newline x+y=(x\land y)+(x\lor y) $$

则$x+y$便可以用$(x\land y)+(x\lor y)$进行混淆，使用上述方法，我们可以轻易地构造出许多线性MBA恒等式，进而构造出相应的混淆。

多项式MBA

多项式MBA是线性MBA的更一般形式，简单点说就是把线性MBA作为乘数相乘并展开。它的数学定义如下：

$$ \sum_{i \in I}a_i (\prod_{j \in J_i} e_{(i,j)} (x_1,x_2,…,x_t)) $$

以下几个例子都是多项式MBA：

$$ f(x,y) = (x \land y)*(x \lor y)+(x \land \lnot y)*(\lnot x \land y) \newline f(x,y) = (x - (x \land y)-(x \lor y))*(-x-1) $$

多项式MBA可以按照变量个数和乘法次数进行分类，上面的两个式子都是二元二次多项式MBA，线性MBA是一种特殊的多项式MBA，线性MBA也可以称为n元一次多项式MBA。

乘一法构造多项式MBA

基于线性MBA混淆构造多项式MBA混淆的最简单方法是乘一法。我们知道有些线性MBA表达式的值恒为1（使用上文介绍的方法也可以轻松构造），那么我们对某个基础线性MBA乘1，将1替换为值恒为1的线性MBA即可构造多项式MBA，下面为一个简单示例： $$ \lnot x = -x-1 \rightarrow 1=-x-\lnot x \newline x+y = (x+y)*1=(x+y)*(-x-\lnot x) =-x^2-x*y-\lnot x*x-\lnot x*y $$

但是这样构造存在一个问题，构造后的多项式MBA能够轻易被还原为因式相乘的形式（通过提取公因式还原），进而化简去掉值恒为1的因式。

我们可以将乘1法进行改进，改进的方法是加值恒为0且与上述构造存在相同子式的MBA，举个简单例子： $$ (x \land y) − y − (x \lor \lnot y) = 1 \newline e_1=x+y=(x\land y)+(x \lor y),e_2=(x \land y) − y − (x \lor \lnot y) \newline e_3=(x\land y)-(x \lor y),e_4=(x \land y) − y +(\lnot x \land y)=0 \newline e_1=e_1*e_2+e_3*e_4=2∗ (x \lor y) ∗ ((x \land y) − y) − (x \lor \lnot y) ∗ ((x \lor y) \newline +(x \land y)) +(\lnot x \land y) ∗ ((x \lor y) − (x \land y)) $$ 上例中$e_3$与$e_1$中的项完全相同，但是符号相反。$e_4$与$e_2$中有部分项相同，这就保证了相乘相加后有部分展开项被消掉了，从而破坏了因式相乘的结构，使得前文提到的化简方法失效。

参考文献

[1] Liu, Binbin, Junfu Shen, Jiang Ming, Qilong Zheng, Jing Li, and Dongpeng Xu. “MBA-Blast: Unveiling and Simplifying Mixed Boolean-Arithmetic Obfuscation,” 2021.

[2] Liu, Binbin, Weijie Feng, Qilong Zheng, Jing Li, and Dongpeng Xu. “Software Obfuscation with Non-Linear Mixed Boolean-Arithmetic Expressions.” In Information and Communications Security, edited by Debin Gao, Qi Li, Xiaohong Guan, and Xiaofeng Liao, 276–92. Lecture Notes in Computer Science. Cham: Springer International Publishing, 2021.