Skip to Main content Skip to Navigation
Conference papers

Effective Infinite-State Model Checking by Input Equivalence Class Partitioning

Abstract : In this paper, it is shown how a complete input equivalence class testing strategy developed by the second author can be effectively used for infinite-state model checking of system models with infinite input domains but finitely many internal state values and finite output domains. This class of systems occurs frequently in the safety-critical domain, where controllers may input conceptually infinite analogue data, but make a finite number of control decisions based on inputs and current internal state. A variant of Kripke Structures is well-suited to provide a behavioural model for this system class. It is shown how the known construction of specific input equivalence classes can be used to abstract the infinite input domain of the reference model into finitely many classes. Then quick checks can be made on the implementation model showing that the implementation is not I/O-equivalent to the reference model if its abstraction to observable minimal finite state machines has a different number of states or a different input partitioning as the reference model. Only if these properties are consistent with the reference model, a detailed equivalence check between the abstracted models needs to be performed. The complete test suites obtained as a by-product of the checking procedure can be used to establish counter examples showing the non-conformity between implementation model and reference model. Using various sample models, it is shown that this approach outperforms model checkers that do not possess this equivalence class generation capability.
Complete list of metadata

https://hal.inria.fr/hal-01678956
Contributor : Hal Ifip <>
Submitted on : Tuesday, January 9, 2018 - 3:38:43 PM
Last modification on : Tuesday, February 13, 2018 - 4:24:03 PM
Long-term archiving on: : Friday, May 4, 2018 - 8:43:21 AM

File

449632_1_En_3_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Niklas Krafczyk, Jan Peleska. Effective Infinite-State Model Checking by Input Equivalence Class Partitioning. 29th IFIP International Conference on Testing Software and Systems (ICTSS), Oct 2017, St. Petersburg, Russia. pp.38-53, ⟨10.1007/978-3-319-67549-7_3⟩. ⟨hal-01678956⟩

Share

Metrics

Record views

258

Files downloads

123