If you restrict it to “formal” regular expressions you’ll stay out of “arbitrary code executing on a Turing machine”.

Regular expression engines are notoriously buggy. You definitely wouldn't want to pass random expressions to libpcre.

Web browsers are already running random expressions from the internet, but their regex implementations have proven the rule by being fodder from exploit writers. In any event, requiring a password manager to pull the engine from Firefox or Chrome wouldn't be cool. They're more likely to use libpcre or re2, but see above.

The NAPTR DNS record type uses regular expressions for domain rewriting: https://en.wikipedia.org/wiki/NAPTR_record Not many DNS libraries support that record type as it adds alot of problematic bloat.

libpcre is exactly the implementation I’m not talking about, because it supports too much. I think re2 doesn’t do backtracking, so it’s probably a better choice.

You can still easily blow up memory with unions, which makes it easy to lock up Linux, which notoriously performs poorly under memory pressure.

A non-backtracking regex engine like re2 should be linear with respect to the regex size and can be configured with a memory budget.

The number of DFA states can explode exponentially. It's a real problem, especially if you're compiling untrusted expressions off the internet.

Evaluation is linear, but you're just evaluating your own password. In this scenario, it may make sense to just use a simple backtracking implementation, though as you alluded to early there aren't many simple ones around.

RE2, at least, will fall back to an NFA-based matcher if things get too pathological.

Just set a memory limit on the process.

Counterpoint: if you allow your browser to run JavaScript, it’s already executing arbitrary regexes it finds on the Internet.

The browser is, the passwords manager is on the other end of an IPC mechanism with a hopefully small and well-defined interface.

My point is that it is possible for your password manager to sandbox regex execution at least as well as your browser does.

I totally agree with your concerns about scope creep increasing the attack surface.

But it's not executing a match, it's creating a random password picker. That's exactly equivalent to parsing the pattern where the actions on terminals are to generate random characters.