From: Phillip Wood Date: Fri, 24 Mar 2023 14:04:47 GMT Subject: Re: [PATCH 0/3] wildmatch: fix exponential behavior Message-ID: <9489e843-1612-4aca-4e20-de23636e16d5@dunelm.org.uk> In-Reply-To: Hi Stolee On 23/03/2023 14:19, Derrick Stolee wrote: > On 3/20/2023 12:09 PM, Phillip Wood wrote: >> From: Phillip Wood >> >> 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