Re: Bug 29863 - Segmentation fault in memcmp-sse2.S if memory contents can concurrently change

[Alejandro Colomar <alx.manpages@gmail.com>]

Hi Zack,

On 12/29/22 08:21, Zack Weinberg via Libc-alpha wrote:
> On Wed, 14 Dec 2022 16:56:28 -0500, Wilco Dijkstra wrote:
>> I'd expect that mem* functions will never read outside their bounds
>> since the bounds are explicitly defined by the arguments, not by the
>> data. So that should be easy to guarantee.
> 
> I concur.
> 
>> For the str* functions it may be harder since the data itself
>> defines when to stop reading.  So if an implementation uses multiple
>> accesses to the same address, you could potentially mistake the end
>> of a string (eg. first one detects a special case, while the 2nd
>> then verifies it).
> 
> I also concur here.
>   
>> Still, I wouldn't expect totally random memory accesses even in this
>> case - you would read beyond the end of a string if the string end
>> is changed concurrently.
> 
> We may run into a problem where it’s difficult to _state_ the limits
> of the misbehavior, just because the C standard doesn’t itself try to
> put limits on misbehavior in the face of an incorrect program, so we
> don’t have any language for it (which I would argue is a bug in the
> standard, see the detailed reply to Carlos that I’ll be writing, er,
> tomorrow).

The standard already makes some kind of guarantee, when it differences between 
bound UB and critical UB.  The problem is that once you've met bound UB, it's 
hard not to convert it to critical UB in the following lines of code.  Even a 
compiler assumption that would otherwise be fine might result in critical UB.

> 
> Still, taking strcmp(a, b) for example, and assuming WLOG a flat
> address space in which a < b, it should be possible to guarantee
> 
>   - no accesses to any byte in the range [0, a) ever
>   - if an oracle for strlen(), capable of executing in zero cycles,
>     would return the same value for strlen(a) throughout the execution
>     of strcmp(), then no accesses to any byte in the range
>     [a+strlen(a), b)
>   - if an oracle for strlen(), capable of executing in zero cycles,
>     would return the same value for strlen(b) throughout the execution
>     of strcmp(), then no accesses to any byte in the range
>     [b+strlen(b), ADDR_MAX)
>   - however, if the oracle strlen() values _do_ change during the
>     execution of strcmp(), then accesses to bytes in the latter two
>     ranges are possible
>   - a SIGSEGV is permissible if and only if there was at least one
>     point during execution at which a call to the oracle strlen() would
>     have triggered a SIGSEGV

Are you meaning this would be an invalid implementation of strcmp(3)?:

int
strcmp(const char *s1, const char *s2)
{
	for (; *s1 != '\0' || *s1 != '\0'; s1++, s2++) {
		if (*s1 < *s2)
			return -1;
		if (*s1 > *s2)
			return 1;
	}
}

Okay, probably it's not the fastest one, but it's simple.  This one would 
SIGSEGV in the following case:

Another thread might insert a NUL at the beginning of each string (after the 
loop has passed over it), and in the next cycle remove the 
previously-terminating NUL from the strings.  The loop would then run forever, 
until a crash.

Cheers,

Alex

> 
> Ne?
> 
>> Finally it's worth mentioning that nscd does the exact same thing:
>> it uses memcmp and non-atomic accesses on shared data that is being
>> modified by other threads. It looks totally broken, especially with
>> weaker memory ordering, however this kind of insanity may actually
>> be a common design pattern...
> 
> I don’t want to hold up nscd as an example of quality design or
> implementation, but yeah, I share your concern re “may actually be a
> common design pattern”…
> 
> zw