Paper Reading: FIBER — Finding Binaries for Patch Verification

FIBER: Identifying and Verifying Missing Security Patches in Firmware (USENIX Security ‘18)

Paper

Key Contribution

FIBER defines a new category of patch presence test: “source to binary” — a middle ground between pure source-level and pure binary-level approaches. It leverages available source patches to generate fine-grained binary signatures, rather than comparing entire functions.

Approach: Source-Binary Matching

Inspired by how a human analyst would manually verify a patch, FIBER operates in three phases:

Phase 1: Change Site Analysis (source level)

Analyze the source patch and pick the most suitable change sites for signature generation. A good change site should be:

• Unique: exists only in the patched version (e.g., a newly added branch conditional or function call). If the change is just a replacement of an existing statement, FIBER excludes it.
• Stable: not affected by other irrelevant code changes. Solution: keep the change site as small as possible so it survives unrelated code evolution.
• Easy-to-recognize: rank changes by statement type for how well they translate to binary:
  • noinline function call — best; directly locatable via symbol table.
  • branch conditionals — good; introduces both structural (CFG) and semantic changes.
  • arithmetic operations (a=b*c) — least preferred; semantic-only change, rarely affects CFG structure.

Additional selection criteria (ranked least → most important): distance to function entrance, function size (smaller = less noise), and change type.

Phase 2: Binary Signature Generation

Compile the reference source with debug info, then translate the selected source change into a binary signature:

• Map source change sites to binary instructions using DWARF debug info.
• Build a local CFG around the change site (Steiner tree approximation — excludes unrelated code, more robust than full-function CFG).
• Identify root instructions: the last instructions in each data-flow chain whose outputs are not consumed by other instructions within the signature. These summarize the key semantics.
  • Example: for ADD X0, X3, X4; CMP X0, X2; BGT label1; — CMP is root (its comparison result drives BGT); ADD is intermediate (consumed by CMP). The root captures the essential data-flow semantic.
  • Root types by statement: call/push (function call), cmp + conditional jmp (conditional), mov/add/sub/mul (assignment), jmp/ret (control transfer).
• Annotate root instructions with semantic formulas (AST expressions) mapping operands back to source-level variables (function params, local vars, return values, immediates). Uses symbolic execution on the reference binary.
• Validate: test the generated signature against both patched and unpatched reference binaries. A valid signature must match the patched version and NOT match the unpatched version.

Phase 3: Matching Engine (on target binary)

Locate the affected function in the target binary (via symbol table), then search for the signature in two passes:

• Quick pass (structural/syntactic):
  • Match CFG topology of the signature as a subgraph of the target function’s CFG.
  • Match basic block exit types (conditional jump, call, return, etc.).
  • Match root instruction types within each basic block.
  • Fast but may produce false positives (no semantic analysis yet).
• Slow pass (semantic):
  • For each candidate from the quick pass, generate semantic formulas for root instructions via symbolic execution.
  • Recursively compare the ASTs with relaxations (e.g., commutative operators, Z3 simplification).
  • Gives a definitive yes/no answer, not a similarity score.

Evaluation

Single dataset only: Android kernel images. No other domains tested.

Dataset

• Reference: Google’s open-source “angler” kernel (v3.10, Nexus 6P). 107 CVE security patches collected from Android Security Bulletin (June 2016 – May 2017).
• Targets: 8 Android kernel images from 3 vendors:
  • Samsung S7 (kernels 0–3, 102 patches each, Qualcomm platform)
  • LG G5 (kernels 4–5, 103 patches each, Qualcomm platform)
  • Huawei P9 (kernels 6–7, only 30–31 patches applicable — different hardware platform, Kirin, so many device-driver patches don’t apply)
• Total tests: ~800 patch presence decisions (107 patches × 8 kernels, minus inapplicable ones).

Accuracy

Kernel	Device	Patches	TP	TN	FP	FN (rate)
0–3	Samsung S7	102	42–92	4–56	0	4–6 (3.92–5.88%)
4–5	LG G5	103	32–95	0–65	0	6–8 (5.88–7.77%)
6	Huawei P9	31	10	20	0	1 (3.23%)
7	Huawei P9	30	25	2	0	3 (10.00%)

• 0 false positives across all kernels — the key claim.
• FN rate 3.23–10%. Root causes of false negatives (manually inspected):
  1. Function inlining differences across compilers/binaries.
  2. Function prototype changes (parameter reordering, rare).
  3. Code customization by vendors — context statements differ, breaking signature match.
  4. Patch adaptation — vendors backport or adapt patches differently.
  5. Angr frontend bugs (2 cases).

Performance

• Offline (one-time per patch):
  • Change site analysis: 107 patches in 21.5s (0.2s avg)
  • Signature translation: 293 signatures in 1608s (5.5s avg)
  • Signature validation against reference kernels: ~6000s total (9–12s avg per signature)
• Online (per target kernel):
  • ~70% of patches matched in <10s each
  • Average 12–23s per patch across kernels
  • Worst case: ~1047s (CVE-2017-0521, very large/complex function)

Unported Patches Found

Found 9 CVEs that vendors failed to port timely, including:

• Critical: CVE-2016-2184, CVE-2016-7910, CVE-2016-10200 (privilege escalation, RCE)
• One patch delayed >6 months at a major vendor (anonymized).
• 4 vulnerabilities eventually patched in later releases but not in the earliest available after the patch date.

Case Studies

5 qualitative cases showing robustness to challenges that binary-only tools would fail on:

• Format string change (CVE-2016-6752): %p → %pK. FIBER dereferences the string pointer to compare content.
• Small change site (CVE-2016-8417): > → >=. Only one conditional jump instruction differs. FIBER catches it via root instruction semantics.
• Patch backport (CVE-2016-3858): downstream has a prior upstream patch not in reference. FIBER’s fine-grained signature is robust because it targets only the specific patch.
• Multiple patched function versions (CVE-2014-9785): target function significantly diverged. FIBER still locates the change site.
• Constant change (CVE-2015-8944): argument changed from 0 to S_IRUSR (0x100). FIBER figures out only the 2nd argument matters.
• Similar basic blocks: local CFG + function-level semantics disambiguate blocks that look alike at basic-block level.

What’s Missing

• No ablation study: quick pass and slow pass are only evaluated as a combined pipeline. No numbers on quick-pass-only accuracy or slow-pass-only cost.
• No direct comparison with other tools: no benchmarks against BinDiff, Genius, Gemini, or any binary-only approach. The paper argues these are complementary (bug search = coarse filter, FIBER = precise verifier), but provides no quantitative comparison.
• Single domain: only Android kernel images. No evaluation on user-space binaries, IoT firmware, or other OSes.

Limitations

NOTE: these limitations are just my own inferences based on the paper’s design.

• Requires symbol tables in target binaries (available in Android kernels, but not always elsewhere).
• Currently supports only C code; needs DWARF debug info for reference compilation.
• Cross-vendor code customization and function inlining differences can cause false negatives.
• Implemented in Python on top of Angr (~5k LOC); supports x86 and AArch64 via VEX IR.