morluto/rea

Fork 0

mirror of https://github.com/morluto/rea.git synced 2026-11-05 06:45:22 +00:00

[GH-ISSUE #3621] [Feature] Unknown binary file-format inference: structure hypotheses, offset/length fields, checksums, and Kaitai Struct reconstruction #1348

New issue

Open

opened 2026-10-16 21:04:33 +00:00 by bsakaguchi · 0 comments

bsakaguchi commented

2026-10-16 21:04:33 +00:00

Owner

Originally created by @matbrgz on GitHub (Oct 14, 2026).
Original GitHub issue: https://github.com/morluto/rea/issues/3621

Summary

The fundamental mission of REA is "Reverse Engineer Anything". While REA possesses specialized static analyzers for recognized formats (ELF, PE, Mach-O, ASAR, PCAP, SQLite), reverse engineers, security researchers, and digital preservationists frequently encounter completely unknown, undocumented proprietary binary formats: custom game archives, proprietary industrial telemetry streams, custom embedded databases, IoT sensor logs, and proprietary file containers.

Currently, reverse engineering an unknown binary format is a tedious, manual process: analysts inspect hex dumps, calculate Shannon entropy, test endianness, hypothesize header fields, search for offset tables and length prefixes, test checksum algorithms, and manually write a parser.

This feature proposal introduces Automated Unknown Binary File-Format Inference to REA. Given an unknown binary file (or a small corpus of related sample files), REA will statistically analyze byte distributions, generate and test structural hypotheses (headers, versions, offset pointers, length fields, record arrays, string pools, and checksums), and reconstruct an executable, human-readable Kaitai Struct (.ksy) specification and parser.

Technical Capabilities & Inference Pipeline

                                    +-----------------------------------------+
                                    | Input: Unknown Binary File(s) (.dat,etc)|
                                    +--------------------+--------------------+
                                                         |
                                                         v
                                     +---------------------------------------+
                                     | 1. Byte Entropy & Primitive Profiling |
                                     | (Endianness, floats, ints, strings)   |
                                     +-------------------+-------------------+
                                                         |
                                                         v
                                     +---------------------------------------+
                                     | 2. Header & Magic Signature Discovery |
                                     | (Magic FourCC, file-size correlation) |
                                     +-------------------+-------------------+
                                                         |
                                                         v
                                     +---------------------------------------+
                                     | 3. Pointer & Length Field Correlation |
                                     | (Seek offsets, chunk lengths, TLVs)   |
                                     +-------------------+-------------------+
                                                         |
                                                         v
                                     +---------------------------------------+
                                     | 4. Array, Record & TOC Inference      |
                                     | (Stride analysis, string pools, TOC)  |
                                     +-------------------+-------------------+
                                                         |
                                                         v
                                     +---------------------------------------+
                                     | 5. Checksum & Hash Inversion          |
                                     | (CRC16/32, Adler32, sum8/16/32, MD5)  |
                                     +-------------------+-------------------+
                                                         |
                                                         v
                                     +---------------------------------------+
                                     | 6. Kaitai Struct (.ksy) Synthesis     |
                                     | & Validated Parser Generation (TS/Py) |
                                     +---------------------------------------+

1. Statistical Byte-Level Profiling & Primitive Typing

Shannon Entropy Mapping: Compute sliding-window Shannon entropy (H) to delineate distinct byte regions:
- Dense compressed / encrypted blocks (H \ge 7.2).
- Structured tabular records & pointer tables (H \approx 3.0 - 5.5).
- Text, string tables, and markup (H \approx 2.0 - 4.5).
- Null-padded / zero-fill regions (H \approx 0.0).
Endianness Hypothesis Testing: Statistically test 16-bit, 32-bit, and 64-bit scalar words under Little-Endian and Big-Endian interpretations, scoring plausibility based on alignment, value ranges, and monotonic progression.
Scalar Type Inference: Discriminate between unsigned/signed integers, IEEE 754 floating-point numbers (f4, f8), bitmasks/flags, and string encodings (ASCII, UTF-8, UTF-16LE, UTF-16BE).

2. Header & Magic Signature Discovery

Magic Byte Identification: Detect initial signature patterns (FourCC printable characters, e.g. RIFF, FORM, BINA, or fixed recurring hex words).
Header Field Hypotheses:
- File Size Verification: Detect integers matching exact file size (L), file size minus header (L - H_{size}), or payload size.
- Version & Revision Detection: Detect common versioning patterns (e.g. major/minor byte pairs, integers 1, 2, 100, or SemVer strings).
- Header Size / Data Offset: Identify fields that point directly to the end of the header or the start of the primary payload.

3. Pointer & Length Field Correlation (Offsets & TLVs)

Pointer Discovery: Scan candidate scalar integers to locate values that represent byte offsets within the file:
- Absolute file offsets (pos == value).
- Header-relative or section-relative offsets (pos == header_offset + value).
- Monotonically increasing offset chains indicating sequential file chunks.
Length Field Discovery: Correlate candidate integers with the byte difference between consecutive offset pointers (length[i] == offset[i+1] - offset[i]).
Tag-Length-Value (TLV) Chunking: Detect repeating sequences of [Tag: u2/u4][Length: u2/u4][Value: bytes], isolating chunk hierarchies and block IDs.

4. Table of Contents (TOC), Array & Record Repetition Detection

Stride & Autocorrelation Analysis: Use autocorrelation and discrete Fourier analysis over byte variance to detect recurring struct record lengths (e.g. array of repeating 24-byte structs).
Table of Contents (TOC) / File Index Reconstruction: Identify centralized index tables that contain lists of file entries with (offset, size, name_pointer, flags).
String Pool & Name Table Carving: Detect contiguous blocks of null-terminated strings or length-prefixed (Pascal) strings, correlating external table indices/offsets with string positions.

5. Checksum & Hash Inversion

Systematically test candidate 8-bit, 16-bit, 32-bit, and 128/256-bit fields against potential data ranges using standard algorithms:
- CRCs: CRC-8, CRC-16 (CCITT, ANSI), CRC-32 (IEEE 802.3, Castagnoli).
- Checksums: Additive sum (8, 16, 32-bit), XOR fold, Adler-32, Fletcher-16/32.
- Cryptographic Hashes: Match candidate 16-byte, 20-byte, or 32-byte fields against MD5, SHA-1, and SHA-256 hashes of preceding chunks.

6. Kaitai Struct (.ksy) Synthesis & Parser Generation

Declarative YAML Generation: Synthesize a clean, fully commented Kaitai Struct (.ksy) schema:
- meta: id, endian (le/be), file-extension.
- seq: sequence of discovered header and body fields.
- types: defined custom substructs for records, table entries, and chunks.
- instances: seek-based expressions (pos: offset, size: length) to model non-contiguous tables and payload pointers.
- enums: inferred enumeration values for discovered tag/type fields.
Automated Validation: Test-compile the generated .ksy schema against the input binary, verifying that the inferred parser parses the binary with zero out-of-bounds or alignment exceptions.
Target Code Generation: Provide exports of the generated parser in TypeScript, Python, Rust, and C++.

Acceptance Criteria

Introduce infer_binary_format in REA CLI and MCP contracts, accepting arbitrary binary inputs.
Accurately detect endianness, header boundaries, and candidate magic numbers on synthetic and real-world unknown fixtures.
Identify offset pointer arrays and correlate them with chunk sizes in structured evidence.
Detect and verify standard CRC32, Adler32, and checksum fields when present.
Output a valid, schema-compliant Kaitai Struct (.ksy) file that compiles without errors and parses the target file.
Provide unit and regression tests covering fixed-record arrays, TLV chunks, and string pool containers.

#743 [Feature] Recover .NET NativeAOT metadata in Ghidra workflows
#3599 [Feature] Passive DNS extraction and cybersecurity analysis primitives
#3615 [Feature] Hardware and Embedded Reverse Engineering
docs/firmware-analysis.md

Originally created by @matbrgz on GitHub (Oct 14, 2026). Original GitHub issue: https://github.com/morluto/rea/issues/3621 [![Type: Feature](https://img.shields.io/badge/type-feature-blue.svg?style=flat-square)](https://github.com/morluto/rea) [![Domain: Game & Engine RE](https://img.shields.io/badge/domain-game_&_engine_RE-green.svg?style=flat-square)](https://github.com/morluto/rea) [![Status: Proposed](https://img.shields.io/badge/status-proposed-blue.svg?style=flat-square)](https://github.com/morluto/rea) [![Ecosystem: REA](https://img.shields.io/badge/ecosystem-morluto%2Frea-8A2BE2.svg?style=flat-square)](https://github.com/morluto/rea) ## Summary The fundamental mission of REA is **"Reverse Engineer Anything"**. While REA possesses specialized static analyzers for recognized formats (ELF, PE, Mach-O, ASAR, PCAP, SQLite), reverse engineers, security researchers, and digital preservationists frequently encounter completely unknown, undocumented proprietary binary formats: custom game archives, proprietary industrial telemetry streams, custom embedded databases, IoT sensor logs, and proprietary file containers. Currently, reverse engineering an unknown binary format is a tedious, manual process: analysts inspect hex dumps, calculate Shannon entropy, test endianness, hypothesize header fields, search for offset tables and length prefixes, test checksum algorithms, and manually write a parser. This feature proposal introduces **Automated Unknown Binary File-Format Inference** to REA. Given an unknown binary file (or a small corpus of related sample files), REA will statistically analyze byte distributions, generate and test structural hypotheses (headers, versions, offset pointers, length fields, record arrays, string pools, and checksums), and reconstruct an executable, human-readable **Kaitai Struct (`.ksy`)** specification and parser. --- ## Technical Capabilities & Inference Pipeline ``` +-----------------------------------------+ | Input: Unknown Binary File(s) (.dat,etc)| +--------------------+--------------------+ | v +---------------------------------------+ | 1. Byte Entropy & Primitive Profiling | | (Endianness, floats, ints, strings) | +-------------------+-------------------+ | v +---------------------------------------+ | 2. Header & Magic Signature Discovery | | (Magic FourCC, file-size correlation) | +-------------------+-------------------+ | v +---------------------------------------+ | 3. Pointer & Length Field Correlation | | (Seek offsets, chunk lengths, TLVs) | +-------------------+-------------------+ | v +---------------------------------------+ | 4. Array, Record & TOC Inference | | (Stride analysis, string pools, TOC) | +-------------------+-------------------+ | v +---------------------------------------+ | 5. Checksum & Hash Inversion | | (CRC16/32, Adler32, sum8/16/32, MD5) | +-------------------+-------------------+ | v +---------------------------------------+ | 6. Kaitai Struct (.ksy) Synthesis | | & Validated Parser Generation (TS/Py) | +---------------------------------------+ ``` ### 1. Statistical Byte-Level Profiling & Primitive Typing - **Shannon Entropy Mapping:** Compute sliding-window Shannon entropy ($H$) to delineate distinct byte regions: - Dense compressed / encrypted blocks ($H \ge 7.2$). - Structured tabular records & pointer tables ($H \approx 3.0 - 5.5$). - Text, string tables, and markup ($H \approx 2.0 - 4.5$). - Null-padded / zero-fill regions ($H \approx 0.0$). - **Endianness Hypothesis Testing:** Statistically test 16-bit, 32-bit, and 64-bit scalar words under Little-Endian and Big-Endian interpretations, scoring plausibility based on alignment, value ranges, and monotonic progression. - **Scalar Type Inference:** Discriminate between unsigned/signed integers, IEEE 754 floating-point numbers (`f4`, `f8`), bitmasks/flags, and string encodings (ASCII, UTF-8, UTF-16LE, UTF-16BE). ### 2. Header & Magic Signature Discovery - **Magic Byte Identification:** Detect initial signature patterns (FourCC printable characters, e.g. `RIFF`, `FORM`, `BINA`, or fixed recurring hex words). - **Header Field Hypotheses:** - **File Size Verification:** Detect integers matching exact file size ($L$), file size minus header ($L - H_{size}$), or payload size. - **Version & Revision Detection:** Detect common versioning patterns (e.g. major/minor byte pairs, integers `1`, `2`, `100`, or SemVer strings). - **Header Size / Data Offset:** Identify fields that point directly to the end of the header or the start of the primary payload. ### 3. Pointer & Length Field Correlation (Offsets & TLVs) - **Pointer Discovery:** Scan candidate scalar integers to locate values that represent byte offsets within the file: - Absolute file offsets (`pos == value`). - Header-relative or section-relative offsets (`pos == header_offset + value`). - Monotonically increasing offset chains indicating sequential file chunks. - **Length Field Discovery:** Correlate candidate integers with the byte difference between consecutive offset pointers (`length[i] == offset[i+1] - offset[i]`). - **Tag-Length-Value (TLV) Chunking:** Detect repeating sequences of `[Tag: u2/u4][Length: u2/u4][Value: bytes]`, isolating chunk hierarchies and block IDs. ### 4. Table of Contents (TOC), Array & Record Repetition Detection - **Stride & Autocorrelation Analysis:** Use autocorrelation and discrete Fourier analysis over byte variance to detect recurring struct record lengths (e.g. array of repeating 24-byte structs). - **Table of Contents (TOC) / File Index Reconstruction:** Identify centralized index tables that contain lists of file entries with `(offset, size, name_pointer, flags)`. - **String Pool & Name Table Carving:** Detect contiguous blocks of null-terminated strings or length-prefixed (Pascal) strings, correlating external table indices/offsets with string positions. ### 5. Checksum & Hash Inversion - Systematically test candidate 8-bit, 16-bit, 32-bit, and 128/256-bit fields against potential data ranges using standard algorithms: - **CRCs:** CRC-8, CRC-16 (CCITT, ANSI), CRC-32 (IEEE 802.3, Castagnoli). - **Checksums:** Additive sum (8, 16, 32-bit), XOR fold, Adler-32, Fletcher-16/32. - **Cryptographic Hashes:** Match candidate 16-byte, 20-byte, or 32-byte fields against MD5, SHA-1, and SHA-256 hashes of preceding chunks. ### 6. Kaitai Struct (.ksy) Synthesis & Parser Generation - **Declarative YAML Generation:** Synthesize a clean, fully commented **Kaitai Struct (`.ksy`)** schema: - `meta`: `id`, `endian` (le/be), `file-extension`. - `seq`: sequence of discovered header and body fields. - `types`: defined custom substructs for records, table entries, and chunks. - `instances`: seek-based expressions (`pos: offset`, `size: length`) to model non-contiguous tables and payload pointers. - `enums`: inferred enumeration values for discovered tag/type fields. - **Automated Validation:** Test-compile the generated `.ksy` schema against the input binary, verifying that the inferred parser parses the binary with zero out-of-bounds or alignment exceptions. - **Target Code Generation:** Provide exports of the generated parser in **TypeScript**, **Python**, **Rust**, and **C++**. --- ## Acceptance Criteria 1. Introduce `infer_binary_format` in REA CLI and MCP contracts, accepting arbitrary binary inputs. 2. Accurately detect endianness, header boundaries, and candidate magic numbers on synthetic and real-world unknown fixtures. 3. Identify offset pointer arrays and correlate them with chunk sizes in structured evidence. 4. Detect and verify standard CRC32, Adler32, and checksum fields when present. 5. Output a valid, schema-compliant **Kaitai Struct (`.ksy`)** file that compiles without errors and parses the target file. 6. Provide unit and regression tests covering fixed-record arrays, TLV chunks, and string pool containers. --- ## Related - #743 [Feature] Recover .NET NativeAOT metadata in Ghidra workflows - #3599 [Feature] Passive DNS extraction and cybersecurity analysis primitives - #3615 [Feature] Hardware and Embedded Reverse Engineering - docs/firmware-analysis.md

bsakaguchi referenced this issue

2026-10-17 21:10:37 +00:00

[PR #1348] [MERGED] docs: explain CI scope and native runner reuse #2816

No milestone

No project

No assignees

1 participant

Notifications

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference

morluto/rea#1348

No description provided.

Rows
Columns