Microgadgets: size does matter in turing-complete return-oriented programming

Abstract

Return-oriented programming (ROP) has gained a lot of popularity lately, as an attack against currently imple-mented defenses in modern operating systems. Several kinds of ROP-based attacks and anti-ROP defenses have been proposed in recent years. The original attack tech-nique depends on the existence of a hand-picked set of byte sequences (called gadgets) in the program, while subsequent approaches use complex scanners, which per-form semantic analysis on the code to locate gadgets. The latter ones are efficient at finding gadgets and build-ing an attack, but incur a significant cost in time. We propose a ROP attack technique, based on a hand-picked but flexible and Turing-complete set of gadgets. One novelty in this approach is the use of microgadgets, which are gadgets restricted to 2 or 3 bytes in length. Our approach splits gadgets into several classes of vary-ing sizes (from 1 to more than 800). Only a single gadget from each class is required for Turing-completeness. The short length of the gadgets, as well as the large size of the classes, increase the likelihood of finding all required gadgets. We also describe an efficient scanner which locates these gadgets in a given program. We then use this scanner on the /usr/bin directories from several Linux distributions, to show that many programs indeed contain a Turing-complete set of microgadgets, which at-tackers can use to perform arbitrary computations. 1