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

[Phillip Wood <phillip.wood123@gmail.com>]

Hi Stolee

On 23/03/2023 14:19, Derrick Stolee wrote:
> On 3/20/2023 12:09 PM, Phillip Wood wrote:
>> 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 for taking the time to look at these again and for prompting me 
to add the regression test in the first place.

Best Wishes

Phillip

> Thanks,
> -Stolee