An In-Place Simplification on Mixed Boolean-Arithmetic Expressions
An In-Place Simplification on Mixed Boolean-Arithmetic Expressions
复制标题
DOI：
10.1155/2022/7307139
复制
发表时间：
2022-09
影响因子：
--
通讯作者：
Binbin Liu;Qilong Zheng;Jing Li;Dongpeng Xu
中科院分区：
文献类型：
--
作者：
Binbin Liu;Qilong Zheng;Jing Li;Dongpeng Xu
混合布尔算术（MBA）表达式，它涉及两种按位操作（例如，NOT、AND和OR）和算术运算（例如，+ 、−和）是一种软件混淆方案。另一方面，已经提出了多种方法来简化MBA表达式。其中，基于表格的解决方案是最有力的简化研究。然而，基于表的解决方案的一个基本限制是，转换表的空间复杂度随着MBA表达式中变量的数量而急剧增加。在这项研究中，我们提出了一种新的方法来简化MBA表达式，没有任何预先计算的要求。首先，一个按位表达式可以转换成一个统一的形式，我们提供了一个数学证明，以保证这种转换的正确性。然后，平滑地执行算术约简以进一步简化表达式并产生简洁的结果。我们实现了所提出的方案作为一个开源的工具，名为MBA-Flatten，并评估它的两个全面的基准。评价结果表明，MBA-Flatten是一种通用、有效的MBA简化方法。此外，MBA-Flatten可以帮助恶意软件分析，并提高SMT求解器在求解MBA方程时的性能。
Mixed Boolean-arithmetic (MBA) expression, which involves both bitwise operations (e.g., NOT, AND, and OR) and arithmetic operations (e.g., + , − , and ∗ ), is a software obfuscation scheme. On the other side, multiple methods have been proposed to simplify MBA expressions. Among them, table-based solutions are the most powerful simplification research. However, a fundamental limitation of the table-based solutions is that the space complexity of the transformation table drastically explodes with the number of variables in the MBA expression. In this study, we propose a novel method to simplify MBA expressions without any precomputed requirements. First, a bitwise expression can be transformed into a unified form, and we provide a mathematical proof to guarantee the correctness of this transformation. Then, the arithmetic reduction is smoothly performed to further simplify the expression and produce a concise result. We implement the proposed scheme as an open-source tool, named MBA-Flatten, and evaluate it on two comprehensive benchmarks. The evaluation results show that MBA-Flatten is a general and effective MBA simplification method. Furthermore, MBA-Flatten can assist malware analysis and boost SMT solvers’ performance on solving MBA equations.