Repository navigation
templates: the filter walk is exponential in a cycle of includes, and cuts a cycle Django renders through #284
Description
Summary
To collect the filters a render reaches, project_templates walks each {% include %} and {% extends %} (_reaching in taint/templates.py). Since #279, each template is walked once for each set of blocks the templates extending it override. A cycle is cut at a template already on the way, identified by its name alone, and a walk the cycle cut is not kept.
This has two consequences:
- False negative. A child can extend a parent that includes it back, inside the block the child overrides. Django renders that parent again with the block overridden, so the recursion stops by itself. The walk cuts it at the parent's name and misses the parent's filters applied to what the include binds.
- Cost. In a cycle through templates that include the level below twice, every walk is cut, so none is kept, and each is walked again on every path. The time quadruples every two levels.
Affected: 0.24.0 (926df83) and earlier. The walk path by path of 0.23.0 cuts at the same places and is exponential on the same shape.
1. False negative: a cycle Django renders through
Templates under app/templates:
a.html:{% extends 'b.html' %} {% block body %}{{ v|upper }}{% endblock %}b.html:{{ v|striptags }} {% block body %}{% include 'a.html' with v=other %}{% endblock %}
Django 5.1.15 renders b.html with {'v': 'fixed', 'other': '<b>bio</b>'} as 'fixed\nbio\n<B>BIO</B>\n\n':
b.htmlincludesa.htmlwithv=other;a.htmlrendersb.htmlwithbodyoverridden;- that render applies
striptagstoother(the second line,bio), and the overridden block appliesupper.
The walk of b.html follows the include to a.html, then its extends back to b.html. There it cuts, since b.html is on the way. It finds striptags reached by v and upper reached by other, but not striptags reached by other.
End to end. Take an advisory whose entry point is django.template.defaultfilters.striptags, Django 4.2.16 in uv.lock, and a view rendering b.html. cycle_fn.py, below, builds the project and runs analyze_project with the bundled plugins. Its view passes the request as other; the control swaps the two values.
The view passes request.POST['bio'] as |
Findings on 0.24.0 |
|---|---|
v (control) |
exploitable-vulnerability at app/views.py:5, through b.html:1 |
other |
none |
cycle_fn.py
"""exploitable-vulnerability findings for striptags, in a child extending a parent that
includes it back inside the block the child overrides. Usage: python -I cycle_fn.py <dir>"""
import sys
from pathlib import Path
from coretrace_python import engine
from coretrace_python.dependency import Advisory, AdvisoryEntryPoint, dump_advisories
from coretrace_python.findings import Severity
from coretrace_python.semantic.symbols import SymbolId
STRIPTAGS = "python.django.template.defaultfilters.striptags"
ADVISORY = Advisory("CVE-2099-0001", "django", "<4.2.17", "striptags is quadratic in its input", Severity.MEDIUM,
entry_points=(AdvisoryEntryPoint(SymbolId(STRIPTAGS), "a template filter"),))
LOCK = """version = 1
[[package]]
name = "app"
version = "0.1.0"
source = { virtual = "." }
dependencies = [{ name = "django" }]
[[package]]
name = "django"
version = "4.2.16"
source = { registry = "https://pypi.org/simple" }
"""
VIEW = (
"from django.http import HttpRequest\n"
"from django.shortcuts import render\n\n"
"def page(request: HttpRequest):\n"
" return render(request, 'b.html', {'v': 'fixed', 'other': request.POST['bio']})\n"
)
FILES = {
"uv.lock": LOCK,
"app/__init__.py": "",
"app/views.py": VIEW,
"app/templates/a.html": "{% extends 'b.html' %}\n{% block body %}{{ v|upper }}{% endblock %}\n",
"app/templates/b.html": "{{ v|striptags }}\n{% block body %}{% include 'a.html' with v=other %}{% endblock %}\n",
}
root = Path(sys.argv[1])
for relative, text in FILES.items():
(root / relative).parent.mkdir(parents=True, exist_ok=True)
(root / relative).write_text(text, encoding="utf-8")
(root / "advisories.json").write_text(dump_advisories((ADVISORY,)), encoding="utf-8")
findings = engine.analyze_project(root, [engine.BUNDLED_PLUGINS]).findings
print("exploitable striptags:", sorted((f.span.start_line, f.metadata.get("through"), f.metadata.get("sink_line")) for f in findings if f.rule_id == "exploitable-vulnerability"))2. Cost: a cycle through doubled includes
level0.html holds {{ name|upper }}{% if more %}{% include 'level{n}.html' %}{% endif %}, and level{k}.html holds {% include 'level{k-1}.html' %}{% include 'level{k-1}.html' %}. A view renders level{n}.html. Django 5.1.15 renders it.
coretrace-python-analyzer --check on 0.24.0, Python 3.12:
| Levels | Without the include in level0.html |
With it |
|---|---|---|
| 12 | 0.7 s | 0.3 s |
| 14 | 0.2 s | 0.8 s |
| 16 | 0.2 s | 3.2 s |
| 18 | 0.2 s | 13.2 s |
| 20 | 0.3 s | 60.0 s |
This shape is unusual. On the 50 projects of the local corpus (14 Django packages, Django 5.1.4, the regression projects, the reproductions of #272 and #273), the walk takes at most 0.6 s.
Directions
These are not measured yet.
- False negative. Cut a cycle at a template already on the way with the same blocks overridden, instead of at its name alone. There are finitely many such pairs, so the walk still ends. In the case above,
b.htmlwalked again withbodyoverridden renders the child's block instead of the include, so the walk stops there, as Django does.- This changes the filters relative to the walk of 0.23.0, which
tests/test_template_filter_walk.pypins. Its cycle case and its comparison with the walk path by path would change.
- This changes the filters relative to the walk of 0.23.0, which
- Cost. Keep the walks a cycle cuts too. Such a walk depends on where it was entered only through which of the templates it reached are on the way. Keep with it the templates it reached, including those it was cut at, and reuse it wherever the same ones are on the way.
- On the shape above, each level would then be walked once for each template the analysis starts a walk from.
- This reuses results cut by a cycle, which templates: collecting filter calls takes time exponential in nested includes #279 chose not to do. It must give the same filters as the walk without it.
Activity
SizzleUnrlsd commentedon Oct 24, 2026
Design
The two directions of the issue were prototyped and measured against Django. Neither is enough on its own:
Both come from the same cause: the walk cuts a cycle at all. The design below drops the cut and computes a least fixpoint instead, which fixes both problems.
What a cut misses
The case of the issue is one instance. The more common one is a template including itself with other bindings, under a condition that ends the recursion:
t.html:{{ v|upper }}{% if go %}{% include 't.html' with v=n0 go='' %}{% endif %}Django 5.1.15 applies
uppertov, then ton0. The walk ofmaincuts the include att.htmland finds onlyv. Cutting at the pair (template, blocks overridden) cuts there too, since the include overrides no block.A recursive tree,
{{ node.name|upper }}{% for child in node.children %}{% include 'node.html' with node=child %}{% endfor %}, shows the same thing:upperat every level, to names that come fromnode.children.mainfinds onlynode.name.Rule
Facts. A fact is a filter that a render reaches: the function, where it is applied, the template applying it, and the names free in the rendered template that reach its value and its argument.
Pairs. A pair is a template, with the blocks that the templates extending it override. The render of a pair applies the facts of its rendered blocks, and renders the pairs its references reach:
{% extends %}adds the blocks the template replaces;{% include %}overrides none.Equations. For every pair
p,R(p)is the least set holding:papplies;rofp, the facts inR(child), with their names mapped throughr's bindings.There is no cut. A template reached again on the way contributes what it reaches.
Computation. The pairs a render reaches are listed once, with their facts and references. They are grouped into strongly connected components, computed by Tarjan's algorithm without recursion. A component is computed after every component its references reach, so their sets are final.
Join in cycles (review of #286). Each combination of the names reaching a filter's value and argument used to be its own fact. Bindings permuted around a cycle then made one fact of every combination: a 272-byte template including itself twice, rotating 14 variables and swapping two, gave 60,762 filters and took 12 s.
V1andV2therefore say what one fact withV1 ∪ V2says. Mapping through a reference distributes over the union, so joining before or after mapping is the same.Guarantees
Convergence. It is a property of the facts:
No partial result. No list is built, and none is returned, before every set of its component has converged. There is no cut, and no walk that a cycle stopped short is kept.
Order. The lists are built from the settled sets alone:
main, order included.The settled sets do not depend on the order of the computation. The components and the references' order are those of the templates. So the lists do not depend on it either.
Measurements
Python 3.12, on
mainat926df83. The design is implemented as G; A, B and AB are the two directions of the issue and their combination, prototyped to compare.Generated projects. There are 1,500 projects of four templates:
There are two modes:
{% if go %}and bindsgo='', so Django renders one more level of each cycle, as a project's condition would.Django. Django 5.1.15 renders each template, with
upperandstriptagsrecording the value they receive.main0, A 0, G 0main467, A 426, G 0What G finds beyond Django.
mainfor 16 templates, all because of a block that a template extending another defines and that no parent defines. Django never renders such a block; the walk counts it as rendered, as it already does without a cycle. Emptying those blocks makes G equal to Django on all 16. That over-approximation is outside this design: it has its own issue.Targeted Django checks. Django renders the templates of each new test, and the tests expect the facts it applies:
b.html)striptagstovand toother,uppertootherstriptagsreached byotheris newv=n0uppertov, then ton0upper, reached byvandn0uppertonode.name, then to the names ofnode.childrenupper, reached bynode.nameandnode.childrenUnrolled reference. This is an independent control. It walks every path path by path, letting each pair come back 3, then 4 times on the way, within a budget of 300,000 steps. With G it shares only how templates are read: what they apply and reference, which blocks render, and how bindings map names.
Closure. On every pair of all 1,500 projects, G's facts equal what the pair applies, with what its references reach mapped through them: as sets outside cycles, joined by application in them, one fact per application. So G's result is a fixpoint, including in the 5 projects above. That it is the least one there rests on the construction, not on the reference.
Order of the computation. G gives the same lists, order included, with the templates inserted in three other orders: 4,500 runs out of 4,500.
Against
main.main; the order may differ.End to end. The reproduction of the issue reports
exploitable-vulnerabilityatapp/views.py:5, throughb.html:1, whether the view passes the request asvor asother.Time. This times
project_templatesalone:mainWithout the join, the permuted bindings took 12 s with 14 variables. With the join, the full CLI analysis of that reproduction takes 0.35 s, as on
main.The shapes are:
level0.htmlincluding the top level under a condition;v0tov6, including itself twice, rotating the variables and swappingv0andv1.Tests
Existing tests that change. Both are in
tests/test_template_filter_walk.py. They pinned the walk ofmain, which cuts cycles; the module's docstring changes with them.test_a_child_its_parent_includes_back_gets_the_same_filters_whichever_is_walked_first, both cases. The parent's list gains(f"{FILTERS}.striptags", parent, 1, 6, parent, ("other",), ())at the end, as Django applies it.main. Its reference becomes the walk path by path, where each pair comes back 2, then 3 times, within 20,000 steps.New tests. These go in a new file:
other, and asvfor the control.