Arrays, Part II: Bound Checking

When writing code based on arrays, one of the most common bug is accessing an array out of bounds. Wether this access is a read or a write, it is definitively a bug that should never occur in a program. Writing out of bounds might be a bug difficult to hunt as the program might write to a memory location which will be used later in the code. The bug will only show up when this location is used, sometimes far away from the culprit. During the development of a new code, bound checking is therefore of uttermost importance. Because of the performance penalty it implies, it is usually turned off in the released version of most number crunching algorithms.

In this article, we’ll go through the different tools available in Fortran, C and C++ for bound checking. Note, that all these tools are specific to the implementation and we’ll only focus on the following compilers: gcc/gfortran, Clang and the Intel compilers. We’ll start with the easiest language for bound checking, Fortran, and end with the most painful one, C.

Fortran

Fortran arrays are the easiest to check as they carry information about their size which could be queried with the \(\verb+size+\) function. This information is passed through function calls and implementing a bound checking is straightforward for compilers. Wether the arrays are static, automatic or dynamic, bound checking is just one compiler option away. Here is an example

program main
    implicit none
    
    integer, dimension(1:3) :: x
    
    write (*,*) x(4)
end program main

which could be compiled with gfortran using the following command line.

gfortran -fcheck=bounds main-static.f90 -o main

As the array and the index are static, the error is detected at compile time.

main-static.f90:6.18:

    write (*,*) x(4)
                  1
Warning: Array reference at (1) is out of bounds (4 > 3) in dimension 1

The line and the column of the bug is given to the user.

Dynamic arrays can also be checked for out of bounds access. This time, we use the Intel compiler \(\verb+ifort+\).

program main
    implicit none
    
    integer, allocatable, dimension(:) :: x
    
    allocate(x(1:3))
    write (*,*) x(4)
end program main

We compile our program with

ifort -check bounds -traceback main-dynamic.f90 -o main

and get the following run time error.

forrtl: severe (408): fort: (2): Subscript #1 of the array X has value 4 which is greater than the upper bound of 3

Image              PC                Routine            Line        Source             
main               00000000004048F0  Unknown               Unknown  Unknown
main               0000000000402E68  MAIN__                      7  main-dynamic.f90
main               0000000000402D0E  Unknown               Unknown  Unknown
libc.so.6          00007FBBFE2F5EED  Unknown               Unknown  Unknown
main               0000000000402BF9  Unknown               Unknown  Unknown

How complex your program could be, your bound checking will always be as simple as that in Fortran.

C++

Now is the turn of C++ for which we’ll only discuss bound-checking for containers available in the standard library (formerly known as the STL). These containers are \(\verb+std::array+\) for static arrays and \(\verb+std::vector+\) for dynamic arrays. The C++ standard states that the accessor \(\verb+.at()+\) should be used bound checked access. This workflow is painful for a programmer who wants to develop with bound checking and release without it. It would need a major rewrite of the code before being released. Therefore, most implementations of the standard library provide a way to enable bound checking for the \(\verb+[]+\) operator. On Linux, the default standard library is \(\verb=libstdc++=\) released with the gcc compiler suite and also used by the Intel compiler. On Mac OSX, the default standard library is \(\verb=libc++=\) developed with Clang and used by the Intel compiler on this platform.

With \(\verb=libstdc++=\), one should use the \(\verb+_GLIBCXX_DEBUG+\) keyword to use it. The program

#include <iostream>
#include <vector>

int main (int argc, char const *argv[])
{
    std::vector<double> v(3);
    
    std::cout << v[3] << std::endl;
    return 0;
}

should be compiled with

g++ -std=c++11 -D_GLIBCXX_DEBUG main.cpp -o main

giving the following error on Mac OSX

/usr/local/Cellar/gcc49/4.9.1/lib/gcc/x86_64-apple-darwin13.3.0/4.9.1/include/c++/debug/vector:357:
    error: attempt to subscript container with out-of-bounds index 3, but 
    container only holds 3 elements.

Objects involved in the operation:
sequence "this" @ 0x0x7fff5e4e3280 {
  type = NSt7__debug6vectorIdSaIdEEE;
}
Abort trap: 6

The same option works well with \(\verb+std::array+\).

Unfortunately, the debug mode of \(\verb=libc++=\) is still a work in progress. To turn it on, one should use the \(\verb+_LIBCPP_DEBUG+\) keyword set to 0. But, as of Clang 3.5 (the current status should be available here), \(\verb+std::vector+\) is bound checked whereas \(\verb+std::array+\) is not. The same program compiled with

clang++ -std=c++11 -D_LIBCPP_DEBUG=0 main.cpp -o main

catches the error at run time

vector[] index out of bounds
Abort trap: 6

but nothing happens if you use a static array. One solution is to dig in the standard library and add code to throw an exception when \(\verb+_LIBCPP_DEBUG+\) is set to 0, which is what I use on my development machine.

C

C is probably the worst language to deal with when it comes to bound checking. Most bound checking implementation in this language suffer from: performance and memory overhead, false positive and out of bounds access not detected. Here are the last tools, which are known to be the best available as of 2014. None of them is as good as what is available in Fortran or C++, but they come closer and closer.

Address Sanitizer

Address Sanitizer has been developed at Google and has been used to find many bugs in the Chrome browser. It can check out of bounds access for static and dynamic arrays. The price to pay is that it makes program run 2 times slower and might use up to three times more memory. These numbers are not that bad compared to other tools such as Valgrind which are known to slow down programs by a factor of 10.

Here is a quick explanation on how Address Sanitizer detects out of bound memory access for memory allocated on the heap. To understand how it works, it is essential to get that Address Sanitizer only raises errors for access to memory that has not been allocated. For instance, if  \(\verb+char *+\) pointers \(\verb+a+\) and \(\verb+b+\) have both been allocated 1024 bytes of memory, and \(\verb+a[1500]+\) happens to be in the region of the memory allocated to \(\verb+b+\), no error will be raised. Therefore, this tool only needs to know which part of the memory has been allocated. It relies on the fact that \(\verb+malloc+\) allocates memory at places which are multiples of 8 (it is said that they are 8-bytes aligned). Therefore, if \(\verb+a+\) has been allocated 6 bytes, the chunk of 8 bytes depicted below has the following state: the first 6 bytes are allocated and the last 2 bytes are not.

array-8-bytes

More generally, every chunk of 8 bytes has the following allocation state: the first \(k\) bytes are allocated and the last \(8-k\) are not. As a consequence, there are only 9 allocation states for a chunk of 8 bytes, an information that can easily been stored in a byte as \(9 \leq 2^8=256\). Therefore, Address Sanitizer uses the following trick: for every chunk of 8 bytes beginning at address \(p\), it stores its allocation state at the address \(p/8\). The first \(1/8^{\text{th}}\) of the memory is therefore used for bookkeeping purposes. Every time there is an access to some memory location, the programs checks its memory book to see if it has been allocated or not and raise an error if it is not. Beware of the fact that if you are unlucky and you make an out of bound access to a part of the memory that has been allocated for another array, Address Sanitizer will be unable to detect the error. But most of out of bounds access begin with an access just after the last element, and Address Sanitizer is careful enough not to allocate any memory here. A different strategy, using poisoned memory, is used to detect out of bounds access for arrays on the stack.

Address Sanitizer is available for LLVM/Clang and Gcc. The program

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

int main (int argc, char const *argv[])
{
    int n = 1024;
    int *a = malloc(n * sizeof(int));
  
    printf("%d\n", a[n]);
    return 0;
}

compiled with

clang -g -O1 -fsanitize=address -fno-omit-frame-pointer main.c -o main

gives the following error message when it runs.

...
SUMMARY: AddressSanitizer: heap-buffer-overflow /Users/fayard/Documents/main.c:9 main
...

Information on where the bug is in the source code is available.

As stated before, Address Sanitizer might miss some out of bounds access.

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

int main (int argc, char const *argv[])
{
    int n = 1024;
    int *a = malloc(n * sizeof(int));
    int *b = malloc(n * sizeof(int));
        
    printf("Out of bound access: %d\n", b[n + n / 2]);
    printf("Pointer shift: %ld\n", b - a);
    return 0;
}

This program runs on my machine and the output is

Out of bound access: -1094795586
Pointer shift: -1280

As you can see, the array \(\verb+b+\) is located before the array \(\verb+a+\) and Adress Sanitizer was smart enough not to stick them together as there is a gap of \(1280 – 1024 = 256\) ints in between the 2 arrays. An out of bound access for \(\verb+b+\) just after the last element would have been detected but accessing it way after that ends up in memory allocated for \(\verb+a+\) and remains undetected.

Unfortunately, there is no way for Address Sanitizer to add this gap in a structure made of static arrays. Therefore, the following error

#include "stdio.h"

typedef struct {
    int a[3];
    int b[3];
} struct_of_array;

int main (int argc, char const *argv[])
{
    struct_of_array x;
    
    printf("%d\n", x.a[3]);
    return 0;
}

is not caught by Address Sanitizer when compiled with gcc.

gcc -fsanitize=address main-static-fail.c -o main
Pointer Checker

Intel came with another solution for bound checking in C. It has been marketed under the name Pointer Checker and is closer to what is available within the Fortran language. Every pointer carry along some bounds that are copied when copying pointers, passed to functions and returned from them. Every time the program tries to access the element of an array, the index is checked against those bounds.

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

int main (int argc, char const *argv[])
{
    int n = 1024;
    int *x = malloc(n * sizeof(int));
    
    printf("%d\n", x[n]);
    return 0;
}

Compiled with

icc -g -check-pointers=rw main-static-struc.c -o main

the programs return an error with an indication of the line where it failed.

CHKP: Bounds check error ptr=0x7fff9f2a5edc sz=4 lb=0x7fff9f2a5ed0 ub=0x7fff9f2a5edb loc=0x40087f
Traceback:
    at address 0x40087f in function main
    in file /home/fayard/Documents/pointer-checker/main-static-struc.c line 14
    at address 0x7f2abaf54eed in function __libc_start_main
    in file unknown line 0
    at address 0x4006f9 in function _start
    in file unknown line 0
32554
CHKP Total number of bounds violations: 1

This tool seems to be much reliable than Address Sanitizer and Intel should release Xeon CPUs with special registers for those bounds. The programs should be even faster than today.

Conclusion

Bound checking is of uttermost importance when developing scientific softwares. Once again, Fortran is ahead when it comes to ease of use with a perfect bound checking environment. C++ is quite close if we use the standard library but we should be aware of implementation differences. C is still very dangerous to deal with when is come to memory access, but tools such as Address Sanitizer and Pointer Checker makes the life of C (and C++) developers easier.

Posted in Uncategorized.

Leave a Reply

Your email address will not be published. Required fields are marked *