* 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).