Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Real-time Visualization of Stream-based Monitoring Data
No full textStream-based runtime monitors are used in safety-critical applications such as Unmanned Aerial Systems (UAS) to compute comprehensive statistics and logical assessments of system health that provide the human operator with critical information in hand-over situations. In such applications, a visual display of the monitoring data can be much more helpful than the textual alerts provided by a more traditional user interface. This visualization requires extensive real-time data processing, which includes the synchronization of data from different streams, filtering and aggregation, and priorization and management of user attention. We present a visualization approach for the RTLola monitoring framework. Our approach is based on the principle that the necessary data processing is the responsibility of the monitor itself, rather than the responsibility of some external visualization tool. We show how the various aspects of the data transformation can be described as RTLola stream equations and linked to the visualization component through a bidirectional synchronous interface. In our experience, this approach leads to highly informative visualizations as well as to understandable and easily maintainable monitoring code
Omen: discovering sequential patterns with reliable prediction delays
Get PDFSuppose we are given a discrete-valued time series X of observed events and an equally long binary sequence Y that indicates whether something of interest happened at that particular point in time. We consider the problem of mining serial episodes, sequential patterns allowing for gaps, from X that reliably predict those interesting events. With reliable we mean patterns that not only predict that an interesting event is likely to follow, but in particular that we can also accurately tell how how long until that event will happen. In other words, we are specifically interested in patterns with a highly skewed distribution of delays between pattern occurrences and predicted events. As it is unlikely that a single pattern can explain a complex real-world progress, we are after the smallest, least redundant set of such patterns that together explain the interesting events well. We formally define this problem in terms of the Minimum Description Length principle, by which we identify the best patterns as those that describe the occurrences of interesting events Y most succinctly given the data over X . As neither discovering the optimal explanation of Y given a set of patterns, nor the discovery of optimal pattern set are problems that allow for straightforward optimization, we break the problem in two and propose effective heuristics for both. Through extensive empirical evaluation, we show that both our main method, Omen , and its fast approximation fOmen , work well in practice and both quantitatively and qualitatively beat the state of the art
Formally Justifying MDL-based Inference of Cause and Effect
Get PDFThe algorithmic independence of conditionals, which postu- lates that the causal mechanism is algorithmically indepen- dent of the cause, has recently inspired many highly success- ful approaches to distinguish cause from effect given only observational data. Most popular among these is the idea to approximate algorithmic independence via two-part Mini- mum Description Length (MDL). Although intuitively sen- sible, the link between the original postulate and practical two-part MDL encodings has so far been left vague. In this work, we close this gap by deriving a two-part formulation of this postulate, in terms of Kolmogorov complexity, which directly links to practical MDL encodings. To close the cy- cle, we prove that this formulation leads on expectation to the same inference result as the original postulate
Small Hazard-Free Transducers
Get PDFIkenmeyer et al. (JACM'19) proved an unconditional exponential separation
between the hazard-free complexity and (standard) circuit complexity of
explicit functions. This raises the question: which classes of functions permit
efficient hazard-free circuits?
In this work, we prove that circuit implementations of transducers with
small state space are such a class. A transducer is a finite state machine that
transcribes, symbol by symbol, an input string of length n into an output
string of length n. We present a construction that transforms any function
arising from a transducer into an efficient circuit of size O(n) computing
the hazard-free extension of the function.
More precisely, given a transducer with s states, receiving n input symbols
encoded by l bits, and computing n output symbols encoded by m bits,
the transducer has a hazard-free circuit of size
m*n*2^O(s+l) and depth O(s*log(n) + l); in particular, if s,
l, m are element of O(1), size and depth are asymptotically optimal.
In light of the strong hardness results by Ikenmeyer et al. (JACM'19), we
consider this a surprising result
Discovering Interpretable Data-to-Sequence Generators
Get PDFWe study the problem of predicting an event sequence given some meta data. In particular, we are interested in learning easily interpretable models that can accurately generate a se- quence based on an attribute vector. To this end, we propose to learn a sparse event-flow graph over the training sequences, and statistically robust rules that use meta data to determine which paths to follow. We formalize the problem in terms of the Minimum Description Length (MDL) principle, by which we identify the best model as the one that compresses the data best. As the resulting optimization problem is NP-hard, we propose the efficient CONSEQUENCE algorithm to discover good event-flow graphs from data.
Through an extensive set of experiments including a case study, we show that it ably discovers compact, interpretable and accurate models for the generation and prediction of event sequences from data, has a low sample complexity, and is particularly robust against noise
Distributed ∆-Coloring Plays Hide-and-Seek
Get PDFWe prove several new tight or near-tight distributed lower bounds for classic symmetry breaking problems in graphs. As a basic tool, we first provide a new insightful proof that any deterministic distributed algorithm that computes a ∆-coloring on ∆-regular trees requires Omega(log_∆ n) rounds and any randomized such algorithm requires Omega(log_∆ log n) rounds. We prove this by showing that a natural relaxation of the ∆-coloring problem is a fixed point in the round elimination framework.
As a first application, we show that our ∆-coloring lower bound proof directly extends to arbdefective colorings. An arbdefective c-coloring of a graph G=(V,E) is given by a c-coloring of V and an orientation of E, where the arbdefect of a color i is the maximum number of monochromatic outgoing edges of any node of color i. We exactly characterize which variants of the arbdefective coloring problem can be solved in O(f(∆) + log* n) rounds, for some function f, and which of them instead require Omega(log_∆ n) rounds for deterministic algorithms and Omega(log_∆ log n) rounds for randomized ones.
As a second application, which we see as our main contribution, we use the structure of the fixed point as a building block to prove lower bounds as a function of ∆ for problems that, in some sense, are much easier than ∆-coloring, as they can be solved in O(log* n) deterministic rounds in bounded-degree graphs. More specifically, we prove lower bounds as a function of ∆ for a large class of distributed symmetry breaking problems, which can all be solved by a simple sequential greedy algorithm. For example, we obtain novel results for the fundamental problem of computing a (2,β)-ruling set, i.e., for computing an independent set S ⊆ V such that every node v ∈ V is within distance ≤ β of some node in S. We in particular show that Omega(β∆^{1/β}) rounds are needed even if initially an O(∆)-coloring of the graph is given. With an initial O(∆)-coloring, this lower bound is tight and without, it still nearly matches the existing O(β∆^{2/(β+1)}+log* n) upper bound. The new (2,β)-ruling set lower bound is an exponential improvement over the best existing lower bound for the problem, which was proven in [FOCS '20]. As a special case of the lower bound, we also obtain a tight linear-in-∆ lower bound for computing a maximal independent set (MIS) in trees. While such an MIS lower bound was known for general graphs, the best previous MIS lower bounds for trees was Omega(log ∆). Our lower bound even applies to a much more general family of problems that allows for almost arbitrary combinations of natural constraints from coloring problems, orientation problems, and independent set problems, and provides a single unified proof for known and new lower bound results for these types of problems.
All of our lower bounds as a function of ∆ also imply substantial lower bounds as a function of n. For instance, we obtain that the maximal independent set problem, on trees, requires Omega(log n / log log n) rounds for deterministic algorithms, which is tight
Masked Training of Neural Networks with Partial Gradients
Get PDFState-of-the-art training algorithms for deep learning models are based on stochastic gradient descent (SGD). Recently, many variations have been explored: perturbing parameters for better accuracy (such as in Extragradient), limiting SGD updates to a subset of parameters for increased efficiency (such as meProp) or a combination of both (such as Dropout). However, the convergence of these methods is often not studied in theory. We propose a unified theoretical framework to study such SGD variants -- encompassing the aforementioned algorithms and additionally a broad variety of methods used for communication efficient training or model compression. Our insights can be used as a guide to improve the efficiency of such methods and facilitate generalization to new applications. As an example, we tackle the task of jointly training networks, a version of which (limited to sub-networks) is used to create Slimmable Networks. By training a low-rank Transformer jointly with a standard one we obtain superior performance than when it is trained separately
Temporal Stream Logic modulo Theories
Get PDFTemporal stream logic (TSL) extends LTL with updates and predicates over arbitrary function terms. This allows for specifying data-intensive systems for which LTL is not expressive enough. In the semantics of TSL, functions and predicates are left uninterpreted. In this paper, we extend TSL with first-order theories, enabling us to specify systems using interpreted functions and predicates such as incrementation or equality. We investigate the satisfiability problem of TSL modulo the standard underlying theory of uninterpreted functions as well as with respect to Presburger arithmetic and the theory of equality: For all three theories, TSL satisfiability is neither semi-decidable nor co-semi-decidable. Nevertheless, we identify three fragments of TSL for which the satisfiability problem is (semi-)decidable in the theory of uninterpreted functions. Despite the undecidability, we present an algorithm – which is not guaranteed to terminate – for checking the satisfiability of a TSL formula in the theory of uninterpreted functions and evaluate it: It scales well and is able to validate assumptions in a real-world system design
Debugger-driven Embedded Fuzzing
Get PDFEmbedded Systems – the hidden computers in our lives – are deployed in the billionths and are already in the focus of attackers. They pose security risks when not tested and maintained thoroughly. In recent years, fuzzing has become a
promising technique for automated security testing of programs, which can generate tons of test inputs for a program. Fuzzing is hardly applied to embedded systems, because of their high diversity and closed character. During my research I want tackle that gap in fuzzing embedded systems – short: “Embedded Fuzzing”. My goal is to obtain insights of the embedded system during execution, by using common debugging interfaces and hardware breakpoints to enable guided fuzzing in a generic and widely applicable way. Debugging interfaces and hardware breakpoints are available for most common microcontrollers, generating a potential industry impact. Preliminary results show that the approach covers basic blocks faster than blackbox fuzzing. Additionally, it is source code agnostic and leaves the
embedded firmware unaltered
Algorithmic aspects of elliptic bases in finite field discrete logarithm algorithms
Get PDFElliptic bases, introduced by Couveignes and Lercier in 2009, give an
elegant way of representing finite field extensions. A natural
question which seems to have been considered independently by several
groups is to use this representation as a starting point for discrete
logarithm algorithms in small characteristic finite fields.
This idea has been recently proposed by two groups working on it, in
order to achieve provable quasi-polynomial time for discrete
logarithms in small characteristic finite fields.
In this paper, we do not try to achieve a provable algorithm but,
instead, investigate the practicality of heuristic algorithms based
on elliptic bases. Our key idea is to use a different model of the
elliptic curve used for the elliptic basis that allows for a
relatively simple adaptation of the techniques used with former
Frobenius representation algorithms.
We have not performed any record computation with this new method but
our experiments with the field \F_{3^{1345}} indicate that
switching to elliptic representations might be possible with
performances comparable to the current best practical methods