My scribe notes for Tuesday, 2/4 -- Nate Parsons

*** Summary
The tutorial paper by Erlingsson was not discussed much, other than that it was a good overview of already known attacks and defenses. The discussion focused on the Return-Oriented Program (ROP) paper by Shacham. This paper introduces a new attack technique that uses a memory safety violation to execute arbitrary behavior. ROPs consist of a sequence of stack pointers to "gadgets" already on the host machine (usually libc). Each gadget is a sequence of x86 binary that does something useful and ends with a 'ret' instruction (0xc3).  The novelty of ROP is that it bypasses the "W⊕X" defense by not requiring any code injection. It is still considered the state of the art in attacks, and extremely resilient.

The concept of full abstraction was introduced as a way of understanding attacks. An abstraction is full when 2 contextually equivalent programs are compiled (according to spec) into 2 contextually equivalent target programs in a reversible process. Many attacks happen when the semantics of the source language are not preserved or enforced in compilation, or if behavior is left undefined. In the latter case, subsets of the language can be considered, or if a consistent interpretation is chosen. A fully abstract compiler has no potential low-level attacks, and the programmer only needs to reason about their program semantics.

* Questions
1. Understanding ROP instructions:
   Conceptually, %esp points to the x86 instructions that interpret a ROP instruction
   Sometimes, gadgets will have side-effects that need to be pre-empted
2. Difference between type safe and full abstraction?
   type safety - source mechanism to rule out certain 'bad' programs
   full abstraction - different, just means that equivalent programs stay equivalent when compiled, often requires type safety
3. Encrypted pointers?
   Can be defeated with a single pointer and plaintext address, but how to get both?
   PointGuard paper (analysis could be a good project)
   Still need to protect data pointers
4. Enforce jumping only to beginning of basic blocks?
   This is CFI, which exists but is considered to be too slow+intrusive
   Could be a change just in cache controller (Louis)
   There would be an overhead in keeping track of these

* Criticisms
1. Some discussion in tutorial paper about the applicability or lack thereof to high-level languages. Paper claims yes, class thinks no
2. I didn't write down any unanswered criticisms of the ROP paper, it seems the paper was well written and expressed a good, new idea.

* Ideas
1. Can some kind of static analysis find if attacker-supplied values can affect program flow in this way? Mayhem (for binaries) will be read later
2. Encrypt Pointers with something better than ⊕ with key?
3. Is Pierce's talk about tagged memory applicable?
4. Implement CFI enforcement with cache controller
5. (overheard at a party) Divide programs into states
   Determine what memory is needed for each state
   Page switch along with state transitions
   This is like robust declassification technique
6. Compiler-enforced diversity?
   Many exploits rely on determistic compilation + offline analysis
   But if program contents can be leaked, then analysis can still happen online/offline
7. Timing-based side channels w/ assoc dictionary looking up values