# Efficient Deobfuscation of Linear Mixed Boolean-Arithmetic Expressions

arXiv: https://arxiv.org/abs/2209.06335 · HTML: https://mlsanity.com/paper/2209.06335/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2022.

## Built on by (most cited first, 2 of 2)

- [gMBA: Expression Semantic Guided Mixed Boolean-Arithmetic Deobfuscation Using Transformer Architectures](https://mlsanity.com/paper/2506.23634/) (2025)
- [GPU-Accelerated Synthesis of Mixed-Boolean Arithmetic: Beyond Caching](https://mlsanity.com/paper/2605.08243/) (2026)

## Abstract (arXiv)

Mixed Boolean-Arithmetic (MBA) expressions are frequently used for obfuscation. As they combine arithmetic as well as Boolean operations, neither arithmetic laws nor transformation rules for logical formulas can be applied to suitably complex expressions, making MBAs hard to simplify and solve. In 2019, Liu et al. demystified linear MBAs, leveraging a transformation between the set B=0,1 of bit values and the set Bn of words of length n∈mathbbN for linear MBAs, originally introduced by Zhou et al. in 2007. With their MBA-Blast and MBA-Solver algorithms, they outperform existing tools noticably in terms of performance as well as ability to simplify of such MBAs. We propose a surprisingly simple algorithm called SiMBA that improves upon MBA-Blast and MBA-Solver in that it can deobfuscate all linear MBAs, does not miss particularly simple solutions and takes only a fraction of their runtime.