NeuReduce: Reducing Mixed Boolean-Arithmetic Expressions by Recurrent Neural Network

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 635–644 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 635 NeuReduce: Reducing Mixed Boolean-Arithmetic Expressions by Recurrent Neural Network Weijie Feng†, Binbin Liu†, Dongpeng Xu∗, Qilong Zheng†, Yun Xu† †University of Science and Technology of China ∗University of New Hampshire {fengwj, robbertl}@mail.ustc.edu.cn dongpeng.xu@unh.edu {qlzheng, xuyun}@ustc.edu.cn Abstract Mixed Boolean-Arithmetic (MBA) expres- sions involve both arithmetic calculation (e.g., plus, minus, multiply) and bitwise computa- tion (e.g., and, or, negate, xor). MBA expres- sions have been widely applied in software ob- fuscation, transforming programs from a sim- ple form to a complex form. MBA expres- sions are challenging to be simplified, because the interleaving bitwise and arithmetic opera- tions causing mathematical reduction laws to be ineffective. Our goal is to recover the orig- inal, simple form from an obfuscated MBA expression. In this paper, we first propose NeuReduce, a string to string method based on neural networks to automatically learn and reduce complex MBA expressions. We de- velop a comprehensive MBA dataset, includ- ing one million diversified MBA expression samples and corresponding simplified forms. After training on the dataset, NeuReduce can reduce complex MBA expressions to mathe- matically equivalent but concise forms. By comparing with three state-of-the-art MBA re- duction methods, our evaluation result shows that NeuReduce outperforms all other tools in terms of accuracy, solving time, and perfor- mance overhead. 1 Introduction Mixed Boolean-Arithmetic (MBA) expression emerges as a software obfuscation (Collberg and Nagra, 2009; Collberg et al., 2012; Ceccato, 2014; Bardin et al., 2017) technique, converting software into a syntactic different but semantic equivalent form. Software developers have broadly adopted MBA expressions obfuscation to resist malicious reverse engineering attacks or illegal cracking. For instance, software vendors (Mougey and Gabriel, 2014) and communication providers (Moghaddam et al., 2012) employ MBA obfuscation to protect critical information such as Digital Rights Man- agement (DRM) or communication protocols and protect users’ private contents. MBA obfuscation technology draws strength from its neat design and rigorous mathematical foundation (Zhou and Zhou, 2006; Zhou et al., 2007). It transforms a simple expression into an equivalent but more complex form, which con- tained mixed arithmetic and bitwise calculations. However, existing mathematical reduction rules can hardly simplify complex MBA expressions, be- cause they only fit either pure arithmetic or bitwise operation. Existing researches explore diverse so- lutions to conquer MBA obfuscation, including bit- blast (Eyrolles, 2017; Guinet et al., 2016), pattern matching (Eyrolles et al., 2016), and software syn- thesis (Blazytko et al., 2017). Nevertheless, these methods treat MBA expressions as black-boxes and neglect expressions’ inner structures, which led to inevitable limitations such as low simplification accuracy or high-performance penalty. In this paper, we propose NeuReduce1, a novel solution that utilizes neural networks to defeat com- plex MBA expressions. Our proposal can take com- plex MBA expression input as a character string for- mat and output the simplification results. NeuRe- duce leverages supervised learning to ensure the correctness and conciseness of its outputs. We also notice that no …

Content truncated to 500 words