Static Detection of Address Leaks
ResumoTaint analysis is a form of program analysis that determines if values produced by unsafe sources might flow into sensitive functions. In this paper we use taint analysis to establish if an adversary might discover the address of any program variable at runtime. The knowledge of an internal program address seems, in principle, a harmless information; however, it gives a malicious user the means to circumvent a protection mechanism known as address space layout randomization, typically used in modern operating systems to hinder buffer overflow attacks, for instance. We depart from previous taint analyses because we also track indirect information leaks, in which confidential data is first stored in memory, from where it flows into some sensitive operation. We have implemented our analysis into the LLVM compiler and have used it to report 204 warnings in a test suite that contains over 1.3 million lines of C code, and includes traditional benchmarks such as SPEC CPU 2006. Our current implementation reduces by more than 14 times the number of sensitive operations that a developer would have to inspect in order to find address leaks manually. Furthermore, our analysis is remarkably efficient: it has been able to process more than 8.2 million assembly instructions in 19.7 seconds!
Bhatkar, E., Duvarney, D. C., and Sekar, R. (2003). Address obfuscation: an efficient approach to combat a broad range of memory error exploits. In USENIX Security, pages 105–120.
Blanchet, B. (1998). Escape analysis: Correctness proof, implementation and experimental results. In POPL, pages 25–37. ACM.
Bond, M. D. and McKinley, K. S. (2007). Probabilistic calling context. In OOPSLA, pages 97–112. ACM.
Buchanan, E., Roemer, R., Shacham, H., and Savage, S. (2008). When good instructions go bad: generalizing return-oriented programming to RISC. In CCS, pages 27–38. ACM.
Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., and Zadeck, F. K. (1991). Efficiently computing static single assignment form and the control dependence graph. TOPLAS, 13(4):451–490.
Denning, D. E. and Denning, P. J. (1977). Certification of programs for secure information flow. Commun. ACM, 20:504–513.
Ghiya, R. and Hendren, L. J. (1998). Putting pointer analysis to work. In POPL, pages 121–133. ACM.
Gough, B. J. (2005). An Introduction to GCC. Network Theory Ltd, 1st edition.
Hardekopf, B. and Lin, C. (2007). The ant and the grasshopper: fast and accurate pointer analysis for millions of lines of code. In PLDI, pages 290–299. ACM.
Jovanovic, N., Kruegel, C., and Kirda, E. (2006). Pixy: A static analysis tool for detecting web application vulnerabilities (short paper). In Symposium on Security and Privacy, pages 258–263. IEEE.
Lattner, C. and Adve, V. S. (2004). LLVM: A compilation framework for lifelong program analysis & transformation. In CGO, pages 75–88. IEEE.
Lattner, C., Lenharth, A., and Adve, V. S. (2007). Making context-sensitive points-to analysis with heap cloning practical for the real world. In PLDI, pages 278–289. ACM.
Levy, E. (1996). Smashing the stack for fun and profit. Phrack, 7(49).
Pearce, D. J., Kelly, P. H. J., and Hankin, C. (2004). Efficient field-sensitive pointer analysis for C. In PASTE, pages 37–42.
Pereira, F. M. Q. and Berlin, D. (2009). Wave propagation and deep propagation for pointer analysis. In CGO, pages 126–135. IEEE.
Pistoia, M., Flynn, R. J., Koved, L., and Sreedhar, V. C. (2005). Interprocedural analysis for privileged code placement and tainted variable detection. In ECOOP, pages 362– 386.
Rimsa, A. A., D’Amorim, M., and Pereira, F. M. Q. (2011). Tainted flow analysis on e-SSA-form programs. In CC, pages 124–143. Springer.
Rochlis, J. A. and Eichin, M. W. (1989). With microscope and tweezers: the worm from MIT’s perspective. Commun. ACM, 32:689–698.
Sagiv, M., Reps, T., and Wilhelm, R. (1998). Solving shape-analysis problems in languages with destructive updating. TOPLAS, 20(1):1–50.
Sagiv, M., Reps, T., and Wilhelm, R. (2002). Parametric shape analysis via 3-valued logic. TOPLAS, 24:217–298.
Shacham, H. (2007). The geometry of innocent flesh on the bone: return-into-libc without function calls (on the x86). In CCS, pages 552–561. ACM.
Shacham, H., Page, M., Pfaff, B., Goh, E.-J., Modadugu, N., and Boneh, D. (2004). On the effectiveness of address-space randomization. In CSS, pages 298–307. ACM.
Steensgaard, B. (1996). Points-to analysis in almost linear time. In POPL, pages 32–41.
Stroustrup, B. (2007). Evolving a language in and for the real world: C++ 1991-2006. In HOPL, pages 1–59. ACM.
Team, J. (2006). The java HotSpot virtual machine. Technical Report Technical White Paper, Sun Microsystems.
Wassermann, G. and Su, Z. (2007). Sound and precise analysis of web applications for injection vulnerabilities. In PLDI, pages 32–41. ACM.
Xie, Y. and Aiken, A. (2006). Static detection of security vulnerabilities in scripting languages. In USENIX-SS. USENIX Association.