Model Checking and the State-Space Explosion · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

Checking a design by exploring its states

Computing · Software Engineering · ages 23-24
Name ______________________   Date ____________

  1. A safety check returns a counterexample trace. What does the trace establish?

    • A suspected implementation failure with no modeled execution
    • A proof that all possible model executions satisfy safety
    • An allowed model execution that violates the safety property

  2. What must a completed finite-state model check cover?

    • Only states on one randomly sampled execution of the model
    • All reachable behavior needed to decide the stated property
    • Only the initial state and its immediate outgoing transitions

  3. The product of component state counts bounds possible global combinations, but fewer combinations may be reachable.

    Circle one:   True   False

  4. A lock model records (a,b), with A's bit first and B's second. A bit of 1 means holding. The trace is (0,0) -> (0,1) -> (1,1). Which transition violates mutual exclusion?

    • B acquires while neither client holds the lock
    • A acquires while B still holds the lock
    • Both clients release their locks at the same time

  5. Three components have 2, 3 and 4 local states. What is the product bound on global state combinations?

    • 24 combinations
    • 9 combinations
    • 12 combinations

  6. Which pair describes abstraction methods that can support a sound safety check when their preservation conditions are proved?

    • Hide variable names; delete all transitions into violating states
    • Keep randomly selected runs; treat no sampled violation as a proof
    • Hide data conservatively; merge states with equivalent relevant behavior

  7. A conservative abstraction returns a violating trace, but no matching execution exists in the original model. What should you conclude?

    • The original model has that bug because every abstract trace is concrete
    • The trace is spurious; refine the abstraction and check again
    • The original model is safe because this single abstract trace was spurious

  8. An abstract model passes a safety check. Which fact supports transferring that result to the concrete model?

    • Concrete runs and their violations are preserved in the abstraction
    • The abstract model has fewer states and finishes much sooner than before
    • Both models use the same property name and the same variable spellings
LightMySky · lightmysky.comW1-mt__pgZ0PzEZo-s1

Answer key

For grown-ups. Fold this page away before handing over the rest.

Checking a design by exploring its states W1-mt__pgZ0PzEZo-s1

  1. An allowed model execution that violates the safety property · The trace establishes a safety violation in the checked model. It does not alone establish that the implementation permits the same steps.
  2. All reachable behavior needed to decide the stated property · A completed check decides the property over reachable behavior. Symbolic representation can cover states without visiting them individually.
  3. True · Each global state selects local component states. Initial states and transition rules can make some combinations unreachable.
  4. A acquires while B still holds the lock · The final transition changes A's bit from 0 to 1 while B's bit stays 1. Both clients then hold the lock.
  5. 24 combinations · Multiply 2 x 3 x 4 = 24. This bounds possible combinations, not the number that must be reachable.
  6. Hide data conservatively; merge states with equivalent relevant behavior · Hidden data must retain its possible transition effects. Merging must preserve property-relevant future behavior.
  7. The trace is spurious; refine the abstraction and check again · The abstraction admitted extra behavior. Rejecting this trace does not establish safety against all other traces.
  8. Concrete runs and their violations are preserved in the abstraction · A concrete violating run would map to an abstract violating run. The abstract safety pass excludes that possibility.
Worksheet · LightMySky