Sound and precise analysis of web applications for injection vulnerabilities

ABSTRACT

Web applications are popular targets of security attacks. One common type of such attacks is SQL injection, where an attacker exploits faulty application code to execute maliciously crafted database queries. Bothstatic and dynamic approaches have been proposed to detect or prevent SQL injections; while dynamic approaches provide protection for deployed software, static approaches can detect potential vulnerabilities before software deployment. Previous static approaches are mostly based on tainted information flow tracking and have at least some of the following limitations: (1) they do not model the precise semantics of input sanitization routines; (2) they require manually written specifications, either for each query or for bug patterns; or (3) they are not fully automated and may require user intervention at various points in the analysis. In this paper, we address these limitations by proposing a precise, sound, and fully automated analysis technique for SQL injection. Our technique avoids the need for specifications by consideringas attacks those queries for which user input changes the intended syntactic structure of the generated query. It checks conformance to this policy byconservatively characterizing the values a string variable may assume with a context free grammar, tracking the nonterminals that represent user-modifiable data, and modeling string operations precisely as language transducers. We have implemented the proposed technique for PHP, the most widely-used web scripting language. Our tool successfully discovered previously unknown and sometimes subtle vulnerabilities in real-world programs, has a low false positive rate, and scales to large programs (with approx. 100K loc).

REFERENCES

• 1: S. W. Boyd and A. D. Keromytis. SQLrand: Preventing SQL injection attacks. In International Conference on Applied Cryptography and Network Security (ACNS), LNCS, volume 2, 2004.
• 2: Gregory Buehrer , Bruce W. Weide , Paolo A. G. Sivilotti, Using parse tree validation to prevent SQL injection attacks, Proceedings of the 5th international workshop on Software engineering and middleware, September 05-06, 2005, Lisbon, Portugal [doi>10.1145/1108473.1108496]
• 3: A. S. Christensen, A. Moller, and M. I. Schwartzbach. Precise analysis of string expressions. In Proceedings of the 10th International Static Analysis Symposium, SAS'03, volume 2694 of LNCS, pages 1--18. Springer-Verlag, June 2003. Available from http://www.brics.dk/JSA/.
• 4: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 5: Jeffrey S. Foster , Tachio Terauchi , Alex Aiken, Flow-sensitive type qualifiers, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 6: Carl Gould , Zhendong Su , Premkumar Devanbu, Static Checking of Dynamically Generated Queries in Database Applications, Proceedings of the 26th International Conference on Software Engineering, p.645-654, May 23-28, 2004
• 7: William G. J. Halfond , Alessandro Orso , Panagiotis Manolios, Using positive tainting and syntax-aware evaluation to counter SQL injection attacks, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181797]
• 8: William G. J. Halfond , Alessandro Orso, AMNESIA: analysis and monitoring for NEutralizing SQL-injection attacks, Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, November 07-11, 2005, Long Beach, CA, USA [doi>10.1145/1101908.1101935]
• 9: K. J. Higgins. Cross-site scripting: Attackers' new favorite flaw, September 2006. http://www.darkreading.com/document.asp?doc_id=103774&WT.svl=news1_1.
• 10: Haruo Hosoya , Benjamin C. Pierce, XDuce: A Typed XML Processing Language (Preliminary Report), Selected papers from the Third International Workshop WebDB 2000 on The World Wide Web and Databases, p.226-244, May 18-19, 2000
• 11: Yao-Wen Huang , Fang Yu , Christian Hang , Chung-Hung Tsai , Der-Tsai Lee , Sy-Yen Kuo, Securing web application code by static analysis and runtime protection, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988679]
• 12: Nenad Jovanovic , Christopher Kruegel , Engin Kirda, Pixy: A Static Analysis Tool for Detecting Web Application Vulnerabilities (Short Paper), Proceedings of the 2006 IEEE Symposium on Security and Privacy (S&P'06), p.258-263, May 21-24, 2006 [doi>10.1109/SP.2006.29]
• 13: Nenad Jovanovic , Christopher Kruegel , Engin Kirda, Precise alias analysis for static detection of web application vulnerabilities, Proceedings of the 2006 workshop on Programming languages and analysis for security, June 10-10, 2006, Ottawa, Ontario, Canada [doi>10.1145/1134744.1134751]
• 14: Gaurav S. Kc , Angelos D. Keromytis , Vassilis Prevelakis, Countering code-injection attacks with instruction-set randomization, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948146]
• 15: C. Kirkegaard and A. Moller. Static analysis for Java Servlets and JSP. In Proceedings of the 13th International Static Analysis.
• 16: Monica S. Lam , John Whaley , V. Benjamin Livshits , Michael C. Martin , Dzintars Avots , Michael Carbin , Christopher Unkel, Context-sensitive program analysis as database queries, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065169]
• 17: V. Benjamin Livshits , Monica S. Lam, Finding security vulnerabilities in java applications with static analysis, Proceedings of the 14th conference on USENIX Security Symposium, p.18-18, July 31-August 05, 2005, Baltimore, MD
• 18: Michael Martin , Benjamin Livshits , Monica S. Lam, Finding application errors and security flaws using PQL: a program query language, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 19: David Melski , Thomas Reps, Interconvertbility of set constraints and context-free language reachability, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.74-89, June 12-13, 1997, Amsterdam, The Netherlands
• 20: Yasuhiko Minamide, Static approximation of dynamically generated Web pages, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060809]
• 21: M. Mohri and M. Nederhof. Regular approximation of context-free grammars through transformation. Robustness in Language and Speech Technology, pages 153--163, 2001.
• 22: Mehryar Mohri , Richard Sproat, An efficient compiler for weighted rewrite rules, Proceedings of the 34th annual meeting on Association for Computational Linguistics, p.231-238, June 24-27, 1996, Santa Cruz, California [doi>10.3115/981863.981894]
• 23: A. Nguyen-Tuong, S. Guarnieri, D. Greene, J. Shirley, and D. Evans. Automatically hardening web applications using precise tainting. In Twentieth IFIP International Information Security Conference (SEC'05), 2005.
• 24: T. Pietraszek and C. V. Berghe. Defending against Injection Attacks through Context-Sensitive String Evaluation. In Proceedings of the 8th International Symposium on Recent Advances in Intrusion Detection (RAID), Sept. 2005.
• 25: Zhendong Su , Gary Wassermann, The essence of command injection attacks in web applications, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.372-382, January 11-13, 2006, Charleston, South Carolina, USA
• 26: M. Sutton. How prevalent are sql injection vulnerabilities?, September 2006. http://portal.spidynamics.com/blogs/msutton/archive/2006/09/26/How-Prev% alent-Are-SQL-Injection-Vulnerabilities_3F00_.aspx.
• 27: N. Tabuchi, E. Sumii, and A. Yonezawa. Regular expression types for strings in a text processing language (extended abstract). In Proceedings of TIP'02 Workshop on Types in Programming, pages 1--18, July 2002.
• 28: Peter Thiemann, Grammar-based analysis of string expressions, Proceedings of the 2005 ACM SIGPLAN international workshop on Types in languages design and implementation, p.59-70, January 10-10, 2005, Long Beach, California, USA [doi>10.1145/1040294.1040300]
• 29: Larry Wall , Tom Christiansen , Randal L. Schwartz , Stephan Potter, Programming Perl (2nd ed.), O'Reilly & Associates, Inc., Sebastopol, CA, 1996
• 30: John Whaley , Monica S. Lam, Cloning-based context-sensitive pointer alias analysis using binary decision diagrams, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 31: Yichen Xie , Alex Aiken, Static detection of security vulnerabilities in scripting languages, Proceedings of the 15th conference on USENIX Security Symposium, p.13-13, July 31-August 04, 2006, Vancouver, B.C., Canada
• 32: Wei Xu , Sandeep Bhatkar , R. Sekar, Taint-enhanced policy enforcement: a practical approach to defeat a wide range of attacks, Proceedings of the 15th conference on USENIX Security Symposium, p.9-9, July 31-August 04, 2006, Vancouver, B.C., Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation

General Terms:
Languages, Security, Verification

Keywords:
static analysis, string analysis, web applications