ARTISTE: Automatic Generation of Hybrid Data Structure Signatures from Binary Code Executions
Juan Caballero, Gustavo Grieco, Mark Marron, Zhiqiang Lin, David I. Urbina · 2012
Data structure signatures can be used for finding instances of data structures holding sensitive data in memory, a crucial capability for many security applications such as memory forensics, rootkit detection, online games cheat analysis, reverse engineering, and virtual machine introspection. Manually generating data structure signatures is a tedious and error-prone process. Prior work automatically generates data structure signatures from the type definitions in the program’s source code, but unfortunately for many programs their source code is not publicly available. In this paper we present ARTISTE, the first tool for automatically generating data structure signatures without access to the program’s source code or debugging symbols. The salient features of ARTISTE are: (1) it generates hybrid signatures that minimize false positives during scanning by combining points-to relationships, value invariants, and cycle invariants; (2) it uses a novel dynamic shape analysis to recover recursive data structures, classifying them by their shapes (e.g., doubly linkedlist or tree); (3) it identifies data structures of the same type allocated at different program points; and (4) it accumulates data structure information over multiple executions, increasingly improving its accuracy. Our experimental results on a number of binary programs show that the hybrid signatures generated by ARTISTE accurately identify instances of the data structures in memory with no false positives or false negatives in 80% of the programs, while prior signature types produce large false positive rates.