[C-prog-lang-l] array bounds checking

[Vladimír Kotal]

Hi all,

as some of you noticed, for the simple(r) cases, the static analyzers built into the modern compilers can detect out of bounds array access at compile time. For cases where the array indices are determined during run time and thus the static analysis falls short, there is another possibility - the Undefined Behavior Saniziter (https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html - UBSan in short). It's a runtime checker built into recent versions of GCC and Clang. 

Here's the UBSan in action on Intel macOS using https://github.com/devnull-cz/c-prog-lang/blob/master/src/array-out-of-bounds.c :

$ clang -O1 -g -fno-omit-frame-pointer -fsanitize=undefined -Wall -Werror -Wextra -pedantic -std=c99    array-out-of-bounds.c   -o array-out-of-bounds

$ ./array-out-of-bounds
Number of array elements: 1024
One-off error (using index 1024)... array-out-of-bounds.c:19:2: runtime error: index 1024 out of bounds for type 'int [1024]'
array-out-of-bounds.c:19:2: runtime error: store to address 0x7ffeedb549c0 with insufficient space for an object of type 'int'
0x7ffeedb549c0: note: pointer points here
00 00 00 00  64 00 84 ff fe 04 2b 9d  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
              ^
OK
Assigning to index 4096... array-out-of-bounds.c:23:2: runtime error: index 4096 out of bounds for type 'int [1024]'
array-out-of-bounds.c:23:2: runtime error: store to address 0x7ffeedb579c0 with insufficient space for an object of type 'int'
0x7ffeedb579c0: note: pointer points here
<memory cannot be printed>
UndefinedBehaviorSanitizer:DEADLYSIGNAL
==43790==ERROR: UndefinedBehaviorSanitizer: stack-overflow on address 0x7ffeedb579c0 (pc 0x0001020abde9 bp 0x7ffeedb549e0 sp 0x7ffeedb539c0 T4486364)
    #0 0x1020abde8 in main array-out-of-bounds.c:23

==43790==ABORTING
Abort trap: 6


One can use various environment variables to influence output gathering and checks made, for example:

UBSAN_OPTIONS=print_stacktrace=1 UBSAN_OPTIONS=log_path=/tmp/ubsan.txt

will print the backtrace for each problem (handy if there is non trivial calling stack involved) and log the output to a file (handy for automated checks and/or if there are lot of problems detected).

UBSan works by modifying the resulting binary by adding a check before each array access operation (see the 'objdump --disassemble=<symbol>' on Linux boxes with and without UBSan - basically the check is fed the information about the array and the index to be accessed before the actual operation happens). If the check fails, a warning is reported, otherwise the program behaves as before. That said, the array-out-of-bounds program when compiled and run on the Linux machines in Mala Strana lab, does not crash by default:

u-pl3:~/c-prog-lang.git/src$ rm array-out-of-bounds
u-pl3:~/c-prog-lang.git/src$ make array-out-of-bounds
gcc -Wall -Werror -Wextra -pedantic -std=c99    array-out-of-bounds.c   -o array-out-of-bounds
u-pl3:~/c-prog-lang.git/src$ ./array-out-of-bounds
Number of array elements: 1024
One-off error (using index 1024)... OK
Assigning to index 4096... OK
u-pl3:~/c-prog-lang.git/src$ echo $?
0


however when compiled with UBSan, it starts crashing on the second out of bounds arrray access (likely due to memory landscape change):

u-pl3:~/c-prog-lang.git/src$ gcc -O1 -g -fno-omit-frame-pointer -fsanitize=undefined -Wall -Werror -Wextra -pedantic -std=c99    array-out-of-bounds.c   -o array-out-of-bounds
u-pl3:~/c-prog-lang.git/src$ ./array-out-of-bounds
Number of array elements: 1024
One-off error (using index 1024)... array-out-of-bounds.c:19:3: runtime error: index 1024 out of bounds for type 'int [1024]'
array-out-of-bounds.c:19:11: runtime error: store to address 0x7ffef3764b60 with insufficient space for an object of type 'int'
0x7ffef3764b60: note: pointer points here
e1 55 00 00  60 4c 76 f3 fe 7f 00 00  00 cd 8f a8 cf d5 cb 67  00 00 00 00 00 00 00 00  7d 48 ec 8f
              ^
OK
Assigning to index 4096... array-out-of-bounds.c:23:3: runtime error: index 4096 out of bounds for type 'int [1024]'
array-out-of-bounds.c:23:16: runtime error: store to address 0x7ffef3767b60 with insufficient space for an object of type 'int'
0x7ffef3767b60: note: pointer points here
<memory cannot be printed>
Segmentation fault (core dumped)


Might be good idea to include this when building and testing your programs. Of course, it depends on test coverage of given program - if the code does not get run, the problem therein cannot be detected with UBSan.

This is just one of tools available, there are more possibilities. Also, can be combined with other tools (defense in depth).


Best regards,


V. Kotal


-------------- next part --------------
HTML attachment scrubbed and removed