Search

While the prominent quantum computing architectures are based on superconducting technology, new quantum hardware technologies are emerging, such as Trapped Ions, Neutral Atoms (or FPQAs), Silicon Spin Qubits, etc. This diverse set of technologies presents fundamental trade-offs in terms of scalability, performance, manufacturing, and operating expenses. To manage these diverse quantum technologies, there is a growing need for a retargetable compiler that can efficiently adapt existing code to these emerging hardware platforms. Such a retargetable compiler must be extensible to support new and rapidly evolving technologies, performant with fast compilation times and high-fidelity execution, and verifiable through rigorous equivalence checking to ensure the functional equivalence of the retargeted code. To this end, we present $Weaver$, the first extensible, performant, and verifiable retargetable quantum compiler framework with a focus on FPQAs due to their unique, promising features. $Weaver$ introduces WQASM, the first formal extension of the standard OpenQASM quantum assembly with FPQA-specific instructions to support their distinct capabilities. Next, $Weaver$ implements the WOptimizer, an extensible set of FPQA-specific optimization passes to improve execution quality. Last, the WChecker automatically checks for equivalence between the original and the retargeted code. Our evaluation shows that $Weaver$ improves compilation times by $10^3\times$, execution times by $4.4\times$, and execution fidelity by $10\%$, on average, compared to superconducting and state-of-the-art (non-retargetable) FPQA compilers., Comment: 11 pages, 12 figures

WebAssembly (WASM) is an immensely versatile and increasingly popular compilation target. It executes applications written in several languages (e.g., C/C++) with near-native performance in various domains (e.g., mobile, edge, cloud). Despite WASM's sandboxing feature, which isolates applications from other instances and the host platform, WASM does not inherently provide any memory safety guarantees for applications written in low-level, unsafe languages. To this end, we propose Cage, a hardware-accelerated toolchain for WASM that supports unmodified applications compiled to WASM and utilizes diverse Arm hardware features aiming to enrich the memory safety properties of WASM. Precisely, Cage leverages Arm's Memory Tagging Extension (MTE) to (i)~provide spatial and temporal memory safety for heap and stack allocations and (ii)~improve the performance of WASM's sandboxing mechanism. Cage further employs Arm's Pointer Authentication (PAC) to prevent leaked pointers from being reused by other WASM instances, thus enhancing WASM's security properties. We implement our system based on 64-bit WASM. We provide a WASM compiler and runtime with support for Arm's MTE and PAC. On top of that, Cage's LLVM-based compiler toolchain transforms unmodified applications to provide spatial and temporal memory safety for stack and heap allocations and prevent function pointer reuse. Our evaluation on real hardware shows that Cage incurs minimal runtime ($<5.8\,\%$) and memory ($<3.7\,\%$) overheads and can improve the performance of WASM's sandboxing mechanism, achieving a speedup of over $5.1\,\%$, while offering efficient memory safety guarantees.

We describe Qonductor, a cloud orchestrator for hybrid quantum-classical applications that run on heterogeneous hybrid resources. Qonductor exposes the $Qonductor~API$, a high-level and hardware-agnostic API for customizable hybrid application development and execution, that abstracts away the complexity of hybrid resource management. To guide hybrid resource management, the $resource~estimator$ accurately estimates execution fidelity and runtime to generate and offer resource plans. The $hybrid~scheduler$ leverages the resource plans to automate job scheduling on hybrid resources and balance the tradeoff between users' objectives of high fidelity and low runtimes and the cloud operator's objective of resource efficiency. We implement an open-source prototype of Qonductor by building on top of Kubernetes and evaluate it using more than 7000 real quantum runs on the IBM quantum cloud to simulate real cloud workloads. Qonductor achieves up to 54\% lower job completion times (JCTs) while sacrificing 6\% fidelity, balances the load across QPU which increases quantum resource utilization by up to 66\%, and scales with increasing system sizes and loads.

We introduce the Quantum Operating System (QOS), a unified system stack for managing quantum resources while mitigating their inherent limitations, namely their limited and noisy qubits, (temporal and spatial) heterogeneities, and load imbalance. QOS features the $\textit{QOS compiler}$ -- a modular and composable compiler for analyzing and optimizing quantum applications to run on small and noisy quantum devices with high performance and configurable overheads. For scalable execution of the optimized applications, we propose the $\textit{QOS runtime}$ -- an efficient quantum resource management system that multi-programs and schedules the applications across space and time while achieving high system utilization, low waiting times, and high-quality results. We evaluate QOS on real quantum devices hosted by IBM, using 7000 real quantum runs of more than 70.000 benchmark instances. We show that the QOS compiler achieves 2.6--456.5$\times$ higher quality results, while the QOS runtime further improves the quality by 1.15--9.6$\times$ and reduces the waiting times by up to 5$\times$ while sacrificing only 1--3\% of results quality (or fidelity).

We present the Quantum Virtual Machine (QVM), an end-to-end generic system for scalable execution of large quantum circuits with high fidelity on noisy and small quantum processors (QPUs) by leveraging gate virtualization. QVM exposes a virtual circuit intermediate representation (IR) that extends the notion of quantum circuits to incorporate gate virtualization. Based on the virtual circuit as our IR, we propose the QVM compiler - an extensible compiler infrastructure to transpile a virtual circuit through a series of modular optimization passes to produce a set of optimized circuit fragments. Lastly, these transpiled circuit fragments are executed on QPUs using our QVM runtime - a scalable and distributed infrastructure to virtualize and execute circuit fragments on a set of distributed QPUs. We evaluate QVM on IBM's 7- and 27-qubit QPUs. Our evaluation shows that using our system, we can scale the circuit sizes executable on QPUs up to double the size of the QPU while improving fidelity by 4.7$\times$ on average compared to larger QPUs and that we can effectively reduce circuit depths to only 40\% of the original circuit depths.

Fault-tolerance techniques depend on replication to enhance availability, albeit at the cost of increased infrastructure costs. This results in a fundamental trade-off: Fault-tolerant services must satisfy given availability and performance constraints while minimising the number of replicated resources. These constraints pose capacity planning challenges for the service operators to minimise replication costs without negatively impacting availability. To this end, we present PCRAFT, a system to enable capacity planning of dependable services. PCRAFT's capacity planning is based on a hybrid approach that combines empirical performance measurements with probabilistic modelling of availability based on fault injection. In particular, we integrate traditional service-level availability mechanisms (active route anywhere and passive failover) and deployment schemes (cloud and on-premises) to quantify the number of nodes needed to satisfy the given availability and performance constraints. Our evaluation based on real-world applications shows that cloud deployment requires fewer nodes than on-premises deployments. Additionally, when considering on-premises deployments, we show how passive failover requires fewer nodes than active route anywhere. Furthermore, our evaluation quantify the quality enhancement given by additional integrity mechanisms and how this affects the number of nodes needed., Comment: 11 pages

Data-driven intelligent applications in modern online services have become ubiquitous. These applications are usually hosted in the untrusted cloud computing infrastructure. This poses significant security risks since these applications rely on applying machine learning algorithms on large datasets which may contain private and sensitive information. To tackle this challenge, we designed secureTF, a distributed secure machine learning framework based on Tensorflow for the untrusted cloud infrastructure. secureTF is a generic platform to support unmodified TensorFlow applications, while providing end-to-end security for the input data, ML model, and application code. secureTF is built from ground-up based on the security properties provided by Trusted Execution Environments (TEEs). However, it extends the trust of a volatile memory region (or secure enclave) provided by the single node TEE to secure a distributed infrastructure required for supporting unmodified stateful machine learning applications running in the cloud. The paper reports on our experiences about the system design choices and the system deployment in production use-cases. We conclude with the lessons learned based on the limitations of our commercially available platform, and discuss open research problems for the future work., Comment: arXiv admin note: text overlap with arXiv:1902.04413

A lease is an important primitive for building distributed protocols, and it is ubiquitously employed in distributed systems. However, the scope of the classic lease abstraction is restricted to the trusted computing infrastructure. Unfortunately, this important primitive cannot be employed in the untrusted computing infrastructure because the trusted execution environments (TEEs) do not provide a trusted time source. In the untrusted environment, an adversary can easily manipulate the system clock to violate the correctness properties of lease-based systems. We tackle this problem by introducing trusted lease -- a lease that maintains its correctness properties even in the presence of a clock-manipulating attacker. To achieve these properties, we follow a "trust but verify" approach for an untrusted timer, and transform it into a trusted timing primitive by leveraging two hardware-assisted ISA extensions (Intel TSX and SGX) available in commodity CPUs. We provide a design and implementation of trusted lease in a system called T-Lease -- the first trusted lease system that achieves high security, performance, and precision. For the application developers, T-Lease exposes an easy-to-use generic APIs that facilitate its usage to build a wide range of distributed protocols.

Page placement is a critical problem for memoryintensive applications running on a shared-memory multiprocessor with a non-uniform memory access (NUMA) architecture. State-of-the-art page placement mechanisms interleave pages evenly across NUMA nodes. However, this approach fails to maximize memory throughput in modern NUMA systems, characterised by asymmetric bandwidths and latencies, and sensitive to memory contention and interconnect congestion phenomena. We propose BWAP, a novel page placement mechanism based on asymmetric weighted page interleaving. BWAP combines an analytical performance model of the target NUMA system with on-line iterative tuning of page distribution for a given memory-intensive application. Our experimental evaluation with representative memory-intensive workloads shows that BWAP performs up to 66% better than state-of-the-art techniques. These gains are particularly relevant when multiple co-located applications run in disjoint partitions of a large NUMA machine or when applications do not scale up to the total number of cores.

System level provenance is of widespread interest for applications such as security enforcement and information protection. However, testing the correctness or completeness of provenance capture tools is challenging and currently done manually. In some cases there is not even a clear consensus about what behavior is correct. We present an automated tool, ProvMark, that uses an existing provenance system as a black box and reliably identifies the provenance graph structure recorded for a given activity, by a reduction to subgraph isomorphism problems handled by an external solver. ProvMark is a beginning step in the much needed area of testing and comparing the expressiveness of provenance systems. We demonstrate ProvMark's usefuless in comparing three capture systems with different architectures and distinct design philosophies., Comment: To appear, Middleware 2019

Machine learning has become a critical component of modern data-driven online services. Typically, the training phase of machine learning techniques requires to process large-scale datasets which may contain private and sensitive information of customers. This imposes significant security risks since modern online services rely on cloud computing to store and process the sensitive data. In the untrusted computing infrastructure, security is becoming a paramount concern since the customers need to trust the thirdparty cloud provider. Unfortunately, this trust has been violated multiple times in the past. To overcome the potential security risks in the cloud, we answer the following research question: how to enable secure executions of machine learning computations in the untrusted infrastructure? To achieve this goal, we propose a hardware-assisted approach based on Trusted Execution Environments (TEEs), specifically Intel SGX, to enable secure execution of the machine learning computations over the private and sensitive datasets. More specifically, we propose a generic and secure machine learning framework based on Tensorflow, which enables secure execution of existing applications on the commodity untrusted infrastructure. In particular, we have built our system called TensorSCONE from ground-up by integrating TensorFlow with SCONE, a shielded execution framework based on Intel SGX. The main challenge of this work is to overcome the architectural limitations of Intel SGX in the context of building a secure TensorFlow system. Our evaluation shows that we achieve reasonable performance overheads while providing strong security properties with low TCB.

The join operation is a fundamental building block of parallel data processing. Unfortunately, it is very resource-intensive to compute an equi-join across massive datasets. The approximate computing paradigm allows users to trade accuracy and latency for expensive data processing operations. The equi-join operator is thus a natural candidate for optimization using approximation techniques. Although sampling-based approaches are widely used for approximation, sampling over joins is a compelling but challenging task regarding the output quality. Naive approaches, which perform joins over dataset samples, would not preserve statistical properties of the join output. To realize this potential, we interweave Bloom filter sketching and stratified sampling with the join computation in a new operator, ApproxJoin, that preserves the statistical properties of the join output. ApproxJoin leverages a Bloom filter to avoid shuffling non-joinable data items around the network and then applies stratified sampling to obtain a representative sample of the join output. Our analysis shows that ApproxJoin scales well and significantly reduces data movement, without sacrificing tight error bounds on the accuracy of the final results. We implemented ApproxJoin in Apache Spark and evaluated ApproxJoin using microbenchmarks and real-world case studies. The evaluation shows that ApproxJoin achieves a speedup of 6-9x over unmodified Spark-based joins with the same sampling rate. Furthermore, the speedup is accompanied by a significant reduction in the shuffled data volume, which is 5-82x less than unmodified Spark-based joins.

IoT-enabled devices continue to generate a massive amount of data. Transforming this continuously arriving raw data into timely insights is critical for many modern online services. For such settings, the traditional form of data analytics over the entire dataset would be prohibitively limiting and expensive for supporting real-time stream analytics. In this work, we make a case for approximate computing for data analytics in IoT settings. Approximate computing aims for efficient execution of workflows where an approximate output is sufficient instead of the exact output. The idea behind approximate computing is to compute over a representative sample instead of the entire input dataset. Thus, approximate computing - based on the chosen sample size - can make a systematic trade-off between the output accuracy and computation efficiency. This motivated the design of APPROXIOT - a data analytics system for approximate computing in IoT. To realize this idea, we designed an online hierarchical stratified reservoir sampling algorithm that uses edge computing resources to produce approximate output with rigorous error bounds. To showcase the effectiveness of our algorithm, we implemented APPROXIOT based on Apache Kafka and evaluated its effectiveness using a set of microbenchmarks and real-world case studies. Our results show that APPROXIOT achieves a speedup 1.3X-9.9X with varying sampling fraction of 80% to 10% compared to simple random sampling.

Major cloud computing operators provide powerful monitoring tools to understand the current (and prior) state of the distributed systems deployed in their infrastructure. While such tools provide a detailed monitoring mechanism at scale, they also pose a significant challenge for the application developers/operators to transform the huge space of monitored metrics into useful insights. These insights are essential to build effective management tools for improving the efficiency, resiliency, and dependability of distributed systems. This paper reports on our experience with building and deploying Sieve - a platform to derive actionable insights from monitored metrics in distributed systems. Sieve builds on two core components: a metrics reduction framework, and a metrics dependency extractor. More specifically, Sieve first reduces the dimensionality of metrics by automatically filtering out unimportant metrics by observing their signal over time. Afterwards, Sieve infers metrics dependencies between distributed components of the system using a predictive-causality model by testing for Granger Causality. We implemented Sieve as a generic platform and deployed it for two microservices-based distributed systems: OpenStack and ShareLatex. Our experience shows that (1) Sieve can reduce the number of metrics by at least an order of magnitude (10 - 100$\times$), while preserving the statistical equivalence to the total number of monitored metrics; (2) Sieve can dramatically improve existing monitoring infrastructures by reducing the associated overheads over the entire system stack (CPU - 80%, storage - 90%, and network - 50%); (3) Lastly, Sieve can be effective to support a wide-range of workflows in distributed systems - we showcase two such workflows: orchestration of autoscaling, and Root Cause Analysis (RCA)., Comment: This technical report is an extended version of our conference publication: J\"org Thalheim, Antonio Rodrigues, Istemi Ekin Akkus, Pramod Bhatotia, Ruichuan Chen, Bimal Viswanath, Lei Jiao, and Christof Fetzer. Sieve: Actionable Insights from Monitored Metrics in Distributed Systems. In Proceedings of Middleware '17, Las Vegas, NV, USA, December 11 - 15, 2017

Cloud computing offers the economies of scale for computational resources with the ease of management, elasticity, and fault tolerance. To take advantage of these benefits, many enterprises are contemplating to outsource the middlebox processing services in the cloud. However, middleboxes that process confidential and private data cannot be securely deployed in the untrusted environment of the cloud. To securely outsource middleboxes to the cloud, the state-of-the-art systems advocate network processing over the encrypted traffic. Unfortunately, these systems support only restrictive middlebox functionalities, and incur prohibitively high overheads due to the complex computations involved over the encrypted traffic. This motivated the design of Slick --- a secure middlebox framework for deploying high-performance Network Functions (NFs) on untrusted commodity servers. Slick exposes a generic interface based on Click to design and implement a wide-range of NFs using its out-of-the box elements and C++ extensions. Slick leverages SCONE (a shielded execution framework based on Intel SGX) and DPDK to securely process confidential data at line rate. More specifically, Slick provides hardware-assisted memory protection, and configuration and attestation service for seamless and verifiable deployment of middleboxes. We have also added several new features for commonly required functionalities: new specialized Click elements for secure packet processing, secure shared memory packet transfer for NFs chaining, secure state persistence, an efficient on-NIC timer for SGX enclaves, and memory safety against DPDK-specific Iago attacks. Furthermore, we have implemented several SGX-specific optimizations in Slick. Our evaluation shows that Slick achieves near-native throughput and latency.

Approximate computing aims for efficient execution of workflows where an approximate output is sufficient instead of the exact output. The idea behind approximate computing is to compute over a representative sample instead of the entire input dataset. Thus, approximate computing - based on the chosen sample size - can make a systematic trade-off between the output accuracy and computation efficiency. Unfortunately, the state-of-the-art systems for approximate computing primarily target batch analytics, where the input data remains unchanged during the course of sampling. Thus, they are not well-suited for stream analytics. This motivated the design of StreamApprox - a stream analytics system for approximate computing. To realize this idea, we designed an online stratified reservoir sampling algorithm to produce approximate output with rigorous error bounds. Importantly, our proposed algorithm is generic and can be applied to two prominent types of stream processing systems: (1) batched stream processing such as Apache Spark Streaming, and (2) pipelined stream processing such as Apache Flink. We evaluated StreamApprox using a set of microbenchmarks and real-world case studies. Our results show that Spark- and Flink-based StreamApprox systems achieve a speedup of $1.15\times$-$3\times$ compared to the respective native Spark Streaming and Flink executions, with varying sampling fraction of $80\%$ to $10\%$. Furthermore, we have also implemented an improved baseline in addition to the native execution baseline - a Spark-based approximate computing system leveraging the existing sampling modules in Apache Spark. Compared to the improved baseline, our results show that StreamApprox achieves a speedup $1.1\times$-$2.4\times$ while maintaining the same accuracy level.

Memory-safety violations are a prevalent cause of both reliability and security vulnerabilities in systems software written in unsafe languages like C/C++. Unfortunately, all the existing software-based solutions to this problem exhibit high performance overheads preventing them from wide adoption in production runs. To address this issue, Intel recently released a new ISA extension - Memory Protection Extensions (Intel MPX), a hardware-assisted full-stack solution to protect against memory safety violations. In this work, we perform an exhaustive study of the Intel MPX architecture to understand its advantages and caveats. We base our study along three dimensions: (a) performance overheads, (b) security guarantees, and (c) usability issues. To put our results in perspective, we compare Intel MPX with three prominent software-based approaches: (1) trip-wire - AddressSanitizer, (2) object-based - SAFECode, and (3) pointer-based - SoftBound. Our main conclusion is that Intel MPX is a promising technique that is not yet practical for widespread adoption. Intel MPX's performance overheads are still high (roughly 50% on average), and the supporting infrastructure has bugs which may cause compilation or runtime errors. Moreover, we showcase the design limitations of Intel MPX: it cannot detect temporal errors, may have false positives and false negatives in multithreaded code, and its restrictions on memory layout require substantial code changes for some programs.

How to preserve users' privacy while supporting high-utility analytics for low-latency stream processing? To answer this question: we describe the design, implementation, and evaluation of PRIVAPPROX, a data analytics system for privacy-preserving stream processing. PRIVAPPROX provides three properties: (i) Privacy: zero-knowledge privacy guarantees for users, a privacy bound tighter than the state-of-the-art differential privacy; (ii) Utility: an interface for data analysts to systematically explore the trade-offs between the output accuracy (with error-estimation) and query execution budget; (iii) Latency: near real-time stream processing based on a scalable "synchronization-free" distributed architecture. The key idea behind our approach is to marry two existing techniques together: namely, sampling (used in the context of approximate computing) and randomized response (used in the context of privacy-preserving analytics). The resulting marriage is complementary - it achieves stronger privacy guarantees and also improves performance, a necessary ingredient for achieving low-latency stream analytics.

Data provenance strives for explaining how the computation was performed by recording a trace of the execution. The provenance trace is useful across a wide-range of workflows to improve the dependability, security, and efficiency of software systems. In this paper, we present Inspector, a POSIX-compliant data provenance library for shared-memory multithreaded programs. The Inspector library is completely transparent and easy to use: it can be used as a replacement for the pthreads library by a simple exchange of libraries linked, without even recompiling the application code. To achieve this result, we present a parallel provenance algorithm that records control, data, and schedule dependencies using a Concurrent Provenance Graph (CPG). We implemented our algorithm to operate at the compiled binary code level by leveraging a combination of OS-specific mechanisms, and recently released Intel PT ISA extensions as part of the Broadwell micro-architecture. Our evaluation on a multicore platform using applications from multithreaded benchmarks suites (PARSEC and Phoenix) shows reasonable provenance overheads for a majority of applications. Lastly, we briefly describe three case-studies where the generic interface exported by Inspector is being used to improve the dependability, security, and efficiency of systems. The Inspector library is publicly available for further use in a wide range of other provenance workflows., Comment: 13 pages

In this paper, we present asymptotic analysis of self-adjusting contraction trees for incremental sliding window analytics.

Instruction-Level Redundancy (ILR) is a well-known approach to tolerate transient CPU faults. It replicates instructions in a program and inserts periodic checks to detect and correct CPU faults using majority voting, which essentially requires three copies of each instruction and leads to high performance overheads. As SIMD technology can operate simultaneously on several copies of the data, it appears to be a good candidate for decreasing these overheads. To verify this hypothesis, we propose Elzar, a compiler framework that transforms unmodified multithreaded applications to support triple modular redundancy using Intel AVX extensions for vectorization. Our experience with several benchmark suites and real-world case-studies yields mixed results: while SIMD may be beneficial for some workloads, e.g., CPU-intensive ones with many floating-point operations, it exhibits higher overhead than ILR in many applications we tested. We study the sources of overheads and discuss possible improvements to Intel AVX that would lead to better performance., Comment: Short version of this report appeared in the 46th IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'2016) under the title "ELZAR: Triple Modular Redundancy using Intel Advanced Vector Extensions (practical experience report)"