Share
Abstraction-Based Model Checking for Real-Time Software-Intensive System Models
Real-time scheduling requirements, complex timed behavior, computations with external data and heavily data-dependent computations make the verification of real-time software-intensive systems difficult. Complex toolchains, such as statechart-based modeling are often required to adequately express these behaviors. However, existing low-level formalisms for timed model checking lack the expressive power to represent system models from high-level modeling toolchains. Moreover, formal verification is adversely affected by the possible interdependence of data-dependent behavior and scheduling. We propose an intermediate modeling formalism to represent timed systems with complex data-driven behaviors, as well as an adaptation of abstraction-based model checking approaches to enable the verification of these models, handling complex control flows caused by component communication and hierarchical modeling.
Critical Systems Research Group
Transcript
59 slides
-
Abstraction-based model checking for real-time software-intensive system models Dóra Cziborová
Alpine Verification Meeting 2024 -
Model checking 2 System Requirement Formalized requirement Formal model Model
checker 🗸 ✗ Reachability -
Model checking – system models 3 • Focus: real-time software-
intensive systems • State-based representation, e.g. statecharts System Requirement Formalized requirement Formal model Model checker 🗸 ✗ Reachability -
Model checking – formal models 4 • Intermediate formalisms: •
High-level language constructs • More expressive than low-level formal models • Easier mapping from system models • The XSTS formalism – eXtended Symbolic Transition System System Requirement Formalized requirement Formal model Model checker 🗸 ✗ Reachability -
Model checking – abstraction 5 System Requirement Formalized requirement Formal
model Model checker 🗸 ✗ • # of data variables • Continuous time • Abstraction • State space: abstract reachability graph (ARG) state space explosion Reachability -
6 I. An intermediate formalism is required • Existing formalism:
timed automata • Extending the XSTS formalism by timing II. Supporting the verification of timed XSTS models • Usual challenges of timed verification • Challenges specific to the timed XSTS formalism Steps to verify timed software-intensive models -
7 The XSTS formalism type State : {Q} ctrl var
state : State = Q var x : integer = 0 var y : integer = 0 trans { if (state == Q) { choice { havoc x; } or { y := x + 1; } } } Environment Simple statechart model XSTS representation -
8 XSTS language constructs Assumption Assignment Non-deterministic assignment assume y
> x; havoc x; y := x + 1; -
8 XSTS language constructs Assumption Assignment Non-deterministic assignment Conditional operation
assume y > x; havoc x; y := x + 1; if (x > 0) { ... } else { ... } -
8 XSTS language constructs Assumption Assignment Non-deterministic assignment Conditional operation
Non-deterministic operation assume y > x; havoc x; y := x + 1; if (x > 0) { ... } else { ... } choice { ... } or { ... } or { ... -
8 XSTS language constructs Assumption Assignment Non-deterministic assignment Conditional operation
Non-deterministic operation Counting loop assume y > x; havoc x; y := x + 1; if (x > 0) { ... } else { ... } choice { ... } or { ... } or { ... for i from 0 to x do { ... } -
• XSTS extended by clock variables and clock operations 9
The TXSTS formalism – Timed XSTS -
• XSTS extended by clock variables and clock operations Clock
set / reset c := 0; c := 500; 9 The TXSTS formalism – Timed XSTS -
• XSTS extended by clock variables and clock operations Clock
set / reset c := 0; c := 500; 9 The TXSTS formalism – Timed XSTS Clock constraints assume c1 – c2 > 0; if (c > 500 || …) … -
• XSTS extended by clock variables and clock operations Clock
set / reset c := 0; c := 500; 9 The TXSTS formalism – Timed XSTS Clock constraints Increment all clocks assume c1 – c2 > 0; if (c > 500 || …) … __delay; -
10 Verification approaches for TXSTS models Engineering model High-level formal
model TXSTS Mapping to intermediate formalism -
10 Verification approaches for TXSTS models Engineering model High-level formal
model TXSTS Mapping to intermediate formalism High-level formal model XSTS Time → data transform. -
10 Verification approaches for TXSTS models Engineering model High-level formal
model TXSTS Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Time → data transform. -
Abstract data domain 10 Verification approaches for TXSTS models Engineering
model High-level formal model TXSTS Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Time → data transform. -
Abstract data domain 10 Verification approaches for TXSTS models Engineering
model High-level formal model TXSTS Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Result of verification Time → data transform. -
Abstract data domain 10 Verification approaches for TXSTS models Engineering
model High-level formal model TXSTS Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Result of verification Mapping Time → data transform. -
Abstract data domain 10 Verification approaches for TXSTS models Engineering
model High-level formal model TXSTS Modified combined verification algorithm Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Result of verification Mapping Time → data transform. -
Abstract data domain Abstract data domain 10 Verification approaches for
TXSTS models Engineering model High-level formal model TXSTS Modified combined verification algorithm Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Result of verification Mapping Time → data transform. -
Abstract data domain Abstract data domain 10 Verification approaches for
TXSTS models Engineering model High-level formal model TXSTS Modified combined verification algorithm Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Abstract time domain Result of verification Mapping Time → data transform. -
Abstract data domain Abstract data domain 10 Verification approaches for
TXSTS models Engineering model High-level formal model TXSTS Modified combined verification algorithm Mapping to intermediate formalism High-level formal model XSTS Abstraction algorithms Abstract time domain Result of verification Mapping Time → data transform. -
11 • Clocks to rational variables • Clock operations to
data operations 1st approach: transformation of TXSTS to XSTS c1 := 0; Clock variable Data variable c1 := 0; -
11 • Clocks to rational variables • Clock operations to
data operations 1st approach: transformation of TXSTS to XSTS c1 := 0; havoc _d; assume _d >= 0; c1 := c1 + _d; c2 := c2 + _d; Clock variable Data variable __delay; c1 := 0; Advance of time _d is nondeterministic and nonnegative -
11 • Clocks to rational variables • Clock operations to
data operations • Existing algorithms can be used without modification • Efficient time abstraction techniques cannot be used 1st approach: transformation of TXSTS to XSTS c1 := 0; havoc _d; assume _d >= 0; c1 := c1 + _d; c2 := c2 + _d; Clock variable Data variable __delay; c1 := 0; Advance of time _d is nondeterministic and nonnegative -
12 • Existing abstraction-based techniques: lazy abstraction, CEGAR • Building
on combined abstraction – Lazy abstraction for timing, CEGAR for data 2nd approach: verification of TXSTS models -
12 • Existing abstraction-based techniques: lazy abstraction, CEGAR • Building
on combined abstraction – Lazy abstraction for timing, CEGAR for data 2nd approach: verification of TXSTS models -
12 • Existing abstraction-based techniques: lazy abstraction, CEGAR • Building
on combined abstraction – Lazy abstraction for timing, CEGAR for data 2nd approach: verification of TXSTS models -
13 • Existing abstraction-based techniques: lazy abstraction, CEGAR • Building
on combined abstraction – Lazy abstraction for timing, CEGAR for data Existing algorithms presume that the results of operations can be computed individually for timing and data 2nd approach: verification of TXSTS models -
13 • Existing abstraction-based techniques: lazy abstraction, CEGAR • Building
on combined abstraction – Lazy abstraction for timing, CEGAR for data Existing algorithms presume that the results of operations can be computed individually for timing and data • A problematic example, with data variable x and clock variable c if ((x == 0 && c > 500) || (x == 1 && c < 400)) { ... } 2nd approach: verification of TXSTS models -
13 • Existing abstraction-based techniques: lazy abstraction, CEGAR • Building
on combined abstraction – Lazy abstraction for timing, CEGAR for data Existing algorithms presume that the results of operations can be computed individually for timing and data • A problematic example, with data variable x and clock variable c if ((x == 0 && c > 500) || (x == 1 && c < 400)) { ... } • Solution: control flow splitting 2nd approach: verification of TXSTS models -
14 Control flow splitting Operation Transformed operation Constraints over Bool
vars Transformation: introducing new Boolean variables, and constraints on these variables -
14 Control flow splitting Operation Transformed operation Constraints over Bool
vars Transformation: introducing new Boolean variables, and constraints on these variables Satisfying assignment Control flow -
14 Control flow splitting Operation Transformed operation Constraints over Bool
vars Variable assignments Transformation: introducing new Boolean variables, and constraints on these variables All-SAT problem Satisfying assignment Control flow -
14 Control flow splitting Operation Transformed operation Constraints over Bool
vars Variable assignments Transformation: introducing new Boolean variables, and constraints on these variables Set of final operations All-SAT problem Satisfying assignment Control flow Independent timing and data, existing methods can be used for verification -
15 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } Clock Data -
15 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } if (b1) { assume x == 0 && c < 5; x := x + 1; } Clock Data -
15 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Clock Data -
15 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Clock Data Constraints: • b1 xor b2 -
16 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Clock Data Constraints: • b1 xor b2 if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } Clock Data -
16 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Constraints: • b1 xor b2 assume x == 0; assume c < 5; if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } -
16 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Constraints: • b1 xor b2 assume x == 0; assume c < 5; choice { assume !(x == 0); } or { assume !(c < 5); } if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } -
16 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Constraints: • b1 xor b2 assume x == 0; assume c < 5; choice { assume !(x == 0); } or { assume !(c < 5); } if (b3) { assume !(x == 0); } if (b4) { assume !(c < 5); } if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } -
16 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Constraints: • b1 xor b2 • b2 (b3b4)(b3b4) assume x == 0; assume c < 5; choice { assume !(x == 0); } or { assume !(c < 5); } if (b3) { assume !(x == 0); } if (b4) { assume !(c < 5); } if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } -
16 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0 && c < 5; x := x + 1; } if (b2) { assume !(x == 0) || !(c < 5); c := 0; } Constraints: • b1 xor b2 • b2 (b3b4)(b3b4) • b2 b3 • b2 b4 assume x == 0; assume c < 5; choice { assume !(x == 0); } or { assume !(c < 5); } if (b3) { assume !(x == 0); } if (b4) { assume !(c < 5); } if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } -
17 Boolean vars + constraints: satisfying assignment control flow
Example – operation transformation if (b1) { assume x == 0; assume c < 5; x := x + 1; } if (b2) { if (b3) { assume !(x == 0); } if (b4) { assume !(c < 5); } c := 0; } Constraints: • b1 xor b2 • b2 (b3b4)(b3b4) • b2 b3 • b2 b4 if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } -
18 Boolean vars + constraints: satisfying assignment control flow
Example – control flow with an SMT solver if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } if (b1) { b1 = false assume x == 0; assume c < 5; x := x + 1; } if (b2) { b2 = true if (b3) { b3 = true assume !(x == 0); } if (b4) { b4 = false assume !(c < 5); } c := 0; } Constraints: • b1 xor b2 • b2 (b3b4)(b3b4) • b2 b3 • b2 b4 -
18 Boolean vars + constraints: satisfying assignment control flow
Example – control flow with an SMT solver if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } if (b1) { b1 = false assume x == 0; assume c < 5; x := x + 1; } if (b2) { b2 = true if (b3) { b3 = true assume !(x == 0); } if (b4) { b4 = false assume !(c < 5); } c := 0; } Constraints: • b1 xor b2 • b2 (b3b4)(b3b4) • b2 b3 • b2 b4 assume !(x == 0); c := 0; -
18 Boolean vars + constraints: satisfying assignment control flow
Example – control flow with an SMT solver if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } if (b1) { b1 = false assume x == 0; assume c < 5; x := x + 1; } if (b2) { b2 = true if (b3) { b3 = true assume !(x == 0); } if (b4) { b4 = false assume !(c < 5); } c := 0; } Constraints: • b1 xor b2 • b2 (b3b4)(b3b4) • b2 b3 • b2 b4 assume !(x == 0); c := 0; assume !(c < 5); c := 0; assume x == 0; assume c < 5; x := x + 1; -
19 • Implemented in the Theta open source verification framework
• Two TXSTS models from Gamma engineering models: – Example model demonstrating the capabilities of Gamma: crossroad – Industrial case study: model of a safety-critical railway protocol • 30 reachability properties, analyzed in two ways: – Reachability of a given state – Timed reachability: reachability of given state under a given time limit Preliminary evaluation of the approaches -
20 • 3 CPU cores, time limit of 20 minutes,
memory limit of 15 GB • Best configurations of both approaches compared: number of verified properties, with mean CPU time • Reachability: same success rate, time→data transf. is faster • Timed reachability: control flow splitting is more successful Preliminary evaluation of the approaches Approach Verified properties with time limit of 20 minutes Reachability Timed reachability Time → data transformation 30/30 (100%) 7.48 s 12/30 (40%) 2.26 s Combined abstraction with control flow splitting 30/30 (100%) 11.09 s 18/30 (60%) 40.99 s -
21 Summary High-level formal model TXSTS Modified combined verification algorithm
Existing abstraction algorithms (no time abstraction) Result of verification Time → data transformation Control flow splitting