ABSTRACT
Binary-level Control-Flow Graph (CFG) construction is essential for applications such as control-flow integrity. There are two main approaches: the binary-analysis approach and the compiler-modification approach. The binary-analysis approach does not require source code, but it constructs low-precision CFGs. The compiler-modification approach requires source code and modifies compilers for CFG generation. We describe the design and implementation of an alternative system for high-precision CFG construction, which still assumes source code but does not modify compilers. Our approach makes use of standard compiler-generated meta-information, including symbol tables, relocation information, and debugging information. A key component in the system is a type-inference engine that infers types of low-level storage locations such as registers from types in debugging information. Inferred types enable a type-signature matching method for high-precision CFG construction.
- Martín Abadi, Mihai Budiu, Úlfar Erlingsson, and Jay Ligatti. 2005. Control-flow integrity. In 12th ACM Conference on Computer and Communications Security (CCS). 340--353. Google ScholarDigital Library
- Dennis Andriesse, Xi Chen, Victor van der Veen, Asia Slowinska, and Herbert Bos. 2016. An In-Depth Analysis of Disassembly on Full-Scale x86/x64 Binaries. In 25th Usenix Security Symposium. 583--600.Google Scholar
- Gogul Balakrishnan and Thomas Reps. 2004. Analyzing Memory Accesses in x86 Executables. In 13th International Conference on Compiler Construction (CC). 5--23.Google ScholarCross Ref
- David Brumley, Ivan Jager, Thanassis Avgerinos, and Edward J. Schwartz. 2011. BAP: A Binary Analysis Platform. In Computer Aided Verification (CAV). 463--469. Google ScholarDigital Library
- Nathan Burow, Scott A. Carr, Joseph Nash, Per Larsen, Michael Franz, Stefan Brunthaler, and Mathias Payer. 2017. Control-Flow Integrity: Precision, Security, and Performance.Comput. Surveys 50, 1 (2017), 16:1--16:33. Google ScholarDigital Library
- Juan Caballero and Zhiqiang Lin. 2016. Type Inference on Executables. Comput. Surveys 48, 4 (2016), 65:1--65:35. Google ScholarDigital Library
- Nicholas Carlini, Antonio Barresi, Mathias Payer, David Wagner, and Thomas R. Gross. 2015. Control-Flow Bending: On the Effectiveness of Control-Flow Integrity. In 24th Usenix Security Symposium. 161--176. Google ScholarDigital Library
- Nicholas Carlini and David Wagner. 2014. ROP is Still Dangerous: Breaking Modern Defenses. In 23rd Usenix Security Symposium. 385--399. Google ScholarDigital Library
- Mihai Christodorescu and Somesh Jha. 2003. Static Analysis of Executables to Detect Malicious Patterns. In 12th Usenix Security Symposium. 169--186. Google ScholarDigital Library
- Lucas Davi, Ahmad-Reza Sadeghi, Daniel Lehmann, and Fabian Monrose. 2014. Stitching the Gadgets: On the Ineffectiveness of Coarse-Grained Control-Flow Integrity Protection. In 23rd Usenix Security Symposium. 401--416. Google ScholarDigital Library
- DWARF Debugging Information Format Committee 2017. DWARF Debugging Information Format Version 5. DWARF Debugging Information Format Committee.Google Scholar
- Enes Göktas, Elias Athanasopoulos, Herbert Bos, and Georgios Portokalidis. 2014. Out of Control: Overcoming Control-Flow Integrity. In IEEE Symposium on Security and Privacy (S&P). 575--589. Google ScholarDigital Library
- Dongseok Jang, Zachary Tatlock, and Sorin Lerner. 2014 SafeDispatch: Securing C++ Virtual Calls from Memory Corruption Attacks. In Network and Distributed System Security Symposium (NDSS).Google ScholarCross Ref
- Christopher Kruegel, William Robertson, Fredrik Valeur, and Giovanni Vigna. 2004. Static Disassembly of Obfuscated Binaries. In 13th Usenix Security Symposium. 255--270. Google ScholarDigital Library
- Chi-Keung Luk, Robert Cohn, Robert Muth, Harish Patil, Artur Klauser, Geoffrey Lowney, Steven Wallace, Vijay Janapa Reddi, and Kim Hazelwood. 2005. Pin: building customized program analysis tools with dynamic instrumentation. In ACM Conference on Programming Language Design and Implementation (PLDI). 190--200. Google ScholarDigital Library
- Julia Menapace, Jim Kingdon, and David MacKenzie. 1999. The "stabs" debug format.Google Scholar
- Greg Morrisett, Gang Tan, Joseph Tassarotti, Jean-Baptiste Tristan, and Edward Gan. 2012. RockSalt: Better, Faster, Stronger SFI for the x86. In ACM Conference on Programming Language Design and Implementation (PLDI). 395--404. Google ScholarDigital Library
- Ben Niu. 2015. Practical Control-Flow Integrity. Ph.D. Dissertation. Lehigh University, Bethlehem, PA.Google Scholar
- Ben Niu and Gang Tan. 2013. Monitor Integrity Protection with Space Efficiency and Separate Compilation. In 20th ACM Conference on Computer and Communications Security (CCS). Google ScholarDigital Library
- Ben Niu and Gang Tan. 2014. Modular Control Flow Integrity. In ACM Conference on Programming Language Design and Implementation (PLDI). 577--587. Google ScholarDigital Library
- Ben Niu and Gang Tan. 2014. RockJIT: Securing Just-In-Time Compilation Using Modular Control-Flow Integrity. In 21st ACM Conference on Computer and Communications Security (CCS). 1317--1328. Google ScholarDigital Library
- Andre Pawlowski, Moritz Contag, Victor van der Veen, Chris Ouwehand, Thorsten Holz, Herbert Bos, Elias Athanasopoulos, and Cristiano Giuffrida. 2017. MARX: Uncovering class Hierarchies in C++ Programs. In Network and Distributed System Security Symposium (NDSS).Google Scholar
- Jannik Pewny and Thorsten Holz. 2013. Control-Flow Restrictor: Compiler-based CFI for iOS. In ACSAC '13: Proceedings of the 2013 Annual Computer Security Applications Conference . Google ScholarDigital Library
- Thomas Reps, Junghee Lim, Aditya Thakur, Gogul Balakrishnan, and Akash Lal. 2010. There's Plenty of Room at the Bottom: Analyzing and Verifying Machine Code. In Computer Aided Verification (CAV). 41--56. Google ScholarDigital Library
- Hovav Shacham. 2007. The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86). In 14th ACM Conference on Computer and Communications Security (CCS). 552--561. Google ScholarDigital Library
- Dawn Song, David Brumley, Heng Yin, Juan Caballero, Ivan Jager, Min Gyung Kang, Zhenkai Liang, James Newsome, Pongsin Poosankam, and Prateek Saxena. 2008. BitBlaze: A New Approach to Computer Security via Binary Analysis. In Proceedings of the 4th International Conference on Information Systems Security. Google ScholarDigital Library
- Caroline Tice, Tom Roeder, Peter Collingbourne, Stephen Checkoway, Úlfar Erlingsson, Luis Lozano, and Geoff Pike. 2014. Enforcing Forward-Edge Control-Flow Integrity in GCC & LLVM. In 23rd Usenix Security Symposium. Google ScholarDigital Library
- Victor van der Veen, Enes Göktas, Moritz Contag, Andre Pawoloski, Xi Chen, Sanjay Rawat, Herbert Bos, Thorsten Holz, Elias Athanasopoulos, and Cristiano Giuffrida. 2016. A Tough Call: Mitigating Advanced Code-Reuse Attacks at the Binary Level. In IEEE Symposium on Security and Privacy (S&P). 934--953.Google ScholarCross Ref
- R. Wahbe, S. Lucco, T. Anderson, and S. Graham. 1993. Efficient Software-Based Fault Isolation. In ACM SIGOPS Symposium on Operating Systems Principles (SOSP). ACM Press, New York, 203--216. Google ScholarDigital Library
- Zhi Wang and Xuxian Jiang. 2010. HyperSafe: A Lightweight Approach to Provide Lifetime Hypervisor Control-Flow Integrity. In IEEE Symposium on Security and Privacy (S&P). 380--395. Google ScholarDigital Library
- Richard Wartell, Vishwath Mohan, Kevin W. Hamlen, and Zhiqiang Lin. 2012. Securing untrusted code via compiler-agnostic binary rewriting. In Proceedings of the 28th Annual Computer Security Applications Conference. 299--308. Google ScholarDigital Library
- Richard Wartell, Yan Zhou, Kevin W. Hamlen, and Murat Kantarcioglu. 2014. Shingled Graph Disassembly: Finding the Undecidable Path. In Proceedings of the 18th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD). Tainan, Taiwan, 273--285.Google ScholarCross Ref
- Richard Wartell, Yan Zhou, Kevin W. Hamlen, Murat Kantarcioglu, and Bhavani Thuraisingham. 2011. Differentiating Code from Data in x86 Binaries. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD), Vol. 3. 522--536. Google ScholarDigital Library
- Zhichen Xu, Barton Miller, and Thomas Reps. 2000. Safety checking of machine code. In ACM Conference on Programming Language Design and Implementation (PLDI). 70--82. Google ScholarDigital Library
- Bennet Yee, David Sehr, Gregory Dardyk, Brad Chen, Robert Muth, Tavis Ormandy, Shiki Okasaka, Neha Narula, and Nicholas Fullagar. 2009. Native Client: A Sandbox for Portable, Untrusted x86 Native Code. In IEEE Symposium on Security and Privacy (S&P). Google ScholarDigital Library
- Chao Zhang, Tao Wei, Zhaofeng Chen, Lei Duan, Laszlo Szekeres, Stephen McCamant, Dawn Song, and Wei Zou. 2013. Practical Control Flow Integrity and Randomization for Binary Executables. In IEEE Symposium on Security and Privacy (S&P). 559--573. Google ScholarDigital Library
- Mingwei Zhang and R. Sekar. 2013. Control Flow Integrity for COTS Binaries. In 22nd Usenix Security Symposium. 337--352. Google ScholarDigital Library
Index Terms
- From Debugging-Information Based Binary-Level Type Inference to CFG Generation
Recommendations
Type Inference on Executables
In many applications, source code and debugging symbols of a target program are not available, and the only thing that we can access is the program executable. A fundamental challenge with executables is that, during compilation, critical information ...
Interactive type debugging in Haskell
Haskell '03: Proceedings of the 2003 ACM SIGPLAN workshop on HaskellIn this paper we illustrate the facilities for type debugging of Haskell programs in the Chameleon programming environment. Chameleon provides an extension to Haskell supporting advanced and programmable type extensions. Chameleon maps the typing ...
Type checking and inference for polymorphic and existential types
CATS '09: Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory - Volume 94This paper proves undecidability of type checking and type inference problems in some variants of typed lambda calculi with polymorphic and existential types. First, type inference in the domain-free polymorphic lambda calculus is proved to be ...
Comments