Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
Get PDFWe generalize the monotone local search approach of Fomin, Gaspers, Lokshtanov and Saurabh [J.ACM 2019], by establishing a connection between parameterized approximation and exponential-time approximation algorithms for {\em monotone subset minimization} problems.
In a {\em monotone subset minimization} problem the input implicitly describes a non-empty set family over a universe of size which is closed under taking supersets.
The task is to find a minimum cardinality set in this family.
Broadly speaking, we use {\em approximate monotone local search} to show that a parameterized -approximation algorithm that runs in c^k \cdot n^{\OO(1)} time, where is the solution size, can be used to derive an -approximation randomized algorithm that runs in d^n \cdot n^{\OO(1)} time, where is the unique value in such that \D{\frac{1}{\alpha}}{\frac{d-1}{c-1}} =\frac{\ln c }{\alpha} and \D{a}{b} is the Kullback-Leibler divergence.
This running time matches that of Fomin et al.\ for , and is strictly better when , for any .
Furthermore, we also show that this result can be derandomized at the expense of a sub-exponential multiplicative factor in the running time.
We use an approximate variant of the exhaustive search as a benchmark for our algorithm.
We show that the classic 2^n \cdot n^{\OO(1)} exhaustive search can be adapted to an -approximate exhaustive search that runs in time
\left ( 1+ \exp\left (-\alpha \cdot \entropy\left (\frac{1}{\alpha}\right)\right)\right)^n \cdot n^{\OO(1)}, where \entropy is the entropy function.
Furthermore, we provide a lower bound stating that the running time of this -approximate exhaustive search is the best achievable running time in an oracle model.
When compared to approximate exhaustive search, and to other techniques, the running times obtained by approximate monotone local search are strictly better for any .
We demonstrate the potential of approximate monotone local search by deriving new and faster exponential approximation algorithms for {\sc Vertex Cover}, {\sc -Hitting Set}, {\sc Directed Feedback Vertex Set}, {\sc Directed Subset Feedback Vertex Set}, {\sc Directed Odd Cycle Transversal} and {\sc Undirected Multicut}.
For instance, we get a -approximation algorithm for {\sc Vertex Cover} with running time 1.114^n \cdot n^{\OO(1)}, improving upon the previously best known -approximation running in time 1.127^n \cdot n^{\OO(1)} by Bourgeois et al.\ [DAM 2011]
Synthesizing Dominant Strategies for Liveness
Get PDFReactive synthesis automatically derives a strategy that satisfies a given specification. However, requiring a strategy to meet the specification in every situation is, in many cases, too hard of a requirement. Particularly in compositional synthesis of distributed systems, individual winning strategies for the processes often do not exist. Remorsefree dominance, a weaker notion than winning, accounts for such situations: dominant strategies are only required to be as good as any alternative strategy, i.e., they are allowed to violate the specification if no other strategy would have satisfied it in the same situation. The composition of dominant strategies is only guaranteed to be dominant for safety properties, though; preventing the use of dominance in compositional synthesis for liveness specifications. Yet, safety properties are often not expressive enough. In this paper, we thus introduce a new winning condition for strategies, called delay-dominance, that overcomes this weakness of remorsefree dominance: we show that it is compositional for both safety and liveness specifications, enabling a compositional synthesis algorithm based on delay-dominance for general specifications. Furthermore, we introduce an automaton construction for recognizing delay-dominant strategies and prove its soundness and completeness. The resulting automaton is of single-exponential size in the squared length of the specification and can immediately be used for safraless synthesis procedures. Thus, synthesis of delay-dominant strategies is, as synthesis of winning strategies, in 2EXPTIME
CLIFuzzer: Mining Grammars for Command-Line Invocations
Get PDFThe behavior of command-line utilities can be very much influenced by passing command-line options and arguments—configuration settings that enable, disable, or otherwise influence parts of the code to be executed. Hence, systematic testing of command-line utilities requires testing them with diverse configurations of supported command-line options.
We introduce CLIFuzzer, a tool that takes an executable program and, using dynamic analysis to track input processing, automatically extract a full set of its options, arguments, and argument types. This set forms a grammar that represents the valid sequences of valid options and arguments. Producing invocations from this grammar, we can fuzz the program with an endless list of random configurations, covering the related code. This leads to increased coverage and new bugs over purely mutation based fuzzers
The Largest Connected Subgraph Game
Get PDFThis paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Get PDFThe Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves π, σ in ℝ^d, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of π and σ under arbitrary translations, to compare the curves' shape irrespective of their absolute location?
There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm.
For the L₁ norm in ℝ^d, we provide an ????(n^{2(d+1)})-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in ℝ², we show that a simple problem-specific insight leads to a (1+ε)-approximation in time ????(n³/ε²). We then show how to obtain a subcubic ????̃(n^{2.5}/ε²) time algorithm with significant new ideas; this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure.
We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems
Assessing Model-free Anomaly Detection in Industrial Control Systems Against Generic Concealment Attacks
Get PDFIn recent years, a number of model-free process-based anomaly detection schemes for Industrial Control Systems (ICS) were proposed. Model-free anomaly detectors are trained directly from process data and do not require process knowledge. They are validated based on a set of public data with limited attacks present.
As result, the resilience of those schemes against general concealment attacks is unclear. In addition, no structured discussion on the properties verified by the detectors exists.
In this work, we provide the first systematic analysis of such anomaly detection schemes, focusing on six model-free process-based anomaly detectors. We hypothesize that the detectors verify a combination of temporal, spatial, and statistical consistencies. To test this, we systematically analyse their resilience against generic concealment attacks. Our generic concealment attacks are designed to violate a specific consistency verified by the detector, and require no knowledge of the attacked physical process or the detector. In addition, we compare against prior work attacks that were designed to attack neural network-based detectors.
Our results demonstrate that the evaluated model-free detectors are in general susceptible to generic concealment attacks. For each evaluated detector, at least one of our generic concealment attacks performs better than prior work attacks. In particular, the results allow us to show which specific consistencies are verified by each detector. We also find that prior work attacks that target neural-network architectures transfer surprisingly well against other architectures
Computing Generalized Convolutions Faster Than Brute Force
Get PDFIn this paper, we consider a general notion of convolution.
Let be a finite domain and let be the set of -length vectors
(tuples) of . Let be a function and
let be a coordinate-wise application of . The -Convolution of two
functions is
\begin{displaymath}
(g \circledast_f h)(v) := \sum_{\substack{v_g,v_h \in
D^n\\ \text{s.t. } v = v_g \oplus_f v_h}} g(v_g) \cdot h(v_h)
\end{displaymath}
for every .
This problem generalizes many fundamental convolutions
such as Subset Convolution, XOR Product, Covering Product or Packing Product,
etc.
For arbitrary function and domain we can compute -Convolution via brute-force enumeration
in time.
Our main result is an improvement over this naive algorithm. We show that -Convolution
can be computed exactly in for constant when has even cardinality. Our main observation is that a
\emph{cyclic partition} of a function can
be used to speed up the computation of -Convolution, and we show that an appropriate
cyclic partition exists for every .
Furthermore, we demonstrate that a single entry of the -Convolution can be computed
more efficiently. In this variant, we are given two functions alongside with a vector and the task of
the -Query problem is to compute integer . This is a
generalization of the well-known Orthogonal Vectors problem. We show that
-Query can be computed in time, where is the exponent of currently fastest matrix multiplication
algorithm
Pareto-Optimal Defenses for the Web Infrastructure: Theory and Practice
Get PDFThe integrity of the content a user is exposed to when browsing the web relies on a plethora of non-web technologies and an infrastructure of interdependent hosts, communication technologies, and trust relations. Incidents like the Chinese Great Cannon or the MyEtherWallet attack make it painfully clear: the security of end users hinges on the security of the surrounding infrastructure: routing, DNS, content delivery, and the PKI. There are many competing, but isolated proposals to increase security, from the network up to the application layer. So far, researchers have focus on analyzing attacks and defenses on specific layers. We still lack an evaluation of how, given the status quo of the web, these proposals can be combined, how effective they are, and at what cost the increase of security comes. In this work, we propose a graph-based analysis based on Stackelberg planning that considers a rich attacker model and a multitude of proposals from IPsec to DNSSEC and SRI. Our threat model considers the security of billions of users against attackers ranging from small hacker groups to nation-state actors. Analyzing the infrastructure of the Top 5k Alexa domains, we discover that the security mechanisms currently deployed are ineffective and that some infrastructure providers have a comparable threat potential to nations. We find a considerable increase of security (up to 13% protected web visits) is possible at relatively modest cost, due to the effectiveness of mitigations at the application and transport layer, which dominate expensive infrastructure enhancements such as DNSSEC and IPsec
The Abe-Okamoto Partially Blind Signature Scheme Revisited
Get PDFPartially blind signatures, an extension of ordinary blind sig- natures, are a primitive with wide applications in e-cash and electronic voting. One of the most efficient schemes to date is the one by Abe and Okamoto (CRYPTO 2000), whose underlying idea — the OR-proof technique — has served as the basis for several works.
We point out several subtle flaws in the original proof of security, and provide a new detailed and rigorous proof, achieving similar bounds as the original work. We believe our insights on the proof strategy will find useful in the security analyses of other OR-proof-based schemes
Local Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descriptive Combinatorics
Get PDFWe study connections between three different fields: distributed local algorithms, finitary factors of iid processes, and descriptive combinatorics. We focus on two central questions: Can we apply techniques from one of the areas to obtain results in another? Can we show that complexity classes coming from different areas contain precisely the same problems? We give an affirmative answer to both questions in the context of local problems on regular trees:
1. We extend the Borel determinacy technique of Marks [Marks - J.Am.Math.Soc.2016] coming from descriptive combinatorics and adapt it to the area of distributed computing, thereby obtaining a more generally applicable lower bound technique in descriptive combinatorics and an entirely new lower bound technique for distributed algorithms. Using our new technique, we prove deterministic distributed Omega(log n)-round lower bounds for problems from a natural class of homomorphism problems. Interestingly, these lower bounds seem beyond the current reach of the powerful round elimination technique [Brandt - PODC 2019] responsible for all substantial locality lower bounds of the last years. Our key technical ingredient is a novel ID graph technique that we expect to be of independent interest; in fact, it has already played an important role in a new lower bound for the Lovász local lemma in the Local Computation Algorithms model from sequential computing [Brandt, Grunau, Rozhoň - PODC 2021].
2. We prove that a local problem admits a Baire measurable coloring if and only if it admits a local algorithm with local complexity O(log n), extending the classification of Baire measurable colorings of Bernshteyn [Bernshteyn - personal communication]. A key ingredient of the proof is a new and simple characterization of local problems that can be solved in O(log n) rounds. We complement this result by showing separations between complexity classes from distributed computing, finitary factors, and descriptive combinatorics. Most notably, the class of problems that allow a distributed algorithm with sublogarithmic randomized local complexity is incomparable with the class of problems with a Borel solution.
We hope that our treatment will help to view all three perspectives as part of a common theory of locality, in which we follow the insightful paper of [Bernshteyn - arXiv 2004.04905]