Runtime defenses
================

Recall overall goal: what to do about software bugs?
  We previously looked at privilege separation.
    Good approach for putting the bugs where they don't matter as much.
    Limits the damage that bugs can cause.
  We also looked at bug-finding techniques to find and fix bugs.
  What if we really need to rely on some code that might be buggy?
    Privilege separation doesn't always apply.
    E.g., login handling must deal with passwords.
    And bug-finding might be incomplete.

Today's focus: runtime defenses.
  Plan: monitor execution of the system to detect buggy behavior.
    Stop the system if we detect something going wrong.
    Typically takes the form of some kind of instrumentation of code.
  Will look at examples of such approaches.
  Broad challenge: overhead of monitoring.
  Broad challenge: relevance / accuracy of checks being enforced.
  Usually runtime defenses make attacks harder,
    rather than providing strong guarantees.

Most prevalent example: memory safety.
  But will look at some non-memory-safety defenses towards the end.

Recall the buffer overflow attack:
  Code has bug that writes past the end of an array.
  Adversary can supply input that goes past the end.
  Overflowing array allows writing to the return address on stack.
  Buffer contains code to run.
  Return address points to this code.

Defense idea: non-executable stack.
  Mark certain memory non-executable, such as the stack.
  Hardware support in the CPU for making this efficient.
  Prevents runtime attacks that jump to overflowed buffers on the stack.
  Q: does NX mean we don't have to worry about buffer overflows?
    Another attack vector: jump to existing code in libc.
    Return address points to address of libc function to run.
  Q: is NX a waste of time if it isn't perfect?

Defense idea: stack canaries (StackGuard, gcc SSP, ..)
  Detects modification of return PC on stack *before* it is used by RET.
  Compiler generates code that pushes a "canary" value on stack at
    function entry, pops and checks value before return.
  Canary sits between variables and return address, e.g.:
                         |                  |
                         +------------------+
        entry %esp ----> |  return address  |    ^
                         +------------------+    |
        new %ebp ------> |    saved %rbp    |    |
                         +------------------+    |
                         |     CANARY       |    | Overflow goes
                         +------------------+    | this way.
                         |     buf[127]     |    |
                         |       ...        |    |
                         |      buf[0]      |    |
                         +------------------+
                         |                  |
  Q: what value should we use for the canary?
  A: perhaps a random number, chosen at program start,
     stored somewhere.

Defense idea: address space layout randomization (ASLR).
  Place process memory at random addresses.
  Adversary does not know precise address of application stack, code, heap, ...
  Makes it more difficult for adversary to exploit memory corruption:
    Don't know where to jump (buffer address randomized).
    Don't know where the code lives (existing code lives at random address).
  Requires compiler support to make all sections relocatable.

Are we done yet?
  What kinds of attacks might work despite ASLR?
  What kinds of attacks might work despite stack canaries?
  * maybe attacker can write or read the secret random canary value somehow.
  * overwrite function pointer on stack before canary.
  * overwrite some other crucial variable on the stack, e.g.
    bool ok = ...;
    char buf[128];
    gets(buf);
    if (ok) {
      ...
    }
  * overflow of one global variable into the next (much like on stack).
  * overflow of heap-allocated buffer.
    (there are an extensive set of defenses for heap allocators, too)

Defense idea: "fat pointers".
  Represent pointer with 3 values:
    Current pointer value.
    Base of the object being pointed to.
    Bound (end of the object being pointed to).
  On allocation: set current=base, set bound to current+size.
  On pointer arithmetic: do not adjust base or bound, do arithmetic on current.
  On dereference: check that base <= current < bound.
  Why might this be too simplistic?
    Minor: costly in terms of memory overhead.
    Moderate: performance overhead from naive bounds checks.
    Major: pointers are no longer single-word-size convertible to integers.
    Major: changes memory layout.
  There are more sophisticated schemes that track base+bound in a separate table.
    But need more elaborate rules and heuristics.

Defense idea: control flow integrity (Clang CFI, MSVC Control Flow Guard, ..).
  Approach: instead of preventing memory corruption, focus on code execution.
  Build graph of all expected (legal) control flow transitions from source code.
  When code executes a branch, check that the branch goes to a legal destination.
    Perhaps specific to the source of the branch.
  Prevents code injection attacks that jump to unexpected / arbitrary code.
  Some state-of-the-art systems have relatively low overhead.
  Makes attacks harder but not necessarily impossible.
    E.g., legal CFG may have too many edges due to uncertainty at compile-time.
    Especially likely with dynamic method dispatch (e.g., C++ virtual function).

How to enforce control-flow integrity at runtime?
  No need to instrument direct jumps: valid control flow at compile time.
  What to do about computed jumps?
    Instead of emitting a "call" instruction, need to emit more code.
    Typically check a bitmap of valid destination addrs.
    Compiler computes these bitmaps and places them in the binary.
    All indirect jumps are augmented with these bitmap checks.
    Can check a global bitmap, or more specific bitmaps.
      E.g., based on the signature of function being invoked (args, types, etc).
    If bitmap indicates the target is not valid, terminate program.

Defense idea: taint tracking.
  Intuition: track where data is coming from / going to.
  E.g., avoid unsanitized data in SQL queries or HTML pages.
  E.g., avoid sensitive data being sent over the network unless access-checked.
  E.g., avoid executing code or pointers that were received over the network.
  Approach: associate metadata with memory contents, propagate when data is copied.
  Main things to figure out for a taint tracking implementation:
    What granularity of state can be tagged?
    What do the tags look like?
    What are the sources (how to assign initial tags)?
    What are the sinks (how to check tags)?
    What operations propagate tags?
    How are tags combined when propagating?
  Can potentially catch interesting bugs that aren't just at one specific place.
    E.g., not just a buffer overflow at a specific location.
    Instead, violation of some global property (untrusted input used in SQL query).
  Has had some real runtime use.
    Some success when implemented using types in dynamically-typed languages.
    Some success in the context of debugging / tracing / testing.

Example taint tracking: Trusted Types in a Web browser.
  [[ Ref: https://developer.mozilla.org/en-US/docs/Web/API/Trusted_Types_API ]]
  Browser allows Javascript to modify the page contents (DOM).
  E.g.: e.innerHTML = x;
    This statement modifies element `e` in the DOM tree, setting its body to x.
  Common attack, which we saw a few weeks ago: cross-site scripting (XSS).
    If `x` is a string, it could contain more Javascript code!
    E.g., x could be "Hello world!  <script>code();</script>".
  Preventing these kinds of XSS: don't pass unsanitized strings.
    Need to escape "<" and ">" characters, etc.
  Runtime checking mechanism: the type of `x` must not be a string.
    Could either be a special "TrustedHTML" string which was sanitized.
      Developer specifies the sanitization / escaping rules.
      Assumes developer can get this right in this one place.
    Or a data structure repsenting the HTML tree to go into the element.
      Assumes the developer would not construct an HTML tree that
        contains adversary's Javascript code.
      Harder to make that kind of mistake than passing string into innerHTML.

Example taint tracking: strings in a language (e.g., PHP, Perl, Ruby).
  Every string has a one-bit tag: "untrusted".
  Network inputs are tagged "untrusted".
  SQL queries, HTML output requires only "trusted" strings.
  String operators preserve "untrusted" bit for the most part.
    Messy question, though.
    Finding a substring in tainted string: probably still tainted.
    Finding a tainted substring in trusted string: maybe not tainted?
  No tainting for other types (integers, etc).
    In particular, control flow not affected when branching on tainted value.
    Why?  Focus is on literal copying of untrusted input.
    Not always correct: e.g., implementation of toupper() using array.
    Could special-case such functions with specialized taint-propagation rules.
  When combining strings, taint is "max" of all inputs.
  How would you ever invoke a SQL query, then?
    Sanitizing functions clear the "untrusted" tag when quoting an string.
  Reasonably effective at catching various injection attacks.
    Untrusted input in SQL query (SQL injection).
    Untrusted input in HTML output (cross-site scripting).
    Untrusted input in shell command (command injection).
  Some limitations.
    What to do about taint tracking for data stored in files or in a database?
    Fuzzy propagation rules for corner cases.
    Sanitizing rules can be error-prone (e.g., used HTML sanitizer for SQL query).
  Still present in PHP and Perl, but Ruby removed taint tracking recently.
  [[ Ref: https://www.doc.ic.ac.uk/~livshits/papers/tr/dynataint_tr.pdf ]]

Example taint tracking: bytes of memory at machine level (mostly research ideas).
  Tag every byte of memory.
  Hardware support to propagate tags.
    Or a binary rewriter / virtual machine.
  Why might this be better?
    Lower-level enforcement: catches bugs in more code, smaller trusted base.
    More complete enforcement: spans processes, languages, maybe even storage.
  Why might this be worse than strings in a language?
    Higher overhead: more operations involve taint tracking.
    "Taint explosion": lots of operations can propagate taint to entire system state.
      E.g., branching on tainted value.
    Harder to introduce semantic meaning for how taint tags should be propagated.
  Keeps coming up in research papers, but no serious use in practice.

Summary.
  Runtime defenses can be useful to catch common bug patterns.
  Need to be clever in finding what assertions can be checked through instrumentation.
  Need to be clever in reducing instrumentation overhead.
  Memory safety, code injection tend to be the usual targets for runtime defenses.
  Taint tracking can help catch broader class of bugs, but somewhat speculative still.