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

From: Derrick Stolee <[email-masked]>
Date: Thu, 23 Mar 2023 10:19:21 -0400

On 3/20/2023 12:09 PM, Phillip Wood wrote:
> From: Phillip Wood <[email-masked]>
> 
> 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