Re: [PATCH 0/3] wildmatch: fix exponential behavior

From: Derrick Stolee <derrickstolee@github.com>
Date: Mar 23, 2023, 14:19 UTC
Message-ID: <f6e3ae73-daae-3cc1-eb16-d4a24a2612db@github.com>
In-Reply-To: <cover.1679328580.git.phillip.wood@dunelm.org.uk>

On 3/20/2023 12:09 PM, Phillip Wood wrote:

Show 13 quoted lines

> From: Phillip Wood <phillip.wood@dunelm.org.uk>
> 
> The wildmatch implementation in git suffers from exponential behavior as
> described in [1] where the time taken for a failing match is exponential
> in the number of wildcards it contains. The original implementation
> imported from rsync is immune but the optimizations introduced by [2.3]
> failed to prevent unnecessary backtracking when handling '*' and '/**/'.
> 
> This bug was were discussed on the security list and the conclusion was
> that it only affects operations that are already potential DoS vectors.
> 
> In the long term it would be nice to get rid of the recursion in the
> wildmatch() code but the patches here focus on a minimal fix.

Thanks for these changes. The patches look good to me.

I particularly appreciate that there is a regression test to avoid this accidentally happening again in the future. The two second timeout is a reasonable balance between "not taking too long" and "will not be flaky, assuming the code is correct". I could imagine that it might _pass_ unexpectedly if it runs on fast-enough hardware, but that's not a huge concern right now. CI machines are not normally powered significantly more than a typical developer machine.

Thanks, -Stolee