Helmholtz Center for Information Security
CISPA – Helmholtz-Zentrum für InformationssicherheitNot a member yet
3406 research outputs found
Sort by
Sets of Robust Rules, and How to Find Them
Get PDFAssociation rules are among the most important concepts in
data mining. Rules of the form X → Y are simple to understand, simple to act upon, yet can model important local dependencies in data.
The problem is, however, that there are so many of them. Both traditional and state-of-the-art frameworks typically yield millions of rules,
rather than identifying a small set of rules that capture the most important dependencies of the data. In this paper, we define the problem
of association rule mining in terms of the Minimum Description Length
principle. That is, we identify the best set of rules as the one that most
succinctly describes the data. We show that the resulting optimization
problem does not lend itself for exact search, and hence propose Grab,
a greedy heuristic to efficiently discover good sets of rules directly from
data. Through an extensive set of experiments we show that, unlike the
state-of-the-art, Grab does reliably recover the ground truth. On real
world data we show it finds reasonable numbers of rules, that upon close
inspection give clear insight in the local distribution of the data
Bridging the Gap Between Abstractions and Critical-Path Heuristics via Hypergraphs
No full textAbstractions and critical-path heuristics are among the most important families of admissible heuristics in classical planning. In this paper, we present a new family of heuristics, which we name hyperabstractions, given by the combination of the principal ideas underlying abstractions and critical-path heuristics. Hyperabstractions approximate goal distances through a mapping from states to sets of abstract states. The abstract transition behavior forms a relation between abstract states and sets of abstract states, and is formally represented via the notion of hypergraphs. We show that both abstractions and critical-path heuristics can naturally be expressed as members of this family. Moreover, we devise a method to construct hyperabstractions, using either a set of abstractions or a critical-path heuristic as a seed, in a way that guarantees that the resulting distance estimations dominate those of the input heuristics, sometimes even strictly. By finding suitable cost partitionings for hyperabstraction heuristics, this dominance result is preserved even in comparison to the additive combination of the input heuristics. Our experiments indicate the potential of this new class of heuristics, opening a wide range of future research topics
Strong Extension-Free Proof Systems
Get PDFWe introduce proof systems for propositional logic that admit short proofs of hard formulas as well as the succinct expression of most techniques used by modern SAT solvers. Our proof systems allow the derivation of clauses
that are not necessarily implied, but which are redundant in the sense that their addition preserves satisfiability. To guarantee that these added clauses are redundant, we consider various efficiently decidable redundancy criteria which we obtain by first characterizing clause redundancy in terms of a semantic implication relationship and then restricting this relationship so that it becomes decidable in polynomial time. As the restricted implication relation is based on unit propagation—a core technique of SAT solvers—it allows efficient proof checking too. The resulting proof systems are surprisingly strong, even without the introduction of new variables—a key feature of short proofs presented in the proof-complexity literature. We demonstrate the strength of our proof systems on the famous pigeon hole formulas by providing short clausal proofs without new variables
The DUSTER Attack: Tor Onion Service Attribution Based on Flow Watermarking with Track Hiding
No full textTor is a distributed network composed of volunteer relays which is designed to preserve the sender-receiver anonymity of communications on the Internet. Despite the use of the onion routing paradigm, Tor is vulnerable to traffic analysis attacks. In this paper we present Duster, an active traffic analysis attack based on flow watermarking that exploits a vulnerability in Tor's congestion control mechanism in order to link a Tor onion service with its real IP address. The proposed watermarking system embeds a watermark at the destination of a Tor circuit which is propagated throughout the Tor network and can be detected by our modified Tor relays in the proximity of the onion service. Furthermore, upon detection the watermark is cancelled so that the target onion service remains unaware of its presence. We performed a set of experiments over the real Tor network in order to evaluate the feasibility of this attack. Our results show that true positive rates above 94% and false positive rates below 0.05% can be easily obtained. Finally we discuss a solution to mitigate this and other traffic analysis attacks which exploit Tor's congestion control
Quantifying the Information Leakage in Cache Attacks via Symbolic Execution
Get PDFCache attacks allow attackers to infer the properties of a secret execution by observing cache hits and misses. But how much information can actually leak through such attacks? For a given program, a cache model, and an input, our CHALICE framework leverages symbolic execution to compute the amount of information that can possibly leak through cache attacks. At the core of CHALICE is a novel approach to quantify information leakage that can highlight critical cache side-channel leakage on arbitrary binary code. In our evaluation on real-world programs from OpenSSL and Linux GDK libraries, CHALICE effectively quantifies information leakage: For an AES-128 implementation on Linux, for instance, CHALICE finds that a cache attack can leak as much as 127 out of 128 bits of the encryption key
FPGA Stream-Monitoring of Real-time Properties
No full textAn essential part of cyber-physical systems is the online evaluation of real-time data streams. Especially in systems that are intrinsically safety-critical, a dedicated monitoring component inspecting data streams to detect problems at runtime greatly increases the confidence in a safe execution. Such a monitor needs to be based on a specification language capable of expressing complex, high-level properties using only the accessible low-level signals. Moreover, tight constraints on computational resources exacerbate the requirements on the monitor. Thus, several existing approaches to monitoring are not applicable due to their dependence on an operating system. We present an FPGA-based monitoring approach by compiling an RTLola specification into synthesizable VHDL code. RTLola is a stream-based specification language capable of expressing complex real-time properties while providing an upper bound on the execution time and memory requirements. The statically determined memory bound allows for a compilation to an FPGA with a fixed size. An advantage of FPGAs is a simple integration process in existing systems and superb executing time. The compilation results in a highly parallel implementation thanks to the modular nature of RTLola specifications. This further increases the maximal event rate the monitor can handle
Multi-device anonymous authentication
No full textRecently, a few pragmatic and privacy protecting systems for authentication in multiple systems have been designed. The most prominent examples include Pseudonymous Signatures for German personal identity cards and Anonymous Attestation. The main properties are that a user can authenticate himself with a single private key (stored on a smart card), but nevertheless the user’s IDs in different systems are unlinkable. We develop a solution which enables a user to achieve the above-mentioned goals while using more than one personal device, each holding a single secret key, but different for each device. Our solution is privacy preserving: it will remain hidden for the service system which device is used. Nevertheless, if a device gets stolen, lost or compromised, the user can revoke it (leaving his other devices intact). In particular, in this way we create a strong authentication framework for cloud users, where the cloud does not learn indirectly personal data. Our solution is based on a novel cryptographic primitive, called Pseudonymous Public Key Group Signature
Pseudonymous Signature Schemes
No full textThe chapter concerns cryptographic schemes enabling to sign digital data in a pseudonymized way. The schemes aim to provide a strong cryptographic evidence of integrity of the signed data and origin of the signature, but at the same time have to hide the identity of the signatory. There are two crucial properties that are specific for pseudonymous signatures: ability to recover the real identity of the signatory in certain circumstances and resilience to Sybil attacks. Despite using a single private key, the signatory can create a (single) unlinkable pseudonym for each domain or sector of activity and generate signatures corresponding to this pseudonym
Detecting Information Flow by Mutating Input data
No full textAnalyzing information flow is central in assessing
the security of applications. However, static and dynamic analyses
of information flow are easily challenged by non-available or
obscure code. We present a lightweight mutation-based analysis
that systematically mutates dynamic values returned by sensitive
sources to assess whether the mutation changes the values passed
to sensitive sinks. If so, we found a flow between source and sink.
In contrast to existing techniques, mutation-based flow analysis
does not attempt to identify the specific path of the flow and is
thus resilient to obfuscation.
In its evaluation, our MUTAFLOW prototype for Android programs showed that mutation-based flow analysis is a lightweight
yet effective complement to existing tools. Compared to the
popular FLOWDROID static analysis tool, MUTAFLOW requires
less than 10% of source code lines but has similar accuracy;
on 20 tested real-world apps, it is able to detect 75 flows that FLOWDROID misses
