TL;DR
This paper introduces "Ontology-Based Processes" (OBPs), a novel model for dynamic systems that leverage Description Logic (DL) ontologies instead of traditional databases for background knowledge. The authors present an SMT-based backward reachability procedure to verify safety properties of OBPs, achieving a decidable PSPACE complexity. This work bridges the gap between formal verification of dynamic systems and the rich expressiveness of ontologies.
What Problem Does This Paper Address?
Verifying dynamic systems, especially those that interact with data, has been a long-standing challenge. Traditional approaches often rely on databases to store background information. However, in many real-world scenarios, this background knowledge is better represented by ontologies, which offer richer semantic expressiveness and can handle incomplete information. Existing formal models for data-aware processes, like artifact systems, typically assume complete data in databases. This paper tackles the problem of verifying safety properties for dynamic processes where the background knowledge is managed by an ontology, specifically one expressed in RDFS (a subset of OWL). The core challenge is to adapt existing verification techniques, which often rely on backward reachability, to work with the unique properties of ontologies, particularly their inherent incompleteness.
Methods
The authors introduce Ontology-Based Processes (OBPs), which are a variant of "simple artifact systems." In OBPs, the traditional read-only database is replaced by a Description Logic (DL) ontology. The system manipulates "artifact variables" (representing the current state) and uses "transitions" (actions) that query the ontology and update these variables.
The key technical contribution is an SMT-based backward reachability procedure for verifying safety properties of OBPs. This procedure is an adaptation of existing techniques for artifact systems but is specifically tailored for ontologies. The core of the method involves:
- Ontology Translation: RDFS ontologies are translated into first-order logic (FO) theories. Crucially, this translation results in a universal theory, which is essential for the subsequent steps.
- Model Completion: A critical theoretical result is proving that the FO translation of RDFS ontologies admits a model completion. This property is vital for ensuring that the verification procedure can make progress and terminate.
- Quantifier Elimination: The procedure relies on a quantifier elimination algorithm for the model completion of the ontology theory. This allows the backward reachability steps to maintain formulas in a manageable, quantifier-free form.
- Backward Reachability Algorithm: The algorithm starts from the set of "unsafe" states (defined by a safety formula) and iteratively computes symbolic preimages through the process transitions. This process continues until a fixpoint is reached (indicating safety) or an initial state is encountered (indicating unsafety).
Datasets
Not discussed in the paper. The paper focuses on a formal model and theoretical verification techniques rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Ontologies as Knowledge Bases for Processes: The paper demonstrates that ontologies can effectively serve as the knowledge base for dynamic processes, offering a more expressive and flexible alternative to traditional databases, especially for handling incomplete information.
- Model Completion is Key: The theoretical proof that RDFS ontologies admit a model completion is a significant finding. This property is not trivial to establish and is fundamental to making backward reachability work in this new setting.
- Bridging SMT and Ontologies: The work successfully bridges the gap between SMT-based verification techniques and the expressive power of DL ontologies, showing how existing powerful tools can be extended to handle richer knowledge representations.
- Decidability in PSPACE: Achieving a PSPACE upper bound for safety verification of OBPs is a strong theoretical result, indicating that the problem is computationally tractable within this framework.
- Justification for RDFS: The paper provides a theoretical justification for choosing RDFS (or its extensions) by showing that it possesses the necessary model-theoretic properties (like model completion) for their verification machinery, while other DLs might not.
Key Results
- Ontology-Based Processes (OBPs): A new formal model for dynamic systems using RDFS ontologies.
- SMT-based Backward Reachability: A novel algorithm for verifying safety properties of OBPs.
- Decidability in PSPACE: The safety problem for OBPs is shown to be decidable in PSPACE.
- Theoretical Guarantees: The paper proves that RDFS ontologies admit a model completion, which is crucial for the decidability results.
Limitations and Future Work
- RDFS Specificity: While the framework is designed to be generalizable to other DLs with similar model-theoretic properties, the current work focuses specifically on RDFS.
- DL-Lite and Other DLs: The authors are actively working on extending the framework to DL-Lite family of DLs and other expressive DLs, which present different translation properties (e.g., equisatisfiability instead of equivalence).
- More Sophisticated Artifact Models: Future work includes extending the approach to more complex artifact-centric models, such as relational artifact systems.
- Beyond Safety Properties: Investigating verification of other properties, such as liveness, is a key future direction. This will involve leveraging temporal logic frameworks like LTLfMT.
- Implementation: The proposed algorithm is not yet implemented in state-of-the-art model checkers, though the authors suggest how this could be achieved by extending existing tools like MCMT.
Summary updated