An investigation into performance-related issues of regular expression matching
Date
2022-11
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT: Regular expressions (regexes) constitute a concise, powerful, and useful pattern
matching language for strings. They are widely supported in programming
languages, text processing programs, and (advanced) text editors. In general,
regex matching is performed efficiently, but in some cases, a vulnerable regex
(and an exploit string) can cause the matching procedure to take exponential
time in the length of the input string. As regexes are frequently used in userfacing
circumstances, vulnerable regexes open up the underlying application to
a potential denial of service vector. Several regex engines choose to implement
an algorithm that will always match an input string in linear time, but can
only support a subset of modern regex constructs.
We show how to implement a construct known as Regular Expressions
with Lookahead (REwLA), and investigate various state complexity results
when converting REwLA to equivalent deterministic finite automata (DFA).
The relationship between REwLA with atomic operations and REwLA without
is investigated, and an algorithm for translating a REwLA with atomic
operations to a REwLA without is provided.
Vulnerable regexes only exist when the regex engine implements a backtracking
algorithm. We extend non-deterministic finite a utomata (NFA) and
regexes by adding memoization to these formalisms. Furthermore, we generalise
the concept of ambiguity in order to be applicable to memoized extensions.
These extensions are aimed at improving the matching time of backtracking
regex engines.
AFRIKAANS OPSOMMING: Regulêre uitdrukkings (regekse) vorm ’n bondige, kragtige en bruikbare taal vir die patroon-ooreenstemming van stringe. Hulle word ondersteun in ’n groot hoeveelheid van programmeertale, teksverwerkingsprogramme en (gevorderde) teksredigeerders. Oor die algemeen word regeks-passing doeltreffend uitgevoer, maar in sommige gevalle kan ’n kwesbare regeks (en ’n uitbuit-string) veroorsaak dat die ooreenstemming prosedure eksponensiële tyd in die lengte van die invoerstring neem. Aangesien regekse gereeld gebruik word in omstandighede waar die gebruiker die hoof akteur is, maak dit kwesbare regekse oop tot ’n moontlike ontkenning van diens aanval. Verskeie regeks-enjins kies om ’n algoritme te implementeer wat altyd ’n invoerstring in lineêre tyd sal pas, maar kan slegs ’n deelversameling van moderne regeks-konstruksies ondersteun. Ons wys hoe om ’n konstruksie, bekend as “Regular Expressions with Lookahead” (REwLA) te implementeer en ondersoek verskeie toestandskompleksiteitsresultate wanneer REwLA na ekwivalente deterministiese eindige outomatiese (DFA) omgeskakel word. Die verband tussen REwLA met atomiese operatore en REwLA daarsonder word ondersoek en ’n algoritme vir die vertaling van REwLA met atomiese operatore na REwLA daarsonder word verskaf. Kwesbare regekse bestaan slegs wanneer die regex-enjin ’n terugspooralgoritme implementeer. Ons brei nie-deterministiese eindige outomatiese (NFA) en regekse uit deur memoisering by hierdie formalisme te voeg. Verder veralgemeen ons die konsep van dubbelsinnigheid om van toepassing te wees op gememoriseerde uitbreidings. Hierdie uitbreidings is daarop gemik om die passingstyd van terugsporing van regeks-enjins te verbeter.
AFRIKAANS OPSOMMING: Regulêre uitdrukkings (regekse) vorm ’n bondige, kragtige en bruikbare taal vir die patroon-ooreenstemming van stringe. Hulle word ondersteun in ’n groot hoeveelheid van programmeertale, teksverwerkingsprogramme en (gevorderde) teksredigeerders. Oor die algemeen word regeks-passing doeltreffend uitgevoer, maar in sommige gevalle kan ’n kwesbare regeks (en ’n uitbuit-string) veroorsaak dat die ooreenstemming prosedure eksponensiële tyd in die lengte van die invoerstring neem. Aangesien regekse gereeld gebruik word in omstandighede waar die gebruiker die hoof akteur is, maak dit kwesbare regekse oop tot ’n moontlike ontkenning van diens aanval. Verskeie regeks-enjins kies om ’n algoritme te implementeer wat altyd ’n invoerstring in lineêre tyd sal pas, maar kan slegs ’n deelversameling van moderne regeks-konstruksies ondersteun. Ons wys hoe om ’n konstruksie, bekend as “Regular Expressions with Lookahead” (REwLA) te implementeer en ondersoek verskeie toestandskompleksiteitsresultate wanneer REwLA na ekwivalente deterministiese eindige outomatiese (DFA) omgeskakel word. Die verband tussen REwLA met atomiese operatore en REwLA daarsonder word ondersoek en ’n algoritme vir die vertaling van REwLA met atomiese operatore na REwLA daarsonder word verskaf. Kwesbare regekse bestaan slegs wanneer die regex-enjin ’n terugspooralgoritme implementeer. Ons brei nie-deterministiese eindige outomatiese (NFA) en regekse uit deur memoisering by hierdie formalisme te voeg. Verder veralgemeen ons die konsep van dubbelsinnigheid om van toepassing te wees op gememoriseerde uitbreidings. Hierdie uitbreidings is daarop gemik om die passingstyd van terugsporing van regeks-enjins te verbeter.
Description
Thesis (MSc) -- Stellenbosch University, 2022.
Keywords
Regular expressions (Computer science), Pattern recognition systems, Programming languages (Electronic computers), UCTD