线性MBA反混淆

背景：线性MBA混淆

1. 定义

• 什么是BA(Boolean-Arithmetic)
  n 为一个正整数，且B={0，1}，那么下面这个代数系统可以成为BA
  
  其中<<,>>代表着左右移位，·代表着乘法，s代表着有符号数的运算。
• 什么是线性MBA Expression
  
  

2. 应用方式举例

例子：
如果存在

那么可以移项

则运算x-y即可由右边的运算混淆代替。
更多的例子:

3. 线性MBA的生成方式

4. 给出混淆过程定义

5. 关键定理的证明

现有工作：mba-blast or 化简引擎

1. 化简思路：

• 1.使用z3等约束求解器进行化简，时间非常长且效果不尽人意
• 2.mba-blast工具(最新论文 MBA-Blast: Unveiling and Simplifying Mixed
  Boolean-Arithmetic Obfuscation)

2. mba-blast数学原理

3. 进一步的

4. 总结

• 在MBA-Blast工具中化简线性mba混淆采用的是迭代化简的过程，它证明了任何mba都可以不断迭代化简，最后化简为简单的形式，因此其算法需要迭代公式库，且变量数目越多需要的化简公式也越多。
• 而进一步的可以发现，本质上是一个线性代数问题，通过构造几个真值向量能够作为极大线性无关组的位运算组合，就能够通过矩阵求逆的方式将任何MBA化简至该位运算组合的表示下。因此只要选取简单的位运算组合，例如x,y,x^y,-1等，即可实现化简。