Reverse Engineering Undocumented Binary Database Storage Formats

You inherit a 4GB .dat file from a proprietary industrial system built in 1998. Vendor bankrupt, source code lost, Windows NT 4.0 host failed. File contains two decades of production data needed by Monday.

Without documentation, binary database files look like noise. Byte streams follow logical rules: engine manages space allocation, tracks record offsets, ensures byte alignment, maintains fast lookup paths.

Decode unknown binary database layout with systematic approach: structural byte inspection, pattern recognition, differential analysis. Parse unknown headers, reconstruct slotted pages, read raw records without specs.

Phase 1: Analyzing Macro Layout and Header Bytes

Every database file starts with metadata. Understand file structure before reading records.

Open binary file in hex editor (xxd, ImHex, r2). Focus on first 512 bytes.

00000000: 5351 4c69 7465 2066 6f72 6d61 7420 3300  SQLite format 3.
00000010: 1000 0101 0040 2020 0000 0001 0000 0004  .....@  ........
00000020: 0000 0000 0000 0000 0000 0001 0000 0004  ................

Inspect initial header block for three elements:

Magic Bytes and Signature Strings

Offset 0x00 contains string markers (SQLITE3, PGSQL) or hex patterns (0x44 0x42 0x46 0x48 / DBFH). If no ASCII string exists, identify consistent non-zero hex values across multiple sample files.

Block and Page Size Indicators

Storage engines divide files into fixed-size chunks matching OS disk allocation units. Common page sizes are powers of two: 512, 1024, 2048, 4096, 8192, 16384 bytes. Scan offsets 0x0A through 0x20 for 2-byte or 4-byte integers. Hex 4096 appears as 0x1000 (big-endian) or 0x0010 (little-endian). Hex 8192 appears as 0x2000 or 0x0020.

Endianness Detection

Find numbers representing total file size or page count. File size 1,048,576 bytes with page size 4096 equals 256 pages (0x0100). Search header for 0x00000100 (big-endian) versus 0x00010000 (little-endian).

Python script to inspect candidate integers:

import struct
 
def inspect_header(file_path):
    with open(file_path, 'rb') as f:
        header = f.read(64)
    
    print(f"Magic String (ASCII): {header[:16]}")
    
    be_uint16 = struct.unpack('>H', header[16:18])[0]
    le_uint16 = struct.unpack('<H', header[16:18])[0]
    be_uint32 = struct.unpack('>I', header[16:20])[0]
    le_uint32 = struct.unpack('<I', header[16:20])[0]
    
    print(f"Offset 16 - BE uint16: {be_uint16}, LE uint16: {le_uint16}")
    print(f"Offset 16 - BE uint32: {be_uint32}, LE uint32: {le_uint32}")
 
inspect_header('legacy_data.db')

If file size divided by page size has zero remainder, page boundary size is valid.

Phase 2: Decoding Page Architecture and Pointer Tables

Disk layouts organize data into independent pages containing page header, record pointers, payload data. Understanding page structures is fundamental when working with low-level storage engines or analyzing database locks mechanics across row, page, and table levels.

Slotted-page architecture is industry standard. Data records and pointer arrays grow toward each other to maximize space utilization.

+===================================================================+
| Page Header (Flags, Transaction ID, Free Space Offset, Slot Count)|
+===================================================================+
| Offset 0 | Offset 1 | Offset 2 | ...                              |  <- Slot Array (Grows Down)
+===================================================================+
|                         Unallocated Space                         |
+===================================================================+
| ... | Record 2 Payload | Record 1 Payload | Record 0 Payload     |  <- Tuple Area (Grows Up)
+===================================================================+

Analyzing page block (0x1000 to 0x2000):

1. Page Header Flags: First 8 to 24 bytes state page type. Root Pages (0x01), Interior B-Tree Pages (0x02), Leaf Pages (0x05), Overflow Pages (0x0A).
2. Slot Pointer Array: Following header, array of 2-byte integers contains byte offsets pointing to record start positions.
3. Record Count: 2-byte field near byte 2 or 4 dictates slot pointer array entry count.

Array [0x0F80, 0x0F20, 0x0EA0] at byte offset 0x1010 shows engine places records near end of 4096-byte page (0x1000 - 0x0080 = 0x0F80), growing backward toward header.

Phase 3: Parsing Record Payloads and Column Data

Extract field values from raw record payload using page slot pointers.

Record byte layouts: fixed-width fixed-offset schemas or variable-length packed schemas.

Fixed-Width Column Layouts

Legacy binary databases enforce strict field widths. Record allocates 4 bytes for integer ID, 32 bytes for null-padded ASCII name, 8 bytes for double float timestamp.

Scan for repeating byte lengths across multiple records. Locate string end markers and null-padding (0x00 or 0x20 spaces).

Variable-Length Varint Layouts

Variable-byte representations (varints) encode integers; length headers prefix strings.

Integer encoding schemes:

• 7-bit Continuation Encoding: Highest bit (0x80) signals extra bytes. Bit 7 set: read next byte. Bit 7 clear: stop.
• Length Prefix Encoding: Fields start with 1-byte or 2-byte length marker.

Python decoder for variable-length integers:

def read_varint(buffer, offset):
    value = 0
    shift = 0
    bytes_read = 0
    
    while True:
        if offset + bytes_read >= len(buffer):
            raise IndexError("Buffer overflow while reading varint")
            
        byte = buffer[offset + bytes_read]
        bytes_read += 1
        
        value |= (byte & 0x7F) << shift
        shift += 7
        
        if not (byte & 0x80):
            break
            
    return value, bytes_read
 
data = bytes([0xAC, 0x02])
val, consumed = read_varint(data, 0)
print(f"Decoded value: {val}, Bytes consumed: {consumed}")

Null Bitmaps

Null bitmap at record header flags empty columns. Table with 8 columns uses single byte at start. Bit 3 zero: column 3 skipped during payload traversal.

Phase 4: Differential Analysis (Black Box Technique)

When static inspection fails due to compression or packing, use differential binary analysis. Controlling input software controls output byte deltas on disk.

[State A: Insert "Alice"] -> Save File A
                                  |
                                  v  Run Binary Diff (cmp / radare2)
                                  |
[State B: Insert "Alicia"] -> Save File B

Workflow to isolate schema rules:

1. Initialize Baseline: Create fresh database with single record (Name: AAAAAAAA, Age: 20). Save as base.db.
2. Mutate One Scalar Variable: Change 20 to 21. Save as mutate_age.db. Run cmp -l base.db mutate_age.db. Modified byte offsets reveal location, length, byte order of Age column.
3. Expand String Lengths: Change AAAAAAAA to AAAAAAAAA. Save as mutate_string.db. Observe length header changes and slot array offset shifts.
4. Identify Transaction Headers: Save twice without modifications. Changing bytes indicate write counters, timestamps, Log Sequence Numbers (LSN). Ignore volatile offsets during field parsing.
5. Delete Records: Delete row and inspect header. Check if engine zeroes payload or decrements slot count.

Phase 5: Reconstructing B-Trees and Navigating Indexes

Databases order records using B-Tree or B+Tree structures to enable efficient lookups, a fundamental concept when optimizing PostgreSQL query performance on large scale tables.

B+Tree file format:

• Leaf Pages: Store record tuples or record IDs.
• Interior Pages: Store router keys paired with child page pointer numbers.

To traverse index tree, start at root page (page 0 or 1). Read page header flags to verify interior node type.

Interior page byte block key-pointer pairs:

+============+============+============+
| Child Page ID (uint32)| High Key Length/Data  | Child Page ID (uint32)|
+============+============+============+
| 0x00000004            | "Customer_1000"       | 0x00000009            |
+============+============+============+

Target key less than "Customer_1000": jump offset to Page ID 4 (4 * Page_Size). Higher: follow Page ID 9. Repeat until landing on Leaf Page.

Handle overflow pages when text strings exceed payload limits (larger than quarter page size). Engine moves string to dedicated overflow page, replacing inline field with 4-byte overflow page pointer.

Phase 6: Writing Native Extractor

Build parser using Rust async zero-copy deserialization or memory-mapped files (mmap) in Python.

Python parser using mmap slices pages without pulling binary file into RAM:

import mmap
import struct
 
class LegacyDBParser:
    def __init__(self, file_path, page_size=4096):
        self.page_size = page_size
        with open(file_path, "rb") as f:
            self.mm = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)
 
    def get_page(self, page_index):
        start = page_index * self.page_size
        end = start + self.page_size
        return self.mm[start:end]
 
    def parse_leaf_page(self, page_index):
        page = self.get_page(page_index)
        page_type, slot_count = struct.unpack(">BH", page[0:3])
        
        if page_type != 0x05:
            return
            
        slots = []
        for i in range(slot_count):
            slot_offset = 3 + (i * 2)
            record_ptr = struct.unpack(">H", page[slot_offset:slot_offset+2])[0]
            slots.append(record_ptr)
            
        print(f"Page {page_index} contains {len(slots)} record slots.")
        
        for ptr in slots:
            rec_len = page[ptr]
            string_data = page[ptr+1 : ptr+1+rec_len]
            print(f"Record at {hex(ptr)}: {string_data.decode('latin-1', errors='replace')}")
 
    def close(self):
        self.mm.close()
 
parser = LegacyDBParser("legacy_data.db")
parser.parse_leaf_page(1)
parser.close()

Isolated parsing prevents invalid pointer offsets on corrupted pages from breaking extraction runs, avoiding silent failures similar to how bounding database reads broke primary application features.

Summary Checklist

1. Verify page dimensions: Divide file size by potential page boundaries (512 to 65536 bytes).
2. Find pointer arrays: Locate offset lists near page start pointing to targets at page end.
3. Map endianness: Compare header size values against big-endian and little-endian unpack results.
4. Isolate values with diffs: Capture byte deltas before and after modifying origin values.
5. Handle varints and pointers: Test fields for continuation flags; identify parent/child page pointers.
6. Stream extraction through memory maps: Parse using offset slices directly.