Directed hypergraphs are vital for modeling complex polyadic relationships in domains such as discrete mathematics, computer science, network security, and systems modeling. However, their inherent complexity often impedes effective visualization and analysis, particularly for large graphs. This paper introduces a novel Transitivity Preserving Projection (TPP) to address the limitations of the computationally intensive Basu and Blanning projection (BBP), which can paradoxically increase complexity by flattening transitive relationships. TPP offers a minimal and complete representation of relationships within a chosen subset of elements, capturing only irreducible dominant metapaths to ensure the smallest set of edges while preserving all essential transitive and direct connections. This approach significantly enhances visualization by reducing edge proliferation and maintains the integrity of the original hypergraph’s structure. We develop an efficient algorithm leveraging the set-trie data structure, reducing the computational complexity from an exponential number of metapath searches in BBP to a linear number of metapath searches with polynomial-time filtering, enabling scalability for real-world applications. Experimental results demonstrate TPP’s superior performance, completing projections in seconds on graphs where BBP fails to terminate within 24 hours. By providing a minimal yet complete view of relationships, TPP supports applications in network security and supply chain analysis, offering a clearer, more efficient framework for hypergraph simplification and analysis.

Decentralized online planning, such as decentralized Monte Carlo tree search (MCTS), is an attractive paradigm for cooperative multi-agent systems in information-gathering tasks. However, current MCTS algorithms implicitly assume that agents are always available and actively contributing throughout the mission. In realistic, dynamic, and volatile environments, agent attrition is common and can severely degrade performance. In this paper, we demonstrate that agent attrition can cause current decentralized MCTS methods to perform arbitrarily worse than the optimum, particularly in applications with submodular reward functions. To address this issue, we propose Attritable Monte Carlo Tree Search (A-MCTS), a decentralized MCTS algorithm that adapts quickly and efficiently to reductions in the set of active agents. Our key idea is to have each agent build its search tree using the global utility function while coordinating with teammates through a regret-matching algorithm. Our theoretical analysis and extensive simulations show that A-MCTS maintains effective coordination among agents, even in high-attrition environments. We evaluate our approach in different information-gathering problems by modeling realistic reference scenarios. Results highlight that A-MCTS substantially improves over the main competing methods regarding global utility, scalability, and robustness.

In this paper, we propose a novel choke point metric for the elimination of attack paths. Our study is motivated by its applications in the widely used Active Directory (AD) attack graphs. Choke points are typically defined as critical locations where the largest number of attack paths converge. Identifying these choke points is crucial. Enumeration of all attack paths is implied in this definition, but the immensity of paths in AD attack graphs makes the task extremely challenging. Consequently, industry solutions and research often rely on mapping only the shortest paths or prioritizing their elimination as a method for hardening AD attack graphs. We theoretically describe and empirically measure major limitations with the shortest path approach. To address the limitations, we introduce a new choke point metric that quantifies the intersection of connections rather than attack paths, which improves upon shortest path mapping. Additionally, we present human experiments to observe how white-hat hackers use shortest path mapping, provide simple graph examples that visually demonstrate failure cases where shortest path-based methods do not yield optimal results, and conduct experiments with a diverse set of real-world and synthetic AD datasets. From the results, we conclude that uninformed attack path mapping cannot capture the complexity of the attack path composition in a real-world attack, and reliance on shortest path mapping leads to significant volatility in security-hardening outcomes. In contrast, the connection-based choke point metric we propose offers greater optimality and utility in mitigating the attack surface.

Security vulnerabilities in Windows Active Directory (AD) systems are typically modeled using an attack graph and hardening AD systems involves an iterative workflow: security teams propose an edge to remove, and IT operations teams manually review these fixes before implementing the removal. As verification requires significant manual effort, we formulate an Adaptive Path Removal Problem to minimize the number of steps in this iterative removal process. In our model, a wizard proposes an attack path in each step and presents it as a set of multiple-choice options to the IT admin. The IT admin then selects one edge from the proposed set to remove. This process continues until the target t is disconnected from source s or the number of proposed paths reaches B. The model aims to optimize the human effort by minimizing the expected number of interactions between the IT admin and the security wizard. We first prove that the problem is #P-hard. We then propose a set of solutions including an exact algorithm, an approximate algorithm, and several scalable heuristics. Our best heuristic, called DPR, can operate effectively on larger-scale graphs compared to the exact algorithm and consistently outperforms the approximate algorithm across all graphs. We verify the effectiveness of our algorithms on several synthetic AD graphs and an AD attack graph collected from a real organization.

Active Directory (AD), a directory service developed for Windows domain networks, is a frequent target for attackers due to its widespread adoption and the sensitive information it manages. Most existing attack path management solutions in ADs rely on simplistic node-to-node graphs, disregarding dependencies between edges. Specifically, in AD systems, there exists policy-defining edges that represent permissions on a set of objects. A single defensive action to remove such an edge can eliminate multiple permissions associated with all objects within the set - effectively removing all other edges connecting nodes in this set. In this paper, we propose a rigorous model that formalizes this concept of node-to-set mapping using $\alpha$-metagraph - a novel high-order graph model for capturing dependencies in AD systems. We present an algorithm for constructing the $\alpha$ metagraph from Active Directory data. Furthermore, we extend the current state-of-the-art AD defensive solution algorithm Spiral - to operate with the $\alpha$-metagraph model, taking advantage of policy-defining edges in AD network defense. Our extensive experiments demonstrate that the proposed $\alpha$-Spiral Algorithm, applied to $\alpha$-metagraphs, delivers timely and superior defense strategies, mitigating more attack sources within time and budget constraints than the original Spiral algorithm on node-to-node graphs.

Active Directory (AD) is the default security management system for Windows domain networks. An AD environment can be described as a cyber-attack graph, with nodes representing computers, accounts, and so forth, and edges indicating existing accesses or known exploits that enable attackers to move from one node to another. This article explores a Stackelberg game model between one attacker and one defender on an AD attack graph. The attacker’s goal is to maximize their chances of successfully reaching the destination before getting detected. The defender’s aim is to block a constant number of edges to minimize the attacker’s chance of success. The article shows that the problem is #P-hard and, therefore, intractable to solve exactly. To defend the AD graph from cyberattackers, this article proposes two defensive approaches. In the first approach, we convert the attacker’s problem to an exponential-sized Dynamic Program that is approximated by a neural network (NN). Once trained, the NN serves as an efficient fitness function for defender’s Evolutionary Diversity Optimization-based defensive policy. The diversity emphasis on the defender’s solution provides a diverse set of training samples, improving the training accuracy of our NN for modeling the attacker. In the second approach, we propose a RL-based policy to solve the attacker’s problem and Critic network-assisted Evolutionary Diversity Optimization-based defensive policy to solve defender’s problem. Experimental results on synthetic AD graphs show that the proposed defensive policies are scalable, highly effective, approximate attacker’s problem accurately and generate good defensive plans.

We propose a combinatorial optimisation model called Limited Query Graph Connectivity Test. We consider a graph whose edges have two possible states (On/Off). The edges' states are hidden initially. We could query an edge to reveal its state. Given a source s and a destination t, we aim to test s−t connectivity by identifying either a path (consisting of only On edges) or a cut (consisting of only Off edges). We are limited to B queries, after which we stop regardless of whether graph connectivity is established. We aim to design a query policy that minimizes the expected number of queries. Our model is mainly motivated by a cyber security use case where we need to establish whether attack paths exist in a given network, between a source (i.e., a compromised user node) and a destination (i.e., a high-privilege admin node). Edge query is resolved by manual effort from the IT admin, which is the motivation behind query minimization. Our model is highly related to Stochastic Boolean Function Evaluation (SBFE). There are two existing exact algorithms for SBFE that are prohibitively expensive. We propose a signifcantly more scalable exact algorithm. While previous exact algorithms only scale for trivial graphs (i.e., past works experimented on at most 20 edges), we empirically demonstrate that our algorithm is scalable for a wide range of much larger practical graphs (i.e., graphs representing Windows domain networks with tens of thousands of edges). We also propose three heuristics. Our best-performing heuristic is via limiting the planning horizon of the exact algorithm. The other two are via reinforcement learning (RL) and Monte Carlo tree search (MCTS). We also derive an algorithm for computing the performance lower bound. Experimentally, we show that all our heuristics are near optimal. The heuristic building on the exact algorithm outperforms all other heuristics, surpassing RL, MCTS and eight existing heuristics ported from SBFE and related literature.

Active Directory (AD), a directory service for Windows domain networks, is a common target for attackers due to its widespread use and the confidential data it contains. According to Microsoft, 95 million AD accounts are attacked every day and new attacks involving AD are a common occurrence. Despite frequent attacks against Active Directory and its critical role in network security, there are no publicly available datasets and tools for generating realistic AD graphs. This absence hinders the development and testing of novel methods for protecting AD systems. Realistic AD datasets are also essential for training and up-skilling human AD defenders. In this work, we develop ADSynth, a scalable and realistic AD attack graph generator. ADSynth uses metagraphs to model design principles of realistic AD systems, relying on three novel ideas: (1) metagraph abstractions of best practices in AD organizational design, (2) metagraph abstractions of security design principles in AD systems, and (3) a random metagraph model of common security misconfigurations. Our experiments demonstrate ADSynth's scalability in creating realistic AD graphs under various security settings. We apply ADSynth to some recent research on AD security and demonstrate that data from ADSynth significantly benefit these studies. ADSynth has been released to the community11https.z/adsynthcsizcr.github.io/22https://github.com/adsynthesizer/ADSynth.git.

Decentralized planning is a key element of cooperative multi-agent systems for information gathering tasks. However, despite the high frequency of agent failures in realistic large deployment scenarios, current approaches perform poorly in the presence of failures, by not converging at all, and/or by making very inefficient use of resources (e.g. energy). In this work, we propose Attritable MCTS (A-MCTS), a decentralized MCTS algorithm capable of timely and efficient adaptation to changes in the set of active agents. It is based on the use of a global reward function for the estimation of each agent’s local contribution, and regret matching for coordination. We evaluate its effectiveness in realistic data-harvesting problems under different scenarios. We show both theoretically and experimentally that A-MCTS enables efficient adaptation even under high failure rates. Results suggest that, in the presence of frequent failures, our solution improves substantially over the best existing approaches in terms of global utility and scalability.

Microsoft Active Directory (AD) is the default security management system for Window domain network. We study the problem of placing decoys in AD network to detect potential attacks. We model the problem as a Stackelberg game between an attacker and a defender on AD attack graphs where the defender employs a set of decoys to detect the attacker on their way to Domain Admin (DA). Contrary to previous works, we consider time-varying (temporal) attack graphs. We proposed a novel metric called response time, to measure the effectiveness of our decoy placement in temporal attack graphs. Response time is defined as the duration from the moment attackers trigger the first decoy to when they compromise the DA. Our goal is to maximize the defender's response time to the worst-case attack paths. We establish the NP-hard nature of the defender's optimization problem, leading us to develop Evolutionary Diversity Optimization (EDO) algorithms. EDO algorithms identify diverse sets of high-quality solutions for the optimization problem. Despite the polynomial nature of the fitness function, it proves experimentally slow for larger graphs. To enhance scalability, we proposed an algorithm that exploits the static nature of AD infrastructure in the temporal setting. Then, we introduce problem-tailored repair operations, ensuring the convergence to better results while maintaining scalability for larger graphs.

We study a Stackelberg game between an attacker and a defender on large Active Directory (AD) attack graphs where the defender employs a set of honeypots to stop the attacker from reaching high-value targets. Contrary to existing works that focus on small and static attack graphs, AD graphs typically contain hundreds of thousands of nodes and edges and constantly change over time. We consider two types of attackers: a simple attacker who cannot observe honeypots and a competent attacker who can. To jointly solve the game, we propose a mixed-integer programming (MIP) formulation. We observed that the optimal blocking plan for static graphs performs poorly in dynamic graphs. To solve the dynamic graph problem, we re-design the mixed-integer programming formulation by combining m MIP (dyMIP(m)) instances to produce a near-optimal blocking plan. Furthermore, to handle a large number of dynamic graph instances, we use a clustering algorithm to efficiently find the m-most representative graph instances for a constant m (dyMIP(m)). We prove a lower bound on the optimal blocking strategy for dynamic graphs and show that our dyMIP(m) algorithms produce close to optimal results for a range of AD graphs under realistic conditions.

In future radio access networks, machine learning (ML) based strategies for short-term forecasting of vehicular trajectories will be key for anticipatory resource allocation and management at the mobile edge. However, training ML models in a centralized fashion, over data collected from a massive heterogeneous and dynamic set of devices, poses significant scalability, reliability, and efficiency challenges, which are still open to date. In this article, we look at the specific issue of scalable and resource-efficient training of ML models in a vehicular environment. To address such a challenge, we propose a new Gossip Learning scheme, i.e., a fully distributed, collaborative training approach based on direct, opportunistic model exchanges via wireless device-to-device (D2D) communications with no centralized support. Our approach is based on constantly improving each node's own model instance through knowledge transfer among nodes, and on different strategies for estimating the potential contribution of neighboring nodes to the training process at a node. Extensive numerical assessments on a variety of measurement-based dynamic urban scenarios suggest that our schemes are able to converge rapidly and provide sufficiently accurate forecasts of vehicle position for time horizons which are typical of future 5 G/6 G dynamic resource allocation algorithms.

Coordinated multi-robot systems are an effective way to harvest data from sensor networks and implement active perception strategies. However, achieving efficient coordination in a way that guarantees a target QoS while adapting dynamically to changes (in the environment and/or in the system) is a key open issue. In this paper, we propose a novel decentralized Monte Carlo Tree Search (MCTS) algorithm for dynamic environments that allows agents to optimize their own actions while achieving some form of coordination. Its main underlying idea is to balance adaptively the exploration-exploitation trade-off to deal effectively with changes in the environment while filtering out outdated and irrelevant samples via a sliding window mechanism. We show both theoretically and through simulations that in dynamic environments our algorithm provides a log-factor (in terms of time steps) smaller regret than state-of-the-art decentralized multi-agent planning methods. We instantiate our approach to the problem of underwater data collection, showing in a variety of different settings that our approach greatly outperforms the best-competing approaches, both in terms of convergence speed and global utility.

Active Directory (AD) is the default security management system for Windows domain networks. An AD environment naturally describes an attack graph where nodes represent computers/accounts/security groups, and edges represent existing accesses/known exploits that allow the attacker to gain access from one node to another. Motivated by practical AD use cases, we study a Stackelberg game between one attacker and one defender. There are multiple entry nodes for the attacker to choose from and there is a single target (Domain Admin). Every edge has a failure rate. The attacker chooses the attack path with the maximum success rate. The defender can block a limited number of edges (i.e., revoke accesses) from a set of blockable edges, limited by budget. The defender's aim is to minimize the attacker's success rate. We exploit the tree-likeness of practical AD graphs to design scalable algorithms. We propose two novel methods that combine theoretical fixed parameter analysis and practical optimisation techniques. For graphs with small tree widths, we propose a tree decomposition based dynamic program. We then propose a general method for converting tree decomposition based dynamic programs to reinforcement learning environments, which leads to an anytime algorithm that scales better, but loses the optimality guarantee. For graphs with small numbers of non-splitting paths (a parameter we invent specifically for AD graphs), we propose a kernelization technique that significantly downsizes the model, which is then solved via mixed-integer programming. Experimentally, our algorithms scale to handle synthetic AD graphs with tens of thousands of nodes.

We have developed a novel ’Teacher-Student with human feedback’ model for Human-Artificial Intelligence (AI) collaborations in cybersecurity tasks. In our model, AI furnishes sufficient information about its decision-making process to enable human agents to provide feedback to improve the model. Our key innovations include: enhancing the interpretability of AI models by analyzing falsely detected samples using LIME and SHAP values; developing a novel posthoc explanation-based dynamic teacher-student model to address concept drift or concept shift; integrating human experts’ feedback on falsely detected samples to increase accuracy, precision, and recall values, without retraining the entire model; establishing a list of attack-based feature values for human experts to promote reproducibility. We show in experiments with real data and threat detection tasks that our model significantly improves the accuracy of existing AI algorithms for these tasks.

Active Directory (AD) is a popular information security management system for Windows domain networks and is an ongoing common target for cyber attacks. Most real-world Active Directory systems consist of millions of entities and links, and there are currently no efficient and effective solutions for hardening Active Directory systems of such scale. In this paper, we propose a novel and scalable double oracle-based algorithm for hardening large AD systems. We formulate the problem as a Stackelberg game between the defender and the attacker on a weighted AD attack graph, where the defender acts as the leader with a budget, and the objective is to find an optimal defender’s pure strategy. We show that our double oracle-based solution has significantly improved speed and scalability compared with previous solutions for hardening AD systems. Lastly, we compare with GoodHound weakest links and show that our solution provides better recommendations for targeting the elimination of optimal attack paths.

We study a Stackelberg game between one attacker and one defender in a configurable environment. The defender picks a specific environment configuration. The attacker observes the configuration and attacks via Reinforcement Learning (RL trained against the observed environment). The defender's goal is to find the environment with minimum achievable reward for the attacker. We apply Evolutionary Diversity Optimization (EDO) to generate diverse population of environments for training. Environments with clearly high rewards are killed off and replaced by new offsprings to avoid wasting training time. Diversity not only improves training quality but also fits well with our RL scenario: RL agents tend to improve gradually, so a slightly worse environment earlier on may become better later. We demonstrate the effectiveness of our approach by focusing on a specific application, Active Directory (AD). AD is the default security management system for Windows domain networks. AD environment describes an attack graph, where nodes represent computers/accounts/etc., and edges represent accesses. The attacker aims to find the best attack path to reach the highest-privilege node. The defender can change the graph by removing a limited number of edges (revoke accesses). Our approach generates better defensive plans than the existing approach and scales better.

Securing cloud environments such as Microsoft Azure cloud is challenging and vulnerabilities due to misconfigurations, especially with user roles assignment, are common. There have been significant efforts to find vulnerabilities that enable lateral movements in Azure AD systems. All of the existing works, however, either follow a manual process to find new vulnerabilities or are only able to discover whether known vulnerabilities exist in a deployed Azure environment. We develop an Azure Active Directory (AAD) lateral movement-discovery tool, CoZure, that can help researchers find new lateral movements in an Azure AD environment. CoZure deploys algorithms from Context-Free Grammar (CFG) to first learn the ways (grammar rules) that security researchers find vulnerabilities and then extend these rules to discover new lateral movement paths. CoZure first collects a large set of existing AAD environment commands using a specialized scraping tool, it then uses CFG to build a knowledge base dataset from these commands and previous attacks. Cozure then applies the knowledge learned to find new combinations of commands that could open up new candidate lateral movements, which are then tested in a real AD environment for validation and manually checked by the user. CoZure helped discover lateral movements that current fuzzing tools (e.g., OneFuzz, RESTler) cannot identify and also shows better performance in finding existing misconfiguration issues in Azure AD. Using CoZure, we have discovered two new (not previously known) lateral movement methods that could lead to numerous new attacking paths in Azure AD.

Active Directory is the default security management system for Windows domain networks. We study the shortest path edge interdiction problem for defending Active Directory style attack graphs. The problem is formulated as a Stackelberg game between one defender and one attacker. The attack graph contains one destination node and multiple entry nodes. The attacker's entry node is chosen by nature. The defender chooses to block a set of edges limited by his budget. The attacker then picks the shortest unblocked attack path. The defender aims to maximize the expected shortest path length for the attacker, where the expectation is taken over entry nodes. We observe that practical Active Directory attack graphs have small maximum attack path length and are structurally close to trees. We first show that even if the maximum attack path length is a constant, the problem is still w[1]-hard with respect to the defender's budget. Having a small maximum attack path length and a small budget is not enough to design fixed-parameter algorithms. If we further assume that the number of entry nodes is small, then we derive a fixed-parameter tractable algorithm. We then propose two other fixed-parameter algorithms by exploiting the tree-like features. One is based on tree decomposition and requires a small tree width. The other assumes a small number of splitting nodes (nodes with multiple out-going edges). Finally, the last algorithm is converted into a graph convolutional neural network based heuristic, which scales to larger graphs with more splitting nodes.

Active Directory (AD) is the default security management system for Windows domain networks. We study a Stackelberg game model between one attacker and one defender on an AD attack graph. The attacker initially has access to a set of entry nodes. The attacker can expand this set by strategically exploring edges. Every edge has a detection rate and a failure rate. The attacker aims to maximize their chance of successfully reaching the destination before getting detected. The defender's task is to block a constant number of edges to decrease the attacker's chance of success. We show that the problem is #P-hard and, therefore, intractable to solve exactly. We convert the attacker's problem to an exponential sized Dynamic Program that is approximated by a Neural Network (NN). Once trained, the NN provides an eficient fitness function for the defender's Evolutionary Diversity Optimisation (EDO). The diversity emphasis on the defender's solution provides a diverse set of training samples, which improves the training accuracy of our NN for modelling the attacker. We go back and forth between NN training and EDO. Experimental results show that for R500 graph, our proposed EDO based defense is less than 1% away from the optimal defense.

Nowcasting, i.e., short-term forecasting, of end user location is becoming increasingly important for anticipatory resource management in radio access networks (RAN). In this paper, we look at the case of vehicles moving in dense urban environments, and we tackle the location nowcasting problem with a particular class of machine learning (ML) algorithms that goes under the name Gossip Learning (GL). GL is a peer-to-peer machine learning approach based on direct, opportunistic exchange of models among nodes via wireless device-to-device (D2D) communications, and on collaborative model training. It has recently proven to scale efficiently to large numbers of static nodes, and to offer better privacy guarantees than traditional centralized learning architectures. We present new decentralized algorithms for GL, suitable for setups with dynamic nodes. In our approach, nodes improve their personalized model instance by sharing it with neighbors, and by weighting neighbors' contributions according to an estimate of their marginal utility. Our results show that the proposed GL algorithms are capable of providing accurate vehicle position predictions for time horizons of a few seconds, which are sufficient to implement effective anticipatory radio resource management.

Coordinated multi-robot systems are an effective way to harvest data from sensor networks and to implement active perception strategies. However, achieving efficient coordination in a way which guarantees a target QoS while adapting dynamically to changes (in the environment, due to sensors’ mobility, and/or in the value of harvested data) is to date a key open issue. In this paper, we propose a novel decentralized Monte Carlo Tree Search algorithm (MCTS) which allows agents to optimize their own actions while achieving some form of coordination, in a changing environment. Its key underlying idea is to balance in an adaptive manner the exploration-exploitation trade-off to deal effectively with abrupt changes caused by the environment and random changes caused by other agents’ actions. Critically, outdated and irrelevant samples - an inherent and prevalent feature in all multi-agent MCTS-based algorithms - are filtered out by means of a sliding window mechanism. We show both theoretically and through simulations that our algorithm provides a log-factor (in terms of time steps) smaller regret than state-of-the-art decentralized multi-agent planning methods. We instantiate our approach on the problem of underwater data collection, showing on a set of different models for changes that our approach greatly outperforms the best available algorithms for that setting, both in terms of convergence speed and of global utility.

Reliable network-policy specification requires abstractions that can naturally model policies together with rigorous formal foundations to reason about these policies. Current specifications satisfy one of these requirements or the other, but not both. A Metagraph is a generalized graph-theoretic structure that overcomes this limitation. They are a natural way of expressing high-level end-to-end network policies. The rich formal foundations provided by metagraph algebra help analyze important network-policy properties such as reachability, redundancy and consistency. These features make metagraphs a clear choice for modeling and reasoning about policies in Formally-Verifiable Policy-Defined Networking (FV-PDN): a network-programming paradigm which has verifiability built-in. In this article, we demonstrate the use of metagraphs in policy specification by modeling and analyzing real policies from a large university network. We show their benefit in FV-PDN by developing a prototype solution which automatically refines metagraph-based high-level policies to device configurations and deploys them to an SDN-based emulated network.

Comparisons between community detection methods are mostly based on their accuracies in recovering the built-in community structure in artificial benchmark networks. Current community detection benchmarks assign a fixed fraction of inter-community links, referred to as the mixing fraction, for every community in the same network. We first show in this paper that the variation in community mixing fractions has different impacts on the performances of different community detection methods that could change the decision to select a particular detecting algorithm. To comprehensively compare community detection methods, we therefore need a benchmark that generates heterogeneous community mixing fractions, which is not currently available. We address this gap by generalizing the state-of-the-art Lancichinetti-Fortunato-Radicchi benchmark to generate networks with heterogeneous community mixing fractions. Using our new benchmark, we can quantify the impact of the variation in community mixing fractions on existing community detection methods and re- evaluate the performance of the detecting algorithms as a function of the heterogeneity among the mixing fractions. Furthermore, we show that the heterogeneous community mixing tests using our generalized benchmark reflect better the performance that would be expected on real networks than the homogeneous community mixing tests using the original benchmark.

Future wireless networks (e.g., 5G) will consist of multiple radio access technologies (RATs). In these networks, deciding which RAT users should connect to is not a trivial problem. Current fully distributed algorithms although guaranteeing convergence to equilibrium states, are often slow, require high exploration times and may converge to undesirable equilibria. To overcome these limitations, this paper develops a network feedback framework that uses limited network-assisted information to improve efficiency of distributed algorithms for RAT selection problem. We prove theoretically that a fully distributed algorithm developed within this framework is guaranteed to converge to a set of correlated equilibria. Our framework guarantees convergence in self-play even when only a single user applies the algorithm. Simulation results demonstrate that our solution: 1) is highly efficient with fast convergence time and low signaling overheads while achieving competitive, if not better, performance both in fairness and utility, as well as achieving lower per-user switchings than state-of-the-art algorithms; and 2) can flexibly support a wide range of network-assisted feedback. The simulations demonstrate the effectiveness of our solution in a heterogeneous environment, where users may potentially apply a number of different RAT selection procedures.

Electromagnetic spectrum is a scarce resource. Spectrum licensing is estimated to consume about 20% of cellular operators' capital expenditure (CAPEX). One important measure of spectrum use is “spectral efficiency” (SE), which is the amount of data bandwidth that a specific technology can extract from a certain amount of radio spectrum and is measured in bits per second per Hz (bps/Hz). Using data from 4 different mobile operators, we show that spectral efficiency as the measure of bits per second per Hz correlates poorly with users' performance on cellular networks. Applying spectral efficiency directly in network performance monitoring or in network planning can provide misleading diagnostics and poorly targeted expansion plans. We propose a new spectral efficiency metric that combines the raw bit per second per Hz measurement with user perceived performance. We show that this new metric correlates well with measured user throughput and is superior metric for network planning and performance monitoring in real networks. We present a number of applications of our new metric on network management and capacity planning tasks. Our implementation of this approach has been used in operational networks for over 8 years and has provided sound basis for CAPEX decision making.

A common goal in network-management is security. Reliable security requires confidence in the level of protection provided. But, many obstacles hinder reliable security management; most prominent is the lack of built-in verifiability in existing management paradigms. This shortfall makes it difficult to provide assurance that the expected security outcome is consistent pre- and post-deployment. Our research tackles the problem from first principles: we identify the verifiability requirements of robust security management, evaluate the limitations of existing paradigms and propose a new paradigm with verifi- ability built in: Formally-Verifiable Policy-Defined Networking (FV-PDN). In particular, we pay attention to firewalls which protect network data and resources from unauthorised access. We show how FV-PDN can be used to configure firewalls reliably in mission critical networks to protect them from cyber attacks.

Firewall configuration is an important activity for any modern day business. It is particularly a critical task for the supervisory control and data acquisition (SCADA) networks that control power stations, water distribution, factory automation, etc. Lack of automation tools to assist with this critical task has resulted in unoptimised, error prone configurations that expose these networks to cyber attacks. Automation can make designing firewall configurations more reliable and their deployment increasingly cost-effective. Best practices have been proposed by the industry for developing high-level security policy (e.g., ANSI/ISA 62443-1-1). But these best practices lack specification in several key aspects needed to allow a firewall to be automatically configured. For instance, the standards are vague on how firewall management policies should be captured at a high-level using its specifications. In this paper, we uncover these missing pieces and propose extensions. We apply our extended best-practice specification to real-world firewall case studies to achieve multiple objectives: 1) to evaluate the usefulness of the refined best-practice in the automated specification of firewalls and 2) to illustrate that even in simple cases, SCADA networks are often insecure due to their misconfigured firewalls.

Emulated networks and systems, where router and server software are run in virtual environments, allow network operators and researchers to perform experiments at large scale more economically than in testbeds. Running real code provides a greater level of realism than simulation.

The prevalence of hidden Markov models (HMMs) in various applications of statistical signal processing and communications is a testament to the power and flexibility of the model. In this paper, we link the identifiability problem with tensor decomposition, in particular, the Canonical Polyadic decomposition. Using recent results in deriving uniqueness conditions for tensor decomposition, we are able to provide a necessary and sufficient condition for the identification of the parameters of discrete time finite alphabet HMMs. This result resolves a long standing open problem regarding the derivation of a necessary and sufficient condition for uniquely identifying an HMM. We then further extend recent preliminary work on the identification of HMMs with multiple observers by deriving necessary and sufficient conditions for identifiability in this setting.

Loss measurements are widely used in today's networks. There are existing standards and commercial products to perform these measurements. The missing element is a rigorous statistical methodology for their analysis. Indeed, most existing tools ignore the correlation between packet losses and severely underestimate the errors in the measured loss ratios. In this paper, we present a rigorous technique for analyzing performance measurements, in particular, for estimating confidence intervals of packet loss measurements. The task is challenging because Internet packet loss ratios are typically small and the packet loss process is bursty. Our approach, SAIL, is motivated by some simple observations about the mechanism of packet losses. Packet losses occur when the buffer in a switch or router fills, when there are major routing instabilities, or when the hosts are overloaded, and so we expect packet loss to proceed in episodes of loss, interspersed with periods of successful packet transmission. This can be modeled as a simple on/off process, and in fact, empirical measurements suggest that an alternating renewal process is a reasonable approximation to the real underlying loss process. We use this structure to build a hidden semi-Markov model (HSMM) of the underlying loss process and, from this, to estimate both loss ratios and confidence intervals on these loss ratios. We use both simulations and a set of more than 18 000 hours of real Internet measurements (between dedicated measurement hosts, PlanetLab hosts, Web and DNS servers) to cross-validate our estimates and show that they are better than any current alternative.

Most large attacks on the Internet are distributed. As a result, such attacks are only partially observed by any one Internet service provider (ISP). Detection would be significantly easier with pooled observations, but privacy concerns often limit the information that providers are willing to share. Multi-party secure distributed computation provides a means for combining observations without compromising privacy. In this paper, we show the benefits of this approach, the most notable of which is that combinations of observations solve identifiability problems in existing approaches for detecting network attacks.

Detection of malicious traffic and network health problems would be much easier if ISPs shared their data. Unfortunately, they are reluctant to share because doing so would either violate privacy legislation or expose business secrets. However, secure distributed computation allows calculations to be made using private data, without leaking this data. This paper presents such a method, allowing multiple parties to jointly infer a Hidden Markov Model (HMM) for traffic and/or user behaviour in order to detect anomalies. We extend prior work on HMMs in network security to include observations from multiple ISPs and develop secure protocols to infer the model parameters without revealing the private data. We implement a prototype of the protocols, and our experiments with the prototype show its has a reasonable computational and communications overhead, making it practical for adoption by ISPs.

Most large attacks on the Internet are distributed. As a result, such attacks are only partially observed by any one Internet Service Provider (ISP). Detection would be significantly easier with pooled observations, but privacy concerns often limit the information that providers are willing to share. Multi-party secure distributed computation provides a means for combining observations without compromising privacy. In this letter, we show the benefits of this approach, the most notable of which is that combinations of observations solve identifiability problems in existing approaches for detecting network attacks.

Network design, as it is currently practiced, involves putting devices together to create a network. However, a network is more than the sum of its parts, both in terms of the services it provides, and the potential for bugs. Devices are important, but their combination into a network should follow from expression of high-level policy, not the minutiae of network device configuration. Ideally we want to consider the network as a whole object. In this paper we develop generalized graph products that allow the mathematical design of a network in terms of small subgraphs that directly express business policy. The result is a flexible algebraic description of networks suitable for manipulation and proof. The approach is more than just design - it allows for analysis of existing networks providing an understanding of the policies used in their construction, something which can be difficult if the original designers no longer work on that network. We apply the approach to several real world networks to demonstrate how it can provide insight, and improve design.

The study of network topology has attracted a great deal of attention in the last decade, but has been hampered by a lack of accurate data. Existing methods for measuring topology have flaws, and arguments about the importance of these have overshadowed the more interesting questions about network structure. The Internet Topology Zoo is a store of network data created from the information that network operators make public. As such it is the most accurate large-scale collection of network topologies available, and includes meta-data that couldn't have been measured. With this data we can answer questions about network structure with more certainty than ever before - we illustrate its power through a preliminary analysis of the PoP-level topology of over 140 networks. We find a wide range of network designs not conforming as a whole to any obvious model.

In this paper we present a rigorous technique for estimating confidence intervals of packet loss measurements. Our approach is motivated by simple observations that the loss process can be modelled as an alternating renewal process. We use this structure to build a Hidden Semi-Markov Model (HSMM) for the measurement process, and from this estimate both loss rates, and their confidence intervals. We use both simulations and a set of more than 18000 hours of real Internet measurements (between dedicated measurement hosts, PlanetLab hosts, web and DNS servers) to cross-validate our estimates, and show that they are significantly more accurate than any current alternative.