APP FAIL due to bug in replace_strstr

[derekbruening]

Pasting from a user on the mailing list: https://groups.google.com/forum/#!topic/drmemory-users/-3D6XCUnnmk

I have found a bug using Dr.Memory in conjunction with mingw-w64.

The strstr( which is replaced by replace_strstr ) function does not return the correct value under certain circumstances.

Here is the minimal test example that reproduces the bug:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int main( void )
{
    const char* test = "xxxA";

    const char* find = strstr( test, "xxA" );
    if( !find )
    {
        puts( "This is a bug!\n" );
    }     

return EXIT_SUCCESS;
}

Compiling with: gcc filename.c without any flags and then running with drmemory as: drmemory a.exe calls the puts function.

Details:

S = arbitrary
x = any character
N = x...xS ( needle )

The strstr function fails if the needle( string to be searched for ) is in the form of x...xS , where x...x is a sequence of at least two identical characters.

The haystack must include the needle, but with at least one additional prefix x. This means haystack must include the sub-string xN.

Examples that fail:
haystack, needle
"xxxxxA", "xxA"
"xxxxxA", "xxxxA"
"PREFIXxxxxxASUFFIX", "xxxxA"

Examples that don't fail:
haystack, needle
"xxA", "xA"
"xxxxxA", "xxxxxA"
"PREFIXxxxxxASUFFIX", "xxxxxA"

Apart from this problem Dr.Memory works beautifully.

Windows 7 32-bit
Dr. Memory version 1.8.1 -- build 0
gcc (i686-win32-sjlj-rev1, Built by MinGW-W64 project) 4.9.2

[derekbruening]

The fix was incorrect. if n==needle we go forward:
hs -= n - 1 - needle; /* backtrack */
Reproducer:
ASSERT_EQ(strstr("xxx", "a"), (char *)NULL);
=>

[ RUN      ] StringTests.strstr
~~Dr.M~~ 
~~Dr.M~~ Error #1: UNADDRESSABLE ACCESS beyond heap bounds: reading 0x03a7173b-0x03a7173c 1 byte(s)
~~Dr.M~~ # 0 replace_strstr                                                            [d:\derek\drmemory\git\src\drmemory\replace.c:684]
~~Dr.M~~ # 1 testing::TestPartResult::ExtractSummary                                   [d:\derek\drmemory\git\src\third_party\googletest\src\gtest-test-part.cc:52]

Ended up breaking Chrome bots:
http://build.chromium.org/p/chromium.memory.fyi/builders/Windows%20Unit%20%28DrMemory%29/builds/619

UNADDRESSABLE ACCESS beyond heap bounds: reading 0x0cc600c4-0x0cc600c5 1 byte(s)
# 0 replace_strstr                                                [e:\b\build\slave\win-builder\drmemory\drmemory\replace.c:694]
# 1 osmesa.dll!ast_declarator_list::hir                           [third_party\mesa\src\src\glsl\ast_to_hir.cpp:2922]
# 2 osmesa.dll!ast_compound_statement::hir                        [third_party\mesa\src\src\glsl\ast_to_hir.cpp:1825]
# 3 osmesa.dll!ast_function_definition::hir                       [third_party\mesa\src\src\glsl\ast_to_hir.cpp:3335]
# 4 osmesa.dll!_mesa_ast_to_hir                                   [third_party\mesa\src\src\glsl\ast_to_hir.cpp:91]
# 5 osmesa.dll!_mesa_glsl_compile_shader                          [third_party\mesa\src\src\mesa\program\ir_to_mesa.cpp:3081]
# 6 osmesa.dll!compile_shader                                     [third_party\mesa\src\src\mesa\main\shaderapi.c:733]
# 7 osmesa.dll!_mesa_CompileShaderARB                             [third_party\mesa\src\src\mesa\main\shaderapi.c:1031]
# 8 gpu.dll!gpu::gles2::Shader::DoCompile                         [gpu\command_buffer\service\shader_manager.cc:85]
Note: refers to 0 byte(s) beyond last valid byte in prior malloc
Note: prev lower malloc:  0x0cc600a8-0x0cc600c4
Note: instruction: cmp    (%eax) $0x00
     else if (strstr(decl->identifier, "__")) {

And others.