Program Analysis Tools

We looked at several examples in class.

Dynamic Techniques

###Valgrind MemCheck for memory analyses
Uninitialized values:
With vg1.c as

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

int main(int argc, char** argv) {
  int* a = malloc(10 * sizeof(int));
  a[5] = 0;
  if (a[argc])
    printf("xx\n");
  return 0;
}

clang -g vg1.c
valgrind ./a.out

Allocated Buffer Overflows:
With vg2.c as

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

int main(int argc, char** argv){
  int i;
  int *a = malloc(sizeof(int) * 10);
  if (!a) return -1; /*malloc failed*/
  for (i = 0; i < 11; i++){
    a[i] = i;
  }
  free(a);
  return 0;
}

clang -g vg2.c
valgrind ./a.out

Memory Leaks:
With vg3.c as

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

int main(int argc, char** argv){
  int i;
  int *a;

  for (i=0; i < 10; i++){
    a = malloc(sizeof(int) * 100);
  }
  free(a);
  return 0;
}

clang -g vg3.c
valgrind ./a.out
valgrind --leak-check=full ./a.out

Data Races:
With race.c as

#include <pthread.h>
#include <stdio.h>

int global;

void *
thread1(void *x) {
  global++;
  return NULL;
}

void *
thread2(void *x) {
  global--;
  return NULL;
}

int
main() {
  for (unsigned i = 0; i < 30; ++i) {
    pthread_t t[2];
    pthread_create(&t[0], NULL, thread1, NULL);
    pthread_create(&t[1], NULL, thread2, NULL);
    pthread_join(t[0], NULL);
    pthread_join(t[1], NULL);
    printf("Global was: %d\n", global);
  }
  return 0;
}

clang race.c -g -lpthread -o race
valgrind --tool=helgrind ./race
valgrind --tool=drd ./race

?????:
With vg4.c as

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

int main(int argc, char** argv){
  int i;
  int x =0;
  int a[10];
  for (i = 0; i < 11; i++)
    a[i] = i;
    
  printf("x is %d\n", x);
  return 0;
}

clang -g vg4.c
valgrind ./a.out
It can't handle everything!

?????:
With vg5.c as

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

int main(int argc, char** argv){
  char *str = malloc(10);
  gets(str);
  printf("%s\n",str);
  free(str);

  return 0;
}

clang -g vg5.c
echo abcabc | valgrind ./a.out
echo abcabcabca | valgrind ./a.out
It can't always handle everything!

Clang/GCC Sanitizers

Originally, the sanitizer infrastructure was developed to work within the clang compiler built on top of LLVM. Thankfully, these options are now available for gcc as well. Just replace clang in any of the invocations below with gcc.

MemorySanitizer
clang -g -fsanitize=memory -fno-omit-frame-pointer vg1.c

AddressSanitizer
clang -g -fsanitize=address -fno-omit-frame-pointer vg2.c
clang -g -fsanitize=address -fno-omit-frame-pointer vg3.c
ASAN_OPTIONS="detect_leaks=1" ./a.out
clang -g -fsanitize=address -fno-omit-frame-pointer vg4.c
clang -g -fsanitize=address -fno-omit-frame-pointer vg5.c

Thread Sanitizer
clang race.c -fsanitize=thread -fPIE -pie -g -lpthread -o race

Undefined Behavior
With ub1.c as

#include <limits.h>

int main (void) {
  return INT_MIN / -1;
}

clang -g -fsanitize=undefined ub1.c

With ub2.c as

#include <limits.h>

int main (void) {
  return -INT_MIN;
}

clang -g -fsanitize=undefined ub2.c

With ub3.c as

int main (void) {
  return 0xffff << 16;
}

clang -g -fsanitize=undefined ub3.c

Static Techniques

###Clang Static Analyzer (scan-build) Simply prepend scan-build before the normal build commands:
scan-build clang -g vg5.c
scan-build clang -g vg4.c

scan-build ./configure
scan-build make

Some example results

FindBugs

java -jar $FINDBUGS_HOME/lib/findbugs.jar
Simply add the jar and/or class files through the GUI interface.

CBMC

For a simple comparison with the clang static analyzer:
scan-build vg1.c
cbmc --bounds-check --pointer-check vg1.c
cbmc --bounds-check --pointer-check vg4.c

And showing the pitfalls of loops:
cbmc binsearch.c --function binsearch --bounds-check
cbmc binsearch.c --function binsearch --unwind 6 --bounds-check

See also LLBMC for bounded model checking of programs compiled by clang/LLVM.

Managing False Positives

###Suppression Dynamic analysis tools usually have some mechanism of error suppression. Users can specify suppression criteria, and any warning that matches these criteria can be prevented.

In Valgrind

You can generate suppression criteria for all warnings in an execution via the --gen-suppressions=all option and capture the output using --log-file:
valgrind --gen-suppressions=all --log-file=suppressionfile ./a.out

Edit this file to match only the warnings you recognize as false positives. You can then use the suppression file to avoid warnings in the future.
valgrind --suppressions=suppressionfile ./a.out

In Clang Sanitizers

All Clang Sanitizers support special case lists / blacklists of errors that ought to be suppressed. Given a particular suppression file, the suppressions are used at compile time via the -fsanitize-blacklist= option:
clang -g -fsanitize=address -fsanitize-blacklist=blacklist.txt vg2.c

More information is available here.

In Clang Static Analyzer

The static analyzer learns about potential bugs based on the the analyzed code. Thus, to avoid false positives, you can either add assertions to the code or remove unnecessary statements that imply potentially bad behavior. In more extreme cases, annotations may be helpful.

A more complete description can be found here.