On-the-fly verification of discrete event simulations by means of simulation purposes: Extended version. (August 2013)

• Record Type: Journal Article
• Authors: da Silva, Paulo Salem; de Melo, Ana C V
• Is Part Of: Simulation. Volume 89:Number 8(2013)
• Page Start: 977
• Page End: 1008
• Publication Date: 2013-08
• Subjects: Runtime verification -- systematic exploration -- formal method -- testing -- transition systems; Computer simulation -- Periodicals; 003.3
• DOI: 10.1177/0037549713490439
• Languages: English
• ISSNs: 0037-5497

Abstract

Discrete event simulations can be used to analyze natural and artificial phenomena. To this end, one provides models whose behaviors are characterized by discrete events in a discrete timeline. By running such a simulation, one can then observe its properties. This suggests the possibility of applying on-the-fly verification procedures during simulations. In this work we propose a method by which this can be accomplished. It consists of modeling the simulation as a transition system (implicitly), and the property to be verified as another transition system (explicitly). The latter we call a simulation purpose and it is used both to verify the success of the property and to guide the simulation. Algorithmically, this corresponds to building a synchronous product of these two transitions systems on-the-fly and using it to operate a simulator. By the end of such an algorithm, it may deliver either a conclusive or inconclusive verdict. If conclusive, it becomes known whether the simulation model satisfies the simulation purpose. If inconclusive, it is possible to adjust certain parameters and try again. The precise nature of simulation purposes, as well as the corresponding satisfiability relations and verification algorithms, are largely determined by methodological considerations important for the analysis of simulations, whose computational characteristics we compare with empirical scientific procedures. We provide a number of ways in which such a satisfiability relation can be defined formally, the related algorithms, and mathematical proofs of soundness, completeness and complexities. Two application examples are given to illustrate the approach.