BINARY PROGRAM DEPENDENCE ANALYSIS: TECHNIQUES, CHALLENGES, AND FUTURE DIRECTIONS

Binary program dependence analysis is pivotal for security applications such as vulnerability detection and malware analysis, yet faces significant challenges due to path explosion, indirect branches, and over-approximation. This survey systematically examines state-of-the-art techniques, including value set analysis (VSA), path-sampling methods (BDA, DueForce), block memory models (BPA, BinPointer), and machine learning approaches (NeuDep), to address three core research questions: (1) how existing methods achieve scalability, (2) the compromises made in scalability and their impact on precision/soundness, and (3) alternative strategies to transcend these tradeoffs. We propose a three-dimensional analytical framework—methodological taxonomy, empirical evaluation, and forward-looking synthesis—to categorize 11 representative tools and evaluate their performance on the SPEC CINT 2000 benchmark. Key findings reveal that path-sampling methods like BDA balance soundness and efficiency but struggle with complex control flow, while machine learning-based NeuDep mitigates false positives through hybrid modeling. Dynamic analysis (DueForce) prioritizes precision but suffers from scalability limitations. Our contributions include a novel taxonomy exposing precision-soundness-scalability tradeoffs, a refined evaluation methodology integrating symbolic execution for accuracy validation, and pioneering pathways for next-generation analysis via sparse value-flow analysis. The results underscore the need for context-aware strategies to handle modern software complexity, offering actionable insights for advancing binary analysis in security hardening and vulnerability defense.