Logo des Repositoriums
Zur Startseite
  • English
  • Deutsch
Anmelden
  1. Startseite
  2. SuUB
  3. Dissertationen
  4. An approach for the verification and synthesis of complete test generation algorithms for finite state machines
 
Zitierlink DOI
10.26092/elib/1665

An approach for the verification and synthesis of complete test generation algorithms for finite state machines

Veröffentlichungsdatum
2022-07-20
Autoren
Sachtleben, Robert  
Betreuer
Peleska, Jan  
Gutachter
Wolff, Burkhart  
Zusammenfassung
Complete test suites are of special interest in the field of model-based testing, as they guarantee high fault detection capabilities under well-specified assumptions. The variety and complexity of strategies generating complete test suites, their implementations, and their completeness proofs impose difficulties upon manual verification. Furthermore, ambiguities or only implicitly specified assumptions in natural language descriptions and proofs easily lead to implementations that do not generate complete test suites.

The present dissertation proposes an alternative approach to the verification and implementation of test strategies that generate complete test suites for testing for language-equivalence on finite state machines, that employs the interactive theorem prover Isabelle.

In the first part of this work, similarities and differences between steps performed by the considered test strategies are identified. From these, a framework is derived as a higher order function capable of representing all considered strategies as concrete applications of it. Several implementations of parameters of this framework are shared between multiple strategies. Additional frameworks are developed to support alternative completeness proofs.

The second part of this work defines finite state machines, their properties and operations, as well as the frameworks in Isabelle/HOL and respectively proves them correct and complete. Completeness proofs over frameworks are decoupled from concrete implementations of their parameters by suitable interfaces. This approach enables the reuse of proofs between similar strategies and thus simplifies completeness proofs for new variations on already handled strategies.

Finally, the definitions in Isabelle are employed to automatically generate provably correct implementations of the considered test strategies. It is shown that these exhibit comparable performance to a manually developed C++ library for certain inputs.
Schlagwörter
Isabelle

; 

theorem proving

; 

finite state machine

; 

complete test strategy

; 

Model-based Testing
Institution
Universität Bremen  
Fachbereich
Fachbereich 03: Mathematik/Informatik (FB 03)  
Dokumenttyp
Dissertation
Zweitveröffentlichung
Nein
Lizenz
https://creativecommons.org/licenses/by/4.0/
Sprache
Englisch
Dateien
Lade...
Vorschaubild
Name

Dissertation_Robert_Sachtleben.pdf

Size

2.29 MB

Format

Adobe PDF

Checksum

(MD5):de96ab67960252dd9ba09d46de88f5cf

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science

  • Datenschutzbestimmungen
  • Endnutzervereinbarung
  • Feedback schicken