Control Flow Integrity
Behavior-based detection
• Stack canaries, non-executable data, and ASLR aim
to complicate various steps in a standard attack
• But they still may not stop it
• Idea: observe the program’s behavior — is it
doing what we expect it to?
• If not, might be compromised
• Challenges
• Define “expected behavior”
• Detect deviations from expectation efficiently
• Avoid compromise of the detector
Control-flow Integrity (CFI)
• Define “expected behavior”:
Control flow graph (CFG)
• Detect deviations from expectation efficiently
In-line reference monitor (IRM)
• Avoid compromise of the detector
Sufficient randomness, immutability
Efficient?
• Classic CFI (2005) imposes 16% overhead on
average, 45% in the worst case
• Works on arbitrary executables
• Not modular (no dynamically linked libraries)
• Modular CFI (2014) imposes 5% overhead on
average, 12% in the worst case
• C only (part of LLVM)
• Modular, with separate compilation
• [Link]
Secure?
• MCFI can eliminate 95.75% of ROP gadgets on
x86-64 versions of SPEC2006 benchmark suite
• By ruling their use non-compliant with the CFG
• Average Indirect-target Reduction (AIR) > 99%
• AIR is, in essence, the percentage of possible targets
of indirect jumps that CFI rules out
- For CFI: nearly all of them
Call Graph
bool'lt(int'x,'int'y)'{'
sort2(int'a[],'int'b[],'int'len)'
''return'x<y;'
{'
}'
''sort(a,'len,'lt);'
bool'gt(int'x,'int'y)'{'
''sort(b,'len,'gt);'
''return'x>y;'
}
}
sort2 lt
sort
gt
Which functions call other functions
Control Flow Graph
bool'lt(int'x,'int'y)'{'
sort2(int'a[],'int'b[],'int'len)'
''return'x<y;'
{'
}'
''sort(a,'len,'lt);'
bool'gt(int'x,'int'y)'{'
''sort(b,'len,'gt);'
''return'x>y;'
}
}
sort2 lt
sort
gt
Break into basic blocks
Distinguish calls from returns
CFI: Compliance with CFG
• Compute the call/return CFG in advance
• During compilation, or from the binary
• Monitor the control flow of the program and
ensure that it only follows paths allowed by the CFG
• Observation: Direct calls need not be monitored
• Assuming the code is immutable, the target address
cannot be changed
• Therefore: monitor only indirect calls
• jmp, call, ret with non-constant targets
Control Flow Graph
bool'lt(int'x,'int'y)'{'
sort2(int'a[],'int'b[],'int'len)'
''return'x<y;'
{'
}'
''sort(a,'len,'lt);'
bool'gt(int'x,'int'y)'{'
''sort(a,'len,'gt);'
''return'x>y;'
}
}
sort2 lt
sort
gt
Direct calls (always the same target)
Control Flow Graph
bool'lt(int'x,'int'y)'{'
sort2(int'a[],'int'b[],'int'len)'
''return'x<y;'
{'
}'
''sort(a,'len,'lt);'
bool'gt(int'x,'int'y)'{'
''sort(a,'len,'gt);'
''return'x>y;'
}
}
sort2 lt
sort
gt
Indirect transfer (call via register, or ret)
In-line Monitor
• Implement the monitor in-line, as a program
transformation
• Insert a label just before the target address of an
indirect transfer
• Insert code to check the label of the target at
each indirect transfer
• Abort if the label does not match
• The labels are determined by the CFG
Simplest labeling
label L
sort2 lt
sort
label L
label L
label L
label L gt
Use the same label at all targets
Simplest labeling
label L
sort2 lt
sort
label L
label L
label L
label L gt
ok…
system
Use the same label at all targets
Blocks return to the start of direct-only call targets
but not incorrect ones
Detailed labeling
label M
sort2 lt
sort
label L
label N
label M
label L gt
ok…
Constraints:
• return sites from calls to sort must share a label (L)
• call targets gt and lt must share a label (M)
• remaining label unconstrained (N)
Still permits call from site A to return to site B
Classic CFI instrumentation
Check target
label
Check target
label
Can we defeat CFI?
• Inject code that has a legal label
• Won’t work because we assume non-executable data
• Modify code labels to allow the desired control flow
• Won’t work because the code is immutable
• Modify stack during a check, to make it seem to
succeed
• Won’t work because adversary cannot change
registers into which we load relevant data
- No time-of-check, time-of-use bug (TOCTOU)
CFI Assurances
• CFI defeats control flow-modifying attacks
• Remote code injection, ROP/return-to-libc, etc.
• But not manipulation of control-flow that is
allowed by the labels/graph
• Called mimicry attacks
• The simple, single-label CFG is susceptible to these
void func(char *arg1)
• Nor data leaks or corruptions {
• Heartbleed would not be prevented int authenticated = 0;
char buffer[4];
• Nor the authenticated overflow strcpy(buffer, str);
- Control modification is allowed by graph if(authenticated) { …
}