Should memchr work with invalid data size?

Should memchr work with invalid data size?

[H.J. Lu]

"main memchr" says

The  memchr()  function  scans  the  initial n bytes of the memory area
pointed to by s for the first instance of c.

But test-memchr.c has

      if (pos < len)
        {
          size_t r = random ();
          if ((r & 31) == 0)
            len = ~(uintptr_t) (p + align) - ((r >> 5) & 31);
          result = (CHAR *) (p + pos + align);
        }

which sets len to some random value, like 18446603336355475958.
Should memchr work with it?


-- 
H.J.

Re: Should memchr work with invalid data size?

[Carlos O'Donell]

On 05/17/2017 06:24 PM, H.J. Lu wrote:
> "main memchr" says
> 
> The  memchr()  function  scans  the  initial n bytes of the memory area
> pointed to by s for the first instance of c.
> 
> But test-memchr.c has
> 
>       if (pos < len)
>         {
>           size_t r = random ();
>           if ((r & 31) == 0)
>             len = ~(uintptr_t) (p + align) - ((r >> 5) & 31);
>           result = (CHAR *) (p + pos + align);
>         }
> 
> which sets len to some random value, like 18446603336355475958.
> Should memchr work with it?

A caller should expect the implementation may read any memory
location from "(char *)s" to "(char *)s + n - 1".

Therefore the above _might_ work depending on the implementation.

Could you please add lots of comments to do_random_tests() and
explain what it's doing and why?

It might have been a valid white-box test to try use a large value
of size_t randomly for an implementation that scans from the front
to back. You would do this kind of testing when looking for overflows.

I would expect an AFL fuzzer might do something similar unless you
constrain it.

-- 
Cheers,
Carlos.

Re: Should memchr work with invalid data size?

[Florian Weimer]

* H. J. Lu:

> "main memchr" says
>
> The  memchr()  function  scans  the  initial n bytes of the memory area
> pointed to by s for the first instance of c.

POSIX is more clear:

| Implementations shall behave as if they read the memory byte by byte
| from the beginning of the bytes pointed to by s and stop at the
| first occurrence of c (if it is found in the initial n bytes).

This language is not found in C99.

> But test-memchr.c has
>
>       if (pos < len)
>         {
>           size_t r = random ();
>           if ((r & 31) == 0)
>             len = ~(uintptr_t) (p + align) - ((r >> 5) & 31);
>           result = (CHAR *) (p + pos + align);
>         }
>
> which sets len to some random value, like 18446603336355475958.
> Should memchr work with it?

In general, the test is invalid, but it might be a valid test for a
specific implementation.

Re: Should memchr work with invalid data size?

[Florian Weimer]

* Florian Weimer:

> * H. J. Lu:
>
>> "main memchr" says
>>
>> The  memchr()  function  scans  the  initial n bytes of the memory area
>> pointed to by s for the first instance of c.
>
> POSIX is more clear:
>
> | Implementations shall behave as if they read the memory byte by byte
> | from the beginning of the bytes pointed to by s and stop at the
> | first occurrence of c (if it is found in the initial n bytes).
>
> This language is not found in C99.
>
>> But test-memchr.c has
>>
>>       if (pos < len)
>>         {
>>           size_t r = random ();
>>           if ((r & 31) == 0)
>>             len = ~(uintptr_t) (p + align) - ((r >> 5) & 31);
>>           result = (CHAR *) (p + pos + align);
>>         }
>>
>> which sets len to some random value, like 18446603336355475958.
>> Should memchr work with it?
>
> In general, the test is invalid, but it might be a valid test for a
> specific implementation.

Ugh, I got that backwards.  The test is unconditionally valid as long
as the byte is found in the allocated part of the buffer.

Re: Should memchr work with invalid data size?

[Andreas Schwab]

On Mai 18 2017, Florian Weimer <fw@deneb.enyo.de> wrote:

> POSIX is more clear:
>
> | Implementations shall behave as if they read the memory byte by byte
> | from the beginning of the bytes pointed to by s and stop at the
> | first occurrence of c (if it is found in the initial n bytes).
>
> This language is not found in C99.

In C11 it has been amended and says basically the same:

"The implementation shall behave as if it reads the characters
sequentially and stops as soon as a matching character is found."

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Should memchr work with invalid data size?

[Adhemerval Zanella]

On 18/05/2017 04:42, Andreas Schwab wrote:
> On Mai 18 2017, Florian Weimer <fw@deneb.enyo.de> wrote:
> 
>> POSIX is more clear:
>>
>> | Implementations shall behave as if they read the memory byte by byte
>> | from the beginning of the bytes pointed to by s and stop at the
>> | first occurrence of c (if it is found in the initial n bytes).
>>
>> This language is not found in C99.
> 
> In C11 it has been amended and says basically the same:
> 
> "The implementation shall behave as if it reads the characters
> sequentially and stops as soon as a matching character is found."
> 
> Andreas.
> 

It was also discussed on BZ#12019 and lead to other bug reports to
actually fixe it on various implementations (BZ#21182, commit 
502697713f4f1, BZ#19387, BZ#20971, BZ#21014, BZ#11230).

As per comment #9 memchr constraints was changed [1] to:

"A number of changes were agreed as follows

Change p1284 lines 42163-42164
In the DESCRIPTION remove "of the object" from

The memchr( ) function shall locate the first occurrence of c (converted
to an unsigned char) in the initial n bytes (each interpreted as unsigned
char) of the object pointed to by s.

In the RETURN VALUE section

The memchr( ) function shall return a pointer to the located byte,
or a null pointer if the byte does not occur in the object.

to
The memchr( ) function shall return a pointer to the located byte,
or a null pointer if the byte is not found.

Add to DESCRIPTION
Implementations shall behave as if they read the memory byte by byte
from the beginning of the bytes pointed to by s and stop at the first
occurrence of c."

So calling memchr with all possible values of size_t is a valid construction.

[1] http://www.opengroup.org/austin/docs/austin_454.txt