Facing infinity in model checking expressive specification languages

Society relies on increasingly complex software and hardware systems, hence techniques capable of proving that they behave as expected are of great and growing interest. Formal verification procedures employ mathematically sound reasoning to address this need. This thesis proposes novel techniques for the verification and falsification of expressive specifications on timed and infinite-state systems. An expressive specification language allows the description of the intended behaviour of a system via compact formal statements written at an abstraction level that eases the review process. Falsifying a specification corresponds to identifying an execution of the system that violates the property (i.e. a witness). The capability of identifying witnesses is a key feature in the iterative refinement of the design of a system, since it provides a description of how a certain error can occur. The designer can analyse the witness and take correcting actions by refining either the description of the system or its specification. The contribution of this thesis is twofold. First, we propose a semantics for Metric Temporal Logic that considers four different models of time (discrete, dense, super-discrete and super-dense). We reduce its verification problem to finding an infinite fair execution (witness) for an infinite-state system with discrete time. Second, we define a novel SMT-based algorithm to identify such witnesses. The algorithm employs a general representation of such executions that is both informative to the designer and provides sufficient structure to automate the search of a witness. We apply the proposed techniques to benchmarks taken from software, infinite-state, timed and hybrid systems. The experimental results highlight that the proposed approaches compete and often outperform specific (application tailored) techniques currently used in the state of the art.

Grantor dc:publisher

Università degli studi di Trento

Year dc:date

2022

Author dc:creator

• Magnago, Enrico

Contributors dc:contributor

• co-advisor: Griggio, Alberto

• Formal Verification, Model Checking, Linear-time Temporal Logic, Metric Temporal Logic, Infinite-state Systems, Timed Systems, SMT

Statement dc:rights

• info:eu-repo/semantics/openAccess
• license:Creative commons
• license uri:http://creativecommons.org/licenses/by-nc/4.0/

Language dc:language

eng

Identifier

http://dx.doi.org/10.15168/11572_356869
10.15168/11572_356869

OAI identifier oai:identifier

oai:iris.unitn.it:11572/356869