A Case Study in Analytic Protocol Analysis in ACL2

Max von Hippel, Panagiotis Manolios, Kenneth L. McMillan, Cristina Nita-Rotaru, Lenore D. Zuck

TL;DR

This paper explores how to perform real analysis—specifically proving limits—within ACL2s, a theorem prover that natively supports only rational numbers. By developing a "rational-only" proof that $\alpha^n$ approaches zero, the authors enable the formal verification of long-term network protocol behaviors (like TCP's retransmission logic) without needing to migrate entire models to incompatible real-number systems.

What Problem Does This Paper Address?

In the world of formal verification, we often want to know how a system behaves in the "long run" (asymptotic behavior). This requires real analysis, the branch of math dealing with limits and calculus.

The challenge is a technical rift in the ACL2 theorem-proving ecosystem:

  1. Standard ACL2/ACL2s: Designed for verifying computer systems, it uses rational numbers. It cannot represent irrationals like $\sqrt{2}$ or the results of most logarithms.
  2. ACL2(r): A variant that supports real numbers but is theoretically incompatible with standard ACL2. You cannot easily move a proof from one to the other because their underlying assumptions about numbers conflict.

If you have a complex model of a network protocol in ACL2s and suddenly need to prove a limit to understand its stability, you are stuck. You either have to rebuild everything in ACL2(r) or find a way to prove "real" math using only "rational" tools. This paper tackles the latter.

Methods

The authors use the TCP Retransmission TimeOut (RTO) calculation (RFC 6298) as their case study. To prove the protocol is stable, they must prove a fundamental theorem: for any $\alpha$ between 0 and 1, the limit of $\alpha^n$ as $n$ goes to infinity is 0.

They compare three distinct proof strategies:

  • The "Real" Proof (ACL2(r)): The standard textbook approach using logarithms. This is the most intuitive but is not portable to standard ACL2s.
  • The Ceiling Proof (ACL2s): A manual $\epsilon-\delta$ proof. It uses the "ceiling" function to find a threshold $n$ where the value drops below a target $\epsilon$. This was "arduous" because it required proving many basic properties of the ceiling function that weren't in the standard libraries.
  • The Binomial Proof (ACL2s): A more clever approach using the binomial theorem to "squeeze" the value of $\alpha^n$. Crucially, they used a semi-automatic method where they leveraged ACL2s’s built-in termination analysis to automatically find the necessary $\delta$ for the proof.

Datasets

Not discussed in the paper. As a formal methods research paper, it relies on mathematical specifications (RFC 6298 for TCP RTO) and logical models rather than empirical datasets.

Key Insights and Ideas

  • The Portability Paradox: The authors highlight that even though rationals are "dense" in the reals (meaning you can get as close to any real number as you want using only fractions), the logical frameworks for the two are often mutually exclusive in automated reasoning.
  • Hacking Termination for Limits: One of the most creative "aha moments" was using ACL2s's automated termination analysis. By defining a function that recursively searches for a value and proving it terminates, the tool effectively proves the existence of a limit's threshold ($\delta$) for you.
  • Library Friction: A significant portion of the "work" in formal verification isn't the core logic, but building the "infrastructure"—proving basic arithmetic lemmas that a human would find trivial but a machine needs explicitly stated.

Key Results

The authors successfully proved that under "steady-state" conditions, the TCP RTO calculation remains bounded and predictable. They also provided a quantitative comparison of the proof efforts:

Proof Strategy Lines of Code Functions Certification Time
Real (ACL2(r)) 161 1 0.58s
Ceiling (Manual) 408 3 64.17s
Binomial (Semi-Auto) 122 2 3.84s

The Semi-Automatic Binomial proof emerged as the clear winner for ACL2s users. It was shorter than even the "natural" real-number proof and significantly more efficient than the manual rational proof.

Limitations and Future Work

  • Library Fragmentation: The authors noted that ACL2’s mathematical libraries are scattered and sometimes conflict, making it hard for new users to find the "right" way to prove simple arithmetic.
  • The Need for a "Bridge": A major suggestion for future work is the creation of a formal "bridge" between ACL2(r) and ACL2. This would allow researchers to prove a theorem in the "easy" real-number world and automatically justify its validity in the "rational" world of computer system models.
  • Analytic Sophistication: The current work assumes a "steady-state" where network samples fall within a fixed range. Future research could investigate more complex, dynamic network conditions using Lipschitz continuity.

Summary updated

Abstract

:When verifying computer systems we sometimes want to study their asymptotic behaviors, i.e., how they behave in the long run. In such cases, we need real analysis, the area of mathematics that deals with limits and the foundations of calculus. In a prior work, we used real analysis in ACL2s to study the asymptotic behavior of the RTO computation, commonly used in congestion control algorithms across the Internet. One key component in our RTO computation analysis was proving in ACL2s that for all alpha in [0, 1), the limit as n approaches infinity of alpha raised to n is zero. Whereas the most obvious proof strategy involves the logarithm, whose codomain includes irrationals, by default ACL2 only supports rationals, which forced us to take a non-standard approach. In this paper, we explore different approaches to proving the above result in ACL2(r) and ACL2s, from the perspective of a relatively new user to each. We also contextualize the theorem by showing how it allowed us to prove important asymptotic properties of the RTO computation. Finally, we discuss tradeoffs between the various proof strategies and directions for future research.
BibTeX
@inproceedings{hippel2023case,
  author = {Max von Hippel and Panagiotis Manolios and Kenneth L. McMillan and Cristina Nita-Rotaru and Lenore D. Zuck},
  title = {{A Case Study in Analytic Protocol Analysis in ACL2}},
  booktitle = {ACL2},
  year = {2023},
  url = {https://openreview.net/forum?id=aDCiOsFwUe},
}

Loading related content...

Figure