char *buf        = ...;
char *buf_end    = ...;
unsigned int off = /* read from untrusted input */;
if (buf + off >= buf_end)
  return;          /* validate off: buf+off too large*/
if (buf + off < buf)
  return;          /* validate off: overflow, buf+off wrapped around */
/* access buf[0..off-1] */

• C spec: pointer overflow is undefined behavior
  • gcc: buf + off cannot overflow (different from hardware!)
  • gcc: if (buf + off < buf) ⇒ if (false)
• Attack: craft a large off to trigger buffer overflow

Undefined behavior: the spec “imposes no requirements,”
typically for certain arguments to an operation

• Original goal: emit efficient code
• Example: C spec imposes no requirements if program accesses an out-of-bounds pointer (doing so is undefined behavior)
• Compiler: no need to emit bounds checks; assume bug-free code

    *p = 42;         /* store 42 to p */
       
    mov $42, (%rdi)  /* no bounds checks */

• Compilers assume a program never invokes undefined behavior
• if (buf + off < buf) ⇒ if (false) legal: any affected program invoked undefined behavior (by overflowing pointers)

Meaningless checks from real code: pointer p; signed integer x

Unstable code: compilers discard code due to undefined behavior

...
if (p + 100 < p)
  return;



...
nop
nop

• Security checks discarded
• Weakness amplified
• Unpredictable system behavior

• A case study of unstable code in real world
• An algorithm for identifying unstable code
• A static checker STACK
  • 160+ previously unknown bugs confirmed and fixed
  • Users: companies (e.g., Intel), several open-source projects, ...

Implement 64-bit signed division x/y in SQL

• Zero check: y == 0
• Overflow check: y == -1 && x == -263
  • Result not representable in [-263,+263-1]

if (y == -1 && x < 0 && (x / y < 0))   /* -263/-1 < 0? */
  error();

SELECT ((-9223372036854775808)::int8) / (-1);

Our proposal:

if (y == -1 && x == INT64_MIN) /* INT64_MIN is -263*/

Developer’s fix:

if (y == -1 && ((-x < 0) == (x < 0)))

• Still unstable code: time bomb for future compilers
  • “it’s an overflow check so it should check for overflow”
  • “we don’t want the constant INT64_MIN; it’s less portable”

Meaningless checks from real code: pointer p; signed integer x

• Different compilers behave in different ways
  • Change/upgrade compiler ⇒ broken system
• Compilers perform many legitimate optimizations
  • Hard to distinguish unstable code from legal optimizations
• Unstable code eliminated without warnings
• Need a systematic approach

C/C++ source → LLVM IR → STACK → warnings

% ./configure
% stack-build make        # intercept cc & generate LLVM IR
% poptck                  # run STACK in parallel

res = x / y;
if (y == -1 && x < 0 && res < 0)
  return;

The check at line 2 is simplified into false, due to division at line 1

model: |                          # possible optimization
  %cmp3 = icmp slt i64 %res, 0
  -->  false
stack:                            # location of unstable code
  - div.c:2
core:                             # why optimized away
  - div.c:1
    - signed division overflow

• What’s the difference, compilers vs most programmers?
  • Assumption Δ: programs don’t invoke undefined behavior

• What can compilers do only with assumption Δ?
  • Optimize away unstable code

• STACK: mimic a compiler that selectively enables Δ
  • Phase I: optimize w/o Δ
  • Phase II: optimize w/ Δ
  • Unstable code: difference between the two phases

res = x / y;
if (y == -1 && x < 0 && res < 0)
  return;

• Assumption Δ:
  • No division by zero: y ≠ 0
  • No division overflow: y ≠ -1 OR x ≠ INT_MIN
• STACK can optimize “res < 0” to “false” only with Δ
  • Phase I: is “res < 0” equivalent to “false” in general? No.
  • Phase II: is “res < 0” equivalent to “false” with Δ? Yes!
• Report “res < 0” as unstable code

One must not trigger undefined behavior at any code fragment

• Reach(e): when to reach and execute code fragment e
• Undef(e): when to trigger undefined behavior at e

Δ = ∀e: Reach(e) → ¬Undef(e)

One must not trigger undefined behavior at any code fragment

Δ = ∀e: Reach(e) → ¬Undef(e)

res = x / y;
if (y == -1 && x < 0 && res < 0)
  return;

Δ = true → ¬((y == 0) ∨ (x == -1 ∧ y == INT_MIN)) # line 1
  ∧ true → ¬false                                 # line 2
  ∧ ((y == -1) ∧ (x < 0) ∧ (x/y < 0)) → ¬false    # line 3

Δ = ¬((y == 0) ∨ (x == -1 ∧ y == INT_MIN))

res = x / y;
if (y == -1 && x < 0 && res < 0)
  return;

• Compute assumption Δ: no undefined behavior
• Two-phase framework: w/o and w/ Δ
  • Report unstable code from difference
• Limitations
  • Missing unstable code: Phase II not powerful enough
  • False warnings: Phase I not powerful enough

• LLVM
• Boolector solver
• ~4,000 lines of C++ code
• Per-function for better scalability
  • Could miss bugs

• Is STACK useful for finding unstable code?
• How precise are STACK’s warnings?
• How much time to analyze a large code base using STACK?
• How prevalent is unstable code?

• Applied STACK to many popular systems
• Inspected warnings and submitted patches to developers
  • Binutils, Bionic, Dune, e2fsprogs, FFmpeg+Libav, file, FreeType, GMP, GRUB, HiStar, Kerberos, libX11, libarchive, libgcrypt, Linux kernel, Mosh, Mozilla, OpenAFS, OpenSSH, OpenSSL, PHP, plan9port, Postgres, Python, QEMU, Ruby+Rubinius, Sane, uClibc, VLC, Wireshark, Xen, Xpdf
• Developers accepted most of our patches
  • 160+ new bugs

• Kerberos: STACK produced 11 warnings
  • Developers accepted every patch
  • No warnings for fixed code
  • Low false warning rate: 0/11
• Postgres: STACK produced 68 warnings
  • 9 patches accepted: server crash
  • 29 patches in discussion: developers blamed compilers
  • 26 time bombs: can be optimized away by future compilers
  • 4 false warnings: benign redundant code
  • Low false warning rate: 4/68

Intel Core i7-980 3.3 GHz, 6 cores

• Applied STACK to all Debian Wheezy packages
  • 8,575 C/C++ packages
  • ∼150 days of CPU time to build and analyze
• STACK warns in ∼40% of C/C++ packages

unsigned long junk;              /* left uninitialized on purpose */
struct timeval tv;

gettimeofday(&tv, NULL);
srandom(junk
        ^ (getpid() << 16)       /* process id */
        ^ tv.tv_sec ^ tv.tv_usec /* time */
       );

uint64_t mul(uint16_t a, uint16_t b) {
    uint32_t c = a * b;
    return c;
}

Question: what’s the result of mul(0xffff, 0xffff)?

• (a) 1
• (b) 0xfffe0001
• (c) 0xfffffffffffe0001

• High-level languages have fewer undefined constructs
• But their interpreters are often written in C/C++

Question: what’s the output of the following PHP code?

<?php
  echo (1<<63) * 2
?>

• Programmers
  • Fix bugs
  • Workaround: disable certain optimizations

• Compilers & checkers
  • Many bug-finding tools fail to model C spec correctly
  • Use our ideas to generate better warnings

• Language designers: revise the spec
  • Eliminate undefined behavior? Perf impact?
  • C++ committee now exploring this question (SG12)

Reflections on trusting trust [Thompson84]

• Hide backdoors
  • Submit a new feature with unstable code
  • Could easily slip through code review

• Compilers optimize away unstable code
  • Subtle bugs
  • Significant security implications
• Compiler writers: use our techniques to generate better warnings
• Language designers: trade-off between performance & security
• Programmers: check your C/C++ code using STACK

http://css.csail.mit.edu/stack/