Delta OTA: Binary Diff (bsdiff, VCDIFF) for Tiny Payloads

Why Binary Diffs Matter in Embedded OTA

A firmware update that changes three lines of application code still triggers a multi-megabyte transfer if you ship the whole image. For a device on a metered cellular plan, that's not a rounding error — it's the difference between a $0.02 update and a$2.00 one, multiplied across a fleet of 100,000 units. Binary diffing — computing the delta between an old image and a new one, then shipping only the delta — routinely cuts OTA payloads by 80–95% for typical point releases, because most of a firmware binary (bootloader, RTOS, static libraries, unchanged application logic) doesn't move between versions.

Bandwidth and storage constraints on IoT/embedded devices

Many embedded targets have 1–4 MB of flash total, with OTA staging requiring a second full-image slot (A/B partitioning). A 2 MB firmware image with a 50 KB delta means you can stage the update in a fraction of the spare flash a full-image scheme would need, which matters on parts where the second slot is the limiting BOM factor.

Cost of cellular/satellite OTA delivery

NB-IoT, LTE-M, and satellite links charge by the byte, and the charge is nonlinear with poor signal — retransmits on a weak link cost more than the nominal payload size. A 2 MB image at marginal SNR can balloon into 6–8 MB of actual radio transfer after retries; a 100 KB delta shrinks that tail risk proportionally.

Power consumption during download phases

Radio transmit/receive is often the single largest current draw in a battery-powered device's duty cycle. Shortening the download phase from minutes to seconds directly extends battery life between updates, which matters for devices that only wake for OTA checks on a scheduled interval.

Flash wear and write-cycle budgets

NOR and NAND flash have finite program/erase cycles (datasheet-specific — check the flash part's endurance rating). A full-image OTA erases and rewrites the entire update partition every release; a delta-based scheme writes only the changed sectors in the reconstructed image, which stretches the write-cycle budget over a longer product lifetime, especially for devices shipping weekly or biweekly patches.

bsdiff: Algorithm, Tradeoffs, and Implementation

Core algorithm: matching blocks, seek tables, and control blocks

bsdiff (Colin Percival, 2003) builds a suffix array over the old file to find long matching byte runs against the new file, then emits three streams: a control stream (copy/insert/seek lengths), a diff stream (byte-wise differences within matched blocks, which compress well because they're often small integers from pointer or offset shifts), and an extra stream (literal bytes for genuinely new content). The three streams are each independently compressed (classically with bzip2), which is why bsdiff output is small even though the raw control/diff data isn't.

Compression ratios on typical firmware binaries

For point releases that touch application code but leave the RTOS, drivers, and bootloader untouched, bsdiff patches of 1–5% of the original image size are common. The ratio depends heavily on whether the compiler/linker produces stable addresses between builds — see the entropy discussion below.

Memory footprint during patch generation and application

Suffix-array construction is the expensive part: bsdiff's reference implementation needs roughly 17–20x the old file's size in RAM during patch generation. That's a non-issue on a CI build server but means you never run bsdiff generation on the device itself. Patch application is lighter but still typically needs the full old image, the full new image, and the patch simultaneously addressable — fine for a build server, tight for a microcontroller with 256 KB of RAM, which is why on-device bsdiff application usually streams through flash rather than loading everything into RAM.

When bsdiff excels and its limitations

bsdiff shines when old and new binaries are structurally similar with localized changes — typical of iterative firmware releases. It struggles when a toolchain upgrade or compiler flag change shifts every function's address by a few bytes, since that turns a one-line source change into a binary that differs almost everywhere. It also doesn't understand instruction encodings, so it can't exploit the fact that a branch-offset change is "the same" edit repeated at every call site — that's a job for specialized binary-diff preprocessors, not vanilla bsdiff.

Integration with embedded build systems

Patch generation belongs as a post-build CI step, invoked after both the previous release artifact and the new build are available. This fits naturally into the stages described in CI Pipeline Stages: Build → Static Analysis → Unit Test → Deploy: the delta job runs after the build stage produces a signed binary and before the deploy stage publishes update artifacts.

VCDIFF (RFC 3284): Streaming and Format Efficiency

VCDIFF window-based encoding for large binaries

VCDIFF processes input in windows rather than requiring the whole file in memory at once, which is the key structural difference from bsdiff. Each window encodes copy/add/run instructions referencing a source window (old file) and target window (new file) within a bounded size, so an encoder/decoder can process a multi-megabyte binary without holding it all in RAM simultaneously.

Interleaved and non-interleaved output formats

VCDIFF supports an interleaved format (instructions, addresses, and data mixed in a single stream, favored by tools like open-vcdiff's "xdelta3"-compatible mode for streaming decode) versus non-interleaved (separate streams, better for secondary compression ratio but requiring more buffering). For an embedded decoder, interleaved format is usually the right choice because it lets the patch applier consume the delta sequentially without seeking.

Secondary compressors (Huffman, LZMA integration)

RFC 3284 defines the instruction format but leaves secondary compression open; implementations commonly layer zlib, LZMA, or a simple Huffman stage on top of the VCDIFF instruction stream. This separation lets you trade decoder complexity for ratio — pure VCDIFF with no secondary compression decodes fast and simple, while VCDIFF+LZMA gets closer to bsdiff ratios at the cost of a heavier decoder.

Lower memory requirements for patch application

Because of windowed processing, a VCDIFF decoder can apply a patch while streaming the old image from flash and writing the new image to flash, holding only one window (often a few KB, tunable) in RAM at a time. This is the main reason VCDIFF (or tools like xdelta3 and open-vcdiff that implement it) shows up more often than bsdiff on RAM-constrained MCUs, even when bsdiff would produce a marginally smaller patch.

Standardization benefits and tool ecosystem

VCDIFF being an RFC means multiple independent implementations (Google's open-vcdiff, xdelta3's compatible mode, various embedded ports) interoperate on the wire format, reducing vendor lock-in for your patch toolchain compared to bsdiff's single reference implementation and informal format.

Patch Generation in CI/CD Pipelines

Automating delta generation between firmware versions

A typical pipeline step: pull the previous N released binaries from artifact storage, compute a delta from each to the new candidate, and publish all deltas alongside the full image. This ties directly into Artifact Management: Firmware Binaries, Checksums, Metadata — deltas are artifacts too, and need the same checksum and metadata discipline as full binaries, including which exact (from-version, to-version) pair each delta applies to.

for base in $(cat supported_base_versions.txt); do
  bsdiff "artifacts/fw-${base}.bin" "artifacts/fw-${new}.bin" \
         "deltas/fw-${base}_to_${new}.bsdiff"
  sha256sum "deltas/fw-${base}_to_${new}.bsdiff" >> deltas/manifest.sha256
done

Storing base-image and delta artifacts

You need every base image you intend to support deltas from, not just the latest — a device stuck three versions behind still needs a path forward. Retention policy for old base images becomes a storage planning question, not just a CI afterthought.

Version compatibility matrices and validation

Maintain an explicit matrix of which (from, to) pairs have been generated, tested, and verified to reconstruct byte-identical to the target image via hash comparison in CI — never trust a delta that hasn't been round-tripped (apply patch to base, hash result, compare to target hash) as part of the pipeline before it's published.

Incremental vs. full-binary fallback strategies

Don't support unbounded delta chains from every historical version — cap it (e.g., last 5–10 releases) and fall back to full-image OTA for anything older. This keeps the compatibility matrix and artifact storage from growing unbounded, and it's a reasonable backlog item to track explicitly; teams managing this under Agile Methodology: Sprint, Backlog, Scrum, Kanban often treat "delta matrix maintenance" as a recurring chore ticket each sprint rather than a one-time setup.

On-Device Patch Application and Verification

RAM constraints: streaming vs. in-memory patching

On an MCU with limited RAM, patch application must stream: read a chunk of old image from flash slot A, read the corresponding delta instructions, write reconstructed bytes to flash slot B, repeat. This is natural for VCDIFF's windowed format; bsdiff application can also be adapted to stream if the control/diff/extra streams are consumed incrementally rather than decompressed wholesale into RAM — check whether your bsdiff port does this before assuming it fits your RAM budget.

CRC and cryptographic hash validation of deltas

Validate the delta itself (CRC32 or SHA-256 over the downloaded patch file) before applying it, and separately validate the reconstructed image (SHA-256 against an expected hash shipped in the update manifest) after applying it and before marking the new partition bootable. Two checks, two different failure modes caught: corrupted transfer versus a bad patch/base combination.

Rollback safety and atomic swap mechanisms

Never patch the currently-running image in place. Apply the delta into the inactive A/B slot, verify the hash, then flip the boot pointer atomically. If verification fails at any stage, the bootloader must fall back to the last known-good slot — this is the same atomic-swap discipline used for full-image OTA, just with an extra verification step for the delta-to-base relationship.

Minimal-footprint patching libraries for embedded systems

Look for libraries explicitly designed for constrained targets (e.g., detools, or stripped-down VCDIFF decoders) that document their RAM footprint in KB, not assume a desktop-oriented reference implementation will port cleanly — the generation-side bsdiff reference, in particular, is not suitable for on-device use.

Practical Payload Reduction: Benchmarks and Trade-offs

Real-world compression ratios: bsdiff vs. VCDIFF vs. raw gzip

Don't take published ratios as gospel — binary similarity between your specific old and new builds, not the algorithm in the abstract, dominates the outcome. Run both bsdiff and a VCDIFF implementation against your actual release pairs and measure; the relative ranking can flip depending on whether your changes are localized or address-shifting. Raw gzip/LZMA on the full new image, with no diffing at all, is the baseline to beat — sometimes it's surprisingly close if the firmware has large recompressible static tables.

Binary similarity analysis and entropy considerations

Compiled binaries with non-deterministic builds (embedded timestamps, randomized symbol ordering, non-reproducible builds) destroy delta efficiency because the diff algorithm sees spurious differences everywhere. Reproducible builds are a prerequisite for good delta ratios, not just a nice-to-have.

Patch size vs. patch generation time vs. device RAM

Smaller patches (bsdiff, often) cost more CI compute time and more generation-side RAM; streaming-friendly formats (VCDIFF) cost a bit more patch size but let the device apply with a tiny RAM footprint. Pick based on which resource is scarcer in your system — CI compute is usually cheap and elastic, device RAM is fixed by the part you already shipped.

When to use delta vs. full OTA

Fall back to full-image OTA when: the delta exceeds some fraction (commonly 50–70%) of the full image size, meaning the binary has changed too much for diffing to help; the device is too many versions behind for a supported delta chain to exist; or the delta-application verification fails twice in a row, in which case continuing to retry a possibly-corrupt delta path is worse than just shipping the full image once.

Integration with Secure Boot and Signing

Signing deltas vs. reconstructed binaries

Sign the full reconstructed image's hash, not the delta file itself, as the thing secure boot ultimately trusts. The delta is signed too (so the device can reject a tampered patch before wasting flash cycles applying it), but the chain of trust that matters for boot is the post-reconstruction hash matching what the manufacturer actually built and tested — the same workflow described in Binary Signing: GPG Sign, Hash Verification of Releases applies here, just with an extra reconstruction step inserted before the final hash check.

Hash verification workflows in constrained environments

A constrained device can usually afford one SHA-256 over the final reconstructed image even if it can't afford to hold two full images in RAM simultaneously — compute the hash incrementally as each flash sector is written during patch application, rather than re-reading the whole image afterward.

Preventing rollback attacks on delta chains

A delta that reconstructs a valid, signed, but older firmware version is a classic downgrade attack vector — the bootloader must check a monotonic version counter (not just signature validity) before accepting the reconstructed image, exactly as it should for full-image updates.

Storage of signing keys in CI infrastructure

Delta generation doesn't change your key management model, but it does add a dependency: the CI job that signs the reconstructed-image hash needs both the new build and the chosen base image available at signing time, which means the signing step in your pipeline has to run after delta validation (round-trip hash check) succeeds, not in parallel with it.