Reproduce “EPSO: A Caching-Based Efficient Superoptimizer for BPF Bytecode” 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

Qian Zhu, Yuxuan Liu, Ziyuan Zhu, Shangqing Liu, Lei Bu

EPSO introduces a caching-based superoptimizer for eBPF bytecode, leveraging an offline phase to synthesize generalized rewrite rules via enumerative search and an online phase for efficient rule application. The system achieves average program size reductions of 11.12% and runtime reductions of 6.60% while drastically lowering optimization overhead compared to existing superoptimizers.

Key insights

  • Offloading computationally intensive superoptimization to an offline rule generation phase, combined with efficient online rule matching, effectively addresses the trade-off between optimization quality and practical efficiency.
  • Developing BPF-specific instruction slicing strategies, which focus on individual register/memory computation chains, and symbolic abstraction enhances the generality and reusability of discovered rewrite rules.
  • Incorporating advanced pruning techniques (e.g., distance estimation, memorizing failed states, disallowing redundant register definitions) within an IDDFS-based enumerative search significantly reduces the computational overhead of superoptimization while enabling comprehensive rule discovery.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.