OpenRaiser/Intern-Atlas huggingface dataset:
A Pattern-based Survey and Categorization of Network Covert Channel Techniques
Venue: arXiv cs.CR 2015
Year: 2015

Network covert channels are used to hide communication inside network protocols. Within the last decades, various techniques for covert channels arose. We surveyed and analyzed 109 techniques developed between 1987 and 2013 and show that these techniques can be reduced to only 11 different patterns. Moreover, the majority (69.7%) of techniques can be categorized in only four different patterns, i.e. most of the techniques we surveyed are very similar. We represent the patterns in a hierarchical catalog using a pattern language. Our pattern catalog will serve as a base for future covert channel novelty evaluation. Furthermore, we apply the concept of pattern variations to network covert channels. With pattern variations, the context of a pattern can change. For example, a channel developed for IPv4 can automatically be adapted to other network protocols. We also propose the pattern-based covert channel optimizations pattern hopping and pattern combination. Finally, we lay the foundation for pattern-based countermeasures: While many current countermeasures were developed for specific channels, a pattern-oriented approach allows to apply one countermeasure to multiple channels. Hence, future countermeasure development can focus on patterns, and the development of real-world protection against covert channels is greatly simplified.
The Effect of Visual Noise on The Completion of Security Critical Tasks
Venue: arXiv cs.HC 2015
Year: 2015

User errors while performing security-critical tasks can lead to undesirable or even disastrous consequences. One major factor influencing mistakes and failures is complexity of such tasks, which has been studied extensively in prior research. Another important issue which hardly received any attention is the impact of both accidental and intended distractions on users performing security-critical tasks. In particular, it is unclear whether, and to what extent, unexpected sensory cues (e.g., auditory or visual) can influence user behavior and/or trigger mistakes. Better understanding of the effects of intended distractions will help clarify their role in adversarial models. As part of the research effort described in this paper, we administered a range of naturally occurring -- yet unexpected -- sounds while study participants attempted to perform a security-critical task. We found that, although these auditory cues lowered participants' failure rates, they had no discernible effect on their task completion times. To this end, we overview some relevant literature that explains these somewhat counter-intuitive findings. Conducting a thorough and meaningful study on user errors requires a large number of participants, since errors are typically infrequent and should not be instigated more than once per subject. To reduce the effort of running numerous subjects, we developed a novel experimental setup that was fully automated and unattended. We discuss our experience with this setup and highlight the pros and cons of generalizing its usage.
Tree-like Queries in OWL 2 QL: Succinctness and Complexity Results
Venue: arXiv cs.AI 2015
Year: 2015

This paper investigates the impact of query topology on the difficulty of answering conjunctive queries in the presence of OWL 2 QL ontologies. Our first contribution is to clarify the worst-case size of positive existential (PE), non-recursive Datalog (NDL), and first-order (FO) rewritings for various classes of tree-like conjunctive queries, ranging from linear queries to bounded treewidth queries. Perhaps our most surprising result is a superpolynomial lower bound on the size of PE-rewritings that holds already for linear queries and ontologies of depth 2. More positively, we show that polynomial-size NDL-rewritings always exist for tree-shaped queries with a bounded number of leaves (and arbitrary ontologies), and for bounded treewidth queries paired with bounded depth ontologies. For FO-rewritings, we equate the existence of polysize rewritings with well-known problems in Boolean circuit complexity. As our second contribution, we analyze the computational complexity of query answering and establish tractability results (either NL- or LOGCFL-completeness) for a range of query-ontology pairs. Combining our new results with those from the literature yields a complete picture of the succinctness and complexity landscapes for the considered classes of queries and ontologies.
Scheduled denoising autoencoders
Venue: arXiv cs.LG 2015
Year: 2015

We present a representation learning method that learns features at multiple different levels of scale. Working within the unsupervised framework of denoising autoencoders, we observe that when the input is heavily corrupted during training, the network tends to learn coarse-grained features, whereas when the input is only slightly corrupted, the network tends to learn fine-grained features. This motivates the scheduled denoising autoencoder, which starts with a high level of noise that lowers as training progresses. We find that the resulting representation yields a significant boost on a later supervised task compared to the original input, or to a standard denoising autoencoder trained at a single noise level. After supervised fine-tuning our best model achieves the lowest ever reported error on the CIFAR-10 data set among permutation-invariant methods.
C-sanitized: a privacy model for document redaction and sanitization
Venue: arXiv cs.CR 2015
Year: 2015

Within the current context of Information Societies, large amounts of information are daily exchanged and/or released. The sensitive nature of much of this information causes a serious privacy threat when documents are uncontrollably made available to untrusted third parties. In such cases, appropriate data protection measures should be undertaken by the responsible organization, especially under the umbrella of current legislations on data privacy. To do so, human experts are usually requested to redact or sanitize document contents. To relieve this burdensome task, this paper presents a privacy model for document redaction/sanitization, which offers several advantages over other models available in the literature. Based on the well-established foundations of data semantics and the information theory, our model provides a framework to develop and implement automated and inherently semantic redaction/sanitization tools. Moreover, contrary to ad-hoc redaction methods, our proposal provides a priori privacy guarantees which can be intuitively defined according to current legislations on data privacy. Empirical tests performed within the context of several use cases illustrate the applicability of our model and its ability to mimic the reasoning of human sanitizers.
Rotation of Sequences: Algorithms and Proofs
Venue: arXiv cs.LO 2015
Year: 2015

Sequence rotation consists of a circular shift of the sequence's elements by a given number of positions. We present the four classic algorithms to rotate a sequence; the loop invariants underlying their correctness; detailed correctness proofs; and fully annotated versions for the verifiers Boogie, Dafny, and ESC/Java2. The presentation illustrates in detail both how the algorithms work and what it takes to carry out mechanized proofs of their correctness.
Correlation Clustering with Noisy Partial Information
Venue: arXiv cs.DS 2015
Year: 2015

In this paper, we propose and study a semi-random model for the Correlation Clustering problem on arbitrary graphs G. We give two approximation algorithms for Correlation Clustering instances from this model. The first algorithm finds a solution of value $(1+ δ) optcost + O_δ(n\log^3 n)$ with high probability, where $optcost$ is the value of the optimal solution (for every $δ> 0$). The second algorithm finds the ground truth clustering with an arbitrarily small classification error $η$ (under some additional assumptions on the instance).
A finer reduction of constraint problems to digraphs
Venue: arXiv cs.CC 2015
Year: 2015

It is well known that the constraint satisfaction problem over a general relational structure A is polynomial time equivalent to the constraint problem over some associated digraph. We present a variant of this construction and show that the corresponding constraint satisfaction problem is logspace equivalent to that over A. Moreover, we show that almost all of the commonly encountered polymorphism properties are held equivalently on the A and the constructed digraph. As a consequence, the Algebraic CSP dichotomy conjecture as well as the conjectures characterizing CSPs solvable in logspace and in nondeterministic logspace are equivalent to their restriction to digraphs.
Minimax Estimation of Functionals of Discrete Distributions
Venue: arXiv cs.IT 2015
Year: 2015

We propose a general methodology for the construction and analysis of minimax estimators for a wide class of functionals of finite dimensional parameters, and elaborate on the case of discrete distributions, where the alphabet size $S$ is unknown and may be comparable with the number of observations $n$. We treat the respective regions where the functional is "nonsmooth" and "smooth" separately. In the "nonsmooth" regime, we apply an unbiased estimator for the best polynomial approximation of the functional whereas, in the "smooth" regime, we apply a bias-corrected Maximum Likelihood Estimator (MLE). We illustrate the merit of this approach by thoroughly analyzing two important cases: the entropy $H(P) = \sum_{i = 1}^S -p_i \ln p_i$ and $F_α(P) = \sum_{i = 1}^S p_i^α,α>0$. We obtain the minimax $L_2$ rates for estimating these functionals. In particular, we demonstrate that our estimator achieves the optimal sample complexity $n \asymp S/\ln S$ for entropy estimation. We also show that the sample complexity for estimating $F_α(P),0<α<1$ is $n\asymp S^{1/α}/ \ln S$, which can be achieved by our estimator but not the MLE. For $1<α<3/2$, we show the minimax $L_2$ rate for estimating $F_α(P)$ is $(n\ln n)^{-2(α-1)}$ regardless of the alphabet size, while the $L_2$ rate for the MLE is $n^{-2(α-1)}$. For all the above cases, the behavior of the minimax rate-optimal estimators with $n$ samples is essentially that of the MLE with $n\ln n$ samples. We highlight the practical advantages of our schemes for entropy and mutual information estimation. We demonstrate that our approach reduces running time and boosts the accuracy compared to existing various approaches. Moreover, we show that the mutual information estimator induced by our methodology leads to significant performance boosts over the Chow--Liu algorithm in learning graphical models.
An Incentive Compatible Multi-Armed-Bandit Crowdsourcing Mechanism with Quality Assurance
Venue: arXiv cs.GT 2015
Year: 2015

Consider a requester who wishes to crowdsource a series of identical binary labeling tasks to a pool of workers so as to achieve an assured accuracy for each task, in a cost optimal way. The workers are heterogeneous with unknown but fixed qualities and their costs are private. The problem is to select for each task an optimal subset of workers so that the outcome obtained from the selected workers guarantees a target accuracy level. The problem is a challenging one even in a non strategic setting since the accuracy of aggregated label depends on unknown qualities. We develop a novel multi-armed bandit (MAB) mechanism for solving this problem. First, we propose a framework, Assured Accuracy Bandit (AAB), which leads to an MAB algorithm, Constrained Confidence Bound for a Non Strategic setting (CCB-NS). We derive an upper bound on the number of time steps the algorithm chooses a sub-optimal set that depends on the target accuracy level and true qualities. A more challenging situation arises when the requester not only has to learn the qualities of the workers but also elicit their true costs. We modify the CCB-NS algorithm to obtain an adaptive exploration separated algorithm which we call { \em Constrained Confidence Bound for a Strategic setting (CCB-S)}. CCB-S algorithm produces an ex-post monotone allocation rule and thus can be transformed into an ex-post incentive compatible and ex-post individually rational mechanism that learns the qualities of the workers and guarantees a given target accuracy level in a cost optimal way. We provide a lower bound on the number of times any algorithm should select a sub-optimal set and we see that the lower bound matches our upper bound upto a constant factor. We provide insights on the practical implementation of this framework through an illustrative example and we show the efficacy of our algorithms through simulations.
Building DNN Acoustic Models for Large Vocabulary Speech Recognition
Venue: arXiv cs.CL 2015
Year: 2015

Deep neural networks (DNNs) are now a central component of nearly all state-of-the-art speech recognition systems. Building neural network acoustic models requires several design decisions including network architecture, size, and training loss function. This paper offers an empirical investigation on which aspects of DNN acoustic model design are most important for speech recognition system performance. We report DNN classifier performance and final speech recognizer word error rates, and compare DNNs using several metrics to quantify factors influencing differences in task performance. Our first set of experiments use the standard Switchboard benchmark corpus, which contains approximately 300 hours of conversational telephone speech. We compare standard DNNs to convolutional networks, and present the first experiments using locally-connected, untied neural networks for acoustic modeling. We additionally build systems on a corpus of 2,100 hours of training data by combining the Switchboard and Fisher corpora. This larger corpus allows us to more thoroughly examine performance of large DNN models -- with up to ten times more parameters than those typically used in speech recognition systems. Our results suggest that a relatively simple DNN architecture and optimization technique produces strong results. These findings, along with previous work, help establish a set of best practices for building DNN hybrid speech recognition systems with maximum likelihood training. Our experiments in DNN optimization additionally serve as a case study for training DNNs with discriminative loss functions for speech tasks, as well as DNN classifiers more generally.
Squares of Random Linear Codes
Venue: arXiv cs.IT 2015
Year: 2015

Given a linear code $C$, one can define the $d$-th power of $C$ as the span of all componentwise products of $d$ elements of $C$. A power of $C$ may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code "typically" fill the whole space? We give a positive answer, for codes of dimension $k$ and length roughly $\frac{1}{2}k^2$ or smaller. Moreover, the convergence speed is exponential if the difference $k(k+1)/2-n$ is at least linear in $k$. The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros.
Dynamic Choreographies - Safe Runtime Updates of Distributed Applications
Venue: arXiv cs.PL 2015
Year: 2015

Programming distributed applications free from communication deadlocks and races is complex. Preserving these properties when applications are updated at runtime is even harder. We present DIOC, a language for programming distributed applications that are free from deadlocks and races by construction. A DIOC program describes a whole distributed application as a unique entity (choreography). DIOC allows the programmer to specify which parts of the application can be updated. At runtime, these parts may be replaced by new DIOC fragments from outside the application. DIOC programs are compiled, generating code for each site, in a lower-level language called DPOC. We formalise both DIOC and DPOC semantics as labelled transition systems and prove the correctness of the compilation as a trace equivalence result. As corollaries, DPOC applications are free from communication deadlocks and races, even in presence of runtime updates.
A New Primitive for a Diffie-Hellman-like Key Exchange Protocol Based on Multivariate Ore Polynomials
Venue: arXiv cs.CR 2015
Year: 2015

In this paper we present a new primitive for a key exchange protocol based on multivariate non-commutative polynomial rings, analogous to the classic Diffie-Hellman method. Our technique extends the proposed scheme of Boucher et al. from 2010. Their method was broken by Dubois and Kammerer in 2011, who exploited the Euclidean domain structure of the chosen ring. However, our proposal is immune against such attacks, without losing the advantages of non-commutative polynomial rings as outlined by Boucher et al. Moreover, our extension is not restricted to any particular ring, but is designed to allow users to readily choose from a large class of rings when applying the protocol. Our primitive can also be applied to other cryptographic paradigms. In particular, we develop a three-pass protocol, a public key cryptosystem, a digital signature scheme and a zero-knowledge proof protocol.
Extremal Mechanisms for Local Differential Privacy
Venue: arXiv cs.IT 2015
Year: 2015

Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where both the data providers and data analysts want to maximize the utility of statistical analyses performed on the released data, we study the fundamental trade-off between local differential privacy and utility. This trade-off is formulated as a constrained optimization problem: maximize utility subject to local differential privacy constraints. We introduce a combinatorial family of extremal privatization mechanisms, which we call staircase mechanisms, and show that it contains the optimal privatization mechanisms for a broad class of information theoretic utilities such as mutual information and $f$-divergences. We further prove that for any utility function and any privacy level, solving the privacy-utility maximization problem is equivalent to solving a finite-dimensional linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the size of the alphabet the data lives in. To account for this, we show that two simple privatization mechanisms, the binary and randomized response mechanisms, are universally optimal in the low and high privacy regimes, and well approximate the intermediate regime.
Identifying Cover Songs Using Information-Theoretic Measures of Similarity
Venue: arXiv cs.IR 2015
Year: 2015

This paper investigates methods for quantifying similarity between audio signals, specifically for the task of of cover song detection. We consider an information-theoretic approach, where we compute pairwise measures of predictability between time series. We compare discrete-valued approaches operating on quantised audio features, to continuous-valued approaches. In the discrete case, we propose a method for computing the normalised compression distance, where we account for correlation between time series. In the continuous case, we propose to compute information-based measures of similarity as statistics of the prediction error between time series. We evaluate our methods on two cover song identification tasks using a data set comprised of 300 Jazz standards and using the Million Song Dataset. For both datasets, we observe that continuous-valued approaches outperform discrete-valued approaches. We consider approaches to estimating the normalised compression distance (NCD) based on string compression and prediction, where we observe that our proposed normalised compression distance with alignment (NCDA) improves average performance over NCD, for sequential compression algorithms. Finally, we demonstrate that continuous-valued distances may be combined to improve performance with respect to baseline approaches. Using a large-scale filter-and-refine approach, we demonstrate state-of-the-art performance for cover song identification using the Million Song Dataset.
Bigtable Merge Compaction
Venue: arXiv cs.DS 2015
Year: 2015

NoSQL databases are widely used for massive data storage and real-time web applications. Yet important aspects of these data structures are not well understood. For example, NoSQL databases write most of their data to a collection of files on disk, meanwhile periodically compacting subsets of these files. A compaction policy must choose which files to compact, and when to compact them, without knowing the future workload. Although these choices can affect computational efficiency by orders of magnitude, existing literature lacks tools for designing and analyzing online compaction policies --- policies are now chosen largely by trial and error. Here we introduce tools for the design and analysis of compaction policies for Google Bigtable, propose new policies, give average-case and worst-case competitive analyses, and present preliminary empirical benchmarks.
Stability of Epidemic Models over Directed Graphs: A Positive Systems Approach
Venue: arXiv cs.SY 2015
Year: 2015

We study the stability properties of a susceptible-infected-susceptible (SIS) diffusion model, so-called the $n$-intertwined Markov model, over arbitrary directed network topologies. As in the majority of the work on infection spread dynamics, this model exhibits a threshold phenomenon. When the curing rates in the network are high, the disease-free state is the unique equilibrium over the network. Otherwise, an endemic equilibrium state emerges, where some infection remains within the network. Using notions from positive systems theory, {we provide novel proofs for the global asymptotic stability of the equilibrium points in both cases over strongly connected networks based on the value of the basic reproduction number, a fundamental quantity in the study of epidemics.} When the network topology is weakly connected, we provide conditions for the existence, uniqueness, and global asymptotic stability of an endemic state, and we study the stability of the disease-free state. Finally, we demonstrate that the $n$-intertwined Markov model can be viewed as a best-response dynamical system of a concave game among the nodes. This characterization allows us to cast new infection spread dynamics; additionally, we provide a sufficient condition for the global convergence to the disease-free state, which can be checked in a distributed fashion. Several simulations demonstrate our results.
Self-motions of pentapods with linear platform
Venue: arXiv cs.RO 2015
Year: 2015

We give a full classification of all pentapods with linear platform possessing a self-motion beside the trivial rotation about the platform. Recent research necessitates a contemporary and accurate re-examination of old results on this topic given by Darboux, Mannheim, Duporcq and Bricard, which also takes the coincidence of platform anchor points into account. For our study we use bond theory with respect to a novel kinematic mapping for pentapods with linear platform, beside the method of singular-invariant leg-rearrangements. Based on our results we design pentapods with linear platform, which have a simplified direct kinematics concerning their number of (real) solutions.