Query-Based Database Policy Assurance Using Semantic Web Technologies

José Hiram Soltren. Advisor: Lalana Kagal
24 August 2009

Decentralized Information Group
MIT Computer Science and Artificial Intelligence Laboratory


Our goal is to leverage existing Semantic Web technologies to provide policy assurance.

SPARQL Queries

PREFIX ex: <http://example.com/#>
SELECT ?s ?id ?n WHERE {
  ?s ex:ssn ?n.
  ?s ex:age ?a.
  ?s ex:key ?id.
  FILTER (?a > 18)

What does this do?

SPARQL Queries

The AIR reasoner cannot understand SPARQL, but it can understand N3, a human readable representation of RDF. We provide an automated tool to convert from SPARQL to N3.
@prefix s: <http://dig.csail.mit.edu/2009/IARPA-PIR/sparql#> .

:Query21117760711251124485 a s:SPARQLQuery;

s:clause [
  s:triplePattern  { :s <http://example.com/#ssn> :n };
  s:triplePattern  { :s <http://example.com/#age> :a };
  s:triplePattern  { :s <http://example.com/#key> :id };
  s:triplePattern  { :a s:booleanGT "18 "};

   s:retrieve [
      s:var :id;
      s:var :n;
      s:var :s;

Policies in AIR

Now that we have converted a query into something that our reasoner can investigate, we need to consider the policies themselves.

What form will our policies take? What kinds of policies can we create?

Example: SSN Restriction Policy

An example of a simple policy: "if SSN number is referred to in the query either as the requested value (RETRIEVE) or just to filter the data (USE), the query is incompliant."

Creating the SSN policy: First Approach

Rules and Policies in AIR

In summary, The SSN policy would show how all of these interact.

Passing or failing various tests gives us information about the query, leading up to a decision regarding the compliance of the query.

First Approach: Check Query Semantics

First, a sanity check to see that this is a SPARQL query.
:SSN_RULE1 a air:BeliefRule;
    air:label "SSN policy rule 1";
    air:description (:Q " is a SPARQL query with a WHERE clause.");
    air:pattern {
       :Q a s:Select;
       s:POSList :P;
       s:WhereClause :W.
Now, let's check to see if SSN is mentioned directly in the WHERE clause.
:SSN_RULE4 a air:BeliefRule;
    air:label "SSN policy rule 4";
	air:description ("The query, " :Q ", includes reference to
	                 SSN number in the where clause"); 
    air:pattern {
        :P s:variable :V.
        :W s:TriplePattern :T.
        :T log:includes { :X <http://xmlns.com/foaf/0.1/ssn> :Y }
    air:assert { :Q air:non-compliant-with :SSNPolicy };

First Approach: Check Query Semantics

We can continue to find mentions of SSN in the OPTIONAL part of a WHERE clause...
:SSN_OP02 a air:BeliefRule;
    air:label "SSN optional clause rule 02";
    air:pattern {
        :W s:OptionalGraphPattern :O.
        :O s:TriplePattern :T.
        :T log:includes { []  [] }
    air:description ("The query, " :Q  ", includes reference to
	             SSN number in the OPTIONAL part of the WHERE clause"); 
    air:assert { :Q air:non-compliant-with :SSNPolicy_OptionalClause }.
...or as a FILTER.
:SSN_FR02 a air:BeliefRule;
    air:label "SSN filter rule 02";
    air:pattern {
        :P s:variable :V.
        :W s:TriplePattern :T.
        :T log:includes { :X <http://xmlns.com/foaf/0.1/ssn> :V }.
        :W s:Filter :F. 
        :F s:TriplePattern :S.
        :S log:includes { :V [] [] }.
    air:description ("The query, " :Q  ", filters on SSN variables"); 
    air:assert { :Q air:non-compliant-with :SSNPolicy_FilterRule }.

Justification UI Screenshot

Finding Structure: Logical Constructs

Many policies build upon basic constructs. We can generalize to create policy "templates".

Finding Structure: Lingustic Constructs

Orthogonally, many policies check the same parts of SPARQL queries. There are a finite number of places to check. We saw these earlier. These are structured by the language, and would change if we used a different query language.

New Approach: Remove Query Semantics

Since there are so many places to look, why not create an abstraction? The new approach brought a new translator and new policies.

Sample: Exclusion Policy

We can construct a sample exclusion policy in AIR.
:exclusion-policy-noncompliance-rule a air:BeliefRule;
    air:label "exclusion-policy, a default deny policy.";
    air:pattern {
        # Catch RETRIEVE
        :P s:var :V0.
        :W s:triplePattern :T0.
        :T0 log:includes { [] ex:a :V0 } .
        # Catch RETRIEVE
        :P s:var :V1.
        :W s:triplePattern :T1.
        :T1 log:includes { [] ex:b :V1 } .
    air:description ("You may see up to 1 of 2 of these attributes: ex:a ex:b .
	                  This query is incompliant: " :Q ) ;
    air:assert{ :Q air:non-compliant-with :exclusion-policy } ;
    # No more policies, go to the base case.
    air:alt [ air:rule :exclusion-policy-default ] .

:exclusion-policy-default a air:BeliefRule;
    air:label "exclusion-policy default rule";
    air:pattern { # Empty search.
    air:description ("No regulated attributes found. Asserting compliance.");
    air:assert{ :Q air:compliant-with :exclusion-policy } .

Other policies follow a similar structure.

Policy Generation

We can find patterns in the logical aspect of policies. We know the limitations of our query language. We also know something about ourselves... Can we automate this process? Yes we can.

Automatic Query Translation

We present a Web interface for automatically translating queries. Each translation has a unique URI.

Automatic Policy Generation

We present a Web interface for automatically composing policies.

Semi-Automatic Policy Execution

We present a Web interface for checking queries. The current implementation requires a manual copy-paste, thus it is only semi automatic. :-)

Live Demo

Looking at a sample policy: "if you RETRIEVE ex:a, you must also USE ex:b and specify the filter ex:b > 18."

Live Demo Output

This query should be compliant. (Click for full size view.)

Reasoning over Query History

Future Work

Query-Based Database Policy Assurance: Summary

Creative Commons License