AllowedPattern is using python re module with user input
Bug #1217194 reported by
Clint Byrum
This bug affects 2 people
Affects | Status | Importance | Assigned to | Milestone | |
---|---|---|---|---|---|
OpenStack Heat |
Triaged
|
Medium
|
Unassigned |
Bug Description
A malicious user could eat up exponential amounts of CPU time and memory by using backreferences. For example
r"(\S+)+x"
If there are no "x" chars in a large body of text, the number of operations increases exponentially with every character being searched.
This capability must be controlled in some way, either by using a less capable regular expression matcher, or finding a way to detect and disable back references.
Changed in heat: | |
assignee: | nobody → Pavlo Shchelokovskyy (pshchelo) |
Changed in heat: | |
assignee: | Pavlo Shchelokovskyy (pshchelo) → nobody |
Changed in heat: | |
assignee: | nobody → Matthew Gilliard (matthew-gilliard-u) |
Changed in heat: | |
assignee: | Matthew Gilliard (matthew-gilliard-u) → nobody |
Changed in heat: | |
assignee: | nobody → Nikunj Aggarwal (nikunj2512) |
Changed in heat: | |
assignee: | Nikunj Aggarwal (nikunj2512) → nobody |
Changed in heat: | |
importance: | High → Medium |
Changed in heat: | |
milestone: | none → no-priority-tag-bugs |
To post a comment you must log in.
Just want to provide more data here, as it may not be clear how dangerous processing raw regular expressions can be:
clint@clint- HP:~/src$ cat /tmp/test.py
import re
import sys
n = int(sys.argv[1])
x = re.compile(('a?' * n) + ('a' * n)) HP:~/src$ time python /tmp/test.py 20
print bool(x.match('a' * n))
clint@clint-
True
real 0m0.085s HP:~/src$ time python /tmp/test.py 25
user 0m0.080s
sys 0m0.004s
clint@clint-
True
real 0m2.062s HP:~/src$ time python /tmp/test.py 30
user 0m2.048s
sys 0m0.012s
clint@clint-
^CTraceback (most recent call last):
File "/tmp/test.py", line 7, in <module>
print bool(x.match('a' * n))
KeyboardInterrupt
real 0m22.336s HP:~/src$ time python /tmp/test.py 26
user 0m22.284s
sys 0m0.008s
clint@clint-
True
real 0m4.165s HP:~/src$ time python /tmp/test.py 27
user 0m4.148s
sys 0m0.008s
clint@clint-
True
real 0m8.501s
user 0m8.456s
sys 0m0.028s
Note that with every added character, the CPU time doubles.