Recommended way to track down array out-of-bound access/write in C program

Question

Consider writing implementation for some not-so-obvious algorithm in C. For example let it be recursive quicksort, that I have found in K. N. King's "C Programming: A Modern Approach, 2nd Edition" book, that it's available from here. The most interesting part consist of two following definitions:

void quicksort(int a[], int low, int high) {     int middle;      if (low >= high)         return;      middle = split(a, low, high);     quicksort(a, low, middle - 1);     quicksort(a, middle + 1, high); }  int split(int a[], int low, int high) {     int part_element = a[low];      for (;;) {        while (low < high && part_element <= a[high])            high--;        if (low >= high)            break;        a[low++] = a[high];         while (low < high && a[low] <= part_element)            low++;        if (low >= high)            break;        a[high--] = a[low];     }      a[high] = part_element;     return high; } 

Both while loops can be optimized by removing low < high tests:

for (;;) {     while (part_element < a[high])         high--;     if (low >= high)         break;     a[low++] = a[high];     a[high] = part_element;      while (a[low] <= part_element)         low++;     if (low >= high)         break;     a[high--] = a[low];     a[low] = part_element; } 

What is the recommended way to make sure that every access or write to array (allocated on stack) is actually valid (i.e. not provoking undefined behaviour) ? What I already tried is to:

• manually debug with gdb on some actual data
• pass source code to static analysis tools like split or cppcheck
• valgrind with --tool=exp-sgcheck switch

For example having five elements array {8, 1, 2, 3, 4}:

#define N 5  int main(void) {     int a[N] = {8, 1, 2, 3, 4}, i;      quicksort(a, 0, N - 1);      printf("After sort:");     for (i = 0; i < N; i++)         printf(" %d", a[i]);     putchar('\n');      return 0; } 

Result is (most certainly it's implemention dependent):

After sort: 1 1 2 4 8 

1. GDB

(gdb) p low $1 = 3 (gdb) p high $2 = 4 (gdb) p a[low] $3 = 1 (gdb) p part_element $4 = 8 (gdb) s 47              low++; (gdb) s 46          while (a[low] <= part_element) (gdb) s 47              low++; (gdb) s 46          while (a[low] <= part_element) (gdb) p low $5 = 5 (gdb) p high $6 = 4 (gdb) bt full #0  split (a=0x7fffffffe140, low=5, high=4) at qsort.c:46         part_element = 8 #1  0x00000000004005df in quicksort (a=0x7fffffffe140, low=0, high=4) at qsort.c:30         middle = <value optimized out> #2  0x0000000000400656 in main () at qsort.c:14         a = {4, 1, 2, 1, 8}         i = <value optimized out> 

As you see low variable went outside boundary:

(gdb) p low $5 = 5 

2. Static analysis tools

$ splint -retvalint -exportlocal qsort.c  Splint 3.1.2 --- 07 Feb 2011  Finished checking --- no warnings  $ cppcheck qsort.c  Checking qsort.c... 

3. Valgrind with --tool=exp-sgcheck

$ valgrind --tool=exp-sgcheck ./a.out  ==5480== exp-sgcheck, a stack and global array overrun detector ==5480== NOTE: This is an Experimental-Class Valgrind Tool ==5480== Copyright (C) 2003-2012, and GNU GPL'd, by OpenWorks Ltd et al. ==5480== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info ==5480== Command: ./a.out ==5480==  ==5480== Invalid read of size 4 ==5480==    at 0x4005A0: split (qsort.c:46) ==5480==    by 0x4005DE: quicksort (qsort.c:30) ==5480==    by 0x400655: main (qsort.c:14) ==5480==  Address 0x7ff000114 expected vs actual: ==5480==  Expected: stack array "a" of size 20 in frame 2 back from here ==5480==  Actual:   unknown ==5480==  Actual:   is 0 after Expected ==5480==  After sort: 1 1 2 4 8 ==5480==  ==5480== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0) 

The location at 0x4005A0: split (qsort.c:46) is matching to the same place as I found by gdb manually.