Path validation in computer networks is used to enforce and verify data forwarding rules across network slices and administrative domains to satisfy specific service level requirements. Deviating from pre-established paths has the potential to downgrade network service quality, increase attack surface area, and disrupt network orchestration capabilities. Network operators regard the network infrastructure and topology as sensitive. This necessitates the need for privacy-preserving path validation techniques that leak minimal information about the overall network path to individual infrastructure owners. We present the design of a decentralized privacy-preserving path validation protocol using Non-Interactive Zero-Knowledge (NIZK) proofs to provide provable path privacy guarantees. The NIZK-based pairwise validation design identifies individual slice nodes that deviate from the prescribed path. Deploying this lightweight protocol periodically enables individual nodes to enforce and validate the network control path. We have implemented and evaluated our system on a testbed simulating a multi-authority network. Our results demonstrate the feasibility of preserving path privacy as well as the practicality of our proposed protocols for next-generation multi-authority sliced networks.

We address the Virtual Network Embedding (VNE) problem in which the task is to map a virtual network onto a given physical substrate network so that the CPU and bandwidth capacity constraints are met. Following the success of Boolean Satisfiability (SAT) methods in areas such as Multi-Agent Path Finding (MAPF), we propose in this paper a novel SAT-based approach for solving the VNE problem. As in MAPF, the various constraints that define the VNE problem are encoded into the SAT models incrementally and via lazy refinements so as to keep the models simple. We also propose various model relaxations and concomitant solution extraction post-processing procedures. Through experiments, we show that our SAT-based approach outperforms other state-of-the-art approaches on a number of VNE instances.

Virtualization is the mechanism of creating virtual representations of physical resources. It is now integrated into almost every facet of computing and is pervasive on the Internet: ranging from data center services and cloud computing services to services on our phones. The common goal for virtualization providers is to ensure that the physical resources are managed efficiently and effectively. This goal induces the Virtual Network Embedding (VNE) problem: the task of properly allocating the physical resources of a network to satisfy virtual requests for resources under various constraints while ensuring the quality of service and maximizing resource utilization. The VNE problem captures many resource allocation tasks arising in computer systems and computer networks. In this paper, we present Improved VNE-CBS (iVNE-CBS) as an efficient and effective algorithm for solving the VNE problem. iVNE-CBS builds on Conflict-Based Search (CBS), a heuristic search framework borrowed from the Multi-Agent Path Finding literature. We show that iVNECBS significantly outperforms popular baseline VNE algorithms: it scales to networks with several hundreds of vertices and thousands of edges, while also producing better-quality solutions.

The Loon project provided 4G LTE connectivity to under-served regions in emergency response and commercial mobile contexts using base stations carried by high-altitude balloons. To backhaul data, Loon orchestrated a moving mesh network of point-to-point radio links that interconnected balloons with each other and to ground infrastructure. This paper presents insights from 3 years of operational experience with Loon's mesh network above 3 continents.

Path validation assures operational integrity in 5G networks with various network infrastructures where nodes en route are operated by multiple untrusted network slicing authorities. However, in order to correctly validate a path, traditional solutions require the entire path to be revealed to all parties involved, which may potentially expose the network structure to malicious attackers. In this work, we propose a decentralized privacy-preserving path validation protocol utilizing XOR, hashing and Non-interactive zero-knowledge proof (NIZK) that guarantees security and privacy but circumvents performance compromise. We tested our protocols in a simulated multi-authority network to show how the privacy-preserving path validation can protect node privacy without significantly degrading performance.

Network slicing is a powerful tool that provides 5G and future networks a robust means for managing cross-application QoS, dynamic traffic migration in response to network events, and in-network data aggregation and computation. Unfortunately, slicing inherits many of the security challenges of cloud and edge computing such as side-channel information leakage, while also encountering new challenges posed by multi-domain authorization and quantum computing. Many extant mechanisms, such as PKI, are insufficient in the face of quantum computers, and existing side-channel mitigations impose heavy overhead costs while only providing defense against known attacks. In this paper, we describe a novel approach to protecting slice control information through the use of Homomorphic Encryption (HE). HE allows quantum-resilient validation and distribution of critical information, while also enabling hierarchical control across multiple domains and providing encrypted computation. Further, threshold HE enables secure decryption and computation of control or measurement information, while protecting the entire slice against potential key-leakage by rendering any one key useless without the required quorum. The benchmark results shown demonstrate that the HE mechanisms used can be deployed in a practical manner, providing stalwart security guarantees against a variety of threats.

Abstract Tackling binary program analysis problems has traditionally implied manually defining rules and heuristics, a tedious and time consuming task for human analysts. In order to improve automation and scalability, we propose an alternative direction based on distributed representations of binary programs with applicability to a number of downstream tasks. We introduce Bin2vec, a new approach leveraging Graph Convolutional Networks (GCN) along with computational program graphs in order to learn a high dimensional representation of binary executable programs. We demonstrate the versatility of this approach by using our representations to solve two semantically different binary analysis tasks – functional algorithm classification and vulnerability discovery. We compare the proposed approach to our own strong baseline as well as published results, and demonstrate improvement over state-of-the-art methods for both tasks. We evaluated Bin2vec on 49191 binaries for the functional algorithm classification task, and on 30 different CWE-IDs including at least 100 CVE entries each for the vulnerability discovery task. We set a new state-of-the-art result by reducing the classification error by 40% compared to the source-code based inst2vec approach, while working on binary code. For almost every vulnerability class in our dataset, our prediction accuracy is over 80% (and over 90% in multiple classes).

IP spoofing has been a persistent Internet security threat for decades. While research solutions exist that can help an edge network detect spoofed and reflected traffic, the sheer volume of such traffic requires handling further upstream.

Protecting data from accidental loss or theft is crucial in today's world of mobile computing. Data Tethers provides flexible environmental policies, which can be attached to data, specifying security requirements that must be met before accessing that data. Data Tethers uses fine-grain data flow tracking to maintain these policies on derivative data. This is implemented by dynamic recompilation of legacy applications without the need to recompile from source. We demonstrate the system's feasibility with microbenchmarks that show individual component performance and benchmarks of real user applications like word processors and spreadsheets.

Denial-of-service (DoS) attacks continue to be a major problem on the Internet. While many defense mechanisms have been created, they all have significant deployment issues. This paper introduces a novel method that overcomes these issues, allowing a small number of deployed DoS defenses to act as secure on-demand shields for any node on the Internet. The proposed method is based on rerouting any packet addressed to a protected autonomous system (AS) through an intermediate filtering node-a shield. In this way, all potentially harmful traffic could be discarded before reaching the destination. The mechanisms for packet rerouting use existing routing techniques and do not require any kind of modification to the deployed protocols or routers. To make the proposed system feasible, from both deployment and usage points of view, traffic rerouting and outsourced filtering could be provided as an insurance-style on-demand service.

Reflector attacks are a variant of denial-of-service attacks that use unwitting, legitimate servers to flood a target. The attacker spoofs the target's address in legitimate service requests, such as TCP SYN packets. The servers, called "reflectors,'' reply to these requests, flooding the target. RAD is a novel defense against reflector attacks. It has two variants -- locally-deployed (L-RAD) and core-deployed (C-RAD). Local RAD uses message authentication codes (MACs) to mark outgoing requests at their source, so the target of a reflector attack can differentiate between replies to legitimate and spoofed requests. MACs can be validated either at the target machine or on a gateway router at the target's network. Core RAD, which is deployed at the AS level, handles larger attacks that overwhelm L-RAD. The source AS marks each packet it sends with a hash message authentication code (HMAC) and core ASes filter packets that carry incorrect HMACs. C-RAD prevents reflector attacks by filtering spoofed requests, rather than filtering reflected replies. We tested both variants using the DETER testbed by replaying backbone traces from the MAWI project archive in a congestion-responsive manner. Our tests show that local RAD is better than the no-defense case, but gets overwhelmed when the attack exceeds the target's network capacity. Core-deployed RAD successfully handles attacks of all rates.

As threats on the Internet become increasingly sophisticated, we now recognize the value in controlling the routing of data in a manner that ensures security. However, few technical means for achieving this goal exist. In this paper we propose and design a system that allows users to specify regions of the Internet they wish their data to avoid. Using our system, data will either arrive at the destination along a path that avoids the specified regions, or no avoiding path exists. Beyond the design, we discuss the deployment, performance and security issues of this system, along with alternative approaches that could be used. Categories and Subject Descriptors C.2.0 [General]: Security and protection; C.2.2 [Network