Policy Assurance Using AIR and SPARQL

José Hiram Soltren and Lalana Kagal
15 April 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 rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
SELECT ?s ?id ?n WHERE {
  ?s foaf:ssn ?n.
  ?s foaf:age ?a.
  ?s foaf:openid ?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, sparql2n3, to convert from SPARQL to N3.
$ ./sparql2n3 query1.rq
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .
@prefix s: <http://dig.csail.mit.edu/2009/IARPA-PIR/sparql#> .
@prefix : <http://dig.csail.mit.edu/2009/IARPA-PIR/query1#> .

:Query a s:Select;
   s:cardinality :ALL;
   s:POSList [
     s:variable :s;
     s:variable :id;
     s:variable :n;
s:WhereClause :WHERE.

:WHERE a s:DefaultGraphPattern;
  s:TriplePattern  { :s <http://xmlns.com/foaf/0.1/ssn> :n };
  s:TriplePattern  { :s <http://xmlns.com/foaf/0.1/age> :a };
  s:TriplePattern  { :s <http://xmlns.com/foaf/0.1/openid> :id };
  s:Filter [ 
      a s:ComparatorExpression;
      s:TriplePattern  { :a s:BooleanGT "18 "^^xsd:integer};

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 or just to filter the data, the query is incompliant."

Creating the SSN policy in AIR

SSN policy in AIR: the WHERE clause rule

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 };


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 }.

Rules and Policies in AIR

In summary, The SSN policy file shows 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.

Justification UI Demo

Try it here

Finding Structure: Logical Constructs

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

Example: Exclusion and Blocking

We can construct a sample exclusion policy in AIR.
:EX_RULE02 a air:BeliefRule;
# Matches WHERE{?x type:B ?y . ?x type:C ?y}
    air:label "Exclusion WHERE clause rule.";
    air:pattern {
        :P s:variable :V.
        :W s:TriplePattern :T.
        :T log:includes { :X type:B :V } .
        :W s:TriplePattern :U.
        :U log:includes { :X type:C :C } .
    air:description ("long_winded_explanation" );
    air:assert { :Q air:non-compliant-with :Exclusion };
    air:alt [ air:rule :EX_RULE03 ].

:EX_RULE03 a air:BeliefRule;
    air:label "Exclusion compliance rule 1.";
    air:pattern { 
        :W s:TriplePattern :T.
        :T log:notIncludes { [] type:B [] }
     air:description ("The query, " :Q  ", includes a reference
		to something of type:C, but not of type:B.");
    air:assert { :Q air:compliant-with :Exclusion };
Other policies follow a similar structure.

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.

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?

Automatic Policy Generation

We propose a graphical interface for automatically composing queries. (This is a work in progress.)

Reasoning over Query History

Policy Assurance in SPARQL: Summary

Creative Commons License