混合布尔算术(第 1 部分):介绍

这段代码主要介绍了混合布尔算术(Mixed Boolean-Arithmetic,MBA)的相关内容,包括一个计算两数之和的函数hmm以及一个更复杂的计算两数之和的函数what,还介绍了生成 MBA 表达式的基本原理、线性 MBA 和置换多项式等概念,并讨论了如何混淆常数以及生成非线性 MBA 的方法等。

主要观点和关键信息:

  • hmm函数通过(x ^ y) + 2 * (x & y)计算两数之和,其中x ^ y是无进位加法,x & y是产生进位的位,乘以 2 后移到正确位置相加。
  • what函数也用于计算两数之和,其中zw的值不重要。
  • MBA 表达式使用线性 MBA 身份和置换多项式这两个原语,线性 MBA 是布尔表达式的线性组合,置换多项式对(n)位整数进行置换。
  • 自动生成线性 MBA 身份的方法是制作输入输出表格,通过求解线性方程组来确定系数,但表格规模大且求解系统困难,利用位运算函数的性质可限制输入规模。
  • 置换多项式的简单特征是多项式的某些系数满足特定条件,求逆较困难,对于高次多项式尚无简单公式。
  • 可以通过混淆常数来组合 MBA 原语,如将常数用线性 MBA 表示,但要注意常数函数的特殊性质,还可以通过将线性 MBA 转换为非线性 MBA 来增加抗混淆性,如用线性 MBA 重写常数因子、用线性 MBA 重写常数 1 后与其他表达式相乘、使用置换多项式等。

重要细节:

  • 对于hmm函数,以 2 位数字为例,通过表格验证了(x ^ y) + 2 * (x & y)等于x + y(mod 4),并可将其写成矩阵形式求解线性方程组。
  • 置换多项式的示例中,以(8)位整数为例,说明了如何根据条件确定多项式及其逆。
  • 在混淆常数的例子中,通过具体代码展示了如何用线性 MBA 表示常数,并说明了求解等价性的方法和时间消耗。
  • 介绍了生成非线性 MBA 的不同方法,如重写常数因子、重写常数 1 后相乘、使用置换多项式等,并说明了验证等价性的时间消耗。

总的来说,这段内容详细介绍了 MBA 的相关概念和技术,包括函数实现、原理分析和应用示例等。

阅读 16
0 条评论