Michael Martin
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.
- A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1988. Google Scholar
Digital Library
- C. Allan, P. Augustinov, A. S. Christensen, L. Hendren, S. Kuzins, O. Lhotak, O. de Moor, D. Sereni, G. Sittampalam, and J. Tibble. Adding Trace Matching with Free Variables to AspectJ. In OOPSLA '05: Proceedings of the 20th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2005. Google ScholarDigital Library
- R. Alur, P. Cerny, P. Madhusudan, and W. Nam. Synthesis of Interface Specifications for Java Classes. In POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 98--109, 2005. Google ScholarDigital Library
- G. Ammons, R. Bodik, and J. Larus. Mining Specifications. In Proceedings of the 29th ACM Symposium on Principles of Programming Languages, pages 4--16, 2002. Google ScholarDigital Library
- C. Anley. Advanced SQL Injection in SQL Server Applications, 2002.Google Scholar
- B. S. Baker. Parameterized Pattern Matching by Boyer-Moore Type Algorithms. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 541--550, 1995. Google ScholarDigital Library
- J. Baker and W. C. Hsieh. Runtime Aspect Weaving Through Metaprogramming. In Proceedings of the First International Conference on Aspect-Oriented Software Development, 2002. Google ScholarDigital Library
- T. Ball and S. Rajamani. SLIC: A Specification Language for Interface Checking (of C). Technical Report MSR-TR-2001-21, Microsoft Research, January 2002.Google Scholar
- P. Bates. Debugging Heterogeneous Distributed Systems Using Event-Based Models of Behavior. In Proceedings of the 1988 ACM SIGPLAN and SIGOPS workshop on Parallel and Distributed Debugging, pages 11--22, 1988. Google ScholarDigital Library
- W. R. Bush, J. D. Pincus, and D. J. Sielaff. A Static Analyzer for Finding Dynamic Programming Errors. Software -Practice and Experience (SPE), 30:775--802, 2000. Google ScholarDigital Library
- J. C. Corbett, M. B. Dwyer, J. Hatcliff, S. Laubach, C. S. Pasareanu, Robby, and H. Zheng. Bandera: Extracting Finite-State Models from Java Source Code. In ICSE '00: Proceedings of the 22nd International Conference on Software Engineering, pages 439--448, 2000. Google ScholarDigital Library
- J. C. Corbett, M. B. Dwyer, J. Hatcliff, and Robby. A Language Framework for Expressing Checkable Properties of Dynamic Software. In SPIN '00: Proceedings of the 7th SPIN Workshop, pages 205--223, 2000. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.Google Scholar
- W. Du and A. P. Mathur. Testing for Software Vulnerability Using Environment Perturbation. In Proceedings of the International Conference on Dependable Systems and Networks (DSN 2000), Workshop On Dependability Versus Malicious Faults, pages 603--612, New York City, NY, June 2000. Google ScholarDigital Library
- M. D. Ernst, A. Czeisler, W. G. Griswold, and D. Notkin. Quickly Detecting Relevant Program Invariants. In ICSE 2000, Proceedings of the 22nd International Conference on Software Engineering, pages 449--458, Limerick, Ireland, June 7--9, 2000. Google ScholarDigital Library
- S. Goldsmith, R. O'Callahan, and A. Aiken. Relational Queries Over Program Traces. In Proceedings of the ACM SIGPLAN 2005 Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2005. Google ScholarDigital Library
- S. Hallem, B. Chelf, Y. Xie, and D. Engler. A System and Language for Building System-Specific, Static Analyses. In Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation (PLDI), pages 69--82, 2002. Google ScholarDigital Library
- 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.Google Scholar
- D. Heine and M. S. Lam. A Practical Flow-Sensitive and Context-Sensitive C and C++ Memory Leak Detector. In Proceedings of the ACM SIGPLAN 2003 Conference on Programming Language Design and Implementation (PLDI), pages 168--181, 2003. Google ScholarDigital Library
- G. J. Holzmann. The Model Checker SPIN. Software Engineering, 23(5):279--295, 1997. Google ScholarDigital Library
- D. Hovemeyer and W. Pugh. Finding Bugs is Easy. In Proceedings of the Onward! Track of the ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2004. Google ScholarDigital Library
- Y.-W. Huang, F. Yu, C. Hang, C.-H. Tsai, D.-T. Lee, and S.-Y. Kuo. Securing Web Application Code by Static Analysis and Runtime Protection. In Proceedings of the 13th Conference on the World Wide Web, pages 40--52, 2004. Google ScholarDigital Library
- D. Janzen and K. de Volder. Navigating and Querying Code Without Getting Lost. In Proceedings of the 2nd Annual Conference on Aspect-Oriented Software Development (AOSD), pages 178--187, 2003. Google ScholarDigital Library
- G. Kiczales, E. Hilsdale, J. Hugunin, M. Kersten, J. Palm, and W. G. Griswold. An Overview of AspectJ. Lecture Notes in Computer Science, 2072:327--355, 2001. Google ScholarDigital Library
- 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.Google Scholar
- S. Kost. An Introduction to SQL Injection Attacks for Oracle Developers, 2004.Google Scholar
- 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.Google ScholarCross Ref
- R. Lencevicius, U. Holzle, and A. K. Singh. Query-Based Debugging of Object-Oriented Programs. In OOPSLA '97: Proceedings of the 12th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 304--317, New York, NY, USA, 1997. ACM Press. Google ScholarDigital Library
- S. Lerner, T. Millstein, E. Rice, and C. Chambers. Automated Soundness Proofs for Dataflow Analyses and Transformations Via Local Rules. In POPL '05: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 364--377, 2005. Google ScholarDigital Library
- Y. A. Liu, T. Rothamel, F. Yu, S. D. Stoller, and N. Hu. Parametric Regular Path Queries. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation (PLDI), pages 219--230, 2004. Google ScholarDigital Library
- B. Livshits and T. Zimmermann. DynaMine: A Framework for Finding Common Bugs by Mining Software Revision Histories. In Proceedings of the ACM SIGSOFT 2005 Symposium on the Foundations of Software Engineering (FSE), Sept. 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Q. H. Mahmoud. Password Masking in the Java Programming Language. http://java.sun.com/developer/technicalArticles/Security/pwordmask/, July 2004.Google Scholar
- F.-M. S. mailing list. Vulnerability Scanner for SQL injection. http://www.derkeiler.com/Mailing-Lists/securityfocus/focus-ms/2003-09/0110.html, 2003.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- S. Northover and M. Wilson. SWT : The Standard Widget Toolkit, Volume 1. Addison-Wesley Professional, 2004. Google ScholarDigital Library
- R. A. Olsson, R. H. Cawford, and W. W. Ho. A Dataflow Approach to Event-Based Debugging. Software - Practice and Experience, 21(2):209--230, 1991. Google ScholarDigital Library
- D. Orleans and K. Lieberherr. DJ: Dynamic Adaptive Programming in Java. In Reflection 2001: Meta-level Architectures and Separation of Crosscutting Concerns , Kyoto, Japan, September 2001. Springer Verlag. 8 pages. Google ScholarDigital Library
- OWASP. Ten Most Critical Web Application Security Vulnerabilities, 2004.Google Scholar
- D. Reimer, E. Schonberg, K. Srinivas, H. Srinivasan, B. Alpern, R. D. Johnson, A. Kershenbaum, and L. Koved. SABER: Smart Analysis Based Error Reduction. In Proceedings of International Symposium on Software Testing and Analysis, 2004. Google ScholarDigital Library
- S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A Dynamic Data Race Detector for Multithreaded Programs. ACM Trans. Comput. Syst., 15(4):391--411, 1997. Google ScholarDigital Library
- S. R. Schach. Object-Oriented and Classical Software Engineering. McGraw-Hill Science/Engineering/Math, 2004. Google ScholarDigital Library
- M. Schonefeld. Hunting Flaws in JDK. In Blackhat Europe, 2003.Google Scholar
- http://patterns.projects.cis.ksu.edu/.Google Scholar
- K. Spett. Cross-Site Scripting: Are Your Web Applications Vulnerable. http://www.spidynamics.com/support/whitepapers/SPIcross-sitescripting.pdf, 2002.Google Scholar
- B. A. Tate. Bitter Java. Manning Publications Co., 2002. Google ScholarDigital Library
- M. Vernon. Top Five Threats. ComputerWeekly.com (http://www.computerweekly.com/Article129980.htm), April 2004.Google Scholar
- J. Voas and G. McGraw. Software Fault Injection: Innoculating Programs Against Errors. John Wiley and Sons, 1997. Google ScholarDigital Library
- 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.Google Scholar
- R. J. Walker and K. Viggers. Implementing Protocols Via Declarative Event Patterns. In SIGSOFT '04/FSE-12: Proceedings of the 12th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 159--169, New York, NY, USA, 2004. ACM Press. Google ScholarDigital Library
- Web Application Security Consortium. Threat Classification. http://www.webappsec.org/tc/WASC-TC-v1 0.pdf, 2004.Google Scholar
- 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. Google ScholarDigital Library
- W. Weimer and G. C. Necula. Finding and Preventing Run-Time Error Handling Mistakes. In 19th Annual ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA '04), Oct. 2004. Google ScholarDigital Library
- J. Whaley and M. S. Lam. Cloning-Based Context-Sensitive Pointer Alias Analysis Using Binary Decision Diagrams. In Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation (PLDI), 2004. Google ScholarDigital Library
- J. Whaley, M. Martin, and M. S. Lam. Automatic Extraction of Object-Oriented Component Interfaces. In Proceedings of the International Symposium of Software Testing and Analysis, pages 218--228, 2002. Google ScholarDigital Library
- J. A. Whittaker and H. H. Thompson. How to Break Software Security. Addison Wesley, 2003.Google Scholar
- Y. Xie and A. Aiken. Scalable Error Detection Using Boolean Satisfiability. In Proceedings of the 32nd ACM Symposium on Principles of Programming Languages, 2005. Google ScholarDigital Library
Index Terms
- Finding application errors and security flaws using PQL: a program query language
Recommendations
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 applicationsA 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 ...
Securing web applications with static and dynamic information flow tracking
PEPM '08: Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulationSQL injection and cross-site scripting are two of the most common security vulnerabilities that plague web applications today. These and many others result from having unchecked data input reach security-sensitive operations. This paper describes a ...
Melton: a practical and precise memory leak detection tool for C programs
Memory leaks are a common type of defect that is hard to detect manually. Existing memory leak detection tools suffer from lack of precise interprocedural analysis and path-sensitivity. To address this problem, we present a static interprocedural ...
Comments