mdh.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
Type-directed Generation and Shrinking for Imperative Programming Languages
Mälardalen University, School of Innovation, Design and Engineering.
Mälardalen University, School of Innovation, Design and Engineering.
2018 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

Optimizing compilers are large and complex systems, potentially consisting of millions of lines of code. As a result, the implementation of an industry standard compiler can contain several serious bugs. This is alarming given the critical part that software plays in modern society. Therefore, we investigate type-directed program generation and shrinking for the testing of compilers for imperative programming languages. We implement a type-directed generator and shrinker for a subset of C in Haskell. The generator is capable of generating type-correct programs that contain variable mutations and challenging program constructs, such as while-statements and if statements. We evaluate the quality of the generated programs by measuring statement coverage of a reference interpreter and by comparing the results to reference test suite. The results show that the generated programs can surpass the test suite in terms of quality by one percentage point of coverage. To test the bug finding capabilities of the generator and the shrinker, we use them to test seven interpreters and manage to identify a total of seven bugs. Furthermore, we test the same interpreters with the reference test suite and find only three bugs. The implications of the results lead us to question the reliability of code coverage as a measure of quality for compiler test suites. Finally, we conclude that type-directed generation and shrinking is a powerful method that can be used for the testing of compilers for imperative programming languages.

Place, publisher, year, edition, pages
2018. , p. 39
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mdh:diva-39673OAI: oai:DiVA.org:mdh-39673DiVA, id: diva2:1215491
Subject / course
Computer Science
Presentation
2018-06-04, Gamma, Högskoleplan 1, Västerås, 10:55 (English)
Supervisors
Examiners
Available from: 2018-06-11 Created: 2018-06-08 Last updated: 2018-06-11Bibliographically approved

Open Access in DiVA

Type-directed Generation and Shrinking for Imperative Programming Languages(531 kB)94 downloads
File information
File name FULLTEXT01.pdfFile size 531 kBChecksum SHA-512
27061855ee9afa5d0af60ddd9893379466f7767fb24766930562d9a72727e54d412655c01c11ff37f01d456cafd868a4a10a0ef744a9269a246dd77e814de08c
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Samuel, BodinJoel, Söderman
By organisation
School of Innovation, Design and Engineering
Computer Sciences

Search outside of DiVA

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

urn-nbn

Altmetric score

urn-nbn
Total: 224 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