Out-of-bounds read in twobyte_memmem

Out-of-bounds read in twobyte_memmem

[Leah Neukirchen]

Hello,

As mentioned in #musl, twobyte_memmem in memmem.c does an out of
bounds read to the byte after the final byte of the buffer, when it
updates hw using *++h before checking k.  Similar code in strstr is
unproblematic since there it will only read the NUL terminator.

Proposed solution is to rewrite the for-loop to make control flow
order explicit, but there may be a more idiomatic solution than this:

static char *twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
{
        uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1];
        h++;
        k--;
        for (;;) {
                if (hw == nw) return (char *)h-1;
                if (!--k) return 0;
                hw = hw<<8 | *++h;
        }
        return 0;
}

This bug was detected by @mourais during development of mblaze on
OpenBSD, using MALLOC_OPTIONS=G.

Thanks,
-- 
Leah Neukirchen  <leah@vuxu.org>  http://leah.zone

[RFC PATCH] fix OOB reads in Xbyte_memmem

[Alexander Monakov]

Reported by Leah Neukirchen.
---
Presumably the loops were written that way to get good performance even in
absence of loop unrolling and/or without relying on advanced compiler
optimizations. In that case the manual loop pipelining should be kept as is,
and the solution is to reduce iteration count by one, pushing out one test
into the loop epilogue.

Alexander

 src/string/memmem.c | 18 +++++++++---------
 1 file changed, 9 insertions(+), 9 deletions(-)

diff --git a/src/string/memmem.c b/src/string/memmem.c
index 4be6a310..54a66e46 100644
--- a/src/string/memmem.c
+++ b/src/string/memmem.c
@@ -5,27 +5,27 @@
 static char *twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
 {
 	uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1];
-	for (h++, k--; k; k--, hw = hw<<8 | *++h)
-		if (hw == nw) return (char *)h-1;
-	return 0;
+	for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++)
+		if (hw == nw) return (char *)h-2;
+	return hw == nw ? (char *)h-2 : 0;
 }
 
 static char *threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
 {
 	uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8;
 	uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8;
-	for (h+=2, k-=2; k; k--, hw = (hw|*++h)<<8)
-		if (hw == nw) return (char *)h-2;
-	return 0;
+	for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8)
+		if (hw == nw) return (char *)h-3;
+	return hw == nw ? (char *)h-3 : 0;
 }
 
 static char *fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n)
 {
 	uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3];
 	uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3];
-	for (h+=3, k-=3; k; k--, hw = hw<<8 | *++h)
-		if (hw == nw) return (char *)h-3;
-	return 0;
+	for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++)
+		if (hw == nw) return (char *)h-4;
+	return hw == nw ? (char *)h-4 : 0;
 }
 
 #define MAX(a,b) ((a)>(b)?(a):(b))
-- 
2.11.0

Re: [RFC PATCH] fix OOB reads in Xbyte_memmem

[Rich Felker]

On Fri, Jun 30, 2017 at 12:35:33AM +0300, Alexander Monakov wrote:
> Reported by Leah Neukirchen.
> ---
> Presumably the loops were written that way to get good performance even in

I think they were just written as the simplest possible
"looks-correct" adaptation of the strstr versions of the code. If
they're good it's probably just by luck.

Rich

Re: [RFC PATCH] fix OOB reads in Xbyte_memmem

[Alexander Monakov]

On Fri, 30 Jun 2017, Alexander Monakov wrote:
>  	uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3];
>  	uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3];
                      ^^^^^^^^
Such shifts can invoke UB by shifting 1 into the sign bit. It's easily
amended by making the shift happen in an unsigned type; I'd suggest
something like 'n[0]*1u<<24 | ...' (I've checked that this does not
appear to thwart bswap recognition in GCC)

I assume this would need to be a separate patch, we desired at all.

Alexander