Untitled
Date
2023-03
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Context-free grammars (CFGs) or simply grammars, are widely used to describe and encode the structure of complex objects. Systems that process such structured objects are known as grammarware. CFGs are also used for software engineering tasks such as testing grammarware, specifically in test suite generation and fuzzing. However, correct and complete CFGs are rarely available, which limits the benefits of these automated techniques. While current grammar engineering approaches can demonstrate the presence of faults in CFGs, none of them can be used to confirm the locations of these faults, much less repair them. In this thesis, we address this problem and develop, implement and evaluate novel automated methods that find locations of faults in CFGs and repair them against a test suite specification. We describe and evaluate the first spectrum-based method aimed at finding faults CFGs. In its basic form, it takes as input a test suite and a modified parser for the grammar that can collect grammar spectra, i.e., the sets of grammar elements used in attempts to parse the individual test cases, and returns as output a ranked list of suspicious elements. We define grammar spectra suitable for localizing faults on the level of the grammar rules and at the rules’ individual symbols, respectively. We show how these types of spectra can be collected in widely used parsing tools. We also show how the spectra can be constructed directly from test cases derived from a grammar, and how these synthetic spectra can be used for localization in cases where standalone parsers implementing the grammars are not available. We qualitatively and quantitatively demonstrate the effectiveness of our fault localization approach. We first evaluate our method over a large number of medium-sized single fault CFGs, which we constructed by fault seeding from a common origin grammar. At the rule level, it ranks the rules containing the seeded faults within the top five rules in about 40%–70% of the cases, and pinpoints them (i.e., correctly identifies them as unique most suspicious rule) in about 10%–30% of the cases, with significantly better results for the synthetic spectra. On average, it ranks the faulty rules within about 25% of all rules. At the item level, our method remains remarkably effective despite the larger number of possible locations: it typically ranks the seeded faults within the top five positions in about 30%–60% of the cases, and pinpoints them in about 15%–40% of the cases. On average, it ranks the seeded faults within about 10%–20% of all positions. We further evaluate our method over CFGs that contain real faults. We show that an iterative approach can be used to localize and manually remove one by one multiple faults in grammars submitted by students enrolled in various compiler engineering courses; in most iterations, the topranked rule already contains an error, and no error is ranked outside the top five ranked rules. We finally apply our method to a large open-source SQLite grammar and show where the original version deviates from the language accepted by the actual SQLite system. We then describe the first method to automatically repair faults in CFGs: given a grammar that fails some tests in a given test suite, we iteratively and gradually transform the grammar until it passes all tests. Our core idea is to build on spectrum-based fault localization to identify promising repair sites (i.e., specific positions in rules), and to apply grammar patches at these sites whenever they satisfy explicitly formulated pre-conditions necessary to potentially improve the grammar. We implement and evaluate passive and active repair variants of our approach. In passive repair, we repair against the fixed input test suite as specification. The active repair variant takes a black-box parser for the unknown target language or oracle that can answer membership queries. The key extension of active repair is to incorporate some test suite enrichment, by generating additional tests from each repair candidate and using the oracle to confirm the outcome of each of these tests. We demonstrate the effectiveness of both repair variants using thirtythree student grammars that contain multiple faults. We show that both variants are effective in fixing real faults in these grammars. A like-for-like comparison of both variants shows that active repair produces more high quality repairs than passive repair.
AFRIKAANS OPSOMMING: Konteksvrye grammatikas (CFG’s) of bloot grammatikas, is wyd gebruik om die struktuur van komplekse voorwerpe te beskryf en te kodeer. Stelsels dat sulke gestruktureerde voorwerpe verwerk word, staan bekend as grammatika. CFG’s word ook gebruik vir sagteware-ingenieurstake soos toetsing grammatika, spesifiek In sagteware-ingenieurswese word CFG’s spesifiek gebruik in die toets van grammatika in toetssuite generering en fuzzing. Korrekte en volledige CFG’s is egter selde beskikbaar, wat die voordele van hierdie outomatiese tegnieke beperk. Dit is grootliks omdat ingenieurspraktyke soos toetsing Terwyl huidige grammatika-ingenieursbenaderings die teenwoordigheid van kan demonstreer foute in CFG’s, óf deur statiese analise tegnieke óf dinamies nie een van hulle kan gebruik word om die liggings van te bevestig nie hierdie foute, nog minder herstel hulle. Die lokalisering en In hierdie tesis spreek ons hierdie probleem aan en ontwikkel, implementeer en evalueer nuwe geoutomatiseerde metodes wat vind liggings van foute in CFG’s en herstel dit teen ’n toetssuite-spesifikasie. Ons beskryf en evalueer die eerste spektrum-gebaseerde metode wat daarop gemik is om te vind foute CFG’s. In sy basiese vorm neem dit as inset ’n toetsreeks en ’n gewysigde ontleder vir die grammatika wat grammatikaspektra kan versamel, dit wil sê die stelle grammatika-elemente wat in poog om die individuele toetsgevalle te ontleed, en gee as uitvoer ’n gerangorde lys van verdagte elemente. Ons definieer grammatikaspektra wat geskik is vir die lokalisering van foute op die vlak van die grammatika reëls en by die reëls se individuele simbole, onderskeidelik. Ons wys hoe hierdie vii Stellenbosch University https://scholar.sun.ac.za viii UITTREKSEL tipe spektra kan versamel word in wyd gebruikte ontledingsinstrumente. Ons wys ook hoe die spektra gekonstrueer kan word direk van toetsgevalle afgelei van ’n grammatika, en hoe hierdie sintetiese spektra kan gebruik word vir lokalisering in gevalle waar selfstandige ontleders wat die grammatika is nie beskikbaar nie. Ons demonstreer kwalitatief en kwantitatief die effektiwiteit van ons foutlokaliseringsbenadering. Ons evalueer eers ons metode oor ’n groot aantal mediumgrootte enkelfout-CFG’s, wat ons gekonstrueer het deur foutsaaiing uit ’n algemene oorsprong-grammatika. Op reëlvlak rangskik dit die reëls wat die gesaaide foute bevat binne die top vyf reëls in ongeveer 40%–70% van die gevalle, en identifiseer hulle (d.w.s. identifiseer hulle korrek as die unieke mees verdagte reël) in ongeveer 10%–30% van die gevalle, met aansienlik beter resultate vir die sintetiese spektra. Gemiddeld rangskik dit die foutiewe reëls binne ongeveer 25% van alle reëls. Op itemvlak bly ons metode merkwaardig effektief ten spyte van die groter aantal moontlike liggings: dit rangskik tipies die gesaaide foute binne die top vyf posisies in ongeveer 30%–60% van die gevalle, en identifiseer hulle in ongeveer 15%–40% van die gevalle. Dit rangskik die gesaaide foute gemiddeld binne ongeveer 10%–20% van alle posisies. Ons evalueer verder ons metode oor CFG’s wat werklike foute bevat. Ons wys dat ’n iteratiewe benadering gebruik kan word om een vir een veelvuldige foute in grammatikas wat ingedien is deur studente wat in verskeie samestelleringenieurswese-kursusse ingeskryf is te lokaliseer en handmatig te verwyder; in die meeste iterasies bevat die reël wat die hoogste gerangskik reeds ’n fout, en geen fout word buite die top vyf reëls gerangskik nie. Ons pas uiteindelik ons metode toe op ’n groot oopbron SQLite-grammatika en wys waar die oorspronklike weergawe afwyk van die taal wat deur die werklike SQLite-stelsel aanvaar word. Ons beskryf dan die eerste benadering om outomaties te herstel foute in CFG’s: gegewe ’n grammatika wat sommige toetse in ’n gegewe toetsreeks druip, ons transformeer die grammatika iteratief en geleidelik totdat dit alle toetse slaag. Ons kern idee is om voort te bou op spektrum-gebaseerde fout lokalisering te identifiseer belowende herstelpersele (d.w.s. spesifieke posisies in reëls), en om aansoek te doen grammatika kolle op hierdie webwerwe wanneer hulle bevredig eksplisiet geformuleer voorwaardes wat nodig is om die grammatika moontlik te verbeter. Ons implementeer en evalueer passiewe en aktiewe herstel variante van ons benadering. In passiewe herstel herstel ons teen die vaste invoertoetssuite as spesifikasie. Die aktiewe herstelvariant neem ’n swartboks-ontleder vir die onbekende teiken taal of orakel wat lidmaatskapnavrae kan beantwoord. Die sleutel uitbreiding van aktiewe herstel is om te inkorporeer ’n mate van toetsreeksverryking, deur bykomende toetse uit elkeen te genereer herstelkandidaat en die gebruik van die orakel om die uitslag van elk van hierdie toetse te bevestig.
AFRIKAANS OPSOMMING: Konteksvrye grammatikas (CFG’s) of bloot grammatikas, is wyd gebruik om die struktuur van komplekse voorwerpe te beskryf en te kodeer. Stelsels dat sulke gestruktureerde voorwerpe verwerk word, staan bekend as grammatika. CFG’s word ook gebruik vir sagteware-ingenieurstake soos toetsing grammatika, spesifiek In sagteware-ingenieurswese word CFG’s spesifiek gebruik in die toets van grammatika in toetssuite generering en fuzzing. Korrekte en volledige CFG’s is egter selde beskikbaar, wat die voordele van hierdie outomatiese tegnieke beperk. Dit is grootliks omdat ingenieurspraktyke soos toetsing Terwyl huidige grammatika-ingenieursbenaderings die teenwoordigheid van kan demonstreer foute in CFG’s, óf deur statiese analise tegnieke óf dinamies nie een van hulle kan gebruik word om die liggings van te bevestig nie hierdie foute, nog minder herstel hulle. Die lokalisering en In hierdie tesis spreek ons hierdie probleem aan en ontwikkel, implementeer en evalueer nuwe geoutomatiseerde metodes wat vind liggings van foute in CFG’s en herstel dit teen ’n toetssuite-spesifikasie. Ons beskryf en evalueer die eerste spektrum-gebaseerde metode wat daarop gemik is om te vind foute CFG’s. In sy basiese vorm neem dit as inset ’n toetsreeks en ’n gewysigde ontleder vir die grammatika wat grammatikaspektra kan versamel, dit wil sê die stelle grammatika-elemente wat in poog om die individuele toetsgevalle te ontleed, en gee as uitvoer ’n gerangorde lys van verdagte elemente. Ons definieer grammatikaspektra wat geskik is vir die lokalisering van foute op die vlak van die grammatika reëls en by die reëls se individuele simbole, onderskeidelik. Ons wys hoe hierdie vii Stellenbosch University https://scholar.sun.ac.za viii UITTREKSEL tipe spektra kan versamel word in wyd gebruikte ontledingsinstrumente. Ons wys ook hoe die spektra gekonstrueer kan word direk van toetsgevalle afgelei van ’n grammatika, en hoe hierdie sintetiese spektra kan gebruik word vir lokalisering in gevalle waar selfstandige ontleders wat die grammatika is nie beskikbaar nie. Ons demonstreer kwalitatief en kwantitatief die effektiwiteit van ons foutlokaliseringsbenadering. Ons evalueer eers ons metode oor ’n groot aantal mediumgrootte enkelfout-CFG’s, wat ons gekonstrueer het deur foutsaaiing uit ’n algemene oorsprong-grammatika. Op reëlvlak rangskik dit die reëls wat die gesaaide foute bevat binne die top vyf reëls in ongeveer 40%–70% van die gevalle, en identifiseer hulle (d.w.s. identifiseer hulle korrek as die unieke mees verdagte reël) in ongeveer 10%–30% van die gevalle, met aansienlik beter resultate vir die sintetiese spektra. Gemiddeld rangskik dit die foutiewe reëls binne ongeveer 25% van alle reëls. Op itemvlak bly ons metode merkwaardig effektief ten spyte van die groter aantal moontlike liggings: dit rangskik tipies die gesaaide foute binne die top vyf posisies in ongeveer 30%–60% van die gevalle, en identifiseer hulle in ongeveer 15%–40% van die gevalle. Dit rangskik die gesaaide foute gemiddeld binne ongeveer 10%–20% van alle posisies. Ons evalueer verder ons metode oor CFG’s wat werklike foute bevat. Ons wys dat ’n iteratiewe benadering gebruik kan word om een vir een veelvuldige foute in grammatikas wat ingedien is deur studente wat in verskeie samestelleringenieurswese-kursusse ingeskryf is te lokaliseer en handmatig te verwyder; in die meeste iterasies bevat die reël wat die hoogste gerangskik reeds ’n fout, en geen fout word buite die top vyf reëls gerangskik nie. Ons pas uiteindelik ons metode toe op ’n groot oopbron SQLite-grammatika en wys waar die oorspronklike weergawe afwyk van die taal wat deur die werklike SQLite-stelsel aanvaar word. Ons beskryf dan die eerste benadering om outomaties te herstel foute in CFG’s: gegewe ’n grammatika wat sommige toetse in ’n gegewe toetsreeks druip, ons transformeer die grammatika iteratief en geleidelik totdat dit alle toetse slaag. Ons kern idee is om voort te bou op spektrum-gebaseerde fout lokalisering te identifiseer belowende herstelpersele (d.w.s. spesifieke posisies in reëls), en om aansoek te doen grammatika kolle op hierdie webwerwe wanneer hulle bevredig eksplisiet geformuleer voorwaardes wat nodig is om die grammatika moontlik te verbeter. Ons implementeer en evalueer passiewe en aktiewe herstel variante van ons benadering. In passiewe herstel herstel ons teen die vaste invoertoetssuite as spesifikasie. Die aktiewe herstelvariant neem ’n swartboks-ontleder vir die onbekende teiken taal of orakel wat lidmaatskapnavrae kan beantwoord. Die sleutel uitbreiding van aktiewe herstel is om te inkorporeer ’n mate van toetsreeksverryking, deur bykomende toetse uit elkeen te genereer herstelkandidaat en die gebruik van die orakel om die uitslag van elk van hierdie toetse te bevestig.
Description
Thesis (PhD)--Stellenbosch University, 2023.