Find capturing groups in user submitted regex

Question

I have a python application which needs to process user submitted regular expressions. Because of performance considerations i want to forbid capturing groups and back references.

My idea is to use another regular expression to verify that the user submitted regex does not contain any named or unnamed group captures like this:

def validate_user_regex(pattern):
    if re.match('[^\\\]\((?:\?P).*?[^\\\]\)', pattern) is not None:
        return False
    return True

While i think my idea may work for capturing groups, i am not sure if this would prevent all kinds of back references. So are there any smarter ways to prevent capturing groups and back references in regular expressions?

If you're worried about slow user regexes, you should be more concerned about [catastrophic backtracking](http://www.regular-expressions.info/catastrophic.html) which can be used maliciously as a form of DoS attack. — Kendall Frey, Jan 16 '15 at 12:44
If it's performance you're worried about rather than groups and back references per se, would it be acceptable to just compile and test the input regex on a small controlled data set, and time its performance empirically? — jez, Jan 16 '15 at 12:53

score 2 · Accepted Answer · edited May 23 '17 at 12:27

Regular expression language is not a regular language so it cannot be reliably split into meaningful parts by a regex (see RegEx match open tags except XHTML self-contained tags for the same case for HTML).

Why not use Python's own parser instead to do this?

>>> r="whate(ever)(?:\\1)"
>>> import sre_parse        #the module used by `re' internally for regex parsing
>>> sre_parse.parse(r)
[('literal', 119), ('literal', 104), ('literal', 97), ('literal', 116),
 ('literal', 101), ('subpattern', (1, [('literal', 101), ('literal', 118), ('lit
eral', 101), ('literal', 114)])), ('subpattern', (None, [('groupref', 1)]))]

As you can see, this is a parse tree, and you're interested in subpattern nodes with non-None in the first element and groupref's.

score 0 · Answer 2 · answered Jan 16 '15 at 12:59

Your regex is very naive. (In fact, I had a hard time finding a group construct that is matched by your regex.)

To avoid false positives, like for example [(bar)], it's necessary to parse/match the entire pattern from left to right. I've come up with this regex:

^(?:\[(?:\\.|[^\]])*\]|\(\?:|[^(\\]|\\\D|\(\?[gmixsu])*$

regex101 demo.

Explanation:

^   # start of string anchor
(?:  # this group matches a single valid expression:
# character classes:
    \[  # the opening [
    (?: 
        \\.  # any escaped character
    | # or 
        [^\]] # anything that's not a closing ]
    )* # any number of times
    \]  # the closing ]
|
# non-capturing groups:
    \(\?:  # (?: literally
|
# normal characters (anything that's not a backslash or (
    [^(\\]
|
# meta sequences like \s
    \\\D
|
# inline modifiers like (?i)
    \(\?[gmixsu]
)* # any number of valid expressions.
$  # end of string anchor

P.S.: This regex does not guarantee that the pattern is valid. (Compiling the pattern can still fail.)

Find capturing groups in user submitted regex

2 Answers2

Linked