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

Overview

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

Express SPARQL queries in RDF (Resource Description Framework), so that we can use our tools to perform reasoning.
Encode policies in the AIR (Accountability in RDF) language.
Provide an interface for checking queries and creating policies.

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?

This is a SPARQL query. The syntax looks like SQL - by design.
We return a table of the SSN, and key for all entities over age 18.

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?

We can test for particular kinds of variables in parts of clauses.
We can make compliance decisions based on logical constructs.
We can reason over a user's query history.
There is enough expressivity to encode interesting policies.

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

Define SSN as a URI: <http://example.com/ssn>.
Check different parts of a query for SSN.
Return as much compliance information as possible.

Creating the SSN policy: First Approach

What parts of a query can contain references to the SSN?
- WHERE clause in SELECT
- OPTIONAL part of a WHERE clause
- FILTER clause
- A variable that is bound to SSN elsewhere.
- ...the list continues. These are properties of SPARQL structure.
How do we create policies that catch these references?
- AIR rules implement pattern matching
- Rules can be chained to form policies
- Independent policies return information

Rules and Policies in AIR

In summary,

A rule (previous slides) performs a check and returns true or false.
Rules can make assertions and call other rules.
A policy may contain multiple rules, but only makes one assertion.
A policy file can contain multiple policies, and make up to one assertion per policy.
We check queries (or "log files" in AIR lingo) against policies (or "rules files").

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.

~A: Restriction (not). May not view something of type:A, at all.
- i.e. the running example, cannot query a user's SSN
A (+) B: Exclusion (xor). May view type:A or type:B, but never both.
- i.e. "cannot query a user's bank account number and SSN."
A <-> B: Inclusion (and). May only view type:A if type:B is also present.
- i.e. can only get the photo of users over 18
A -> ~B: Chaining (ordered xor). Viewing type:A prevents viewing type:B.
- i.e. "cannot query for driver's license number after having queried SSN."
Exclusion and generalizes to max(M,N).
- max(M,N) defined as "may view up to M fields of N for M ≤ N."
- easy to understand, difficult to program directly
- i.e. "may know up to 3 of: last name, DOB, SSN, driver's license number, bank account number."
- max(N-1,N) is easy. General max(M,N) is hard and currently unsupported..

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.

WHERE clause in SELECT. Reveals data.
WHERE clause in CONSTRUCT. Reveals data in a different format.
WHERE clause in DESCRIBE. Reveals metadata.
OPTIONAL part of any WHERE clause. Reveals data if it is available.
FILTER. Indicates potential misuse of a field.
ORDER BY. Similar to FILTER.
ASK. Reveals information, enough queries can return interesting results.
- Example: 746,347,500 queries would exhaust the SSN space per my calculations.
FROM clause. Allows user to specify a table directly, potential security hole.
Variable bindings.
UNION. This chains queries together.

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?

We only need to look for certain triple patterns to assert compliance.
Policies which closely follow SPARQL semantics are difficult to construct, brittle, and do not give any additional functionality.
Simpler policies that do not depend on SPARQL semantics lend themselves to automation and porting to additional languages.

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.

A few logical constructs allow us to create interesting policies.
We can chain rules, and many are repetitive.

We know the limitations of our query language.

There are only so many patterns we can check.
Almost all of our policies involve checking the same list of patterns.

We also know something about ourselves...

We're lazy! Writing policies is time consuming.

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

Create the policy.

Create a sample (good) query.

# Sample SPARQL query using example namespace.
PREFIX ex: 
SELECT ?s ?a WHERE {
     ?s ex:a ?a.
     ?s ex:b ?b.
     FILTER (?b > 18) }

Check for compliance.(Ignore the display error for now.)

Live Demo Output

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

Reasoning over Query History

Perhaps the most imporatant application is reasoning over a history of queries.
- We extend policy assurance from single queries to a history of queries.
- State must be maintained outside of AIR as the reasoner cannot store state.
Approach: let the reasoner deal with histories. Use a wrapper script.
- Pass multiple queries to the reasoner.
- Preserves order, but may require annotation.
This works with automatically generated policies, but only from the command line at the moment. More details are available in the DIG repository.

Future Work

SPARQL Endpoint Integration
SQL Support
Support for more SPARQL language features
Browser-based processing
Policy generation from natural language
Semantic Policies (Yotam's project)
Database description ontology and auto-population in UI

Query-Based Database Policy Assurance: Summary

We have demonstrated a system capable of making relatively simple policy checks against SPARQL queries.
We believe this system offers enough robustness to encode more substantial policies.
We have found enough structure in our policies to create an interface to ease policy generation.

Thank you!
Questions?

Query-Based Database Policy Assurance Using Semantic Web Technologies

Overview

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

SPARQL Queries

Policies in AIR

Example: SSN Restriction Policy

Creating the SSN policy: First Approach

Rules and Policies in AIR

First Approach: Check Query Semantics

First Approach: Check Query Semantics

Justification UI Screenshot

Finding Structure: Logical Constructs

Finding Structure: Lingustic Constructs

New Approach: Remove Query Semantics

Sample: Exclusion Policy

Policy Generation

Automatic Query Translation

Automatic Policy Generation

Semi-Automatic Policy Execution

Live Demo

Live Demo Output

Reasoning over Query History

Future Work

Query-Based Database Policy Assurance: Summary