Abstract
A system is data-independent with respect to a data type X iff the operations it can perform on values of type X are restricted to just equality testing. The system may also store, input and output values of type X. We study model checking of systems which are data-independent with respect to two distinct type variables X and Y, and may in addition use arrays with indices from X and values from Y. Our main interest is the following parameterised model-checking problem: whether a given program satisfies a given temporal-logic formula for all non-empty finite instances of X and Y. Initially, we consider instead the abstraction where X and Y are infinite and where partial functions with finite domains are used to model arrays. Using a translation to data-independent systems without arrays, we show that the μ-calculus model-checking problem is decidable for these systems. From this result, we can deduce properties of all systems with finite instances of X and Y. We show that there is a procedure for the above parameterised model-checking problem of the universal fragment of the μ-calculus, such that it always terminates but may give false negatives. We also deduce that the parameterised model-checking problem of the universal disjunction-free fragment of the μ-calculus is decidable. Practical motivations for model checking data-independent systems with arrays include verification of memory and cache systems, where X is the type of memory addresses, and Y the type of storable values. As an example we verify a fault-tolerant memory interface over a set of unreliable memories.
1. Introduction
In the field of formal verification, model checking serves as a rigorous method to ensure that systems, such as communication protocols or memory controllers, adhere to specified safety and liveness properties. A significant challenge in this domain is the verification of parameterized systems—systems designed to operate correctly regardless of the size of their underlying data types (e.g., a memory controller that must function whether it addresses 4 locations or 4 billion).
The concept of data independence provides a path forward: if a system's operations on a data type are restricted to equality testing (moving values without arithmetic or logical manipulation), properties can often be proven for any size of that data type. However, the introduction of arrays complicates this landscape. Arrays can store an unbounded number of values, potentially creating an infinite state space. While previous research established that adding a global "array reset" operation (clearing all elements simultaneously) renders the model-checking problem undecidable, this paper investigates whether decidability can be maintained in systems that utilize arrays but lack a reset operation.
2. Methodology
The authors propose a framework based on abstraction and syntactic translation to bridge the gap between complex array-based systems and decidable scalar systems.
2.1 Infinite Abstraction
The approach begins by considering an abstraction where the data types for indices ($X$) and values ($Y$) are infinite sets. In this context, arrays are modeled as partial functions with finite domains. An "undefined" entry in an array represents a location that has not yet been written to, effectively acting as a placeholder for future nondeterministic values. This abstraction allows the researchers to reason about the system's behavior without being constrained by specific finite bounds.
2.2 Syntactic Translation and Bisimulation
The core technical contribution is a method to translate a program containing arrays into a bisimulation-equivalent program that uses only a finite set of scalar variables. This is achieved by creating "shadow" variables; for instance, if a program uses an array $a$ and an index variable $x$, the translation introduces a variable $ax$ to track the current value of $a[x]$. The authors rigorously prove that this simplified, array-free program maintains the same temporal logic properties as the original.
2.3 Logic Framework
The properties are defined using the μ-calculus, a highly expressive temporal logic. By proving results within the μ-calculus, the authors ensure their findings apply to other widely used logics, such as LTL and CTL.
3. Key Insights
- The Finite View: The fundamental insight is that at any discrete point in a program's execution, it can only interact with a finite number of array elements—specifically those indexed by the variables currently in use. Despite the theoretical size of the array, the program's "spatial" interaction is always limited.
- Partiality as Nondeterminism: Treating uninitialized locations as "undefined" allows the system to handle the transition from infinite abstractions back to real-world finite instances.
- The Decidability Frontier: The research identifies a clear boundary for automated verification. While multiple arrays are permissible, the inclusion of a global reset operation is the "poison pill" that makes automated solving mathematically impossible.
4. Results and Case Study
The paper establishes several critical results regarding the decidability of the μ-calculus in these systems:
- Infinite Arrays: Model checking is proven decidable for the infinite-array abstraction.
- Universal Fragment: For finite systems, the "universal fragment" of the μ-calculus (properties holding for all execution paths) can be checked with a procedure that always terminates, though it may produce false negatives.
- Disjunction-Free Fragment: For the universal disjunction-free fragment, the problem is fully decidable with no false negatives.
To demonstrate practical utility, the authors verified a Fault-Tolerant Memory Interface. This system manages three unreliable memories by writing data to all three and using a majority vote during reads. Using the Murφ model checker, the authors successfully proved that the interface correctly returns the last written value regardless of memory size, even if one memory unit fails.
5. Conclusion and Future Work
This work demonstrates that model checking remains a viable tool for complex data-independent systems with arrays, provided they do not utilize global resets. While the current framework may produce false negatives for certain universal properties, it remains sound (no false positives). Future research directions include extending the translation to support multi-dimensional arrays and array-to-array assignments, with the ultimate goal of verifying industrial-scale cache-coherence protocols.
Summary updated