JOÃO P. HESPANHA
OBJECTIVES
We will develop algorithms and technologies to endow a distributed information system
with the capability of (i) detecting failures of its components or attacks to its
integrity; and (ii) responding to these failures or attacks to minimize their damage to
the overall system. The algorithms developed will use proven tools from Nonlinear Adaptive
Control and Supervisory Control. These algorithms will be independent of current hardware,
communication protocols, and application software; and, therefore, applicable to any
information system that may appear in the next 10-20 years. We will focus on the
protection of small to medium-size communication networks that support information
systems. This work will be validated in the context of current network protocols.
INTRODUCTION
In technological fields that are evolving as rapidly as information systems it is crucial
to develop algorithms and tools whose applicability is not restricted to a particular
piece of hardware, communication protocol, or software application, that may become
obsolete in a few years. We will therefore focus our work on technologies that are
hardware/software independent. This requires one to abstract information systems to the
essential entities that define them: the data, the sources and receivers of information,
the processing nodes, and the transmission links.
The network that supports an information system is composed of basic processing
units-called nodes-that are physically connected by transmission links. Nodes are
responsible for (i) converting the data produced by the information sources into
units-called packets-that the transmission links are able to carry, (ii) reconstructing
the original data from the packets and feeding it to the receivers, and (iii) routing
packets inside the network. A maximum bit-rate capacity is always associated with each
transmission link.
The previous paragraphs describe the fundamental elements that constitute a distributed
information system. The algorithms and technologies developed under this contract will
apply to any information system that fits under this very general framework and therefore
will continue to be useful, at least, for the next 10-20 years.
A physical connection should be understood in a broad sense that encompasses a wire, an optical cable connection, and RF link, etc.
For the purposes of developing IA systems one must assume that a sophisticated enemy
may corrupt any of the elements forming the supporting communication network. For example:
a node's routing algorithms may be tampered with, the packets that flows through a nodes
may be monitored or tampered with, nodes can be overflowed with traffic (an attack also
known as denial-of-service), the links can be severed, false nodes can be inserted into a
severed link, etc.
The challenge for information assurance is precisely to build a reliable information
system supported by a network whose components are potentially unreliable and can be taken
over by a sophisticated enemy. Under this task, we will develop technologies capable of
(i) detecting failures or attacks to the information system, and (ii) autonomously
responding to these failures or attacks to minimize their damage to the system. We will
focus on specialized automated, high-speed attacks.
The most common defenses in today's information systems are firewalls, access control
lists, and data encryption [28,29]. Firewalls and access control lists limit the access of
shared resources to certain systems or users that have been authenticated through some
clearance mechanism. Firewalls typically operate at the level of the communication
protocol and filter the network traffic to prevent unauthorized users to access specific
resources "behind" the firewall. Firewalls usually authenticate users simply by
their network address. Defense mechanisms based on access control lists typically operate
at the operating system or application level and refuse service to unauthorized users.
Because they operate at a higher level in the information system's hierarchy, access
control lists allow for more sophisticated authentication mechanisms, typically relying on
secret passwords. The paradigm behind data encryption is that any user can access the raw
data that flows in the communication network that support the information system, but only
those that hold the correct decryption key can decode this data into useful information.
Often systems using data encryption rely on the use of public encryption keys that are
distinct from private decryption keys. The encryption key can then be broadcast through a
non-secure network, whereas the decryption key is always kept at location assumed secure.
A common feature to the defense mechanisms described above is their static nature and
consequent inability to adapt when under attack. This is because, in general, the policies
that define which traffic can go through a firewall, or which users/systems are allowed to
access a certain resource are defined by human operators and do not change as a response
to perceived threats. Unfortunately, in order for static defenses to achieve high levels
of security they often end up restricting heavily the services provided by the system. For
example, in order for the local network of a company to be immune to attacks by denial of
service (i.e., when outside computer(s) direct large amounts of packets to the network to
produce an extreme degradation of performance), it must setup severe restrictions on the
traffic that can flow into its local network. These will also prevent legitimate users
from remotely accessing the company's computer resources.
Under this proposal, we seek to develop defense mechanisms that do not suffer from the
shortcomings described above. Such mechanisms must be able to monitor the network, detect
potential attacks or component failures, and adapt the existing defenses to deal with the
perceived threat. These algorithms must operate in machine-time to minimize the damage due
to high-speed automated attacks. To achieve this we will borrow techniques from Nonlinear
Adaptive Control [11] and Multiple-Model Supervisory Control [12,13].
The successful completion of this task requires (i) the selection of suitable models for
communication networks, (ii) the design of multiple-model estimation techniques for
information systems, and (iii) the development of actuation systems for IA.
TECHNICAL APPROACH
Most IA defense mechanisms in use are static and incapable of adapting when under attack.
Under this task, we seek to develop defense mechanisms that do not suffer from this
shortcoming, by using tools from Nonlinear Adaptive Control [11] and Multiple-Model
Supervisory Control [12,13].
Both Adaptive and Supervisory Control are inspired on the Certainty
Equivalence Principal. In this context, certainty equivalence advocates that,
at each instant of time, one should design the feedback control to an imprecisely modeled
process based on the current estimate of what the process is, with the understanding that
such estimate is to be viewed as correct even though it may not be. Adaptive and
Supervisory Control differ in that the former updates the process estimate in a continuous
fashion whereas the latter switches among a (possibly infinitely large) pool of multiple
candidate models. With the discovery that architectures based on certainty equivalent
render closed-loop feedback control systems detectable through the estimation errors
[25,36] and the recent advances the analysis of switching logics [37] it became possible
to apply Supervisory Control to very general classes of problems ranging from disturbance
rejection to the control of strongly nonlinear nonholonomic systems [38,39,40]. It is our
goal to further extend these techniques to IA problems.
Much like the multiple-model paradigm of Supervisory Control, IA systems go through
several distinct modes of operation in an unpredictable fashion. E.g., a system may start
in what could be called normal operation, then be subject to a high traffic condition, and
later on suffer a malicious attack. It is therefore necessary to build several basic
candidate control modules, each designed for a specific mode of operation or type of
attack. In practice, each of these controllers corresponds to a particular set of
parameters for routing tables, firewalls, access control lists, etc. The Supervisory
Control problem consists then in orchestrating the switching between the candidate
controllers so as to protect the IA system from attacks or component faults and,
simultaneously, to give legitimate users large flexibility under normal mode of operation.
Through a simple example, we proceed by demonstrating how a typical IA problem can be cast in the framework of Multiple-Model Supervisory Control.
Multiple-Model Detection and Control of Denial of Service Attacks
Consider the six-node communication network represented by the graph in Figure 1.
Figure 1: Graph representation of a communications network.
In this figure the nodes are numbered from 1 through 6 and each edge in the graph
corresponds to a bi-directional communication link between the corresponding nodes. The
problem we want to address here is the detection and control of a Denial of Service (DS)
attack to this network. In this type of attack, data packets are introduced into the
network in large quantities to cause an extreme degradation of performance that will
effectively freeze all communication. In what follows, we assume a DS attack to the
network will be attempted through node 4. However, the IA defenses do not know this in
advance.
Static firewalls are typically used to defend systems against DS attacks by isolating
portions of the network considered critical. However, this type of defense restricts
communications severely and, perhaps even more importantly, will fail against attacks from
inside the firewall. In our example, we assume that all six nodes are part of a critical
enclave of the network and solutions involving static firewalls between these nodes are
unacceptable under normal mode of operation.
To build intelligent, adaptive defenses one needs to (i) detect if an attack is taking
place and (ii) determine which node or link is responsible for the attack. In general,
these tasks will have to be performed by one (or a few) nodes in the network in a
decentralized fashion and it is therefore not reasonable to assume that full information
about the state of the network is available for the IA defenses.
In what follows, we assume that node 1 is responsible for defending the networks against DS attacks and, to achieve its task, it can only monitor the traffic in the links connected to it.
We shall consider a simple model for the traffic in this network. Let us denote by x a
vector consisting of the amount of traffic (e.g., measured in data packets by second) in
each unidirectional transmission link. Since we have ten bi-directional links, x Î Ñ20.
For simplicity, we assume the following linear stochastic model for the evolution of x
under normal operation:
x( k + 1) = A x( k ) + B n, k e {0, 1, 2, … }, (1)
where n denotes a stationary random process that represents traffic injected into the network by information sources. The matrix A effectively models the topology of the network and typical traffic flows. In particular, the entry of A in the ith row and jth column encodes how much traffic from the jth link is routed to the ith link. Figure 2(a) shows a graphical representation of a typical matrix A for the network represented in Figure 1. The matrix B in (1) encodes the connectivity between legitimate information sources and the links. Here we took B to be the identity matrix, which corresponds to one source of information per link.
(a) |
(b) |
Figure 2: (a) Matrix A in models (1) and (2). (b) Matrices in model
(3).
Both in (a) and (b), light stands for a zero (or small) entry whereas dark for a nonzero
one.
A DS attack can be viewed as an extra input to our traffic model. In fact, a system under attack can be modeled by
x( k + 1) = A x( k ) + B n + d, k e{0, 1, 2, … }. (2)
where d represents traffic being injected to disrupt the system. In practice one does not know where and how much traffic is being injected; therefore, d can take one of several possible values from a "pool" of potential attacks A. For the network in Figure 1, one has six types of basic attacks, each one corresponding the injection of traffic on a specific node. Since every type of attack will be of an "unknown" intensity, the "pool" of basic attacks would be of the form
A := { ldi : l > 0, i = 1, 2, ...., 6 } (3)
where di models the injection of traffic in node i and l represents the intensity of the attack. Figure 2(b) shows graphical representations of typical di.
Suppose now that an attack to the network is attempted through node 4. Figure 3 shows a simulation of the traffic in the network links corresponding to such an attack taking place at time 25. The top plot displays the traffic that can be monitored by node 1 and the lower one the traffic that this node cannot observe directly. When the attack takes place an increase of traffic is observed all over the network. This increase is specially noticable in the links coming out of node 4 (lower plot in Figure 3), however node 1 cannot observe these links. In fact, the increase in traffic in the links connected to node 1 is essentially uniform and therefore it is not clear where the attack is coming from.
 Figure 3: Simulated traffick corresponding to a DS attack at time 25, through node 4. |
 Figure 4: Attack detection and identification using state-shared multi-estimators. |
One can then pose the question: Can node 1 determine if an attack is taking place by monitoring the traffic that flows through the links connected to it? And if so, Can node 1 identify which node is responsible for the increase in traffic? For the model above, the answer to both these questions is yes. In fact, state-shared multi-estimators from Supervisory Control [41,39] can be used to efficiently estimate which attack is taking place, i.e., which element of A explains the data being observed. Due to stochastic nature of (2), this answer always carry some probability of error that decreases to zero as the time interval over which the observation takes place grows to infinity. Figure 4 shows the result of attack detection and identification using state-shared multi-estimators similar to those developed for Supervisory Control. The top plot shows an exponentially-weighted norm of the identification error for each attacking node. Soon after the attack has started, the identification error associated with node 4 becomes significantly lower than the rest clearly indicating that this node is responsible for the increase in traffic. The lower plot shows the estimate of the traffic injected by node 4.
Although simple, this example clearly shows the potential of multiple-model estimation for the design of IA defenses. Under this proposal we will develop the technologies and tools required to transition from simple examples like the one above to operational Autonomical Information Assurance.
REFERENCES
