Sound and Efficient Generation of Data-Oriented Exploits via Programming Language Synthesis

Data-oriented programming (DOP) is a methodology for embedding malicious programs into fixed executable vulnerable binaries. DOP is effective for implementing code reuse attacks that exploit memory corruptions without violating many defence techniques, such as non-execute, address space layer randomisation, control flow and code point integrity. Existing approaches for automated exploit generation for DOP follow the program synthesis approach: given a description of an attack phrased as a program, they perform extensive constraint-based search to identify the required payload for the corrupted memory. The program synthesis-inspired approaches come with three major shortcomings regarding (a) efficiency: attack generation often takes prohibitively large amount of time, (b) soundness: they provide no formal guarantees whatsoever that a particular user-described attack is feasible in a particular vulnerable program with suitable payloads, and (c) capability visibility: they do not make clear to users what attack capabilities are admitted by the vulnerable program.

In this work, we propose a novel approach to synthesise code reuse attacks via DOP by casting this task as an instance of the previously unexplored programming language synthesis idea. Given a vulnerable program and an exploit (e.g., buffer overflow), our approach derives a grammar of a programming language for describing the available attacks. Our approach addresses the issue (a) by shifting the cost of synthesising individual attacks to synthesising the entire attack language: once the grammar is generated, the compilation of each attack takes negligible time. The issues (b) and (c) are addressed by establishing correctness of our grammar synthesis algorithm: any attack expressible in terms of a generated grammar is realisable. We implement our approach in a tool called DOPPLER—an end-to-end compiler for DOP-based attacks. We evaluate DOPPLER against available state-of-the art techniques on a set of 17 case studies, including three recent CVEs, demonstrating its improved effectiveness (it generates more attacks) and efficiency (it does so much faster).