\chapter{Trust Metrics}
\label{tmetrics}

In this chapter, we review the literature of trust metrics, present a
quantitative framework for analyzing the attack resistance of trust
metrics. Finally, we prove tight upper and lower bounds on the attack
resistance of trust metrics given the usual scalar assumptions.

\section{The simplest trust metric}

In this section, we present the simplest possible trust metric, which
forms the basis of other trust metrics in the literature.

There are three inputs to this trust metric: a directed graph, a
designated ``seed'' node indicating the root of trust, and a
``target'' node. We wish to determine whether the target node is
trustworthy.

Each edge from $s$ to $t$ in the graph indicates that $s$ believes
that $t$ is trustworthy. The simplest possible trust metric evaluates
whether $t$ is reachable from $s$. If not, there is no reason to
believe that $t$ is trustworthy, given the data available.

In a cryptographic implementation, each node corresponds to a public
key, and each edge from $s$ to $t$ corresponds to a digitally signed
\emph{certificate}. In the usual terminology, $s$ is the
\emph{issuer}, $t$ is the \emph{subject}. The certificate itself is
some string identifying $t$, along with a digital signature of this
string generated by $s$.

The simplest trust metric is also the weakest with respect to
attacks. If an attacker is able to generate an edge from any node
reachable from the seed to a node under his control, then he can cause
arbitrary nodes to be accepted.  As the size of the reachable subgraph
increases, the risk of any such attack increases as well. Thus, the
primary focus in the literature is to present stronger trust metrics
that (hopefully) resist attacks better, while still accepting most
nodes that deserve trust.

Section~\ref{tmetric-survey}, discusses a sampling of trust metrics
previously published. Section~\ref{tmetric-quant}, presents a
quantitative notion of ``attack resistance.'' 

\section{Survey of the literature}
\label{tmetric-survey}

All trust metrics include the three inputs described above: the trust
graph, the seed node, or \emph{trust root}, and the target. Some trust
metrics add more detail to these inputs. Trust edges may contain some
conditions or restrictions, for example that $t$ is himself
trustworthy, but cannot be trusted to vouch for other nodes. In
addition, the target may be a richer assertion than merely whether a
certain node is trustworthy. For example, edges may additionally
identify a maximum dollar value, and the target may be an assertion
that the target node can be trusted with a transaction of some dollar
value.

Finally, there may be additional policies to be enforced by the trust
metric, or parameters supplied. Often, these parameters control the
overall strictness or tolerance of the trust metric.

The most general form of ``trust management'' system is represented by
PolicyMaker\cite{BFL96}, as certificates and policies can represent
arbitrary computations in Turing-complete language. Applications of
PolicyMaker tend to focus on the language of assertions rather than
trust computations over the graph, but the fully general nature of the
system allows the the latter to be implemented.

Most trust metrics in the literature assume monotonicity. More
precisely, if a monotonic trust metric accepts a node $t$ as
trustworthy when given a graph $G$, it will also accept node $t$ when
given a graph $G'$ that contains all trust edges in $G$. A primary
motivation for this assumption is scaling. In particular, it allows
for highly efficient overall distributed architectures in which all
participants need only access a small, local subset of the global
trust graph. Further, under such an assumption, there is no special
vulnerability to denial of service attacks. With the monotonicity
assumption, if an attacker can withold trust edges (i.e. cause the
verifier to evaluate a subset of the global trust graph), then it
cannot cause nodes to be accepted other than those which would be
accepted given the entire trust graph.

The simplest trust metric is clearly monotonic. Adding edges to the
trust graph can only cause more nodes to be reachable.

Another relatively simple trust metric is similar to the simplest one,
with the additional constraint that path lengths are bounded by some
parameter $k$. Thus, all nodes within a distance of $k$ edges from the
seed are accepted. A variation of this trust metric is used in X.509
systems.

Perhaps the earliest published system resembling a modern trust metric
is the Beth, Borcherding, and Klein\cite{beth94valuation}. This system
contains a set of elaborate inference rules for deriving a
``trustworthiness'' value between 0 and 1, using both ``direct trust''
and ``recommendation trust'' relationships encoded on edges. However,
further work by Reiter and Stubblebine\cite{RS97b} showed this trust
metric to be no more secure than the simple reachability criterion
described above. Note that the BBK trust metric is not monotonic.

A still earlier system is described by Tarah and
Huitema\cite{tarah92associating}, who suggest evaluating both
certificates and ``certificate paths.'' They suggest several possible
simple trust metrics, including the length of the certification path
and the minimum of involved trust values along the path. However,
because it evaluates only paths, rather than general graphs, this
system does not quite meet the definition of ``trust metric''.

Reiter and Stubblebine\cite{RS97a} presented the first trust metric
with the ability to resist nontrivial attacks. Briefly, this trust
metric counts the number of node-independent paths of bounded length
from the seed to the target. Thus, both the path length and the
threshold for the minimum number of such paths are tunable parameters
of the metric. A simple characterization of its attack resistance
follows easily: an attacker must add ``bad'' edges to nodes under his
own control to at least as many nodes as the threshold for the number
of independent paths. Even though evaluation of this trust metric is
an NP-complete problem, the experimental PathServer implementation
seems to perform reasonably well in practice.

Maurer presented an intriguing trust metric based on randomized
experiments\cite{Mau96}. Very briefly, each edge in the network has
an associated probability. The result of the trust metric is the
probability that the target is reachable from the seed in a subgraph
of the original graph where each node is present with the probability
given in the original graph.

Both implementation and analysis of the Maurer trust metric are
challenging. In addition, we present an analysis below
(Section~\ref{maurer-analysis}) suggesting that the Maurer metric is
vulnerable to an easily-mounted attack. To do so, we will first need
to prepare a framework for quantitatively evaluating the attack
resistance of a trust metric.

\section{Framework for analysis}
\label{tmetric-quant}

What does it mean for a trust metric to be attack resistant? In
this section, we present a quantitative framework for this question.

In any given attack, we assume that the attacker can add or delete
edges from the legitimate part of the trust graph, pointing to
arbitrary nodes. These edges may point directly to nodes under the
attacker's control, or perhaps to other good nodes, in order to
fool the trust metric.

We assign a \emph{cost} to each such attack. A typical cost metric is
to count the number of edges added. Assuming an attack of a given
cost, what is the highest number of bad assertions the attacker can
force to be accepted? If this number is limited, the trust metric is
attack resistant. If it can grow to the same order as the number of
good assertions even for a fairly low cost attack, then the trust
metric suffers from catastrophic failure and is not attack resistant.

\subsection{Cost metrics: node vs edge attacks}

We consider two cost metrics. The simplest is to count the number of
edges added. Another useful metric is to count the number of
``attacked '' nodes with added outedges, and to assume that any such
node may have an arbitrary number of edges added. As we will see
later, the attack-resistance properties of different trust metrics
behave differently under these two cost assumptions. Note that, for
any given attack, the number of nodes counted is no greater than the
number of edges counted.

An edge attack corresponds to fooling a victim into generating an
edge. In many cases, mounting such an attack is straightforward. For
example, the attacker may send a forged email pretending to be a
friend of the victim, asking for a cert. Many such electronic means
of transmitting key material suffer from lack of authentication.

Similarly, a node attack corresponds to taking over the victim's
ability to create certificates. Such an attack is generally harder
than an edge attack, but still feasible. For example, anyone with
physical access to the victim's machine can recover the private key
used to sign certificates, for example by using a keyboard sniffer to
recover the encryption key used to protect the private key.

Edge attack: number of certs. Corresponds to fooling the victim once.

Protection against node attack is a stronger property than protection
against edge attack. Attack of a single node can correspond to an
arbitrary number of edges.

Another factor in trust metric: how many certs are needed? At
simplest, indegree of target node.

We analyze two classes of attacks: one in which the attacker is able
to choose the victims, and another in which the victims are chosen
randomly. The former class of attack is at least as effective as the
latter, and, not surprisingly, we find that it in most cases it is
considerably more so. This result parallels the literature in
scale-free networks, in which removing the ``hubs'' in a scale-free
network with hub-and-spoke topology is far more effective in
fragmenting the network than simply removing random nodes.

\section{Analysis: upper bounds}

Strict upper bounds on effectiveness of trust metric. For node attack,
if $n$ nodes are attacked, entire system falls, where $n$ is minimum
indegree of target node.

Proof: attacker chooses target that is accepted (with minimum
indegree), and chooses its predecessors as victims. Since indegree is
$n$, attack is $n$ nodes. Removing the original target, the graph is
identical to the one in which the original target is accepted, so the
trust metric can't distinguish.

For edge attack, if $n^2$ nodes are attacked, entire system fails.
Choose target as above, then spoof inedges of predecessors of target.

\section{Analysis: lower bounds}

This section analyzes existing trust metrics.

Present simple flow-based metrics, and prove (using min-cut) that they
almost exactly meet the upper bounds given above.

\section{Analysis of Maurer's trust metric}
\label{maurer-analysis}

Analysis of Maurer: follow \cite{LA98}.

\section{Discussion}

Several conclusions follow from the analysis presented in preceding
sections. First, the scalar trust metrics place a very low upper bound
on the attack resistance possible to achieve. Second, we demonstrate
that simple trust metrics based on maximum network flow meet these
upper bounds. Thus, within these assumptions, there is little if any
room to design improved trust metrics.

In particular, analysis of Maurer's trust metric shows its attack
resistance to be both disappointing and equivalent to much simpler
metrics.

A reasonable conclusion, then, is that it is the monotonicity
assumption itself which is flawed, and that it is not possible to
achieve good attack resistance by verifying a small, local subset of
the trust edges comprising the global trust metric. Indeed, in the
next chapter, we show that by relaxing the monotonicity assumption, a
reasonably simple trust metric also based on maximum network flows can
acheive dramatically better attack resistance.