regex · text processing · security
What is regex, exactly?
A regular expression, or regex, is a small language for describing the shape of text rather than its exact content. Instead of asking "is this string equal to abc", you ask "does this string look like three letters, a dash, and four digits".
That is the whole idea. Everything else is notation.
The notation, in one pass
Most of what you will read is built from a handful of pieces:
.any single character,\da digit,\wa word character,\swhitespace*zero or more,+one or more,?zero or one,5between two and five[abc]any one of these,[^abc]anything but these,[a-z]a range^start of the string,$end of it(...)a group you can repeat or capture,|either side
So ^\d3-\d4$ reads: from the start, three digits, a dash, four digits, then the end. Nothing more.
Why the same pattern behaves differently in two languages
There is no single regex. There is a family of dialects that agree on the basics and diverge past them: POSIX, PCRE, the flavour built into JavaScript, the one in Python, the one in Go. Lookbehind, named groups, Unicode property escapes and even what \d considers a digit are places where they part company.
The practical consequence is that a pattern copied from a Stack Overflow answer written for one language can silently do something else in yours. Test it where it will run, not where you found it. That is what the regex tester on this site is for.
The failure mode worth knowing: catastrophic backtracking
Here is the part that turns a text-matching utility into an operational problem.
Most regex engines in mainstream languages work by backtracking. When a pattern can match in more than one way, the engine tries one split, and if the rest fails, it comes back and tries another. For ordinary patterns that is cheap. For some patterns it is not.
The dangerous shape is a repetition inside a repetition, where the two can divide the same text between them in many ways. The textbook example is (a+)+$. Fed a long run of a characters followed by one character that cannot match, the engine has to try every possible way of splitting those as between the inner and outer repetition before it can conclude failure. The number of combinations grows exponentially with the length of the input.
Twenty characters may be instant. Thirty may take a second. Forty may not finish while you are still employed. And because this only happens on input that nearly matches, it never shows up in the tests you wrote with input that matches.
When that regex runs on user-supplied input on a server, the exponential case is reachable by anyone who can send a request. That is the denial-of-service class known as ReDoS, catalogued by the OWASP as a regular-expression denial of service.
How to stay out of it
Be suspicious of nested quantifiers. A + or * applied to a group that already contains one is the shape to look for. Often it can be flattened to something with a single, unambiguous way to match.
Anchor and be specific. ^, $ and precise character classes cut the number of splits the engine has to consider. [^"]* is usually better than .*.
Do not run user input through a hand-written regex casually. For emails, URLs and dates, a parser or a well-tested library beats a clever pattern, and it fails in ways you can read.
Know your engine. Some, such as Go's RE2, are built on a different algorithm and do not backtrack at all. They give up features like backreferences in exchange for a guaranteed linear-time match. If a regex must run on hostile input, that trade is often the right one.
The short version
A regex describes the shape of text, in a notation that is smaller than it looks and less portable than it seems. Learn the dozen symbols, verify the dialect where the code will run, and treat a quantifier inside a quantifier as a defect until proven otherwise. The pattern that matches everything you tested is not the one that will take the site down.
