Method and appliance for XML policy matching
View Patent ↗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.
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.