  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.
