Re: [PATCH] t4062: stop using repetition in regex
- From
René Scharfe <l.s.r@web.de>
- Date
- Aug 9, 2017, 14:15 UTC
- Message-ID
- <e3e65635-2dc8-de58-5662-3eab619aedb3@web.de>
- In-Reply-To
- <50c2eaab-d1d8-3376-6e7a-1c898d978d12@web.de>
Am 09.08.2017 um 08:15 schrieb René Scharfe:
Show 38 quoted lines
> Am 09.08.2017 um 07:29 schrieb Junio C Hamano:
>> René Scharfe <l.s.r@web.de> writes:
>>
>>> Am 09.08.2017 um 00:26 schrieb Junio C Hamano:
>>>> ... but in the meantime, I think replacing the test with "0$" to
>>>> force the scanner to find either the end of line or the end of the
>>>> buffer may be a good workaround. We do not have to care how many of
>>>> random bytes are in front of the last "0" in order to ensure that
>>>> the regexec_buf() does not overstep to 4097th byte, while seeing
>>>> that regexec() that does not know how long the haystack is has to do
>>>> so, no?
>>>
>>> Our regexec() calls strlen() (see my other reply).
>>>
>>> Using "0$" looks like the best option to me.
>>
>> Yeah, it seems that way. If we want to be close/faithful to the
>> original, we could do "^0*$", but the part that is essential to
>> trigger the old bug is not the "we have many zeroes" (or "we have
>> 4096 zeroes") part, but "zero is at the end of the string" part, so
>> "0$" would be the minimal pattern that also would work for OBSD.
>
> Thought about it a bit more.
>
> "^0{4096}$" checks if the byte after the buffer is \n or \0 in the
> hope of triggering a segfault. On Linux I can access that byte just
> fine; perhaps there is no guard page. Also there is a 2 in 256
> chance of the byte being \n or \0 (provided its value is random),
> which would cause the test to falsely report success.
>
> "0$" effectively looks for "0\n" or "0\0", which can only occur
> after the buffer. If that string is found close enough then we
> may not trigger a segfault and report a false positive.
>
> In the face of unreliable segfaults we need to reverse our strategy,
> I think. Searching for something not in the buffer (e.g. "1") and
> considering matches and segfaults as confirmation that the bug is
> still present should avoid any false positives. Right?And that's not it either. *sigh*
If the 4097th byte is NUL or LF then we can only hope its access triggers a segfault -- there is no other way to distinguish the result from a legitimate match when limiting with REG_STARTEND. So we have to accept this flakiness.
We can check the value of that byte with [^0] and interpret a match as failure, but that adds negation and makes the test more complex.
^0*$ would falsely match if the 4097th byte (and possibly later ones) is 0. We need to make sure we check for end-of-line after the 4096th byte, not later.
Sorry, Dscho, I thought we could take a shortcut here, but -- as you wrote all along -- we can't.
So how about this?
-- >8 -- Subject: [PATCH] t4062: use less than 256 repetitions in regex
OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255. That's the minimum acceptable value according to POSIX. In t4062 we use 4096 repetitions in the test "-G matches", though, causing it to fail. Combine two repetition operators, both less than 256, to arrive at 4096 zeros instead of using a single one, to fix the test on OpenBSD.
Original-patch-by: David Coppa <dcoppa@openbsd.org> Signed-off-by: Rene Scharfe <l.s.r@web.de> --- t/t4062-diff-pickaxe.sh | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
diff --git a/t/t4062-diff-pickaxe.sh b/t/t4062-diff-pickaxe.sh index 7c4903f497..1130c8019b 100755 --- a/t/t4062-diff-pickaxe.sh +++ b/t/t4062-diff-pickaxe.sh @@ -14,8 +14,10 @@ test_expect_success setup ' test_tick && git commit -m "A 4k file" ' + +# OpenBSD only supports up to 255 repetitions, so repeat twice for 64*64=4096. test_expect_success '-G matches' ' - git diff --name-only -G "^0{4096}$" HEAD^ >out && + git diff --name-only -G "^(0{64}){64}$" HEAD^ >out && test 4096-zeroes.txt = "$(cat out)" '
-- 2.14.0