Verifying the integrity of a file is a fundamental operation in file transfer. Common tools compute a short hash value that is sent along with the file, but computing this value requires going over the entire file and if the file is huge, then this process is slow. We introduce blkhash - a novel hash algorithm optimized for disk images, that is up to 4 orders of magnitude faster than commonly used tools. We implemented a new command line tool and library that can be used in the virtualization space for verifying storage management operations. Our approach can significantly contribute to use cases such as: (1) Very fast computing of virtual disk hash value in software defined storage, (2) Verifying an entire disk image content as part of a supply chain integrity verification or in the context of confidential computing.

Placement of VMs in the cloud is one of the most fundamental problems in systems research. Traditionally, placement algorithms assume that the schedulers have complete information about the currently available resources at each host. However, this assumption is in many cases unrealistic, as gathering fresh status information from each of the thousands of hosts in a large data center incurs excessive communication overhead, which results in long queueing delays. Efforts to resolve this problem by employing several parallel schedulers typically exhibit collisions when several schedulers are simultaneously trying to place VMs on the same host. Our work analyzes the performance of various placement algorithms and provides empirical evidence that using multiple randomized schedulers obtains high throughput, while significantly decreasing both the communication overhead, and the number of collisions between schedulers. We, therefore, introduce Adaptive Partial State Random (APSR) – an efficient parallel random resource management algorithm that samples only from a small number of hosts and dynamically adjusts the degree of parallelism to provide provable guarantees on the probability of collisions between distinct schedulers. We formally analyze APSR, evaluate it on real workloads, and integrate it into the popular OpenStack cloud management platform. Our evaluation shows that APSR matches the throughput provided by other parallel schedulers, while achieving up to 13x lower decline ratio and a reduction of over 85% in communication overheads.

Most modern systems utilize caches to reduce the average data access time and optimize their performance. Recently proposed policies implicitly assume uniform access times, but variable access times naturally appear in domains such as storage, web search, and DNS resolution. Our work measures the access times for various items and exploits variations in access times as an additional signal for caching algorithms. Using such a signal, we introduce adaptive access time-aware cache policies that consistently improve the average access time compared with the best alternative in diverse workloads. Our adaptive algorithm attains an average access time reduction of up to 46% in storage workloads, up to 16% in web searches, and 8.4% on average when considering all experiments in our study.

Cloud operators require timely identification of Heavy Hitters (HH) and Hierarchical Heavy Hitters (HHH) for applications such as load balancing, traffic engineering, and attack mitigation. However, existing techniques are slow in detecting new heavy hitters. In this paper, we present the case for identifying heavy hitters throughsliding windows. Sliding windows are quicker and more accurate to detect new heavy hitters than current interval-based methods, but to date had no practical algorithms. Accordingly, we introduce, design, and analyze theMementofamily of sliding window algorithms for the HH and HHH problems in the single-device and network-wide settings. We use extensive evaluations to show that our single-device solutions are orders of magnitude faster than existing sliding window techniques and comparable in speed to state-of-the-art non-windowed sampling based technique. Furthermore, we exemplify our network-wide HHH detection capabilities on a realistic testbed. To that end, we implemented Memento as an open-source extension to the popular HAProxy cloud load-balancer. In our evaluations, using an HTTP flood by 50 subnets, our network-wide approach detected the new subnets faster and reduced the number of undetected flood requests by up to$37\times $compared to the alternatives.

Network Function Virtualization (NFV) carries the potential for on-demand deployment of network algorithms in virtual machines (VMs). In large clouds, however, VM resource allocation incurs delays that hinder the dynamic scaling of such NFV deployment. Parallel resource management is a promising direction for boosting performance, but it may significantly increase the communication overhead and the decline ratio of deployment attempts. Our work analyzes the performance of various placement algorithms and provides empirical evidence that state of the art parallel resource management dramatically increases the decline ratio of deterministic algorithms, but hardly affects randomized algorithms. We therefore introduce APSR - an efficient parallel random resource management algorithm that requires information only from a small number of hosts and dynamically adjusts the degree of parallelism to provide provable decline ratio guarantees. We formally analyze APSR, evaluate it on real workloads, and integrate it into the popular OpenStack cloud management platform. Our evaluation shows that APSR matches the throughput provided by other parallel schedulers, while achieving up to 13x lower decline ratio and a reduction of over 85% in communication overheads.

Network Function Virtualization (NFV) enables software implementations of middleboxes such as load balancing, traffic engineering and quality of service. These often rely on network measurement such as per-flow frequency estimation, bandwidth estimation, counting distinct elements and estimating the traffic entropy. Keeping up with the line speed is an active challenge for NFV measurement techniques, and library algorithms are simply too slow. Sampling is a natural technique to increase the measurement throughput, but it requires a certain amount of traffic before accuracy is guaranteed. In this work, we introduce a throughput acceleration method that preserves accuracy from the very first packet. This technique works with a variety of existing measurement algorithms (e.g., the ones mentioned above), and improves their throughput while guaranteeing their correctness throughout the entire measurement. Our work includes a rigors analysis, an extensive evaluation with real network traces, and a real DPDK enabled Open vSwitch implementation.

Cloud operators require real-time identification of Heavy Hitters (HH) and Hierarchical Heavy Hitters (HHH) for applications such as load balancing, traffic engineering, and attack mitigation. However, existing techniques are slow in detecting new heavy hitters.

Hierarchical heavy hitters (HHH) identification is useful for various network utilities such as anomaly detection, DDoS mitigation, and traffic analysis. However, the increasing support for jumbo frames enables attackers to overload the system with fewer packets, avoiding detection by packet counting techniques. This paper suggests an efficient algorithm for detecting HHH based on their traffic volume that asymptotically improves the runtime of previous works. We implement our algorithm in Open vSwitch (OVS) and incur a 4-6% overhead compared to a 42% throughput reduction experienced by the state-of-the-art.

One of the biggest challenges for the Internet of Things (IoT) is to bridge the currently fragmented trust domains. The traditional PKI model relies on a common root of trust and does not fit well with the heterogeneous IoT ecosystem where constrained devices belong to independent administrative domains. In this work we describe a distributed trust model for the IoT that leverages the existing trust domains and bridges them to create end-to-end trust between IoT devices without relying on any common root of trust. Furthermore we define a new cryptographic primitive, denoted as obligation chain designed as a credit-based Blockchain with a built-in reputation mechanism. Its innovative design enables a wide range of use cases and business models that are simply not possible with current Blockchain-based solutions while not experiencing traditional blockchain delays. We provide a security analysis for both the obligation chain and the overall architecture and provide experimental tests that show its viability and quality.

Development of secure methods for storing log files is of tremendous importance for cyber security. One of the first actions by a hacker upon penetrating a machine is editing the log files to remove evidence of their presence. We propose to improve the security of these log files through a blockchain based solution. We show how our solution can be used to help organizations to mutually protect their sensitive log data even if some of them are compromised. Our solution allows data confidentiality between the collaborative parties.

Monitoring flow volumes is a fundamental capability in network measurement. Sampling is often used to cope with the line speed and the applied methods typically rely on uniform packet sampling. However, it is inaccurate when there is a large variance in packet sizes. In this work we introduce Byte Uniform Sampling (BUS), a sampling method for estimating flow volumes. We show that BUS can be combined with existing unweighted estimation algorithms and that the result is a weighted algorithm. BUS enables an asymptotic update time improvement as existing weighted algorithms are slower. We formally analyze BUS and evaluate it on five Internet traces. Finally, we extend the DPDK version of Open vSwitch to support BUS and demonstrate similar throughput when compared to uniform packet samples.

Monitoring tasks, such as anomaly and DDoS detection, require identifying frequent flow aggregates based on common IP prefixes. These are known as hierarchical heavy hitters (HHH), where the hierarchy is determined based on the type of prefixes of interest in a given application. The per packet complexity of existing HHH algorithms is proportional to the size of the hierarchy, imposing significant overheads.

Network coding helps maximize the network throughput. However, such schemes are also vulnerable to pollution attacks in which malicious forwarders inject polluted messages into the system. Traditional cryptographic solution, such as digital signatures, are not suited for network coding, in which nodes do not forward the original packets, but rather linear combinations of the data they received. We describe secure scheme that uses batch techniques and selective verification to efficiently verify the integrity of the received packets. We show that for real peer-to-peer networks, our scheme is much more efficient than previously suggested schemes.