{"thread":{"id":"46537","subject":"[PATCH] t4062: stop using repetition in regex","startedAt":"2017-08-08T06:53:43Z","lastAt":"2017-08-11T18:21:12Z","messageCount":17,"participants":["René Scharfe","Johannes Schindelin","Junio C Hamano","David Coppa"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"325783","messageId":"861dc875-7300-fe5a-1360-0ed546c8c2bb@web.de","threadId":"46537","inReplyTo":null,"subject":"[PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-08T06:53:21Z","receivedAt":"2017-08-08T06:53:43Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\nThat's the minimum acceptable value according to POSIX.  In t4062 we use\n4096 repetitions in the test \"-G matches\", though, causing it to fail.\n\nDo the same as the test \"-S --pickaxe-regex\" in the same file and search\nfor a single zero instead.  That still suffices to trigger the buffer\noverrun in older versions (checked with b7d36ffca02^ and --valgrind on\nLinux), simplifies the test a bit, and avoids exceeding OpenBSD's limit.\n\nOriginal-patch-by: David Coppa <dcoppa@openbsd.org>\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n t/t4062-diff-pickaxe.sh | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/t/t4062-diff-pickaxe.sh b/t/t4062-diff-pickaxe.sh\nindex 7c4903f497..c16e5af6fa 100755\n--- a/t/t4062-diff-pickaxe.sh\n+++ b/t/t4062-diff-pickaxe.sh\n@@ -15,7 +15,7 @@ test_expect_success setup '\n \tgit commit -m \"A 4k file\"\n '\n test_expect_success '-G matches' '\n-\tgit diff --name-only -G \"^0{4096}$\" HEAD^ >out &&\n+\tgit diff --name-only -G0 HEAD^ >out &&\n \ttest 4096-zeroes.txt = \"$(cat out)\"\n '\n \n-- \n2.14.0\n"},{"id":"325807","messageId":"alpine.DEB.2.21.1.1708081648130.11175@virtualbox","threadId":"46537","inReplyTo":"861dc875-7300-fe5a-1360-0ed546c8c2bb@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-08-08T14:49:59Z","receivedAt":"2017-08-08T14:50:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi René,\n\nOn Tue, 8 Aug 2017, René Scharfe wrote:\n\n> OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\n> That's the minimum acceptable value according to POSIX.  In t4062 we use\n> 4096 repetitions in the test \"-G matches\", though, causing it to fail.\n> \n> Do the same as the test \"-S --pickaxe-regex\" in the same file and search\n> for a single zero instead.  That still suffices to trigger the buffer\n> overrun in older versions (checked with b7d36ffca02^ and --valgrind on\n> Linux), simplifies the test a bit, and avoids exceeding OpenBSD's limit.\n\nI am afraid not. The 4096 is precisely the page size required to trigger\nthe bug on Windows against which this regression test tries to safeguard.\n\nMaybe simply disable the test on OpenBSD instead? Or guard the {4096}\nbehind the MINGW prereq.\n\nCiao,\nDscho"},{"id":"325809","messageId":"1e7ed028-77fe-195a-4acf-6c80d1704463@web.de","threadId":"46537","inReplyTo":"alpine.DEB.2.21.1.1708081648130.11175@virtualbox","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-08T15:18:31Z","receivedAt":"2017-08-08T15:19:36Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 08.08.2017 um 16:49 schrieb Johannes Schindelin:\n> Hi René,\n> \n> On Tue, 8 Aug 2017, René Scharfe wrote:\n> \n>> OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\n>> That's the minimum acceptable value according to POSIX.  In t4062 we use\n>> 4096 repetitions in the test \"-G matches\", though, causing it to fail.\n>>\n>> Do the same as the test \"-S --pickaxe-regex\" in the same file and search\n>> for a single zero instead.  That still suffices to trigger the buffer\n>> overrun in older versions (checked with b7d36ffca02^ and --valgrind on\n>> Linux), simplifies the test a bit, and avoids exceeding OpenBSD's limit.\n> \n> I am afraid not. The 4096 is precisely the page size required to trigger\n> the bug on Windows against which this regression test tries to safeguard.\n\nChecked with b7d36ffca02^ on MinGW now as well and found that it\nsegfaults with the proposed change ten out of ten times.\n\nYou get different results?  How is that possible?  The search string is\nNUL-terminated in each case, while the point of the test is that the\nfile contents isn't, right?\n\n> Maybe simply disable the test on OpenBSD instead? Or guard the {4096}\n> behind the MINGW prereq.\n\nIt's easy to build a long search string with two repetitions or by using\na longer string as the base, if necessary.  But first we need to find out\nwhy regexec() doesn't overflow in your case.  My build uses the version\nfrom compat/.  Why would it stop before reaching a NUL?  That sounds like\na different and serious bug.\n\nThanks,\nRené\n"},{"id":"325866","messageId":"xmqqinhxaf0i.fsf@gitster.mtv.corp.google.com","threadId":"46537","inReplyTo":"1e7ed028-77fe-195a-4acf-6c80d1704463@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-08T22:09:01Z","receivedAt":"2017-08-08T22:09:17Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Am 08.08.2017 um 16:49 schrieb Johannes Schindelin:\n>> Hi René,\n>> \n>> On Tue, 8 Aug 2017, René Scharfe wrote:\n>> \n>>> OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\n>>> That's the minimum acceptable value according to POSIX.  In t4062 we use\n>>> 4096 repetitions in the test \"-G matches\", though, causing it to fail.\n>>>\n>>> Do the same as the test \"-S --pickaxe-regex\" in the same file and search\n>>> for a single zero instead.  That still suffices to trigger the buffer\n>>> overrun in older versions (checked with b7d36ffca02^ and --valgrind on\n>>> Linux), simplifies the test a bit, and avoids exceeding OpenBSD's limit.\n>> \n>> I am afraid not. The 4096 is precisely the page size required to trigger\n>> the bug on Windows against which this regression test tries to safeguard.\n>\n> Checked with b7d36ffca02^ on MinGW now as well and found that it\n> segfaults with the proposed change ten out of ten times.\n\nThat is a strange result but I can believe it.\n\nThe reason why I find it strange is that the test wants to run\ndiff_grep() in diffcore-pickaxe.c with one == NULL (because we are\nlooking at difference between an initial empty commit and the\ncurrent commit that adds 4096-zeroes.txt file), which makes the\ncurrent blob (i.e. a page of '0' that may be mmap(2)ed without\ntrailing NUL to terminate it) scanned via regexec() to look for the\nsearch string.\n\nI can understand why Dscho originally did \"^0{4096}$\"; it is to\nensure that the whole page is scanned for 4096 zeroes and then the\ncode would somehow make sure that there is no more byte until the\nend of line, which will force regexec (but not regexec_buf that knows\nwhere the buffer ends) to look at the 4097th byte that does not exist.\n\nIf you change the pattern to just \"0\" that is not anchored, I'd expect\nregexec() that does not know how big the haystack is to just find \"0\"\nat the first byte and happily return without segfaulting (because it\ndoes not even have to scan the remainder of the buffer).\n\nSo I find Dscho's concern quite valid, even though I do believe you\nwhen you say the code somehow segfaults.  I just can not tell\nhow/why it would segfault, though---it is possible that regexec()\nimplementation is stupid and does not realize that it can return early\nreporting success without looking at the rest of the buffer, but\nsomehow I find it unlikely.\n\nPuzzled.\n\n> You get different results?  How is that possible?  The search string is\n> NUL-terminated in each case, while the point of the test is that the\n> file contents isn't, right?\n"},{"id":"325868","messageId":"xmqq7eydae7r.fsf@gitster.mtv.corp.google.com","threadId":"46537","inReplyTo":"xmqqinhxaf0i.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-08T22:26:16Z","receivedAt":"2017-08-08T22:26:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <gitster@pobox.com> writes:\n\n> So I find Dscho's concern quite valid, even though I do believe you\n> when you say the code somehow segfaults.  I just can not tell\n> how/why it would segfault, though---it is possible that regexec()\n> implementation is stupid and does not realize that it can return early\n> reporting success without looking at the rest of the buffer, but\n> somehow I find it unlikely.\n>\n> Puzzled.\n>\n>> You get different results?  How is that possible?  The search string is\n>> NUL-terminated in each case, while the point of the test is that the\n>> file contents isn't, right?\n\nIntellectual curiosity tells me we may want to find out why it\nfails, but in the meantime, I think replacing the test with \"0$\" to\nforce the scanner to find either the end of line or the end of the\nbuffer may be a good workaround.  We do not have to care how many of\nrandom bytes are in front of the last \"0\" in order to ensure that\nthe regexec_buf() does not overstep to 4097th byte, while seeing\nthat regexec() that does not know how long the haystack is has to do\nso, no?\n"},{"id":"325870","messageId":"6e721fde-0c6d-1539-b4fb-110aac47989b@web.de","threadId":"46537","inReplyTo":"xmqqinhxaf0i.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-08T22:27:58Z","receivedAt":"2017-08-08T22:28:13Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 00:09 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>> Am 08.08.2017 um 16:49 schrieb Johannes Schindelin:\n>>> Hi René,\n>>>\n>>> On Tue, 8 Aug 2017, René Scharfe wrote:\n>>>\n>>>> OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\n>>>> That's the minimum acceptable value according to POSIX.  In t4062 we use\n>>>> 4096 repetitions in the test \"-G matches\", though, causing it to fail.\n>>>>\n>>>> Do the same as the test \"-S --pickaxe-regex\" in the same file and search\n>>>> for a single zero instead.  That still suffices to trigger the buffer\n>>>> overrun in older versions (checked with b7d36ffca02^ and --valgrind on\n>>>> Linux), simplifies the test a bit, and avoids exceeding OpenBSD's limit.\n>>>\n>>> I am afraid not. The 4096 is precisely the page size required to trigger\n>>> the bug on Windows against which this regression test tries to safeguard.\n>>\n>> Checked with b7d36ffca02^ on MinGW now as well and found that it\n>> segfaults with the proposed change ten out of ten times.\n> \n> That is a strange result but I can believe it.\n> \n> The reason why I find it strange is that the test wants to run\n> diff_grep() in diffcore-pickaxe.c with one == NULL (because we are\n> looking at difference between an initial empty commit and the\n> current commit that adds 4096-zeroes.txt file), which makes the\n> current blob (i.e. a page of '0' that may be mmap(2)ed without\n> trailing NUL to terminate it) scanned via regexec() to look for the\n> search string.\n> \n> I can understand why Dscho originally did \"^0{4096}$\"; it is to\n> ensure that the whole page is scanned for 4096 zeroes and then the\n> code would somehow make sure that there is no more byte until the\n> end of line, which will force regexec (but not regexec_buf that knows\n> where the buffer ends) to look at the 4097th byte that does not exist.\n> \n> If you change the pattern to just \"0\" that is not anchored, I'd expect\n> regexec() that does not know how big the haystack is to just find \"0\"\n> at the first byte and happily return without segfaulting (because it\n> does not even have to scan the remainder of the buffer).\n> \n> So I find Dscho's concern quite valid, even though I do believe you\n> when you say the code somehow segfaults.  I just can not tell\n> how/why it would segfault, though---it is possible that regexec()\n> implementation is stupid and does not realize that it can return early\n> reporting success without looking at the rest of the buffer, but\n> somehow I find it unlikely.\n> \n> Puzzled.\n\nGood point.  Valgrind reports:\n\n==57466== Process terminating with default action of signal 11 (SIGSEGV): dumping core\n==57466==  Access not within mapped region at address 0x4027000\n==57466==    at 0x4C2EDF4: strlen (vg_replace_strmem.c:458)\n==57466==    by 0x59D9F76: regexec@@GLIBC_2.3.4 (regexec.c:240)\n==57466==    by 0x54D96E: diff_grep (diffcore-pickaxe.c:0)\n==57466==    by 0x54DAC3: pickaxe_match (diffcore-pickaxe.c:149)\n\nAnd you can see in our version in compat/regex/regexec.c:241 that the\nfirst thing regexec() does is calling strlen().\n\nSo to avoid depending on that implementation detail we'd need to use\na search string that won't be found (e.g. \"1\") or with unlimited\nrepetition (e.g. \"0*\"), right?\n\nRené\n"},{"id":"325874","messageId":"cd60d779-fe38-4f0e-4d36-2c40b2afec7d@web.de","threadId":"46537","inReplyTo":"xmqq7eydae7r.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-08T22:34:30Z","receivedAt":"2017-08-08T22:34:45Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 00:26 schrieb Junio C Hamano:\n> Junio C Hamano <gitster@pobox.com> writes:\n> \n>> So I find Dscho's concern quite valid, even though I do believe you\n>> when you say the code somehow segfaults.  I just can not tell\n>> how/why it would segfault, though---it is possible that regexec()\n>> implementation is stupid and does not realize that it can return early\n>> reporting success without looking at the rest of the buffer, but\n>> somehow I find it unlikely.\n>>\n>> Puzzled.\n>>\n>>> You get different results?  How is that possible?  The search string is\n>>> NUL-terminated in each case, while the point of the test is that the\n>>> file contents isn't, right?\n> \n> Intellectual curiosity tells me we may want to find out why it\n> fails, but in the meantime, I think replacing the test with \"0$\" to\n> force the scanner to find either the end of line or the end of the\n> buffer may be a good workaround.  We do not have to care how many of\n> random bytes are in front of the last \"0\" in order to ensure that\n> the regexec_buf() does not overstep to 4097th byte, while seeing\n> that regexec() that does not know how long the haystack is has to do\n> so, no?\n\nOur regexec() calls strlen() (see my other reply).\n\nUsing \"0$\" looks like the best option to me.\n\nRené\n"},{"id":"325915","messageId":"xmqqtw1h8g1u.fsf@gitster.mtv.corp.google.com","threadId":"46537","inReplyTo":"cd60d779-fe38-4f0e-4d36-2c40b2afec7d@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-09T05:29:33Z","receivedAt":"2017-08-09T05:29:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Am 09.08.2017 um 00:26 schrieb Junio C Hamano:\n>> ... but in the meantime, I think replacing the test with \"0$\" to\n>> force the scanner to find either the end of line or the end of the\n>> buffer may be a good workaround.  We do not have to care how many of\n>> random bytes are in front of the last \"0\" in order to ensure that\n>> the regexec_buf() does not overstep to 4097th byte, while seeing\n>> that regexec() that does not know how long the haystack is has to do\n>> so, no?\n>\n> Our regexec() calls strlen() (see my other reply).\n>\n> Using \"0$\" looks like the best option to me.\n\nYeah, it seems that way.  If we want to be close/faithful to the\noriginal, we could do \"^0*$\", but the part that is essential to\ntrigger the old bug is not the \"we have many zeroes\" (or \"we have\n4096 zeroes\") part, but \"zero is at the end of the string\" part, so\n\"0$\" would be the minimal pattern that also would work for OBSD.\n\nDscho?\n"},{"id":"325921","messageId":"50c2eaab-d1d8-3376-6e7a-1c898d978d12@web.de","threadId":"46537","inReplyTo":"xmqqtw1h8g1u.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-09T06:15:59Z","receivedAt":"2017-08-09T06:16:27Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 07:29 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>> Am 09.08.2017 um 00:26 schrieb Junio C Hamano:\n>>> ... but in the meantime, I think replacing the test with \"0$\" to\n>>> force the scanner to find either the end of line or the end of the\n>>> buffer may be a good workaround.  We do not have to care how many of\n>>> random bytes are in front of the last \"0\" in order to ensure that\n>>> the regexec_buf() does not overstep to 4097th byte, while seeing\n>>> that regexec() that does not know how long the haystack is has to do\n>>> so, no?\n>>\n>> Our regexec() calls strlen() (see my other reply).\n>>\n>> Using \"0$\" looks like the best option to me.\n> \n> Yeah, it seems that way.  If we want to be close/faithful to the\n> original, we could do \"^0*$\", but the part that is essential to\n> trigger the old bug is not the \"we have many zeroes\" (or \"we have\n> 4096 zeroes\") part, but \"zero is at the end of the string\" part, so\n> \"0$\" would be the minimal pattern that also would work for OBSD.\n\nThought about it a bit more.\n\n\"^0{4096}$\" checks if the byte after the buffer is \\n or \\0 in the\nhope of triggering a segfault.  On Linux I can access that byte just\nfine; perhaps there is no guard page.  Also there is a 2 in 256\nchance of the byte being \\n or \\0 (provided its value is random),\nwhich would cause the test to falsely report success.\n\n\"0$\" effectively looks for \"0\\n\" or \"0\\0\", which can only occur\nafter the buffer.  If that string is found close enough then we\nmay not trigger a segfault and report a false positive.\n\nIn the face of unreliable segfaults we need to reverse our strategy,\nI think.  Searching for something not in the buffer (e.g. \"1\") and\nconsidering matches and segfaults as confirmation that the bug is\nstill present should avoid any false positives.  Right?\n\nThanks,\nRené\n"},{"id":"325953","messageId":"e3e65635-2dc8-de58-5662-3eab619aedb3@web.de","threadId":"46537","inReplyTo":"50c2eaab-d1d8-3376-6e7a-1c898d978d12@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-09T14:15:10Z","receivedAt":"2017-08-09T14:15:37Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 08:15 schrieb René Scharfe:\n> Am 09.08.2017 um 07:29 schrieb Junio C Hamano:\n>> René Scharfe <l.s.r@web.de> writes:\n>>\n>>> Am 09.08.2017 um 00:26 schrieb Junio C Hamano:\n>>>> ... but in the meantime, I think replacing the test with \"0$\" to\n>>>> force the scanner to find either the end of line or the end of the\n>>>> buffer may be a good workaround.  We do not have to care how many of\n>>>> random bytes are in front of the last \"0\" in order to ensure that\n>>>> the regexec_buf() does not overstep to 4097th byte, while seeing\n>>>> that regexec() that does not know how long the haystack is has to do\n>>>> so, no?\n>>>\n>>> Our regexec() calls strlen() (see my other reply).\n>>>\n>>> Using \"0$\" looks like the best option to me.\n>>\n>> Yeah, it seems that way.  If we want to be close/faithful to the\n>> original, we could do \"^0*$\", but the part that is essential to\n>> trigger the old bug is not the \"we have many zeroes\" (or \"we have\n>> 4096 zeroes\") part, but \"zero is at the end of the string\" part, so\n>> \"0$\" would be the minimal pattern that also would work for OBSD.\n> \n> Thought about it a bit more.\n> \n> \"^0{4096}$\" checks if the byte after the buffer is \\n or \\0 in the\n> hope of triggering a segfault.  On Linux I can access that byte just\n> fine; perhaps there is no guard page.  Also there is a 2 in 256\n> chance of the byte being \\n or \\0 (provided its value is random),\n> which would cause the test to falsely report success.\n> \n> \"0$\" effectively looks for \"0\\n\" or \"0\\0\", which can only occur\n> after the buffer.  If that string is found close enough then we\n> may not trigger a segfault and report a false positive.\n> \n> In the face of unreliable segfaults we need to reverse our strategy,\n> I think.  Searching for something not in the buffer (e.g. \"1\") and\n> considering matches and segfaults as confirmation that the bug is\n> still present should avoid any false positives.  Right?\n\nAnd that's not it either. *sigh*\n\nIf the 4097th byte is NUL or LF then we can only hope its access\ntriggers a segfault -- there is no other way to distinguish the\nresult from a legitimate match when limiting with REG_STARTEND.  So\nwe have to accept this flakiness.\n\nWe can check the value of that byte with [^0] and interpret a\nmatch as failure, but that adds negation and makes the test more\ncomplex.\n\n^0*$ would falsely match if the 4097th byte (and possibly later\nones) is 0.  We need to make sure we check for end-of-line after\nthe 4096th byte, not later.\n\nSorry, Dscho, I thought we could take a shortcut here, but -- as\nyou wrote all along -- we can't.\n\nSo how about this?\n\n-- >8 --\nSubject: [PATCH] t4062: use less than 256 repetitions in regex\n\nOpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\nThat's the minimum acceptable value according to POSIX.  In t4062 we use\n4096 repetitions in the test \"-G matches\", though, causing it to fail.\nCombine two repetition operators, both less than 256, to arrive at 4096\nzeros instead of using a single one, to fix the test on OpenBSD.\n\nOriginal-patch-by: David Coppa <dcoppa@openbsd.org>\nSigned-off-by: Rene Scharfe <l.s.r@web.de>\n---\n t/t4062-diff-pickaxe.sh | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/t/t4062-diff-pickaxe.sh b/t/t4062-diff-pickaxe.sh\nindex 7c4903f497..1130c8019b 100755\n--- a/t/t4062-diff-pickaxe.sh\n+++ b/t/t4062-diff-pickaxe.sh\n@@ -14,8 +14,10 @@ test_expect_success setup '\n \ttest_tick &&\n \tgit commit -m \"A 4k file\"\n '\n+\n+# OpenBSD only supports up to 255 repetitions, so repeat twice for 64*64=4096.\n test_expect_success '-G matches' '\n-\tgit diff --name-only -G \"^0{4096}$\" HEAD^ >out &&\n+\tgit diff --name-only -G \"^(0{64}){64}$\" HEAD^ >out &&\n \ttest 4096-zeroes.txt = \"$(cat out)\"\n '\n \n-- \n2.14.0\n"},{"id":"325954","messageId":"CABM=MFLYkVDjpeVKbErbX+szv7_NXre6U_Z_cOtKakcPDR5U3w@mail.gmail.com","threadId":"46537","inReplyTo":"e3e65635-2dc8-de58-5662-3eab619aedb3@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"David Coppa","fromEmail":"dcoppa@gmail.com","sentAt":"2017-08-09T14:25:23Z","receivedAt":"2017-08-09T14:25:50Z","isPatch":true,"sender":{"key":"dcoppa@gmail.com","avatar":null},"body":"On Wed, Aug 9, 2017 at 4:15 PM, René Scharfe <l.s.r@web.de> wrote:\n> Am 09.08.2017 um 08:15 schrieb René Scharfe:\n>> Am 09.08.2017 um 07:29 schrieb Junio C Hamano:\n>>> René Scharfe <l.s.r@web.de> writes:\n>>>\n>>>> Am 09.08.2017 um 00:26 schrieb Junio C Hamano:\n>>>>> ... but in the meantime, I think replacing the test with \"0$\" to\n>>>>> force the scanner to find either the end of line or the end of the\n>>>>> buffer may be a good workaround.  We do not have to care how many of\n>>>>> random bytes are in front of the last \"0\" in order to ensure that\n>>>>> the regexec_buf() does not overstep to 4097th byte, while seeing\n>>>>> that regexec() that does not know how long the haystack is has to do\n>>>>> so, no?\n>>>>\n>>>> Our regexec() calls strlen() (see my other reply).\n>>>>\n>>>> Using \"0$\" looks like the best option to me.\n>>>\n>>> Yeah, it seems that way.  If we want to be close/faithful to the\n>>> original, we could do \"^0*$\", but the part that is essential to\n>>> trigger the old bug is not the \"we have many zeroes\" (or \"we have\n>>> 4096 zeroes\") part, but \"zero is at the end of the string\" part, so\n>>> \"0$\" would be the minimal pattern that also would work for OBSD.\n>>\n>> Thought about it a bit more.\n>>\n>> \"^0{4096}$\" checks if the byte after the buffer is \\n or \\0 in the\n>> hope of triggering a segfault.  On Linux I can access that byte just\n>> fine; perhaps there is no guard page.  Also there is a 2 in 256\n>> chance of the byte being \\n or \\0 (provided its value is random),\n>> which would cause the test to falsely report success.\n>>\n>> \"0$\" effectively looks for \"0\\n\" or \"0\\0\", which can only occur\n>> after the buffer.  If that string is found close enough then we\n>> may not trigger a segfault and report a false positive.\n>>\n>> In the face of unreliable segfaults we need to reverse our strategy,\n>> I think.  Searching for something not in the buffer (e.g. \"1\") and\n>> considering matches and segfaults as confirmation that the bug is\n>> still present should avoid any false positives.  Right?\n>\n> And that's not it either. *sigh*\n>\n> If the 4097th byte is NUL or LF then we can only hope its access\n> triggers a segfault -- there is no other way to distinguish the\n> result from a legitimate match when limiting with REG_STARTEND.  So\n> we have to accept this flakiness.\n>\n> We can check the value of that byte with [^0] and interpret a\n> match as failure, but that adds negation and makes the test more\n> complex.\n>\n> ^0*$ would falsely match if the 4097th byte (and possibly later\n> ones) is 0.  We need to make sure we check for end-of-line after\n> the 4096th byte, not later.\n>\n> Sorry, Dscho, I thought we could take a shortcut here, but -- as\n> you wrote all along -- we can't.\n>\n> So how about this?\n>\n> -- >8 --\n> Subject: [PATCH] t4062: use less than 256 repetitions in regex\n>\n> OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\n> That's the minimum acceptable value according to POSIX.  In t4062 we use\n> 4096 repetitions in the test \"-G matches\", though, causing it to fail.\n> Combine two repetition operators, both less than 256, to arrive at 4096\n> zeros instead of using a single one, to fix the test on OpenBSD.\n>\n> Original-patch-by: David Coppa <dcoppa@openbsd.org>\n> Signed-off-by: Rene Scharfe <l.s.r@web.de>\n> ---\n>  t/t4062-diff-pickaxe.sh | 4 +++-\n>  1 file changed, 3 insertions(+), 1 deletion(-)\n>\n> diff --git a/t/t4062-diff-pickaxe.sh b/t/t4062-diff-pickaxe.sh\n> index 7c4903f497..1130c8019b 100755\n> --- a/t/t4062-diff-pickaxe.sh\n> +++ b/t/t4062-diff-pickaxe.sh\n> @@ -14,8 +14,10 @@ test_expect_success setup '\n>         test_tick &&\n>         git commit -m \"A 4k file\"\n>  '\n> +\n> +# OpenBSD only supports up to 255 repetitions, so repeat twice for 64*64=4096.\n>  test_expect_success '-G matches' '\n> -       git diff --name-only -G \"^0{4096}$\" HEAD^ >out &&\n> +       git diff --name-only -G \"^(0{64}){64}$\" HEAD^ >out &&\n>         test 4096-zeroes.txt = \"$(cat out)\"\n>  '\n>\n> --\n> 2.14.0\n\nI think this should work w/o problems on OpenBSD:\n\n$ uname -a\nOpenBSD open.bsdgeek.it 6.1 GENERIC#54 amd64\n$ git diff --name-only -G \"^0{4096}$\" HEAD^ 1>/dev/null\nfatal: invalid regex: invalid repetition count(s)\n$ git diff --name-only -G \"^(0{64}){64}$\" HEAD^ 1>/dev/null\n$\n\nCiao!\nDavid\n"},{"id":"325963","messageId":"xmqqh8xg7mhy.fsf@gitster.mtv.corp.google.com","threadId":"46537","inReplyTo":"e3e65635-2dc8-de58-5662-3eab619aedb3@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-09T16:07:53Z","receivedAt":"2017-08-09T16:08:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n>> In the face of unreliable segfaults we need to reverse our strategy,\n>> I think.  Searching for something not in the buffer (e.g. \"1\") and\n>> considering matches and segfaults as confirmation that the bug is\n>> still present should avoid any false positives.  Right?\n>\n> And that's not it either. *sigh*\n>\n> If the 4097th byte is NUL or LF then we can only hope its access\n> triggers a segfault -- there is no other way to distinguish the\n> result from a legitimate match when limiting with REG_STARTEND.  So\n> we have to accept this flakiness.\n\n> We can check the value of that byte with [^0] and interpret a\n> match as failure, but that adds negation and makes the test more\n> complex.\n>\n> ^0*$ would falsely match if the 4097th byte (and possibly later\n> ones) is 0.  We need to make sure we check for end-of-line after\n> the 4096th byte, not later.\n\nI do not have a strong objection against \"^0{64}{64}$\", but let me\nmake sure that I understand your rationale correctly.\n\nWe assume that we do not have an unmapped guard page to reliably\ntrap us.  So \"^0{64}{64}$\" will report a false success when that\n4097th byte is either NUL or LF.  There is 2/256 probability of that\nhappening but we accept it.\n\nA pattern \"0$\" will give us a false success in the same case, but\nthe reason why it is worse is because in addition, we get a false\nsuccess if that second page begins with \"0\\0\" or \"0\\n\".  The chance\nof that happening is additional 2/256 * 1/256.  Worse yet, the page\ncould start with \"00\\0\" or \"00\\n\", which is additional 2/256 *\n1/65536.  We could have yet another \"0\" at the beginning of that\nsecond page, which only increases the chance of us getting a false\nsucess.\n\nWe consider that 2/256 * (1/256 + 1/256^2 + 1/256^3 + ...) is too\nbig an additional chance of getting false success to be acceptable,\neven though 2/256 which is the chance of false success that we have\nto and are willing to accept.\n\nNow I am not good at doing math on the keyboard and text terminal,\nbut\n\n    X    = (1/256 + 1/256^2 + ...)\n    256X = 1 + X\n    X    = 1/255\n\nso that additional rate of false success is 2/256 * 1/255.\n\nSo we are saying that we accept ~1/100 false success rate, but\nadditional ~1/30000 is unacceptable.\n\nI do not know if I buy that argument, but I do think that additional\nfalse success rate, even if it is miniscule, is unnecessary.  So as\nlong as everybody's regexp library is happy with \"^0{64}{64}$\",\nlet's use that.\n\nThanks.\n"},{"id":"325966","messageId":"13394372-1494-6650-05ec-0122e02664d3@web.de","threadId":"46537","inReplyTo":"xmqqh8xg7mhy.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-09T17:20:43Z","receivedAt":"2017-08-09T17:20:59Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 18:07 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>>> In the face of unreliable segfaults we need to reverse our strategy,\n>>> I think.  Searching for something not in the buffer (e.g. \"1\") and\n>>> considering matches and segfaults as confirmation that the bug is\n>>> still present should avoid any false positives.  Right?\n>>\n>> And that's not it either. *sigh*\n>>\n>> If the 4097th byte is NUL or LF then we can only hope its access\n>> triggers a segfault -- there is no other way to distinguish the\n>> result from a legitimate match when limiting with REG_STARTEND.  So\n>> we have to accept this flakiness.\n> \n>> We can check the value of that byte with [^0] and interpret a\n>> match as failure, but that adds negation and makes the test more\n>> complex.\n>>\n>> ^0*$ would falsely match if the 4097th byte (and possibly later\n>> ones) is 0.  We need to make sure we check for end-of-line after\n>> the 4096th byte, not later.\n> \n> I do not have a strong objection against \"^0{64}{64}$\", but let me\n> make sure that I understand your rationale correctly.\n> \n> We assume that we do not have an unmapped guard page to reliably\n> trap us.  So \"^0{64}{64}$\" will report a false success when that\n> 4097th byte is either NUL or LF.  There is 2/256 probability of that\n> happening but we accept it.\n> \n> A pattern \"0$\" will give us a false success in the same case, but\n> the reason why it is worse is because in addition, we get a false\n> success if that second page begins with \"0\\0\" or \"0\\n\".  The chance\n> of that happening is additional 2/256 * 1/256.  Worse yet, the page\n> could start with \"00\\0\" or \"00\\n\", which is additional 2/256 *\n> 1/65536.  We could have yet another \"0\" at the beginning of that\n> second page, which only increases the chance of us getting a false\n> sucess.\n\nI demonstrated a lack of logical thinking and now you bring on\nprobabilities!? ;-)\n\nThere could be any characters except NUL and LF between the 4096 zeros\nand \"0$\" for the latter to match wrongly, no?  So there are 4095\nopportunities for the misleading pattern in a page, with probabilities\nlike this:\n\n  0$                          1/256 * 2/256\n  .0$         254/256       * 1/256 * 2/256\n  ..0$       (254/256)^2    * 1/256 * 2/256\n  .{3}0$     (254/256)^3    * 1/256 * 2/256\n\n  .{4094}0$  (254/256)^4094 * 1/256 * 2/256\n\nThat sums up to ca. 1/256 (did that numerically).  Does that make\nsense?\n\n> So we are saying that we accept ~1/100 false success rate, but\n> additional ~1/30000 is unacceptable.\n> \n> I do not know if I buy that argument, but I do think that additional\n> false success rate, even if it is miniscule, is unnecessary.  So as\n> long as everybody's regexp library is happy with \"^0{64}{64}$\",\n> let's use that.\n\nThe parentheses are necessary (\"^(0{64}){64}$\"), at least on OpenBSD.\nIt doesn't accept consecutive repetition operators without them.  We\ncould use \"^(00000000000000000000000000000000){128}$\" instead if\nthere's a problem with that.\n\nRené\n"},{"id":"325972","messageId":"xmqqwp6c63bm.fsf@gitster.mtv.corp.google.com","threadId":"46537","inReplyTo":"13394372-1494-6650-05ec-0122e02664d3@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-09T17:47:25Z","receivedAt":"2017-08-09T17:47:41Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> There could be any characters except NUL and LF between the 4096 zeros\n> and \"0$\" for the latter to match wrongly, no?  So there are 4095\n> opportunities for the misleading pattern in a page, with probabilities\n> like this:\n>\n>   0$                          1/256 * 2/256\n>   .0$         254/256       * 1/256 * 2/256\n>   ..0$       (254/256)^2    * 1/256 * 2/256\n>   .{3}0$     (254/256)^3    * 1/256 * 2/256\n>\n>   .{4094}0$  (254/256)^4094 * 1/256 * 2/256\n>\n> That sums up to ca. 1/256 (did that numerically).  Does that make\n> sense?\n\nYes, thanks.  I think the number would be different for \"^0*$\" (the\nabove is for \"0$\") and moves it down to ~1/30000, but as I said,\nallowing additional false success rate is unnecessary (even if it is\nminiscule enough to be acceptable), so let's take the 64*64 patch.\n\n>> So we are saying that we accept ~1/100 false success rate, but\n>> additional ~1/30000 is unacceptable.\n>> \n>> I do not know if I buy that argument, but I do think that additional\n>> false success rate, even if it is miniscule, is unnecessary.  So as\n>> long as everybody's regexp library is happy with \"^0{64}{64}$\",\n>> let's use that.\n>\n> The parentheses are necessary (\"^(0{64}){64}$\"), at least on OpenBSD.\n\nSorry, what I wrote was merely a typo; the one from you I applied\ndid have the parens so we are good.\n\nThanks.\n"},{"id":"325996","messageId":"alpine.DEB.2.21.1.1708092349220.11175@virtualbox","threadId":"46537","inReplyTo":"CABM=MFLYkVDjpeVKbErbX+szv7_NXre6U_Z_cOtKakcPDR5U3w@mail.gmail.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2017-08-09T21:49:46Z","receivedAt":"2017-08-09T21:49:59Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi all,\n\nOn Wed, 9 Aug 2017, David Coppa wrote:\n\n> On Wed, Aug 9, 2017 at 4:15 PM, René Scharfe <l.s.r@web.de> wrote:\n> > Am 09.08.2017 um 08:15 schrieb René Scharfe:\n> >> Am 09.08.2017 um 07:29 schrieb Junio C Hamano:\n> >>> René Scharfe <l.s.r@web.de> writes:\n> >>>\n> >>>> Am 09.08.2017 um 00:26 schrieb Junio C Hamano:\n> >>>>> ... but in the meantime, I think replacing the test with \"0$\" to\n> >>>>> force the scanner to find either the end of line or the end of the\n> >>>>> buffer may be a good workaround.  We do not have to care how many of\n> >>>>> random bytes are in front of the last \"0\" in order to ensure that\n> >>>>> the regexec_buf() does not overstep to 4097th byte, while seeing\n> >>>>> that regexec() that does not know how long the haystack is has to do\n> >>>>> so, no?\n> >>>>\n> >>>> Our regexec() calls strlen() (see my other reply).\n> >>>>\n> >>>> Using \"0$\" looks like the best option to me.\n> >>>\n> >>> Yeah, it seems that way.  If we want to be close/faithful to the\n> >>> original, we could do \"^0*$\", but the part that is essential to\n> >>> trigger the old bug is not the \"we have many zeroes\" (or \"we have\n> >>> 4096 zeroes\") part, but \"zero is at the end of the string\" part, so\n> >>> \"0$\" would be the minimal pattern that also would work for OBSD.\n> >>\n> >> Thought about it a bit more.\n> >>\n> >> \"^0{4096}$\" checks if the byte after the buffer is \\n or \\0 in the\n> >> hope of triggering a segfault.  On Linux I can access that byte just\n> >> fine; perhaps there is no guard page.  Also there is a 2 in 256\n> >> chance of the byte being \\n or \\0 (provided its value is random),\n> >> which would cause the test to falsely report success.\n> >>\n> >> \"0$\" effectively looks for \"0\\n\" or \"0\\0\", which can only occur\n> >> after the buffer.  If that string is found close enough then we\n> >> may not trigger a segfault and report a false positive.\n> >>\n> >> In the face of unreliable segfaults we need to reverse our strategy,\n> >> I think.  Searching for something not in the buffer (e.g. \"1\") and\n> >> considering matches and segfaults as confirmation that the bug is\n> >> still present should avoid any false positives.  Right?\n> >\n> > And that's not it either. *sigh*\n> >\n> > If the 4097th byte is NUL or LF then we can only hope its access\n> > triggers a segfault -- there is no other way to distinguish the\n> > result from a legitimate match when limiting with REG_STARTEND.  So\n> > we have to accept this flakiness.\n> >\n> > We can check the value of that byte with [^0] and interpret a\n> > match as failure, but that adds negation and makes the test more\n> > complex.\n> >\n> > ^0*$ would falsely match if the 4097th byte (and possibly later\n> > ones) is 0.  We need to make sure we check for end-of-line after\n> > the 4096th byte, not later.\n> >\n> > Sorry, Dscho, I thought we could take a shortcut here, but -- as\n> > you wrote all along -- we can't.\n> >\n> > So how about this?\n> >\n> > -- >8 --\n> > Subject: [PATCH] t4062: use less than 256 repetitions in regex\n> >\n> > OpenBSD's regex library has a repetition limit (RE_DUP_MAX) of 255.\n> > That's the minimum acceptable value according to POSIX.  In t4062 we use\n> > 4096 repetitions in the test \"-G matches\", though, causing it to fail.\n> > Combine two repetition operators, both less than 256, to arrive at 4096\n> > zeros instead of using a single one, to fix the test on OpenBSD.\n> >\n> > Original-patch-by: David Coppa <dcoppa@openbsd.org>\n> > Signed-off-by: Rene Scharfe <l.s.r@web.de>\n> > ---\n> >  t/t4062-diff-pickaxe.sh | 4 +++-\n> >  1 file changed, 3 insertions(+), 1 deletion(-)\n> >\n> > diff --git a/t/t4062-diff-pickaxe.sh b/t/t4062-diff-pickaxe.sh\n> > index 7c4903f497..1130c8019b 100755\n> > --- a/t/t4062-diff-pickaxe.sh\n> > +++ b/t/t4062-diff-pickaxe.sh\n> > @@ -14,8 +14,10 @@ test_expect_success setup '\n> >         test_tick &&\n> >         git commit -m \"A 4k file\"\n> >  '\n> > +\n> > +# OpenBSD only supports up to 255 repetitions, so repeat twice for 64*64=4096.\n> >  test_expect_success '-G matches' '\n> > -       git diff --name-only -G \"^0{4096}$\" HEAD^ >out &&\n> > +       git diff --name-only -G \"^(0{64}){64}$\" HEAD^ >out &&\n> >         test 4096-zeroes.txt = \"$(cat out)\"\n> >  '\n> >\n> > --\n> > 2.14.0\n> \n> I think this should work w/o problems on OpenBSD:\n> \n> $ uname -a\n> OpenBSD open.bsdgeek.it 6.1 GENERIC#54 amd64\n> $ git diff --name-only -G \"^0{4096}$\" HEAD^ 1>/dev/null\n> fatal: invalid regex: invalid repetition count(s)\n> $ git diff --name-only -G \"^(0{64}){64}$\" HEAD^ 1>/dev/null\n> $\n\nPerfect!\n\nThank y'all for being so thorough,\nDscho"},{"id":"326005","messageId":"faa74d6d-90b5-2de1-6478-854d3d52d30e@web.de","threadId":"46537","inReplyTo":"xmqqwp6c63bm.fsf@gitster.mtv.corp.google.com","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"René Scharfe","fromEmail":"l.s.r@web.de","sentAt":"2017-08-10T06:08:20Z","receivedAt":"2017-08-10T06:08:46Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 09.08.2017 um 19:47 schrieb Junio C Hamano:\n> René Scharfe <l.s.r@web.de> writes:\n> \n>> There could be any characters except NUL and LF between the 4096 zeros\n>> and \"0$\" for the latter to match wrongly, no?  So there are 4095\n>> opportunities for the misleading pattern in a page, with probabilities\n>> like this:\n>>\n>>    0$                          1/256 * 2/256\n>>    .0$         254/256       * 1/256 * 2/256\n>>    ..0$       (254/256)^2    * 1/256 * 2/256\n>>    .{3}0$     (254/256)^3    * 1/256 * 2/256\n>>\n>>    .{4094}0$  (254/256)^4094 * 1/256 * 2/256\n>>\n>> That sums up to ca. 1/256 (did that numerically).  Does that make\n>> sense?\n> \n> Yes, thanks.  I think the number would be different for \"^0*$\" (the\n> above is for \"0$\") and moves it down to ~1/30000, but as I said,\n> allowing additional false success rate is unnecessary (even if it is\n> miniscule enough to be acceptable), so let's take the 64*64 patch.\n\nAh, right, now I get your calculation in the email I replied to above.\n\"^0*$\" has a probability of 2/255 to produce false positives.\n\nThanks,\nRené\n"},{"id":"326155","messageId":"xmqq7eya0xvd.fsf@gitster.mtv.corp.google.com","threadId":"46537","inReplyTo":"faa74d6d-90b5-2de1-6478-854d3d52d30e@web.de","subject":"Re: [PATCH] t4062: stop using repetition in regex","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-08-11T18:20:54Z","receivedAt":"2017-08-11T18:21:12Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"René Scharfe <l.s.r@web.de> writes:\n\n> Am 09.08.2017 um 19:47 schrieb Junio C Hamano:\n>> René Scharfe <l.s.r@web.de> writes:\n>> \n>>> There could be any characters except NUL and LF between the 4096 zeros\n>>> and \"0$\" for the latter to match wrongly, no?  So there are 4095\n>>> opportunities for the misleading pattern in a page, with probabilities\n>>> like this:\n>>>\n>>>    0$                          1/256 * 2/256\n>>>    .0$         254/256       * 1/256 * 2/256\n>>>    ..0$       (254/256)^2    * 1/256 * 2/256\n>>>    .{3}0$     (254/256)^3    * 1/256 * 2/256\n>>>\n>>>    .{4094}0$  (254/256)^4094 * 1/256 * 2/256\n>>>\n>>> That sums up to ca. 1/256 (did that numerically).  Does that make\n>>> sense?\n>> \n>> Yes, thanks.  I think the number would be different for \"^0*$\" (the\n>> above is for \"0$\") and moves it down to ~1/30000, but as I said,\n>> allowing additional false success rate is unnecessary (even if it is\n>> miniscule enough to be acceptable), so let's take the 64*64 patch.\n>\n> Ah, right, now I get your calculation in the email I replied to above.\n> \"^0*$\" has a probability of 2/255 to produce false positives.\n\nYes, and that is larger than 2/256 we would have to accept with the\noriginal \"^0{4096}$\" or the updated \"^(0{64}){64}$\" by ~1/30000,\nwhich is unnecessary additional false rate of success.\n\nThanks.\n\n\n\n\n"}]}