Finding errors in components that exchange xml data

ABSTRACT

Two or more components (e.g., objects, modules, or programs) interoperate when they exchange data, such as XML data. Using Application Programming Interface (API) calls exported by XML parsers remains a primary mode of accessing and manipulating XML, and these API calls lead to various run-time errors in components that exchange XML data. Currently, no tool checks the source code of interoperating components for potential flaws caused by third-party API calls that lead to incorrect XML data exchanges and runtime errors, even when components are located within the same application

Our solution combines program abstraction and symbolic execution in order to reengineer the approximate schema of XML data that would be output by a component. This schema is compared using bisimulation with the schema of XML data that is expected by some other components. We describe our approach and give our error checking algorithm. We implemented our approach in a tool that we used on open source and commercial systems and discovered errors that were not detected during their design and testing.

REFERENCES

• 1: Anne Geraci , Freny Katki , Louise McMonegal , Bennett Meyer , John Lane , Paul Wilson , Jane Radatz , Mary Yee , Hugh Porteous , Fredrick Springsteel, IEEE Standard Computer Dictionary: Compilation of IEEE Standard Computer Glossaries, Institute of Electrical and Electronics Engineers Inc., The, 1991
• 2: Cost Analysis of Inadequate Interoperability in the U.S. Capital Facilities Industry, GCR 04-867. NIST, August 2004.
• 3: Institute for Software Research, University of California, Irvine, xADL 2.0 project, Apigen for xArch schemas,. http://www.isr.uci.edu/projects/xarchuci/tools-apigen.html, 2004.
• 4: Sun Microsystems, Java Architecture for XML Binding (JAXB),. http://java.sun.com/xml/jaxb, 2004.
• 5: Castor XML databinding framework,. http://www.castor.org/xml-framework.html, 2005.
• 6: Serge Abiteboul , Peter Buneman , Dan Suciu, Data on the Web: from relations to semistructured data and XML, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 7: 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
• 8: G. M. Bierman, E. Meijer, and W. Schulte. The essence of data access in cmega. In ECOOP, pages 287--311, 2005.
• 9: 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]
• 10: L. A. Clarke and D. J. Richardson, editors. Symbolic evaluation methods for program analysis. Prentice-Hall, 1981.
• 11: Bill Curtis , Herb Krasner , Neil Iscoe, A field study of the software design process for large systems, Communications of the ACM, v.31 n.11, p.1268-1287, Nov. 1988 [doi>10.1145/50087.50089]
• 12: Xiang Fu , Tevfik Bultan , Jianwen Su, Model checking XML manipulating software, Proceedings of the 2004 ACM SIGSOFT international symposium on Software testing and analysis, July 11-14, 2004, Boston, Massachusetts, USA
• 13: Matthew Harren , Mukund Raghavachari , Oded Shmueli , Michael G. Burke , Rajesh Bordawekar , Igor Pechtchanski , Vivek Sarkar, XJ: facilitating XML processing in Java, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060788]
• 14: Daniel Jackson , Mandana Vaziri, Finding bugs with a constraint solver, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.14-25, August 21-24, 2000, Portland, Oregon, United States
• 15: J. C. King. A program verifier. In IFIP Congress (1), pages 234--249, 1971.
• 16: James C. King, Symbolic execution and program testing, Communications of the ACM, v.19 n.7, p.385-394, July 1976 [doi>10.1145/360248.360252]
• 17: Christian Kirkegaard , Anders Mller , Michael I. Schwartzbach, Static Analysis of XML Transformations in Java, IEEE Transactions on Software Engineering, v.30 n.3, p.181-192, March 2004 [doi>10.1109/TSE.2004.1271173]
• 18: Andrew J. Ko , Brad A. Myers , Htet Htet Aung, Six Learning Barriers in End-User Programming Systems, Proceedings of the 2004 IEEE Symposium on Visual Languages - Human Centric Computing, p.199-206, September 26-29, 2004 [doi>10.1109/VLHCC.2004.47]
• 19: David Mandelin , Lin Xu , Rastislav Bodík , Doug Kimelman, Jungloid mining: helping to navigate the API jungle, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 20: J. Meier, S. Vasireddy, A. Babbar, and A. Mackman. Improving .NET application performance and scalability. Microsoft Corporation, 2004.
• 21: R. Schmelzer. Breaking XML to optimize performance. ZapThink LLC - special to SearchWebServices.com, Oct. 2002.
• 22: Diomidis Spinellis, A critique of the Windows application programming interface, Computer Standards & Interfaces, v.20 n.1, p.1-8, Nov. 16, 1998 [doi>10.1016/S0920-5489(98)00012-9]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Symbolic execution; Diagnostics

General Terms:
Algorithms, Experimentation, Verification

Keywords:
XML schema, bisimulation, interoperability, program analysis, schema validator, symbolic execution