For many compiled languages, source-level types are erased very early in the compilation process. As a result, further compiler passes may convert type-safe source into type-unsafe machine code. Type-unsafe idioms in the original source and type-unsafe optimizations mean that type information in a stripped binary is essentially nonexistent. The problem of recovering high-level types by performing type inference over stripped machine code is called type reconstruction, and offers a useful capability in support of reverse engineering and decompilation.
In this paper, we motivate and develop a novel type system and algorithm for machine-code type inference. The features of this type system were developed by surveying a wide collection of common source- and machine-code idioms, building a catalog of challenging cases for type reconstruction. We found that these idioms place a sophisticated set of requirements on the type system, inducing features such as recursively-constrained polymorphic types. Many of the features we identify are often seen only in expressive and powerful type systems used by high-level functional languages.
Using these type-system features as a guideline, we have developed Retypd: a novel static type-inference algorithm for machine code that supports recursive types, polymorphism, and subtyping. Retypd yields more accurate inferred types than existing algorithms, while also enabling new capabilities such as reconstruction of pointer const annotations with 98% recall. Retypd can operate on weaker program representations than the current state of the art, removing the need for high-quality points-to information that may be impractical to compute.
Wed 15 JunDisplayed time zone: Tijuana, Baja California change
10:30 - 12:00
|Into the depths of C: elaborating the de facto standards|
Kayvan Memarian University of Cambridge, Justus Matthiesen University of Cambridge, James Lingard University of Cambridge (when this work was done), Kyndylan Nienhuis University of Cambridge, David Chisnall University of Cambridge, Robert N. M. Watson University of Cambridge, Peter Sewell University of CambridgeLink to publication Media Attached
|Living on the edge: Rapid-toggling probes with cross modification on x86|
Buddhika Chamith , Bo Joel Svensson Indiana University, Luke Dalessandro Indiana University, Ryan R. Newton Indiana UniversityPre-print Media Attached
|Polymorphic Type Inference for Machine Code|
Research PapersPre-print Media Attached