Applying a patch with a fuzzFactor can be very very slow

[ExplodingCabbage]

Thanks to the following five security researchers for reporting this:

• ziyue0530@gmail.com (Ziyue), https://zyy0530.github.io/
• 2459406270@qq.com (Chenchen), https://7thparkk.github.io/
• cshe0476@uni.sydney.edu.au (Strick), https://str1ckl4nd.github.io/
• liyi.zhou@sydney.edu.au (Liyi), https://lzhou1110.github.io/
• chng0012@uni.sydney.edu.au (Maurice), http://maurice.busystar.org/

Finding 1: Fuzzy patch application can cause algorithmic complexity DoS
Affected behavior

applyPatch and applyPatches support fuzzy patch matching. With crafted hunks and a high fuzzFactor, the matching logic can end up exploring many alternatives recursively and spend a large amount of CPU time on a single input.

Affected entrypoints

`applyPatch(...)`
`applyPatches(...)`

Reproduction notes
In our reproduction, a normal control case completed in under 1 ms, while a crafted fuzzy patch took about 7.7 seconds on the same setup:

control time: 0.568181 ms
exploit time: 7737.472789 ms
slowdown: 13617.9717x

The issue appears to come from recursive branch exploration in the fuzzy patch application logic.

[ExplodingCabbage]

My assorted thoughts follow.

Given the fuzzy-matching logic recurses whenever it pairs a patch line with a non-matching source file line, and it can do that up to fuzzFactor times, I guess the worst case execution time grows exponentially with fuzzFactor.

I nonetheless don't view this as having significant security implications since it will virtually always be the case that:

• the fuzzFactor is set by the application and not taken from untrusted input
• fuzzFactor is small
• it will occur to an application developer before choosing to use non-zero fuzz factors that this will necessarily have adverse performance implications and plausibly have serious ones, and if this matters to them they will do some benchmarking to ensure the perf they get is acceptable or else take measures to mitigate the problem (like doing their fuzzy-matching within an execution-time-limited subprocess)

I also think this is probably not a serious problem from an ordinary performance perspective either, since, again, fuzzFactor will normally be small!

All that said, it's not ideal. If I'm not mistaken/confused, I think the poor time complexity is surely avoidable! The current fuzzy matching algorithm is effectively using the naive recursive approach to computing Levenshtein distance, when of course much faster approaches are available. As it happens, on various occasions the idea of adding support for Levenshtein diffs to jsdiff has come up on the issue tracker; if I did this, I could use jsdiff's own Levenshtein diffing support to find the optimal pairing of lines from the patch with lines from the file being patched.

(Failing any of that, I could at least warn about the perf implications of a high fuzzFactor in the README!)