\chapter{Security and Stability}

\label{ch:issues}

The distribution of propagation and provenance across a network
introduces several issues that must be addressed to ensure that any
such system is useful in constructing large systems.  Some of these
issues, such as garbage collecting unused copies of cells, are not
immediately harmful if left unresolved; I consider such issues to be
future work in this area.  Other issues, such as data security and
loss of stability due to race conditions, are more directly harmful to
distributed propagation.  If left unresolved, these issues offer
significant hurdles to the consideration of data propagation as a
viable computational platform.  I address these issues in more detail
in this chapter.

% Eh, don't like this but...

\section{Distributing Propagators}

\subsection{Merging and Race Conditions}

Although the periodic re-synchronization operation described in
Section~\ref{sec:resync} helps to alleviate many causes of
de-synchronization in propagator networks, we must also consider
potential race conditions in a distributed propagator network.  Race
conditions naturally arise within distributed and concurrent systems
as a form of non-deterministic behavior that may be caused by a
reordering concurrent events. \cite{netzer1992race,netzer1996mpirace}
Such race conditions may lead to de-synchronization of copies of a cell
in which data is lost in a distributed propagator system.

It is usually possible to generate a race condition in any concurrent,
general-purpose computing system.  With proper adherence to the
protocol, however, distributed propagation reduces the chance of
accidentally inducing a race condition.  The idempotency and
commutativity constraints placed on the cell merge operation,
described in Section~\ref{sec:mergeprops}, limit the chances of
developing many race conditions.  Merges must behave identically
regardless of the order or number of updates received.  This implies
that the contents of the cell will not usually depend on the
timeliness or ordering of update messages.  While it is still possible
to construct applications with race conditions (e.g. a non-commutative
operation retrofitted to be commutative may still result in race
conditions), these problems are clearly the responsibility of the
application layer, rather than caused by the propagation mechanism
itself.

\begin{figure}
\begin{center}
\includegraphics{broken-clique.pdf}
\caption{A clique of cells is temporarily broken when a new cell joins.}
\label{fig:broken-clique}
\end{center}
\end{figure}

Other race conditions in distributed propagators are induced by the
implicit concurrency of cell initialization.  It is possible to
construct a scenario in which update messages from an initializing
cell copy (E in Figure~\ref{fig:broken-clique}) are dropped at
existing peers between the time that the initializing cell copy learns
the set of all peers and the time that the new cell has notified these
peers of its existence.  Similarly, the remote cell copy (B) may
receive an update \textit{after} the initializing cell copy has
read the existing peer, but \textit{before} it has learned all other
remote peers in the network.  In this case, the update is dropped at
the new cell.

Both of these race conditions are byproducts of the fact that the
network is not a complete clique during the initialization process.
Although the network may begin as a clique (left side of
Figure~\ref{fig:broken-clique}), the clique is broken when a new cell
adds itself to the remote peer's ``Peers'' collection; this adds a
single edge between that cell and the cell from which it is
initializing (center of Figure~\ref{fig:broken-clique}).  The network
only returns to being a clique when the new cell has added itself to
every known peer; this adds the final edge that restores the clique
(right side of Figure~\ref{fig:broken-clique}).  During the time that
the network topology is not a clique, timeliness guarantees about
updates do not hold.

The re-synchronization operation resolves this.  Once the new cell is
being initialized, the entire network may no longer be a clique, but
it remains \textit{eventually connected}.  Updates made by the
initializing cell will always be propagated to the remote cell, and
from there, the re-synchronization mechanism will suffice to
eventually diffuse those updates to the remainder of the network.
Similarly, any updates that are not directly received by the
initializing cell \textit{will} be received by the remote cell, which
may then propagate the message to the initializing cell through its
re-synchronization operation.

% TODO: Should we have an image?

\subsection{On Connection Failure}

Similar issues arise due to the need to connect to a pre-existing
distributed cell, although these are not strictly race conditions.
How may we handle temporary unavailability of a remote cell without
blocking local computation?  If the remote cell isn't available at
initialization time, we still permit local computation; we may merge
local data into the cell any time after it has been created, even if
it hasn't been initialized from a remote cell.  That said, the cell
must be able to reconnect to the network when possible in order to
ensure that its updates are propagated to the currently unavailable
remote cell.  We must be able to guarantee \textit{eventual
  connectedness} of the network, or the contents of the cell will not
converge.

There are several ways to approach this issue, including the
na\"{\i}ve approach of simply retrying the connection.  We may also
allow for several backup URLs to be provided at initialization time.
If the primary URL is unavailable, the cell would then be able to fall
back on an alternate URL for another copy of the same cell.
Regardless of the approach taken, recovering from an initialization
failure caused by a lack of network connectivity requires the cell to
continue trying to initialize.  A failure to initialize may not
compromise the ability of the distributed propagator system to perform
local computation, but it may prevent local computation from obtaining
useful results.

\section{Securing Distributed Cells}

\label{sec:security}

Applications that use distributed propagation may require securing the
data transferred over the distributed propagator network.  Although a
cell that contains facts about meteorological temperatures may seem to
be a trifle, unworthy of any security whatsoever, there are no
constraints on the data a cell contains; cells may contain anything
from benign personal data to highly classified government information.
Thus, security of data within a propagator network may be necessary to
ensure wide acceptance of distributed propagation.

There are several methods that may be used to secure propagation.  For
example, existing methods used to secure otherwise unencrypted
channels may be useful on a distributed propagator network without any
security.  Unfortunately, this is not necessarily a safe practice;
even unsecured distributed propagation will reveal the hosts who have
copies of a specific cell, identified by its UUID.  It will also
reveal information about the frequency and source of updates and
re-synchronization attempts. By mapping this network structure to the
structure of networks for which the data is \textit{known}, it may be
possible to derive knowledge about the otherwise secured network.
This general approach to deriving network structure has already been
used to deanonymize social networks \cite{narayanan2009social}, and it
would be reasonable to assume that this class of attacks could be used
to deduce some useful knowledge of a propagator network as well.

A more secure approach to securing propagation would be to secure the
underlying protocol itself.  Although the flows of data would still be
traceable, meta-data about the requests, such as the identity of the
cell, would be more difficult to determine without a detailed traffic
analysis, if possible at all.  As my proposal for distributed
propagation uses HTTP as a substrate for distributed propagation, we
may utilize SSL to secure the HTTP protocol so that communications are
completely opaque to eavesdroppers.

By using SSL to encrypt the underlying HTTP communications, we are not
only able to defend communications against man-in-the-middle attacks,
but we also provide a method of non-interactive authentication by
using certificates to identify client and server.  Unfortunately,
na\"{\i}ve use of SSL is insufficient for encrypting propagation; SSL
assumes that connections need only be secured between two physical
hosts, rather than between two users on those hosts.  This may be
unacceptable on an implementation that hosts cells for a number of
different individuals.  These individuals may desire their own
point-to-point encryption that is not possible with SSL; SSL allows a
server to offer only a single server-wide certificate, rather than
allowing the certificate to vary according to the URL
requested.\footnote{SSL's most recent incarnation, TLS, allows for
  certificates to be presented based on the \textit{hostname} rather
  than the server's IP address. This allows the server some
  flexibility in selecting its certificate to present to the client,
  but even TLS is required to offer the server's certificate before
  the full HTTP URL being requested is made available to the server.}
The following scenario demonstrates this issue more clearly:

Assume that Alice wishes to connect to an intermittently available
cell operated by Bob. Bob's cell is hosted on a DProp peer that he
shares with Eve. If Eve was aware of the times when Bob's cell was
unavailable, she could create a cell with the same URL as Bob's and
wait for updates from Alice.  Alice would be unable to distinguish
whether the cell had been created by Bob or by Eve, as the only
mechanism for authenticating the DProp peer is a server-wide
certificate.  This means that the same certificate is provided to
Alice to identify the cell's creator, regardless of who actually
created it.

Several na\"{\i}ve solutions to this issue exist.  Permanent
reservation of cell URLs is one such solution, as it would effectively
prevent an eavesdropper from registering a cell that was previously
used by another person.  We could also use a secondary identifier or
key that would directly identify the owner of the cell.

A better mechanism would be to encrypt the contents of the cells
themselves.  If Bob shared knowledge about the cell's encryption with
Alice, Alice would be able to decrypt the cell and its corresponding
updates.  She would be safe in the knowledge that the cell had not
been modified, as \textit{only} Alice and Bob had the information
necessary to encrypt the cell in the first place.  This approach is
problematic, however, as it requires double-encryption of the
contents.  This adds complexity to the code and effectively double the
computational power needed to propagate data, as every new propagation
would require encryption \textit{twice}.

One other possible solution may resolve this issue; instead of
double-encryption or abandoning SSL, we may be able to use the SSL
protocol's existing renegotiation mechanism.  SSL renegotiation allows
either the server or client to force the other party to re-authenticate
in the middle of SSL communications.  This also allows the client or
server to change its set of encryption and decryption keys.  Thus, we
may use this approach in distributed propagation to allow the server
to change its keys to match those used to identify the requested cell
while keeping all parts of the HTTP communications secure.  This
requires the client to know the set of server-wide keys that will be
presented initially, and assumes that the server would renegotiate the
set of keys upon receiving the request for the cell.  If this was not
done, the client could simply opt to not send any updates or requests
to a cell which did not renegotiate to the expected keys.

% TODO: Personally proofread the old Ch. 2 Provenance section.

% TODO (General): Not ``inevitable'' but rather layering.

% TODO (General): Complexity of merging two different pointer sets

% TODO (Long-term): What does it mean to be a propagator?

% TODO (General): Explain REST better.

\section{Auditing Provenance Traces}

\label{sec:provaudit}

When constructing a provenance structure like those described in
Section~\ref{sec:provenance}, it may be necessary to audit the
structure to ensure that data and provenance were not tampered with.
Traditional methods of provenance verification may prove to be a
useful basis to implementing provenance auditing mechanisms within our
system.

Much work in securing provenance against tampering has assumed that
provenance takes the form of a \textit{linear chain} of modification
or possession records, rather than the directed acyclic graph we
assume in this thesis.  \cite{schneier1999logs} Linear provenance may
be sufficient for some use cases; provenance-aware file systems, for
example, define provenance through the operations performed on a
single file, so there is no need to trace multiple inputs and outputs.
\cite{sar2005lineagefs} Propagators do not simply have singular inputs
and outputs; this is why we assume that our provenance has a graph-like
structure.  This also means that we must be able to secure this
graph-like structure against modification.

We may be able to use a method of signing chains of provenance
recently proposed by Hasan, et al \cite{hasan2009picasso} as the basis
for securing provenance graphs.  Hasan proposes that each record in a
provenance chain should include a cryptographic signature of that
record.  This signature would consist of a hash of a set of meta-data
in the record combined with the signature of the previous record in
the provenance chain.  This hash would then be signed with the private
key of the individual responsible for that particular record of the
provenance.  This would assign provable authorship of the record to a
specific individual.

% Mention the constraints this places on the modification of the
% provenance.

This provenance may then be verified by processing each record of the
chain in order.  The verification algorithm calculates the expected
value of the hash from the signature of the previous record and the
current meta-data and validates the calculated hash against the
signature of the current record using the record owner's public key.
If the signature cannot be validated, then the provenance or data has
been tampered with.  The provenance algorithm then processes the next
record in the chain.

Although Hasan's proposal assumes that provenance is a linear chain,
the algorithm may be easily modified to verify a graph-like provenance
structure.  Rather than signing a hash that uses the single most
recent record checksum, we may sign a hash that uses \textit{all} of
the parents of a provenance record.  The verification algorithm would
be modified to include the signatures of all parent records when
constructing the hash.  Instead of traversing a linear structure, the
verification would move from the ancestors of the graph towards the
seed using a depth-first traversal of the graph from the seed.  In
this sense, Hasan's original proposal is simply a degenerate case in
which the number of parents of a record is restricted to one.

To ensure integrity of provenance within distributed propagator
networks, we would include this variant of Hasan's signature as part
of each record stored in the provenance sub-cell.  In the stub method
forming the basis of the merge operation of the provenance sub-cell, we
would also add a subroutine to automatically calculate the new
signature for the root provenance record given the signatures of the
most immediate parents of that record and include this signature as
part of the record structure itself.

% Benefits of Local provenance?  This probably belongs to the
% provenance section.
