bug in optimised strstr

[Jeff Johnston]

Eric Blake wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> According to Sam Clegg on 10/2/2008 2:41 AM:
>   
>> I think there is bug in the current strstr implementation.  I initially
>> found this in the codesourcery distribution and have recently reproduced
>> it using newlib form CVS on both arm and x86 platforms.  Here is the
>> repro case:
>>
>>     const char* s1 = "GL_OES_byte_coordinates GL_OES_compressed_paletted_texture GL_OES_fixed_point GL_OES_point_size_array GL_OES_point_sprite GL_OES_read_format GL_OES_single_precision GL_IMG_texture_compression_pvrtc GL_IMG_texture_env_enhanced_fixed_function GL_ARB_texture_env_combine GL_ARB_texture_env_dot3 GL_IMG_user_clip_planes GL_OES_matrix_get GL_IMG_vertex_program GL_EXT_multi_draw_arrays GL_OES_matrix_palette GL_OES_draw_texture ";
>>     const char* s2 = "GL_IMG_texture_compression_pvrtc";
>>     const char* res = strstr(s1, s2);  // crash in critical_factorization
>>     
>
> Thanks for the test case.  I wrote that implementation of strstr earlier
> this year, and it is in use in both newlib and m4 1.4.11 (among other
> places).  I could not quickly confirm the crash using m4 1.4.11 (I got the
> expected answer of s1+165), but I'll continue looking into the matter
> (perhaps there is a subtle bug in newlib not present in m4's version).
>
>   
>> This bug seems to have been in newlib for a long time.
>>     
>
> Do you have a stack trace?  If so, which line of critical_factorization is
> crashing?  That implementation was only submitted around Jan or Feb of
> this year; did the previous implementation crash?  If the crash is truly
> in critical_factorization, then you should see it for almost any s1 that
> is longer than s2 (critical_factorization only operates on s2).  Is the
> bug also present in memmem or strcasestr, which also use
> critical_factorization?
>
>   

Don't bother Sam....

  max_suffix = SIZE_MAX;
  j = 0;
  k = p = 1;
  while (j + k < needle_len)
    {
      a = CANON_ELEMENT (needle[j + k]);
      b = CANON_ELEMENT (needle[max_suffix + k]);

it is the line b=....

It cannot be correct as you are trying to reference SIZE_MAX + 1 the 
first time through the loop.

-- Jeff J.