\documentclass[letterpaper]{article}
\usepackage{cite}
\usepackage{graphics}
\usepackage{url}
\usepackage[pdfauthor={Jose Hiram Soltren},%
            pdftitle={Policy Assurance in Database Systems},%
            pdftex]{hyperref}

\author{Jos\'e Hiram Soltren
        $<$\href{mailto:jsoltren@mit.edu}{jsoltren@mit.edu}$>$}
\title{Policy Assurance in Database Systems}
\date{\today}

\begin{document}
\maketitle

\section{Introduction}

The widespread use of automated systems to collect, store, and retrieve data in the public, private, and academic sectors has given rise to a large number of databases. Many of these databases contain private, personally identifiable, or sensitive information. In the financial sector, databases store information about bank accounts, trades and company activity that is not suitable for a large audience. In the health services industry, hospitals and insurance companies maintain databases containing confidential patient health data. In the military, databases contain classified and secret data that must remain hidden for reasons of national security. All of these systems share a common need of regulated access to data.

% Talk about traditional methods of access control here.

Database systems traditionally use some form of access control to enforce policies regarding the data they contain. These policies, a form of rule-based access control, create a control structure that mimics the structure of the database itself. We can restrict access to tables, enable certain views of data, or prohibit access selectively. These systems have two major points of failure. The first is that they require system designers to think about data and security simultaneously. The second is that they often fall short, creating a substantial ``gray area'' between unlimited access and highly restricted access.

Policy assurance is the use of a system of rules and reasoners to show that access to or utilization of a shared resource is within the confines of a pre-established set of rules. In this project, we will apply Semantic Web technologies to policy assurance in database systems. We argue that the logical reasoners of the Semantic Web world are well suited for a more abstract form of rule-based access control. We will define a language
that allows us to describe database queries, and their semantics, to both
human and automated agents. We will construct a policy framework that
enables us to create policies from abstract concepts, and use existing
logical reasoners to determine whether or not we are in compliance of these
technologies. Finally, we will integrate our system into an existing
relational database implementation.

Our approach is novel in using Semantic Web technologies for this type
of policy checking. The use of access controls in database systems is not
new, nor is the use of reasoning systems and forward chaining to make
logical deductions. We feel that Semantic Web technologies are well suited
to the database access control problem, as they provide a robust, dynamic,
and traceable way of implementing access control at a very fine granularity.

The rest of this proposal is structured as follows. First, we describe the problem of policy assurance in databases in more detail, offering sample scenarios. We then discuss the current state-of-the-art, including a discussion of existing Semantic Web technologies, and best practices in database administration using traditional models of access control. We then discuss a sample implementation, and demonstrate
how the use of Semantic Web technologies is fundamentally different from prior approaches. We set a framework for future work and discuss challenges before concluding.


\section{Problem Description}

Our goal is to create a policy assurance system for a database containing sensitive data. Specifically, we wish to encode abstract policies in a reasoning language, and determine if access to our database is in adherence to these policies. Re-using as much of our existing framework as possible, we can inform users of how we derive at the conclusion of whether or not they are acting within the policies we established. Our policy assurance system will function as an external component to an existing database management system, providing external feedback to the system.

\begin{figure}[htb!]
\centering
\includegraphics{system-drawing-1}
\caption{High level architecture of our proposed policy assurance reasoner, demonstrating its separation from the existing database management system.}
\end{figure}

We would like for our system to work in databases with policies that restrict what the database administrator can do. The database administrator may be in charge of a database containing secured, limited-access, or confidential data. The administrator must be assured that users of the system are in compliance of the policies in place, even though the administrator may not have permission to see the queries, or the results of the queries, that the users make. Our system aims to provide a database administrator with a tool that tells them if users are playing fair, or breaking the rules.

\section{Previous Work}

\subsection{Policy Awareness}

Within the realm of the Semantic Web, there is prior work relating to policy awareness. This is the application of reasoner technologies to rule-based systems, where the rules represent laws, licenses, or policies that relate to the system.

The Information Accountability paper describes the arenas in which policy-aware systems are if interest. \cite{info-account} Among these are privacy, copyright, surveillance, and data mining. The paper argues that if we can trace who uses data and how they use it, if we have a way of finding accountability, we can begin to move toward policies that are between full disclosure and full control. The paper offers scenarios of how information aware systems would be useful in everyday life.

REIN (Rei and N3, named after the Rei policy specification language and the Notation 3 language) describes a system offering ``policy management''. \cite{rein} The system is policy-language agnostic, and operates in an independent environment, offering a yes/no opinion of policy compliance to an existing system. The REIN paper defines three possible operating modes. In the server-side rules operating mode, the analogy of choice is an application for a library card. The user does not know the rules, but supplies the information requested on the form to the library for processing. In the client-side rules mode, the onus of rule checking is on the user. The hybrid mode offers a way of sharing this responsibility. At present, REIN is implemented in Python, using the N3 policy language and the CWM reasoner.

There is prior work demonstrating the use of a policy-aware system for checking license information. \cite{creative-commons} In this case, the system uses Creative Commons license policies to check for compliance with the content creator's sharing preferences. The author describes this system as a way of ``keeping honest people honest.'' The system, as implemented, converts meta data on an image file to an AIR policy, and checks usage patterns against a set of rules that parallel the Creative Commons license policies. If, for example, an image from the Flickr Web site is used on someones personal page, in violation of the content creator's wishes as expressed in their choice of Creative Commons licensing, this tool will detect a conflict.

Our logical approach is to use the Accuontability in RDF (AIR, where RDF stands for ``resource description framework'') reasoning language to implement policies. We have yet to specify how we will encode policies, or queries.

\subsection{Methodologies of Access Control}
% talk about DAC/MAC/RBAC here

We are implementing a form of access control in this project. We thought it would be instructive to look at the existing literature, and the approaches systems designers take in designing traditional access control systems. Systems designers tend to have a different mind set when approaching security problems than Web designers: systems designers tend to favor closed systems, whereas Web designers tend to favor open systems. Existing relational database systems extend on these technologies in their implementation of access control.

\subsubsection{Yesterday: Mandatory and Discretionary Access Control}

The traditional models of access control, circa the mid 1980s, consist of mandatory access control, or MAC, and discretionary access control, or DAC. The origins of MAC lie in secure military systems, as a way to enforce permissions on proprietary, secured, confidential data. \cite{Qiu85trustedcomputer} In an MAC system, the only way to gain access to data is to expressly have an outside authority grant access. There is absolutely no provision for an end user to alter permissions on data. The primitives for enforcing access control extend deep into the design of the operating system. MAC systems explicitly define rings of access. Some secure Unix operating systems, including SELinux, utilize MAC design principles.

%MAC systems lend themselves to formal verification techniques. - verify this

Discretionary access control is a design principle that allows a user to show that they have the credentials to access data. \cite{Qiu85trustedcomputer}Users have the capability of modifying their own permissions, or the permissions of others. A widespread example of a DAC system is that of Unix style permissions. On Unix systems, everything, from devices to network sockets to data on a disk, is represented as a file. Every file has three sets of permissions: those for the owning user, for the owning group, and for everyone else. Each of these sets may be granted (or denied) permissions to read, write, and/or execute a file. The operating system checks the user's credentials and the file's permissions before enabling an operation. Access Control Lists (ACLs) are another example of a DAC system. There is prior work investigating the use of DAC in object-oriented databases. \cite{dac-db} Such a security model works well for general purpose computing, but not in all scenarios.

The excessive rigors in the implementation of a MAC system, and the inadequacy of a DAC system, have led systems researchers to newer design philosophies that allow finer granularity in security settings.

\subsubsection{Role Based Access Control}

In the early 1990s, systems researchers began to find practical limitations in the expressive power of the discretionary access control model. Researchers presented role based access control as a more secure, easy to implement alternative to discretionary access control. \cite{rbac} Role based access control is a form of mandatory access control, in that users obtain their permissions from an outside authority. The primary difference is in the structure of permissions. In role based access control, a user can be assigned to one (or more, in some implementations) ``roles''. As an example, a user in a large company might wear several hats throughout their time in the company, from ``human resources associate'' to ``financial associate'' to ``systems analyst''. Each of these roles requires a different set of permissions. The formal description of role based access control, demonstrated in the paper, shows the power and flexibility of assigning roles rather than individual permissions. It is particularly well suited to assigning permissions where a high user turnover rate is present.

\subsubsection{Rule- and Policy-Based Access Control}
% Talk about REIN here. Talk about SWRL, too.

Rule based access control is an extension and a generalization of role based access control. Instead of simple roles, we can use rules and logic to derive whether or not a particular agent should have access to a particular resource. As an example, consider a student trying to access a secured Web page. The student may have credentials saying, ``I am a graduate student'', ``my adviser is Professor Smith'', and ``I am a member of Research Group X''. The page may have a set of rules defining access: it may be restricted to individuals who are members of certain research groups, and also graduate students. Different versions of the page may exist based on the credentials used. REIN \cite{rein} and SWRL \cite{rulebased} provide sample implementations of policy based access control.

Our system will likely mimic one of these closely. We will draw from their examples in the way that they define and process rules.

\subsection{Prior Work in Relational Databases}

Our project seeks to address a particular shortcoming in database systems at present. In order to enforce access control policies, the database must be able to see the queries that a user is making against the database. This poses a problem when the queries themselves may reveal sensitive data. Access control lists are insufficient in this regard, whereas misuse and intrusion detection efforts are more closely related with our work.

\subsubsection{Access Control Lists}

Modern relational database management systems utilize some form of discretionary or role-based access control to regulate access to tables, using some form of access control list. The database administrator may restrict database access to particular rows or columns in particular tables, may grant or deny read and write permissions, and may limit the user to executing particular queries. \cite{mysql} In effect, all of these systems limit the user to seeing a particular subset of the data in the database.

It follows that the structure of the access control policy must closely follow the structure of the data itself. The structure of the security policy may divulge secure information, and may not be tolerant of changes to the underlying structure of the database.

\subsubsection{Access Control Features In A Modern RDBMS}

Modern RDBMS packages, such as Oracle, offer a wide variety of access control features. We can roughly group them into five categories. \cite{acl-oracle} \cite{oracle} \cite{rbac-commercial}

\begin{itemize}
	\item{Privileges}
	\item{Views}
	\item{Stored Procedures}
	\item{Roles}
	\item{Virtual Private Databases}
\end{itemize}

Privileges explicitly grant access to perform an action on a particular database object. A database administrator, or a user with appropriate privileges, can grant or revoke privileges. A view is a dynamic table, the output of a particular query against the database. A stored procedure is a particular command, like a user defined function, provided for database access. A role, as described in the preceeding section on role-based access control, is a type of meta-user that helps congregate database permissions. A virtual private database is a form of information hiding, partitioning the database such that a user only sees certain data.

These systems are able to specify access rights for users and groups on databases, and work well enough in the majority of usage cases. However, this design is not without its limitations. The access policies must closely follow the structure of the data, in many cases involving the database administrator to know a great deal about the structure of the tables. Changes to the layout of data will break previously defined policies. Privileges can be granted or revoked in a conflicting fashion, often making it difficult to determine correct access. Views and virtual private databases may be overly restricting, preventing honest individuals from carrying out their responsibilities. Our work seeks to address the numerous limitations with systems of this design by introducing a more flexible, more abstract means for defining permissions.

\subsubsection{Misuse and Intrusion Detection}

There is a decent amount of prior work in the field of intrusion detection systems in databases. The authors of intrusion detection papers argue that, though an outsider threat is very real, current databases do little to guard against violations of policy conducted by a trusted insider with database access. Detection of Misuse in Database Systems (DEMIDS) \cite{demids} was one of the first systems to detect potential misuse in a database system. By monitoring queries, using audit logs, and determining a frequent item set, the DEMIDS system is able to guess whether or not a particular access by a particular user is likely to be permitted. This approach suffers from a granularity issue: with too high or too low granularity, it is likely that the system will see a high number of false positive policy violations, or respectively, a high number of false negatives.

Later systems expand on some of the DEMIDS ideas, adding better learning or classification techniques. Cathey et. al. \cite{Cathey03misusedetection} developed a system that uses a combination of user query profile learning, abnormal query behavior detection, clustering documents, clustering query results, and relevance feedback to better understand how particular users and groups access a database. Over time, Cathey's system will ``learn'' common access patterns. Kamra et. al. \cite{Kamra} extend this theme further, requiring the use of role-based access control, and using a naive Bayes classifier to learn standard access patterns. Their approach argues that, by only considering roles instead of individual users or tables, the granularity is correct. Kamra's paper also argues against a formal definition of intrusion detection, saying that the intrusion detection application is much more purpose-built, and therefore less suited to a formal approach.

Our work will extend this research by using a system of rules to implement intrusion detection. Certainly, the aforementioned techniques would be helpful in the initial instrumentation of rule sets, by finding common ways that users access data.

\subsection{Alteration of Data}
% discuss things like k-anonymity and de-identification here

An orthogonal approach to security of certain kinds of sensitive data is the alteration of the data itself. If we restrict the utility of the data through alteration, we can, in theory, limit the usefulness of the data, its sensitivity, and its potential for damage. The classic example of this approach is the use of a heavy black marker to manually censor sensitive government documents prior to public release. There has been some research into formalizing and automating this process.

% TODO: Talk more about Latanya Sweeney's work.

Sweeney has published a great deal of research on this particular topic. k-anonymity \cite{kanon} \cite{kanon2} offers a formal approach to the de-identification process. A data set that offers k-anonymity for some k is constructed such that, for every attribute (column), there are at least k occurrences of that attribute (rows). Phrased differently, a data set of census data  would be anonymous for $k=2$ if there were at least two occurrences of each name, address, age, and so on. By setting a value of k, dependent on the application, we can guarantee difficulty in re-creating and de-identifying the data set. Datafly \cite{datafly} is a system that can de-identify data automatically, removing singletons, changing social security numbers (SSNs) and dates of birth, changing ZIP codes, and the like.

% TODO: Talk about the MIMIC II database, and the challenges they face, based on the conversation with Mauricio.

De-identification and privacy problems are nothing new to the biomedical informatics world. Access to, and use of, medical data faces heavy regulation, most prominently from the Health Insurance Portability and Accountability Act (HIPAA) of 1996. The Multi-parameter Intelligent Monitoring for Intensive Care database, or MIMIC II (\url{http://mimic.mit.edu/}) is a database, provided by an MIT research group, for research purposes. The MIMIC group has published many papers discussing and evaluating different de-identification algorithms.

With access to the database, our system could potentially anonymize data using any of a number of well known techniques. This would allow us to keep original data, and only serve data that is as specific as it needs to be for a particular application.

\section{Design Proposal}

\subsection{Semantic Web}

\begin{quote}
``The Semantic Web is not a separate Web but an extension of the current one, in which information is given well-defined meaning, better enabling computers and people to work in cooperation.''

- Tim Berners-Lee, James Hendler, and Ora Lassila
\end{quote}

The Semantic Web is an ongoing endeavor to make information accessible to
both human agents, and automated systems. It is an extension of the World Wide Web, a collection of design principles that seek to foster information
sharing in new ways through the use of new systems.

At present, Semantic Web technologies specify specific ways of encapsulating information so that it is human and machine readable. The primary method is Resource Description Framework (RDF), an Extensible Markup Language (XML) specification that binds objects to properties. The Notation 3 (N3) language is a form of ``syntactic sugar'' for RDF. Accountability in RDF, or AIR, offers a language for expressing policies in RDF languages. \cite{air}

Applications such as the Tabulator browser addition render RDF information in an easily human readable form. The real power in Semantic Web technologies is the way that they easily lend themselves to rule-based systems and reasoners. One existing system, N3Logic, uses the N3 language to perform reasoning. \cite{n3logic} AIR also provided an infrastructure for logical reasoning.

\subsection{SPARQL Query Language and SPASQL}

Our work will likely incorporate the SPARQL language. A relatively recent development named with a recursive acronym, the ``SPARQL Protocol and RDF Query Language'' \cite{sparql} provides a way of encapsulating a database query, such as a Structured Query Language (SQL) query, in an RDF language. Its expressive power is perhaps best demonstrated by an example. Suppose that we have the following data, expressed as a set of RDF triples.

\begin{verbatim}
@prefix foaf:  <http://xmlns.com/foaf/0.1/> .

_:a  foaf:name   "Johnny Lee Outlaw" .
_:a  foaf:mbox   <mailto:jlow@example.com> .
_:b  foaf:name   "Peter Goodguy" .
_:b  foaf:mbox   <mailto:peter@example.org> .
_:c  foaf:mbox   <mailto:carol@example.org> .
\end{verbatim}

With the aforementioned data set, we could create a query that would pull pairs of names and e-mail addresses from the data set. In SPARQL, this query would have the following syntax.

\begin{verbatim}
PREFIX foaf:   <http://xmlns.com/foaf/0.1/>
SELECT ?name ?mbox
WHERE
  { ?x foaf:name ?name .
    ?x foaf:mbox ?mbox }
\end{verbatim}

The real power of SPARQL is the fact that it is already conveniently encoded in an RDF language. This fact makes it easy to use SPARQL queries as the input to a reasoner. We will consider ways of incorporating this query language into our reasoner.

SPASQL is an extension of the SQL language, which allows an RDBMS to process SPARQL queries. An implementation of SPASQL may be contained within the RDBMS, or as an extension or module.\cite{spasql}

\subsection{Project Contributions}

We propose to create a system that implements policy assurance using existing Semantic Web technologies. We will re-use as much existing technology as is feasible in the process. We will express policies in an RDF language, likely AIR, and use an existing reasoner to deduce whether or not an access pattern is in accordance with access policies. When deducing whether or not a query is valid, we will consider the user's entire query history. We will use the SPARQL language to represent queries, and will need to implement a way of converting standard SQL queries to the SPARQL format.

We will only provide the infrastructure for creating policies, and demonstrate the feasibility of the system using a small test case. It will be the responsibility of the database administrator, perhaps in tandem with the policy assurance implementers, to populate the space of access policies.

We will design our reasoner as an add-on to existing relational database management systems (RDBMS). The database will hand off certain data to our system, likely a SQL query or some modified version thereof. Our system will deduce whether or not the query is compliant with an access policy, and provide a ``yes/no'' recommendation to the RDBMS back end. The RDBMS can choose to accept or ignore our challenge.

In the short term, we aim to have an accuracy of 0.80. We define accuracy according to the following weighted equation,

\begin{equation}
accuracy=\frac{N}{N_{correct}+1.5 \cdot N_{fp}+2 \cdot N_{fn}}
\end{equation}

where $N_{correct}$ is the number correct, $N_{fp}$ is the number of false positives, and $N_{fn}$ is the number of false negatives. We hope to approach an accuracy of 0.98 within two years' time.

\subsection{Project Milestones and Deliverables}

We will approach this project in three phases.

\begin{itemize}
\item{\textbf{Phase I:} We will use SPASQL to convert SPARQL queries to RDF. We will write low level AIR policies to check the compliance of these SPARQL queries, and demonstrate a test case.}
\item{\textbf{Phase II:} We will create an abstraction for these SPARQL queries, and provide a meta level that removes dependence on the data structure.}
\item{\textbf{Phase III:} We will move from using SPARQL to using SQL directly, either by converting SQL directly to RDF, or to SPARQL and then RDF.} 
\end{itemize}

\section{Challenges}

Our solution does not address the issue of users who conspire together. It may be possible for two users to work as a team, obtaining independent sets of data from a protected database. The users can combine the data offline and break one of our policies.

We have yet to define a method of transforming a SQL query into an object that a reasoner can understand, and it would be impossible to do so without access to the query itself. Since we wish to implement this system as a drop-in addition to an existing system, it is particularly important to work within the existing database query infrastructure. Some languages, including SPARQL and SPASQL, may be well suited to our goals.

\section{Conclusion}

Our approach to database security differs from previous approaches in that it uses rule-based Semantic Web technologies to offer policy assurance. Our system will integrate with relational database management systems in production, offering a yes/no opinion as to whether or nor a single or series of queries is in violation of a policy. This will allow fine-grained access control to users, and policy assurance for administrators, with no divulging of information at any stage.

\bibliographystyle{acm}
\bibliography{thesis-proposal}

\end{document}
