The essence of command injection attacks in web applications

ABSTRACT

Web applications typically interact with a back-end database to retrieve persistent data and then present the data to the user as dynamically generated output, such as HTML web pages. However, this interaction is commonly done through a low-level API by dynamically constructing query strings within a general-purpose programming language, such as Java. This low-level interaction is ad hoc because it does not take into account the structure of the output language. Accordingly, user inputs are treated as isolated lexical entities which, if not properly sanitized, can cause the web application to generate unintended output. This is called a command injection attack, which poses a serious threat to web application security. This paper presents the first formal definition of command injection attacks in the context of web applications, and gives a sound and complete algorithm for preventing them based on context-free grammars and compiler parsing techniques. Our key observation is that, for an attack to succeed, the input that gets propagated into the database query or the output document must change the intended syntactic structure of the query or document. Our definition and algorithm are general and apply to many forms of command injection attacks. We validate our approach with SqlCheckS, an implementation for the setting of SQL command injection attacks. We evaluated SqlCheckS on real-world web applications with systematically compiled real-world attack data as input. SqlCheckS produced no false positives or false negatives, incurred low runtime overhead, and applied straightforwardly to web applications written in different languages.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: C. Anley. Advanced SQL Injection in SQL Server Applications. An NGSSoftware Insight Security Research (NISR) publication, 2002. http://www.nextgenss.com/papers/advanced_sql_injection.pdf.
• 3: G. Bierman, E. Meijer, and W. Schulte. The essence of data access in Cω. In The 19th European Conference on Object-Oriented Programming (ECOOP), 2005. To appear.
• 4: 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.
• 5: Claus Brabrand , Anders Møller , Mikkel Ricky , Michael I. Schwartzbach, PowerForms: Declarative client-side form field validation, World Wide Web, v.3 n.4, p.205-214, December 2000 [doi>10.1023/A:1018772405468]
• 6: Gregory T. 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]
• 7: William R. Cook , Siddhartha Rai, Safe query objects: statically typed objects as remotely executable queries, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062488]
• 8: David Wagner , Drew Dean, Intrusion Detection via Static Analysis, Proceedings of the 2001 IEEE Symposium on Security and Privacy, p.156, May 14-16, 2001
• 9: R. DeLine and M. Fähndrich. The Fugue protocol checker: Is your software baroque? Technical Report MSR-TR-2004-07, Microsoft Research, Jan. 2004. http://research.microsoft.com/~maf/Papers/tr-2004-07.pdf.
• 10: Jeffrey S. Foster , Manuel Fähndrich , Alexander Aiken, A theory of type qualifiers, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.192-203, May 01-04, 1999, Atlanta, Georgia, United States
• 11: Michael Furr , Jeffrey S. Foster, Checking type safety of foreign function calls, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 12: 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
• 13: 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]
• 14: Yao-Wen Huang , Shih-Kun Huang , Tsung-Po Lin , Chung-Hung Tsai, Web application security assessment by fault injection and behavior monitoring, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775174]
• 15: 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]
• 16: John B. Kam , Jeffrey D. Ullman, Global Data Flow Analysis and Iterative Algorithms, Journal of the ACM (JACM), v.23 n.1, p.158-171, Jan. 1976 [doi>10.1145/321921.321938]
• 17: Kavado, Inc. InterDo Vers. 3.0, 2003.
• 18: Gary A. Kildall, A unified approach to global program optimization, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.194-206, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512945]
• 19: A. Klein. Blind XPath Injection. Whitepaper from Watchfire, 2005.
• 20: Eugene Kohlbecker , Daniel P. Friedman , Matthias Felleisen , Bruce Duba, Hygienic macro expansion, Proceedings of the 1986 ACM conference on LISP and functional programming, p.151-161, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319859]
• 21: Larry Koved , Marco Pistoia , Aaron Kershenbaum, Access rights analysis for Java, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 22: 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]
• 23: R. Lemos. Flawed USC admissions site allowed access to applicant data, July 2005. http://www.securityfocus.com/news/11239.
• 24: V. B. Livshits and M. S. Lam. Finding security vulnerabilities in Java applications with static analysis. In Usenix Security Symposium, Aug. 2005. To appear.
• 25: K. J. L. Mark Grechanik, William R. Cook. Static checking of object-oriented polylingual systems. http://www.cs.utexas.edu/users/wcook/Drafts/FOREL.pdf, Mar. 2005.
• 26: 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
• 27: Russell A. McClure , Ingolf H. Krüger, SQL DOM: compile time checking of dynamic SQL statements, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA [doi>10.1145/1062455.1062487]
• 28: S. McPeak. Elsa: An Elkhound-based C++ Parser, May 2005. http://www.cs.berkeley.edu/~smcpeak/elkhound/.
• 29: E. Meijer, W. Schulte, and G. Bierman. Unifying tables, objects and documents, 2003.
• 30: Gleb Naumovich , Paolina Centonze, Static analysis of role-based access control in J2EE applications, ACM SIGSOFT Software Engineering Notes, v.29 n.5, September 2004 [doi>10.1145/1022494.1022530]
• 31: 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.
• 32: 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.
• 33: Sanctum Inc. Web Application Security Testing-Appscan 3.5. http://www.sanctuminc.com.
• 34: Sanctum Inc. AppShield 4.0 Whitepaper., 2002. http://www.sanctuminc.com.
• 35: David Scott , Richard Sharp, Abstracting application-level web security, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511498]
• 36: D. Scott and R. Sharp. Specifying and enforcing application-level web security policies. IEEE Transactions on Knowledge and Data Engineering, 15(4):771--783, 2003.
• 37: Security Focus. http://www.securityfocus.com.
• 38: SPI Dynamics. Web Application Security Assessment. SPI Dynamics Whitepaper, 2003.
• 39: Walid Taha , Tim Sheard, Multi-stage programming with explicit annotations, Proceedings of the 1997 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.203-217, June 12-13, 1997, Amsterdam, The Netherlands
• 40: Larry Wall , Mike Loukides, Programming Perl, O'Reilly & Associates, Inc., Sebastopol, CA, 2000
• 41: G. Wassermann and Z. Su. An Analysis Framework for Security in Web Applications. In Proceedings of the FSE Workshop on Specification and Verification of Component-Based Systems (SAVCBS 2004), pages 70--78, 2004.
• 42: Daniel Weise , Roger Crew, Programmable syntax macros, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.156-165, June 21-25, 1993, Albuquerque, New Mexico, United States
• 43: 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

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Parsing; Grammar types (e.g., context-free, context-sensitive)

General Terms:
Algorithms, Experimentation, Languages, Reliability, Security, Verification

Keywords:
command injection attacks, grammars, parsing, runtime verification, web applications