GUESSING, MODEL CHECKING AND THEOREM PROVING OF STATE MACHINE PROPERTIES – A CASE STUDY ON QLOCK

Abstract

It is worth understanding state machines better because various kinds of systems can be formalized as state machines and therefore understanding state machines has something to do with comprehension of systems. Understanding state machines can be interpreted as knowing properties they enjoy and comprehension of systems is interpreted as knowing whether they satisfy requirements. We (mainly the second author) have developed a tool called SMGA that basically takes a finite sequence of states from a state machine and generates a graphical animation of the finite sequence or the state machine. Observing such a graphical animation helps us guess properties of the state machine. We should confirm whether the state machine enjoys the guessed properties because such guessed properties may not be true properties of the state machine. Model checking is one possible technique to do so. If the state machine has a fixed small number of reachable states, model checking is enough. Otherwise, however, it is not. If that is the case, we should use some other techniques to make sure that the system enjoys the guessed properties. Interactive theorem proving is one such technique. The paper reports on a case study in which a mutual exclusion protocol called Qlock is used as an example to exemplify the abovementioned idea or methodology.

Keywords: graphical animations of state machines, model checking, theorem proving, invariant properties