TL;DR
This paper presents the formal verification of Scala's LongMap, a realistic mutable hash table. The authors successfully verified its correctness using the Stainless verifier, introducing novel techniques for handling mutable data structures and reference swapping. This work not only validates a widely-used library component but also uncovers and fixes a subtle bug in the original implementation.
What Problem Does This Paper Address?
Verifying mutable data structures is significantly more challenging than verifying their purely functional counterparts. While purely functional data structures have seen great success with formal verification tools, mutable structures, which are common in practical programming, often lag behind. This gap is particularly pronounced in languages like Scala, where efficient mutable collections are prevalent. The authors aim to bridge this gap by tackling the formal verification of a complex, real-world mutable data structure: Scala's LongMap. This involves dealing with imperative features like in-place updates, resizing, and potential aliasing, which are notoriously difficult to model and verify.
Methods
The core of this work is the formal verification of Scala's LongMap using the Stainless program verifier. To achieve this, the authors employed several key techniques:
- Reference Implementation: They created an immutable map based on a list of tuples as a specification. The
LongMapoperations were then proven to correspond to this immutable specification. - New Stainless Construct: To handle the resizing of the hash table's underlying array (a common operation in mutable data structures), they introduced a novel "swap operation" into Stainless. This construct allows for replacing references without introducing aliasing, which is crucial for implementing the decorator pattern and managing mutable state.
- Decorator Pattern: The implementation was refactored using the decorator pattern, separating concerns between a fixed-size hash table (
LongMapFixedSize) and a resizable one (LongMap). This modular approach simplifies the verification process by breaking down the complexity. - Adaptations for Verifier: Several adaptations were made to the original Scala code to make it amenable to verification. This included replacing
whileloops with tail-recursive functions (which Stainless can handle efficiently) and using case classes instead of bitwise operations for data representation to improve SMT solver performance.
Datasets
Not discussed in the paper. The evaluation uses synthetic data generated for performance benchmarks.
Key Insights and Ideas
- The Challenge of Mutable Structures: The paper highlights that verifying mutable data structures is not just about proving correctness but also about adapting verification tools and techniques to handle imperative features like in-place updates and reference manipulation.
- The Power of the Swap Operation: The introduction of a "swap operation" in Stainless proved critical. It enabled the implementation of resizable data structures by allowing the replacement of underlying mutable state without violating Stainless's non-aliasing guarantees, thus expanding the verifier's expressiveness.
- Decorator Pattern for Modularity: Using the decorator pattern was instrumental in managing the complexity of verification. By separating the fixed-size core from the resizing logic, the proof effort was significantly reduced and made more modular.
- Subtle Bugs in Production Code: The verification process uncovered a critical bug in the original
LongMapimplementation related to itsrepackoperation, which could lead to an infinite loop for large hash tables. This underscores the value of formal verification in finding bugs that might be missed by traditional testing or bounded model checking.
Key Results
- Full Formal Verification: The authors successfully achieved full formal verification of Scala's mutable
LongMapusing Stainless. - Bug Discovery and Fix: A bug in the
repackoperation, causing an infinite loop for large hash tables (specifically, after inserting 2^28 elements), was identified and fixed. This bug was not previously known and highlights the limitations of bounded model checking. - Performance: The verified implementation shows a performance slowdown of approximately 1.5x compared to the original
LongMapin lookups. The authors argue this is acceptable given the benefits of formal verification. An "optimized" version (Opti) that sacrifices some verification-friendly adaptations brings the performance closer to the original, suggesting that the overhead is largely due to verification-specific changes. - Codebase: The paper provides the verified code as an open-source contribution.
Limitations and Future Work
- Performance Overhead: While the performance is deemed acceptable, there is a noticeable slowdown compared to the original implementation. The authors attribute this to verification-specific adaptations like pointer indirection in the
_valuesarray and the use ofArray.fill. Future work could explore more efficient ways to handle these aspects. - Subset of Scala: Stainless supports a subset of Scala. While the authors adapted the code, full Scala support would be ideal.
- Future Directions: The authors suggest that the techniques developed, particularly the swap operation and the modular verification approach, can be applied to verify other complex mutable data structures in Scala. Further improvements to Stainless's support for imperative features would also be beneficial.
Summary updated