Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Abstraction-Based Model Checking for Real-Time ...

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.

Transcript

59 slides
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 8 XSTS language constructs Assumption Assignment Non-deterministic assignment Conditional operation

    assume y > x; havoc x; y := x + 1; if (x > 0) { ... } else { ... }
  7. 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. 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 { ... }
  9. • XSTS extended by clock variables and clock operations Clock

    set / reset c := 0; c := 500; 9 The TXSTS formalism – Timed XSTS
  10. • 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 || …) …
  11. • 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;
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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;
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 14 Control flow splitting Operation Transformed operation Constraints over Bool

    vars Transformation: introducing new Boolean variables, and constraints on these variables
  31. 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
  32. 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
  33. 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
  34. 15 Boolean vars + constraints: satisfying assignment  control flow

    Example – operation transformation if (x == 0 && c < 5) { x := x + 1; } else { c := 0; } Clock Data
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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; }
  40. 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; }
  41. 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; }
  42. 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  (b3b4)(b3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; }
  43. 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  (b3b4)(b3b4) • 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; }
  44. 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  (b3b4)(b3b4) • b2  b3 • b2  b4 if (x == 0 && c < 5) { x := x + 1; } else { c := 0; }
  45. 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  (b3b4)(b3b4) • b2  b3 • b2  b4
  46. 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  (b3b4)(b3b4) • b2  b3 • b2  b4 assume !(x == 0); c := 0;
  47. 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  (b3b4)(b3b4) • b2  b3 • b2  b4 assume !(x == 0); c := 0; assume !(c < 5); c := 0; assume x == 0; assume c < 5; x := x + 1;
  48. 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
  49. 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
  50. 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

More Decks by Critical Systems Research Group

Other Decks in Research