Simplifying Mixed Boolean-Arithmetic Obfuscation by Program Synthesis and Term Rewriting

Abstract

Mixed Boolean Arithmetic (MBA) obfuscation transforms a pro- gram expression into an equivalent but complex expression that is hard to understand. MBA obfuscation has been popular to pro- tect programs from reverse engineering thanks to its simplicity and effectiveness. However, it is also used for evading malware detection, necessitating the development of effective MBA deob- fuscation techniques. Existing deobfuscation methods suffer from either of the four limitations: (1) lack of general applicability, (2) lack of flexibility, (3) lack of scalability, and (4) lack of correctness. In this paper, we propose a versatile MBA deobfuscation method that synergistically combines program synthesis, term rewriting, and an algebraic simplification method. The key novelty of our approach is that we perform on-the-fly learning of transformation rules for deobfuscation, and apply them to rewrite the input MBA expression. We implement our method in a tool called ProMBA and evaluate it on over 4000 MBA expressions obfuscated by the state-of-the-art obfuscation tools. Experimental results show that our method outperforms the state-of-the-art MBA deobfuscation tool by a large margin, successfully simplifying a vast majority of the obfuscated expressions into their original forms.