Reproduce “Simplifying MBA Expression Using E-Graphs” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Seoksu Lee, Hyeongchang Jeon, Eun-Sun Cho
Researchers at Chungnam National University developed an E-graph-based term rewriting method for simplifying Mixed Boolean Arithmetic (MBA) expressions, a technique used in code obfuscation. This approach achieved an average processing time of less than 0.1 seconds per MBA expression and demonstrated up to a 34.33% reduction in expression size, outperforming previous deobfuscation tools in speed.
Key insights
- E-graphs effectively manage and rewrite complex MBA expressions, enabling systematic simplification while inherently preserving semantic equivalence.
- A focused set of basic rewriting rules, when combined with the efficiency of E-graphs, can yield substantial speed improvements in deobfuscation compared to prior methods.
- The inherent characteristics of MBA expressions, such as linearity, polynomial structure, and the presence of constants, significantly influence the achievable simplification ratio and success rate of the process.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.