See also: source code.

Wish I'd noticed this paper sooner, as I seem to have done a lot of overlapping work with the authors over the past few months:

During the development of Retypd, we carried out an extensive investigation of common machine-code idioms in compiled C and C++ code that create challenges for existing type-inference methods. For each challenging case, we identified requirements for any type system that could correctly type the idiomatic code. The results of this investigation appear in §2. The type system used by Retypd was specifically designed to satisfy these requirements. These common idioms pushed us into a far richer type system than we had first expected, including features like recursively constrained type schemes that have not previously been applied to machine-code type inference.

Section two contains an excellent discussion of real-world issues that arise when trying to reconstruct (or even simply model) types in compiled C++ binaries. The only thing that seems to be missing is shifted pointers with negative displacements.

I'm looking forward to examine it in depth soon.