skip to main content
article

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

Published: 12 October 2005 Publication History

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]
A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1988.
[2]
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.
[3]
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.
[4]
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.
[5]
C. Anley. Advanced SQL Injection in SQL Server Applications, 2002.
[6]
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.
[7]
J. Baker and W. C. Hsieh. Runtime Aspect Weaving Through Metaprogramming. In Proceedings of the First International Conference on Aspect-Oriented Software Development, 2002.
[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]
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.
[10]
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.
[11]
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.
[12]
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.
[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]
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.
[16]
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.
[17]
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.
[18]
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.
[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]
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.
[21]
G. J. Holzmann. The Model Checker SPIN. Software Engineering, 23(5):279--295, 1997.
[22]
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.
[23]
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.
[24]
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.
[25]
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.
[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]
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.
[30]
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.
[31]
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.
[32]
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.
[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]
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.
[43]
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.
[44]
OWASP. Ten Most Critical Web Application Security Vulnerabilities, 2004.
[45]
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.
[46]
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.
[47]
S. 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]
B. A. Tate. Bitter Java. Manning Publications Co., 2002.
[52]
M. Vernon. Top Five Threats. ComputerWeekly.com (http://www.computerweekly.com/Article129980.htm), April 2004.
[53]
J. Voas and G. McGraw. Software Fault Injection: Innoculating Programs Against Errors. John Wiley and Sons, 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]
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.
[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]
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.
[59]
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.
[60]
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.
[61]
J. A. Whittaker and H. H. Thompson. How to Break Software Security. Addison Wesley, 2003.
[62]
Y. Xie and A. Aiken. Scalable Error Detection Using Boolean Satisfiability. In Proceedings of the 32nd ACM Symposium on Principles of Programming Languages, 2005.

Cited By

View all
  • (2024)Efficient Detection of Java Deserialization Gadget Chains via Bottom-up Gadget Search and Dataflow-aided Payload Construction2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00150(3961-3978)Online publication date: 19-May-2024
  • (2024)A neuro-fuzzy security risk assessment system for software development life cycleHeliyon10.1016/j.heliyon.2024.e3349510:13(e33495)Online publication date: Jul-2024
  • (2023)Testing the channels of convolutional neural networksProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i12.26726(14774-14782)Online publication date: 7-Feb-2023
  • Show More Cited By

Index Terms

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

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 40, Issue 10
    Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming systems languages and applications
    October 2005
    531 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/1103845
    Issue’s Table of Contents
    • cover image ACM Conferences
      OOPSLA '05: Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications
      October 2005
      562 pages
      ISBN:1595930310
      DOI:10.1145/1094811
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 12 October 2005
    Published in SIGPLAN Volume 40, Issue 10

    Check for updates

    Author Tags

    1. SQL injection
    2. bug finding
    3. pattern matching
    4. program traces
    5. resource leaks
    6. web applications

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)46
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 09 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Efficient Detection of Java Deserialization Gadget Chains via Bottom-up Gadget Search and Dataflow-aided Payload Construction2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00150(3961-3978)Online publication date: 19-May-2024
    • (2024)A neuro-fuzzy security risk assessment system for software development life cycleHeliyon10.1016/j.heliyon.2024.e3349510:13(e33495)Online publication date: Jul-2024
    • (2023)Testing the channels of convolutional neural networksProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i12.26726(14774-14782)Online publication date: 7-Feb-2023
    • (2023)Tabby: Automated Gadget Chain Detection for Java Deserialization Vulnerabilities2023 53rd Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)10.1109/DSN58367.2023.00028(179-192)Online publication date: Jun-2023
    • (2023)Insecurity Refactoring: Automated Injection of Vulnerabilities in Source CodeComputers & Security10.1016/j.cose.2023.103121128(103121)Online publication date: May-2023
    • (2022)CerberusProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3559381(2459-2473)Online publication date: 7-Nov-2022
    • (2022)Fluently specifying taint-flow queries with TQLEmpirical Software Engineering10.1007/s10664-022-10165-y27:5Online publication date: 1-Sep-2022
    • (2021)Example-guided synthesis of relational queriesProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454098(1110-1125)Online publication date: 19-Jun-2021
    • (2021)RML: Theory and practice of a domain specific language for runtime verificationScience of Computer Programming10.1016/j.scico.2021.102610205(102610)Online publication date: May-2021
    • (2021)Detecting trend deviations with generic stream processing patternsInformation Systems10.1016/j.is.2019.101446101(101446)Online publication date: Nov-2021
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media