administrivia

hw3 due next Thursday

hw4 out / new lab (talk to staff)

weeks 8 & 9: networking & sockets

today’s plan

memory errors

valgrind

other debugging techniques

(weeks 9 & 10: helgrind, static checkers)

memory errors

out-of-bounds read/write

read before initialization

read/write after free

double free

memory leak

consequences

segfaults: hardware & OS traps

worse, anything can happen

control-flow hijack, code injection, …

hard to find: non-deterministic & unpredictable

why this price: performance & control

what’s correct

safety property: must be true all the time

liveness property: that will eventually be true

bugs: violations of safety & liveness properties

bug reports

false positives: incorrect bug reports

false negatives: missing bug reports

how to detect memory errors

high-level idea: state machine

strawman: two-bit state for every bit

do we have/need per-bit alloc?

shadow memory & registers

V bit: valid-value bit for every bit

A bit: valid-address bit for every byte

overhead:

1 memory byte - 9 shadow bits (8 V and 1 A)

1 register byte - 8 shadow bits (8 V)

two-level table: 4GB address space

primary map - 64KB entries, secondary map - 64KB V & 8KB A

see further readings for 64-bit and optimizations

implementation

how to monitor memory and registers? virtualization

x86 → VEX IR → instrumentation → x86

system calls? model each system call

multiple threads? serialized execution

relate bugs to source code? gcc -g

false positives

when to report bugs: need to reduce false positives

every memory op? delay reporting (e.g., until externally visible)

in glibc? whitelist: glibc-*.supp

false negatives

every path

others? evil.c

adjacent areas from two mallocs

Geoffrey Liu:

+-------------+
|  char *a    |
   ...
|             | <-- a[99]: valgrind doesn't complain
+-------------+
|.............| <-- a[100]: valgrind catches this
|..some non-..|
|..mallocated.|
|....space....|
|.............|
+-------------+
|   char *b   |
   ...          <-- a[500]: valgrind doesn't complain
|             |
+-------------+

q: how would you improve valgrind to address this limitation?

other limitations

high-level bugs?

porting effort

can a buggy program overwrite valgrind’s shadow memory?

bug example from hw2

// HW2: wds->docIDs hash table
// Each entry's key is a docID and the value
// is the "positions" word positions list.
HTIter iter = HashTableMakeIterator(wds->docIDs);
...
HTKeyValue kv;
HTIteratorGet(iter, &kv);
... = NumElementsInHashTable(kv.value);
...
HTIteratorFree(iter);

bug example from last lecture

#include <vector>
#include <iostream>

int main() {
  std::vector<int> a {1, 2, 3};
  for (auto i = a.begin(); i != a.end(); ++i)
    a.push_back(*i);
  for (auto i : a)
    std::cout << i << std::endl;
}

no type information

other memory debugging tools

Linux kernel’s kmemcheck

gdb’s watchpoints

Google’s Address Sanitizer: “gcc -fsanitizer=address”

static checkers from lec 14

more valgrind-based tools

valgrind’s tool suite

week 9: data race detection (helgrind)

privacy leak measurement