Cache side-channels are a major threat to cryptographic implementations, particularly block ciphers. Traditional manual hardening methods transform block ciphers into Boolean circuits, a practice refined since the late 90s. The only existing automatic approach based on Boolean circuits achieves security but suffers from performance issues. This paper examines the use of Lookup Tables (LUTs) for automatic hardening of block ciphers against cache side-channel attacks. We present a novel method combining LUT-based synthesis with quantitative static analysis in our HyCaMi framework. Applied to seven block cipher implementations, HyCaMi shows significant improvement in efficiency, being 9.5× more efficient than previous methods, while effectively protecting against cache side-channel attacks. Additionally, for the first time, we explore balancing speed with security by adjusting LUT sizes, providing faster performance with slightly reduced leakage guarantees, suitable for scenarios where absolute security and speed must be balanced.

High-level synthesis (HLS) can be used to create hardware accelerators for compute-intense software parts such as loop structures. Usually, this process requires significant amount of user interaction to steer kernel selection and optimizations. This can be tedious and time-consuming. In this article, we present an approach that fully autonomously finds independent loop iterations and reductions to create parallelized accelerators. We combine static analysis with information available only at runtime to maximize the parallelism exploited by the created accelerators. For loops where we see potential for parallelism, we create fully parallelized kernel implementations. If static information does not suffice to deduce independence, then we assume independence at compile time. We verify this assumption by statically created checks that are dynamically evaluated at runtime, before using the optimized kernel. Evaluating our approach, we can generate speedups for five out of seven benchmarks. With four loop iterations running in parallel, we achieve ideal speedups of up to 4× and on average speedups of 2.27×, both in comparison to an unoptimized accelerator.

The size and complexity of high-performance computing applications present a serious challenge to manual reasoning about program behavior. The vastness and diversity of code bases often break automatic analysis tools, which could otherwise be used. As a consequence, developers resort to mini-apps, i.e., trimmed-down proxies of the original programs that retain key performance characteristics. Unfortunately, their construction is difficult and time consuming and prevents their mass production. In this paper, we propose a systematic and tool-supported approach to extract mini-apps from large-scale applications that reduces the manual effort needed to create them. Our approach covers the stages kernel identification, data capture, code extraction and representativeness validation. We demonstrate it using an astrophysics simulation with ≈ 8.5 million lines of code and extract a mini-app with only ≈ 1, 100 lines of code. For the mini-app, we evaluate the reduction of code complexity and execution similarity, and show how it enables the tool-supported discovery of unexploited parallelization opportunities, reducing the simulation’s runtime significantly.

Attack trees are a popular graphical notation for capturing threats to IT systems. They can be used to describe attacks in terms of attacker goals and attacker actions. By focusing on the viewpoint of a single attacker and on a particular attacker goal in the creation of an attack tree, one reduces the conceptual complexity of threat modeling substantially. Aspects not covered by attack trees, like the behavior of the system under attack, can then be described using other models to enable a security analysis based on a combination of the models.

Attack trees are a popular notation for describing threats to systems, both in academia and industry. Originally, attack trees lacked a formal semantics, but formal semantics for different variants of attack trees were proposed later. These semantics focus on the attacker's actions defined in the leaves and the logical structure defined by the inner nodes of an attack tree. Surprisingly, they do not clarify the connection to the goal defined at the root node in a satisfactory fashion. In this article, we aim at a better clarification of this connection between the attacks and the attacker goal specified by an attack tree. We argue that there are multiple sensible success criteria for attacks wrt. a given attacker goal and develop a framework for defining such criteria. We exploit our framework to identify similarities and differences between automatic attack-tree generation techniques. Finally, we propose a novel variant of attack trees that allows one to express exploits in an explicit fashion.

Controlling confidential information in concurrent systems is difficult, due to covert channels resulting from interaction between threads. This problem is exacerbated if threads share resources at fine granularity. In this work, we propose a novel monitoring framework to enforce strong information security in concurrent programs. Our monitors are hybrid, combining dynamic and static program analysis to enforce security in a sound and rather precise fashion. In our framework, each thread is guarded by its own local monitor, and there is a single global monitor. We instantiate our monitoring framework to support rely-guarantee style reasoning about the use of shared resources, at the granularity of individual memory locations, and then specialize local monitors further to enforce flow-sensitive progress-sensitive information-flow control. Our local monitors exploit rely-guarantee-style reasoning about shared memory to achieve high precision. Soundness of rely-guarantee-style reasoning is guaranteed by all monitors cooperatively. The global monitor is invoked only when threads synchronize, and so does not needlessly restrict concurrency. We prove that our hybrid monitoring approach enforces a knowledge-based progress-sensitive non-interference security condition.

We experimentally evaluate program transformations for removing timing side-channel vulnerabilities wrt. security and overhead. Our study of four well-known transformations confirms that their performance overhead differs substantially. A novelty of our work is the empirical investigation of channel bandwidths, which clarifies that the transformations also differ wrt. how much security they add to a program. Interestingly, we observe such differences even between transformations that have been proven to establish timing-sensitive noninterference. Beyond clarification, our findings provide guidance for choosing a suitable transformation for removing timing side-channel vulnerabilities. Such guidance is needed because there is a trade-off between security and overhead, which makes choosing a suitable transformation non-trivial. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Research on information flow security for concurrent programs usually assumes sequential consistency although modern multi-core processors often support weaker consistency guarantees. In this article, we clarify the impact that relaxations of sequential consistency have on information flow security. We consider four memory models and prove for each of them that information flow security under this model does not imply information flow security in any of the other models. This result suggests that research on security needs to pay more attention to the consistency guarantees provided by contemporary hardware. The other main technical contribution of this article is a program transformation that soundly enforces information flow security under different memory models. This program transformation is significantly less restrictive than a transformation that first establishes sequential consistency and then applies a traditional information flow analysis for concurrent programs.

The idea of building secure systems by plugging together "secure'' components is appealing, but this requires a definition of security which, in addition to taking care of top-level security goals, is strengthened appropriately in order to be compositional. This approach has been previously studied for information-flow security of shared-variable concurrent programs, but the price for compositionality is very high: a thread must be extremely pessimistic about what an environment might do with shared resources. This pessimism leads to many intuitively secure threads being labelled as insecure. Since in practice it is only meaningful to compose threads which follow an agreed protocol for data access, we take advantage of this to develop a more liberal compositional security condition. The idea is to give the security definition access to the intended pattern of data usage, as expressed by assumption-guarantee style conditions associated with each thread. We illustrate the improved precision by developing the first flow-sensitive security type system that provably enforces a noninterference-like property for concurrent programs.

Interrupt-driven communication with hardware devices can be exploited for establishing covert channels. In this article, we propose an information-theoretic framework for analyzing the bandwidth of such interrupt-related channels while taking aspects of noise into account. As countermeasures, we present mechanisms that are already implemented in some operating systems, though for a different purpose. Based on our formal framework, the effectiveness of the mechanisms is evaluated. Despite the large body of work on covert channels, this is the first comprehensive account of interrupt-related covert channel analysis and mitigation.

The security of computation at the level of a specific programming language and the security of complex systems at a more abstract level are two major areas of current security research. With the objective to integrate the two, this article proposes an adequate translation of a timing-sensitive sec urity property for simple multi-threaded programs into a more general security framework. Soundness and completeness of the translation guarantee that the trace-based specification of the translation of a multi-threaded program is secure if and only if the original program is secure. Finally, the translation is extended to a distributed setting, and it is demonstrated how to derive global security of the overall system from local security of each thread. The translation is presented as a two-step process where the first step is independent from the concrete programming language.

When complex systems are constructed from simpler components it is important to know how properties of the components behave under composition. We present various compositionality results for security properties. In particular we introduce a novel security property and show that this property is, in general, composable although it is weaker than forward correctability. Moreover we demonstrate that certain nontrivial security properties emerge under composition and illustrate how this fact can be exploited. All compositionality results that we present are verified with the help of a single, quite powerful lemma. Basing on this lemma, we also re-prove several already known compositionality results with the objective to unify these results. As a side effect, we obtain a classification of known compositionality results for security properties.

Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

In a stepwise development process, it is essential that system properties that have been already investigated in some phase need not be re-investigated in later phases. In formal developments, this corresponds to the requirement that properties are presented under refinement. While safety and liveness properties are indeed preserved under most standard forms of refinement, it is well known that this is, in general, not true for information flow properties, a large and useful class of security properties. We propose a collection of refinement operators as a solution to this problem. We prove that these operators preserve information flow as well as other system properties. Thus, information flow properties become compatible with stepwise development. Moreover we show that our operators are an optimal solution.

We present a framework in which different notions of security can be defined in a uniform and modular way. Each definition of security is formalized as a security predicate by assembling more primitive basic security predicates. A collection of such basic security predicates is defined and we demonstrate how well-known concepts like generalized non-interference or separability can be constructed from them. The framework is open and can be extended with new basic security predicates using a general schema. We investigate the compatibility of the assembled definitions with system properties apart from security and propose a new definition of security which does not restrict non-critical information flow. It turns out that the modularity of our framework simplifies these investigation. Finally, we discuss the stepwise development of secure systems.

To date, there is little evidence that modular reasoning about fault-tolerant systems can simplify the verification process in practice. This question is studied using a prominent example from the fault tolerance literature: the problem of reliable broadcast in point-to-point networks subject to crash failures of processes. The experiences from this case study show how modular specification techniques and rigorous proof re-use can indeed help in such undertakings.