* Out-of-bounds read in twobyte_memmem
@ 2017-06-29 13:37 Leah Neukirchen
2017-06-29 21:35 ` [RFC PATCH] fix OOB reads in Xbyte_memmem Alexander Monakov
0 siblings, 1 reply; 4+ messages in thread
From: Leah Neukirchen @ 2017-06-29 13:37 UTC (permalink / raw)
To: musl
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* [RFC PATCH] fix OOB reads in Xbyte_memmem
2017-06-29 13:37 Out-of-bounds read in twobyte_memmem Leah Neukirchen
@ 2017-06-29 21:35 ` Alexander Monakov
2017-06-29 21:48 ` Rich Felker
2017-07-10 18:11 ` Alexander Monakov
0 siblings, 2 replies; 4+ messages in thread
From: Alexander Monakov @ 2017-06-29 21:35 UTC (permalink / raw)
To: musl
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC PATCH] fix OOB reads in Xbyte_memmem
2017-06-29 21:35 ` [RFC PATCH] fix OOB reads in Xbyte_memmem Alexander Monakov
@ 2017-06-29 21:48 ` Rich Felker
2017-07-10 18:11 ` Alexander Monakov
1 sibling, 0 replies; 4+ messages in thread
From: Rich Felker @ 2017-06-29 21:48 UTC (permalink / raw)
To: musl
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
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: [RFC PATCH] fix OOB reads in Xbyte_memmem
2017-06-29 21:35 ` [RFC PATCH] fix OOB reads in Xbyte_memmem Alexander Monakov
2017-06-29 21:48 ` Rich Felker
@ 2017-07-10 18:11 ` Alexander Monakov
1 sibling, 0 replies; 4+ messages in thread
From: Alexander Monakov @ 2017-07-10 18:11 UTC (permalink / raw)
To: musl
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
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2017-07-10 18:11 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-06-29 13:37 Out-of-bounds read in twobyte_memmem Leah Neukirchen
2017-06-29 21:35 ` [RFC PATCH] fix OOB reads in Xbyte_memmem Alexander Monakov
2017-06-29 21:48 ` Rich Felker
2017-07-10 18:11 ` Alexander Monakov
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).