RFC 9485

I-Regexp: An Interoperable Regular Expression Format

📅 published October 2023, from ietf

Internet Engineering Task Force (IETF) 🎀 Standards Track RFC 9485 ✨

Okay bestie, let's get into it. This is RFC 9485, titled I-Regexp: An Interoperable Regular Expression Format 💖. It's a Standards Track document from October 2023 (ISSN 2070-1721), written by C. Bormann of Universität Bremen TZI and T. Bray of Textuality. It doesn't obsolete or update any other RFCs, so it's a fresh start 🌸.

Part 1 covers the title block, the status stuff, the intro, the syntax, the checking stuff, the semantics, and the mapping section. Part 2 is coming, so stay tuned 🧚.

Abstract ✨

Okay so the whole point of this doc is to define I-Regexp, a flavor of regular expression that's intentionally limited in scope so it can work across tons of different regexp libraries 🦋. Lowkey iconic, no cap.

Status of This Memo 📜

This is an Internet Standards Track document, so it's official-official 👑.

It's a product of the Internet Engineering Task Force (IETF), which means it represents the consensus of the IETF community. It got public review and was approved for publication by the Internet Engineering Steering Group (IESG). If you want more on Internet Standards, check out Section 2 of RFC 7841 💅.

For the current status, any errata, and how to give feedback, head to https://www.rfc-editor.org/info/rfc9485 🔥.

Copyright (c) 2023 IETF Trust and the persons identified as the document authors. All rights reserved 💜.

This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (https://trustee.ietf.org/license-info) in effect on the date of publication. Please review these carefully, because they spell out your rights and restrictions. Code Components extracted from this document must include Revised BSD License text as described in Section 4.e of the Trust Legal Provisions, and they're provided without warranty as described in the Revised BSD License 🫶.

Table of Contents 🍓

  • 1. Introduction
    • 1.1. Terminology
  • 2. Objectives
  • 3. I-Regexp Syntax
    • 3.1. Checking Implementations
  • 4. I-Regexp Semantics
  • 5. Mapping I-Regexp to Regexp Dialects
    • 5.1. Multi-Character Escapes
    • 5.2. XSD Regexps
    • 5.3. ECMAScript Regexps
    • 5.4. PCRE, RE2, and Ruby Regexps
  • 6. Motivation and Background
    • 6.1. Implementing I-Regexp
  • 7. IANA Considerations
  • 8. Security Considerations
  • 9. References
    • 9.1. Normative References
    • 9.2. Informative References
  • Acknowledgements
  • Authors' Addresses

1. Introduction 🧚

Okay so this spec describes an interoperable regular expression (we'll call it "regexp" for short) flavor called I-Regexp 💖.

I-Regexp doesn't do the advanced stuff like capture groups, lookahead, or backreferences. It only does Boolean matching, which means it just tells you whether a regexp matches a piece of text. Simple and iconic 💅.

I-Regexp supports the entire repertoire of Unicode characters (Unicode scalar values). Both the I-Regexp strings and the strings they're matched against are sequences of Unicode scalar values, often shown in UTF-8 encoding form [STD63] for interchange 🌸.

I-Regexp is a subset of XML Schema Definition (XSD) regular expressions [XSD-2] ✨.

This document also includes guidance for converting I-Regexps to work with several well-known regexp idioms 🦋.

The development of I-Regexp was motivated by the work of the JSONPath Working Group (WG). The WG wanted regular expressions in JSONPath filters in its specification [JSONPATH-BASE], but couldn't find a useful spec for regexps that would be interoperable across the popular libraries 😭.

1.1. Terminology 🎀

This document uses the abbreviation "regexp" for what's usually called a "regular expression" in programming. The term "I-Regexp" is a noun meaning a character string (a sequence of Unicode scalar values) that conforms to the requirements in this spec. The plural is "I-Regexps" 💜.

This spec uses Unicode terminology, and a good starting point is [UNICODE-GLOSSARY] 🌈.

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here 🫶.

The grammatical rules in this document are to be read as ABNF, as described in [RFC5234] and [RFC7405], where the "characters" of Section 2.3 of [RFC5234] are Unicode scalar values 🧚.

2. Objectives 🌸

I-Regexps should handle the vast majority of practical cases where a matching regexp is needed in a data-model specification or a query-language expression ✨.

At the time of writing, an editor of this document surveyed the regexp syntax used in recently published RFCs. All examples found there should be covered by I-Regexps, both syntactically and with their intended semantics. The exception is multi-character escapes, and workaround guidance for those is in Section 5 💅.

3. I-Regexp Syntax 💖

An I-Regexp MUST conform to the ABNF specification in Figure 1 👑.

i-regexp = branch *( "|" branch )
branch = *piece
piece = atom [ quantifier ]
quantifier = ( "*" / "+" / "?" ) / range-quantifier
range-quantifier = "{" QuantExact [ "," [ QuantExact ] ] "}"
QuantExact = 1*%x30-39 ; '0'-'9'

atom = NormalChar / charClass / ( "(" i-regexp ")" )
NormalChar = ( %x00-27 / "," / "-" / %x2F-3E ; '/'-'>'
 / %x40-5A ; '@'-'Z'
 / %x5E-7A ; '^'-'z'
 / %x7E-D7FF ; skip surrogate code points
 / %xE000-10FFFF )
charClass = "." / SingleCharEsc / charClassEsc / charClassExpr
SingleCharEsc = "\" ( %x28-2B ; '('-'+'
 / "-" / "." / "?" / %x5B-5E ; '['-'^'
 / %s"n" / %s"r" / %s"t" / %x7B-7D ; '{'-'}'
 )
charClassEsc = catEsc / complEsc
charClassExpr = "[" [ "^" ] ( "-" / CCE1 ) *CCE1 [ "-" ] "]"
CCE1 = ( CCchar [ "-" CCchar ] ) / charClassEsc
CCchar = ( %x00-2C / %x2E-5A ; '.'-'Z'
 / %x5E-D7FF ; skip surrogate code points
 / %xE000-10FFFF ) / SingleCharEsc
catEsc = %s"\p{" charProp "}"
complEsc = %s"\P{" charProp "}"
charProp = IsCategory
IsCategory = Letters / Marks / Numbers / Punctuation / Separators /
    Symbols / Others
Letters = %s"L" [ ( %s"l" / %s"m" / %s"o" / %s"t" / %s"u" ) ]
Marks = %s"M" [ ( %s"c" / %s"e" / %s"n" ) ]
Numbers = %s"N" [ ( %s"d" / %s"l" / %s"o" ) ]
Punctuation = %s"P" [ ( %x63-66 ; 'c'-'f'
 / %s"i" / %s"o" / %s"s" ) ]
Separators = %s"Z" [ ( %s"l" / %s"p" / %s"s" ) ]
Symbols = %s"S" [ ( %s"c" / %s"k" / %s"m" / %s"o" ) ]
Others = %s"C" [ ( %s"c" / %s"f" / %s"n" / %s"o" ) ]

Figure 1: I-Regexp Syntax in ABNF 🧁

Okay, one extra restriction: charClassExpr is NOT allowed to match [^]. By this grammar, it would parse as a positive character class containing just the character ^, so watch out for that one 🙈.

Basically this is an XSD regexp without:

  • character class subtraction,
  • multi-character escapes like \s, \S, and \w, and
  • Unicode blocks.

An I-Regexp implementation MUST be a complete implementation of this limited subset. Full support for the Unicode functionality defined in this spec is REQUIRED. The implementation:

  • MUST NOT limit itself to 7- or 8-bit character sets such as ASCII, and
  • MUST support the Unicode character property set in character classes.

3.1. Checking Implementations 🔍

A _checking_ I-Regexp implementation is one that checks a supplied regexp for compliance with this spec and reports any problems. Checking implementations give users confidence that they didn't accidentally insert syntax that isn't interoperable, so checking is RECOMMENDED. Exceptions can be made for low-effort implementations that map I-Regexp to another regexp library by simple steps, like the mapping operations in Section 5. There, the effort for full checking might dwarf the rest of the implementation work. Implementations SHOULD document whether or not they're checking 💅.

Specs that use I-Regexp might want to define when their implementations can work with a non-checking I-Regexp implementation, and when full checking is needed, possibly while defining their own implementation classes 🌈.

4. I-Regexp Semantics 🦋

This syntax is a subset of the one in [XSD-2]. Implementations that interpret I-Regexps MUST yield Boolean results as specified in [XSD-2]. (See also Section 5.2.) 💖

5. Mapping I-Regexp to Regexp Dialects 🗺️

The material in this section is NOT normative. It's guidance for developers who want to use I-Regexps in other regexp dialects 🌸.

5.1. Multi-Character Escapes ✨

I-Regexp doesn't support common multi-character escapes (MCEs) or the character classes built around them. You can usually replace them with the examples in Table 1 🫶.

+============+===============+
| MCE/class: | Replace with: |
+============+===============+
| \S         | [^ \t\n\r]    |
+------------+---------------+
| [\S ]      | [^\t\n\r]     |
+------------+---------------+
| \d         | [0-9]         |
+------------+---------------+

             Table 1: Example
          Substitutes for Multi-
            Character Escapes

Note that the semantics of \d in XSD regexps is that of \p{Nd}. But that would include every Unicode character that's a digit in various writing systems, which is almost certainly not what's needed in IETF publications 🙈.

The construct \p{IsBasicLatin} is basically a reference to legacy ASCII. You can replace it with the character class [\u0000-\u007f] 🍓.

5.2. XSD Regexps 👑

Any I-Regexp is also an XSD regexp [XSD-2], so the mapping is an identity function 💅.

A few errata for [XSD-2] have been fixed in [XSD-1.1-2], so it's also included in the Normative References (Section 9.1). XSD 1.1 is less widely implemented than XSD 1.0, and XSD 1.0 implementations are likely to include these bugfixes. For the intents and purposes of this spec, an implementation of XSD 1.0 regexps is equivalent to an implementation of XSD 1.1 regexps 🌈.

5.3. ECMAScript Regexps 🧚

To get an ECMAScript regexp [ECMA-262] from an I-Regexp, perform these steps:

  • For any unescaped dots (.) outside character classes (first alternative of the charClass production), replace the dot with [^\n\r].
  • Envelope the result in ^(?: and )$.

The ECMAScript regexp is to be interpreted as a Unicode pattern ("u" flag; see Section 21.2.2 "Pattern Semantics" of [ECMA-262]) 💜.

Note that where a regexp literal is required, the actual regexp needs to be enclosed in / 🎀.

5.4. PCRE, RE2, and Ruby Regexps 💎

To get a valid regexp in Perl Compatible Regular Expressions (PCRE) [PCRE2], the Go programming language's RE2 regexp library [RE2], or the Ruby programming language, do the same steps as in Section 5.3, except the last step is different:

  • Enclose the regexp in \A(?: and )\z.

That's the end of part 1 bestie 🥹. Part 2 covers the rest of the RFC, including Motivation and Background, IANA Considerations, Security Considerations, References, and Acknowledgements, so we'll pick up right there 💖✨.

6. Motivation and Background ✨

okay so regexes started out as a way to ask a yes or no question: does this text match the pattern? 🦋 Over time people kept piling on parsing features, so now they can also pull out arbitrary bits of matched text and swap them for other stuff. 🧩 All those extra features made parsing-regexp libraries buggy and kinda unpredictable on performance, and an attacker who controls the regexp you're processing can totally exploit that for denial-of-service attacks 😭💀. I-Regexp is built for interoperability and to be way less vulnerable to that mess 💅. The trade-off is that its ONLY job is giving a Boolean answer about whether a character sequence matches a regexp. No extraction, no replacing, just yes or no 🫶

6.1. Implementing I-Regexp

XSD regexps are relatively easy to implement or map onto widely implemented parsing-regexp dialects 🌸. There are a few notable exceptions though:

  • Character class subtraction. This is a super useful feature in lots of specifications, but it's sadly mostly missing from parsing-regexp dialects 😩. So it's left out of I-Regexp.
  • Multi-character escapes. \d, \w, \s and their uppercase complement classes vary a LOT between regexp flavors 🙈. So they're omitted from I-Regexp too.
  • Unicode tables. Not every regexp implementation can access the Unicode tables needed to run things like \p{Nd}, even though the \p/\P feature is pretty widely available now ✨. You could in principle translate these into character-class matches, but that also needs access to those tables 🧚. So regexp libraries in severely constrained environments may not be able to support I-Regexp conformance. 🥺

7. IANA Considerations 🍓

This document has no IANA actions.

8. Security Considerations 🔥

Okay, this part is serious bestie, so pay attention 🚨 While it's technically out of scope for this spec, Section 10 ("Security Considerations") of RFC 3629 [STD63] still applies to implementations. You need to take special note of the last paragraph of Section 3 ("UTF-8 definition") of RFC 3629 [STD63], because an I-Regexp implementation may need to mitigate limitations of the platform implementation in this regard 💀.

As we talked about in Section 6, the more complex regexp libraries may contain exploitable bugs, and those can lead to crashes and remote code execution 😱. There's also the problem that these libraries often have performance characteristics that are really hard to predict, which opens the door to attacks that overload an implementation by matching against an expensive attacker-controlled regexp 🫠.

I-Regexps were designed so they can be implemented in a way that holds up against BOTH of these threats 💖. This objective has to be addressed all the way through the implementation effort, not just at one step. Non-checking implementations (see Section 3.1) are likely to expose security limitations of whatever regexp engine they use. That may be less of a problem if the engine was built with security in mind, like [RE2] 🛡️. Either way, a checking implementation is still RECOMMENDED 👑.

Implementations that specifically implement the I-Regexp subset can, with care, generally be designed to run in linear time and space in the input, and to detect when that wouldn't be the case (see below) ✨.

Existing regexp engines should be able to handle most I-Regexps pretty easily (after the adjustments discussed in Section 5) 💅. But they might eat up excessive resources for some types of I-Regexps, or outright reject them because they can't guarantee efficient execution 😬. (Heads up: different versions of the same regexp library may be more or less vulnerable to excessive resource consumption in these cases 🌈.)

Range quantifiers (like a{2,4}) are the big troublemakers here, for both existing and I-Regexp focused implementations 🌪️. So implementations may limit range quantifiers in composability, disallowing nested range quantifiers such as (a{2,4}){2,4}. They may also limit range, disallowing very large ranges such as a{20,200000}. Or they can detect and reject any excessive resource consumption caused by range quantifiers 🧯.

I-Regexp implementations that are used to evaluate regexps from untrusted sources need to be robust in these cases. Implementers using existing regexp libraries are encouraged: - to check their documentation to see if mitigations are configurable, such as limits in resource consumption, and - to document their own degree of robustness resulting from employing such mitigations.

9. References 📚

9.1. Normative References

[RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
           Requirement Levels", BCP 14, RFC 2119,
           DOI 10.17487/RFC2119, March 1997,
           <https://www.rfc-editor.org/info/rfc2119>.

[RFC5234]  Crocker, D., Ed. and P. Overell, "Augmented BNF for Syntax
           Specifications: ABNF", STD 68, RFC 5234,
           DOI 10.17487/RFC5234, January 2008,
           <https://www.rfc-editor.org/info/rfc5234>.

[RFC7405]  Kyzivat, P., "Case-Sensitive String Support in ABNF",
           RFC 7405, DOI 10.17487/RFC7405, December 2014,
           <https://www.rfc-editor.org/info/rfc7405>.

[RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC
           2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174,
           May 2017, <https://www.rfc-editor.org/info/rfc8174>.

[XSD-1.1-2]
           Peterson, D., Ed., Gao, S., Ed., Malhotra, A., Ed.,
           Sperberg-McQueen, C. M., Ed., Thompson, H., Ed., and P.
           Biron, Ed., "W3C XML Schema Definition Language (XSD) 1.1
           Part 2: Datatypes", W3C REC REC-xmlschema11-2-20120405,
           W3C REC-xmlschema11-2-20120405, 5 April 2012,
           <https://www.w3.org/TR/2012/REC-xmlschema11-2-20120405/>.

[XSD-2]    Biron, P., Ed. and A. Malhotra, Ed., "XML Schema Part 2:
           Datatypes Second Edition", W3C REC REC-xmlschema-
           2-20041028, W3C REC-xmlschema-2-20041028, 28 October 2004,
           <https://www.w3.org/TR/2004/REC-xmlschema-2-20041028/>.

9.2. Informative References

[ECMA-262] Ecma International, "ECMAScript 2020 Language
           Specification", Standard ECMA-262, 11th Edition, June
           2020, <https://www.ecma-international.org/wp-
           content/uploads/ECMA-262.pdf>.

[JSONPATH-BASE]
           Gössner, S., Ed., Normington, G., Ed., and C. Bormann,
           Ed., "JSONPath: Query expressions for JSON", Work in
           Progress, Internet-Draft, draft-ietf-jsonpath-base-20, 25
           August 2023, <https://datatracker.ietf.org/doc/html/draft-
           ietf-jsonpath-base-20>.

[PCRE2]    "Perl-compatible Regular Expressions (revised API:
           PCRE2)", <http://pcre.org/current/doc/html/>.

[RE2]      "RE2 is a fast, safe, thread-friendly alternative to
           backtracking regular expression engines like those used in
           PCRE, Perl, and Python. It is a C++ library.", commit
           73031bb, <https://github.com/google/re2>.

[RFC7493]  Bray, T., Ed., "The I-JSON Message Format", RFC 7493,
           DOI 10.17487/RFC7493, March 2015,
           <https://www.rfc-editor.org/info/rfc7493>.

[STD63]    Yergeau, F., "UTF-8, a transformation format of ISO
           10646", STD 63, RFC 3629, November 2003.

           <https://www.rfc-editor.org/info/std63>

[UNICODE-GLOSSARY]
           Unicode, Inc., "Glossary of Unicode Terms",
           <https://unicode.org/glossary/>.

Acknowledgements 💜

Discussion in the IETF JSONPATH WG about whether to include a regexp mechanism into the JSONPath query expression specification 🧠, plus earlier chats about the YANG pattern and Concise Data Definition Language (CDDL) .regexp features, is what motivated this specification 🌟.

The basic approach for this specification was inspired by "The I-JSON Message Format" [RFC7493] 🎀.

Authors' Addresses 🦋

Carsten Bormann
Universität Bremen TZI
Postfach 330440
D-28359 Bremen
Germany
Phone: +49-421-218-63921
Email: cabo@tzi.org

Tim Bray
Textuality
Canada
Email: tbray@textuality.com
📦 where this page comes from