Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
Get PDFIn the general AntiFactor problem, a graph and, for every vertex of , a set of forbidden degrees is given. The task is to find a set of edges such that the degree of in is \emph{not} in the set . Standard techniques (dynamic programming plus fast convolution) can be used to show that if is the largest forbidden degree, then the problem can be solved in time if a tree decomposition of width is given. However, significantly faster algorithms are possible if the sets are sparse:
our main algorithmic result shows that if every vertex has at most forbidden degrees (we call this special case AntiFactor_x), then the problem can be solved in time . That is, AntiFactor_x is fixed-parameter tractable parameterized by treewidth and the maximum number of excluded degrees.
Our algorithm uses the technique of representative sets, which can be generalized to the optimization version, but (as expected) not to the counting version of the problem. In fact, we show that #AntiFactor_1 is already #W[1]-hard parameterized by the width of the given decomposition. Moreover, we show that, unlike for the decision version, the standard dynamic programming algorithm is essentially optimal for the counting version. Formally, for a fixed nonempty set , we denote by X-AntiFactor the special case where every vertex has the same set of forbidden degrees. We show the following lower bound for every fixed set : if there is an such that #X-AntiFactor can be solved in time given a tree decomposition of width , then the Counting Strong Exponential-Time Hypothesis (#SETH) fails
Parameterized Complexity of Weighted Multicut in Trees
Get PDFThe \textsc{Edge Multicut} problem is a classical cut problem where given an undirected graph , a set of pairs of vertices , and a budget , the goal is to determine if there is a set of at most edges such that for each , has no path from to . \textsc{Edge Multicut} has been relatively recently shown to be fixed-parameter tractable (FPT), parameterized by , by Marx and Razgon [SICOMP 2014], and independently by Bousquet et al. [SICOMP 2018]. In the weighted version of the problem, called \textsc{Weighted Edge Multicut} one is additionally given a weight function and a weight bound , and the goal is to determine if there is a solution of size at most and weight at most . Both the FPT algorithms for \textsc{Edge Multicut} by Marx et al.\ and Bousquet et al.\ fail to generalize to the weighted setting. In fact, the weighted problem is non-trivial even on trees and determining whether \textsc{Weighted Edge Multicut} on trees is FPT was explicitly posed as an open problem by Bousquet et al.\ [STACS 2009]. In this article, we answer this question positively by designing an algorithm which uses a very recent result by Kim et al.\ [STOC 2022] about directed flow augmentation as subroutine.
We also study a variant of this problem where there is no bound on the size of the solution, but the parameter is a structural property of the input, for example, the number of leaves of the tree. We strengthen our results by stating them for the more general vertex deletion version
Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
Get PDFWe give an isomorphism test that runs in time n^{polylog(h)} on all n-vertex graphs excluding some h-vertex graph as a topological subgraph. Previous results state that isomorphism for such graphs can be tested in time n^{polylog(n)} (Babai, STOC 2016) and n^{f(h)} for some function (Grohe and Marx, SIAM J. Comp., 2015).
Our result also unifies and extends previous isomorphism tests for graphs of maximum degree d running in time n^{polylog(d)} (FOCS 2018) and for graphs of Hadwiger number h running in time n^{polylog(h)} (FOCS 2020)
Differentially Describing Groups of Graphs
Get PDFHow does neural connectivity in autistic children differ from neural connectivity in healthy children or autistic youths? What patterns in global trade networks are shared across classes of goods, and how do these patterns change over time? Answering questions like these requires us to differentially describe groups of graphs: Given a set of graphs and a parti- tion of these graphs into groups, discover what graphs in one group have in common, how they systematically differ from graphs in other groups, and how multiple groups of graphs are related. We refer to this task as graph group analysis, which seeks to describe similarities and differences between graph groups by means of statistically significant subgraphs. To per- form graph group analysis, we introduce GRAGRA, which uses maximum entropy modeling to identify a non-redundant set of subgraphs with statistically significant associations to one or more graph groups. Through an extensive set of ex- periments on a wide range of synthetic and real-world graph groups, we confirm that GRAGRA works well in practice
ML-Doctor: Holistic Risk Assessment of Inference Attacks Against Machine Learning Models
Get PDFInference attacks against Machine Learning (ML) models allow adversaries to learn information about training data, model parameters, etc. While researchers have studied these attacks thoroughly, they have done so in isolation. We lack a comprehensive picture of the risks caused by the attacks, such as the different scenarios they can be applied to, the common factors that influence their performance, the relationship among them, or the effectiveness of defense techniques. In this paper, we fill this gap by presenting a first-of-its-kind holistic risk assessment of different inference attacks against machine learning models. We concentrate on four attacks - namely, membership inference, model inversion, attribute inference, and model stealing - and establish a threat model taxonomy. Our extensive experimental evaluation conducted over five model architectures and four datasets shows that the complexity of the training dataset plays an important role with respect to the attack's performance, while the effectiveness of model stealing and membership inference attacks are negatively correlated. We also show that defenses like DP-SGD and Knowledge Distillation can only hope to mitigate some of the inference attacks. Our analysis relies on a modular re-usable software, ML-Doctor, which enables ML model owners to assess the risks of deploying their models, and equally serves as a benchmark tool for researchers and practitioners
From Input Coverage to Code Coverage: Systematically Covering Input Structure with k-Paths
Get PDFGrammar-based testing uses a given grammar to produce syntactically valid inputs. Intuitively, to cover program features, it is necessary to also cover input features. We present a measure of input coverage called k-path coverage, which
takes into account the coverage of individual syntactic elements as well as their combinations up to a given depth k. A k-path coverage with k = 1 prescribes that all individual symbols be covered; k-path coverage with k = 2 dictates that all symbols in the context of all their parents be covered; and so on.
Using the k-path measure, we make a number of contributions.
(1) We provide an \emph{algorithm for grammar-based production} that constructively covers a given k-path measure. In our evaluation, using k-path during production results in a significantly higher code coverage than state-of-the-art approaches that ignore input coverage.
(2) We show on a selection of real-world subjects that coverage of input elements, as measured by k-path, correlates with code coverage. As a consequence, k-path coverage can also be used to predict code coverage.
(3) We show that one can learn associations between individual k-path features and coverage of specific locations: "Method `distrule` is invoked whenever both `+` and `*` occur in an expression." Developers can interpret these associations to create suitable inputs that focus on selected methods, or have tools generate inputs that immediately target these methods.
The above approaches have been implemented in the \tribble and \codeine prototypes, and evaluated on a number of processors for JSON, CSV, URLs, and Markdown. All tools and data are available as open source
Open-Domain, Content-Based, Multi-Modal Fact-Checking of Out-of-Context Images via Online Resources
No full textMisinformation is now a major problem due to its potential high risks to our core democratic and societal values and orders. Out-of-context misinformation is one of the easiest and effective ways used by adversaries to spread viral false stories. In this threat, a real image is re-purposed to support other narratives by misrepresenting its context and/or elements. The internet is being used as the go-to way to verify information using different sources and modalities. Our goal is an inspectable method that automates this time-consuming and reasoning-intensive process by fact-checking the image-caption pairing using Web evidence. To integrate evidence and cues from both modalities, we introduce the concept of 'multi-modal cycle-consistency check'; starting from the image/caption, we gather textual/visual evidence, which will be compared against the other paired caption/image, respectively. Moreover, we propose a novel architecture, Consistency-Checking Network (CCN), that mimics the layered human reasoning across the same and different modalities: the caption vs. textual evidence, the image vs. visual evidence, and the image vs. caption. Our work offers the first step and benchmark for open-domain, content-based, multi-modal fact-checking, and significantly outperforms previous baselines that did not leverage external evidence
Plant 'n' Seek: Can You Find the Winning Ticket?
Get PDFThe lottery ticket hypothesis has sparked the rapid development of pruning algorithms that perform structure learning by identifying a sparse subnetwork of a large randomly initialized neural network. The existence of such 'winning tickets' has been proven theoretically but at suboptimal sparsity levels. Contemporary pruning algorithms have furthermore been struggling to identify sparse lottery tickets for complex learning tasks. Is this suboptimal sparsity merely an artifact of existence proofs and algorithms or a general limitation of the pruning approach? And, if very sparse tickets exist, are current algorithms able to find them or are further improvements needed to achieve effective network compression? To answer these questions systematically, we derive a framework to plant and hide target architectures within large randomly initialized neural networks. For three common challenges in machine learning, we hand-craft extremely sparse network topologies, plant them in large neural networks, and evaluate state-of-the-art lottery ticket pruning methods. We find that current limitations of pruning algorithms to identify extremely sparse tickets are likely of algorithmic rather than fundamental nature and anticipate that our planting framework will facilitate future developments of efficient pruning algorithms, as we have addressed the issue of missing baselines in the field raised by Frankle et al
Algebraic Restriction Codes and their Applications
Get PDFConsider the following problem: You have a device that is supposed to compute a linear combination of its inputs, which are taken from some finite field. However, the device may be faulty and compute arbitrary functions of its inputs. Is it possible to encode the inputs in such a way that only linear functions can be evaluated over the encodings? I.e., learning an arbitrary function of the encodings will not reveal more information about the inputs than a linear combination.
In this work, we introduce the notion of algebraic restriction codes (AR codes), which constrain adversaries who might compute any function to computing a linear function. Our main result is an information-theoretic construction AR codes that restrict any class of function with a bounded number of output bits to linear functions. Our construction relies on a seed which is not provided to the adversary.
While interesting and natural on its own, we show an application of this notion in cryptography. In particular, we show that AR codes lead to the first construction of rate-1 oblivious transfer with statistical sender security from the Decisional Diffie-Hellman assumption, and the first-ever construction that makes black-box use of cryptography. Previously, such protocols were known only from the LWE assumption, using non-black-box cryptographic techniques. We expect our new notion of AR codes to find further applications, e.g., in the context of non-malleability, in the future
Hiding in Plain Sight? On the Efficacy of Power Side Channel-Based Control Flow Monitoring
Get PDFPhysical side-channel monitoring leverages the physical
phenomena produced by a microcontroller (e.g. power con-
sumption or electromagnetic radiation) to monitor program
execution for malicious behavior. As such, it offers a promis-
ing intrusion detection solution for resource-constrained em-
bedded systems, which are incompatible with conventional
security measures. This method is especially relevant in safety
and security-critical embedded systems such as in industrial
control systems. Side-channel monitoring poses unique chal-
lenges for would-be attackers, such as: (1) limiting attack
vectors by being physically isolated from the monitored sys-
tem, (2) monitoring immutable physical side channels with
uninterpretable data-driven models, and (3) being specifically
trained for the architectures and programs on which they are
applied to. As a result, physical side-channel monitors are
conventionally believed to provide a high level of security.
In this paper, we propose a novel attack to illustrate that,
despite the many barriers to attack that side-channel moni-
toring systems create, they are still vulnerable to adversarial
attacks. We present a method for crafting functional malware
such that, when injected into a side-channel-monitored sys-
tem, the detector is not triggered. Our experiments reveal that
this attack is robust across detector models and hardware im-
plementations. We evaluate our attack on the popular ARM
microcontroller platform on several representative programs,
demonstrating the feasibility of such an attack and highlight-
ing the need for further research into side-channel monitors