Recovering bzip2 blocks: which bytes survive corruption?

The location of damage changes the recovery result

We generated one 320,000-byte payload, compressed it with bzip2 -1c, and made five damaged copies. Four mutations flip exactly one bit; the fifth truncates the file inside its third compressed block. The unchanged file supplies a control. All operations use bzip2 and bzip2recover 1.0.8 on the recorded Linux build.

For every copy, we run whole-file integrity testing and decompression, then bzip2recover. Every resulting candidate is separately tested and decoded. A fragment counts below only when both commands succeed and its bytes exactly match one original block. The original payload is the reference, not a checksum calculated from the damaged file.

Candidate creation is not validation. The recovery command exits zero in all six cases, including those with invalid candidates. A successful split does not mean every output file is sound or that the original object is complete. These six deliberately chosen cases do not estimate a real-world recovery rate.

A broken delimiter can affect its neighbor

The manual describes independently handled blocks, 48-bit boundary patterns and a CRC per block. It explicitly separates extracting candidates with bzip2recover from testing them with bzip2 -t. [1, section 2.6]

The release source explains the two-block effect. Its scanner finds marker patterns and takes the intervening bit ranges as candidates. Corrupting the second block's marker removes the delimiter after block 1 as well as the recognizable start of block 2. The scanner emits one invalid candidate spanning that region, followed by valid candidates for blocks 3 and 4. [2, bzip2recover.c, boundary scan]

This is a limit of the tested scanning-and-validation path, not proof that both blocks are irretrievably lost. Only one marker bit was changed; a different repair method with sufficient evidence could do better. Likewise, our block-CRC mutation changes a checksum, not the payload, but strict validation still rejects that candidate. A failed checksum does not identify which side of the comparison is wrong.

Why a bad stream checksum can leave every block intact

The library checks decoded block CRCs and accumulates a combined stream CRC. The recovery writer wraps each candidate as a separate bzip2 stream, using its stored block CRC for the new one-block trailer. It does not preserve the original stream-wide validation context. [2, bzlib.c and bzip2recover.c]

Flipping only the combined CRC therefore makes the original stream fail, while all four reconstructed one-block streams validate. Joining their decoded output reproduces our original payload exactly. The independent byte comparison establishes completeness in this experiment; successful local CRC checks alone would not establish that no original block was missing.

The original stream checksum can accept a different block order

The salvage cases above deliberately damage a block or its framing. A second experiment keeps all compressed blocks intact and changes their order inside one stream. This tests a different question: can successful block checks and the original final check establish the original object?

Native bzip2 1.0.8 compressed a deterministic 3,250,000-byte input into one 33-block stream with bzip2 -1c. We exchanged the complete encoded blocks at positions 1 and 33, retaining the header, all block bits and the original trailer. No stored checksum was recalculated. Compressed length remained 3,276,204 bytes; decoded length also stayed unchanged, but an exact comparison with the original input failed.

The small-memory native decoder agreed. Python's single-stream decoder also reached EOF with zero unused bytes for the accepted exchange, so this is not a reader stopping at the first of several concatenated streams. Output from rejected cases is recorded, never counted as valid recovery; those returned lengths are implementation observations, not a promised valid prefix.

Why the distance is 32 blocks

The release source rotates a 32-bit accumulator left by one bit, then XORs the next decoded block CRC into it. The decoder checks that accumulated value against the stored stream CRC. If R is that rotation and b_i is block i's CRC, the combination is: [2, compress.c and bzlib.c]

C_0 = 0
C_i = R(C_(i-1)) XOR b_i
C_n = XOR over i=1..n of R^(n-i)(b_i)

Because 32 rotations restore a 32-bit word, positions separated by 32 blocks have equal weights. Exchanging their CRC contributions leaves the final value unchanged for any two CRCs. The same reasoning applies to distances that are multiples of 32 when block count and other blocks stay fixed. No individual block-checksum collision has to be found.

This is a property of the combination operation, not the polynomial period of the per-block CRC and not a CRC over concatenated decoded bytes. Our distance-1 and distance-31 controls fail, but that does not prove every shorter exchange is detected: particular CRC values can still cancel. The CRC analysis explains why error patterns and protection scope matter. RFC 3385 likewise conditions error probabilities on the model; its iSCSI rates do not measure this designed permutation. [3]

Validate content together with position

A trusted digest of the complete original byte sequence detects the demonstrated reordering. A block manifest needs to bind object identity, generation, position, length and content digest; an unordered collection of valid block hashes does not establish the original order. Authenticate that reference where tampering is in scope. A digest stored beside mutable data is not automatically trusted.

Where storage-system evidence agrees, and where it stops

Bairavasundaram and colleagues separated checksum mismatches from block-identity discrepancies in their FAST 2008 production-storage study. The system checked file membership and offset during file reads; its RAID scrub could not perform that filesystem-context check. The authors observed identity discrepancies that checksums alone had not detected. [4, sections 2.2-2.3 and 5.1]

The engineering connection is to validate bytes in their expected context. This is an analogy between protection boundaries, not evidence that the study's disks suffered bzip2 permutations. Its support-log population, selective logging and incomplete knowledge of scrub coverage cannot estimate this experiment's real-world frequency. [4, section 3.2]

These are source-derived synthetic examples, not a measured fault rate or a claim of a newly discovered vulnerability. Retained runs from two builds of bzip2 1.0.8, including an upstream UBSan build, agree semantically; they are not independent codec implementations. The current system replay also agrees.

The CC0 order experiment, system observations, retained source-build observations, tests and source hashes and locators make this result inspectable. Keep both result JSON files beside the script and tests to run the suite. The byte-exact input oracle is generated independently from the recorded SHAKE-256 seed.

python3 probe.py --check results-system.json
python3 -m unittest -v test_probe.py
python3 -O -m unittest -v test_probe.py

Do not turn missing intervals into adjacent records

After the block-data mutation, the verified sequence is blocks 1, 3 and 4. Blind concatenation removes 99,980 bytes from the middle. In that output, the first byte of block 3 moves from original offset 199,961 to offset 99,981. An application sees adjacent bytes where the original had a gap.

A compressed block is not automatically a record, archive entry or database page. Even exact fragment bytes need application-level interpretation. Preserve fragments, their order, validation results and known missing intervals separately. If a length or location is unknown, retain that uncertainty; do not invent a zero-filled region and label it recovered data.

Our four decoded block lengths are 99,981, 99,980, 99,981, 20,058 bytes. The -1 setting is a block-size parameter, not a promise of exactly 100,000 original bytes per recovered file. The implementation's block limit and run-length processing make that shortcut unsafe. [1, section 2.5] [2, bzlib.c]

We know the original intervals because the pristine split reconstructs the independently generated input. Real recovery may lack that reference. The tool's numbered candidate files and compressed-bit positions do not supply an uncompressed offset map or a trustworthy missing-byte count.

A practical recovery record

1. Preserve the original compressed object and work on a copy in a separate directory. If the medium itself is failing, first establish an acquisition strategy; this experiment starts from available file bytes.
2. Record tool versions, input identity, candidate order and each validation outcome. Keep rejected output separate from validated fragments.
3. Compare available length, digests and record inventory against independently retained expectations. Do not calculate a new digest of the fragments and treat it as evidence of their original completeness.
4. Report partial salvage separately from a complete restore, then check the recovered application's structure and meaning.

The related ddrescue analysis addresses acquisition provenance; archive validation and dependencies addresses completed decoding and member selection. This experiment adds the intervening question: which damaged-file fragments can still be validated?

Reproduce the six fixtures

The CC0 reproduction script requires Python 3, bzip2 and bzip2recover. It accepts no external archive or device: it creates bounded synthetic files in a private temporary directory and refuses to overwrite an existing result file.

python3 bzip2-salvage.py --output bzip2-results.json

The full observation JSON records exact mutation offsets, candidate bit ranges, return statuses, byte counts, hashes, original-block matches, gaps, executable identity and generation time. The input recipe is fixed, with no random seed. Run the control tests alongside the script. The bzip2 corpus record links the mechanism to reusable definitions.

These observations establish behavior for one fixture family and recorded executables. They do not establish a fault distribution, optimal block size, security guarantee or probability of recovering a real archive. CRCs are not cryptographic authentication. Bytes returned by a command that fails are recorded but never counted as validated salvage.

Primary sources

1. Julian Seward. bzip2 and libbzip2 1.0.8: sections 2.3, 2.5 and 2.6 (recovery).
2. bzip2 1.0.8 official source release: bzip2recover.c, bzlib.c and compress.c.
3. RFC 3385, sections 1-2: CRC error-model assumptions (Informational).
4. Bairavasundaram et al. An Analysis of Data Corruption in the Storage Stack. FAST 2008, sections 2.2-2.3, 3.2 and 5.1.