Events 2020

Learning by exploration in an unknown and changing environment

Qingyun Wu University of Virginia
27 Feb 2020, 2:00 pm - 3:00 pm
Saarbrücken building E1 5, room SB 029
simultaneous videocast to Kaiserslautern building G26, room KL 111 / Meeting ID: 6312
SWS Colloquium
Learning is a predominant theme for any intelligent system, humans or machines. Moving beyond the classical paradigm of learning from past experience, e.g., supervised learning from given labels, a learner needs to actively collect exploratory feedback to learn the unknowns. Considerable challenges arise in such a setting, including sample complexity, costly and even outdated feedback.

In this talk, I will introduce our themed efforts on developing solutions to efficiently explore the unknowns and dynamically adjust to the changes through exploratory feedback. …
Learning is a predominant theme for any intelligent system, humans or machines. Moving beyond the classical paradigm of learning from past experience, e.g., supervised learning from given labels, a learner needs to actively collect exploratory feedback to learn the unknowns. Considerable challenges arise in such a setting, including sample complexity, costly and even outdated feedback.

In this talk, I will introduce our themed efforts on developing solutions to efficiently explore the unknowns and dynamically adjust to the changes through exploratory feedback. Specifically, I will first present our studies in leveraging special problem structures for efficient exploration. Then I will present our work on empowering the learner to detect and adjust to potential changes in the environment adaptively. Besides, I will also highlight the impact our research has generated in top-valued industry applications, including online learning to rank and interactive recommendation.
Read more

Compactness in Cryptography

Giulio Malavolta UC Berkeley and CMU
25 Feb 2020, 10:00 am - 11:00 am
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111 / Meeting ID: 6312
SWS Colloquium
The communication complexity of secure protocols is a fundamental question of the theory of computation and has important repercussions in the development of real-life systems. As an example, the recent surge in popularity of cryptocurrencies has been enabled and accompanied by advancements in the construction of more compact cryptographic machinery. In this talk we discuss how to meet the boundaries of compactness in cryptography and how to exploit succinct communication to construct systems with new surprising properties. …
The communication complexity of secure protocols is a fundamental question of the theory of computation and has important repercussions in the development of real-life systems. As an example, the recent surge in popularity of cryptocurrencies has been enabled and accompanied by advancements in the construction of more compact cryptographic machinery. In this talk we discuss how to meet the boundaries of compactness in cryptography and how to exploit succinct communication to construct systems with new surprising properties. Specifically, we consider the problem of computing functions on encrypted data: We show how to construct a fully-homomorphic encryption scheme with message-to-ciphertext ratio (i.e. rate) of 1 – o(1), which is optimal. Along the way, we survey the implication of cryptographic compactness in different contexts, such as proof systems, scalable blockchains, and fair algorithms.
Read more

Software Testing as Species Discovery

Marcel Böhme Monash University
10 Feb 2020, 10:00 am - 11:00 am
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111 / Meeting ID: 6312
SWS Colloquium
A fundamental challenge of software testing is the statistically well-grounded extrapolation from program behaviors observed during testing. For instance, a security researcher who has run the fuzzer for a week has currently no means (i) to estimate the total number of feasible program branches, given that only a fraction has been covered so far, (ii) to estimate the additional time required to cover 10% more branches (or to estimate the coverage achieved in one more day, …
A fundamental challenge of software testing is the statistically well-grounded extrapolation from program behaviors observed during testing. For instance, a security researcher who has run the fuzzer for a week has currently no means (i) to estimate the total number of feasible program branches, given that only a fraction has been covered so far, (ii) to estimate the additional time required to cover 10% more branches (or to estimate the coverage achieved in one more day, resp.), or (iii) to assess the residual risk that a vulnerability exists when no vulnerability has been discovered. Failing to discover a vulnerability, does not mean that none exists—even if the fuzzer was run for a week (or a year). Hence, testing provides no formal correctness guarantees.

In this talk, I establish an unexpected connection with the otherwise unrelated scientific field of ecology, and introduce a statistical framework that models Software Testing and Analysis as Discovery of Species (STADS). For instance, in order to study the species diversity of arthropods in a tropical rain forest, ecologists would first sample a large number of individuals from that forest, determine their species, and extrapolate from the properties observed in the sample to properties of the whole forest. The estimation (i) of the total number of species, (ii) of the additional sampling effort required to discover 10% more species, or (iii) of the probability to discover a new species are classical problems in ecology. The STADS framework draws from over three decades of research in ecological biostatistics to address the fundamental extrapolation challenge for automated test generation. Our preliminary empirical study demonstrates a good estimator performance even for a fuzzer with adaptive sampling bias—AFL, a state-of-the-art vulnerability detection tool. The STADS framework provides statistical correctness guarantees with quantifiable accuracy.
Read more

Hybrid optimization techniques for multi-domain coupling in cyber-physical systems design

Debayan Roy TU Munich
07 Feb 2020, 3:00 pm - 4:00 pm
Kaiserslautern building G26, room 111
simultaneous videocast to Saarbrücken building E1 5, room 029 / Meeting ID: 6312
SWS Colloquium
In a cyber-physical system (CPS), a physical process is controlled by software running on a cyber platform. And there exists a strong interaction between the physical dynamics, the control software, the sensors and actuators, and the cyber resources (i.e., computation, communication, and memory resources). These systems are common in domains such as automotive, avionics, health-care, smart manufacturing, smart grid, among others. The state-of-practice is to design CPSs using a disjoint set of tools handling different design domains. …
In a cyber-physical system (CPS), a physical process is controlled by software running on a cyber platform. And there exists a strong interaction between the physical dynamics, the control software, the sensors and actuators, and the cyber resources (i.e., computation, communication, and memory resources). These systems are common in domains such as automotive, avionics, health-care, smart manufacturing, smart grid, among others. The state-of-practice is to design CPSs using a disjoint set of tools handling different design domains. Such a design methodology has proved to be inefficient with respect to resource usage and performance. In this talk, I will discuss how models from different engineering disciplines can be integrated to design efficient cyber-physical systems. In particular, I will show two use-cases. First, I will talk about a multi-resource platform consisting of high- and low-quality resources. Correspondingly, I will show that a cost-efficient switching control strategy can be designed exploiting heterogeneous resources and by effectively managing the interplay between control theory, scheduling and formal verification. Second, I will talk about the cyber-physical battery management systems (BMS) for high-power battery packs. I will specifically discuss the problem of cell balancing which is an important task of BMS. I will show how integrated modeling of the individual cells, battery architecture, control circuits, and cyber architecture, can lead to energy- and time-efficient scheduling for active cell balancing.
Read more

Designing responsible information systems

Asia J. Biega Microsoft Research Montreal, Canada
07 Feb 2020, 10:00 am - 11:00 am
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111 / Meeting ID: 6312
SWS Colloquium
Information systems have the potential to enhance or limit opportunities when mediating user interactions. They also have the potential to violate privacy by accumulating observational data into detailed user profiles or by exposing people in sensitive contexts. This talk will cover measures and mechanisms we have proposed for mitigating various threats to user well-being in online information ecosystems. In particular, I am going to focus on two contributions in the areas of algorithmic fairness and privacy. …
Information systems have the potential to enhance or limit opportunities when mediating user interactions. They also have the potential to violate privacy by accumulating observational data into detailed user profiles or by exposing people in sensitive contexts. This talk will cover measures and mechanisms we have proposed for mitigating various threats to user well-being in online information ecosystems. In particular, I am going to focus on two contributions in the areas of algorithmic fairness and privacy. The first contribution demonstrates how to operationalize the notion of equity in the context of search systems and how to design optimization models that achieve equity while accounting for human cognitive biases. The second ties our empirical work on profiling privacy and data collection to concepts in data protection laws. Finally, I will discuss the necessity for a holistic approach to responsible technology, from studying different types of harms, through development of different types of interventions, up to taking a step back and refusing technologies that cannot be fixed by technical tweaks.
Read more

Spectector: Principled Detection of Speculative Information Flows

Jan Reineke Fachrichtung Informatik - Saarbrücken
05 Feb 2020, 12:15 pm - 1:15 pm
Saarbrücken building E1 5, room 002
Joint Lecture Series
The recent Spectre attacks exploit speculative execution and microarchitectural side channels, such as caches, to leak sensitive information. Since the underlying hardware vulnerabilities are here to stay in billions of deployed devices, software countermeasures have been developed. Rigorously reasoning about their effectiveness, however, requires a well-defined notion of security against speculative execution attacks, which has been missing until now. We put forward speculative non-interference, the first semantic notion of security against speculative execution attacks, and we develop Spectector, …
The recent Spectre attacks exploit speculative execution and microarchitectural side channels, such as caches, to leak sensitive information. Since the underlying hardware vulnerabilities are here to stay in billions of deployed devices, software countermeasures have been developed. Rigorously reasoning about their effectiveness, however, requires a well-defined notion of security against speculative execution attacks, which has been missing until now. We put forward speculative non-interference, the first semantic notion of security against speculative execution attacks, and we develop Spectector, an algorithm based on symbolic execution to automatically prove speculative non-interference, or to detect violations. We implement Spectector in a tool, which we use to detect subtle leaks and optimizations opportunities in the way major compilers place Spectre countermeasures.
Read more

veribetrfs: Verification as a Practical Engineering Tool

Jon Howell VMware Research, Bellevue, WA, USA
17 Jan 2020, 10:30 am - 11:30 am
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 111 / Meeting ID: VMR 6312
SWS Distinguished Lecture Series
Recent progress in systems verification have shown that verification techniques can scale to thousands of lines. It is time to ask whether verification can displace testing as an effective path to software correctness. The veribetrfs project is developing a verified high-performance storage system. A primary goal of the project is to reduce verification methodology to engineering practice. Veribetrfs is developed using the Iron★ methodology, a descendent of the Ironclad and IronFleet projects. So far, we have a key-value store with 100k iops performance and strong guarantees against data loss. …
Recent progress in systems verification have shown that verification techniques can scale to thousands of lines. It is time to ask whether verification can displace testing as an effective path to software correctness. The veribetrfs project is developing a verified high-performance storage system. A primary goal of the project is to reduce verification methodology to engineering practice. Veribetrfs is developed using the Iron★ methodology, a descendent of the Ironclad and IronFleet projects. So far, we have a key-value store with 100k iops performance and strong guarantees against data loss. This talk will give an overview of the methodology and describe how we have enhanced it in veribetrfs. 
Read more

Information Consumption on Social Media: Efficiency, Divisiveness, and Trust

Mahmoudreza Babaei Max Planck Institute for Software Systems
17 Jan 2020, 10:00 am - 11:00 am
Saarbrücken building E1 5, room 029
simultaneous videocast to Kaiserslautern building G26, room 113 / Meeting ID: 6312
SWS Student Defense Talks - Thesis Proposal
Over the last decade, the advent of social media has profoundly changed the way people produce and consume information online. On these platforms, users themselves play a role in selecting the sources from which they consume information, overthrowing traditional journalistic gatekeeping. Moreover, advertisers can target users with news stories using users’ personal data.

This new model has many advantages: the propagation of news is faster, the number of news sources is large, and the topics covered are diverse. …
Over the last decade, the advent of social media has profoundly changed the way people produce and consume information online. On these platforms, users themselves play a role in selecting the sources from which they consume information, overthrowing traditional journalistic gatekeeping. Moreover, advertisers can target users with news stories using users’ personal data.

This new model has many advantages: the propagation of news is faster, the number of news sources is large, and the topics covered are diverse. However, in this new model, users are often overloaded with redundant information, and they can get trapped in filter bubbles by consuming divisive and potentially false information. To tackle these concerns, in my thesis, I address the following important questions: • (i) How efficient are users at selecting their information sources? We have defined three intuitive notions of users’ efficiency in social media – link (the number of sources the user follows), in-flow (the amount of redundant information she acquires), and delay efficiency (the delay with which she receives the information). We use these three measures to assess how good users are at selecting who to follow within the social media system in order to acquire information most efficiently. • (ii) How can we break the filter bubbles that users get trapped in? Users on social media sites such as Twitter often get trapped in filter bubbles by being exposed to radical, highly partisan, or divisive information. To prevent users from getting trapped in filter bubbles, we propose an approach to inject diversity in users’ information consumption by identifying non-divisive, yet informative information. We propose a new method to identify less divisive information on controversial topics using features such as the publishers’ political leaning. • (iii) How can we design an efficient framework for fact-checking? The proliferation of false information is a major problem in social media. To counter it, social media platforms typically rely on expert fact-checkers to detect false news. However, human fact-checkers can realistically only cover a tiny fraction of all stories. So, it is important to automatically prioritize and select a small number of stories for human to fact check. However, the goals for prioritizing stories for fact-checking are unclear.

We identify three desired objectives to prioritize news for fact-checking. These objectives are based on the users’ perception of the truthfulness of stories. Our key finding is that these three objectives are incompatible in practice.
Read more

Towards a Tight Understanding of the Complexity of Algorithmic Problems

Dániel Marx MPI-INF - D1
08 Jan 2020, 12:15 pm - 1:15 pm
Saarbrücken building E1 5, room 002
Joint Lecture Series
-