Identification of data structure in memory dump of executed sample

RDS: Recursive data structure proﬁling, 2005
Laika: Digging For Data Structures, 2008
Keywords:
Similarity in malware
SigGraph: Brute Force Scanning of Kernel Data Structure Instances Using Graph-based Signatures, 2011
Keywords: data structure isomorphism, signature creation, Kernel rootkit detection, kernel version inference
Detection of kernel structures in memory dump. Compiler based approach. Generate signatures based on source code (AST).

KOP
MAS
Microsoft efforts at rootkit detection in kernel memory dumps. Massive data source.

Identification of data structures in dynamic execution of samples

MemPick: High-Level Data Structure Detection in C/C++ Binaries
Keywords: Shape analysis, Allocation dynamic analysis, overlay
Uses Intel PIN to instrument allocation primitives. Creates a graph based on pointer values? Type analysis. Overlays detection. Classify linked list, trees shapes. Performance assessment of tree usage.
Overall, conclusion seems focused on detection of linked list structures (hint at performance domain).
DDT: design and evaluation of a dynamic program analysis for optimizing data structure usage, 2009
Rewards: Automatic reverse engineering of data structures from binary execution, 2010
Howard: a dynamic excavator for reverse engineering data structures, 2011
TIE: Principled reverse engineering of types in binary programs, 2011

Shape analysis: Discovers and verifies properties of linked data structure to verify high level correctness of programs.
Allocation dynamic analysis: Instrumentation of sample to identify allocated memory block. Not heap walking. Require one or multiple run of the sample.
Heap walking: Identify allocated memory block by following the static memory dump heap management structure.
Low-level data structure identiﬁcation: Detection of primitive types or records.
High-level data structure identiﬁcation: Recursive data structure and linked (pointer) structures.