Information Technology Reference
In-Depth Information
Rule-Based Topological Vulnerability Analysis
Vipin Swarup
1
, Sushil Jajodia
2
, and Joseph Pamula
2
1
The MITRE Corporation, 7515 Colshire Drive, McLean, VA 22102
2
Center for Secure Information Systems, George Mason University,
Fairfax, VA 22030-4444
{
jajodia, jpamula
}
@gmu.edu
swarup@mitre.org
Abstract.
Attack graphs represent known attack sequences that attack-
ers can use to penetrate computer networks. Recently, many researchers
have proposed techniques for automatically generating attack graphs for
a given computer network. These techniques either use model checkers
to generate attack graphs and suffer from scalability problems, or they
are based on an assumption of monotonicity and are unable to represent
real-world situations.
In this paper, we present a vulnerability analysis technique that is
more scalable than model-checker-based solutions and more expressive
than monotonicity-based solutions. We represent individual attacks as
the transition rules of a rule-based system. We define noninterfering rule-
sets and present ecient, scalable algorithms for those sets. We then con-
sider arbitrary nonmonotonic rulesets and present a series of optimiza-
tions which permit us to perform vulnerability assessment eciently in
most practical cases. We motivate the issues and illustrate our techniques
using a substantial example.
1
Introduction
An attacker typically penetrates a computer network by probing and modify-
ing the network configuration and by exploiting vulnerabilities. For instance,
an attacker might execute a sequence of actions that first probe a network for
vulnerable systems, then exploit a detected vulnerability to gain user-level priv-
ileges on a remote host, then exploit another vulnerability to gain root-level
privileges, and finally use the privileges to compromise the system. As another
example, consider a network with firewall rules that prevent external packets
from reaching a critical server directly. An attacker might launch an attack on
port 80 of some internal machine (thus bypassing the firewall) and then use that
intermediate host to attack the critical server.
The work of Pamula and Jajodia was partially supported by the National Science
Foundation under grants IIS-0430402 and IIS-0242237, Air Force Research Labora-
tory, Rome under the grant F30602-00-2-0512, and the Army Research Oce under
the grant DAAD19-03-1-0257.
V. Gorodetsky, I. Kotenko, and V. Skormin (Eds.): MMM-ACNS 2005, LNCS 3685, pp. 23-37, 2005.
c
