Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Coverage directed algorithms for test suite construction from LR-automata
Thesis (MSc)--Stellenbosch University, 2022.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University
2022
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867614065792122880 |
|---|---|
| access_status_str | Open Access |
| author | Rossouw, Christoffel Jacobus |
| author2 | Fischer, Bernd |
| author_browse | Fischer, Bernd Rossouw, Christoffel Jacobus |
| author_facet | Fischer, Bernd Rossouw, Christoffel Jacobus |
| author_sort | Rossouw, Christoffel Jacobus |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University |
| description | Thesis (MSc)--Stellenbosch University, 2022. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/124734 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:46:07.073Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2022 |
| publishDateRange | 2022 |
| publishDateSort | 2022 |
| publisher | Stellenbosch : Stellenbosch University |
| publisherStr | Stellenbosch : Stellenbosch University |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/124734 Coverage directed algorithms for test suite construction from LR-automata Rossouw, Christoffel Jacobus Fischer, Bernd Stellenbosch University. Faculty of Science. Dept. of Computer Science. UCTD Probabilistic automata Parsers (Computer grammar) Algorithms Thesis (MSc)--Stellenbosch University, 2022. ENGLISH ABSTRACT: Bugs in software can have disastrous results in terms of both economic cost and human lives. Parsers can have bugs, like any other type of software, and must therefore be thoroughly tested in order to ensure that a parser recognizes its intended language accurately. However, parsers often need to recognize many different variations and combinations of grammar structures which can make it time consuming and difficult to construct test suites by hand. We therefore require automated methods of test suite construction for these systems. Currently, the majority of test suite construction algorithms focus on the grammar describing the language to be recognized by the parser. In this thesis we take a different approach. We consider the LR-automaton that recognizes the target language and use the context information encoded in the automaton. Specifically, we define a new class of algorithm and coverage criteria over a variant of the LR-automaton that we define, called an LR-graph. We define methods of constructing positive test suites, using paths over this LR-graph, as well as mutations on valid paths to construct negative test suites. We evaluate the performance of our new algorithms against other state-of-the-art algorithms. We do this by comparing coverage achieved over various systems, some smaller systems used in a university level compilers course and other larger, real-world systems. We find good performance of our algorithms over these systems, when compared to algorithms that produce test suites of equivalent size. Our evaluation has uncovered a problem in grammar-based testing algorithms that we call bias. Bias can lead to significant variation in coverage achieved over a system, which can in turn lead to a flawed comparison of two algorithms or unrealized performance when a test suite is used in practice. We therefore define bias and measure it for all grammar-based test suite construction algorithms we use in this thesis. AFRIKAANSE OPSOMMING: Foute in sagteware kan rampspoedige resultate hˆe in terme van beide eko nomiese koste en menselewens. Ontleders kan foute hˆe soos enige ander tipe sagteware en moet daarom deeglik getoets word om te verseker dat ’n ontleder sy beoogde taal akkuraat herken. Ontleders moet egter dikwels baie verskillende variasies en kombinasies van grammatikastrukture herken wat dit tydrowend en moeilik kan maak om toetsreekse met die hand te bou. Ons benodig dus outomatiese metodes van toetsreeks-konstruksie vir hierdie stelsels. Tans fokus die meeste toetsreeks-konstruksiealgoritmes op die grammatika wat die taal beskryf wat deur die ontleder herken moet word. In hierdie tesis volg ons ’n ander benadering. Ons beskou die LR-outomaat wat die teikentaal herken en gebruik die konteksinligting wat in die outomaat ge¨enkodeer is. Spesifiek, ons definieer ’n nuwe klas algoritme en dekkingskriteria oor ’n variant van die LR-outomaat wat ons definieer, wat ’n LR-grafiek genoem word. Ons definieer metodes om positiewe toetsreekse te konstrueer deur paaie oor hierdie LR-grafiek te gebruik, asook mutasies op geldige paaie om negatiewe toetsreekse te konstrueer. Ons evalueer die werkverrigting van ons nuwe algoritmes teenoor ander moderne algoritmes. Ons doen dit deur dekking wat oor verskeie stelsels behaal is, te vergelyk, sommige kleiner stelsels wat in ’n samestellerskursus op universiteitsvlak en ander groter werklike stelsels gebruik word. Ons vind goeie werkverrigting van ons algoritmes oor hierdie stelsels, in vergelyking met algoritmes wat toetsreekse van ekwivalente grootte produseer. Ons evaluering het ’n probleem in grammatika-gebaseerde toetsalgoritmes ontdek wat ons vooroordeel noem. Vooroordeel kan lei tot aansienlike variasie in dekking wat oor ’n stelsel behaal word, wat weer kan lei tot ’n gebrekkige vergelyking van twee algoritmes of ongerealiseerde prestasie wanneer ’n toets reeks in die praktyk gebruik word. Ons definieer dus vooroordeel en meet dit vir alle grammatika-gebaseerde toetsreeks-konstruksiealgoritmes wat ons in hierdie tesis gebruik. Masters 2022-03-01T10:33:19Z 2022-04-29T09:29:25Z 2022-03-01T10:33:19Z 2022-04-29T09:29:25Z 2022-04 Thesis http://hdl.handle.net/10019.1/124734 en_ZA Stellenbosch University 102 pages application/pdf Stellenbosch : Stellenbosch University |
| spellingShingle | UCTD Probabilistic automata Parsers (Computer grammar) Algorithms Rossouw, Christoffel Jacobus Coverage directed algorithms for test suite construction from LR-automata |
| title | Coverage directed algorithms for test suite construction from LR-automata |
| title_full | Coverage directed algorithms for test suite construction from LR-automata |
| title_fullStr | Coverage directed algorithms for test suite construction from LR-automata |
| title_full_unstemmed | Coverage directed algorithms for test suite construction from LR-automata |
| title_short | Coverage directed algorithms for test suite construction from LR-automata |
| title_sort | coverage directed algorithms for test suite construction from lr automata |
| topic | UCTD Probabilistic automata Parsers (Computer grammar) Algorithms |
| url | http://hdl.handle.net/10019.1/124734 |
| work_keys_str_mv | AT rossouwchristoffeljacobus coveragedirectedalgorithmsfortestsuiteconstructionfromlrautomata |