Biblio

Multi- and many-core systems are increasingly prevalent in embedded systems. Additionally, isolation requirements between different partitions and criticalities are gaining in importance. This difficult combination is not well addressed by current software systems. Parallel systems require consistency guarantees on shared data-structures often provided by locks that use predictable resource sharing protocols. However, as the number of cores increase, even a single shared cache-line (e.g. for the lock) can cause significant interference. In this paper, we present a clean-slate design of the SPeCK kernel, the next generation of our COMPOSITE OS, that attempts to provide a strong version of scalable predictability - where predictability bounds made on a single core, remain constant with an increase in cores. Results show that, despite using a non-preemptive kernel, it has strong scalable predictability, low average-case overheads, and demonstrates better response-times than a state-of-the-art preemptive system.

Cyber-physical systems (CPSs), due to their direct influence on the physical world, have to meet extended security and dependability requirements. This is particularly true for CPS that operate in close proximity to humans or that control resources that, when tampered with, put all our lives at stake. In this paper, we review the challenges and some early solutions that arise at the architectural and operating-system level when we require cyber-physical systems and CPS infrastructure to withstand advanced and persistent threats. We found that although some of the challenges we identified are already matched by rudimentary solutions, further research is required to ensure sustainable and dependable operation of physically exposed CPS infrastructure and, more importantly, to guarantee graceful degradation in case of malfunction or attack.

Today ICT networks are the economy's vital backbone. While their complexity continuously evolves, sophisticated and targeted cyber attacks such as Advanced Persistent Threats (APTs) become increasingly fatal for organizations. Numerous highly developed Intrusion Detection Systems (IDSs) promise to detect certain characteristics of APTs, but no mechanism which allows to rate, compare and evaluate them with respect to specific customer infrastructures is currently available. In this paper, we present BAESE, a system which enables vendor independent and objective rating and comparison of IDSs based on small sets of customer network data.

This paper presents a model to evaluate and select security countermeasures from a pool of candidates. The model performs industrial evaluation and simulations of the financial and technical impact associated to security countermeasures. The financial impact approach uses the Return On Response Investment (RORI) index to compare the expected impact of the attack when no response is enacted against the impact after applying security countermeasures. The technical impact approach evaluates the protection level against a threat, in terms of confidentiality, integrity, and availability. We provide a use case on malware attacks that shows the applicability of our model in selecting the best countermeasure against an Advanced Persistent Threat.

This paper considers a decentralized switched control problem where exact conditions for controller synthesis are obtained in the form of semidefinite programming (SDP). The formulation involves a discrete-time switched linear plant that has a nested structure, and whose system matrices switch between a finite number of values according to finite-state automation. The goal of this paper is to synthesize a commensurately nested switched controller to achieve a desired level of 2-induced norm performance. The nested structures of both plant and controller are characterized by block lower-triangular system matrices. For this setup, exact conditions are provided for the existence of a finite path-dependent synthesis. These include conditions for the completion of scaling matrices obtained through an extended matrix completion lemma.When individual controller dimensions are chosen at least as large as the plant, these conditions reduce to a set of linear matrix inequalities. The completion lemma also provides an algorithm to complete closed-loop scaling matrices, leading to inequalities for  ontroller synthesis that are solvable either algebraically or numerically through SDP.

The increasing size and complexity of massively parallel systems (e.g. HPC systems) is making it increasingly likely that individual circuits will produce erroneous results. For this reason, novel fault tolerance approaches are increasingly needed. Prior fault tolerance approaches often rely on checkpoint-rollback based schemes. Unfortunately, such schemes are primarily limited to rare error event scenarios as the overheads of such schemes become prohibitive if faults are common. In this paper, we propose a novel approach for algorithmic correction of faulty application outputs. The key insight for this approach is that even under high error scenarios, even if the result of an algorithm is erroneous, most of it is correct. Instead of simply rolling back to the most recent checkpoint and repeating the entire segment of computation, our novel resilience approach uses algorithmic error localization and partial recomputation to efficiently correct the corrupted results. We evaluate our approach in the specific algorithmic scenario of linear algebra operations, focusing on matrix-vector multiplication (MVM) and iterative linear solvers. We develop a novel technique for localizing errors in MVM and show how to achieve partial recomputation within this algorithm, and demonstrate that this approach both improves the performance of the Conjugate Gradient solver in high error scenarios by 3x-4x and increases the probability that it completes successfully by up to 60% with parallel experiments up to 100 nodes.

We study the Lp induced gain of discretetime linear switching systems with graph-constrained switching sequences. We first prove that, for stable systems in a minimal realization, for every p ≥ 1, the Lp-gain is exactly characterized through switching storage functions. These functions are shown to be the pth power of a norm. In order to consider general systems, we provide an algorithm for computing minimal realizations. These realizations are rectangular systems, with a state dimension that varies according to the mode of the system. We apply our tools to the study on the of L2-gain. We provide algorithms for its approximation, and provide a converse result for the existence of quadratic switching storage functions. We finally illustrate the results with a physically motivated example.

We introduce a novel framework for the stability analysis of discrete-time linear switching systems with switching sequences constrained by an automaton. The key element of the framework is the algebraic concept of multinorm, which associates a different norm per node of the automaton, and allows to exactly characterize stability. Building upon this tool, we develop the first arbitrarily accurate approximation schemes for estimating the constrained joint spectral radius ρˆ, that is the exponential growth rate of a switching system with constrained switching sequences. More precisely, given a relative accuracy r > 0, the algorithms compute an estimate of ρˆ within the range [ ˆρ, (1+r)ρˆ]. These algorithms amount to solve a well defined convex optimization program with known time-complexity, and whose size depends on the desired relative accuracy r > 0.

In this paper, we develop a new framework to analyze stability and stabilizability of Linear Switched Systems (LSS) as well as their gain computations. Our approach is based on a combination of state space operator descriptions and the Youla parametrization and provides a unified way for analysis and synthesis of LSS, and in fact of Linear Time Varying (LTV) systems, in any lp induced norm sense. By specializing to the l∞ case, we show how Linear Programming (LP) can be used to test stability, stabilizability and to synthesize stabilizing controllers that guarantee a near optimal closed-loop gain.

In this work we are interested in the stability and L2-gain of hybrid systems with linear flow dynamics, periodic time-triggered jumps and nonlinear possibly set-valued jump maps. This class of hybrid systems includes various interesting applications such as periodic event-triggered control. In this paper we also show that sampled-data systems with arbitrarily switching controllers can be captured in this framework by requiring the jump map to be set-valued. We provide novel conditions for the internal stability and L2-gain analysis of these systems adopting a lifting-based approach. In particular, we establish that the internal stability and contractivity in terms of an L2-gain smaller than 1 are equivalent to the internal stability and contractivity of a particular discretetime set-valued nonlinear system. Despite earlier works in this direction, these novel characterisations are the first necessary and sufficient conditions for the stability and the contractivity of this class of hybrid systems. The results are illustrated through multiple new examples.

In this paper we develop a new framework to analyze stability and stabilizability of Linear Switched Systems (LSS) as well as their gain computations. Our approach is based on a combination of state space operator descritions and the Youda parametrization and provides a unified way to analysis an synthesis of LSS and in fact of Linear Time Varying (LTV) systems, in any lp induced norm sense. By specializing to the l case, we show how Linear Programming (LP) can be used to test stability, stabiliazbility and to synthesize stabilizing controllers that guarantee a near optimal closed-loop gain.

Anonymous microblogging platforms, such as Whisper, Yik Yak, and Secret have emerged as important tools for sharing one’s thoughts without fear of judgment by friends, the public, or authorities. These platforms provide anonymity by allowing users to share content (e.g., short messages) with their peers without revealing authorship information to other users. However, recent advances in rumor source detection show that existing messaging protocols, including those used in the mentioned anonymous microblogging applications, leak authorship information when the adversary has global access to metadata. For example, if an adversary can see which users of a messaging service received a particular message, or the timestamps at which a subset of users received a given message, the adversary can infer the message author’s identity with high probability. We introduce a novel anonymous messaging protocol, which we call adaptive diffusion, that is designed to resist such adversaries. We show that adaptive diffusion spreads messages quickly while achieving provably-optimal anonymity guarantees for specific classes of connectivity networks. Simulations on real social network data show that adaptive diffusion effectively hides the location of the source on real-world networks.

Anonymous messaging platforms like Whisper and Yik Yak allow users to spread messages over a network (e.g., a social network) without revealing message authorship to other users. The spread of messages on these platforms can be modeled by a diffusion process over a graph. Recent advances in network analysis have revealed that such diffusion processes are vulnerable to author deanonymization by adversaries with access to metadata, such as timing information. In this work, we ask the fundamental question of how to propagate anonymous messages over a graph to make it difficult for adversaries to infer the source. In particular, we study the performance of a message propagation protocol called adaptive diffusion introduced in (Fanti et al., 2015). We prove that when the adversary has access to metadata at a fraction of corrupted graph nodes, adaptive diffusion achieves asymptotically optimal source-hiding and significantly outperforms standard diffusion. We further demonstrate empirically that adaptive diffusion hides the source effectively on real social networks.
 

Anonymous messaging applications have recently gained popularity as a means for sharing opinions without fear of judgment or repercussion. These messages propagate anonymously over a network, typically de ned by social connections or physical proximity. However, recent advances in rumor source detection show that the source of such an anonymous message can be inferred by certain statistical inference attacks. Adaptive di usion was recently proposed as a solution that achieves optimal source obfuscation over regular trees. However, in real social networks, the degrees difer from node to node, and adaptive di usion can be signicantly sub-optimal. This gap increases as the degrees become more irregular.

In order to quantify this gap, we model the underlying network as coming from standard branching processes with i.i.d. degree distributions. Building upon the analysis techniques from branching processes, we give an analytical characterization of the dependence of the probability of detection achieved by adaptive di usion on the degree distribution. Further, this analysis provides a key insight: passing a rumor to a friend who has many friends makes the source more ambiguous. This leads to a new family of protocols that we call Preferential Attachment Adaptive Di usion (PAAD). When messages are propagated according to PAAD, we give both the MAP estimator for nding the source and also an analysis of the probability of detection achieved by this adversary. The analytical results are not directly comparable, since the adversary's observed information has a di erent distribution under adaptive di usion than under PAAD. Instead, we present results from numerical experiments that suggest that PAAD achieves a lower probability of detection, at the cost of increased communication for coordination.

In a multiagent system, a (social) norm describes what the agents may expect from each other.  Norms promote autonomy (an agent need not comply with a norm) and heterogeneity (a norm describes interactions at a high level independent of implementation details). Researchers have studied norm emergence through social learning where the agents interact repeatedly in a graph structure.

In contrast, we consider norm emergence in an open system, where membership can change, and where no predetermined graph structure exists.  We propose Silk, a mechanism wherein a generator monitors interactions among member agents and recommends norms to help resolve conflicts.  Each member decides on whether to accept or reject a recommended norm.  Upon exiting the system, a member passes its experience along to incoming members of the same type.  Thus, members develop norms in a hybrid manner to resolve conflicts.

We evaluate Silk via simulation in the traffic domain.  Our results show that social norms promoting conflict resolution emerge in both moderate and selfish societies via our hybrid mechanism.

To help establish a more scientific basis for security science, which will enable the development of fundamental theories and move the field from being primarily reactive to primarily proactive, it is important for research results to be reported in a scientifically rigorous manner. Such reporting will allow for the standard pillars of science, namely replication, meta-analysis, and theory building. In this paper we aim to establish a baseline of the state of scientific work in security through the analysis of indicators of scientific research as reported in the papers from the 2015 IEEE Symposium on Security and Privacy. To conduct this analysis, we developed a series of rubrics to determine the completeness of the papers relative to the type of evaluation used (e.g. case study, experiment, proof). Our findings showed that while papers are generally easy to read, they often do not explicitly document some key information like the research objectives, the process for choosing the cases to include in the studies, and the threats to validity. We hope that this initial analysis will serve as a baseline against which we can measure the advancement of the science of security.