BINARY PROGRAM DEPENDENCE ANALYSIS: TECHNIQUES, CHALLENGES, AND FUTURE DIRECTIONS
Keywords:
Dependence analysis, Binary analysis, Static analysis, Path explosion, Abstract interpretationAbstract
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.References
[1] Zhang, Z, You, W, Tao, G, et al. BDA: practical dependence analysis for binary executables by unbiased whole-program path sampling and per-path abstract interpretation. Proceedings of the ACM on Programming Languages, 2019; 3(OOPSLA): 1-31. DOI: 10.1145/3360563.
[2] Pei, K, She, D, Wang, M, et al. NeuDep: neural binary memory dependence analysis. in ESEC/FSE '22: 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. 2022. ACM. DOI: 10.1145/3540250.3549147.
[3] He, D, Xie, D, Wang, Y, et al. Define-Use Guided Path Exploration for Better Forced Execution. in ISSTA '24: 33rd ACM SIGSOFT International Symposium on Software Testing and Analysis. 2024. ACM. DOI: 10.1145/3650212.3652128.
[4] Gui, B, Song, W, Huang, J. UAFSan: an object-identifier-based dynamic approach for detecting use-after-free vulnerabilities. in ISSTA '21: 30th ACM SIGSOFT International Symposium on Software Testing and Analysis. 2021. ACM. DOI: 10.1145/3460319.3464835.
[5] Cheng, K, Zheng, Y, Liu, T, et al. Detecting Vulnerabilities in Linux-Based Embedded Firmware with SSE-Based On-Demand Alias Analysis. in ISSTA '23: 32nd ACM SIGSOFT International Symposium on Software Testing and Analysis. 2023. ACM. DOI: 10.1145/3597926.3598062.
[6] Zhang, M, Sekar, R. Control Flow Integrity for COTS Binaries. USENIX Association. 2013.
[7] Van Der Veen, V, Goktas, E, Contag, M, et al. A Tough Call: Mitigating Advanced Code-Reuse Attacks at the Binary Level. in 2016 IEEE Symposium on Security and Privacy (SP). 2016. IEEE. DOI: 10.1109/SP.2016.60.
[8] Gu, Y, Zhao, Q, Zhang, Y, et al. PT-CFI: Transparent Backward-Edge Control Flow Violation Detection Using Intel Processor Trace. in CODASPY '17: Seventh ACM Conference on Data and Application Security and Privacy. 2017. ACM. DOI: 10.1145/3029806.3029830.
[9] Yan, J, Yan, G, Jin, D. Classifying Malware Represented as Control Flow Graphs using Deep Graph Convolutional Neural Network. in 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 2019. IEEE. DOI: 10.1109/DSN.2019.00020.
[10] Yin, H, Song, D, Egele, M, et al. Panorama: capturing system-wide information flow for malware detection and analysis. in CCS07: 14th ACM Conference on Computer and Communications Security 2007. 2007. ACM. DOI: 10.1145/1315245.1315261.
[11] Cha, S K, Avgerinos, T, Rebert, A, et al. Unleashing Mayhem on Binary Code. in 2012 IEEE Symposium on Security and Privacy (SP) Conference dates subject to change. 2012. IEEE. DOI: 10.1109/SP.2012.31.
[12] Cozzi, E, Graziano, M. Fratantonio, Y, et al. Understanding Linux Malware. in 2018 IEEE Symposium on Security and Privacy (SP). 2018. IEEE. DOI: 10.1109/SP.2018.00054.
[13] Wu, W, Chen, Y, Xing, X, et al. KEPLER: Facilitating control-flow hijacking primitive evaluation for linux kernel vulnerabilities. USENIX Association. 2019.
[14] Spensky, C, Machiry, A, Burow, N, et al. Glitching Demystified: Analyzing Control-flow-based Glitching Attacks and Defenses. in 2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 2021. IEEE. DOI: 10.1109/DSN48987.2021.00051.
[15] Duta, V, Giuffrida, C, Bos, H, et al. PIBE: practical kernel control-flow hardening with profile-guided indirect branch elimination. in ASPLOS '21: 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. 2021. ACM. DOI: 10.1145/3445814.3446740.
[16] Chen, Y, Zhang, D, Wang, R, et al. NORAX: Enabling Execute-Only Memory for COTS Binaries on AArch64. in 2017 IEEE Symposium on Security and Privacy (SP). 2017. IEEE. DOI: 10.1109/SP.2017.30.
[17] MITRE. CWE Top 25 Most Dangerous Software Weaknesses. 2024. Retrieved from: https://cwe.mitre.org/top25/ .
[18] Schloegel, M, Bars, N, Schiller, N, et al. SoK: Prudent Evaluation Practices for Fuzzing. in 2024 IEEE Symposium on Security and Privacy (SP). 2024. IEEE. DOI: 10.1109/SP54263.2024.00137.
[19] Kim, T E, Choi, J, Heo, K, et al. DAFL: Directed grey-box fuzzing guided by data dependency. USENIX Association. 2023.
[20] Balakrishnan, G, Reps, T. Analyzing Memory Accesses in x86 Executables, in Compiler Construction, E. Duesterwald, Editor. Springer Berlin Heidelberg: Berlin, Heidelberg. 2004, 5-23.
[21] Balakrishnan, G, Reps, T. WYSINWYX: What you see is not what you eXecute. ACM Transactions on Programming Languages and Systems, 2010, 32(6): 1-84. DOI: 10.1145/1749608.1749612.
[22] Song, D, Brumley, D, Yin, H, et al. BitBlaze: A New Approach to Computer Security via Binary Analysis, in Information Systems Security, R. Sekar and A.K. Pujari, Editors. Springer Berlin Heidelberg: Berlin, Heidelberg. 2008, 1-25.
[23] Shoshitaishvili, Y, Wang, R, Salls, C, et al. SOK: (State of) The Art of War: Offensive Techniques in Binary Analysis. in 2016 IEEE Symposium on Security and Privacy (SP). 2016. IEEE. DOI: 10.1109/SP.2016.17.
[24] Cousot, P, Cousot, R. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. in the 4th ACM SIGACT-SIGPLAN symposium. 1977. ACM Press. DOI: 10.1145/512950.512973.
[25] Park, J, Lee, H, Ryu, S. A Survey of Parametric Static Analysis. ACM Computing Surveys, 2022, 54(7): 1-37. DOI: 10.1145/3464457.
[26] Baldoni, R, Coppa, E, D’elia, D C, et al. A Survey of Symbolic Execution Techniques. ACM Computing Surveys, 2019, 51(3): 1-39. DOI: 10.1145/3182657.