PaperlayerView exact revision on arXiv

Source-linked AI summary

SEMPRE: Semantic-Aware Protocol Reverse Engineering via Consistency-Driven Joint Optimization

Yihua Xu, Weijie Huang, Xiaofeng Wang, Hang Zhang, Binghui Wang, Yue Duan

arXiv:2610.31844v1cs.CR

TL;DR

PRE must recover message structures and field semantics despite brittle rules, weak modeling of neighboring-field dependencies, and difficulty with nested protocols. SEMPRE combines dynamic program analysis with recursive LLM reasoning and iterative joint refinement. Across evaluated protocols, it reports stronger field-detection and semantic-inference results than prior tools, and demonstrates utility on Mirai traffic.

  • Problem

    Existing PRE methods rely on brittle rules, under-model dependencies among neighboring fields, and struggle to recover nested protocols.

    Source: B. Motivation · p. 3, §VI · p. 13

  • Method

    SEMPRE grounds recursive LLM reasoning in dynamic taint and loop traces, then iteratively refines field boundaries and semantics using high-confidence predictions as constraints.

    Source: §I · p. 2, A. Overview · p. 4

  • Results

    SEMPRE achieves average F1 scores of 0.76 for field detection and 0.72 for semantic inference, compared with no baseline above 0.4 and 0.14 for BinPRE, respectively.

    Source: §I · p. 3

  • Takeaways & Limitations

    SEMPRE also accurately recovers undocumented fields and semantics in Mirai botnet traffic.

    Source: §VII · p. 13

    SEMPRE supports only six semantic function labels and annotates at byte granularity, limiting recovery of finer-grained bit-level semantics.

    Source: §VI · p. 13

Abstract

from arXiv · show

Protocol reverse engineering (PRE) is essential for understanding undocumented or proprietary communication formats, enabling security-critical tasks such as vulnerability discovery, malware C2 analysis, and IDS signature generation. However, existing PRE techniques rely on brittle hand-written rules, under-model contextual dependencies among neighboring fields, and often fail on messages with nested sub-protocols. We present SEMPRE, a fully automated PRE framework that replaces ad-hoc heuristics with recursive LLM reasoning grounded in fine-grained dynamic program analysis. SEMPRE uses taint-flow and loop traces to guide an LLM-driven tree-of-thought search that slices messages into fields while detecting nested sub-payloads, producing a hierarchical layout. It then infers each field's type and role and iteratively refines boundaries by freezing high-confidence segments and re-running detection under semantic constraints, yielding an EM-style procedure that monotonically improves structure and semantics until convergence. Evaluated on a broad corpus of mainstream protocols against six state-of-the-art (vs. <0.4 for all baselines) and 0.72 for semantic inference (vs. 0.13 for BinPRE). Ablations confirm the contribution of each component, and a case study on a prolific real-world botnet demonstrates practical utility.

I. INTRODUCTION

SEMPRE addresses fragile PRE methods by jointly inferring field boundaries and semantics, including hierarchical structure for nested payloads. The introduction frames PRE as recovering message structure and field meaning when protocol specifications are unavailable, incomplete, or proprietary.

A. Problem Statement

  • PRE seeks to identify message-field boundaries and infer each field’s type and role when specifications are unavailable, incomplete, or proprietary.It supports security tasks including malware C2 analysis, vulnerability discovery, and IDS signature generation.Source: §I · p. 1

I. INTRODUCTION

  • Existing binary-analysis methods rely on hand-crafted rules, often isolate fields from contextual dependencies, and can flatten nested protocols into layouts that obscure protocol-layer boundaries.These limitations can make filename detection brittle and leave multi-layer payloads only partially recovered.Source: §I · p. 2
  • SEMPRE combines fine-grained dynamic analysis with recursive LLM reasoning, iteratively using semantic predictions to refine field boundaries and boundary hypotheses to support semantic inference.The framework also recursively detects nested payloads and formalizes refinement as a monotonic process that converges to a local optimum.Source: §I · pp. 2–3
  • SEMPRE achieves average F1 scores of 0.76 for field detection and 0.72 for semantic inference, versus no baseline above 0.4 and 0.14 for BinPRE, respectively.The evaluation compared SEMPRE with six state-of-the-art tools across popular protocols.Source: §I · p. 3

A. Problem Statement

  • The problem statement models field detection as choosing a complete, ordered segmentation of byte intervals and semantic inference as assigning each field a type or function label.The evaluation reuses BinPRE’s vocabulary of five types and six semantic functions for comparison.Source: A. Problem Statement · p. 3

B. Motivation

The motivating examples expose three gaps in existing PRE: rigid heuristics, weak modeling of cross-field dependencies, and inadequate handling of nested protocols. SEMPRE uses execution evidence and joint inference to address them.

Inflexible Heuristics-Based Rules

  • BinPRE’s filename heuristic misses the TFTP value “pxelinux.cfg/C0” because it excludes a slash permitted by the protocol specification.SEMPRE instead grounds semantic hypotheses in dynamic execution evidence, supporting generalization to unseen but specification-compliant values.Source: B. Motivation · p. 3

Ignorance of Semantic Relationships

  • Length–Value dependencies link fields: byte[4] specifies a two-byte payload, while byte[2–3] encodes the total message length.These constraints can reduce ambiguity in field boundaries and semantic labels.Source: B. Motivation · p. 4
  • BinPRE labels byte[4] locally and splits byte[2–3] into two length fields, missing constraints that SEMPRE uses to refine boundaries and labels jointly.A boundary error around a length field can distort downstream layout, while a semantic error can discard constraints needed for segmentation.Source: B. Motivation · p. 4

Insufficient Handling of Nested Protocols

  • An EtherNet/IP message can embed one or more CIP messages; the example’s CIP sub-payload spans byte[46–81], nearly half the message.Each embedded CIP message has its own field layout and semantics.Source: B. Motivation · p. 4
  • Existing tools may stop at the outer header/payload boundary or flatten the message, whereas SEMPRE explicitly targets nested protocols through recursive inference.Either approach can leave the embedded protocol unanalyzed or missegment its fields and labels.Source: B. Motivation · p. 4

III. SYSTEM DESIGN AND IMPLEMENTATION

SEMPRE combines dynamic execution evidence with LLM-based field detection and semantic inference. Its stages use per-message taint and loop traces, structured search, and iterative semantic constraints to produce a stable annotated layout.

A. Overview

  • SEMPRE alternates field detection and semantic inference, feeding high-confidence labels back as constraints until the joint objective stops improving.The process operates on each message independently and produces a stable, semantically annotated layout.Source: A. Overview · p. 4

B. Pre-processing

  • Taint analysis tracks which instructions access, propagate, or transform input bytes, while loop detection links repeated processing to message bytes to expose variable-length fields and size relationships.These execution traces provide evidence for segmenting a message into fields.Source: B. Pre-processing · p. 5

C. Field Detection

  • Tree-of-Thoughts search explores candidate field boundaries using taint, loop, and semantic cues, scoring and pruning inconsistent segmentations before selecting a lowest-cost complete path.SEMPRE evaluates candidates against coverage of tainted bytes, structural or semantic constraints, and protocol-pattern plausibility.Source: C. Field Detection · pp. 5–6
  • When a potential sub-payload is identified, SEMPRE recursively applies its field-detection procedure to that region until no further sub-payloads remain.The detector uses the message, taint and loop information, and any inferred semantics; semantic labels are empty on the first iteration.Source: C. Field Detection · pp. 5–6

D. Semantic Inference

SEMPRE treats semantic inference as structured search over field interpretations, using contextual constraints and corpus priors. High-confidence labels then constrain subsequent joint rounds of field detection and semantic inference.

D. Semantic Inference

  • A field’s type and function can depend on neighboring fields and message-level constraints, so semantic inference is not an independent label assignment.A putative length field, for example, constrains how the succeeding payload must be parsed.Source: D. Semantic Inference · p. 6
  • SEMPRE uses Tree-of-Thoughts to explore candidate type–function paths, scoring constraint consistency and corpus priors and pruning incoherent paths with branch-and-bound.The search proceeds in sliding windows of five fields.Source: D. Semantic Inference · p. 7
  • Paths below a calibrated cost threshold are marked high-confidence, and their labels become constraints for the next field-detection and semantic-inference iteration.The coupled process progressively converges on a globally coherent interpretation.Source: D. Semantic Inference · p. 7

E. Joint Optimization

SEMPRE alternates field detection and semantic inference, retaining high-confidence predictions as constraints to refine both. Its analysis characterizes stabilization as a conditional stable fixed point, not unconditional convergence to an optimum.

E. Joint Optimization

  • High-confidence field and semantic predictions become constraints for the next iteration, and SEMPRE repeats refinement until it judges further optimization unnecessary.Each iteration detects provisional fields, infers semantic labels, and selects high-confidence predictions to fix; the process can restart if it has not converged within its limit.Source: E. Joint Optimization · p. 7

F. Analysis of Iterative Refinement

  • Stabilization is conditional: SEMPRE’s stochastic LLM stages do not guarantee convergence for arbitrary executions.The analysis relies on a finite candidate space, reliable retained constraints, and refinements that do not decrease the consistency objective.Source: F. Analysis of Iterative Refinement · pp. 7–8
  • Semantic constraints such as reliable length–payload relationships can reduce ambiguity in field detection, while refined boundaries constrain semantic inference.This reciprocal constraint is the intended basis for consistency-preserving refinement.Source: F. Analysis of Iterative Refinement · p. 8
  • The refinement process reaches a stable fixed point when neither consistency improvement nor growth in reliable constraints continues.The analysis characterizes this stable state, rather than claiming local or global optimality.Source: F. Analysis of Iterative Refinement · p. 8

IV. EVALUATION

The evaluation tests SEMPRE’s effectiveness, robustness, component contributions, and performance on real-world malware protocols. Its setup uses multiple protocol datasets, annotated message fields, and field-level and semantic metrics.

IV. EVALUATION

  • The evaluation asks whether SEMPRE detects fields and infers semantics effectively, generalizes across LLM knowledge and backbones, benefits from each component, and handles malware protocols.These questions define the evaluation’s five research questions.Source: §IV · p. 8

A. Experimental Setup

  • The study compares SEMPRE with six PRE techniques spanning network-traffic-based and binary-analysis-based approaches.The baselines are PolyGlot, Tupni, AutoFormat, BinPRE, BinaryInferno, and DynPRE.Source: A. Experimental Setup · p. 8
  • The evaluation covers eight widely used protocols, three undocumented protocols, and Mirai as a botnet-protocol case study.The protocol datasets are D1, D2, and D3, respectively.Source: A. Experimental Setup · p. 8
  • Ground truth records byte-level field boundaries and one type and function label per field, cross-validated against Wireshark dissections.Some fields lack type or function labels where the taxonomy is insufficient or documentation conflicts with Wireshark interpretation.Source: A. Experimental Setup · p. 9
  • Field detection and semantic inference are evaluated with precision, recall, and F1, using field-level boundary correctness for detection.Type and function outcomes are assessed against ground-truth labels, with per-field results aggregated for semantic metrics.Source: A. Experimental Setup · p. 9

B. RQ1: Effectiveness on Field Detection

SEMPRE achieves the strongest reported field-detection results across the evaluated protocols and also outperforms the compared tools on semantic inference. Its performance remains strong without LLM prior knowledge and with a different backbone model.

B. RQ1: Effectiveness on Field Detection

  • 0.76 F1 is a 95% improvement over BinPRE’s 0.39 for field detection across eight protocols.SEMPRE correctly identifies 4,822 of 6,465 ground-truth fields, 933 more than the runner-up.Source: Figure 9 · p. 9, B. RQ1: Effectiveness on Field Detection · p. 9
  • SEMPRE’s field-detection advantage has two minor exceptions: BinPRE scores 1.00 versus SEMPRE’s 0.99 on Modbus, and AutoFormat has higher precision on DNP3.For DNP3, SEMPRE uses less than 10% of the taint- and loop-analysis data under API input-length constraints, yet attains approximately 0.80 F1.Source: B. RQ1: Effectiveness on Field Detection · p. 9

C. RQ2: Effectiveness on Semantic Inference

  • SEMPRE outperforms BinPRE on type inference across evaluated protocols and all baselines on function inference, with boundary errors contributing to weaker results on some protocols.TFTP type inference is comparatively lower at 0.3542; S7comm, EIP, and HTTP function inference scores are 0.64, 0.67, and 0.70, respectively.Source: C. RQ2: Effectiveness on Semantic… · p. 10

D. RQ3: Robustness and Generalization

  • SEMPRE-zero still significantly outperforms BinPRE on most protocols, and SEMPRE with DeepSeek-v3.1-terminus remains comparable to GPT-o3 and beats BinPRE.DNP3 is the zero-prior-knowledge exception because input-length limits truncate taint context; on undocumented protocols, SEMPRE also consistently outperforms BinPRE and vanilla GPT-o3, except for comparable KTP performance.Source: D. RQ3: Robustness and Generalization · pp. 10–11

E. RQ4: Ablation Study

The ablation study examines recursive sub-payload detection and iterative optimization on a small-scale dataset. Both components contribute to field detection and semantic inference, while tree-of-thought alone does not improve performance.

E. RQ4: Ablation Study

  • The ablation uses a cost-efficient small-scale dataset containing the first 10 messages from each protocol.It examines recursive sub-payload detection and iterative optimization.Source: E. RQ4: Ablation Study · p. 11
  • 0.76 average field-detection F1 with recursive detection exceeds 0.58 without recursive detection or iterative optimization.The component notably improves Ethernet/IP from 0.37 to 0.71 and HTTP from 0.39 to 0.62, while DNS drops from 1.00 to 0.77.Source: E. RQ4: Ablation Study · p. 11, Table VII · p. 12
  • Iterative optimization raises average type-inference F1 to 0.62 and function-inference F1 to 0.74.With optimization removed, the corresponding scores are 0.56 and 0.58; adding it further boosts performance from the no-recursion/no-optimization configuration.Source: E. RQ4: Ablation Study · p. 11, Table VI · p. 11
  • On nested Ethernet/IP, SEMPRE detects 483 correct fields versus 176 without sub-payload detection.This comparison is reported as evidence for recursive detection’s contribution on nested protocols.Source: E. RQ4: Ablation Study · pp. 11–12, Table VIII · p. 12
  • Removing tree-of-thought degrades F1 from 0.76/0.62/0.74 to 0.71/0.50/0.56, although tree-of-thought alone does not improve performance.The study concludes that recursive sub-payload detection and iterative optimization are essential for high performance.Source: E. RQ4: Ablation Study · p. 12

F. RQ5: Case Study

SEMPRE is evaluated on Mirai traffic and situated among PRE and LLM reasoning approaches. The discussion identifies reliability, byte-level semantics, and adversarial robustness as limitations.

F. RQ5: Case Study

  • In the Mirai case study, SEMPRE recovered perfectly accurate boundaries for 9 of 10 messages, while BinPRE did so for 2.BinPRE's single-pass assumption is broken by Mirai's repeated buffer parsing; its F1 reaches 0.55 when given a two-pass hint, while SEMPRE remains at 0.83.Source: F. RQ5: Case Study · p. 12

A. Protocol Reverse Engineering

  • PRE spans traffic-based and binary-analysis approaches; BinPRE represents a strong binary-analysis baseline, while earlier tools provide limited semantic information.Traffic-based methods identify recurring patterns in traces; binary-analysis methods inspect program input processing.Source: A. Protocol Reverse Engineering · pp. 12–13

B. LLM Reasoning Techniques

  • SEMPRE grounds tree search in execution evidence, addressing ToT's assumption that each reasoning step is a clean natural-language fragment.The paper also grounds iterative self-critique in taint maps and loop inventories rather than free-form text judgment.Source: B. LLM Reasoning Techniques · p. 13

VI. DISCUSSION

  • Tree-of-Thoughts and iterative refinement improve LLM effectiveness, but cannot entirely eliminate hallucination and reliability limitations.The discussion also notes that LLMs can struggle with consistency across long or complex reasoning chains.Source: §VI · p. 13
  • SEMPRE's six semantic function labels and byte-granularity annotation limit recovery of finer bit-level meanings, such as distinct CAN flags.The authors identify bit-level taint tracking, semantic inference, and a richer function taxonomy as future work.Source: §VI · p. 13
  • Obfuscation that randomizes field-access order or copies data into scratch buffers can blur taint signals and defeat ToT search.The authors leave addressing this adversarial setting for future research.Source: §VI · p. 13

VII. CONCLUSION

  • SEMPRE attains field-detection F1 of 0.76 and semantic-inference F1 of 0.72 across eight mainstream protocols, and the conclusion reports effective recovery on Mirai traffic.The Mirai case study reports 0.83 field-detection F1 with or without a two-pass hint, compared with 0.55 for BinPRE given the hint.Source: F. RQ5: Case Study · p. 12, §VII · p. 13

APPENDIX

The appendix describes SEMPRE's prompt inputs and field-detection instructions, and outlines ethical considerations around security use, privacy, and misuse.

ETHICAL CONSIDERATIONS

  • SEMPRE's potential security benefits include vulnerability discovery, malware analysis, and IDS signature generation, while protocol reconstruction could also enable attacks on users.The paper says experimental data come from open-source repositories or legally captured traffic, with sensitive identifiers anonymized.Source: ETHICAL CONSIDERATIONS · p. 14

A. Prompt Design

  • Structured prompts provide taint and loop-analysis outputs, the raw message, high-confidence semantic cues, and explicit reasoning instructions to constrain task-specific context.The authors state that this structure reduces hallucinations and improves consistency across runs.Source: A. Prompt Design · p. 17

1) The Prompt Template: Field Detection

  • The field-detection template directs the LLM to use execution-record offsets as initial fields, then apply Tree-of-Thoughts to predict fields one by one.The instructions specify a search depth of five and a strict zero-background mode for the listed protocols.Source: 1) The Prompt Template: Field Detection · p. 17, Figure 10 · p. 17

2) The Conversation for Field Detection:

SEMPRE uses separate LLM interactions for field detection and semantic inference, with semantic labels feeding iterative boundary refinement and recursive parsing of sub-payloads.

2) The Conversation for Field Detection:

3) The Prompt Template: Semantic Inference:

4) The Conversation for Semantic Inference:

  • Each iteration updates fields and semantic labels; taint evidence and consistency rules guide predictions, while detected protocol sub-payloads are parsed recursively.The semantic-inference interaction uses prior iteration labels and returns updated fields, types, and functions.Source: 4) The Conversation for Semantic… · p. 17

B. Tables

The appendix provides definitions for common semantic labels, compares tools on example protocols, and describes the evaluation datasets.

C. Common Types and Functions

1) Results from Different Tools:

2) Details for Protocol in Datasets:

  • The dataset table describes protocol-message formats as binary, text, or mixed, and identifies the resources for each protocol binary.The table also marks incorrect field detection, unsupported cases, and nested sub-payload detection.Source: 2) Details for Protocol in Datasets · p. 18, Table XV · p. 18

3) Semantic Capabilities of the Baselines:

The tables compare semantic capabilities across PRE systems, report SEMPRE's performance across backbones and on undocumented protocols, and detail function-inference results with a message-coverage caveat for DynPRE.

3) Semantic Capabilities of the Baselines:

4) Tables Related to RQ3:

5) Tables Related to RQ2:

Related papers

Loading 2610.31844v1…