Static detection of cross-site scripting vulnerabilities

ABSTRACT

Web applications support many of our daily activities, but they often have security problems, and their accessibility makes them easy to exploit. In cross-site scripting (XSS), an attacker exploits the trust a web client (browser) has for a trusted server and executes injected script on the browser with the server's privileges. In 2006, XSS constituted the largest class of newly reported vulnerabilities making it the most prevalent class of attacks today. Web applications have XSS vulnerabilities because the validation they perform on untrusted input does not suffice to prevent that input from invoking a browser's JavaScript interpreter, and this validation is particularly difficult to get right if it must admit some HTML mark-up. Most existing approaches to finding XSS vulnerabilities are taint-based and assume input validation functions to be adequate, so they either miss real vulnerabilities or report many false positives.

This paper presents a static analysis for finding XSS vulnerabilities that directly addresses weak or absent input validation. Our approach combines work on tainted information flow with string analysis. Proper input validation is difficult largely because of the many ways to invoke the JavaScript interpreter; we face the same obstacle checking for vulnerabilities statically, and we address it by formalizing a policy based on the W3C recommendation, the Firefox source code, and online tutorials about closed-source browsers. We provide effective checking algorithms based on our policy. We implement our approach and provide an extensive evaluation that finds both known and unknown vulnerabilities in real-world web applications.

REFERENCES

• 1: A. S. Christensen, A. Møller, 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/.
• 2: S. Christey. Vulnerability type distributions in CVE, Oct. 2006. http://cwe.mitre.org/documents/vuln-trends.html.
• 3: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 4: 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
• 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: Oystein Hallaraker , Giovanni Vigna, Detecting Malicious JavaScript Code in Mozilla, Proceedings of the 10th IEEE International Conference on Engineering of Complex Computer Systems, p.85-94, June 16-20, 2005 [doi>10.1109/ICECCS.2005.35]
• 8: 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.
• 9: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 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: 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]
• 13: 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, p.258-263, May 21-24, 2006 [doi>10.1109/SP.2006.29]
• 14: 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]
• 15: Engin Kirda , Christopher Kruegel , Giovanni Vigna , Nenad Jovanovic, Noxes: a client-side solution for mitigating cross-site scripting attacks, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France [doi>10.1145/1141277.1141357]
• 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: 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]
• 19: M. Mohri and M. Nederhof. Regular approximation of context-free grammars through transformation. Robustness in Language and Speech Technology, pages 153--163, 2001.
• 20: 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]
• 21: Charles Reis , John Dunagan , Helen J. Wang , Opher Dubrovsky , Saher Esmeir, BrowserShield: vulnerability-driven filtering of dynamic HTML, Proceedings of the 7th symposium on Operating systems design and implementation, November 06-08, 2006, Seattle, Washington
• 22: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 23: 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.
• 24: P. Vogt, F. Nentwich, N. Jovanovic, E. Kirda, C. Kruegel, and G. Vigna. Cross site scripting prevention with dynamic data tainting and static analysis. In Proceeding of the Network and Distributed System Security Symposium (NDSS), San Diego, CA, February 2007.
• 25: Gary Wassermann , Zhendong Su, Sound and precise analysis of web applications for injection vulnerabilities, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 26: 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
• 27: 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
• 28: Dachuan Yu , Ajay Chander , Nayeem Islam , Igor Serikov, JavaScript instrumentation for browser security, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France

INDEX TERMS

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

General Terms:
Languages, Security, Verification

Keywords:
cross-site scripting, input validation, static analysis, web applications