\documentclass{llncs}
\usepackage{url,color,floatflt}
\usepackage{fancyvrb,relsize,url,graphicx,epsfig}

%\setlength{\abovecaptionskip}{0pt}
%\setlength{\belowcaptionskip}{0pt}

% to fix the line wrapping issue
\sloppy

\DefineVerbatimEnvironment%
   {VerbatimN3}%
   {Verbatim}%
   {fontsize=\scriptsize, xleftmargin=0.25in}
\DefineVerbatimEnvironment%
   {VerbatimScript}%
   {Verbatim}%
   {fontsize=\scriptsize}

% comment out a section
\long\def\comment#1{\relax}

% qname
\newcommand{\qname}[1]{\texttt{#1}}

% something to do with air
\newcommand{\air}[1]{\textbf{\textit{#1}}}

% something to do with rdf/n3
\newcommand{\rdf}[1]{{\bf #1}}

% Put remarks in the paper easily located by ``bigodot'' in margin
% Usage: \todo{twf: we need a better example here.}
\newcommand{\todo}[1]{
\mbox{}\marginpar[\hfill$\bigodot$]{$\bigodot$\hfill}
{\sc#1}}
%\newcommand{\todo}[1]{{\bf TODO:} #1}

%% ISWC 2010 Research Track
%% http://iswc2010.semanticweb.org/node/8

\begin{document}

\title{From Truth Maintenance to Trust Management on the Semantic Web
  \thanks{\small This work was supported in part by NSF Cybertrust
    award number 04281, IARPA award number FA8750-07-2-0031, and AFOSR
    award number 6921570.}}

\author{Lalana Kagal\inst{1} \and Ian Jacobi\inst{1} \and Ankesh
  Khandelwal\inst{2}}

\institute{MIT CSAIL \\
Cambridge, MA 02139 \\ 
\email{ \{lkagal, jacobi\}@csail.mit.edu}
\and
Rensselaer Polytechnic Institute \\
Troy, NY 12180\\
\email{ankesh@cs.rpi.edu}
}


\maketitle

\begin{abstract}

The Semantic Web is a decentralized forum on which anyone can publish
their structured data or extend and reuse existing data. This inherent
openness of the Web raises questions about the trustworthiness of Web
data --- which data sources to trust, what data of these sources to
trust, how to make declarations about trust, how to use these
declarations to calculate trust, etc. This paper does not propose a
new trust management model or mechanism. Instead, it shows how AIR, a
Web rule language, can be used to develop different kinds of trust
models to address trust issues of the open Web. The AIR rule language
is based on Semantic Web technologies and uses {\it truth maintenance}
to track how inferences are deduced. It has several useful features
that can be used to model trust of data sources, data, and rules as
well as inferences made by rules.  It also reasons over this
information to make further inferences.  AIR generates justifications
for all inferences made, allowing the trustworthiness of inferences to
be evaluated by consumers of this data.  In this paper, we provide an
overview of AIR and illustrate how it can be used for trust management
using an example from the financial domain.

\comment{Main contribution of this paper is illustrating how AIR can
  be used to represent and reason over trust management models for
  handling trust issues on the open Web. Not focussed on developing
  new trust management or evolution techniques such as cite trust
  papers}

\end{abstract}

\section{Introduction}
\label{sec:intro}

The Semantic Web provides technologies for rendering machine-readable data 
on the Web. These technologies include the Resource Description
Framework (RDF)~\cite{bl05n3primer}, a standard data model, RDF Schema
(RDFS)~\cite{w3c02rdfs}, a language for describing vocabularies such
as class and property hierarchies using RDF, and the Web Ontology
Language (OWL 1 \& 2)~\cite{w3c04owl,w3c09owl}, an ontology language
for expressing all kinds of domain knowledge, including complex
relationships between classes and properties. Much of this data is
generated and maintained by multiple individuals or organizations in a
decentralized manner over the Web, with incentives for reuse. This
form of data, also known as {\it Linked Data}~\cite{bizer09linked}, is
interconnected but spatially dispersed. Rules must be able to
dynamically traverse this web of data to obtain additional facts, if
required, to support conclusions. Given the openness of the Web,
however, the reliability of data depends on trustworthiness of the
source, the maintainer of the data, the last date it was updated,
etc. For example, there might be multiple Friend Of a Friend
(FOAF)\footnote{http://www.foaf-project.org/} files for Tim
Berners-Lee that describe his social profile in RDF, however, the one
that is most trusted is the one available at the W3C website. This is
due to the trustworthiness of the source, W3C. Things that are deduced
from data sources also have derived trustworthiness from those of the
sources and of any rules used in the deduction. In this work, we
consider different aspects of trust-based usage of Web data including
associating trust with rule-based deductions.

AIR ({\bf A}ccountability {\bf I}n {\bf R}DF) is a Semantic Web-based
rule language. It provides a version of production rules that can
exist on separate Web servers but can be linked together, also called
nested rules, allowing for modular development~\cite{kagal10AIR}. This
modularity and nested activation reflect how rules in laws, security
policies, business rules and work-flows are defined. AIR is
represented in N3~\cite{bl05n3primer}, a human-readable representation
of the RDF data model, and supports a rich set of functions for
selectively accessing trusted content from the Web as well as
cryptographic, string, and math operations.  Furthermore, AIR supports
contextually scoped reasoning, i.e.  rule conditions can be scoped to
be satisfied against different datasets or against deductions from
different rules and datasets. Note that these datasets and rules can
be specified in a rule definition, and can be dynamically selected,
such as through the use of trust metrics.

The AIR reasoner provides detailed justification (explanations) for
deductions by using a {\it Truth Maintenance System}, which keeps
track of the logical structure of a derivation. The justification
gives the details of the rules that fired, the order in which they
fired, and the data sources that contributed to the satisfaction of a
rule condition. This information is particularly useful when
evaluating the trustworthiness of an inference.

We may have different degrees of belief for rules and data and may
specify trust values that represent those degrees. These trust values
can be used when the rules are defined and may be incorporated in the
rule condition such that only those inferences that can be trusted are
deduced. These deductions can be further filtered by the rules that
use them based on new beliefs.  In the latter case, information on the
rules that fired and the datasets used to make the deduction may be
obtained from the justification produced by the AIR reasoner.

This paper is structured as follows: we begin by introducing existing
work dealing with trust on the web. Then, in section 3, we discuss
trust problems on the web by giving an example. Section 4 gives an
overview of the AIR language and how reasoning is performed. In
section 5 we describe how AIR can be used for trust management on the
Web. Finally, section 6 provides a summary and directions for future
work.

\section{Related Work}

Well-known trust management systems such as
PolicyMaker~\cite{blaze96dtrust}, KeyNote~\cite{blaze99keynote},
REFEREE~\cite{chu97referee}, and Delegation
Logics~\cite{li03delegation} view trust management as an authorization
problem. They define mechanisms for inferring whether a requester
(software or human agent) is permitted to perform a certain action or
access a certain resource based on a set of constraints defined by the
action/data owner. PolicyMaker, one of the first distributed trust
management schemes proposed, reasons over policies, a set of
credentials, and a string describing the secure action and can reply
with a yes/no answer dependent on whether the credentials meet/do not
meet the requirements of the policy.  It may also provide additional
requirements that would make the request acceptable. KeyNote is the
next generation of PolicyMaker. The basic function of both PolicyMaker
and KeyNote is to be able to answer queries about authorization;
neither is aimed at handling trust issues of data or data
sources. REFEREE was designed to facilitate security decisions for Web
browsing. It is similar to PolicyMaker as it allows its assertions
(credentials and policies) to be described in a programming
language. Unlike PolicyMaker, however, its trust management engine is
able to fetch additional credentials while evaluating a request and
can also perform cryptographic-signature verification. Delegation
Logic (DL) is a logic-based language for authorization in distributed
systems and is used to represent authorization through delegations.

Our approach is different from the above approaches in that it is
focused on evaluating the trustworthiness of data on the open Web and
on allowing decision making mechanisms about trust to be declaratively
specified. Approaches most related to ours are those which discuss how
trust values for users and data sources can computed such as
~\cite{richardson03trustmanagement,yolanda02trusting,golbeck03trustnetworks,kuter07sunny}. Richardson
et al. enable users to maintain trust for other users and provide
functions to merge these values into trust values for all users by
leveraging the path of trust between
users~\cite{richardson03trustmanagement}. Kuter et al. allow users to
maintain trust values or trust estimates for data sources and provide
a probabilistic technique to use that information to compute a trust
estimate for a data source~\cite{kuter07sunny}. Our approach can be
thought of as a meta-modeling approach that allows different trust
frameworks to be declaratively developed and possibly combined. It
provides a rule language, mechanisms for accessing the Web and
cryptographic, math, string and other related functions for specifying
how trust is assigned and calculated.


\section{Trust Problems on the Web}

There are two levels of trust we must have before we can establish a
complete determination of trust in Web reasoning: trust in data
sources and trust in rules.  Together, these two levels of trust may
be combined to synthesize a level of trust in the inferences made by a
reasoner.  Trust in data sources forms the cornerstone of trust on the
Web, as no trust may be established without a firm foundation in the
data we utilize in making decisions.  It is worthwhile to consider
rules in which the trust of a data source itself plays a role in
determining whether a rule may have matched.

Consider the following example: a stock broker, Big Bucks, Inc., makes
buy and sell recommendations to its clients based on an algorithm that
looks at various news, blog, and discussion forum feeds and then
matches them against desired criteria for each client.  Isabel, a
client of Big Bucks, has a fairly aggressive portfolio and is willing
to purchase any company for which a recommendation is published.
Unfortunately, not every stock analyst is trustworthy, as they may
have a vested interest in seeing certain stocks outperform others.  As
a result, Isabel may require a high level of trust in the sources in
which the recommendations are published.

More complex policies must also be represented.  Another customer of
Big Bucks, Jay, is more conservative than Isabel, and may requires two
buy recommendations from stock analysts (although he trusts their sell
recommendations more) \textit{and} requires that the stock be above
its 200 day moving average.  Since Jay trusts some statements more
than other statements, we must be able to differentially select trust
values dependent on the type of data used from a source.

The second level of trust we must consider is that of trust in rules.
Although being able to trust base facts is an important factor in
reasoning, many scenarios may have some level of trust integrated into
the rules themselves.  Rules may be probabilistic or produce only
partially trustworthy results due to a lack of certainty about the
rule itself.

For example, some of Big Bucks's customers may rely on rules that Big
Bucks itself has made available for use for its customers.  Karl uses
Big Bucks's rules as part of his decision making process, but does not
entirely trust them, as Big Bucks may have a conflict of interest in
making suggestions to its customers.  Karl may wish to only partially
trust Big Bucks's rules, depending on the output of other rules to
corroborate Big Bucks's conclusions as to what stocks are worth buying
or selling.

A framework that is flexible enough to capture these requirements
would be useful for trust management for Web data. In the following
sections, we show how AIR, a general Web rule language, can be used to
express different kinds of trust in data, data sources, and rules and
combine them in various ways to compute trust values for Web data.

\begin{figure}
\begin{VerbatimN3}
@prefix s: <http://s.example.org/ontology#>.
@prefix b: <http://b.example.org/ont#>.
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix : <http://src1.example.org/JohnAnalyst#>.

@forSome :X .

:X a <http://www.example.com/shoe>.
s:AmazonFootwear s:rec s:Buy.
a:BestPhone s:rec s:Buy.
a:ConArtist s:rec s:DontBuy.
:Weather :prediction :VeryHot. 
b:SARS rdf:type b:PotentialVirusOutbreak.
\end{VerbatimN3}
\caption{{\bf Content of an RDF Data Source}}
\label{fig:datasource}
\end{figure}

\section{Overview of AIR}

The rule language we use, AIR, is written in N3~\cite{bl05n3primer}, a
syntax for representing Semantic Web data based on the RDF abstract
syntax.  N3 makes use of a number of basic concepts from RDF,
including the concept of triples, which correspond to the logic
predicate \textit{holds(subject, predicate, object)}.  The logical
terms \textit{subject}, \textit{predicate}, and \textit{object} may be
literals, existentially quantified resources known as ``blank nodes'',
or opaque Uniform Resource Identifiers (URIs) denoted inside angle
brackets or using qualified names
(QNames)\footnote{http://www.w3.org/TR/REC-xml-names/\#ns-qualnames}. For
example, in Figure~\ref{fig:datasource}, the triple, \air{b:SARS
  rdf:type b:PotentialVirusOutbreak} has \textit{b:SARS} as
\textit{subject}, \textit{rdf:type} as predicate and \textit{
  b:PotentialVirusOutbreak} as \textit{object}. N3 extends RDF's
abstract syntax by adding formula quoting and universal
quantification.  Figure~\ref{fig:datasource} provides some examples of
N3 triples. RDF documents consist of conjunctions of these triples
which may also be called graphs or formulas. Please refer to
\url{http://www.w3.org/2000/10/swap/Primer} for an overview of N3 and
to the Appendix for the list of namespaces used in the paper.

\begin{figure}[!t]
\begin{center}
\includegraphics[width=5.6in]{images/air-ont.jpg}
\end{center}
\caption{{\bf AIR Rule Ontology}}
\label{fig:ont}
\end{figure}

AIR is made up of a set of built-in functions and two independent
ontologies --- the first is for the specification of AIR rules, and
the second deals with describing justifications for the inferences
made by AIR rules. The built-in functions allow rules to access Web
resources, query SPARQL Query Language for RDF (SPARQL)
endpoints~\cite{sparqlw3c}, and perform scoped contextualized
reasoning, as well as basic math, string and cryptographic operations.
While developing the rule vocabulary, we focused on capturing how real world 
rules and laws are written to allow them to be represented naturally in AIR. 
For the justification vocabulary, our focus was on re-usability of justifications 
and on automated proof checking. When given as input some AIR rules, defined
in the AIR rules vocabulary, and some Semantic Web data, the AIR
reasoner produces a set of inferences that are annotated with
justifications, described in the justification vocabulary. The runtime
input to AIR rules can be any RDF graph or an empty graph, if the
rules only access Web resources. In the 
following subsections we cover the AIR rule ontology and built-in functions; 
the AIR reasoner and representation of AIR justifications.

\subsection{AIR Rules}

\comment{
\todo{Notes: We introduce ontologies suddenly without explanation.
  Also, how to explain our sudden discussion of functions?  If they
  have a basic knowledge of RDF, they probably think it's
  declarative... Added a para on ontologies to the begin}}

The AIR rule vocabulary consists of several key classes and properties, 
shown in Figure~\ref{fig:ont}, which are identified by their QNames.
\air{air:Belief-rule} is a class of resources representing the set of
all rules for which full justifications are made.  These rules may
then have the properties \air{air:if}, \air{air:then}, and
\air{air:else} associated with them to represent the N3 pattern to be
matched, and the actions to take if the pattern matches, or does not
match, respectively.  \air{air:then} and \air{air:else} actions may be
described in terms of the facts they assert (using the
\air{air:assert} property) or the rules they cause to match next
(using the \air{air:rule} property). Figure~\ref{fig:exrule}
demonstrates how AIR rule vocabulary can be used to define Isabel's
simple rule about recommending stocks.  The rule suggests that Isabel
only buy stock in a certain company, \air{ air:assert \{ :Isabel
  s:shouldBuy :COMPANY\}}, if a data source such as a stock analyst of
a trust value greater than or equal to 5, \air{:TRUST1
  math:notLessThan 5}, recommends that the stock of that company be
bought, \air{ :COMPANY s:rec s:Buy }.

\comment{\todo{We probably should explain subject/predicate/object}}

\begin{figure}
\begin{VerbatimN3}
@forAll :SRC1,:TRUST1.

:IsabelBuyRule a air:Belief-rule ;
    air:if {
        :SRC1 log:includes { :COMPANY s:rec s:Buy . }.
        :SRC1 t:trustvalue :TRUST1.
        :TRUST1 math:notLessThan 5. }
    air:then [ air:assert { :Isabel s:shouldBuy :COMPANY . } ] .
\end{VerbatimN3}
\caption{{\bf Example AIR Rule:} \qname{IsabelBuyRule} uses the trust ontology
  described in Figure~\ref{fig:trustdecl}.b to assign trust to data
  sources. Isabel only buys stock in a certain company if a data source
  such as a stock analyst of a trust value greater than 5 recommends
  that the stock of that company be bought}
\label{fig:exrule}
\end{figure}

AIR supports several functions including cryptographic, math, string,
list and time functions.  \air{:TRUST1 math:notLessThan 5} is an
example graph pattern that uses the \qname{math:notLessThan} built-in
function. The subgraph of \air{:TRUST1 math:notLessThan 5} matches if
the value of \qname{:TRUST1}, which is a variable, is found to be
greater than or equal to 5. Similarly, {\air { :KEY crypto:md5 :HASH}
  calculates the MD5 hash of \qname{:KEY} and sets \qname{:HASH} to
  it. AIR also includes functions for signing and verifying signatures
  and certificates.

Traditionally, rule languages have been designed with the assumption
that all rules can use all the input data for deductions. However,
this isn't very desirable in a Web rule language, especially for
trust-based deductions. As we will also see through our examples,
different rules may require restricting of scope of applicability to a
subset of input data or documents, based off belief in the data or
documents. Sometimes the data is not just defined existentially but
also has an intentional component, defined through rules (which we may
call int-def-rules).  In order to access the complete data we must be
able to access the extensional as well as intentionally-defined data,
without risking unintended application of int-def-rules to the entire
input data. Note that the two scenarios described above are
different aspects of contextually scoped reasoning.  AIR includes
functions that are useful in manipulating remote data, and that
support contextually scoped reasoning such as \air{log:semantics},
\air{log:includes} and \air{air:justifies} built-in functions.

The \air{log:semantics} built-in fetches a document and returns its
representation as an N3 graph.  This N3 graph may then be used in
conjunction with the \air{log:includes} and \air{log:notIncludes}
built-ins to determine whether a sub-graph is, or is not, present in
the graph.  These \air{log} built-ins can be used to selectively
access content from Web resources.  \air{air:justifies} is a
particularly powerful built-in function that executes some external
AIR rules against some Semantic Web data and checks whether they
produces a certain RDF graph. It returns a graph containing both the
inferred results as well as the justification of the facts. In
Figure~\ref{fig:rule1}, \air{air:justifies} is used to execute a set
of rules and the inferred recommendation is only accepted if the
inference was made by a trusted rule. SPARQL queries can be executed
from within AIR rules using \air{sparql} built-ins. SPARQL CONSTRUCT
queries may be sent to SPARQL endpoints using the
\air{sparql:queryEndpoint} property assertion, and subgraph patterns
may be searched for in the graph returned by the endpoint.

\comment{\todo{Still need an overview of justification vocab}}


\subsection{AIR Reasoner}
\comment{\todo{Everything below is lifted from the IEEE Policy paper.}}

A deductive reasoning system derives conclusions from previous
deductions or premises by the application of deductive rules. For any
given conclusion, it is useful to know the specific set of premises
that it was derived from; this set is called the set of dependencies
for the conclusion. Dependency tracking is the process of maintaining
dependency sets for derived conclusions.

Some dependency-tracking mechanisms provide additional features. For
example, a Truth Maintenance System (TMS) keeps track of the logical
structure of a derivation, which is an effective explanation of the
corresponding conclusion.  Another useful feature, also provided by a
TMS, is the ability to assume and retract hypothetical premises.
There are several reasons why dependency tracking is useful for trust
management systems: (i) the dependency set for a result provides a
natural focus when trying to solve policy compliance problems, and
(ii) it can provide a concise explanation for a result. This is
essential for confirming that a trust framework is correctly modeled.
It can also help identify situations where a framework is having
unanticipated or undesirable consequences.

AIR uses a {\it Truth Maintenance System} as the dependency tracking
mechanism~\cite{kagal08using}. The TMS provides considerable power in
a very simple mechanism; its primary cost is the memory required to
record the structure of a derivation. Although the TMS technology was
invented in the 1970s~\cite{doyle79}, and recent work in applying
truth maintenance systems to problem solving was done in the
90s~\cite{forbus93building}, it is not well known outside the
artificial intelligence community.

\comment{Can we change first line to - "Our reasoner is a deductive
  reasoning system, where condition of a rule, which is
  production-rule like, is a pattern to be matched against a set of
  believed statements."?  The idea being to use the phrase "deductive
  reasoning system" - AK Yes - LK} \comment{added "or it fails to
  match, " after "When the pattern matches, "-AK}

Our reasoner is a deductive reasoning system, where condition of a rule,
which is production-rule like, is a pattern to be matched against a set of
believed statements. When the pattern matches, or it fails to match, 
the rule's action is performed. Typically the action asserts new beliefs, causing them to
be added to the set of believed statements. When something is added to
the belief set, it is associated with a justification for its
belief. In the case of a simple statement of fact, there is a trivial
justification that the statement is an assumption. A derived statement
has a justification based on the inputs used to make the derivation.


\begin{figure}[!t]
\begin{center}
\includegraphics[width=3in]{images/RuleApplication.jpg}
\end{center}
\caption{{\bf Ontology for description of a rule firing event}}
\label{fig:ruleapp}
\end{figure}

In such a simple rule system, all of the dependency information is
implied by the rules themselves. If a new belief is asserted by a
rule's action, then its justification is the set of statements that
matched the rule's pattern. More precisely, we believe the asserted
statement if and only if we believe every one of the matched
statements. Additionally, the justification records an identifier for
the rule; this identifier together with the matched statements provide
all the relevant information about the particular deduction step just
performed. Typically these deduction steps build on one another,
resulting in a tree-like justification structure for any given belief,
in which the belief is the trunk of the tree and the assumptions are
the leaves. This tree structure is a complete explanation of the
support for the belief.

The afore-mentioned dependencies are captured through an \air{Event}
based ontology. There is an event for every important operation
performed during reasoning - \air{Dereference},
\air{BuiltinAssertion}, \air{BuiltinExtraction}, \air{RuleApplication}
and \air{ClosingTheWorld}.

\air{Dereference} is used to relate the documents, of both data and
rules, with their graph representations.  The built-in triples are
premises and they are computed as needed by the reasoner. The output
data of the abstract event \air{BuiltinAssertion} is assumed to be all
the triples that hold for a particular built-in.  The specific triples
that were computed are represented as \air{outputdata} of the
\air{BuiltinExtraction} event, which refers to the abstract operation
of extracting the triple from all the facts.

Firing of a rule is captured as a \air{RuleApplication} event.
Figure~\ref{fig:ruleapp} describes various properties associated with
a \air{RuleApplication} event. The rule-id is given by the
\air{air:rule} property. Whether the \air{then} or \air{else} action
fired is described using \air{airj:branch}. If the \air{then} branch
fired then the subset of data that satisfied the condition is declared
using \air{airj:matchedgraph}.  The \air{else} actions fire only if no
\air{then} actions can be fired for all other rules. Before the
\air{else} actions actually fire, the world is closed (temporarily)
assuming all the failed rule conditions to be false. The closing of
world is captured using the \air{ClosingTheWorld} event. When a nested
rule fires a \air{nestedDependency} is established with the firing of
the parent rule event, which activated the nested rule. The triples
asserted when the rule fired, are associated with the \air{air:outputdata} property.

\comment{\todo{Work the paragraph below into the paper better}}

In Figure~\ref{fig:rule2} we filter those buy recommendations for Karl, 
\air{:Karl s:shouldBuy :COMPANY}, that are supported by a trusted \qname{:RULE}
defined in \url{http://bigbucks.example.com/rules}. The rule searches the 
justification returned by AIR reasoner for a \air{RuleApplication} event,
\qname{:RULEAPPEVENT}, such that some \qname{:RULE} fired and asserted the buy recommendation.

\begin{figure}[t]
\begin{tabular}{|p{1in}|p{2.25in}|p{2.5in}|}
\hline
{\bf Ontology Type } & {\bf Ontology Definition} & {\bf Example Assignments} \\
\hline
a. Simple binary trust & TrustedSource rdf:type rdfs:Class. UnTrustedSource rdf:type rdfs:Class & $<$http://src1.example.org$>$ rdf:type TrustedSource.  $<$http://srcx.example.org$>$ rdf:type UnTrustedSource\\
\hline
b. Trust value & trustvalue rdf:type rdf:Property. &  $<$http://src2.example.org$>$ trustvalue 8. $<$http://src1.example.org$>$ trustvalue 2 \\
\hline
c. Qualified trust & trust rdf:type rdf:Property; range TrustVal. tval rdf:type rdf:Property; domain TrustVal. tpattern rdf:type rdf:Property; domain TrustVal. &  $<$http://src1.example.org$>$ trust [ tval 8; tpattern \{ :VARIABLE s:rec s:Buy\} ].  
$<$http://hospital.example.org$>$ trust [ tval 99; tpattern \{ :VAR1 rdf:type h:PotentialVirusOutbreak; h:duration :VAR2 \} ]\\
\hline
d. Trust associated with rules & trustvalue rdf:type rdf:Property & $<$http://bigbucks.example.com/rules \#BuyRule$>$ trustvalue 7 \\
\hline
\end{tabular}
\caption{{\bf Example Trust Declarations for Data Sources and Rules} }
\label{fig:trustdecl}
\end{figure}

\section{AIR and Trust Management}

As AIR is a Semantic Web-based rule language it is able to reason over
different semantic representations for trust. The language does not
insist on any specific representation of trust and allows the
user/system to provide a representation that best captures their
requirements. Figure~\ref{fig:trustdecl} provides some examples of how
trust could be assigned to data sources.  Figure~\ref{fig:trustdecl}.a
is a simple way of representing binary trust. It defines 2 classes,
\qname{TrustedSource} and \qname{UnTrustedSource}, and a source can be
declared to be either trusted or untrusted depending on which class
it belongs to. Figure~\ref{fig:trustdecl}.b illustrates how trust
values can be assigned to sources through a \qname{trustvalue}
property.  Figure~\ref{fig:trustdecl}.c is an example of trusting a
source with respect to certain data. For example, a hospital site may
be trusted with information about a potential virus outbreak but may
not be trusted with respect to its inflation predictions. The
\qname{tpattern} is a graph pattern property and it signifies that
only RDF data from the source that match the pattern will be
trusted. For example, if the content of a trusted site is as shown in
Figure~\ref{fig:datasource} and the \qname{tpattern} is in
Figure~\ref{fig:trustdecl}.c, then only the triples that match the
\qname{tpattern}, \air{s:AmazonFootwear s:rec s:Buy.  a:BestPhone
  s:rec s:Buy. }, will be trusted and the triples regarding the virus
outbreak and weather will be ignored.  AIR currently supports simple
graph patterns to specify the kinds of data trusted from a certain
source. Similar representations are possible for rules, for example,
Figure~\ref{fig:trustdecl}.d shows a trust value associated with a AIR
rule, \qname{BuyRule}.

\begin{figure}[!t]
\begin{VerbatimN3}
@forAll :SRC1, :SRC2, :TRUST1, :TRUST2, :COMPANY, :PRICE, :MA200.

:JayBuyRule a air:Belief-rule ;
    air:if {
        :SRC1 log:includes { :COMPANY s:rec s:Buy . } ;
              t:trust [ t:pattern { :VARIABLE s:rec s:Buy . } ;
                               t:value :TRUST1 ] .
        :SRC2 log:includes { :COMPANY s:rec s:Buy . } ;
              t:trust [ t:pattern { :VARIABLE s:rec s:Buy . } ;
                               t:value :TRUST2 ] .
        :TRUST1 math:notLessThan 7 .
        :TRUST2 math:notLessThan 7 .
        <http://stocks.example.com/ticker> log:includes {
              :COMPANY s:stockPrice :PRICE ;
                  s:TwoHundredDayMA :MA200 . } .
        :PRICE math:greaterThan :MA200 .
    } ;
    air:then [ air:rule :CompareSources ] .

:CompareSources a air:Belief-rule ;
    air:if { :SRC1 owl:sameAs :SRC2 . } ;
    air:else [ air:assert { :Jay s:shouldBuy :COMPANY . } ] .
\end{VerbatimN3}
\caption{{\bf Compute trust in data using trust in data sources:
  }\qname{JayBuyRule} uses the trust ontology described in
  Figure~\ref{fig:trustdecl}.c to assign trust to data sources with
  respect to buy recommendations. If there are two different data
  sources with trust values greater than or equal to 7 that recommend
  the same stock, and if the stock is above its 200 day moving
  average, then the rule recommends that Jay should buy that stock.}
\label{fig:rule1}
\end{figure}

AIR rules can be written to consume these trust declarations and
combine them in different ways in order to compute trust values for
data or inferences of interest. \qname{JayBuyRule} uses the trust
ontology described in Figure~\ref{fig:trustdecl}.c to assign trust to
data sources with respect to buy recommendations. \qname{:JayBuyRule}
recommends that Jay buy a stock if there are two different data
sources with trust values greater than 7 that recommend it and if the
stock is above its 200 day moving average. The rule could be modified
to calculate the minimum or average trust of all sources recommending
a particular stock and estimate how trusted the recommendation to buy
the stock is. Probabilities associated with data sources could also be
handled similarly.

AIR rules can also reuse and execute other AIR rules. As rules
themselves could have trust values associated with them, as in
Figure~\ref{fig:trustdecl}.d, it is possible to reason about the
trustworthiness of rules and deduce trust of inferences made by them.
AIR's support for the \air{air:justifies} property allows for the
execution of other rules which we may be able to query for trust.  The
rule \qname{:KarlBuyRule} in Figure~\ref{fig:rule2} encapsulates such
a rule and recommends that Karl buy a stock only if the rule that is
used to justify the recommendation is trusted by Karl with a trust
value greater than or equal to 7.

In \qname{:KarlBuyRule}, \air{air:justifies} is used to run the rules
at the URL $<$http://bigbucks.example.com/rules$>$ (as extracted with
\air{log:semantics}) against some trusted data.  The result of this
reasoning is stored in the output variable \qname{:RULEJUST}, which
may be used with other built-in functions, like \air{log:includes}, to
determine not only which facts are asserted by the rules, but also the
justifications for such.  These justifications may then be used to
determine the rules which caused some conclusion to be found to be
true and their trust values.

\comment{
\note{The below will work for specific trust patterns.  General trust
  patterns are harder because I don't know if a universal variable
  that is bound to another variable will remain universally
  quantified.  It would also make rules more complex.  What about a
  trust pattern \{ :S :P s:Buy \} ???  I'm not sure it's possible
  because we need to say that the value of the value of a variable is
  equal to something.  As far as I know, we can't dereference a
  variable TWICE.}}

\begin{figure}[t]
\begin{VerbatimN3}
@forAll :RULESET, :DATA, :RULEJUST, :COMPANY, :RULE, :TRUST.

:KarlBuyRule a air:Belief-rule ;
    air:if {
        <http://bigbucks.example.com/rules> log:semantics :RULESET .
        ((:RULESET) (:DATA)) air:justifies :RULEJUST .
        :RULEJUST log:includes {
            @forSome :RULEAPPEVENT .
            :Karl s:shouldBuy :COMPANY .
            :RULEAPPEVENT pmlj:outputdata { :Karl s:shouldBuy :COMPANY . } .
            :RULEAPPEVENT air:rule :RULE .
        } .
        :RULE t:trust :TRUST .
        :TRUST math:notLessThan 7 .
    } ;
    air:then [ air:assert { :Karl s:shouldBuy :COMPANY . } ] .
\end{VerbatimN3}
\caption{{\bf Compute trust in data using trust in rules:
  }\qname{KarlBuyRule} uses the trust ontology described in
  Figure~\ref{fig:trustdecl}.d to assign trust to the rules used by
  Big Bucks to generate buy recommendations.  If the rule used to
  generate a buy recommendation has a trust value greater than or
  equal to 7, then the rule recommends that Karl should buy that
  stock.}
\label{fig:rule2}
\end{figure}

\section{Summary and Future Work}

In this paper, we discussed how AIR, a Semantic Web-based rule
language, could be used to model and reason over trust of data
sources, rules and inferences. We discussed several ways of modeling
trust including binary trust, simple trust values and qualified trust
for both data sources and rules and showed how these trust values
could be used and combined by rules for trust management. Though this
work demonstrates the usefulness of AIR, it relies on user-generated
rules for handling trust. As part of our future work, we will work on
general rules that will handle trust transparently such that users do
not need to explicitly know about or handle trust in their systems but
will be able to customize these rules to do it for them. These rules
will also take other factors into consideration while computing trust,
such as the maintainer of the data, the last date it was updated, and
frequency of updates, which could either be meta-data associated with
the data itself or available from public annotation services such as
Annotea~\cite{annotea}.


\comment{
\section*{Acknowledgements}
We would like to thank the members of the Decentralized Information
Group at MIT as well as those of the Tetherless Constellation Group at
RPI for their advice and contributions to this project.  This work was
supported in part by NSF Cybertrust award number 04281, IARPA award
number FA8750-07-2-0031, and AFOSR award number 6921570.
}

\bibliographystyle{abbrv}
\bibliography{paper}

\appendix

\section{APPENDIX: Namespaces}

In this paper, we refer to the namespaces defined in
Figure~\ref{fig:namespaces}.

\begin{figure}
\begin{VerbatimScript}
@prefix air: <http://dig.csail.mit.edu/2009/AIR/air#>.
@prefix airj: <http://dig.csail.mit.edu/2009/AIR/airjustification#>.
@prefix log: <http://www.w3.org/2000/10/swap/log#>.
@prefix math: <http://www.w3.org/2000/10/swap/math#>.
@prefix sparql: <http://www.w3.org/2000/10/swap/sparqlCwm#>.

@prefix pmlj: <http://inference-web.org/2.0/pml-justification.owl#>.

@prefix rdfs: <http://www.w3.org/2000/01/rdf-schema#>.

@prefix t: <http://bigbucks.example.com/trust#>.
@prefix s: <http://bigbucks.example.com/stocks#>.
@prefix : <http://bigbucks.example.com/buyPolicy#>.
\end{VerbatimScript}
\caption{{\bf Namespaces Used}}
\label{fig:namespaces}
\end{figure}

\end{document}
