Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Greedy combinatorial test case generation using unsatisfiable cores
National Institute of Advanced Industrial Science and Technology (AIST), Japan.ORCID iD: 0000-0002-3656-1614
Show others and affiliations
2016 (English)In: ASE 2016 - Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, Association for Computing Machinery (ACM), 2016, 614-624 p.Conference paper, Published paper (Refereed)
Abstract [en]

Combinatorial testing aims at covering the interactions of parameters in a system under test, while some combinations may be forbidden by given constraints (forbidden tuples). In this paper, we illustrate that such forbidden tuples correspond to unsatisfiable cores, a widely understood notion in the SAT solving community. Based on this observation, we propose a technique to detect forbidden tuples lazily during a greedy test case generation, which significantly reduces the number of required SAT solving calls. We further reduce the amount of time spent in SAT solving by essentially ignoring constraints while constructing each test case, but then "amending" it to obtain a test case that satisfies the constraints, again using unsatisfiable cores. Finally, to complement a disturbance due to ignoring constraints, we implement an efficient approximative SAT checking function in the SAT solver Lingeling. Through experiments we verify that our approach significantly improves the efficiency of constraint handling in our greedy combinatorial testing algorithm.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2016. 614-624 p.
Series
IEEE ACM International Conference on Automated Software Engineering, ISSN 1527-1366
Keyword [en]
Combinatorial testing, SAT solving, Test case generation
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-199093DOI: 10.1145/2970276.2970335ISI: 000390237000060Scopus ID: 2-s2.0-84989163860ISBN: 978-145033845-5 (print)OAI: oai:DiVA.org:kth-199093DiVA: diva2:1062025
Conference
31st IEEE/ACM International Conference on Automated Software Engineering, ASE 2016, Singapore Management UniversitySingapore, Singapore, 3 September 2016 through 7 September 2016
Note

QC 20170117

Available from: 2017-01-04 Created: 2016-12-28 Last updated: 2017-01-17Bibliographically approved

Open Access in DiVA

fulltext(1056 kB)25 downloads
File information
File name FULLTEXT01.pdfFile size 1056 kBChecksum SHA-512
dc10c32a41bfe19a8d54a9580e03b53747b3a11a5d904160de7b10475058ec282a74804dd708a5806dd9c16a89ad6d354ca1ad13de0a4b0c7dae13d0b378f6a5
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Artho, Cyrille
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 25 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

Altmetric score

Total: 32 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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