State of art reference

In Q4 2016, reddit finally helped me identify the relevant academic field. below is a short list of what I found and find relevant.

Identification of data structure in memory dump of executed sample

• Laika: Digging For Data Structures, 2008
  Keywords: Bayesian unsupervised learning, typed pointer
  Parse the whole memory pages without precise identification of memory chunks. Basic type heuristics. Introduce the indea of typed pointer, where same-size records with pointers values in same offset would probably be the same type.
  Applied to malware triage using bayesian learning.
  ****NB: Concept tested in haystack circa 2011-2012 **** TODO: look for follow-ups. heap walker anyone ?

• 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).
  ****NB: Concept very similar to haystack ****

• KOP

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

Identification of type in (static|dynamic) reverse analysis of samples

• TIE: Principled reverse engineering of types in binary programs, 2011
  Keywords: Type reconstruction, code analysus

Identification of data structures in dynamic execution of samples

• ASI: Aggregate Structure Identification and its Application to Program Analysis, 1999 Keywords:
  Label known typed structures from known function signatures

• VSA: Value Set analysis ?

• RDS: Recursive data structure profiling, 2005
  Keywords: profiling, shape graph analysis, Allocation dynamic analysis
  It creates a graph of relation between records based on pointer values. Note: I'm not sure I understand the finality of using dynamic analysis for this

• DDT: design and evaluation of a dynamic program analysis for optimizing data structure usage, 2009
  Keywords: data structure identification, Allocation dynamic analysis, interface detection, memory graph
  Create a memory graph. Takes into account the allocation-site to type a memory chunk. Allow performance analysis of linked data structure (lists, tree).

• Rewards: Automatic reverse engineering of data structures from binary execution, 2010
  Keywords:
  Builds on ASI ?

• Howard: a dynamic excavator for reverse engineering data structures, 2011
  Keywords: allocation dynamic analysis,
  Analysis access pattern to determine field size. Uses allocation-locality, types sink and typed pointer to type records. Array detection using loop unrolling and access analysis (linked list {prev,next} pointers). Generation of new debug symbols. Based on KLEE for instrumentation. Focus of work seems to be performance and memory protection. NB: CodeSurfer/x86 is a combination of VSA and ASI.

• MemPick: High-Level Data Structure Detection in C/C++ Binaries, 2013
  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).

Terminology

• 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 identification: Detection of primitive types or records.
• High-level data structure identification: Recursive data structure and linked (pointer) structures.