  With the widespread deployment of Control-Flow Integrity (CFI), control-flow
hijacking attacks, and consequently code reuse attacks, are significantly more
difficult. CFI limits control flow to well-known locations, severely
restricting arbitrary code execution. Assessing the remaining attack surface of
an application under advanced control-flow hijack defenses such as CFI and
shadow stacks remains an open problem.
  We introduce BOPC, a mechanism to automatically assess whether an attacker
can execute arbitrary code on a binary hardened with CFI/shadow stack defenses.
BOPC computes exploits for a target program from payload specifications written
in a Turing-complete, high-level language called SPL that abstracts away
architecture and program-specific details. SPL payloads are compiled into a
program trace that executes the desired behavior on top of the target binary.
The input for BOPC is an SPL payload, a starting point (e.g., from a fuzzer
crash) and an arbitrary memory write primitive that allows application state
corruption. To map SPL payloads to a program trace, BOPC introduces Block
Oriented Programming (BOP), a new code reuse technique that utilizes entire
basic blocks as gadgets along valid execution paths in the program, i.e.,
without violating CFI or shadow stack policies. We find that the problem of
mapping payloads to program traces is NP-hard, so BOPC first reduces the search
space by pruning infeasible paths and then uses heuristics to guide the search
to probable paths. BOPC encodes the BOP payload as a set of memory writes.
  We execute 13 SPL payloads applied to 10 popular applications. BOPC
successfully finds payloads and complex execution traces -- which would likely
not have been found through manual analysis -- while following the target's
Control-Flow Graph under an ideal CFI policy in 81% of the cases.
