Instrumenting programs for performing run-time checking of properties, such as regular shapes, is a common and useful technique that helps programmers detect incorrect program behaviors. This is specially true in dynamic languages such as Prolog. However, such run-time checks inevitably introduce run-time overhead (in execution time, memory, energy, etc.). Several approaches have been proposed for reducing this overhead, such as eliminating the checks that can statically be proved to always succeed, and/or optimizing the way in which the (remaining) checks are performed. However, there are cases in which it is not possible to remove all checks statically (e.g., open libraries which must check their interfaces, complex properties, unknown code, etc.) and in which, even after optimizations, these remaining checks may still introduce an unacceptable level of overhead. It is thus important for programmers to be able to determine the additional cost due to the run-time checks and compare it to some notion of admissible cost. The common practice used for estimating run-time checking overhead is profiling, which is not exhaustive by nature. In this talk we propose a method that uses static analysis to estimate such overhead, with the advantage that the estimations are functions parameterized by input data sizes. Unlike profiling, this approach can provide guarantees for all possible execution traces, and allows assessing how the overhead grows as the size of the input grows. Our method also extends an existing assertion verification framework to express ``admissible'' overheads, and statically and automatically checks whether the instrumented program conforms with such specifications. Finally, we present an experimental evaluation of our approach that suggests that our method is feasible and promising.

In this talk, I will introduce you to Cross-Origin State Inference (COSI) attacks. In a COSI attack, an attacker convinces a victim into visiting an attack web page, which leverages the cross-origin interaction features of the victim’s web browser to infer the victim’s state at a target web site. COSI attacks can be leveraged to mount several privacy attacks on web users including determining whether the victim has an account or is the administrator of a prohibited web site, determining if the victim owns sensitive content hosted at a target web site, and identifying whether the victim is the owner of a specific account. While COSI attacks are not new, they have previously been considered as sparse attacks under different names. We systematically study COSI attacks as a comprehensive category, identify different classes of them, and propose an approach for detecting them. Although I will not get into the details of our detection approach (saving for another occasion), I will present the COSI attacks we found on popular live web sites including linkedin.com, blogger.com and drive.google.com. Finally, I will present the defenses for COSI attacks.

Transient resources—resources with transient availability offered by cloud providers at a discounted price—present an opportunity to reduce operational costs of running jobs in the cloud. Unfortunately, there are key problems that emerge when one attempts to use transient resources to reduce the cost of running time-constrained jobs in the cloud. Previous works fail to address these problems and are either not able to offer significant savings or miss termination deadlines. First, the fact that transient resources can be evicted, requiring the job to be re-started (even if not from scratch) may lead provisioning policies to fall-back to expensive on-demand configurations more often than desirable, or even to miss deadlines. Second, when a job is restarted, the new configuration can be different from the previous, which might make eviction recovery costly. In this talk, we present Hourglass, a system that addresses these issues by combining two novel techniques: a slack-aware provisioning strategy that selects configurations considering the remaining time before the job’s termination deadline, and a fast reload mechanism to quickly recover from evictions. By switching to an on-demand configuration when (but only if) the target deadline is at risk of not being met, we are able to obtain significant cost savings while always meeting the deadlines. Our results show that, unlike previous work, Hourglass is able to significantly reduce the operating costs in the order of 60 − 70% while guaranteeing that deadlines are met.

In this talk, I will present tail-call optimisation in a functional programming language in the presence of multiple evaluation orders (strict, lazy, call-by-name semantics). The source language, similar to Haskell, is transformed to a low-level, minimal, first-order functional language with non-strict semantics, lazy evaluation and lazy structured data as well as strictness annotations. To find opportunities for optimisation, I performed a static analysis on the low-level functional language, to spot tail-call positions. The interesting part, compared with languages with strict semantics, is that lazy semantics makes program values escape their context and thus finding tail-call positions is not trivial. This optimisation was evaluated on an interpreter of the language that explicitly allocates and measures frames, so that on tail-call positions found by the analysis, I could properly replace the unnecessary current frame's arguments with the arguments needed by the frame that represents the next function call. This optimisation either improves program run-time, or does not change it. Also, in the case of strict programs, the optimisation is equivalent to classic tail-call optimisation. In conclusion, in a non-strict, lazy-evaluated functional language with lazy data constructors and strictness annotations, for all benchmarks, there is always memory optimisation, and for the majority of them there is a significant memory optimisation with performance boost.

I'll present a study of the rate for continuously non-malleable codes. Such codes allow to encode a message in a way that continuous tampering attacks on the codeword yield a decoded value that is unrelated to the original message. The results are: • For the case of bit-wise independent tampering, we establish the existence of rate-one continuously non-malleable codes with information-theoretic security, in the plain model. • For the case of split-state tampering, we establish the existence of rate-one continuously non-malleable codes with computational security, in the (non-programmable) random oracle model. We further exhibit a rate-1/2 code and a rate-one code in the common reference string model, but the latter only withstands non-adaptive tampering. It is well known that computational security is inherent for achieving continuous non-malleability in the split-state model (even in the presence of non-adaptive tampering).

Everyone has heard about quantum computers and that they will compromise the current Internet security. Quantum computers use q-bits instead of the classical bits and, therefore, can represent an exponential number of states at once (this is called quantum superposition). But, what does that mean? Why some algorithms are dramatically speeded up in this paradigm? Are these computers really as powerful as the media makes us think? In the first talk driven by two speakers (to the best of our knowledge) in the history of the IMDEA S4 (Spring Software Seminar Series), we will give an overview on the model of quantum computation and its principles, focusing on Shor's algorithm for integer factorization. It is guaranteed that the audience will understand nothing and something at the same time.

Many micro-architectural attacks rely on the capability of an attacker to efficiently find small eviction sets: groups of virtual addresses that map to the same cache set. This capability has become a decisive primitive for cache sidechannel, rowhammer, and speculative execution attacks. Despite their importance, algorithms for finding small eviction sets have not been systematically studied in the literature. In this paper, we perform such a systematic study. We begin by formalizing the problem and analyzing the probability that a set of random virtual addresses is an eviction set. We then present novel algorithms, based on ideas from threshold group testing, that reduce random eviction sets to their minimal core in linear time, improving over the quadratic state-of-the-art. We complement the theoretical analysis of our algorithms with a rigorous empirical evaluation in which we identify and isolate factors that affect their reliability in practice, such as adaptive cache replacement strategies and TLB thrashing. Our results indicate that our algorithms enable finding small eviction sets much faster than before, and under conditions where this was previously deemed impractical.

Even though there have been a large number of proposals to accelerate databases using specialized hardware, often the opinion of the community is pessimistic: the performance and energy efficiency benefits of specialization are seen to be outweighed by the limitations of the proposed solutions and the additional complexity of including specialized hardware, such as field programmable gate arrays (FPGAs), in servers. Recently, however, as an effect of stagnating CPU performance, server architectures started to incorporate various programmable hardware and the availability of such components brings opportunities to databases. In the light of a shifting hardware landscape and emerging analytics workloads, it is time to revisit our stance on hardware acceleration. In this talk we highlight several challenges that have traditionally hindered the deployment of hardware acceleration in databases and explain how they have been alleviated or removed altogether by recent research results and the changing hardware landscape. We also highlight a new set of questions that emerge around deep integration of heterogeneous programmable hardware in tomorrow’s databases.