Assessing a network's vulnerability to attack and random failure is a difficult and important problem that changes with network application and representation. We furnish algorithms that bound the robustness of a network under attack. We utilize both static graph-based and dynamic trace-driven representations to construct solutions appropriate for different scenarios. For static graphs we first introduce a spectral technique for developing a lower bound on the number of connected pairs of vertices in a graph after edge removal, which we apply to random graphs and the power grid of the Philippines. To address the problem of resource availability in networks we develop a second technique for bounding the number of nominally designated client vertices that can be disconnected from all server vertices after either edge or vertex removal (or both). This algorithm is also tested on the power grid and a wireless mesh network, the Internet AS level graph, and the highway systems of Iowa and Michigan. Dynamic networks are modeled as disruption tolerant networks (DTNs). DTNs are composed of mobile nodes that are intermittently connected via short-range wireless radios. In the context of both human and vehicular mobility networks we study both the effect of targeted node removal and the effect of augmentation with stationary relays.

In this paper, we concentrate on computing several critical budgets for interdiction of the multicommodity network flows, and studying the interdiction effects of the changes on budget. More specifically, we first propose general interdiction models of the multicommodity flow problem, with consideration of both node and arc removals and decrease of their capacities. Then, to perform the vulnerability analysis of networks, we define the function F(R) as the minimum amount of unsatisfied demands in the resulted network after worst-case interdiction with budget R. Specifically, we study the properties of function F(R), and find the critical budget values, such as , the largest value under which all demands can still be satisfied in the resulted network even under the worst-case interdiction, and , the least value under which the worst-case interdiction can make none of the demands be satisfied. We prove that the critical budget for completely destroying the network is not related to arc or node capacities, and supply or demand amounts, but it is related to the network topology, the sets of source and destination nodes, and interdiction costs on each node and arc. We also observe that the critical budget is related to all of these parameters of the network. Additionally, we present formulations to estimate both and . For the effects of budget increasing, we present the conditions under which there would be extra capabilities to interdict more arcs or nodes with increased budget, and also under which the increased budget has no effects for the interdictor. To verify these results and conclusions, numerical experiments on 12 networks with different numbers of commodities are performed.

<p>This thesis explores a few geometric optimization problems that arise</p><p>in robotics and sensor networks. In particular we present efficient</p><p>algorithms for the hitting-set problem and the budgeted hitting-set problem.</p><p>Given a set of objects and a collection of subsets of the objects,</p><p>called ranges, the hitting-set problem asks for a minimum number of </p><p>objects that intersect all the subsets in the collection.</p><p>In geometric settings, objects are </p><p>typically a set of points and ranges are defined by a set of geometric</p><p>regions (e.g., disks or polygons), i.e., the subset of points lying in each </p><p>region forms a range.</p><p>The first result of this thesis is an efficient algorithm for an instance</p><p>of the hitting-set problem in which both the set of points and the set</p><p>of ranges are implicitly defined. Namely, we are given a convex</p><p>polygonal robot and a set of convex polygonal obstacles, and we wish</p><p>to find a small number of congruent copies of the robot that intersect</p><p>all the obstacles.</p><p>Next, motivated by the application of sensor placement in sensor networks,</p><p>we study the so-called ``art-gallery'' problem. Given a polygonal</p><p>environment, we wish to place the minimum number of guards so that</p><p>the every point in the environment is visible from at least one guard.</p><p>This problem can be formulated as a hitting-set problem. We present</p><p>a sampling based algorithm for this problem and study various extensions</p><p>of this problem.</p><p>Next, we study the geometric hitting-set problem in a dynamic setting,</p><p>where the objects and/or the ranges change with time and the goal is</p><p>to maintain a hitting set. We present algorithms </p><p>which maintain a small size hitting set with sub-linear update time.</p><p>Finally, we consider the budgeted hitting-set problem, in which we</p><p>are asked to choose a bounded number of objects that intersect as many</p><p>ranges as possible. Motivated by applications in network vulnerability</p><p>analysis we study this problem in a probabilistic setting.</p> / Dissertation

Transport networks have to provide carriers with time-efficient alternative routes in case of disruptions. It is, therefore, essential for transport network planners and operators to identify sections within the network which, if broken, have a considerable negative impact on the networks performance. Research on transport network analysis provides lots of different approaches and models in order to identify such critical sections. Most of them, however, are only applicable to mono-modal transport networks and calculate indices which represent the criticality of sections by using aggregated data. The model presented, in contrast, focuses on the analysis of intermodal transport networks by using a traffic micro simulation. Based on available, real-life data, our approach models a transport network as well as its actual traffic participants and their individual decisions in case of a disruption. The resulting transport delay time due to a specific disruption helps to identify critical sections and critical networks, as a whole. Therefore, the results are a valuable decision support for transport network planners and operators in order to make the infrastructure less vulnerable, more attractive for carriers and thus more economically sustainable. In order to show the applicability of the model we analyse the Austrian intermodal transport network and show how critical sections can be evaluated by this approach. (authors' abstract)

It is widely accepted that modern computer networks (often presented as a heterogeneous collection of functioning organisations, applications, software, and hardware) contain vulnerabilities. This research proposes a new methodology to compute a dynamic severity cost for each state. Here a state refers to the behaviour of a system during an attack; an example of a state is where an attacker could influence the information on an application to alter the credentials. This is performed by utilising a modified variant of the Common Vulnerability Scoring System (CVSS), referred to as a Dynamic Vulnerability Scoring System (DVSS). This calculates scores of intrinsic, time-based, and ecological metrics by combining related sub-scores and modelling the problem’s parameters into a mathematical framework to develop a unique severity cost. The individual static nature of CVSS affects the scoring value, so the author has adapted a novel model to produce a DVSS metric that is more precise and efficient. In this approach, different parameters are used to compute the final scores determined from a number of parameters including network architecture, device setting, and the impact of vulnerability interactions. An attack graph (AG) is a security model representing the chains of vulnerability exploits in a network. A number of researchers have acknowledged the attack graph visual complexity and a lack of in-depth understanding. Current attack graph tools are constrained to only limited attributes or even rely on hand-generated input. The automatic formation of vulnerability information has been troublesome and vulnerability descriptions are frequently created by hand, or based on limited data. The network architectures and configurations along with the interactions between the individual vulnerabilities are considered in the method of computing the Cost using the DVSS and a dynamic cost-centric framework. A new methodology was built up to present an attack graph with a dynamic cost metric based on DVSS and also a novel methodology to estimate and represent the cost-centric approach for each host’ states was followed out. A framework is carried out on a test network, using the Nessus scanner to detect known vulnerabilities, implement these results and to build and represent the dynamic cost centric attack graph using ranking algorithms (in a standardised fashion to Mehta et al. 2006 and Kijsanayothin, 2010). However, instead of using vulnerabilities for each host, a CostRank Markov Model has developed utilising a novel cost-centric approach, thereby reducing the complexity in the attack graph and reducing the problem of visibility. An analogous parallel algorithm is developed to implement CostRank. The reason for developing a parallel CostRank Algorithm is to expedite the states ranking calculations for the increasing number of hosts and/or vulnerabilities. In the same way, the author intends to secure large scale networks that require fast and reliable computing to calculate the ranking of enormous graphs with thousands of vertices (states) and millions of arcs (representing an action to move from one state to another). In this proposed approach, the focus on a parallel CostRank computational architecture to appraise the enhancement in CostRank calculations and scalability of of the algorithm. In particular, a partitioning of input data, graph files and ranking vectors with a load balancing technique can enhance the performance and scalability of CostRank computations in parallel. A practical model of analogous CostRank parallel calculation is undertaken, resulting in a substantial decrease in calculations communication levels and in iteration time. The results are presented in an analytical approach in terms of scalability, efficiency, memory usage, speed up and input/output rates. Finally, a countermeasures model is developed to protect against network attacks by using a Dynamic Countermeasures Attack Tree (DCAT). The following scheme is used to build DCAT tree (i) using scalable parallel CostRank Algorithm to determine the critical asset, that system administrators need to protect; (ii) Track the Nessus scanner to determine the vulnerabilities associated with the asset using the dynamic cost centric framework and DVSS; (iii) Check out all published mitigations for all vulnerabilities. (iv) Assess how well the security solution mitigates those risks; (v) Assess DCAT algorithm in terms of effective security cost, probability and cost/benefit analysis to reduce the total impact of a specific vulnerability.

One of the most powerful properties of mathematical systems theory is the fact that interconnecting systems yields composites that are themselves systems. This property allows for the engineering of complex systems by aggregating simpler systems into intricate patterns. We call these interconnection patterns the "structure" of the system. Similarly, this property also enables the understanding of complex systems by decomposing them into simpler parts. We likewise call the relationship between these parts the "structure" of the system. At first glance, these may appear to represent identical views of structure of a system. However, further investigation invites the question: are these two notions of structure of a system the same? This dissertation answers this question by developing a theory of dynamical structure. The work begins be distinguishing notions of structure from their associated mathematical representations, or models, of a system. Focusing on linear time invariant (LTI) systems, the key technical contributions begin by extending the definition of the dynamical structure function to all LTI systems and proving essential invariance properties as well as extending necessary and sufficient conditions for the reconstruction of the dynamical structure function from data. Given these extensions, we then develop a framework for analyzing the structures associated with different representations of the same system and use this framework to show that interconnection (or subsystem) structures are not necessarily the same as decomposition (or signal) structures. We also show necessary and sufficient conditions for the reconstruction of the interconnection (or subsystem) structure for a class of systems. In addition to theoretical contributions, this work also makes key contributions to specific applications. In particular, network reconstruction algorithms are developed that extend the applicability of existing methods to general LTI systems while improving the computational complexity. Also, a passive reconstruction method was developed that enables reconstruction without actively probing the system. Finally, the structural theory developed here is used to analyze the vulnerability of a system to simultaneous attacks (coordinated or uncoordinated), enabling a novel approach to the security of cyber-physical-human systems.