Method and appliance for XML policy matching

• US 20090037379A1
• Filed: 07/30/2007
• Published: 02/05/2009
• Est. Priority Date: 07/30/2007
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Bou-Diab, Bashar Said, Boone, Paul
• Granted Patent: US 7,668,802 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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:

a) distinctly storing simple policies and complex policies applicable to the application layer formatted documents in a simple policies data structure and respectively a complex policies data structure;

b) parsing a document received as streaming application layer data in a hierarchical structure, for enabling evaluation of an object in the document;

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

d) discontinue the query for that object in the simple and complex policies data structures once all simple and complex policies that match the object are identified; and

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

2. A method as claimed in claim 1, wherein the document is an XML document and the object is the result of evaluation of an XPath expression.

3. A method as claimed in claim 2, wherein said simple data structure stores XPath queries that do not use wildcard “

*” and

descendent “

//”

expressions.

4. A method as claimed in claim 3, wherein the simple data structure is a Deterministic Finite Automation (DFA) structure.

5. A method as claimed in claim 3, wherein querying the simple data structure is performed using a Deterministic Finite Automation (DFA) structure, where two or more XPath queries that have a common prefix are merged.

6. A method as claimed in claim 2, wherein said complex policies data structure stores XPath queries that use wildcard “

*” and

descendent “

//”

expressions.

7. A method as claimed in claim 6, wherein the complex policies data structure includes a compressed deterministic finite automation (DFA) structure for representing the queries, and a stack structure for representing the 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 the final location step of a query.

8. A method as claimed in claim 7, wherein the stack structure uses a single stack for all tags received from the document and a stack for the wildcard “

*”

.

9. A system for enforcing application-layer policies to XML 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.