[v2,1/3] String: Add overflow tests for strnlen, memchr, and strncat [BZ #27974]

  This commit adds tests for a bug in the wide char variant of the
functions where the implementation may assume that maxlen for wcsnlen
or n for wmemchr/strncat will not overflow when multiplied by
sizeof(wchar_t).

These tests show the following implementations failing on x86_64:

wcsnlen-sse4_1
wcsnlen-avx2

wmemchr-sse2
wmemchr-avx2

strncat would fail as well if it where on a system that prefered
either of the wcsnlen implementations that failed as it relies on
wcsnlen.

Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
---
Some notes:

I only tested this patch (and the subsequent fixes) on a machine that
prefers EVEX.

The fix for wcsnlen-sse2 is possibly invalid. What it does is checks
if the computation is maxlen * sizeof(wchar_t) + s overflows, and if
so just calls wcslen. The rational is that either the end of the
string will be found in readable memory or the user invoked UB by
calling wcsnlen on a string that is not contained in valid memory
and without a maxlen to that will bound it in valid memory.

 string/test-memchr.c  | 39 ++++++++++++++++++++++++---
 string/test-strncat.c | 61 +++++++++++++++++++++++++++++++++++++++++++
 string/test-strnlen.c | 33 +++++++++++++++++++++++
 3 files changed, 130 insertions(+), 3 deletions(-)
  

On Tue, Jun 22, 2021 at 11:20 AM Noah Goldstein <goldstein.w.n@gmail.com> wrote:
>
> This commit adds tests for a bug in the wide char variant of the
> functions where the implementation may assume that maxlen for wcsnlen
> or n for wmemchr/strncat will not overflow when multiplied by
> sizeof(wchar_t).
>
> These tests show the following implementations failing on x86_64:
>
> wcsnlen-sse4_1
> wcsnlen-avx2
>
> wmemchr-sse2
> wmemchr-avx2
>
> strncat would fail as well if it where on a system that prefered
> either of the wcsnlen implementations that failed as it relies on
> wcsnlen.
>
> Signed-off-by: Noah Goldstein <goldstein.w.n@gmail.com>
> ---
> Some notes:
>
> I only tested this patch (and the subsequent fixes) on a machine that
> prefers EVEX.
>
> The fix for wcsnlen-sse2 is possibly invalid. What it does is checks
> if the computation is maxlen * sizeof(wchar_t) + s overflows, and if
> so just calls wcslen. The rational is that either the end of the
> string will be found in readable memory or the user invoked UB by
> calling wcsnlen on a string that is not contained in valid memory
> and without a maxlen to that will bound it in valid memory.
>
>  string/test-memchr.c  | 39 ++++++++++++++++++++++++---
>  string/test-strncat.c | 61 +++++++++++++++++++++++++++++++++++++++++++
>  string/test-strnlen.c | 33 +++++++++++++++++++++++
>  3 files changed, 130 insertions(+), 3 deletions(-)
>
> diff --git a/string/test-memchr.c b/string/test-memchr.c
> index 665edc32af..ce964284aa 100644
> --- a/string/test-memchr.c
> +++ b/string/test-memchr.c
> @@ -65,8 +65,8 @@ do_one_test (impl_t *impl, const CHAR *s, int c, size_t n, CHAR *exp_res)
>    CHAR *res = CALL (impl, s, c, n);
>    if (res != exp_res)
>      {
> -      error (0, 0, "Wrong result in function %s %p %p", impl->name,
> -            res, exp_res);
> +      error (0, 0, "Wrong result in function %s (%p, %d, %zu) -> %p != %p",
> +             impl->name, s, c, n, res, exp_res);
>        ret = 1;
>        return;
>      }
> @@ -91,7 +91,7 @@ do_test (size_t align, size_t pos, size_t len, size_t n, int seek_char)
>      }
>    buf[align + len] = 0;
>
> -  if (pos < len)
> +  if (pos < MIN(n, len))
>      {
>        buf[align + pos] = seek_char;
>        buf[align + len] = -seek_char;
> @@ -107,6 +107,38 @@ do_test (size_t align, size_t pos, size_t len, size_t n, int seek_char)
>      do_one_test (impl, (CHAR *) (buf + align), seek_char, n, result);
>  }
>
> +static void
> +do_overflow_tests (void)
> +{
> +  size_t i, j, len;
> +  const size_t one = 1;
> +  uintptr_t buf_addr = (uintptr_t) buf1;
> +
> +  for (i = 0; i < 750; ++i)
> +    {
> +        do_test (0, i, 751, SIZE_MAX - i, BIG_CHAR);
> +        do_test (0, i, 751, i - buf_addr, BIG_CHAR);
> +        do_test (0, i, 751, -buf_addr - i, BIG_CHAR);
> +        do_test (0, i, 751, SIZE_MAX - buf_addr - i, BIG_CHAR);
> +        do_test (0, i, 751, SIZE_MAX - buf_addr + i, BIG_CHAR);
> +
> +      len = 0;
> +      for (j = 8 * sizeof(size_t) - 1; j ; --j)
> +        {
> +          len |= one << j;
> +          do_test (0, i, 751, len - i, BIG_CHAR);
> +          do_test (0, i, 751, len + i, BIG_CHAR);
> +          do_test (0, i, 751, len - buf_addr - i, BIG_CHAR);
> +          do_test (0, i, 751, len - buf_addr + i, BIG_CHAR);
> +
> +          do_test (0, i, 751, ~len - i, BIG_CHAR);
> +          do_test (0, i, 751, ~len + i, BIG_CHAR);
> +          do_test (0, i, 751, ~len - buf_addr - i, BIG_CHAR);
> +          do_test (0, i, 751, ~len - buf_addr + i, BIG_CHAR);
> +        }
> +    }
> +}
> +
>  static void
>  do_random_tests (void)
>  {
> @@ -221,6 +253,7 @@ test_main (void)
>      do_test (page_size / 2 - i, i, i, 1, 0x9B);
>
>    do_random_tests ();
> +  do_overflow_tests ();
>    return ret;
>  }
>
> diff --git a/string/test-strncat.c b/string/test-strncat.c
> index 2ef917b820..37ea26ea05 100644
> --- a/string/test-strncat.c
> +++ b/string/test-strncat.c
> @@ -134,6 +134,66 @@ do_test (size_t align1, size_t align2, size_t len1, size_t len2,
>      }
>  }
>
> +static void
> +do_overflow_tests (void)
> +{
> +  size_t i, j, len;
> +  const size_t one = 1;
> +  CHAR *s1, *s2;
> +  uintptr_t s1_addr;
> +  s1 = (CHAR *) buf1;
> +  s2 = (CHAR *) buf2;
> +  s1_addr = (uintptr_t)s1;
> + for (j = 0; j < 200; ++j)
> +      s2[j] = 32 + 23 * j % (BIG_CHAR - 32);
> + s2[200] = 0;
> +  for (i = 0; i < 750; ++i) {
> +    for (j = 0; j < i; ++j)
> +      s1[j] = 32 + 23 * j % (BIG_CHAR - 32);
> +    s1[i] = '\0';
> +
> +       FOR_EACH_IMPL (impl, 0)
> +    {
> +      s2[200] = '\0';
> +      do_one_test (impl, s2, s1, SIZE_MAX - i);
> +      s2[200] = '\0';
> +      do_one_test (impl, s2, s1, i - s1_addr);
> +      s2[200] = '\0';
> +      do_one_test (impl, s2, s1, -s1_addr - i);
> +      s2[200] = '\0';
> +      do_one_test (impl, s2, s1, SIZE_MAX - s1_addr - i);
> +      s2[200] = '\0';
> +      do_one_test (impl, s2, s1, SIZE_MAX - s1_addr + i);
> +    }
> +
> +    len = 0;
> +    for (j = 8 * sizeof(size_t) - 1; j ; --j)
> +      {
> +        len |= one << j;
> +        FOR_EACH_IMPL (impl, 0)
> +          {
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, len - i);
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, len + i);
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, len - s1_addr - i);
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, len - s1_addr + i);
> +
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, ~len - i);
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, ~len + i);
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, ~len - s1_addr - i);
> +            s2[200] = '\0';
> +            do_one_test (impl, s2, s1, ~len - s1_addr + i);
> +          }
> +      }
> +  }
> +}
> +
>  static void
>  do_random_tests (void)
>  {
> @@ -316,6 +376,7 @@ test_main (void)
>      }
>
>    do_random_tests ();
> +  do_overflow_tests ();
>    return ret;
>  }
>
> diff --git a/string/test-strnlen.c b/string/test-strnlen.c
> index 920f58e97b..f53e09263f 100644
> --- a/string/test-strnlen.c
> +++ b/string/test-strnlen.c
> @@ -89,6 +89,38 @@ do_test (size_t align, size_t len, size_t maxlen, int max_char)
>      do_one_test (impl, (CHAR *) (buf + align), maxlen, MIN (len, maxlen));
>  }
>
> +static void
> +do_overflow_tests (void)
> +{
> +  size_t i, j, len;
> +  const size_t one = 1;
> +  uintptr_t buf_addr = (uintptr_t) buf1;
> +
> +  for (i = 0; i < 750; ++i)
> +    {
> +      do_test (0, i, SIZE_MAX - i, BIG_CHAR);
> +      do_test (0, i, i - buf_addr, BIG_CHAR);
> +      do_test (0, i, -buf_addr - i, BIG_CHAR);
> +      do_test (0, i, SIZE_MAX - buf_addr - i, BIG_CHAR);
> +      do_test (0, i, SIZE_MAX - buf_addr + i, BIG_CHAR);
> +
> +      len = 0;
> +      for (j = 8 * sizeof(size_t) - 1; j ; --j)
> +        {
> +          len |= one << j;
> +          do_test (0, i, len - i, BIG_CHAR);
> +          do_test (0, i, len + i, BIG_CHAR);
> +          do_test (0, i, len - buf_addr - i, BIG_CHAR);
> +          do_test (0, i, len - buf_addr + i, BIG_CHAR);
> +
> +          do_test (0, i, ~len - i, BIG_CHAR);
> +          do_test (0, i, ~len + i, BIG_CHAR);
> +          do_test (0, i, ~len - buf_addr - i, BIG_CHAR);
> +          do_test (0, i, ~len - buf_addr + i, BIG_CHAR);
> +        }
> +    }
> +}
> +
>  static void
>  do_random_tests (void)
>  {
> @@ -283,6 +315,7 @@ test_main (void)
>    do_random_tests ();
>    do_page_tests ();
>    do_page_2_tests ();
> +  do_overflow_tests ();
>    return ret;
>  }
>
> --
> 2.25.1
>

LGTM.

Reviewed-by: H.J. Lu <hjl.tools@gmail.com>

Thanks.