Data representation 5: Undefined behavior, assembly

Overview

We investigate the consequences of undefined behavior, run a simple stack-smashing attack, and begin the assembly unit.

Signed integer overflow is undefined behavior

• INT_MAX + 1 == 💩
  • Undefined behavior
  • Sanitizer reports error
  • Optimizer can assume it never happens
  • Computer hardware acts like unsigned overflow

datarep-arith/ubsignedinc three ways

1. SAN=1 (sanitized, optimized)
2. SAN=0 O=0 (not sanitized, not optimized)
3. SAN=0 (not sanitized, optimized)

More examples of undefined behaviors

• Dividing an integer by 0
• Using an uninitialized variable
• Violating the live object rule
• Modifying a const object
• Accessing data beyond the bounds of an array
• Comparing pointers to unrelated objects using < <= > >=
• Accessing an invalid iterator
• Accessing an object using a pointer of incompatible type

Consequences

• Because signed overflow is undefined behavior, the compiler can assume computer integer arithmetic behaves like mathematical integer arithmetic
  • For instance, it can assume that x + 1 > x
• This helps compilers generate faster code
  • For instance, the undefined behavior sanitizer, which adds overflow checks, can slow down code by 1.5x
• But it also causes security nightmares
  • Modern languages have tried to tamp down on undefined behaviors

Optimizers and undefined behavior

1. ./ubsignedloop 0 0x7fffffff (SAN=1, SAN=0, SAN=0 O=0)
2. ./ubtable 4 (SAN=1, SAN=0 O=0, SAN=0)

Smashing the stack, and intro to assembly

• datarep-smash/smasher.cc, made with UNSAFE=1

Aside: Internal metadata

Aside: Representing sets bitwise

• Bitwise operators allow us to efficiently represent small sets
• A set is a collection of elements, each of which might be present or absent
• An integer is a collection of bits, each of which might be 1 or 0
• Set operations, such as union, intersection, and membership-test, correspond to bitwise operations

Bitset example

• Consider sets taken from the universe {e, f, g, h}
• Assign each element m a distinct bit value ℬ(m) (which must be a power of two)
  • For example, ℬ(e) = 1, ℬ(f) = 2, ℬ(g) = 4, ℬ(h) = 8
• A set of elements is represented as the sum of the ℬ values
  • ℬ({}) =
  • ℬ({}) = 0
  • ℬ({e, g}) =
  • ℬ({e, g}) = ℬ(e) + ℬ(g) = 5
  • ℬ({e, f, g, h}) =
  • ℬ({e, f, g, h}) = 15
• Union and intersection
  • ℬ(X ∪ Y) =
  • ℬ(X ∪ Y) = (ℬ(X) | ℬ(Y))
  • ℬ(X ∩ Y) =
  • ℬ(X ∩ Y) = (ℬ(X) & ℬ(Y))
  • Map to bitwise & and |!
  • For example, {e, f} ∪ {e, h} = {e, f, h}, and indeed (3 | 9) == 11
• Set difference maps to & with ~
  • ℬ(X ∖ Y) = (ℬ(X) & ~ℬ(Y))
• Membership testing maps to &
  • m ∈ X ⟺ (ℬ(m) & ℬ(X)) != 0