Memcpy with pointers to overlapping memory

[stevenjohnstone]

Problem found by fuzzing.

Example program:

#include <assert.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

#include <prism.h>

/*
00000000: 2d3e 7d5f 353d 5f35 2c5f 352c            ->}_5=_5,_5,
*/

uint8_t input[] = {
  0x2d, 0x3e, 0x7d, 0x5f, 0x35, 0x3d, 0x5f, 0x35, 0x2c, 0x5f, 0x35, 0x2c
};
unsigned int input_len = 12;

// Cause ASAN to call abort on an error to make
// debugging inside gdb easier
const char* __asan_default_options() {
  return "abort_on_error=1:handle_abort=1";
}


int main(int argc, const char **argv) {
    (void) argc;
    (void) argv;
    pm_parse_success_p(input, input_len, NULL);
    return 0;
}

Build with

clang -Iinclude $(find src -name "*.c") -fsanitize=address -ggdb3 memcpy-overlap.c -o memcpy-overlap

ASAN flags memcpy as working on overlapping ranges:

./memcpy-overlap
=================================================================
==83662==ERROR: AddressSanitizer: memcpy-param-overlap: memory ranges [0x603000001d50,0x603000001d60) and [0x603000001d58, 0x603000001d68) overlap
    #0 0x000103305cb0 in __asan_memcpy.cold.1+0x24 (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x85cb0)
    #1 0x0001032bafc0 in __asan_memcpy+0x1ec (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x3afc0)
    #2 0x0001029f7bb4 in parse_target_implicit_parameter prism.c:13470
    #3 0x000102a2e298 in parse_write prism.c:13728
    #4 0x0001029e7bd8 in parse_expression_infix prism.c:21366
    #5 0x0001029d720c in parse_expression prism.c:22350
    #6 0x0001029c10e8 in parse_statements prism.c:13987
    #7 0x0001029e6360 in parse_expression_prefix prism.c:20837
    #8 0x0001029d6e34 in parse_expression prism.c:22298
    #9 0x0001029c10e8 in parse_statements prism.c:13987
    #10 0x0001029a9cdc in parse_program prism.c:22571
    #11 0x0001029a9aec in pm_parse prism.c:23003
    #12 0x0001029aaa98 in pm_parse_success_p prism.c:23120
    #13 0x000102a781c8 in main memcpy-overlap.c:29
    #14 0x00019c9c9d50  (<unknown module>)

0x603000001d50 is located 0 bytes inside of 32-byte region [0x603000001d50,0x603000001d70)
allocated by thread T0 here:
    #0 0x0001032bd4fc in realloc+0x80 (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x3d4fc)
    #1 0x000102a3e174 in pm_node_list_grow node.c.erb:35
    #2 0x000102a3dda8 in pm_node_list_append node.c.erb:48
    #3 0x000102a1aa38 in parse_variable prism.c:16572
    #4 0x0001029f74ec in parse_variable_call prism.c:16594
    #5 0x0001029dbabc in parse_expression_prefix prism.c:18705
    #6 0x0001029d6e34 in parse_expression prism.c:22298
    #7 0x0001029c10e8 in parse_statements prism.c:13987
    #8 0x0001029e6360 in parse_expression_prefix prism.c:20837
    #9 0x0001029d6e34 in parse_expression prism.c:22298
    #10 0x0001029c10e8 in parse_statements prism.c:13987
    #11 0x0001029a9cdc in parse_program prism.c:22571
    #12 0x0001029a9aec in pm_parse prism.c:23003
    #13 0x0001029aaa98 in pm_parse_success_p prism.c:23120
    #14 0x000102a781c8 in main memcpy-overlap.c:29
    #15 0x00019c9c9d50  (<unknown module>)

0x603000001d58 is located 8 bytes inside of 32-byte region [0x603000001d50,0x603000001d70)
allocated by thread T0 here:
    #0 0x0001032bd4fc in realloc+0x80 (libclang_rt.asan_osx_dynamic.dylib:arm64e+0x3d4fc)
    #1 0x000102a3e174 in pm_node_list_grow node.c.erb:35
    #2 0x000102a3dda8 in pm_node_list_append node.c.erb:48
    #3 0x000102a1aa38 in parse_variable prism.c:16572
    #4 0x0001029f74ec in parse_variable_call prism.c:16594
    #5 0x0001029dbabc in parse_expression_prefix prism.c:18705
    #6 0x0001029d6e34 in parse_expression prism.c:22298
    #7 0x0001029c10e8 in parse_statements prism.c:13987
    #8 0x0001029e6360 in parse_expression_prefix prism.c:20837
    #9 0x0001029d6e34 in parse_expression prism.c:22298
    #10 0x0001029c10e8 in parse_statements prism.c:13987
    #11 0x0001029a9cdc in parse_program prism.c:22571
    #12 0x0001029a9aec in pm_parse prism.c:23003
    #13 0x0001029aaa98 in pm_parse_success_p prism.c:23120
    #14 0x000102a781c8 in main memcpy-overlap.c:29
    #15 0x00019c9c9d50  (<unknown module>)

SUMMARY: AddressSanitizer: memcpy-param-overlap prism.c:13470 in parse_target_implicit_parameter
==83662==ABORTING
[1]    83662 abort      ./memcpy-overlap

Problem appears to be where an item is removed from an array. Should probably replace memcpy with memmove there.

It's possible for this to cause bugs if the libc implementation chooses to copy backwards. If the compiler can prove the src and dst pointers overlap it can use the undefined behaviour to replace memcpy entirely with aggressively optimised inlined code which does unexpected stuff.