A Verified Timsort C Implementation in Isabelle/HOL

Yu Zhang, Yongwang Zhao, David SanánarXiv 2018 · arXiv

TL;DR

This paper presents a formally verified C implementation of the Timsort algorithm, a widely used sorting algorithm. By leveraging the Isabelle/HOL theorem prover and its embedded imperative language Simpl, the authors achieve a machine-checked proof of correctness and then generate C code, offering a reliable Timsort implementation for C-based systems.

What Problem Does This Paper Address?

Ensuring the reliability of software is paramount, especially for fundamental algorithms like sorting that are used in countless applications. While Timsort is a sophisticated and efficient sorting algorithm, widely adopted in languages like Python and Java, a formally verified implementation in C, a ubiquitous programming language, has been lacking. Existing efforts have focused on Java (using tools like KeY) or have produced unverified C implementations. This paper addresses this gap by providing a formally verified Timsort implementation in C, bridging the divide between high-level algorithmic correctness and low-level, production-ready code.

Methods

The core of this work lies in a two-step process: formal specification and verification using Isabelle/HOL, followed by code generation.

  1. Formal Specification and Verification in Isabelle/HOL: The authors use Simpl, a generic imperative language embedded within the Isabelle/HOL theorem prover. Simpl is designed for program verification and closely mirrors C-like syntax, making it suitable for specifying imperative algorithms. Timsort's logic is translated into Simpl, and its correctness is then formally proven using Isabelle/HOL's theorem proving capabilities. This includes proving functional correctness and, crucially, verifying stack invariants that are essential for Timsort's efficiency and stability. The paper highlights the use of a verification condition generator (VCG) within Simpl to simplify the proof process.
  2. Manual C Code Generation: After the Simpl specification is formally verified, the authors manually translate it into a C implementation. The C-like syntax of Simpl facilitates a straightforward translation. This manual generation is then tested against a set of random test cases.

Datasets

Not discussed in the paper. The paper focuses on the formal verification of an algorithm and its implementation, rather than training or evaluating on specific datasets. Test cases are generated randomly.

Key Insights and Ideas

  • Bridging the Gap: The paper demonstrates a practical approach to obtaining formally verified C code from high-level specifications. This is crucial for critical software components where reliability is paramount.
  • Simpl as an Effective Intermediate Language: Simpl's C-like syntax and its integration with Isabelle/HOL proved to be a powerful combination for specifying and verifying imperative algorithms like Timsort.
  • Focus on Stack Invariants: A significant portion of the verification effort is dedicated to proving Timsort's complex stack invariants. The paper highlights a previously identified bug in OpenJDK's implementation related to these invariants, underscoring their importance.
  • Modularity in Verification: The authors emphasize the benefits of modularity in formal verification, allowing different aspects of an algorithm (e.g., correctness, stability) to be verified separately, which simplifies the overall process.
  • Efficiency of VCG: The paper suggests that using Isabelle/HOL's VCG leads to a less proof-intensive effort compared to other verification tools like KeY for similar tasks.

Key Results

  • A formally verified specification of the Timsort algorithm in Simpl within Isabelle/HOL.
  • A manually generated C implementation of Timsort derived from the verified Simpl specification.
  • The C implementation has been tested with random test cases and its correctness is validated by comparing its output with that of the standard C library's quicksort.
  • The authors report a proof effort of 1,600 lines within Isabelle/HOL, which they suggest is less than comparable efforts in other systems.

Limitations and Future Work

  • Manual Code Generation: The current C code generation is manual, which is prone to errors and not scalable for large programs. The authors express a desire to automate this translation process by building a verified compiler from Simpl to C.
  • Performance Testing: While the C implementation is tested for correctness, a comprehensive performance evaluation using benchmarks is planned for future work.
  • Full Functional Correctness: The paper primarily focuses on stack invariants and functional correctness. Future work aims to formally verify the full functional correctness of the Timsort implementation.

Summary updated

BibTeX
@misc{zhang2018verified,
  author = {Yu Zhang and Yongwang Zhao and David Sanán},
  title = {{A Verified Timsort C Implementation in Isabelle/HOL}},
  year = {2018},
  eprint = {1812.03318},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1812.03318},
}
Figure