borgbackup
Pattern evaluation is easily dos'd
While it's pretty clear that re: patterns can trivially lead to exponential CPU use, fm: and sh: are affected as well, since they translate to the same backtracing regex engine (Python sre).
Easy reproducer:
borg init repo
mkdir input
touch input/aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
borg create repo::archive input -e 'input/a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b'
This is problematic for anyone who uses Borg as back-end where users can specify exclusion patterns and the expectation that Borg would not consume arbitrary amounts of resources exists (e.g. because user directories already have quotas).
Suggested workaround for developers: Sanitize user-specified patterns to prefix them with sh: or fm:, so that no regex may be specified, and ensure that each pattern contains only ~two or so **/* (sh:/fm:).
Workaround for Borg:
Not so easy.
Since re: was exposed in the past and is basically not possible to implement using any RE engine other than SRE, that attack surface is not possible to close. In fact this was already discussed once: #2459
For sh: and fm: we should switch to either a real glob implementation and not translation to regexes, or use a DFA RE engine (like re2).
Reference: https://research.swtch.com/glob
a*a*a*b takes <0.1 seconds to not match. a*a*a*a*b takes 0.3 seconds to not match. a*a*a*a*a*b takes 10 seconds to not match.
Wolfram alpha tells us that the reproducer would take about 1e+30 years to not match. Exponential complexity is ... pretty bad. There's a reason NP is the land of idle dreams...
Edit: Due to the not very accurate first data point the fit is a bit off. Six a* is predicted as 330 seconds, but actually takes 452 seconds. Thus, the new prediction for the reproducer would actually be 2.8e+46 years (a mere factor 28 quadrillion).
The speed-up by avoiding broken algorithms should be in the range of approximately 100 septendecillion for the reproducer.
What is the bug here? (see labels)
About the potential DoS: it is the client that is DoSed here. Which is pretty pointless if it is not a multiuser system. On multiuser-systems there are likely a lot of ways to consume inappropriate amounts of resources, you don't need to tweak borg's patterns for that.
What is the bug here?
Globbing is generally expected to complete in less than one era, and it's not that difficult to run into this issue. Just mistaking fm: for a shell-like syntax can cause it in some circumstances (a pattern like */*/* should work).
An implementation issue in sh:, not collapsing adjacent equivalent stars, contributes to the problem. fm: has the same problem. Just a short run of stars makes it hang.
Therefore, this is at least a docs bug, since the docs don't mention any of these issues at all. I very much see this as a Borg bug as well.
Which is pretty pointless if it is not a multiuser system.
=>
This is problematic for anyone who uses Borg as back-end where users can specify exclusion patterns and the expectation that Borg would not consume arbitrary amounts of resources exists (e.g. because user directories already have quotas).