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 check fails and returns a counterexample trace. What is it?

    • A guess at where the bug might be
    • A proof that the system is safe
    • A run of the model that reaches the bug

  2. What does a model checker explore?

    • Only the starting state
    • Every reachable state of a finite model
    • One randomly picked run

  3. Adding components multiplies the number of states.

    Circle one:   True   False

  4. You modeled a small protocol and got a failing trace. How do you use it?

    • Delete the trace and rerun
    • Read it back as a bug in the design
    • Ship the model since traces are normal

  5. Your check will not finish. Following the lesson, what do you do?

    • Shrink the model with an abstraction that keeps the property intact
    • Check fewer states at random
    • Rewrite the property until it passes

  6. Which two cuts respect the lesson's rule for shrinking a model?

    • Drop the property and sample at random
    • Add components and hope for speed
    • Hide detail the property never mentions and merge states it cannot tell apart

  7. A check fails. Which output helps you most, and why?

    • The state count, showing how big the model is
    • The counterexample trace, showing the exact run that breaks the property
    • The runtime, showing how long the check took

  8. A teammate says a passing check on any small model proves the real system safe. What is missing?

    • The abstraction must preserve the property, or the pass means nothing
    • Small models are always wrong
    • Passing checks never matter
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. A run of the model that reaches the bug · The trace is a concrete path ending in the violation.
  2. Every reachable state of a finite model · Checking means visiting every state the model can reach.
  3. True · Each new component multiplies the combinations the checker must visit.
  4. Read it back as a bug in the design · The trace shows the design flaw in action.
  5. Shrink the model with an abstraction that keeps the property intact · Abstract the model down, never the meaning of the property.
  6. Hide detail the property never mentions and merge states it cannot tell apart · Both cuts shrink states while the property keeps its meaning.
  7. The counterexample trace, showing the exact run that breaks the property · The failing run is the finding: it pinpoints the flaw.
  8. The abstraction must preserve the property, or the pass means nothing · A pass only speaks about the real system through a faithful abstraction.
Worksheet · LightMySky