Pith. sign in

REVIEW 3 major objections 8 minor 26 references

Data Flows in You: Benchmarking and Improving Static Data-flow Analysis on Binary Executables

T0 review · 3 major / 8 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A new benchmark of 277,072 compiled binaries shows static data-flow analyses are far less accurate than assumed, and three targeted model extensions raise the best engine from 0.39 recall/0.13 precision to 0.99 recall/0.32 precision.

desk verdict Useful benchmark and honest engine comparison, but the near-perfect recall claim rests on an incomplete dynamic ground truth and a selection aligned with the proposed extensions. read the letter →

arxiv 2506.00313 v1 pith:H6WJDQAK submitted 2025-05-30 cs.CR

Nicolaas Weideman , Sima Arasteh , Mukund Raghothaman , Jelena Mirkovic , Christophe Hauser This is my paper
classification cs.CR
keywords binarydata-flowanalysisstaticbenchmarkingaliasclassesdynamicgroundtruthvulnerabilitydiscoveryfieldsensitivitycallingconventionmodelingmicrobenchmarkgeneration
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Although accurate static data-flow analysis on binaries is undecidable in general, tools approximate it with heuristics, and nobody had systematically measured how badly those approximations fail. This paper builds that measurement: a labeled benchmark of 215,072 microbenchmark cases, mapping to 277,072 binaries, plus dynamically traced memory flows from six real-world programs. On that benchmark, three leading binary analysis engines recover only a fraction of true flows, with the best at 0.39 recall and 0.13 precision. The paper then shows that three small, targeted model extensions—respecting the calling convention, preserving the caller's stack frame across calls, and refusing to alias memory at different constant offsets—raise recall to 0.99 and precision to 0.32. In three vulnerability case studies, the improved analysis recovers data flows through the vulnerable instructions that the original tool missed.

What carries the argument

The load-bearing machinery is the benchmark's ground-truth design: fully specified microbenchmark cases, where the target flow is either unconditional or impossible by construction, combined with dynamically traced flows from real binaries, all categorized by alias classes. On top of that, the three model extensions each repair one approximation: C1, calling-convention awareness, preserves definitions passed as arguments across a callee call; C2, stack frame preservation, artificially restores the caller's stack frame across calls by undoing the call instruction's push; and F, constant-based field disunion, concretizes only the undefined registers in an address expression rather than the whole address, so distinct constant offsets stay distinct. Together these extensions target the two places the benchmark showed the unextended engine to fail: flows interrupted by calls and false aliasing between different fields of a structure.

What would settle it

Re-run the real-world evaluation with ground truth from a much larger dynamic corpus, such as fuzzing the same six binaries, and check whether the extended engine still finds 99% of the newly observed flows; if recall on those additional flows drops well below 0.99, the near-perfect recall was an artifact of the limited dynamic coverage.

Watch

Extended reading notes

Core claim

The paper's central claim is that the gap between ideal and actual binary data-flow analysis is not primarily a consequence of theoretical undecidability; it is caused by specific, diagnosable modeling approximations inside analysis engines: how they treat an address that cannot be resolved inside the function, what they assume a called function does to memory, and whether they keep fields at different constant offsets distinct. The benchmark makes these failures visible by scoring flows under a new taxonomy called alias classes, which classify each flow by whether the pointer entered the function as an argument, from the stack, from a heap allocation, or from global memory. In the microbenchmarks, the engine that the authors later extend reports every unconditional flow yet also reports every impossible heap and foreign flow, making the false positives systematic. On the real-world binaries, that unextended engine finds 39% of the dynamically observed flows at 13% precision, while a second engine effectively assumes no two memory addresses alias and a third compares access syntax. Adding the three model extensions raises recall to 99% and precision to 32%, and in three vulnerability case studies it recovers 12, 36, and 27 additional true-positive flows through the instructions involved in each bug.

Load-bearing premise

The real-world scores assume that running the projects' own test suites and keeping the five functions with the most dynamic flows gives a trustworthy lower-bound ground truth, so every static-only report is counted as wrong and every unexecuted flow as missed (Sections IV.C and V.B).

Editorial extensions

If this is right

  • The benchmark provides a reusable, labeled corpus of 215,072 microbenchmark cases and 277,072 binaries organized by alias classes, so any future data-flow analysis can be scored on the same axes.
  • The real-world evaluation quantifies the gap: across the three engines, recall ranged from 0.03 to 0.39 and precision from 0.04 to 0.66 before any extension.
  • The three model extensions raise the extended engine from 0.39 recall/0.13 precision to 0.99 recall/0.32 precision, showing that most missed flows can be recovered without abandoning the engine's architecture.
  • In three vulnerability case studies, the extended analysis finds 12, 36, and 27 additional true-positive data flows through the vulnerable instructions, which the original tool missed.
  • The microbenchmark results isolate specific problem classes—impossible heap and foreign flows, and stack flows with distinct offsets—giving future work a clear target for further precision improvements.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural next step is to apply the same three extensions to the other two engines, since their failure modes look different; if the fixes transfer, the benchmark would show whether these root causes are general across implementations.
  • The 0.99 recall could partly reflect the lower-bound dynamic ground truth, because static-only flows were counted as errors; re-running with a much larger fuzzing-based dynamic corpus would test whether near-perfect recall survives broader execution coverage.
  • The remaining precision gap at 0.32 suggests the conservative call-handling policy keeps too many flows alive; a summary-based inter-procedural analysis that kills flows when the callee provably overwrites the location could push precision higher while preserving recall.
  • Constant-based field disunion points to a broader heuristic for binary analysis: offset equality is cheap, effective evidence about non-aliasing, and combining it with access-width tracking could close the remaining multi-byte heap false positives.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. The paper introduces alias classes (Stack, Heap, Foreign, Global) to categorize binary-level data flows and builds a large benchmark consisting of 215,072 microbenchmark source-level test cases mapped to 277,072 unique target functions, augmented with dynamically discovered data flows from 30 functions across 6 real-world binaries. The authors evaluate three binary analysis engines (angr, Ghidra, Miasm) on this benchmark, reporting very low accuracy, and then propose three model extensions implemented in angr: C1 (calling-convention-based preservation of flows across callees), C2 (stack-frame preservation), and F (constant-based field disunion). They report that these extensions improve angr's real-world recall estimate from 0.39 to 0.99 and precision from 0.13 to 0.32, and that they improve recovery of vulnerability-related instructions in three case studies (CVE-2018-5785, CVE-2022-4904, CVE-2023-31130).

Significance. If the results hold, this is a valuable contribution: it is the first large-scale labeled benchmark for evaluating static data-flow analysis on binaries, it ships reproducible generation and evaluation frameworks, and the three model extensions are simple and plausible improvements with concrete demonstrations on vulnerability case studies. The alias-class taxonomy is a useful organizing device, and the microbenchmark size and the per-class breakdown of failures (Table II) provide actionable diagnostics for tool developers. The main weakness is that the headline real-world recall of 0.9942 is not a lower bound and is computed over a biased sample of functions, so the 'near-perfect recall' claim is not yet established.

major comments (3)
  1. [Section V.B and Table VIII] The reported recall of 0.9942 for angr CF is not a lower bound, and the paper's own caveat addresses only part of the problem. The text states that D\S is a lower-bound approximation for false negatives, but recall is computed as |D∩S|/|D|. If M = T\D is the set of true flows not observed dynamically, the true recall is (|D∩S|+|M∩S|)/(|D|+|M|). Since the dynamic ground truth comes only from each project's own test suite, M may be substantial, and an analysis that misses many unobserved true flows could have true recall far below 0.9942. The subsequent claim in Section VI.C that 'any real data flow is likely to be reported by angr CF with near guaranteed certainty' is therefore unsupported. A concrete remedy is to report recall as an interval with a bound on M derived from coverage or saturation measurements, to evaluate on functions with much higher dynamic coverage, or to explicitly reframe the claim as recall over dynamically observed flows only.
  2. [Section IV.C and Table I] The real-world test functions are selected as the five functions per binary with the most dynamically observed memory flows, and these functions are dominated by (Stack, Stack) flows, e.g., Mujs jsR_run4 has 380 of 386 such flows and cp copy_internal has 354 of 360. Extensions C1 and C2 explicitly preserve stack-frame and callee-crossing flows, and F targets distinct-offset field sensitivity. The real-world evaluation therefore measures the extensions on a sample that over-represents exactly the phenomena they encode. This does not invalidate the improvements, but it does not support a general statement of 'almost perfect recall' beyond this sample. A concrete test is to evaluate on a held-out or randomly selected set of functions, or at minimum to report per-alias-class and per-function recall to show performance where (F,F), (G,G), and (H,H) flows are not swamped by (S,S) flows.
  3. [Section VI.A and VI.B] The microbenchmark improvement is partly a restatement of the benchmark labels. The callee-interrupted test case in Listings 11 and 12 is labeled underspecified, and C1/C2 make the analysis preserve flows across callees by construction; the distinct-offset test case in Listing 13 is labeled impossible, and F's rule is literally that distinct constant offsets imply no flow. The fact that angr C and angr F score well on these microbenchmarks is therefore expected from the design rather than an independent confirmation of the model. This would be acceptable if the real-world results were strong enough to validate the model independently, but given the sample-selection issue and the recall-estimation gap above, the current evidence does not yet separate the model's genuine predictive power from the benchmark's alignment with the model. A useful test is to apply the extensions to benchmarks whose ground truth is produced by a different mechanism or to an independent corpus that is not filtered by dynamic flow count.
minor comments (8)
  1. [Section III.B] The sentence 'the data flow under test is is the target data flow' contains a duplicated word; remove the second 'is'.
  2. [Section III-A2d] The phrase 'Different binary code representations can may impact accuracy' should be 'can impact' or 'may impact', not both.
  3. [Section IV.C] The project name 'Apatche-Httpd' is a typo for 'Apache-Httpd'.
  4. [Table IV] In the chmod (S, S) row, Miasm is reported as finding 4 of 97 dynamic flows, which is 4.12%, not 6.19%; the table also omits the '%' sign after '7.78' in the CJson (S, S) Ghidra column.
  5. [Listing 11 caption] The caption reads 'A fully-specified unconditional data flow between exists between lines 1 and 2'; this is grammatically garbled and should be reworded.
  6. [Listing 19 caption] The caption spells 'assembly' as 'assmbly'; fix the typo.
  7. [Section VI.C] The phrase 'We prove the real-world improvement of angr CF' overstates what an empirical evaluation with an incomplete ground truth can establish; 'demonstrate' or 'show' is more accurate.
  8. [Section III-A3d] The list of argument-passing registers 'rdi, rsi, rdx, rcs, r8, r9' contains 'rcs' instead of 'rcx'.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the real-world evaluation is independent of the microbenchmark-driven extension design, though the 0.99 recall is an estimate over incomplete dynamic ground truth.

full rationale

The paper's derivation chain is: (1) synthesize labeled microbenchmarks; (2) evaluate angr, Ghidra, and Miasm; (3) infer failure modes from the microbenchmark; (4) design extensions C1/C2/F; (5) re-score the microbenchmark and six real-world binaries. Step (5) on real-world binaries is not entailed by steps (3)-(4): the extensions encode general heuristics (preserve callee-crossing flows, disunite constant offsets), and whether those heuristics recover dynamically observed flows in coreutils, Apache, Mujs, and cJSON is an empirical question. Some microbenchmark rows showing 0% -> 100% for callee-interrupted 'underspecified' cases are partly tautological, because 'possible' is defined as 'could be made to flow by out-of-scope data' (Section III-A2e), so any reported edge matches that label by construction; however, the headline real-world 0.99 recall and 0.32 precision are not produced by that tautology. The dynamic ground truth is incomplete: Section V.B states that D\S is only a lower bound approximation for false negatives, so Table VIII's recall is an estimate, not a lower bound, and the statement that 'any real data flow is likely to be reported by angr CF with near guaranteed certainty' (Section VI.C) overstates the evidence. That is a validity/correctness limitation, not circularity. The only self-citation, BinHunter [18], is cited as an example of vulnerability tools that rely on data flow and is not load-bearing. Overall, no prediction in the paper reduces to its inputs by construction; the score of 2 reflects the minor microbenchmark-label tautology and the non-load-bearing self-citation without treating either as central.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The benchmark and extensions rest on several domain assumptions about binary compilation, calling conventions, and the scope of data-flow analysis. There are no numeric fitted parameters; the model choices are structural heuristics, which reduces the numeric circularity burden but introduces policy assumptions that directly affect the reported gains.

assumptions (5)
  • domain assumption Ground truth assigned at the source level remains valid at the binary level after compilation.
    Microbenchmark test cases are labeled in source, then compiled. The authors use volatile and DWARF symbols to locate the target instructions, but compiler transformations could in principle alter the intended write-read relationship.
  • domain assumption Intra-procedural memory data flows are the main challenge of data-flow analysis, and register flows can be ignored.
    Section II.B explicitly excludes register flows and inter-procedural flows. This limits the benchmark's coverage and means conclusions about 'data-flow analysis' are only about one slice of the problem.
  • ad hoc to paper Distinct constant offsets imply no data flow between memory accesses.
    Model extension F assumes accesses with different constant offsets refer to different fields. The authors note multi-byte accesses can overlap, which violates this assumption, yet it is central to the extension.
  • ad hoc to paper Callee functions have no effect on the caller's data flows and stack frame.
    Extensions C1 and C2 preserve data flows across callees and artificially restore the stack pointer. This is a heuristic that will be wrong when a callee overwrites memory that the caller later reads.
  • domain assumption The System V AMD64 calling convention is sufficient to identify pointer origins in real binaries.
    Foreign pointers are inferred from specific argument registers and heap pointers from rax. Other calling conventions, wrappers, or indirect calls could break this inference, as the authors partially acknowledge with 'unknown' alias classes.
invented entities (1)
  • Alias classes (Stack, Heap, Foreign, Global)
    purpose: Categorize data flows by pointer origin to identify where analyses fail.
    This is a new taxonomy introduced to structure the benchmark. It is a labeling scheme, not a separate empirical phenomenon, and it has no falsifiable prediction outside the paper's own classification procedure.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Data Flows in You: Benchmarking and Improving Static Data-flow Analysis on Binary Executables." pith.science (2026). https://pith.science/paper/H6WJDQAK

@misc{pith2026250600313,
  author       = {Pith},
  title        = {Pith review of: Data Flows in You: Benchmarking and Improving Static Data-flow Analysis on Binary Executables},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H6WJDQAK}},
  note         = {Machine review of arXiv:2506.00313}
}
read the original abstract

Data-flow analysis is a critical component of security research. Theoretically, accurate data-flow analysis in binary executables is an undecidable problem, due to complexities of binary code. Practically, many binary analysis engines offer some data-flow analysis capability, but we lack understanding of the accuracy of these analyses, and their limitations. We address this problem by introducing a labeled benchmark data set, including 215,072 microbenchmark test cases, mapping to 277,072 binary executables, created specifically to evaluate data-flow analysis implementations. Additionally, we augment our benchmark set with dynamically-discovered data flows from 6 real-world executables. Using our benchmark data set, we evaluate three state of the art data-flow analysis implementations, in angr, Ghidra and Miasm and discuss their very low accuracy and reasons behind it. We further propose three model extensions to static data-flow analysis that significantly improve accuracy, achieving almost perfect recall (0.99) and increasing precision from 0.13 to 0.32. Finally, we show that leveraging these model extensions in a vulnerability-discovery context leads to a tangible improvement in vulnerable instruction identification.

Figures

Figures reproduced from arXiv: 2506.00313 by the authors.

Figure 1
Figure 1. We modify the intra-procedural data-flow graph to reconnect registers [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. We modify the intra-procedural data-flow graph to eliminate data [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

26 extracted references · 22 canonical work pages

  1. [1]

    WYSINWYX: what you see is not what you execute,

    G. Balakrishnan and T. W. Reps, “WYSINWYX: what you see is not what you execute,”ACM Trans. Program. Lang. Syst., vol. 32, no. 6, pp. 23:1–23:84, 2010. [Online]. Available: https://doi.org/10.1145/1749608.1749612

    work page arXiv 2010

  2. [2]

    The Angr binary analysis platform,

    angr, “The Angr binary analysis platform,” http://angr.io, 2016

    work page 2016

  3. [3]

    Ghidra, “Ghidra,” https://ghidra-sre.org/, 2022

    work page 2022

  4. [4]

    Miasm, “Miasm,” https://miasm.re, 2019

    work page 2019

  5. [5]

    Undecidability of context-sensitive data-independence analysis,

    T. W. Reps, “Undecidability of context-sensitive data-independence analysis,”ACM Trans. Program. Lang. Syst., vol. 22, no. 1, pp. 162–186,

    work page

  6. [6]

    A. V . Aho, R. Sethi, and J. D. Ullman,Compilers: Principles, Techniques, and Tools, ser. Addison-Wesley series in computer science / World student series edition. Addison-Wesley, 1986. [Online]. Available: https://www.worldcat.org/oclc/12285707

    arXiv 1986

  7. [7]

    Interprocedural static slicing of binary executables,

    ´A. Kiss, J. J ´asz, G. Lehotai, and T. Gyim ´othy, “Interprocedural static slicing of binary executables,” in3rd IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2003), 26-27 September 2003, Amsterdam, The Netherlands. IEEE Computer Society, 2003, p

    work page 2003

  8. [8]

    WYSINWYX: what you see is not what you execute,

    G. Balakrishnan, T. W. Reps, D. Melski, and T. Teitelbaum, “WYSINWYX: what you see is not what you execute,” in Verified Software: Theories, Tools, Experiments, First IFIP TC 2/WG 2.3 Conference, VSTTE 2005, Zurich, Switzerland, October 10-13, 2005, Revised Selected Papers and Discussions, ser. Lecture Notes in Computer Science, B. Meyer and J. Woodcock, ...

    work page doi:10.1007/978-3-540-69149-5 2005

Show all 26 references
  1. [9]

    Classes of recursively enumerable sets and their decision problems,

    H. G. Rice, “Classes of recursively enumerable sets and their decision problems,”Transactions of the American Mathematical society, vol. 74, no. 2, pp. 358–366, 1953

    1953

  2. [10]

    The undecidability of aliasing,

    G. Ramalingam, “The undecidability of aliasing,”ACM Trans. Program. Lang. Syst., vol. 16, no. 5, pp. 1467–1471, 1994. [Online]. Available: https://doi.org/10.1145/186025.186041

    1994

  3. [11]

    Pyelftools,

    pyelftools, “Pyelftools,” https://github.com/eliben/pyelftools, 2023

    2023

  4. [12]

    Coreutils - GNU core utilities,

    coreutils, “Coreutils - GNU core utilities,” https://www.gnu.org/software/coreutils/, 2023

    2023

  5. [13]

    Apache - HTTP Server Project,

    apache, “Apache - HTTP Server Project,” https://httpd.apache.org/, 2023

    2023

  6. [14]

    Artifex, “MuJS,” https://mujs.com/, 2023

    2023

  7. [15]

    cJSON - Ultralightweight JSON parser in ANSI C ,

    cjson, “cJSON - Ultralightweight JSON parser in ANSI C ,” https://github.com/DaveGamble/cJSON, 2023

    2023

  8. [16]

    Pin: building customized program analysis tools with dynamic instrumentation,

    C. Luk, R. S. Cohn, R. Muth, H. Patil, A. Klauser, P. G. Lowney, S. Wallace, V . J. Reddi, and K. M. Hazelwood, “Pin: building customized program analysis tools with dynamic instrumentation,” in Proceedings of the ACM SIGPLAN 2005 Conference on Programming Language Design and ...

    2005

  9. [17]

    Bvdetector: A program slice- based binary code vulnerability intelligent detection system,

    J. Tian, W. Xing, and Z. Li, “Bvdetector: A program slice- based binary code vulnerability intelligent detection system,”Inf. Softw. Technol., vol. 123, p. 106289, 2020. [Online]. Available: https://doi.org/10.1016/j.infsof.2020.106289

    2020

  10. [18]

    Binhunter: A fine-grained graph representation for localizing vulnerabilities in binary executables *,

    S. Arasteh, J. Mirkovic, M. Raghothaman, and C. Hauser, “Binhunter: A fine-grained graph representation for localizing vulnerabilities in binary executables *,” inAnnual Computer Security Applications Conference, ACSAC 2024, Honolulu, HI, USA, December 9- 13, 2024. IEEE, 2024,...

    2024

  11. [19]

    An in-depth analysis of disassembly on full-scale x86/x64 binaries,

    D. Andriesse, X. Chen, V . van der Veen, A. Slowinska, and H. Bos, “An in-depth analysis of disassembly on full-scale x86/x64 binaries,” in25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10-12, 2016, T. Holz and S. Savage, Eds. USENIX Association, 2...

    2016

  12. [20]

    Ground truth for binary disassembly is not easy,

    C. Pang, T. Zhang, R. Yu, B. Mao, and J. Xu, “Ground truth for binary disassembly is not easy,” in31st USENIX Security Symposium, USENIX Security 2022, Boston, MA, USA, August 10-12, 2022, K. R. B. Butler and K. Thomas, Eds. USENIX Association, 2022, pp. 2479–2495. [Online]. A...

    2022

  13. [21]

    Sok: All you ever wanted to know about x86/x64 binary disassembly but were afraid to ask,

    C. Pang, R. Yu, Y . Chen, E. Koskinen, G. Portokalidis, B. Mao, and J. Xu, “Sok: All you ever wanted to know about x86/x64 binary disassembly but were afraid to ask,” in42nd IEEE Symposium on Security and Privacy, SP 2021, San Francisco, CA, USA, 24-27 May 2021. IEEE, 2021, pp...

    2021

  14. [22]

    rev.ng: a unified binary analysis framework to recover cfgs and function boundaries,

    A. D. Federico, M. Payer, and G. Agosta, “rev.ng: a unified binary analysis framework to recover cfgs and function boundaries,” inProceedings of the 26th International Conference on Compiler Construction, Austin, TX, USA, February 5-6, 2017, P. Wu and S. Hack, Eds. ACM, 2017, ...

    2017

  15. [23]

    Pointer analysis: haven’t we solved this problem yet?

    M. Hind, “Pointer analysis: haven’t we solved this problem yet?” inProceedings of the 2001 ACM SIGPLAN-SIGSOFT Workshop on Program Analysis For Software Tools and Engineering, PASTE’01, Snowbird, Utah, USA, June 18-19, 2001, J. Field and G. Snelting, Eds. ACM, 2001, pp. 54–61....

    2001

  16. [24]

    Towards automatically generating a sound and complete dataset for evaluating static analysis tools,

    A. Machiry, N. Redini, E. Gustafson, H. Aghakhani, C. Kruegel, and G. Vigna, “Towards automatically generating a sound and complete dataset for evaluating static analysis tools,”Workshop on Binary Analysis Research (BAR), 2019. [Online]. Available: https://par.nsf.gov/biblio/10155111

    2019

  17. [118]

    Available: https://doi.org/10.1109/SCAM.2003.1238038

    [Online]. Available: https://doi.org/10.1109/SCAM.2003.1238038

    2003 arXiv

  18. [2000]

    Available: https://doi.org/10.1145/345099.345137

    [Online]. Available: https://doi.org/10.1145/345099.345137

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.