Reduce impact of parsing crafted templates with repeat tags

[Jake Howard]

The template system uses a regex to extract template tags from text. Given certain inputs, this can take an excessive amount of time:

In [2]: %timeit Template("{%" * 2000)
34.7 ms ± 153 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [3]: %timeit Template("{%" * 10000)
877 ms ± 1.49 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [4]: %timeit Template("{%" * 20000)
3.49 s ± 47 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [5]: %timeit Template("{%")
11.5 µs ± 55.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

The cause is excessive backtracking in the ​pattern used. Since the template system is so versatile and performance-critical, fixing the issue appears non-trivial.

Note: This bug was raised with the Security Team prior to opening, however was not deemed a security vulnerability since parsing untrusted (or semi-trusted) templates is ​explicitly warned against.

[Natalia Bidart]

Thank you Jake for taking the time to create this report. Accepting following the conversation within the Security Team.

[Aditya Chaudhary]

Can't we use precompiling a regex pattern to enhance performance by avoiding repeated compilation overhead for frequent matches?

[Jake Howard]

Can't we use precompiling a regex pattern

No, this regex is already compiled before execution (see the linked code above). Repeat compiling isn't the performance hit here, it's the backtracking in the pattern itself.

[Hailey Johnson]

See PR #19360​https://github.com/django/django/pull/19360

[Jacob Walls]

It may not be an "acceptance requirement" to fix the following, given its limited application, but I did want to mention the following finding after 1a9fba7a6c2a0acead19bbb45c25ceb0fdcca7c8, in case someone wants to look into it as well:

Matching can become quadratic when a long verbatim name contains repeated {% endverbatim sequences and the block body repeats those sequences without completing the expected closing tag:

{% verbatim {% endverbatim {% endverbatim finish %}
{% endverbatim {% endverbatim {% endverbatim {% endverbatim %}

The block’s name is {% endverbatim {% endverbatim finish. Each {% endverbatim in the body starts a potential match that eventually fails because finish is missing.