Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • 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
Turning evil regexes harmless
Department of Computer Science, Stellenbosch University, Stellenbosch, South Africa.
Department of Computer Science, Center for AI Research, CSIR, Stellenbosch University, Stellenbosch, South Africa.
Department of Information Science, Center for AI Research, CSIR, Stellenbosch University, Stellenbosch, South Africa.
2017 (English)In: SAICSIT '17: Proceedings of the South African Institute of Computer Scientists and Information Technologists, ACM Digital Library, 2017, article id 38Conference paper, Published paper (Refereed)
Abstract [en]

We explore the relationship between ambiguity in automata and regular expressions on the one hand, and the matching time of backtracking regular expression matchers on the other. We focus in particular on the extreme cases where we have either an exponential amount of ambiguity or no ambiguity at all. We also investigate techniques to reduce or remove ambiguity from regular expressions, which can then be used to transform regular expressions which might be exploited by using algorithmic complexity, into harmless equivalent expressions.

Place, publisher, year, edition, pages
ACM Digital Library, 2017. article id 38
Keywords [en]
algorithmic complexity attack, ReDoS, regular expression, backtracking matcher, ambiguity
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-192862DOI: 10.1145/3129416.3129440ISI: 000426499000060Scopus ID: 2-s2.0-85032647990ISBN: 978-1-4503-5250-5 (print)OAI: oai:DiVA.org:umu-192862DiVA, id: diva2:1641654
Conference
SAICSIT '17: South African Institute of Computer Scientists and Information Technologists, Thaba 'Nchu, South Africa, September 26-28, 2017
Available from: 2022-03-02 Created: 2022-03-02 Last updated: 2022-03-03Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Berglund, Martin

Search in DiVA

By author/editor
Berglund, Martin
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 411 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • 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