Stream firewalling of xml constraints

ABSTRACT

As XML-based messages have become common in many client-server protocols, there is a need to protect application servers from invalid or dangerous messages. This leads to the XML stream firewalling problem; that of applying integrity constraints against a large number of simultaneous streams. We conduct the first investigation of a constraint engine optimized for the generation of XML stream firewalls. We isolate a class of DTDs and XPath constraints which support the generation of low-space filters, and provide algorithms for generating firewalls with low per-input-character time and per-stream space. We give experimental results which show that we have achieved these goals in practice.

REFERENCES

• 1: Mehmet Altinel , Michael J. Franklin, Efficient Filtering of XML Documents for Selective Dissemination of Information, Proceedings of the 26th International Conference on Very Large Data Bases, p.53-64, September 10-14, 2000
• 2: M. Benedikt and A. Jeffrey. Efficient and expressive tree filters. In Proc. FSTTCS, 2007.
• 3: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 4: Alexis Campailla , Sagar Chaki , Edmund Clarke , Somesh Jha , Helmut Veith, Efficient filtering in publish-subscribe systems using binary decision diagrams, Proceedings of the 23rd International Conference on Software Engineering, p.443-452, May 12-19, 2001, Toronto, Ontario, Canada
• 5: Chee-Yong Chan , Wenfei Fan , Pascal Felber , Minos Garofalakis , Rajeev Rastogi, Tree pattern aggregation for scalable XML data dissemination, Proceedings of the 28th international conference on Very Large Data Bases, p.826-837, August 20-23, 2002, Hong Kong, China
• 6: C.-Y. Chan, P. Felber, M. Garofalakis, and R. Rastogi. Efficient Filtering of XML Documents with XPath Expressions. In Proc. ICDE, 2000.
• 7: J. Clark. Expat ? The XML Parser Toolkit. http://www.jclark.com/xml/expat.html.
• 8: E. M. Clarke, O. Grumberg, and D. Peled. Model Checking. MIT Press, 2000.
• 9: Yanlei Diao , Shariq Rizvi , Michael J. Franklin, Towards an internet-scale XML dissemination service, Proceedings of the Thirtieth international conference on Very large data bases, p.612-623, August 31-September 03, 2004, Toronto, Canada
• 10: M. Franceschet. XPathMark: an XPath benchmark for XMark generated data. In Proc. XSYM, 2005.
• 11: Todd J. Green , Gerome Miklau , Makoto Onizuka , Dan Suciu, Processing XML Streams with Deterministic Automata, Proceedings of the 9th International Conference on Database Theory, p.173-189, January 08-10, 2003
• 12: Ashish Kumar Gupta , Dan Suciu, Stream processing of XPath queries with predicates, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872809]
• 13: The iProClass database. http://pir.georgetown.edu.
• 14: Maarten Marx , Maarten de Rijke, Semantic characterizations of navigational XPath, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083792]
• 15: M.Francechet. XPathMark: an XPath benchmark for XMark generated data. In Proc. XSYM, 2005.
• 16: Dan Olteanu, SPEX: Streamed and Progressive Evaluation of XPath, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.934-949, July 2007 [doi>10.1109/TKDE.2007.1063]
• 17: Feng Peng , Sudarshan S. Chawathe, XPath queries on streaming data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872810]
• 18: Albrecht Schmidt , Florian Waas , Martin Kersten , Michael J. Carey , Ioana Manolescu , Ralph Busse, XMark: a benchmark for XML data management, Proceedings of the 28th international conference on Very Large Data Bases, p.974-985, August 20-23, 2002, Hong Kong, China
• 19: Christoph Koch , Stefanie Scherzinger , Michael Schmidt, The GCX system: dynamic buffer minimization in streaming XQuery evaluation, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 20: Standard ML. http://www.standardml.org.
• 21: D. Veillard. The XML C Parser and Toolkit of Gnome: XSLT, 2003. http://xmlsoft.org/XSLT.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Languages, Security

Keywords:
query processing, streams, xml, xpath