A Case Study in Analytic Protocol Analysis in ACL2

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

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.

Introduction: The Challenge of Asymptotic Analysis

In formal verification, understanding the long-term or "asymptotic" behavior of a system is crucial for ensuring stability. This requires real analysis—the study of limits and calculus. However, a technical rift exists within the ACL2 ecosystem. Standard ACL2s, optimized for computer system verification, operates on rational numbers and cannot represent irrationals or logarithms. Conversely, ACL2(r) supports real numbers but is theoretically incompatible with standard ACL2s models. This paper explores how to bridge this gap by proving fundamental limits within a rational-only framework.

Case Study: TCP Retransmission TimeOut (RTO)

The authors use the TCP Retransmission TimeOut (RTO) calculation (RFC 6298) as a practical case study. To prove the protocol's stability, one must demonstrate that the RTO remains bounded over time. A core component of this proof involves showing that for any $\alpha \in [0, 1)$, the limit of $\alpha^n$ as $n \to \infty$ is 0.

TCP Retransmission TimeOut (RTO) sampling and packet loss scenario.

Comparing Proof Strategies

The paper evaluates three distinct approaches to proving $\lim_{n \to \infty} \alpha^n = 0$:

  1. The "Real" Proof (ACL2(r)): This follows the standard textbook derivation using logarithms. While intuitive, it relies on irrational numbers, making it non-portable to standard ACL2s.
  2. The Ceiling Proof (ACL2s): A manual $\epsilon-\delta$ proof using the "ceiling" function to find a threshold $n$. This approach proved arduous due to the lack of pre-existing library support for ceiling function properties.
  3. The Binomial Proof (ACL2s): A semi-automatic approach using the binomial theorem to "squeeze" the value. The authors creatively leveraged ACL2s’s automated termination analysis to find the necessary $\delta$ threshold.
The standard "Real" proof strategy for the limit of $\alpha^n$ using logarithms, which requires irrational number support.

Key Results and Insights

The semi-automatic Binomial proof emerged as the most efficient method for ACL2s users, being shorter than the "natural" real-number proof and significantly faster than the manual rational proof.

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

A major insight was the "Portability Paradox": although rationals are dense in reals, the logical frameworks for the two are often mutually exclusive. The authors also demonstrated that "hacking" termination analysis can effectively automate the discovery of limit thresholds.

Conclusion and Future Work

The study highlights the need for better "bridges" between real and rational logic systems in formal methods. Future work includes developing a formal mechanism to translate proofs from ACL2(r) to ACL2s and extending analysis to 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},
}
Figure