Method for extracting the structure of an input for a binary program
Inventors
NARASIMHA, Seshagiri Prabhu • Lakhotia, Arun
Assignees
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
Publication Number
US-12572332-B2
Publication Date
2026-03-10
Expiration Date
Abstract
Herein disclosed is a method for automatically automatically infer a recursive state machine (RSM) describing the space of acceptable input of an arbitrary binary program. This method automatically identifies atomic fields of fixed and variable lengths and syntactic elements, such as separators and terminators, and generalizes them into regular expression tokens. It constructs an RSM of tokens to represent structures such as arrays and records. Further, it constructs nested states in RSM to represent complex, nested structures. The RSM may serve as an independent parser for the program's acceptable input.
Core Innovation
The invention discloses an automated method for extracting a structure of a binary program by inferring a recursive state machine that represents the space of acceptable inputs for an arbitrary binary program. A state machine is provided and a serialized representation of a data structure is provided as input, wherein the data structure comprises one or more fields that are atomic or composite, and each atomic field comprises one or more values as a sequence of bytes.
During execution, the method produces a taint trace comprising a sequence of tuples that includes an instruction address, an abstracted calling context, and a set of taints that is the union of all taints of all operands of an instruction during an invocation. From the taint trace, the method identifies the field values and each field value’s corresponding source index, constructs a taint interval tree, derives one or more field tokens, and classifies instructions that access the field values to infer a field type for each set of instructions.
The method then constructs a structure transition graph and applies these steps recursively to construct a recursive state machine. Nested structures are represented with nested states and recursion, and recursive extraction can join RSMs inferred from different inputs into a single abstract state machine without requiring a separate parser.
Claims Coverage
The partial content includes two independent claims. Each independent claim centers on recursively extracting a structure of a binary program using taint traces, tokens, type inference, and graph construction to produce a recursive state machine.
Recursive extraction using taint trace, tokens, type inference, and structure transition graph
A method for extracting a structure of a binary program that provides a state machine, provides inputs comprising a serialized representation of a data structure with atomic or composite fields (atomic fields having sequence-of-bytes values), producing a taint trace with instruction address, abstracted calling context, and union taints of instruction operands; identifying field values and each field value’s corresponding source index; constructing a taint interval tree; deriving field tokens; classifying instructions that access the field values to infer a field type; constructing a structure transition graph; and applying each of these steps recursively to construct a recursive state machine.
State machine construction from frontier with token, type, and data encoding annotation
A method for extracting a structure of a binary program that provides a state machine, further comprising constructing a state machine from a frontier by ordering taint interval graph nodes by start offsets, creating nodes for each source index, marking the last source index as the final node and the new node as the start node, annotating each node with the token, type, and data encoding of its respective source index, and adding edges to the taint interval graph and a start edge; providing inputs comprising a serialized representation of a data structure with atomic or composite fields (atomic fields having sequence-of-bytes values); producing a taint trace from which field values and corresponding source indices are identified; constructing a taint interval tree; deriving field tokens; classifying instructions accessing the field values to infer a field type; constructing a structure transition graph; and applying each of these steps recursively to construct a recursive state machine.
Across both independent claims, the inventive core is recursive structure extraction for a binary program driven by taint-trace tuples, mapping taint-trace source indices to field values, deriving field tokens, inferring field types via instruction classification, and constructing a structure transition graph to build a recursive state machine, with one claim additionally specifying state-machine construction from a frontier annotated with token, type, and data encoding.
Stated Advantages
Enables joining RSMs inferred from different inputs into a single abstract state machine without requiring a separate parser.
Documented Applications
Inferring a recursive state machine representing the space of acceptable inputs for an arbitrary binary program.
Interested in licensing this patent?