Applying a patch with a fuzzFactor can be very very slow

Thanks to the following five security researchers for reporting this:

• [email protected] (Ziyue), https://zyy0530.github.io/
• [email protected] (Chenchen), https://7thparkk.github.io/
• [email protected] (Strick), https://str1ckl4nd.github.io/
• [email protected] (Liyi), https://lzhou1110.github.io/
• [email protected] (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.