Abstract

Return-orientated programming (ROP) identifies pieces of a process’s executable memory ending in a return instruction (gadgets), and enlists them as an instruction set in which a new, “parasitic” program can be written, hijacking the process’s control flow. Since gadgets are already present in executable memory, there is no reliance upon memory being mapped as both writeable and executable, which lets the ROP program (or “chain”) bypass the shellcode attack mitigation known as w ⊕ x. As such ROP represents one of the most difficult exploit mechanisms to mitigate. This thesis explores ROP-chain generation as a domain for evolutionary computation. It describes a system called ROPER (Return-Oriented Program Evolution with ROPER), designed and implemented by the author, which orchestrates the evolution of ROP-chains towards declaratively specified objectives. The author goes on to study the behaviour and ecology of the ROP-chain populations generated by ROPER, and their responses to various environmental pressures. Issues of importance include: 1) establishing a robust environment for evolution to discover ROP solutions, 2) the design of variation operators, 3) emergent strategies for genomic resilience, and 4) the role of speciation through fitness sharing. Case studies are performed using four very different tasks representative of: 1) the functional objective of a bare bones exploit, 2) a supervised learning task, 3) policy discovery for an agent playing ‘Snake’, and 4) an “unwinnable” task in which fitness is gauged randomly, so that the effects of non-selective pressures in the environment can be studied. Taken together this work represents the first time that ROP evolution has been explicitly demonstrated (at least in the public domain), and studied across a range of tasks.