💻 computer science

Towards the Systematic Testing of Regular Expression Engines

Dit paper introduceert ReTest, een framework dat grammatica-bewuste fuzzing combineert met metamorfe testen om regular expression-engines systematisch te testen en bugs te detecteren zonder afhankelijk te zijn van een consistent cross-implementation standaard.

Oorspronkelijke auteurs: Berk Çakar, Dongyoon Lee, James C. Davis

Gepubliceerd 2026-03-03

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Berk Çakar, Dongyoon Lee, James C. Davis

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat regular expressions (of "regex") de superkrachtige zoekmachines zijn van de programmeerwereld. Ze worden gebruikt om tekst te filteren, wachtwoorden te controleren en e-mails te sorteren. Maar deze zoekmachines worden aangedreven door regex-engines (software die de zoekopdrachten uitvoert).

Het probleem is: deze engines zitten vol met foutjes. Soms vinden ze iets wat ze niet moeten vinden, en soms crasht de hele computer.

De auteurs van dit paper, Berk Çakar, Dongyoon Lee en James C. Davis, hebben een nieuw systeem bedacht genaamd ReTest om deze engines beter te testen. Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Probleem: De "Taalbarrière" en de "Willekeurige Hap"

Hoe testen mensen nu of een regex-engine goed werkt? Ze proberen twee dingen, maar beide hebben grote haken en ogen:

De "Vergelijkingsmethode" (Differential Testing):
- Hoe het werkt: Je laat twee verschillende engines (bijvoorbeeld die van Python en die van Java) dezelfde zoekopdracht doen. Als ze een ander antwoord geven, denk je: "Aha, er is een fout!"
- Het probleem: Het is alsof je een Fransman en een Nederlander vraagt om een recept te vertalen. Als de Fransman "boter" zegt en de Nederlander "margarine", is dat niet per se een fout in het recept; het is gewoon een verschil in dialect. Regex-engines hebben allemaal hun eigen "dialect". Ze verschillen in details. De vergelijkingsmethode schreeuwt dus vaak om hulp bij dingen die helemaal geen fouten zijn.
De "Willekeurige Hap" (Naive Fuzzing):
- Hoe het werkt: Je gooit willekeurige karakters tegen de engine aan (bijv. a#%$z!) om te zien of hij crasht.
- Het probleem: Regex is een taal met strenge regels. Als je willekeurige karakters gooit, is het alsof je een auto probeert te starten door er een baksteen in te gooien. De engine ziet de "zin" niet en stopt direct met lezen. Je test dan alleen of de engine goed kan lezen, maar niet of hij goed kan rijden (de daadwerkelijke zoeklogica).

2. De Oplossing: ReTest (De Slimme Zoektocht)

De auteurs hebben ReTest gebouwd. Dit is een slimme robot die twee superkrachten combineert:

Kracht 1: De "Grammatica-Bewuste Fuzzing" (De Slimme Bakker)

In plaats van willekeurige karakters te gooien, leert ReTest eerst de grammatica van de taal.

De Analogie: Stel je voor dat je een bakker bent die brood test. Een domme bakker gooit zand in het deeg. Een slimme bakker (ReTest) weet dat brood uit bloem, water en gist moet bestaan. Hij maakt dus alleen maar geldig deeg, maar hij varieert de ingrediënten op slimme manieren.
Hoe het werkt: ReTest kijkt naar de structuur van de zoekopdracht (zoals een boomdiagram) en vervangt onderdelen op een manier die grammaticaal correct blijft. Hierdoor komt hij veel dieper in de software en test hij de echte zoeklogica, niet alleen de leesfunctie.

Kracht 2: Metamorfische Testen (De Spiegelmethode)

Hoe weet je of het antwoord van de engine correct is als er geen "juiste antwoord" bestaat om mee te vergelijken?

De Analogie: Stel je voor dat je een spiegel hebt. Als je een object voor de spiegel houdt, moet de afbeelding er precies hetzelfde uitzien, ook als je de spiegel een beetje draait.
Hoe het werkt: ReTest gebruikt wiskundige regels (uit de "Kleene-algebra"). Hij neemt een zoekopdracht, verandert hem op een slimme manier (bijvoorbeeld: "als ik dit zoek, moet het hetzelfde resultaat geven als als ik dat zoek"), en laat de engine beide uitvoeren.
- Als de engine zegt: "Zoekopdracht A geeft 'ja', maar de veranderde Zoekopdracht B geeft 'nee'", dan is er een fout.
- Dit werkt zonder een andere engine te nodig te hebben. De engine test zichzelf op consistentie.

3. De Resultaten: De "Drie Nieuwe Gaten"

Toen ze ReTest testten op een populaire engine genaamd PCRE:

Meer dekking: ReTest testte 3 keer zoveel onderdelen van de code als de oude methoden.
Nieuwe fouten gevonden: Ze vonden drie nieuwe, gevaarlijke fouten (waarbij geheugen werd beschadigd) die eerder waren gemist.
Geen vals alarm: Omdat ze de "spiegelmethode" gebruikten, hoefden ze zich geen zorgen te maken over dialectverschillen. Als het niet klopt, is het echt een fout.

Samenvatting in één zin

ReTest is een slimme testrobot die regex-engines niet test door ze willekeurige onzin te geven of ze met elkaar te vergelijken, maar door ze grammaticaal correcte puzzels te laten oplossen en te controleren of ze zelfconsistent blijven, waardoor ze veel dieper en nauwkeuriger fouten vinden.

De boodschap is duidelijk: we moeten stoppen met het gissen en beginnen met het systematisch testen van deze cruciale software, zodat onze digitale wereld veiliger blijft.

Probleemstelling

Regular expression (regex) engines zijn fundamentele softwarecomponenten die worden gebruikt voor patroonmatching, validatie en tekstverwerking in bijna elk softwareproject. Ondanks hun belang zijn deze engines vatbaar voor bugs en kwetsbaarheden (zoals geheugenveiligheidsproblemen en semantische fouten).

De huidige testpraktijken voor regex-engines hebben echter twee grote tekortkomingen:

Gebrek aan gestructureerde inputgeneratie: Bestaande fuzzing-methoden gebruiken vaak naïeve mutaties op byte-niveau. Dit genereert vaak syntactisch ongeldige regex-patronen die door de parser worden afgewezen, waardoor de complexe matching-logica van de engine nooit wordt getest.
Het "Oracle-probleem": Het bepalen of de output van een engine correct is, is moeilijk.
- Differential testing (vergelijken met andere engines) faalt omdat er geen universele standaard is; verschillende engines (dialecten) hebben subtiele semantische verschillen (bijv. POSIX vs. PCRE), wat leidt tot veel vals-positieven.
- Unit tests vereisen handmatig opgestelde verwachte resultaten, wat niet schaalbaar is voor de enorme ruimte van mogelijke patronen.

Methodologie: Het ReTest Framework

De auteurs stellen ReTest voor, een systematisch testframework dat twee complementaire technieken combineert om de bovengenoemde problemen op te lossen:

Grammabewuste Fuzzing (Grammar-Aware Fuzzing):
- In plaats van willekeurige byte-mutaties, parseert ReTest regex-patronen naar Abstract Syntax Trees (AST).
- Het gebruikt een corpus van meer dan 500.000 reële regex-patronen als zaad (seeding).
- Mutaties worden uitgevoerd door subbomen in de AST te vervangen door semantisch compatibele alternatieven uit een dynamisch bijgehouden pool. Dit zorgt ervoor dat gegenereerde patronen altijd syntactisch geldig blijven, waardoor de matching-logica effectief wordt getest.
- Coverage-gestuurde feedback (edge coverage) leidt de mutatieprocessen om diepere codepaden te bereiken.
Metamorfe Testing (Metamorphic Testing):
- Om het oracle-probleem op te lossen zonder afhankelijk te zijn van een andere engine, gebruikt ReTest algebraïsche eigenschappen afgeleid uit de Kleene-algebra.
- Het framework past transformaties toe op een regex-patroon (bijv. $r^* \equiv (r^*)^*$ of associativiteit van alternatieven) die de semantiek niet mogen veranderen.
- Als de engine verschillende resultaten geeft voor het originele patroon en het getransformeerde patroon, is dit een bewijs van een semantische bug. Dit werkt dialect-onafhankelijk.
Veiligheidscorrectie:
- Voor het detecteren van crashes en geheugenveiligheidsfouten (zoals buffer overflows) integreert ReTest runtime-sanitizers (AddressSanitizer, MemorySanitizer, UBSan).

Belangrijkste Bijdragen

Empirische Studie: Een analyse van 22 regex-engines (eerste partij en third-party) die aantoont dat 82% van de bugs door gebruikers wordt gemeld en dat slechts 2 van de 22 engines grammabewuste fuzzing gebruiken.
Bug- en CVE-analyse: Onderzoek naar 1.007 bugs en 156 CVE's. De studie toont aan dat semantische bugs (35%) en geheugenveiligheidskwetsbaarheden (52% van de CVE's) de dominante problemen zijn.
Catalogus van Metamorfe Relaties: Het samenstellen van een catalogus van 16 metamorfe relaties voor K-regex (Kleene-fragmenten) die dienen als dialect-onafhankelijke orakels.
Het ReTest Framework: Een werkend prototype dat grammabewuste fuzzing combineert met metamorfe testing.

Resultaten (Voorlopige Evaluatie)

De auteurs hebben ReTest geëvalueerd op PCRE v8.45 en vergeleken met twee baselines:

Naïeve Fuzzing (zoals gebruikt in OSS-Fuzz).
Grammabewuste Fuzzing (gebaseerd op de V8/Irregexp aanpak).

Kernresultaten:

Code Coverage: ReTest bereikte 40,12% edge coverage, wat een 3x verbetering is ten opzichte van de baselines (respectievelijk ~11,8% en ~12,7%). De initiële seeding met een corpus gaf direct een voordeel, maar de context-bewuste mutaties leverden een extra stijging op.
Bug Ontdekking: ReTest ontdekte drie nieuwe geheugenveiligheidsbugs in PCRE v8.45 (waaronder heap-corruptie en buffer overflows) die door de baselines niet werden gevonden.
Efficiëntie: Hoewel ReTest minder iteraties uitvoerde (~~40k) dan naïeve fuzzing (~~156 miljoen), was de kwaliteit van de gegenereerde inputs veel hoger, wat leidde tot diepere code-exploratie.

Betekenis en Conclusie

Dit paper biedt een nieuwe richting voor het testen van kritieke software-infrastructuur. De belangrijkste implicaties zijn:

Overbrugging van het Oracle-probleem: Door metamorfe testing te gebruiken, kunnen bugs worden gevonden zonder een "waarheid" van een andere engine nodig te hebben, wat essentieel is in een wereld met veel verschillende regex-dialecten.
Verbeterde Veiligheid: De focus op grammabewuste inputgeneratie zorgt ervoor dat de complexe matching-logica (waar de meeste bugs zitten) daadwerkelijk wordt getest, in plaats van alleen de parser.
Toekomstperspectief: De auteurs plannen om de metamorfe relaties uit te breiden naar uitgebreide regex (E-regex) en de framework te evalueren op alle 22 onderzochte engines.

Samenvattend stelt ReTest een systematische, schaalbare en dialect-onafhankelijke aanpak voor om bugs en kwetsbaarheden in regex-engines proactief te detecteren, wat essentieel is voor de betrouwbaarheid en veiligheid van moderne softwaresystemen.