Formal Specification and Verification of Task Time Constraints for Real-Time Systems

Ning Ge (1) , Marc Pantel (1, 2) , Xavier Crégut (1, 2)

1 IRIT-ACADIE - Assistance à la Certification d’Applications DIstribuées et Embarquées
2 Toulouse INP - Institut National Polytechnique (Toulouse)

Model-Driven Engineering enables to assess a system's model properties since the early phases of its lifecycle and to improve iteratively these models according to the verification results. Safety critical real-time systems have stringent requirements related to the specification and verification of system's task-level time constraints. The common formal methods used to assess these properties for design models rely on a translation of the user models into formal verification languages like Time Petri Net and on the expression of the required properties using Timed LTL (Linear Temporal Logic)/CTL (Computation Tree Logic) or mu-calculus. However, these logics are mainly used to assess safety and liveness properties. Their capability for expressing time related properties is more limited and can lead to combinatorial state space explosion problems during model checking. In addition, they are mainly concerned with symbolic time event-level properties without quantitative time tolerance aspects. This contribution focuses on a formal specification and verification method for system's task-level time constraints (including synchronization, coincidence, exclusion, precedence, sub-occurrence and causality) in both finite and infinite time scope. It proposes a method to translate task time constraints that cannot be assessed by common tools to verifiable time property specifications, which are composed of a set of verifiable time property patterns. These time property patterns are quantitative and independent of both the design modeling language and the verification language as soon as it provides timed elements, making the translation method reusable with different tools. Then, observer-based model checking for Time Petri Nets is used to verify these time property patterns. This contribution analyses the computational complexity and the method's performance for the various patterns. This synchronization properties' specification and verification methods have been integrated in a time property verification framework for UML-MARTE safety critical real-time systems.

Mots clés: Keywords: MDE; RTS; Task; Time Constraint; Formal Specification; Verification; Time Property Patterns; Time Petri Net; Observer-Based Model Checking

Domaines: Modélisation et simulation; Systèmes embarqués; Génie logiciel [cs.SE]

Ning Ge, Marc Pantel, Xavier Crégut. Formal Specification and Verification of Task Time Constraints for Real-Time Systems. 2012. ⟨hal-00695622⟩