The CERT/CC research team's survivability research has lead to the development and study of a class of emergent algorithms that can achieve non-functional global properties such as survivability in highly distributed systems even if those properties do not or cannot exist within individual nodes (see "Emergent Algorithms for Survivable Systems" in these proceedings). For analysis, testing and evaluation both of survivability in unbounded networks and of emergent algorithms for survivability systems, simulation is needed. This has lead to seeking a simulation language appropriate for research in survivability systems.

An extended search identified no existing simulation or conventional language that meets the needs of analysis of survivability algorithms. These specific needs arise from a desire to use detailed models of unbounded networks under realistic revisions (both from evolution and attack) to analyze and evaluate survivability algorithms. Setup of the evaluation requires the capability to express a network in terms of protocols and unbounded numbers of independently-programmed nodes. This expression requires visibility and control capabilities consistent with those of nodes of a modern network. The analysis requires analyst-defined visualization of the operation of the algorithm and the state of the network. This visualization must be global enough to capture the essential semantics of the emergent algorithms and to provide meaningful instrumentation. Configuration of analysis conditions requires modeling credible attack scenarios and arbitrary sequences of network revisions. Limitations of existing languages, led the authors to develop a new simulation environment that meets these needs of survivability research.

The environment bases its semantics on three types of entities. Processes model local activities of a network node or system component in a multithreaded execution, supporting inherent characteristics of distributed network behavior such as restrictions on global visibility and central control. Observers provide the visualization or observation of the algorithm as a whole, serving as instrumentation or data-gathering mechanisms. Facilitators modify the network, for both desirable and undesirable purposes. Each of these entities can model either human or automated agents. Entity behavior is described using in a special-purpose simulation language with modern procedural semantics, and may be either pre-programmed or entered interactively.

Processes are instantiated as simulated nodes. Nodes only have access to their own local state and designated fields of neighbor nodes, together with multiported communication links between themselves and other nodes. Specifically, nodes and their associated processes have no global visibility or central control in the simulation, although the language allows any Boolean predicate as a definition of a "neighbor node". Each node also has its own independent simulated clock. Nodes interact across their links using user-defined protocols, with some commonly-used protocols provided as defaults. The communication primitives include send and receive operations, with modeled delays given by the link bandwidth and amount of ongoing communication. The send and receive operations process messages of any type (including executable code) and designated size, with a time-out to model link overload or communication failure. Nodes can create, communicate, and execute programs.

Observers are a generalization of processes, relaxing the restriction against global visibility. Observers may interact directly with the user to present views on the simulation, or may operate noninteractively to provide data gathering for analysis. Observers may reference the local state of any node, monitor actions on any communication link, monitor scheduling, and monitor the position or depiction of any node. These capabilities allow capture of selective portions of the global network state for semantics supporting meaningful instrumentation of the survivability algorithm.

Facilitators are a generalization of observers, relaxing the restriction against central control and assignment to private variables of any individual node. Facilitators may modify the local state of any node or alter the scheduling in the simulation. In general, facilitators support programmed or user-specified changes to the network or the simulation.

All entities may have a programmed location and graphical depiction. The simulation user interface provides interaction with entities and observation via mobile, scaleable and panable windows on the simulated world. The environment supports type-safe persistent storage of simulation results, program fragments and execution states.

Together, the features of the simulator provide a flexible tool for the expression, evaluation and analysis of survivability algorithms in unbounded networks. The simulator provides an entirely interpretive uniprocessor-based implementation of the simulation language, to facilitate user interaction with the algorithms and their run-state. The simulator is written in a portable fashion, with implementations running on both PC and Macintosh computers. The simulator provides new capabilities supporting the CERT/CC research team's ongoing work on emergent algorithm development and survivability architecture assessment.

¹

Prof. Shimeall's participation in this effort is supported by funds administered by the Naval Postgraduate School Research Council. This work was performed on sabbatical with the CERT/CC Research Team.

^SM

CERT is registered in the U.S. Patent and Trademark Office

Back to the Table of Contents
   [31]