Practical programming, validation and verification with finite-state machines: a library and its industrial application

Finite-state machines (FSMs) are among the oldest models employed in the formalization and analysis of both software and hardware. Owing to their simplicity, there exist various implementations to support their practical application in mainstream programming languages. Through such software libraries, programmers can explicitly define states, events and transitions in order to delegate the machine’s execution to an underlying engine. However, as far as we know, no such library provides formal verification capabilities alongside its execution engine. That is to say, once an FSM is defined, the resulting program cannot be used as a formal specification to be subject to formal verification, thereby not making the analytical tractability of FSMs available. Formal verification, if any, is conducted in an independent model separate from the program, thus duplicating the information and creating the possibility of discrepancies between both. In this paper we show how to overcome this limitation. To this end, we present the V erum library, which allows the specification, execution and verification of FSMs in the Ruby language, largely bypassing the need to explicitly employ an additional modeling language. Formal verification is achieved by automatically translating the source program of the FSM into a Timed Automaton (TA) specification for the UPPAAL model checker. To illustrate the value of the approach, we present the industrial problem which inspired the creation of this tool and is currently using it, namely, a payment system. Besides the technical aspects of the tool, a number of practical lessons learned with this application are explored. Although we describe very concrete artifacts and applications, the overall approach is quite general.