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

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



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@xxxxxxxxxxxxx>

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



[Index of Archives]     [Linux Kernel Development]     [Gcc Help]     [IETF Annouce]     [DCCP]     [Netdev]     [Networking]     [Security]     [V4L]     [Bugtraq]     [Yosemite]     [MIPS Linux]     [ARM Linux]     [Linux Security]     [Linux RAID]     [Linux SCSI]     [Fedora Users]

  Powered by Linux