Finding application errors and security flaws using PQL: a program query language

ABSTRACT

A number of effective error detection tools have been built in recent years to check if a program conforms to certain design rules. An important class of design rules deals with sequences of events asso-ciated with a set of related objects. This paper presents a language called PQL (Program Query Language) that allows programmers to express such questions easily in an application-specific context. A query looks like a code excerpt corresponding to the shortest amount of code that would violate a design rule. Details of the tar-get application's precise implementation are abstracted away. The programmer may also specify actions to perform when a match is found, such as recording relevant information or even correcting an erroneous execution on the fly.We have developed both static and dynamic techniques to find solutions to PQL queries. Our static analyzer finds all potential matches conservatively using a context-sensitive, flow-insensitive, inclusion-based pointer alias analysis. Static results are also use-ful in reducing the number of instrumentation points for dynamic analysis. Our dynamic analyzer instruments the source program to catch all violations precisely as the program runs and to optionally perform user-specified actions.We have implemented the techniques described in this paper and found 206 errors in 6 large real-world open-source Java applica-tions containing a total of nearly 60,000 classes. These errors are important security flaws, resource leaks, and violations of consis-tency invariants. The combination of static and dynamic analysis proves effective at addressing a wide range of debugging and pro-gram comprehension queries. We have found that dynamic analysis is especially suitable for preventing errors such as security vulner-abilities at runtime.

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: Chris Allan , Pavel Avgustinov , Aske Simon Christensen , Laurie Hendren , Sascha Kuzins , Ondřej Lhoták , Oege de Moor , Damien Sereni , Ganesh Sittampalam , Julian Tibble, Adding trace matching with free variables to AspectJ, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 3: Rajeev Alur , Pavol Černý , P. Madhusudan , Wonhong Nam, Synthesis of interface specifications for Java classes, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.98-109, January 12-14, 2005, Long Beach, California, USA
• 4: Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.4-16, January 16-18, 2002, Portland, Oregon
• 5: C. Anley. Advanced SQL Injection in SQL Server Applications, 2002.
• 6: Brenda S. Baker, Parameterized pattern matching by Boyer-Moore-type algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.541-550, January 22-24, 1995, San Francisco, California, United States
• 7: Jason Baker , Wilson Hsieh, Runtime aspect weaving through metaprogramming, Proceedings of the 1st international conference on Aspect-oriented software development, April 22-26, 2002, Enschede, The Netherlands [doi>10.1145/508386.508396]
• 8: T. Ball and S. Rajamani. SLIC: A Specification Language for Interface Checking (of C). Technical Report MSR-TR-2001-21, Microsoft Research, January 2002.
• 9: Peter Bates, Debugging heterogeneous distributed systems using event-based models of behavior, Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and distributed debugging, p.11-22, May 05-06, 1988, Madison, Wisconsin, United States
• 10: William R. Bush , Jonathan D. Pincus , David J. Sielaff, A static analyzer for finding dynamic programming errors, Software—Practice & Experience, v.30 n.7, p.775-802, June 2000 [doi>10.1002/(SICI)1097-024X(200006)30:7<775::AID-SPE309>3.0.CO;2-H]
• 11: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Shawn Laubach , Corina S. Păsăreanu , Robby , Hongjun Zheng, Bandera: extracting finite-state models from Java source code, Proceedings of the 22nd international conference on Software engineering, p.439-448, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337234]
• 12: James C. Corbett , Matthew B. Dwyer , John Hatcliff , Robby, A Language Framework for Expressing Checkable Properties of Dynamic Software, Proceedings of the 7th International SPIN Workshop on SPIN Model Checking and Software Verification, p.205-223, August 30-September 01, 2000
• 13: R. F. Crew. ASTLOG: A Language for Examining Abstract Syntax Trees. In Proceedings of the USENIX Conference on Domain-Specific Languages, pages 229--242, 1997.
• 14: W. Du and A. P. Mathur. Vulnerability Testing of Software System Using Fault Injection. Technical report, COAST, Purdue University, West Lafayette, IN, US, April 1998.
• 15: Wenliang Du , Aditya P. Mathur, Testing for Software Vulnerability Using Environment Perturbation, Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8), p.603-612, June 25-28, 2000
• 16: Michael D. Ernst , Adam Czeisler , William G. Griswold , David Notkin, Quickly detecting relevant program invariants, Proceedings of the 22nd international conference on Software engineering, p.449-458, June 04-11, 2000, Limerick, Ireland [doi>10.1145/337180.337240]
• 17: Simon Goldsmith , Robert O'Callahan , Alex Aiken, Relational queries over program traces, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 18: Seth Hallem , Benjamin Chelf , Yichen Xie , Dawson Engler, A system and language for building system-specific, static analyses, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 19: R. Hastings and B. Joyce. Purify: Fast Detection of Memory Leaks and Access Errors. In Proceedings of the Winter USENIX Conference, pages 125--136, December 1992.
• 20: David L. Heine , Monica S. Lam, A practical flow-sensitive and context-sensitive C and C++ memory leak detector, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 21: Gerard J. Holzmann, The Model Checker SPIN, IEEE Transactions on Software Engineering, v.23 n.5, p.279-295, May 1997 [doi>10.1109/32.588521]
• 22: David Hovemeyer , William Pugh, Finding bugs is easy, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA [doi>10.1145/1028664.1028717]
• 23: 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]
• 24: Doug Janzen , Kris De Volder, Navigating and querying code without getting lost, Proceedings of the 2nd international conference on Aspect-oriented software development, p.178-187, March 17-21, 2003, Boston, Massachusetts [doi>10.1145/643603.643622]
• 25: Gregor Kiczales , Erik Hilsdale , Jim Hugunin , Mik Kersten , Jeffrey Palm , William G. Griswold, An Overview of AspectJ, Proceedings of the 15th European Conference on Object-Oriented Programming, p.327-353, June 18-22, 2001
• 26: A. Klein. Divide and Conquer: HTTP Response Splitting, Web Cache Poisoning Attacks, and Related Topics. http://www.packetstormsecurity.org/papers/general/whitepaper httpresponse.pdf, 2004.
• 27: S. Kost. An Introduction to SQL Injection Attacks for Oracle Developers, 2004.
• 28: P. Lam and M. Rinard. A Type System and Analysis for the Automatic Extraction and Enforcement of Design Information. In Proceedings of the 17th European Conference on Object-Oriented Programming, pages 275--302, Darmstadt, Germany, July 2003.
• 29: Raimondas Lencevicius , Urs Hölzle , Ambuj K. Singh, Query-based debugging of object-oriented programs, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.304-317, October 05-09, 1997, Atlanta, Georgia, United States
• 30: Sorin Lerner , Todd Millstein , Erika Rice , Craig Chambers, Automated soundness proofs for dataflow analyses and transformations via local rules, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.364-377, January 12-14, 2005, Long Beach, California, USA
• 31: Yanhong A. Liu , Tom Rothamel , Fuxiang Yu , Scott D. Stoller , Nanjun Hu, Parametric regular path queries, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 32: Benjamin Livshits , Thomas Zimmermann, DynaMine: finding common error patterns by mining software revision histories, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 33: V. B. Livshits and M. S. Lam. Finding Security Errors in Java Programs with Static Analysis. In Proceedings of the 14th Usenix Security Symposium, Aug. 2005.
• 34: Q. H. Mahmoud. Password Masking in the Java Programming Language. http://java.sun.com/developer/technicalArticles/Security/pwordmask/, July 2004.
• 35: F.-M. S. mailing list. Vulnerability Scanner for SQL injection. http://www.derkeiler.com/Mailing-Lists/securityfocus/focus-ms/2003-09/0110.html, 2003.
• 36: H. Masuhara and K. Kawauchi. Dataflow Pointcut in Aspect-Oriented Programming. In APLAS'03 - the First Asian Symposium on Programming Languages and Systems, pages 105--121, 2003.
• 37: Netcontinuum, Inc. Web Application Firewall: How NetContinuum Stops the 21 Classes of Web Application Threats. http://www.netcontinuum.com/products/whitePapers/getPDF.cfm?n=NC WhitePaper WebFirewall.pdf, 2004.
• 38: N. Nethercote and A. Mycroft. Redux: A Dynamic Dataflow Tracer. In O. Sokolsky and M. Viswanathan, editors, Electronic Notes in Theoretical Computer Science, volume 89. Elsevier, 2003.
• 39: N. Nethercote and J. Seward. Valgrind: A Program Supervision Framework. In O. Sokolsky and M. Viswanathan, editors, Electronic Notes in Theoretical Computer Science, volume 89. Elsevier, 2003.
• 40: A. Nguyen-Tuong, S. Guarnieri, D. Greene, J. Shirley, and D. Evans. Automatically Hardening Web Applications Using Precise Tainting. In Proceedings of the 20th IFIP International Information Security Conference, 2005.
• 41: S. Northover and M. Wilson. SWT : The Standard Widget Toolkit, Volume 1. Addison-Wesley Professional, 2004.
• 42: Ronald A. Olsson , Richard H. Crawford , W. Wilson Ho, A dataflow approach to event-based debugging, Software—Practice & Experience, v.21 n.2, p.209-229, Feb. 1991 [doi>10.1002/spe.4380210207]
• 43: Doug Orleans , Karl J. Lieberherr, DJ: Dynamic Adaptive Programming in Java, Proceedings of the Third International Conference on Metalevel Architectures and Separation of Crosscutting Concerns, p.73-80, September 25-28, 2001
• 44: OWASP. Ten Most Critical Web Application Security Vulnerabilities, 2004.
• 45: Darrell Reimer , Edith Schonberg , Kavitha Srinivas , Harini Srinivasan , Bowen Alpern , Robert D. Johnson , Aaron Kershenbaum , Larry Koved, SABER: smart analysis based error reduction, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 46: Stefan Savage , Michael Burrows , Greg Nelson , Patrick Sobalvarro , Thomas Anderson, Eraser: a dynamic data race detector for multithreaded programs, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.391-411, Nov. 1997 [doi>10.1145/265924.265927]
• 47: Stephen R Schach, Object-Oriented and Classical Software Engineering, McGraw-Hill Science/Engineering/Math, 2004
• 48: M. Schonefeld. Hunting Flaws in JDK. In Blackhat Europe, 2003.
• 49: http://patterns.projects.cis.ksu.edu/.
• 50: K. Spett. Cross-Site Scripting: Are Your Web Applications Vulnerable. http://www.spidynamics.com/support/whitepapers/SPIcross-sitescripting.pdf, 2002.
• 51: Bruce A. Tate, Bitter Java, Manning Publications Co., Greenwich, CT, 2002
• 52: M. Vernon. Top Five Threats. ComputerWeekly.com (http://www.computerweekly.com/Article129980.htm), April 2004.
• 53: Jeffrey M. Voas , Gary McGraw, Software fault injection: inoculating programs against errors, John Wiley & Sons, Inc., New York, NY, 1997
• 54: D. Wagner, J. Foster, E. Brewer, and A. Aiken. A First Step Towards Automated Detection of Buffer Overrun Vulnerabilities. In Proceedings of Network and Distributed Systems Security Symposium, pages 3--17, 2000.
• 55: Robert J. Walker , Kevin Viggers, Implementing protocols via declarative event patterns, Proceedings of the 12th ACM SIGSOFT twelfth international symposium on Foundations of software engineering, October 31-November 06, 2004, Newport Beach, CA, USA
• 56: Web Application Security Consortium. Threat Classification. http://www.webappsec.org/tc/WASC-TC-v1 0.pdf, 2004.
• 57: W. Weimer and G. Necula. Mining Temporal Specifications for Error Detection. In Proceedings of the 11th International Conference on Tools and Algorithms For The Construction And Analysis Of Systems, pages 461--476, Apr. 2005.
• 58: Westley Weimer , George C. Necula, Finding and preventing run-time error handling mistakes, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 59: 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
• 60: John Whaley , Michael C. Martin , Monica S. Lam, Automatic extraction of object-oriented component interfaces, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 61: J. A. Whittaker and H. H. Thompson. How to Break Software Security. Addison Wesley, 2003.
• 62: Yichen Xie , Alex Aiken, Scalable error detection using boolean satisfiability, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.351-363, January 12-14, 2005, Long Beach, California, USA

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

General Terms:
Languages, Reliability, Security

Keywords:
SQL injection, bug finding, pattern matching, program traces, resource leaks, web applications