<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Jan 2, 2023 at 11:20 AM Rob Landley <<a href="mailto:rob@landley.net">rob@landley.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">On 1/1/23 18:06, Ray Gardner wrote:<br>
> Some questions and comments on the memcmp() issue from the 2022-12-23 notes.html<br>
> entry.<br>
> <br>
> I suspect that memcmp("a", "abc", 4); is a simplified version of the actual case<br>
> that caused an issue with ASAN.<br>
<br>
Yes, but the simplified version triggered gcc/glibc's ASAN for me.<br>
<br>
> What was the actual case like?<br>
<br>
toys/*/sh.c line 3080-ish:<br>
<br>
// "for" on its own line is an error.<br>
if (arg->c == 1 && ex && !memcmp(ex, "do\0A", 4)) {<br>
s = "newline";<br>
goto flush;<br>
}<br>
<br>
There are multiple "do" cases that need to match the keyword to trigger parser<br>
state advancement, but they have an extra byte appended after the NUL to<br>
distinguish while/do for/do select/do when the parser uses the entry on the top<br>
of the stack to determine parsing context. We expect a "do" statement to end<br>
this, but "for ((a;b;c;)); do" is very different from "while true; do".<br>
<br>
The ex = *expect ? (*expect)->prev->data : 0; it's comparing against is the<br>
string constant that actually got pushed onto the expect stack this time around:<br>
<br>
(*expect)->prev->data = "do\0C";<br>
dlist_add(expect, (*s == 'c') ? "esac" : "do\0A");<br>
<br>
end = 0;<br>
if (!strcmp(s, "if")) end = "then";<br>
else if (!strcmp(s, "while") || !strcmp(s, "until")) end = "do\0B";<br>
else if (!strcmp(s, "{")) end = "}";<br>
else if (!strcmp(s, "(")) end = ")";<br>
else if (!strcmp(s, "[[")) end = "]]";<br>
<br>
dlist_add(expect, end);<br>
<br>
And so on. Any string constant starting with "do" will have a fourth byte, and<br>
any other string constant is going to diverge within the bounds of the actual<br>
string constant so we're _going_ to hit inequality before falling off the end.<br></blockquote><div><br></div><div>isn't your function _strncmp()_ rather than memcmp() though?</div><div><br></div><div>even though one _could_ write a byte-by-byte memcmp(), the standard does not require that, and i'm aware of no non-C implementation that works that way. (musl may have misled you here? strictly BSD also has a memcmp.c that's byte-by-byte, but all the real architectures have assembler versions they use instead.)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> Was part of<br>
> either buffer in unallocated memory? If so, could that memory be accessed in<br>
> some other scenario?<br>
<br>
If compile time string constants become unallocated there's something wrong with<br>
the ELF loader or we did something really FUNKY with mmap()...<br>
<br>
> xmemcmp() doesn't do the same thing as memcmp(). memcmp() compares char as<br>
> unsigned, and xmemcmp uses plain char *, so if plain char is signed by<br>
> default, xmemcmp will return the opposite "sense" from memcmp for e.g.<br>
> xmemcmp("0xF0", "a", 2).<br>
<br>
<a href="https://landley.net/toybox/design.html:#:~:text=Signedness%20of%20char" rel="noreferrer" target="_blank">https://landley.net/toybox/design.html:#:~:text=Signedness%20of%20char</a><br>
<br>
<a href="https://github.com/landley/toybox/blob/master/configure#L16" rel="noreferrer" target="_blank">https://github.com/landley/toybox/blob/master/configure#L16</a></blockquote><div><br></div><div>my confusion with the xmemcmp() name is (a) that this isn't really a memcmp() because you want to guarantee that you don't read past a mismatch [because it might be a NUL because you're actually dealing with strings], and (b) that everywhere (?) else in toybox the leading `x` means "or exit". which this doesn't do.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
> Easy fix is to use<br>
> <br>
> while (len--) if ((ii = *(unsigned char *)one++ - *(unsigned char *)two++)) break;<br>
> <br>
> It appears memcmp() is only used for equality testing now, but if you leave<br>
> xmemcmp() unchanged it could cause trouble later if it's used for<br>
> less/equal/greater comparison.<br>
> <br>
> As for ASAN, you can disable the catching of memcmp.<br>
<br>
Android has a test suite they need stuff to pass to sleep at night. I don't have<br>
to agree with it, I can add compliance stuff to make them happy.<br>
<br>
Every checker throws the occasional false positive. ASAN is far far far less<br>
annoying than any static checker I've ever tried to use. Compared to the years I<br>
spent arguing with gcc's "is never actually used uninitialized" warnings, this<br>
is a rounding error.<br>
<br>
> I know nothing of toybox or<br>
> linux or ASAN, so I may be off base here,<br>
<br>
The design page linked above is a bit verbose, but I dunno how to make it<br>
shorter and still say enough stuff. I need to do a refresh pass on<br>
<a href="https://landley.net/code.html" rel="noreferrer" target="_blank">https://landley.net/code.html</a> (which was never actually _finished_, but the<br>
project's a moving target).<br>
<br>
> No ASAN memcmp testing is done if intercept_memcmp is 0.<br>
<br>
Leaving aside "I already fixed it" and instances like<br>
<a href="https://github.com/landley/toybox/commit/472599b99bec" rel="noreferrer" target="_blank">https://github.com/landley/toybox/commit/472599b99bec</a> where I may grumble but I<br>
do actually check in even completely useless changes to mollify the sanitizer,<br>
in this case the chance of an actual bug is nonzero. (Merely astronomically small.)<br>
<br>
Bionic does seem to do the "optimized" version where it's doing word sized<br>
reads. Well, MAYBE it isn't here because libc/arch-arm/generic/bionic/memcmp.S has:<br>
<br>
/* make sure we have at least 8+4 bytes, this simplify things below<br>
* and avoid some overhead for small blocks<br>
*/<br>
cmp r2, #(8+4)<br>
bmi 10f<br></blockquote><div><br></div><div>yeah, all our many memcmps will do the largest reads they can. so arm64 will start with 16 bytes/load but get down to 1 if it needs to. but that 4 would mean it wouldn't do less than a 4-byte load. (you'd have gotten the behavior you were hoping for if your constant had been 3 though!)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
But I up for tracing the flow of assembly that uses hexadecimal constants for<br>
its jumps. (Checking in generated code is technical debt even _before_ you<br>
hand-modify it.)<br>
<br>
But assuming it's doing word sized reads even when presented with unaligned<br>
input, it _is_ theoretically possible that somebody could use the FDPIC loader<br>
for security reasons on a system with MMU (it's ASLR on steroids, the security<br>
nuts who pull that sort of thing tend not to talk about it), and if our shorter<br>
constant is the last entry in the entire rodata segment (I dunno how llvm/lld<br>
orders rodata entries) and the last page is exactly full, and the string we're<br>
comparing against is "{" (3 bytes), you could theoretically have the word sized<br>
read go up to two bytes off the end and fault.<br>
<br>
Android shipping billions of devices with half a gig of DRAM and no ECC memory<br>
is statistically going to cause WAY more problems than that, but sure. I can use<br>
a version that _explicitly_ does byte at a time comparisons.<br>
<br>
> Not sure if turning off<br>
> strict_memcmp will shut up the error you encountered,<br>
<br>
But that's not their test.<br></blockquote><div><br></div><div>indeed. not least because we use hwasan :-)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
> but it does for the case<br>
> above. You can also compile the options into the source (see<br>
> <a href="https://github.com/google/sanitizers/wiki/AddressSanitizerFlags" rel="noreferrer" target="_blank">https://github.com/google/sanitizers/wiki/AddressSanitizerFlags</a><br>
><br>
> const char *__asan_default_options() {<br>
> return "intercept_memcmp=1:strict_memcmp=0";<br>
> }<br>
<br>
I posted here christmas eve about how I had to do that to shut off the memory<br>
leak detector, because gcc was ignoring the environment variable.<br>
<br>
> ASAN may be overly paranoid with strict_memcmp, but I think it's looking (with<br>
> strict) to see if any of the two buffers fall in unallocated (or even just<br>
> uninitialized? how would it know?) memory.<br>
<br>
It cares that we go off the end of a string constant. At a guess it's putting a<br>
guard byte between each one and marking that byte poisoned in the funky shadow<br>
map thing?<br></blockquote><div><br></div><div>aiui, yes, asan goes out of its way to make the "highly improbable" easily reproducible. (because, yes, when the _visible_ part of your ecosystem is 3bn users [and you can't even see the rest of the iceberg], unlikely shit happens daily. best to catch it before it ships!)</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Note that it triggered on gcc with glibc, and I haven't looked at glibc's memcmp<br>
source because gnu and gplv3 and ew. But also because it doesn't matter because<br>
I dunno what implementation they'll switch to in future, and in THEORY doing<br>
readahead is always a possibility (Bionic's neon version claims to be abusing<br>
the FPU to do 32 _byte_ comparisons), and in THEORY you could fall off the edge<br>
of a segment doing that.<br></blockquote><div><br></div><div>for arm64, the SVE memcmp() will load as many bytes as your vector size :-) interestingly, there seem to be new instructions for non-faulting loads, specifically so you can do this kind of thing: <a href="https://developer.arm.com/documentation/ddi0596/2021-12/SVE-Instructions/LDNF1B--Contiguous-load-non-fault-unsigned-bytes-to-vector--immediate-index--">https://developer.arm.com/documentation/ddi0596/2021-12/SVE-Instructions/LDNF1B--Contiguous-load-non-fault-unsigned-bytes-to-vector--immediate-index--</a></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Rob<br>
_______________________________________________<br>
Toybox mailing list<br>
<a href="mailto:Toybox@lists.landley.net" target="_blank">Toybox@lists.landley.net</a><br>
<a href="http://lists.landley.net/listinfo.cgi/toybox-landley.net" rel="noreferrer" target="_blank">http://lists.landley.net/listinfo.cgi/toybox-landley.net</a><br>
</blockquote></div></div>