Validating structural properties of nested objects

ABSTRACT

Frameworks are widely used to facilitate software reuse and accelerate development time. However, there are currently no systematic mechanisms to enforce the explicit and implicit rules of these frameworks. This paper focuses on a class of framework rules that place restrictions on the properties of data structures in framework applications. We present a mechanism to enforce these rules by the use of a generic "bad store template" which can be customized for different rule instances. We demonstrate the use of this template to validate specific bad store rules within J2EE framework applications. Violations of these rules cause subtle defects which manifest themselves at runtime as data loss, data corruption, or race conditions. Our algorithm to detect "bad stores" is implemented in the Smart Analysis-Based Error Reduction (SABER) validation tool, where we pay special attention to facilitating problem understanding and remediation, by providing detailed problem explanations. We present experimental results on four commercially deployed e-commerce applications that show over 200 "bad stores".

REFERENCES

• 1: Ole Agesen, The Cartesian Product Algorithm: Simple and Precise Type Inference Of Parametric Polymorphism, Proceedings of the 9th European Conference on Object-Oriented Programming, p.2-26, August 07-11, 1995
• 2: Thomas Ball , Sriram K. Rajamani, The SLAM project: debugging system software via static analysis, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-3, January 16-18, 2002, Portland, Oregon
• 3: D. Bacon, J. Bloch, J. Bogda, C. Click, P. Haahr, D. Lea, T. May, J. Maessen, J.D. Mitchell, K. Nilsen, W. Pugh, E.G. Sirer. The "Double check locking is broken". http://www.cs.umd.edu/ pugh/java/memoryModel/DoubleCheckedLocking.html.
• 4: 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]
• 5: Hao Chen , David Wagner, MOPS: an infrastructure for examining security properties of software, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586142]
• 6: Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 7: 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]
• 8: Manuvir Das , Sorin Lerner , Mark Seigle, ESP: path-sensitive program verification in polynomial time, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 9: D. L. Detlefs. An overview of the extended static checking system. SIGSOFT Proceedings of the First Workshop on Formal Methods in Software Practice, January 1996, 1--9.
• 10: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 11: Dawson Engler , Ken Ashcraft, RacerX: effective, static detection of race conditions and deadlocks, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 12: D. Engler, B. Chelf, A. Chou and S. Hallem, Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions, In Proc. of SOSP, October 2000, 1--16.
• 13: David Evans, Static detection of dynamic memory errors, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.44-53, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 14: 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
• 15: D. Hovemeyer and W. Pugh, Finding Bugs is Easy, <http://www.cs.umd.edu/ pugh/java/bugs/docs/findbugsPaper.pdf>
• 16: Daniel Jackson, Aspect: detecting bugs with abstract dependences, ACM Transactions on Software Engineering and Methodology (TOSEM), v.4 n.2, p.109-145, April 1995 [doi>10.1145/210134.210135]
• 17: JavaTM 2 Platform, Enterprise Edition Specification, v1.4 API Specification, Sun Microsystems. 11/24/2003.
• 18: S.C. Johnson. Lint, a C program checker. Unix Programmer's Manual, 4.2 Berkeley Software Distribution Supplementary Docs; U.C. Berkeley, 1984.
• 19: Larry Koved , Marco Pistoia , Aaron Kershenbaum, Access rights analysis for Java, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 20: K.M.Leino, G. Nelson, and J. Saxe. ESC/Java User's Manual. Technical note 2000-002, Compaq Systems Research Center, Oct. 2001.
• 21: Ana Milanova , Atanas Rountev , Barbara G. Ryder, Parameterized object sensitivity for points-to and side-effect analyses for Java, Proceedings of the 2002 ACM SIGSOFT international symposium on Software testing and analysis, July 22-24, 2002, Roma, Italy
• 22: Parasoft Corporation. Automatic Java{TM} software and component testing: using Jtest to automate unit testing and coding standard enforcement, <http://www.parasoft.com/jsp/products/article.jsp?articleId=839&product=Jtest>>.
• 23: D. Reimer, K. Srinivas, H. Srinivasan, RD Johnson, and L. Koved. SABER: Smart Analysis Based Error Reduction. IBM Research Report, 2004.
• 24: 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]
• 25: N. Sterling. Warlock: a static data race analysis tool. In USENIX Proceedings, Winter Technical Conference, 1993, 97--106.
• 26: J. Viega , J. T. Bloch , Y. Kohno , G. McGraw, ITS4: A static vulnerability scanner for C and C++ code, Proceedings of the 16th Annual Computer Security Applications Conference, p.257, December 11-15, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.3 Coding Tools and Techniques

General Terms:
Design, Management, Performance, Verification

Keywords:
code validation, context sensitive analysis, frameworks