Dynamic test input generation for web applications

ABSTRACT

Web applications routinely handle sensitive data, and many people rely on them to support various daily activities, so errors can have severe and broad-reaching consequences. Unlike most desktop applications, many web applications are written in scripting languages, such as PHP. The dynamic features commonly supported by these languages significantly inhibit static analysis and existing static analysis of these languages can fail to produce meaningful results on realworld web applications.

Automated test input generation using the concolic testing framework has proven useful for finding bugs and improving test coverage on C and Java programs, which generally emphasize numeric values and pointer-based data structures. However, scripting languages, such as PHP, promote a style of programming for developing web applications that emphasizes string values, objects, and arrays.

In this paper, we propose an automated input test generation algorithm that uses runtime values to analyze dynamic code, models the semantics of string operations, and handles operations whose argument and return values may not share a common type. As in the standard concolic testing framework, our algorithm gathers constraints during symbolic execution. Our algorithm resolves constraints over multiple types by considering each variable instance individually, so that it only needs to invert each operation. By recording constraints selectively, our implementation successfully finds bugs in real-world web applications which state-of-the-art static analysis tools fail to analyze.

REFERENCES

• 1: M. Benedikt, J. Freire, and P. Godefroid. Veriweb: Automatically testing dynamic web sites. In Proceedings of the Eleventh International World Wide Web Conference (WWW 2002), 2002.
• 2: T. S. BV. Tiobe programming community index, September 2007. URL: http://www.tiobe.com/tpci.htm.
• 3: C. Cadar and D. R. Engler. Execution generated test cases: How to make system code crash itself. In Model Checking Software, 12th International SPIN Workshop, pages 2--23, 2005.
• 4: Cristian Cadar , Vijay Ganesh , Peter M. Pawlowski , David L. Dill , Dawson R. Engler, EXE: automatically generating inputs of death, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180445]
• 5: Manuel Costa , Miguel Castro , Lidong Zhou , Lintao Zhang , Marcus Peinado, Bouncer: securing software by blocking bad input, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 6: Christoph Csallner , Yannis Smaragdakis, JCrasher: an automatic robustness tester for Java, Software—Practice & Experience, v.34 n.11, p.1025-1050, September 2004 [doi>10.1002/spe.602]
• 7: E. de Vries, J. Gilbert, and P. Biggar. phc: The open source php compiler.
• 8: Michael Emmi , Rupak Majumdar , Koushik Sen, Dynamic test input generation for database applications, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273484]
• 9: A. Futoransky, E. Gutesman, and A. Waissbein. A dynamic technique for enhancing the security and privacy of web applications. In Proc. Black Hat USA, 2007.
• 10: Bhargav S. Gulavani , Thomas A. Henzinger , Yamini Kannan , Aditya V. Nori , Sriram K. Rajamani, SYNERGY: a new algorithm for property checking, Proceedings of the 14th ACM SIGSOFT international symposium on Foundations of software engineering, November 05-11, 2006, Portland, Oregon, USA [doi>10.1145/1181775.1181790]
• 11: William G. J. Halfond , Alessandro Orso, Improving test case generation for web applications using automated interface discovery, Proceedings of the the 6th joint meeting of the European software engineering conference and the ACM SIGSOFT symposium on The foundations of software engineering, September 03-07, 2007, Dubrovnik, Croatia [doi>10.1145/1287624.1287646]
• 12: 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
• 13: X. Jia and H. Liu. Rigorous and automatic testing of web applications, 2002.
• 14: 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]
• 15: M. Kunc. What do we know about language equations? In Developments in Language Theory, 11th International Conference (DLT 2007), pages 23--27, 2007.
• 16: David Chenho Kung , Chien-Hung Liu , Pei Hsia, An Object-Oriented Web Test Model for Testing Web Applications, 24th International Computer Software and Applications Conference, p.537-542, October 25-28, 2000
• 17: Yong Lei , James H. Andrews, Minimization of Randomized Unit Test Cases, Proceedings of the 16th IEEE International Symposium on Software Reliability Engineering, p.267-276, November 08-11, 2005 [doi>10.1109/ISSRE.2005.28]
• 18: J. Jenny Li , David Weiss , Howell Yee, Code-coverage guided prioritized test generation, Information and Software Technology, v.48 n.12, p.1187-1198, December, 2006 [doi>10.1016/j.infsof.2006.06.007]
• 19: 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]
• 20: Nicholas Nethercote , Julian Seward, Valgrind: a framework for heavyweight dynamic binary instrumentation, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 21: 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.
• 22: C. Pacheco and M. D. Ernst. Eclat: Automatic generation and classification of test inputs. In Object-Oriented Programming, 19th European Conference (ECOOP 2005), pages 504--527, 2005.
• 23: Wojciech Plandowski, Satisfiability of Word Equations with Constants is in PSPACE, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.495, October 17-18, 1999
• 24: 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]
• 25: Filippo Ricca , Paolo Tonella, Analysis and testing of Web applications, Proceedings of the 23rd International Conference on Software Engineering, p.25-34, May 12-19, 2001, Toronto, Ontario, Canada
• 26: K. Sen and G. Agha. Cute and jcute : Concolic unit testing and explicit path model-checking tools. In Computer Aided Verification, 18th International Conference (CAV 2006), pages 419--423, 2006. (Tool Paper).
• 27: Koushik Sen , Darko Marinov , Gul Agha, CUTE: a concolic unit testing engine for C, 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
• 28: Zhendong Su , Gary Wassermann, The essence of command injection attacks in web applications, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.372-382, January 11-13, 2006, Charleston, South Carolina, USA
• 29: 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
• 30: Yichen Xie , Alex Aiken, Static detection of security vulnerabilities in scripting languages, Proceedings of the 15th conference on USENIX Security Symposium, July 31-August 04, 2006, Vancouver, B.C., Canada

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

General Terms:
Reliability, Verification

Keywords:
automatic test generation, concolic testing, directed random testing, web applications