Linear-Time Verification of Data-Aware Dynamic Systems with Arithmetic

Paolo Felli, Marco Montali, Sarah WinklerAAAI 2022 · DOI

Introduction

In modern software engineering, particularly in AI and Business Process Management (BPM), systems are increasingly "data-aware." These systems do not just follow a sequence of steps; they make decisions based on complex data variables like prices, timers, or counters. Verifying the correctness of such systems is notoriously difficult. While checking simple control flows is straightforward, adding linear arithmetic constraints—such as requiring a new bid to be at least $10 higher than the previous one—often leads to undecidability. This is because arithmetic can be used to simulate universal computation, making it impossible for a general algorithm to guarantee an answer for all possible inputs.

The Finite Summary Property

The core contribution of this research is the introduction of the "finite summary" property. This semantic property provides a unified framework for identifying when a data-aware system can be safely reduced to a finite-state abstraction.

A system possesses a finite summary if its potentially infinite set of data states can be partitioned into a finite number of equivalence classes. These classes are represented by logical formulas, allowing a verification engine to reason about "regions" of data rather than specific values. By proving that this property enables a faithful finite-state abstraction, the authors demonstrate that checking linear-time properties ($LTL_f$) becomes decidable for a wide range of previously disconnected system classes.

Modeling Data-Aware Systems

The authors define these systems as Data-Aware Dynamic Systems with Arithmetic (DDSAs). To illustrate the complexity involved, the paper utilizes an auction process as a primary motivating example.

An auction process modeled as a DDSA with arithmetic constraints.

As shown in Figure 1, transitions in a DDSA depend on arithmetic guards (e.g., [d^r > 0]) and updates (e.g., [s^w = o^r + 10]). The finite summary property allows for the verification of properties like "a winner must always pay more than the starting price" without needing to simulate every possible numerical bid.

Unifying Decidable Fragments

Historically, researchers found "islands of decidability"—specific constraint types where verification was possible. This paper unifies these fragmented results by showing they are all instances of the finite summary property.

Examples of different constraint classes (monotonicity, gap-order, etc.) unified under the finite summary property.

As illustrated in Figure 2, the framework handles several well-known classes:

  • Monotonicity Constraints: Variables that only increase or decrease over time.
  • Gap-Order Constraints: Constraints requiring a minimum difference between variables (e.g., $x - y \ge 2$).
  • Feedback Freedom: Systems where data flow does not create infinite cycles of dependency.
  • Bounded Lookback: A new class introduced in this paper where a variable's current value depends only on a fixed, finite number of previous steps.

Practical Implementation and Results

The theoretical framework is supported by the ada tool, a prototype implementation using Python and the Z3 SMT solver. The authors evaluated ada using benchmarks from the business process mining community and complex examples like the auction system.

The results confirm that $LTL_f$ verification is decidable for any DDSA satisfying the finite summary property. Furthermore, the authors provide modularity theorems, allowing developers to mix different constraint types in different components of a large system while maintaining overall verifiability. For instance, one could use gap-order constraints for a timer and monotonicity for a price counter within the same verified model.

Conclusion

By moving from syntactic rules to a semantic "finite summary" property, this work provides a powerful, unifying lens for formal verification. It bridges the gap between control-flow analysis and data-driven reasoning, offering a path toward more robust and reliable automated systems in complex, data-heavy domains.

Summary updated

BibTeX
@inproceedings{felli2022linear,
  author = {Paolo Felli and Marco Montali and Sarah Winkler},
  title = {{Linear-Time Verification of Data-Aware Dynamic Systems with Arithmetic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i5.20505},
}
Figure