2008 · Conference paper
Tupni: Automatic Reverse Engineering of Input Formats
Tupni infers an input format from an execution trace of an x86 program parsing one input, using byte-level dynamic taint tracking. It segments the input into fields from the instructions that operate on tainted bytes, finds record sequences from parsing loops, groups records into types by the code that handles them, and emits an enhanced BNF grammar with length, value and some inter-message constraints. Grammars from several inputs can be merged into a more complete specification. The evaluation covers five file formats (WMF, BMP, JPG, PNG, TIF) and five network protocols (DNS, RPC, TFTP, HTTP, FTP), and the output is used for zero-day vulnerability signature generation with ShieldGen.
Scope and limitations
Tupni needs the parsing program and a recorded execution trace for every input; it does not work from captured traffic or files alone. The prototype combined iDNA traces with a re-implemented Vigilante taint engine, and the traces came from Windows XP SP2 binaries such as gdi32.dll, gdiplus.dll, nslookup.exe and IIS components. Single-input accuracy uses one input per format, scored by the authors against published specifications; WMF, DNS and HTTP guided the design, compressed image data was skipped in favor of container structure, and no quantitative baseline was run because earlier tools were unavailable. All record sequences were found, with some false-positive sequences, and 889 of 1,551 PNG fields were misidentified because the program ignored repeated chunk data. Coverage depends on input diversity, constraints can be specific to the samples, byte-level taint handles fields that do not align with bytes poorly (including many encrypted or compressed formats), and formats beyond regular expressions are out of scope. Inter-message constraints were evaluated only for TFTP, and multi-input aggregation only on 150 WMF files.
Why it fits this collection
Adds a classic execution-based input-format inference method that recovers record sequences, record types and field constraints, complementing the collection’s traffic-based and binary-assisted protocol-format research.
Publication and review details
- Venue
- ACM CCS 2008
- Status
- Conference paper
- Publication / posting date
- October 27, 2008
- Date source
- ACM’s Crossref deposit records print and online publication on 2008-10-27, and an archived copy of the ACM article page shows the same date. The CCS meeting dates are not substituted.
- DOI
- 10.1145/1455770.1455820
Crossref and the archived ACM page give the five authors in this order, CCS ’08 pages 391–402, and the main title “Tupni” with subtitle “automatic reverse engineering of input formats”; the record uses the paper’s capitalization. The text was reviewed in the 12-page copy on the Microsoft Research publication page, whose byline spells the fifth author “Luiz Irun-Briz”; the record follows the ACM and Crossref spelling. The paper states that the prototype has 14,000 lines of C++ and 4,100 lines of Perl outside Vigilante and iDNA, and it links no code or data; the Windows test binaries and the 150 WMF files from an internal Microsoft repository are not public artifacts. No code or experiments were run.
Sources reviewed
Source review only; experiments were not rerun for this collection. Cite the original authors using the linked paper or BibTeX.
Primary sources
- https://dl.acm.org/doi/10.1145/1455770.1455820
- https://web.archive.org/web/20250206195542/https://dl.acm.org/doi/10.1145/1455770.1455820
- https://api.crossref.org/works/10.1145/1455770.1455820
- https://dl.acm.org/doi/pdf/10.1145/1455770.1455820
- https://www.microsoft.com/en-us/research/publication/tupni-automatic-reverse-engineering-of-input-formats/
- https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tupni-ccs08.pdf