scyllarus-and-mifd.tex

\section{The Scyllarus and MIFD systems}
\label{sec:mifd}

Our original system Scyllarus
%% TODO Restore for QR'15
% was an open system which 
performed IDS
fusion on a diverse set of third party \idses~\cite{goldman:discex2001}.
Its successor
MIFD (Model-based Intrusion Fusion and Detection)
enhances Scyllarus
%% TODO Restore for QR'15
% as part of the STRATUS system's integration of
 to integrate
IDS fusion into a comprehensive suite for cyber defense
\anoncite{thayer13:_compar_strat_tactic_respon_cyber_threat}.
For simplicity we refer to our \ids fusion system as ``MIFD,'' but
except where we specify otherwise, our account applies to Scyllarus as well.

The first tasks performed by MIFD are
\emph{collection} and \emph{translation}: IDS reports
must be collected and presented to MIFD, and
must be translated into a common
sensor report data structure for processing.
We will not discuss these less interesting
preliminaries, except to mention that they
involve a substantial amount of data rectification
%% TODO Restore for QR'15
 to address the lack of standardization in data formats and event taxonomies.
%.  There is no widely-accepted
%common data format (the proposed IDMEF standard~\cite{IDMEF} has not caught on), nor
%is there an accepted taxonomy for events or event roles (e.g., the widely used ``source''
%and ``destination'' are not consistently applied).
%These problems are exacerbated by the fact that intrusion detection ``systems''
%are often simply a casually-assembled anthology of rules by different authors running in the same
%framework.

{\ids} fusion proper begins with
\textbf{Clustering.} From the
sensor reports,
and based on an ontology detailing how (and with what probability)
sensor reports may correspond to events,
MIFD generates \emph{event hypotheses} to represent the
underlying events of interest that may have caused the sensor reports.  A
sensor report that provides evidence for an event hypothesis is a
\emph{supporter}.
The clustering process constructs a
directed graph of event hypothesis and sensor report nodes forming a
Bayesian belief network.

Figure \ref{fig:bnets}(a) shows the Bayes net generated by MIFD for
the very simple case of a single event hypothesized to be the cause of
a number of sensor reports.  In general sensor reports will be
ambiguous, each supporting several different event hypotheses.
Figure~\ref{fig:bnets}(b) shows a more complex example where sensor reports
might be caused by two different underlying events.
Finally, Figure~\ref{fig:bnets}(c) shows a more complex example where an event
has two component sub-events.
%% DONE: cut the following sentence because its meaning wasn't
%% clear.... I think what's meant is something like "label" rather than
%% "measurement," but I couldn't figure out how to clarify it. --- How
%% about this?
% The sensors themselves are simply either on or off, without any additional
% outputs which would distinguish hypotheses.

\ids rules detect indirect features of intrusions, but they typically
report only the intrusion that their designer believes has caused the feature.
This creates a number of problems, first and foremost that the
sensors have high false positive rates.
For example, a local software update server
may look like an attacker performing reconnaissance.
Worse, some false positives are correlated: the normal
activity of a print server may be mis-detected as a scan by several
different sensors.
To handle simple sensor failures, MIFD associates with each sensor a false
positive likelihood.
But to address the correlated false positives such as the scanning example, we
introduce benign events, that can compete with attack and (simple) false
positive explanations for results.\footnote{Where possible, we try to introduce sensors that
can specifically detect the benign events. 
%% TODO Restore for QR'15
%To return to our earlier example, we
%might introduce a ``print server sensor'' to help disambiguate detections. We do
%not address this issue in our experiments.
}

Another problem with indirect sensing is that the sensors are often imprecise:
the features that they detect often occur not only in the absence of the
advertised intrusion, but in the presence of \emph{other} intrusions with
similar characteristics.

%% TODO Restore for QR'15 --- we'd earlier discussed
%% removing this paragraph anyway.
%MIFD also has \emph{complex} events that have component sub-events, such as a
%phishing attack with component events phishing email and drive-by-download.
%Our current experiments do not address the role of complex events, so we will
%not discuss them further.

\begin{figure}
  \centering
  \begin{tabular}{c@{\hspace{3mm}}c@{\hspace{3mm}}c}
  \includegraphics[width=.2\columnwidth]{figures/bnets1-cropped.pdf} &
  \includegraphics[width=.267\columnwidth]{figures/bnets2-cropped.pdf} &
  \includegraphics[width=.4\columnwidth]{figures/bnets3-cropped.pdf} 
  \\ (a) & (b) & (c)\\
  \end{tabular}
  \caption{Bayes networks generated by MIFD.}
  \label{fig:bnets}
  
\end{figure}

The second inference step is \textbf{Assessment,} in which MIFD assigns a degree of belief
to each of the event hypotheses.
MIFD does this by performing Bayesian updating on the belief network constructed
by the clustering process. 
%% As we discuss below, MIFD does this using the \zplus qualitative probability
%% scheme rather than standard probability theory.
%%

Note that Scyllarus and MIFD are intended as long-running online services, not batch processes.
Scyllarus has run for months at a time.
One major requirement for such long-term operation is that the
inference steps must be performed cyclically.  MIFD repeatedly reads
reports and clusters them, periodically interrupting that
cycle to perform assessment.
Scyllarus also periodically flushes older events and reports out of working
memory (they persist in a database).

%% FIXED Although this next sentence is a true fact, I'm not sure it
%% belongs here --- it makes assessment efficient, but that's not per
%% se an inherent requirement for long-term operation.
% Moreover, in general the Bayesian belief network
% is not fully connected, so for efficiency MIFD assesses each connected
% component individually.
% \footnote{%
%   An additional essential requirement for long-term operation, not
%   relevant to the remainder of this presentation, is some form of
%   garbage collection: old event hypotheses and sensor reports
%   guaranteed no longer to be relevant to subsequent report must be
%   removed from working memory.}

\input{zplus}

% Not sure that the reader cares about the data model, yet.  Maybe; maybe not.
\hide{%
\mifd\ operates under the following data model:  It receives
\emph{sensor reports} and generates \emph{event
  hypotheses}. Hypotheses include a \emph{likelihood} slot, which
\mifd\ may update as it receives additional reports, plus a list of
\emph{supporters} which may be either sensor reports or other
hypotheses. Both sensor reports and hypotheses have a list of
\emph{supports}, inverse to the \emph{supporters} relationship.
Both reports and hypotheses are associated with \emph{prototype}
objects which contain information common to all instances sharing a
prototype. In particular:
\begin{compactitem}
\item Sensor report prototypes include a slot for the (natural
  number-valued) qualitative probability of false positives for the
  report.
\item Event prototypes include a slot for the qualitative
  probability of the event occurring.
\end{compactitem}
The relationship between reports and events is modeled to \mifd\ as
\emph{hypothesis matchers}, which pair a report prototype and an event
prototype. Each instance where a particular sort of event might
trigger a particular sort of report is modeled as a separate
hypothesis matcher, so there may be several hypothesis matchers
pertaining to each sensor report prototype.  In an initializing step,
\mifd\ creates a table of hypothesis matchers indexed by sensor report
prototypes.

\mifd\ provides two operations, \emph{clustering} and
\emph{assessing}.  Clustering occurs whenever \mifd\ receives a new
sensor report.  For each of the event prototypes paired with the new
report's prototype by some hypothesis matcher,
\begin{compactitem}
\item If there are existing hypotheses with that event prototype, then
  \mifd\ adds the new report as a supporter of these hypotheses.
\item If there are no existing hypotheses with that event prototype,
  then \mifd\ creates a new hypothesis with the new report as its sole
  supporter.
\end{compactitem}

Assessment occurs whenever \mifd\ is required to produce updates to
hypothesis likelihood. Each sensor report could individually justify
possibly many events, but in assessment \mifd\ distinguishes more
likely hypothesized events from less likely ones, taking into account
all reports and the prior probabilities of hypothesized events and
report false positives.  We can first decompose this task by
considering the graph formed by the \emph{supporters} relationship on
reports and hypotheses, and consider the connected subgraphs in
turn. Moreover, we need consider only those subgraphs containing a
sensor report received since the last assessment.

To distinguish the more and less likely hypothesized events in each
connected subgraph, \mifd\ uses an assumption-based truth maintenance
system (ATMS). An ATMS is a directed, acyclic hypergraph in which
nodes represent possibly-true statements, and hyperedges from $N$
nodes to a single node represent an inference from the $N$ statements
concluding the single statement~\cite{Forbus+DeKleer:1993}. The
initial nodes of the ATMS hypergraph are called \emph{assumptions}; in
\mifd's use of ATMSs there are three forms of assumption:
\begin{compactitem}
\item ``Event $X$ did happen.''
\item ``Event $Y$ did not happen.''
\item ``Sensor report $Z$ was a false positive.''
\end{compactitem}
Corresponding pairs of the first two forms are marked in the ATMS as
\emph{nogood}.  Node representing that an event occurred can be
justified either the corresponding event assumption, or by other
events which can be generalized or collected together; nodes
representing the receipt of a sensor report can be justified either by
an event's node, or by a false positive and the negation of an event
happening.

As an ATMS's hypergraph is constructed, the ATMS algorithm maintains
the list of minimal consistent assumption sets that justify each node.
\mifd\ is interested in the most likely consistent assumption sets
satisfying the sensor report nodes, that is, those which have the
lowest total qualitative probability rank.  In principal \mifd\ could
simply add another ``goal'' node justified by the sensor report nodes,
use the ATMS algorithm to maintain its assumption sets, and find the
most likely ones. But in practice this is not a feasible approach;
finding all such consistent sets simply overwhelms the ATMS algorithm.
Instead \mifd\ performs an A* search to find the most likely unions of
assumption sets from each of the sensor node labels.

Finally, to determine the likelihood of each hypothesized event $E$,
\mifd\ looks for the presence of the assumptions that $E$ did or did
not happen in the most likely assumption sets. If only the positive
assumption occurs in these sets, then the hypothesis is deemed
\emph{likely}, the highest of the three output qualitative probability
values; if only the negative assumption occurs, then \emph{unlikely},
the lowest. If both positive and negative assumptions occur, then the
hypothesis is given a third, middle value \emph{plausible}.}

% Because the domain does not afford us access to good statistics, we do not use
% conventional Bayesian reasoning.  Instead, we use a qualitative abstraction of
% probabilistic reasoning, very similar to the big-O scheme familiar to computer
% scientists, \emph{\zplus}~\cite{Goldszmidt:92,Goldszmidt:92a,Goldszmidt:96}.


%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "main"
%%% End: