Method and appliance for XML policy matching

• US 7,668,802 B2
• Filed: 07/30/2007
• Issued: 02/23/2010
• Est. Priority Date: 07/30/2007
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Boone, Paul, Bou-Diab, Bashar Said
• Primary Examiner(s): Lewis, Cheryl
• Application Number:
  US11/878,981
• Publication Number:
  US 20090037379A1
• Time in Patent Office: 939 Days
• Field of Search: 707 2- 5, 707/100, 707/101, 707103 R-103 Z, 715/200, 715/234
• US Class Current: 707/708
• CPC Class Codes: G06F 16/8365 Query optimisation
• CPC Class Codes: G06F 16/8373 Query execution

Abstract

An XML matching engine and method are provided, where policy rules expressed using XPath/XQuery policies are matched to streaming XML documents. Two distinct data structures are used: a combined modified DFA data structure for storing simple XPath queries (no wildcards or descendents) and a modified AFilter structure for storing complex queries (with wildcards or/and descendents). As the matching engine receives XML tags from XML parser, matching is performed in both structures in parallel.

Claims

1. A method of enforcing application-layer policies to application layer formatted documents, each policy defining a rule and an action, comprising:

distinctly storing simple policies and complex policies applicable to the application layer formatted documents in a simple policies data structure, wherein said simple policies data structure stores XPath queries that do not use wildcard “

*” and

descendent “

//”

expressions, and, respectively, a complex policies data structure, wherein said complex policies data structure stores XPath queries that use wildcard “

*” and

descendent “

//”

expressions;

parsing a document received as streaming application layer data in a hierarchical structure, for enabling evaluation of an object in the document, wherein the document is an Extensible Markup Language (XML) document and the object is a result of evaluation of an XPath expression;

simultaneously querying the simple and complex policies data structures to identify all policies corresponding to the object;

discontinuing the query for the object in the simple and complex policies data structures once all of the simple and complex policies that match the object are identified; and

executing the actions defined by the simple and complex policies corresponding to the object.

2. The method of claim 1, wherein the simple data structure is filtered by a Deterministic Finite Automaton (DFA) structure.

3. The method of claim 1, wherein querying the simple data structure is performed using a Deterministic Finite Automaton (DFA) structure, where two or more XPath queries that have a common prefix are merged.

4. The method of claim 1, wherein the complex policies data structure is filtered by a compressed Deterministic Finite Automaton (DFA) structure for representing the query, and a stack structure for representing currently active tags of the XML document, the stack structure being used for traversing the DFA structure on receipt of a tag in the document that matches a final location step of the query.

5. The method of claim 4, wherein the stack structure uses a single stack for all tags received from the document and a second stack for the wildcard “

*”

.

6. The method of claim 1, wherein the simple policies data structure is a simple policies database.

7. The method of claim 1, wherein the complex policies data structure is a complex policies database.

8. The method of claim 1, wherein the simultaneously querying involves use of an XQuery language in a query module.

9. The method of claim 1, wherein the simultaneously querying terminates once a policy matching the XML document is found in either the simple policies data structure or the complex policies data structure.

10. The method of claim 1, wherein prefixes of overlapping queries are only stored once in the simple policies data structure.

11. A system for enforcing application-layer policies to documents, each policy defining a rule and an action, comprising:

a XML parser for parsing a XML document received as streaming XML data in a hierarchical structure to enable evaluation of an object in the XML document;

a simple policies data structure for storing XPath queries that do not use wildcard “

*” and

descendent “

//”

expressions;

a complex policies data structure for storing XPath queries that use wildcard “

*” and

descendent “

//”

expressions;

means for simultaneously querying the simple and complex policies data structures to identify all policies corresponding to the object; and

means for executing the actions defined by the policies corresponding to the object identified in the data structures.

12. The system of claim 11, wherein the simple policies data structure is filtered by a Deterministic Finite Automaton (DFA) structure.

13. The system of claim 11, wherein querying the simple policies data structure is performed using a Deterministic Finite Automaton (DFA) structure, where two or more XPath queries that have a common prefix are merged.

14. The system of claim 11, wherein the complex policies data structure is filtered by a compressed Deterministic Finite Automaton (DFA) structure for representing the query, and a stack structure for representing currently active tags of the XML document, the stack structure being used for traversing the DFA structure on receipt of a tag in the document that matches a final location step of the query.

15. The system of claim 14, wherein the stack structure uses a single stack for all tags received from the document and a second stack for the wildcard “

*”

.

16. The system of claim 11, wherein the simple policies data structure is a simple policies database.

17. The system of claim 11, wherein the complex policies data structure is a complex policies database.

18. The system of claim 11, wherein the simultaneously querying involves use of an XQuery language in a query module.

19. The system of claim 11, wherein the simultaneously querying terminates once a policy matching the XML document is found in either the simple policies data structure or the complex policies data structure.

20. The system of claim 11, wherein prefixes of overlapping queries are only stored once in the simple policies data structure.