DynPRE: Protocol Reverse Engineering via Dynamic Inference

DynPRE: Protocol Reverse Engineering via Dynamic Inference

Speakers: Zhengxiong Luo

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=LOeWsdNOF04

Overview

In the realm of network security, understanding unknown protocol specifications is a foundational yet formidable challenge. This task, known as protocol reverse engineering (PRE), is indispensable for a myriad of critical security applications, including fuzzing, model checking, automatic exploit generation, and even code generation. A precise recovery of a protocol's format and state machine forms the bedrock for generating legitimate packet sequences for fuzzing or constructing accurate models for formal verification. However, existing PRE methodologies often grapple with significant limitations, either demanding access to source code or binaries (which are frequently unavailable for proprietary or embedded systems) or suffering from low accuracy due to their reliance on static network traces.

Zhengxiong Luo's talk at the NDSS Symposium introduces DYNPRE, a novel, fully automatic, network trace-based protocol reverse engineering tool designed to overcome these long-standing challenges. DYNPRE distinguishes itself by integrating a dynamic inference approach. Unlike traditional methods that passively analyze static network traces, DYNPRE actively communicates with the target server, intelligently constructing probe messages to extract insightful semantic information and acquire additional samples as needed. This active probing strategy makes DYNPRE particularly adept at handling input traces with limited initial information, addressing the critical shortcomings of prior art.

The core innovation of DYNPRE lies in its ability to effectively interact with a server without any prior protocol specifications and to design a probing strategy that is broadly applicable while inducing diverse server behaviors. It tackles the complexities of stateful systems and dynamically assigned session-specific identifiers, which often lead to request rejections in traditional passive methods. By dynamically inferring field semantics directly from server responses to byte-level modifications and refining its understanding through iterative interaction, DYNPRE achieves a significantly more accurate and comprehensive understanding of underlying protocol structures and semantics, thereby enhancing the efficacy of downstream security analyses.

Background

▶ Watch: Introduction to DYNPRE and problem motivation (0:00)

Protocol reverse engineering methods traditionally bifurcate into two primary categories: program analysis-based and network trace-based. Each category presents its own set of advantages and inherent limitations that DYNPRE aims to transcend.

Program analysis-based approaches, exemplified by techniques such as taint analysis or static binary analysis, dynamically monitor the internal execution of a protocol application. By tracking how messages are processed within the program, these methods can achieve high accuracy, leveraging the rich runtime semantics available. Tools like WEIZZ and Prospex fall into this category. However, their significant drawback is the prerequisite for access to the source code or binary of the protocol implementation. This access is frequently unavailable, especially when dealing with embedded systems, proprietary software, or black-box devices like many IoT gadgets, severely limiting their applicability in real-world scenarios.

Network trace-based approaches, on the other hand, operate by taking static network traces (captured packet data) as input and performing statistical analysis on these observed communications. These methods are generally easier to deploy as they only require network access to capture traffic. However, they typically suffer from lower accuracy due to two main limitations. Firstly, their effectiveness is heavily contingent on the availability of high-quality network traces that contain diverse protocol messages and cover most protocol features. Obtaining such traces often requires prior protocol knowledge and is not always feasible given the distributional biases inherent in real-world network traffic. If a specific message type or field value rarely appears in the captured trace, statistical methods may misinterpret or entirely miss its significance.

Secondly, and more critically, purely statistical methods frequently struggle to capture field semantics that are not explicitly manifested in value changes across messages. For example, consider an SMB2 message. If a Length field consistently has values less than 0x010000 across all input messages, the highest two bytes might always be 0x0000. A tool like Netzob, relying on statistical variance, might erroneously treat these constant 0x0000 bytes as a fixed field and misplace the actual length field's highest byte into an adjacent, semantically unrelated field. Such misidentification of field boundaries severely impacts protocol comprehension, particularly for downstream tasks like fuzzing, where accurate length fields are crucial for understanding memory behavior. Another example is a Reserved field in a protocol header, which might always be 0x00. While its value doesn't change, it still holds a semantic role (reserved for future use). Statistical analysis might simply label it as a constant, failing to capture its true meaning or distinguish it from other constant fields with different implications. Similarly, the highest byte of the Command field in SMB2 is reserved for customization and is always 0x00 in well-formed messages. Netzob might split this into two independent fields, treating the reserved byte as a constant, thus hindering a complete understanding of the protocol design. This fundamental gap between field semantics and statistical characteristics poses a significant challenge for existing trace-based tools.

DYNPRE's basic idea is inspired by two key observations: dynamic interaction allows for the generation of supplementary samples beyond the original input, and it enables the acquisition of field semantic information directly from the server, which inherently encodes the protocol logic. By actively probing the server with various requests, DYNPRE enriches its dataset with legitimate response messages, making it easier for subsequent analysis to uncover hidden nuances, such as the behavior of an incrementing MessageID field in SMB2. Furthermore, observing the server's reactions to modifications—e.g., a Reserved field being ignored versus a Command field changing the response type—provides direct semantic feedback that static analysis cannot.

To effectively leverage interactive capabilities, DYNPRE must overcome two specific challenges:

• Challenge C.1: Proper interaction with the server. Servers are often stateful systems, requiring well-formed messages in a specific sequence. Crucially, many protocols employ session-specific identifiers (e.g., TCP's SequenceNumber, HTTP's Cookie, SSL's SessionID, SMB2's SessionID and TreeID, FTP's PassivePort). These identifiers are dynamically assigned by the server and are essential for maintaining context across sessions. Using outdated or incorrect values will inevitably lead to rejected requests, preventing any meaningful interaction. DYNPRE identified such identifiers in 16 out of 50 public and proprietary protocols examined, highlighting their prevalence.
• Challenge C.2: Effective exploration of the interactive server for protocol understanding. Constructing probe requests to elicit diverse server behaviors is difficult because the server must be in the appropriate state to accept the message, and arbitrary modifications can destroy message structure, yielding uninformative results. Moreover, analyzing server responses is challenging due to their opaque nature without prior protocol knowledge and the presence of random noise (e.g., SystemTime fields in SMB2 responses) that can interfere with analysis.

Key Findings

▶ Watch: Adaptive message rewriting for server interaction (2:00)

DYNPRE's extensive evaluation across a diverse set of public and proprietary protocols yielded several compelling key findings, demonstrating its significant advancements over existing protocol reverse engineering tools:

• Superior Format Inference Accuracy: DYNPRE substantially outperforms all state-of-the-art tools in identifying byte boundaries and inferring protocol formats. Across various dataset sizes and 12 widely used public protocols, DYNPRE achieved an average accuracy of 0.83, an F1-score of 0.70, and a critical perfection score of 0.50. This perfection score, which measures exact field matches to ground truth, is 3.3x higher than that of tools like Netzob, Netplier, FieldHunter, and BinaryInferno, and 1.6x higher than Nemesys, enabling far more precise downstream security analyses.
• Exceptional Message Type Inference: For the crucial task of message type inference, DYNPRE achieved an average V-measure of 0.94, significantly outperforming competitors such as Netzob (0.72), Netplier (0.73), FieldHunter (0.83), and Nemesys (0.83). This indicates DYNPRE's superior ability to correctly cluster messages into their respective types.
• Robust Session-Specific Identifier Detection: DYNPRE accurately identifies all potential session-specific identifiers within network traces and derives correct message rewrite rules. This was validated across protocols like HTTP (Cookie), SMB/SMB2 (SessionID, TreeID, ServerGuid), BGP (MyAS), and TFTP (DestinationPort). Its capability to handle complex scenarios, such as the varying lifetimes of identifiers in SMB/SMB2 or the y=x+1 constraint for the Stamp field in the Xiaomi camera protocol, highlights its robustness.
• Effectiveness of Refinement Strategy: The proposed mapping-based refinement strategy significantly enhances DYNPRE's format inference capabilities. It demonstrated an average improvement of 0.05 in accuracy, 0.10 in F1-score, and 0.13 in perfection compared to DYNPRE operating without this refinement, underscoring the value of exploiting correlations between request and response formats.
• Success with Proprietary IoT Protocols: DYNPRE proved highly effective in reverse engineering real-world proprietary protocols used in IoT devices. In experiments with devices like Yeelight LED lights and Xiaomi Mijia Smart Cameras, DYNPRE successfully inferred message formats. Crucially, messages generated based on these inferred formats not only triggered original device behaviors but also unlocked additional, previously unobserved behaviors (e.g., 7 original behaviors led to 15 different triggered behaviors), validating the depth and accuracy of DYNPRE's understanding.
• Scalability for Checksum Mechanisms: DYNPRE can integrate with existing tools like delsum 1 to handle protocols employing checksums. For the ICMP protocol, DYNPRE successfully reversed the checksum algorithm and achieved a perfection score of 0.66, demonstrating its adaptability to such protective mechanisms.
• Dynamic Interaction's Crucial Role: The consistent superiority of DYNPRE, even when other tools were provided with dynamically enhanced datasets, highlights that its core strength lies not just in more samples, but in its unique strategy of correlating modification operations with server feedback to infer precise byte semantics, a capability static analysis inherently lacks.

Technical Deep Dive

▶ Watch: Dynamic probing strategy for protocol understanding (3:00)

DYNPRE's robust performance stems from its sophisticated system design, which seamlessly integrates dynamic interaction with intelligent analysis. The workflow, as depicted in the talk, begins with preprocessing and then proceeds through two main components: the Session-Specific Identifier Detector and the Dynamic Inference module.

System Design Overview

1. Filtering and Slicing: The initial step involves preprocessing input network traces. This module extracts relevant messages, filters out irrelevant protocols (e.g., by leveraging known information from lower layers like TCP ports, IP addresses, and timestamps), and groups them into distinct traces, typically based on TCP sessions. Each trace is then analyzed sequentially.

1. Session-Specific Identifier Detector: This module is crucial for DYNPRE's ability to interact correctly with stateful servers. It recognizes all embedded session-specific identifiers (e.g., SessionID, TreeID) within a trace and extracts their detailed attributes, including their source (where the dynamic value is first introduced), references (where the value is subsequently consumed), and their constraint relationships (e.g., y = x for direct consistency, or y = x+1 for incrementing counters like the Xiaomi camera's Stamp field). These attributes are compiled into message rewrite rules.

The detection process, outlined in Algorithm 1, is recursive and iterative. DYNPRE starts with an empty set of rewrite rules and incrementally learns them through the inferAndVerify procedure. For each session, it establishes a new connection, stores live responses in a LiveResponsePool, and attempts to replay the original network trace.

• Request Rewriting: Before sending a request message M, DYNPRE rewrites it (P_r) by applying the current rewrite rules from Y_cur and leveraging live responses from the LiveResponsePool to ensure session-specific identifiers are valid.
• Response Verification: For a response message M in the original trace, DYNPRE receives a live response M' from the server and compares them. If M and M' differ but are compatible (same length, differences concentrated in continuous segments, not scattered), M likely contains session-specific identifiers.
• Rule Calculation: If M is not yet in Y_cur, the calculateRules procedure identifies differing byte regions (DynRegions) between M and M'. It then analyzes these regions to solve constraints based on the trace, deriving a set of feasible rewrite rules Y_R. DYNPRE considers five constraint terms: x, x+1, px (multiplicative), px+1, and null (for random noise). These new rules are combined with existing ones, and the process recursively attempts to validate the updated rule set. This recursive validation ensures that the inferred rules allow for successful replay of the entire trace.

Dynamic Inference Module

Leveraging the message rewrite rules, this module enables DYNPRE to seamlessly interact with the server and perform its core dynamic inference.

1. On-the-Fly Message Rewriting: This mechanism is the practical application of the rules derived by the Session-Specific Identifier Detector. It dynamically extracts values of session-specific identifiers from server responses (when the response is a source) and adaptively updates the corresponding byte regions in subsequent requests before transmission (when the request contains references). For instance, if message ④ in an SMB2 session is the source of a SessionID (bytes M44..51), its value is extracted from the live response and then injected into M44..51 of subsequent requests like message ⑤.

1. Message Probing: DYNPRE analyzes the format of each request message M by performing byte-level flip modifications. This strategy is based on three key insights:

• The byte is the smallest field unit in most protocols, making byte-level identification granular and appropriate.
• Modifying content (flipping bits or changing values) rather than adding or deleting bytes helps preserve the overall message structure, allowing for deeper semantic feedback.
• By assigning values that markedly differ from the original, DYNPRE maximizes the exposure of semantic changes in server responses, even when server response semantics are initially opaque.

Crucially, to ensure meaningful feedback, DYNPRE first drives the server into the appropriate state receptive to the message M under analysis. This is achieved by replaying the preceding requests in the trace (Γ:M) using the established on-the-fly message rewriting mechanism to maintain valid session context.

1. Request Analysis (Algorithm 2): This procedure infers the format L for a request M, where each field in L is a tuple Ms..e T (byte range and type).

• Q(Mi) represents the SENDRECV operation: establishing a new session, sending preceding requests Γ:M to set the server state, and then sending the probe request Mi. Message rewriting ensures session-specific identifier validity.
• Ri is the response pool for Mi, collecting multiple responses to explore variations (due to session-specific identifiers or random fields). maski denotes bytes that differ across responses in Ri.
• DYNPRE sequentially analyzes each byte i in M to determine if it's the start of a new field. To check if byte i and the current field's start byte s are semantically identical, a two-step check is performed:

1. Compare their masks: maski should be a subset of masks.
2. Compare their response pools Ri and Rs (for byte s), ignoring regions in masks. This comparison accounts for value propagation under modification, indicating if changing one byte semantically affects another.

• If the check fails, i is deemed the start of a new field. For a newly identified field Ms..e, its basic type (constant or variable) is determined by randomly modifying its value and observing if all responses are semantically identical or produce the same error.

1. Response Analysis: Unlike requests, responses are often received passively and are difficult to probe directly. DYNPRE employs a statistical method, leveraging the additional responses obtained from modifying each byte of the request M. These byte-level modifications often yield numerous responses of the same type as M but with subtle differences. DYNPRE filters these responses (R') to retain those with the same length as M, then applies an alignment algorithm (similar to Netzob's) to R' to infer the format by merging consecutive identical or variable bytes.

1. Mapping Based Refinement: This final step exploits correlations between inferred request and response formats. Protocols often exhibit consistent header structures and one-to-one mapping relationships between field values (e.g., SMB2 requests and responses share header structures, and ProtocolID is constant in both, while Command fields correspond). DYNPRE identifies the field that appears most frequently across all inferred message formats. It then checks if this field exhibits an injective function f(Ms..e) -> Ms..e (a strong correlation). If found, this field is treated as a common field, and both request and response formats are refined by coupling their results. This process iterates until no further common fields can be identified. The first common field discovered is typically considered the message type field of the protocol due to the strong correspondence between request and response message types.

Scalability for Checksum Mechanisms

DYNPRE also addresses the challenge of checksums, which can render probe messages ineffective if modifications lead to verification failures. To improve scalability, DYNPRE integrates with delsum 1, an existing tool for checksum reverse engineering. It first uses delsum to infer the checksum algorithm, then automatically generates rewrite rules to recalculate the checksum before sending modified messages, as demonstrated successfully on the ICMP protocol.

Demo / Proof of Concept

▶ Watch: Refinement process and type inference for accuracy (4:00)

While the talk didn't feature a live, interactive demo, DYNPRE's capabilities were robustly demonstrated through its evaluation on real-world proprietary protocols used in IoT devices. This section served as a compelling proof-of-concept for its practical applicability.

The evaluation process for proprietary protocols involved three meticulous steps:

1. Input Message Construction: Researchers activated various behaviors on target IoT devices using their official applications, capturing the network traffic. These messages were labeled according to the triggered behaviors and used as input for DYNPRE.
2. Protocol Reverse Engineering: DYNPRE then interacted with the IoT devices, inferring the message format for each activated behavior through its dynamic inference mechanism. For devices employing encrypted communication, DYNPRE demonstrated its flexibility by decrypting traffic using the device's private key before analysis.
3. Application of Inferred Formats: Based on the inferred formats, new messages were programmatically generated. These messages were constructed using a structure-aware approach: constant fields remained unchanged, variable fields were populated with existing values or randomly modified, and random field deletions were also performed. These newly generated messages were then sent to the target devices.

The results were striking: the generated messages not only successfully triggered the original behaviors (e.g., turning a light on/off, brightening, creating groups, adding forbidden domains to a router) but also initiated additional behaviors that were never observed in the initial input traces. For example, from 7 original behaviors initially observed, the messages generated by DYNPRE's inferred formats triggered a total of 15 different behaviors. This effectively validated the accuracy and completeness of the formats inferred by DYNPRE. The talk specifically highlighted that the "behavior-determining bytes"—typically command fields or arguments—were consistently identified by DYNPRE as variable fields, underscoring its precise semantic understanding.

Case Study 1: Xiaomi Smart Camera

A detailed case study on the Xiaomi Smart Camera further elucidated DYNPRE's prowess in handling complex, real-world scenarios. During the camera's startup session, DYNPRE successfully identified two crucial session-specific identifiers in the Hello Response message: DeviceID and Stamp. The Stamp field, an increasing counter designed to prevent replay attacks, required a specific constraint: if the device assigned a value x to this field, the subsequent client request had to use x+1. DYNPRE accurately generated a rewrite rule for this, specifying the source (M12..15 in message ②), references (M12..15 in message ③), and the constraint y = x+1. The DeviceID field, a unique identifier, was also correctly handled, with DYNPRE adapting its rewrite behavior depending on whether the trace capture and learning devices were the same. This ability to detect and adapt to such intricate identifier constraints, including non-trivial arithmetic relationships, is paramount for maintaining live session validity and extracting profound semantic feedback.

Case Study 2: Yeelight Light

Another compelling example involved the Yeelight Smart Light. DYNPRE's analysis of a "brightening" message in hex format precisely identified the behavior-determining bytes. The second inferred field (blue background in Figure 10 from the paper) was correctly identified as the command field. By manipulating values in this field, DYNPRE could instruct the light to perform various actions, including turning on/off, brightening, and dimming. The fourth inferred field (orange background) was identified as the command arguments, which for the "set brightness" command carried the target brightness value. This precise identification allowed direct manipulation of the light's brightness. The speaker also noted that successfully detecting this field enables effective fuzzing by assigning abnormal values, such as those that could trigger integer overflow vulnerabilities, thus directly linking DYNPRE's output to practical security applications.

These demonstrations collectively illustrate DYNPRE's capability to operate as a black-box tool on undocumented, proprietary systems, yielding accurate and actionable protocol specifications that enable both understanding and active manipulation for security assessment.

Defensive Implications

▶ Watch: SMB2 example demonstrating traditional method limitations (4:15)

DYNPRE offers significant defensive implications for organizations and security professionals, particularly in an era dominated by proprietary protocols, IoT devices, and complex network infrastructures.

1. Enhanced Visibility for Undocumented Protocols: Many critical systems, especially in IoT, SCADA, or legacy enterprise environments, rely on undocumented or proprietary communication protocols. DYNPRE provides a powerful mechanism for organizations to gain black-box visibility into these protocols. This is crucial for:

• Supply Chain Security: Independently verifying the communication behavior of third-party devices and components, reducing reliance on potentially incomplete or absent vendor documentation.
• Risk Assessment: Understanding the attack surface of proprietary systems by precisely identifying command fields, arguments, and state transitions.

1. Improved Security Tooling: The accurate and semantically rich protocol models generated by DYNPRE directly enhance the effectiveness of various security tools:

• Fuzzing: DYNPRE's output enables the generation of structure-aware, legitimate, and state-aware inputs for fuzzing proprietary or complex protocols. This leads to more efficient discovery of vulnerabilities like integer overflows (as demonstrated with the Yeelight light) or buffer overflows, which are often missed by generic fuzzers.
• Intrusion Detection/Prevention Systems (IDPS): With precise protocol formats, defenders can develop more accurate signatures and behavioral rules for detecting anomalous or malicious traffic specific to their undocumented systems. This moves beyond simple byte patterns to semantic understanding.
• Formal Verification and Model Checking: DYNPRE's ability to infer protocol state machines provides the foundational input for formal verification, allowing critical systems to be rigorously analyzed for design flaws or logical vulnerabilities.
• Security Audits: Security teams can use DYNPRE to perform in-depth audits of proprietary applications, identifying potential weaknesses in message parsing or state handling that could be exploited.

1. Proactive Vulnerability Research: Security researchers can leverage DYNPRE to accelerate the discovery of vulnerabilities in widely deployed, yet opaque, systems. By quickly reverse engineering protocols, the time-to-exploit for newly discovered vulnerabilities can be reduced, allowing for faster defensive responses.

1. Addressing Stateful Protocol Vulnerabilities: DYNPRE's emphasis on correctly handling session-specific identifiers and state transitions highlights a critical area for defenders. Mismanagement or predictable generation of session IDs, sequence numbers, or other state-maintaining fields can lead to session hijacking, replay attacks, or other authentication bypasses. Understanding these mechanisms through DYNPRE's lens allows defenders to audit their implementations for robustness.

1. Checksums are Not a Panacea: The successful integration with delsum 1 to bypass checksum mechanisms for protocols like ICMP serves as a reminder that checksums, while providing data integrity, are not a security barrier against a determined attacker using sophisticated reverse engineering tools. Defenders should not rely on simple checksums as a primary security control for message authenticity or integrity against active probing.

In essence, DYNPRE empowers defenders by turning black-box protocols into transparent specifications, enabling a proactive and informed approach to securing complex and often undocumented network environments.

Key Takeaways

• DYNPRE is a novel, automatic, and black-box protocol reverse engineering tool that operates without requiring source code, binaries, or prior protocol knowledge.
• It overcomes the limitations of traditional static network trace analysis by actively interacting with the target server to generate diverse samples and directly infer field semantics.
• DYNPRE achieves significantly higher accuracy in both format and message type inference compared to state-of-the-art tools, demonstrating an average perfection score of 0.50 for field identification (3.3x improvement) and a V-measure of 0.94 for message type inference.
• The tool effectively handles complex session-specific identifiers (e.g., SMB2's SessionID, Xiaomi Camera's Stamp with y=x+1 constraint) and ensures proper interaction with stateful servers through dynamic message rewriting.
• DYNPRE's efficacy extends to real-world proprietary protocols in IoT devices, where it successfully inferred formats that not only replicated original behaviors but also unlocked previously unobserved functionalities (triggering 15 behaviors from 7 original ones).
• While DYNPRE incurs a performance overhead due to its dynamic interaction (averaging 259 minutes for 1000 messages and millions of exchanged messages), this is considered a worthwhile trade-off for the significantly more accurate and semantically rich understanding of target protocols, which is crucial for downstream security applications like fuzzing and vulnerability analysis.

About the Speaker(s)

Zhengxiong Luo is the presenter of DYNPRE, a novel approach to protocol reverse engineering via dynamic inference. The provided metadata and transcript indicate he is a researcher involved in this work, but do not offer specific details about his title, affiliation, or other biographical information.