Reproduce “Non-Termination Proving: 100 Million LoC and Beyond” 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

Julien Vanegue, Jules Villard, Peter O'Hearn, Azalea Raad

Researchers from Bloomberg, Meta FAIR, Imperial College London, and University College London developed `Pulse∞`, a static analysis tool capable of detecting non-termination (divergence) in programs. The tool analyzed over 100 million lines of C, C++, and Hack code, identifying more than 30 previously unknown divergence issues in open-source projects like the Linux kernel and OpenSSL.

Key insights

  • Achieving sound non-termination proving at industrial scale (100M+ LoC) is feasible by combining under-approximation, compositional reasoning, and advanced symbolic execution.
  • Under-approximate detection of repeating abstract states provides a robust method for identifying true divergence, minimizing false positives crucial for industrial adoption.
  • Most divergence bugs are 'shallow,' meaning a small loop unrolling bound (e.g., k=3) is highly effective for detection, contributing to analysis efficiency.

Summary by alphaXiv.

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