5.6. Borrowing from Well-Established Fields

When considering the derivation of solutions to survivability problems we will subscribe to the notion of optimality. In an attempt to find solutions and increase rigor in certain critical cyber problem domains, we will investigate transformations of security and survivability problems to other well-established disciplines, utilizing their mathematical models.

Using problem transformation in order to solve hard problems is not a new strategy; it has been used extensively in mathematics and engineering. Well-known examples include exponentiation or Laplace transformation. The general strategy is to transform the original problem into a different problem space in which known solutions exist, or solutions can be found at lesser cost. After a solution has been derived in the new problem space, a reverse transformation is used to translate the solution found back to the original problem space.

The general interest in transformation is two-fold. First, we are interested in practical solutions to the original survivability problem. This includes potential algorithms and heuristics. Second, we want to use the transformation domain as a source for information that helps us understand the time and space complexity of the original problem. This will give us valuable information about computational feasibility and scalability. Furthermore, it can potentially be the basis for comparing different solutions to the original problem in the transformation domain.

5.6.1. Problem Transformation

Many survivability applications can be addressed by utilizing the five-stage transformation model introduced by Krings [41]. The basic philosophy of the model, shown in Figure 5.2, will be explained using a simple example of a networked computer system (e.g., a cluster of workstations or a grid). The transformation domain will be assumed to be that of scheduling theory. Any other suitable domain could be used as well, for example, graph theory, game theory, Markov models, Monte Carlo approaches, or economic modeling.

Application

Let us assume that the application is a general networked computer system. One can envision the system as a collection of workstations connected via local area networks (LANs) and wide area networks (WANs), consisting of typical components like switches, routers, bridges, or gateways. The components themselves are connected via diverse technologies and protocols.

Model Generation

The application is transformed into a task graph together with the task model specification, if applicable. Given the infrastructure graph of the system in our example, the graph view comes natural. Thus, the general model is based on a directed graph G = (V, E), where V is a finite set of vertices v_i, and E is a set of edges e_ij, i ≠ j, representing precedence relations between v_i and v_j in V. In our example, vertices are the workstations and network components like routers or bridges. The edges are the interconnections.

Parameterization

Now that the application is mapped to vertices and edges of G, a mapping of application specific parameters to generic parameters is needed. Examples of parameters for vertices are computational power of workstations, and those for network components and connections are quality of service (QoS) parameters such as network throughput, propagation delay, communication cost, or priority. The vertices and/or edges of the graph need to be assigned weights representing their characteristics. The results can be generalized by integer or real valued weights. Thus, for each vertex in V and edge in E, vertex and edge weights are defined respectively. Let denote the vertex weight of vertex v_i and denote the weight of edge e_ij.

Model Abstraction and Representation

The weighted graph G can now be considered in the context of a problem in the target domain (e.g., a graph or scheduling problem). For example, a graph theoretical formulation could follow directly from G together with a suitable manipulative objective (e.g., finding the least-cost path between two vertices). Similarly, a scheduling theoretical formulation would imply the specification of a suitable scheduling model S, specifying the task and processing environment as well as the optimization criteria.

Algorithmic Solutions

Assume that we consider a transformation to scheduling theoretical formulations. The scheduling model S is now subjected to scheduling algorithms. The goal is to find optimal or suboptimal solutions for the specific survivability criteria, applying the best suitable algorithm(s). A wealth of algorithms and heuristics of varying space and time complexity exist. Appropriate algorithms need to be identified that suit the optimization criteria. In addition, useful information about the time or space complexity may be inherited from the algorithms. This may provide valuable information about the solution space. After the application of the scheduling algorithms or heuristics, optimal or suboptimal solutions will be available. It should be pointed out that the focus of this discussion is not on scheduling algorithms, but on the identification of an appropriate scheduling model. Once the model is specified, a literature review for potential algorithms is required. However, given the semi-standardized formulations of scheduling models, this process can be very efficient. Of course, one can hand the problem over to experts in the transformation field. But, given the elegance of the formulations of scheduling problems, which are outlined below, one does not necessarily have to be a scheduling theorist to find the problems in the literature.

Reverse Transformation

The solutions of the graph or scheduling algorithms must now be translated back to the application. This requires a reverse transformation analogous to the transformation used in the model generation section above. This step represents the transformation from the solution space back to the application space.

Before giving some examples of how the transformation model can be used to solve security or survivability problems, some basic explanations of our transformation domain, in this case scheduling theory, are needed.

5.6.2. Scheduling Problems

The key to the model transformation is to understand how to derive an appropriate transformation. Our target domain is scheduling (i.e., a scheduling model S) and its interpretation in the context of the specific survivability application. This burden cannot be taken over by a scheduling expert, unless he or she has insight into security or survivability research. In order to avoid lengthy descriptions of scheduling models S, a compact classification description of the form S = (α|β|γ) is widely used in the literature [42–44]. The fields α, β, and γ indicate the processor environment, the task and resource characteristics, and the optimization criteria, respectively. Each field will be briefly introduced next, together with some standard notation indicated in parenthesis.

The first field of S (i.e., α) specifies the assumptions placed on the processor environment. There are many different attributes associated with processors. For example, processors may be identical, uniform, unrelated, or dedicated. Identical processors (P) refer to a homogeneous processor environment. Uniform processors (Q) assume different speeds b_i for each processor. In scheduling, uniformity implies that processor speeds differ but the processor’s speed is constant over time (i.e., it does not depend on the task it executes). If the speed is dependent on the task performed, processors are called unrelated. In the transformation model, unrelated processors, denoted by (R), can be a convenient model to describe computers subjected to denial of service (DoS) attacks, which may be distributed denial of service (DDoS). Lastly, some problems require dedicated processors that are assumed to be specialized for the execution of certain tasks. Other applications execute tasks in stages at different processors or clusters. In scheduling theory, such problems are described in open shop, flow shop, and job shop systems.

The second field of S (i.e., β) specifies the task and resource characteristics. Tasks may be nonpreemptive (Φ) or preemptive (pmtn). Once a nonpreemptive task is started, its execution can not be interrupted. If preemption is allowed, task execution can be interrupted. If the tasks are subjected to precedence constraints, the specific constraints are indicated, for example, (Φ) indicates independent tasks and (chain) indicates task chains.

The last field of S (i.e., γ) indicates the optimization criteria. Optimization is often defined based on task completion times, flow times, lateness, tardiness, or earliness. The completion time C_j of the last task T_j of the schedule is called the makespan. Thus, the makespan indicates the overall length of the schedule. Makespan optimization is denoted by (C_max). Another interesting criterion is the flow time F_j, which is the sum of the waiting time and processing time of a task, and optimization of average flow time or weighted flow time is denoted by (ΣF_j) and (Σw_jF_j), respectively. Other optimization criteria include minimization of lateness L_j = C_j – d_j (i.e., the completion time minus the task’s deadline); tardiness D_j = max{C_j – d_j, 0}, which considers only the contribution of late tasks; or earliness E_j = max{d_j – C_j, 0}.

Many security or survivability problems can be mapped to scheduling problems. One key observation is that security personnel or mechanisms can be viewed as the processor environment. There are many ways to map the security problem examples described below to a scheduling problem S = (α|β|γ). The formulations shown are only examples. Especially in the task and resource characteristics (i.e., β), many interpretations and formulations are possible. This vagueness should be seen as a strength, not a weakness, as it introduces flexibility in generating a solution space.

5.6.3. Case Study: Autonomous Mobile Agents

When an application executes code that it receives from the outside, then the obvious question is how does one know that the code has not been corrupted or is hostile? For example, executing an executable file attached to an email is like taking a leap of faith, as it constitutes a significant risk (e.g., a virus may be part of the code). We will use migratory mobile agents as an example of traversing code that may be subject to attacks or may attack itself. There are no points made about pros or cons of agent-based systems, but every security researcher will agree that this paradigm, by its very nature, constitutes real security challenges.

In order to address security concerns and system survivability, let us suggest that the agent systems use redundancy with a specific focus on secret sharing [32, 46] rather then pure spatial or information redundancy [47–50]. In secret sharing, the information is divided into k shares and one has to have all shares to use the information. If each agent carries a single share, secret sharing using k shares can be extended to achieve survivability by adopting an m-of-k scheme, in which the information of m out of k uncorrupted agents is needed to perform an action [46]. We now apply the transformation process described above.

Assume we want to investigate the feasibility or wisdom of using a multi-agent system to implement critical functionalities on a set of networked computer systems. The relative importance of each computer of the system is prioritized (e.g., indicated by an indexed priority scheme). Next, assume that a secret sharing scheme is implemented requiring k_i shares for a specific processing element (i.e., the computer PE_i). Thus, all k_i agents must be present at computer PE_i to perform their specific function. Given this secret sharing agent scheme, it is important to find efficient agent traversal paths, for example, paths that maximize the efficiency of agents assembling at computers to perform the intended task, such as response to malicious acts. In other words, how does one direct the individual agents, carrying their shares, to congregate at different computers efficiently?

The application is translated into a task graph G = (V, E) consisting of K job chains C_k each representing a group of computers. Each computer to be traversed by the agents is shown as a vertex (i.e., job J_k,i ϵ C_k, for 1 ≤ k ≤ K). The position of J_k,i in C_k (i.e., the chain position) indicates the relative computer priority.

The parameters reflecting the functionality executed by the agents during job J_k,i need to be specified. The job priorities are implicitly defined by the position of J_k,i in chain C_k, and the processing and release times of J_k,i are determined by p_k,i and r_k,i, respectively. Potential cost or liabilities due to malicious acts can be modeled by weight w_k,i.

Suitable scheduling models for this description can be found in Dror et al. [51], where “Strong”—“Weak” chain constrained scheduling is discussed. The specific model considered is:

Pm|fix_j, chain, p_j = 1|C_max

where m is the number of machines (represented by agents) in the system. The number of machines necessary to process a job is indicated by fix_j and chain indicating chain precedence. It should be noted that fix_j indicates the degree of secret sharing. To show how this model suits the application an example from Dror et al. [51] is given. Let J denote a partition of all jobs J_k,j. Furthermore, let J^expr denote the set of jobs that require all machines with indices indicated in expr for execution. Now jobs can be partitioned by their resource requirements. If one assumes m = 3, then jobs can be partitioned as:

Equation 5.1

The superscripts indicate the machines required, for example, J¹²³ comprises all jobs that need machines M1, M2, and M3 to execute, whereas jobs in J¹² only require M1 and M2. The number of indices listed in the superscripts indicates the degree of secret sharing required by each of the jobs of the associated set. For example, each job in J¹²³ requires that in the application domain three agents be present before their respective functionality can be executed. Similarly, each job in J¹², J¹³, and J²³ requires two agents; however, each set has its specific set of associated agents. The problem

P3|fix_j, chain, p_j = 1|C_max

captures the notion of scheduling the tasks in J.

It is shown in Dror et al. [51] that the problem Pm|fix_j, weakchain, p_j = 1|C_max can be solved in O(n) time if all jobs of chain k belong to the same partition in Eq. 5.1. The last constraint is called agreeable machine configuration. The weak chain constrained implies that scheduling two jobs of a chain, under consideration of the chain precedence constraint, may be interleaved with other jobs. This interleaving is not allowed in strong chain constrained scheduling. The problem Pm|fix_j, strong chain, p_j = 1|C_max, for m> 1 has been shown to be NP-hard in the strong sense [46]. Similarly, problem P3|fix_j, strongchain, p_j = 1|C_max with agreeable machine configuration is NP-hard in the strong sense [52, 53].

The reverse transformation is quite trivial. A valid schedule produced by any scheduling algorithm directly reflects the agent traversal path.

In conclusion to this example, we want to point out that the point made in this discussion on problem transformation is not to insist on using a specific approach to solve a problem, but to identify a methodology that allows us to analyze and perhaps derive direct solutions from other fields, thereby taking advantage of all benefits inherited by using their mathematical models. This may allow us to analyze the space and time complexity, shedding light on scalability and even feasibility. The previous example is not trivial, but neither is the survivability application. Understanding the scheduling model exposes the inherited limitations or expense of using secret sharing in such an application. However, given the application domain (i.e., migratory agents), the security challenges may leave little choice if one wants to guarantee survivability.