kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Algorithms and Tools for Learning-based Testing of Reactive Systems
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

In this thesis we investigate the feasibility of learning-based testing (LBT) as a viable testing methodology for reactive systems. In LBT, a large number of test cases are automatically generated from black-box requirements for the system under test (SUT) by combining an incremental learning algorithm with a model checking algorithm. The integration of the SUT with these algorithms in a feedback loop optimizes test generation using the results from previous outcomes. The verdict for each test case is also created automatically in LBT.

To realize LBT practically, existing algorithms in the literature both for complete and incremental learning of finite automata were studied. However, limitations in these algorithms led us to design, verify and implement new incremental learning algorithms for DFA and Kripke structures. On the basis of these algorithms we implemented an LBT architecture in a practical tool called LBTest which was evaluated on pedagogical and industrial case studies.

The results obtained from both types of case studies show that LBT is an effective methodology which discovers errors in reactive SUTs quickly and can be scaled to test industrial applications. We believe that this technology is easily transferrable to industrial users because of its high degree of automation.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2013. , p. xii, 79
Series
Trita-CSC-A, ISSN 1653-5723 ; 2013:03
Keywords [en]
specification-based testing, learning-based testing, reactive systems, LBTest, case studies
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-119267ISBN: 978-91-7501-674-0 (print)OAI: oai:DiVA.org:kth-119267DiVA, id: diva2:610371
Public defence
2013-04-16, F3, Lindstedtsvägen 26, Kungliga Tekniska Högskolan, Stockholm, 10:00 (English)
Opponent
Supervisors
Note

QC 20130312

Available from: 2013-03-12 Created: 2013-03-11 Last updated: 2022-06-24Bibliographically approved
List of papers
1. Incremental Learning based Testing for Reactive Systems
Open this publication in new window or tab >>Incremental Learning based Testing for Reactive Systems
2011 (English)In: / [ed] Martin Gogolla and Burkhart Wolff, 2011, p. 134-151Conference paper, Published paper (Refereed)
Abstract [en]

We show how the paradigm of learning-based testing (LBT)can be applied to automate specification-based black-box testing of reactivesystems. Since reactive systems can be modeled as Kripke structures,we introduce an efficient incremental learning algorithm IKL forsuch structures. We show how an implementation of this algorithm combinedwith an efficient model checker such as NuSMV yields an effectivelearning-based testing architecture for automated test case generation(ATCG), execution and evaluation, starting from temporal logic requirements.

Series
Lecture Notes In Computer Science ; 6706
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-37339 (URN)10.1007/978-3-642-21768-5_11 (DOI)000392155000011 ()2-s2.0-79960247126 (Scopus ID)978-3-642-21767-8 (ISBN)
Conference
5th International Conference on Tests and Proofs (TAP)
Note

QC 20110822

Available from: 2011-08-09 Created: 2011-08-09 Last updated: 2022-06-24Bibliographically approved
2. An Efficient Model Inference Algorithm for Learning-based Testing of Reactive Systems
Open this publication in new window or tab >>An Efficient Model Inference Algorithm for Learning-based Testing of Reactive Systems
2012 (English)Report (Other academic)
Abstract [en]

Learning-based testing (LBT) is an emerging methodology to automate iterative black-box requirements testing of software systems. The methodology involves combining model inference with model checking techniques. However, a variety of optimisations on model inference are necessary in order to achieve scalable testing for large systems.

In this paper we describe the IKL learning algorithm which is an active incremental learning algorithm for deterministic Kripke structures. We formally prove the correctness of IKL. We discuss the optimisations it incorporates to achieve scalability of testing. We also evaluate a black box heuristic for test termination based on convergence of IKL learning.

Publisher
p. 29
Keywords
automata learning, black-box testing, learning-based testing, reactive systems
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-119266 (URN)
Note

QC 20130312

Available from: 2013-03-11 Created: 2013-03-11 Last updated: 2022-06-24Bibliographically approved
3. LBTest: A Learning-based Testing Tool for Reactive Systems
Open this publication in new window or tab >>LBTest: A Learning-based Testing Tool for Reactive Systems
2013 (English)In: Proceedings - IEEE 6th International Conference on Software Testing, Verification and Validation, ICST 2013, IEEE Computer Society, 2013, p. 447-454Conference paper, Published paper (Refereed)
Abstract [en]

We give an introduction to the LBTest tool which implements learning-based testing for reactive systems. It makes use of incremental learning and model checking algorithms to automate: i) test case generation, ii) test execution and iii) test verdict construction. The paper illustrates the tool by means of a pedagogical case study, to enable the user to setup and learn the tool quickly. We provide a usability exercise to support tool evaluation.

Place, publisher, year, edition, pages
IEEE Computer Society, 2013
Keywords
requirements testing, learning-based testing, black-box testing, LBTest
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-119088 (URN)10.1109/ICST.2013.62 (DOI)000332473300050 ()2-s2.0-84883443673 (Scopus ID)978-0-7695-4968-2 (ISBN)
Conference
IEEE 6th International Conference on Software Testing, Verification and Validation, ICST 2013; Luxembourg; Luxembourg; 18 May 2013 through 20 May 2013
Note

QC 20130312

Available from: 2013-03-06 Created: 2013-03-06 Last updated: 2022-06-24Bibliographically approved
4. Case Studies in Learning-based Testing
Open this publication in new window or tab >>Case Studies in Learning-based Testing
Show others...
2013 (English)Report (Other academic)
Abstract [en]

We present case studies which show how the paradigm of learning-based testing (LBT) can be successfully applied to black-box requirements testing of reactive systems. For this we apply a new testing tool LBTest, which combines algorithms for incremental black-box learning of Kripke structures with model checking technology. We show how test requirements can be modeled in propositional linear temporal logic extended by finite abstract data types. We provide benchmark performance results for LBTest applied to two industrial case studies. Finally we present a first coverage study for the tool.

Publisher
p. 22
Keywords
Learning-based Testing, Specification-based Testing, case studies
National Category
Computer Sciences
Identifiers
urn:nbn:se:kth:diva-119265 (URN)
Note

QC 20130312

Available from: 2013-03-11 Created: 2013-03-11 Last updated: 2022-06-24Bibliographically approved

Open Access in DiVA

fulltext(15120 kB)5001 downloads
File information
File name FULLTEXT02.pdfFile size 15120 kBChecksum SHA-512
1159241bbe6dda225448f0cb78f9bc0fd168e7bd628a2eb450184620415f436f8fb2734ad9734da3d553b855d875b5955d0d9741b5ff4c612c0f85906231fe6b
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Sindhu, Muddassar
By organisation
Theoretical Computer Science, TCS
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 5001 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 2892 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf