Biblio

Nearest neighbor search is a fundamental problem in various research fields like machine learning, data mining and pattern recognition. Recently, hashing-based approaches, for example, locality sensitive hashing (LSH), are proved to be effective for scalable high dimensional nearest neighbor search. Many hashing algorithms found their theoretic root in random projection. Since these algorithms generate the hash tables (projections) randomly, a large number of hash tables (i.e., long codewords) are required in order to achieve both high precision and recall. To address this limitation, we propose a novel hashing algorithm called density sensitive hashing (DSH) in this paper. DSH can be regarded as an extension of LSH. By exploring the geometric structure of the data, DSH avoids the purely random projections selection and uses those projective functions which best agree with the distribution of the data. Extensive experimental results on real-world data sets have shown that the proposed method achieves better performance compared to the state-of-the-art hashing approaches.

Blind Source Separation (BSS) deals with the recovery of source signals from a set of observed mixtures, when little or no knowledge of the mixing process is available. BSS can find an application in the context of network coding, where relaying linear combinations of packets maximizes the throughput and increases the loss immunity. By relieving the nodes from the need to send the combination coefficients, the overhead cost is largely reduced. However, the scaling ambiguity of the technique and the quasi-uniformity of compressed media sources makes it unfit, at its present state, for multimedia transmission. In order to open new practical applications for BSS in the context of multimedia transmission, we have recently proposed to use a non-linear encoding to increase the discriminating power of the classical entropy-based separation methods. Here, we propose to append to each source a non-linear message digest, which offers an overhead smaller than a per-symbol encoding and that can be more easily tuned. Our results prove that our algorithm is able to provide high decoding rates for different media types such as image, audio, and video, when the transmitted messages are less than 1.5 kilobytes, which is typically the case in a realistic transmission scenario.

Image inpainting is the process of filling the unwanted region in an image marked by the user. It is used for restoring old paintings and photographs, removal of red eyes from pictures, etc. In this paper, we propose an efficient inpainting algorithm which takes care of false edge propagation. We use the classical exemplar based technique to find out the priority term for each patch. To ensure that the edge content of the nearest neighbor patch found by minimizing L2 distance between patches, we impose an additional constraint that the entropy of the patches be similar. Entropy of the patch acts as a good measure of edge content. Additionally, we fill the image by considering overlapping patches to ensure smoothness in the output. We use structural similarity index as the measure of similarity between ground truth and inpainted image. The results of the proposed approach on a number of examples on real and synthetic images show the effectiveness of our algorithm in removing objects and thin scratches or text written on image. It is also shown that the proposed approach is robust to the shape of the manually selected target. Our results compare favorably to those obtained by existing techniques.
 

Sources such as speakers and environments from different communication devices produce signal variations that result in interference generated by different communication devices. Despite these convolutions, signal variations produced by different mobile devices leave intrinsic fingerprints on recorded calls, thus allowing the tracking of the models and brands of engaged mobile devices. This study aims to investigate the use of recorded Voice over Internet Protocol calls in the blind identification of source mobile devices. The proposed scheme employs a combination of entropy and mel-frequency cepstrum coefficients to extract the intrinsic features of mobile devices and analyzes these features with a multi-class support vector machine classifier. The experimental results lead to an accurate identification of 10 source mobile devices with an average accuracy of 99.72%.
 

Wireless information security generates shared secret keys from reciprocal channel dynamics. Current solutions are mostly based on temporal per-frame channel measurements of signal strength and suffer from low key generate rate (KGR), large budget in channel probing, and poor secrecy if a channel does not temporally vary significantly. This paper designs a cross-layer solution that measures noise-free per-symbol channel dynamics across both time and frequency domain and derives keys from the highly fine-grained per-symbol reciprocal channel measurements. This solution consists of merits that: (1) the persymbol granularity improves the volume of available uncorrelated channel measurements by orders of magnitude over per-frame granularity in conventional solutions and so does KGR; 2) the solution exploits subtle channel fluctuations in frequency domain that does not force users to move to incur enough temporal variations as conventional solutions require; and (3) it measures noise-free channel response that suppresses key bit disagreement between trusted users. As a result, in every aspect, the proposed solution improves the security performance by orders of magnitude over conventional solutions. The performance has been evaluated on both a GNU SDR testbed in practice and a local GNU Radio simulator. The cross-layer solution can generate a KGR of 24.07 bits per probing frame on testbed or 19 bits in simulation, although conventional optimal solutions only has a KGR of at most one or two bit per probing frame. It also has a low key bit disagreement ratio while maintaining a high entropy rate. The derived keys show strong independence with correlation coefficients mostly less than 0.05. Furthermore, it is empirically shown that any slight physical change, e.g. a small rotation of antenna, results in fundamentally different cross-layer frequency measurements, which implies the strong secrecy and high efficiency of the proposed solution.
 

Virtualized environments are widely thought to cause problems for software-based random number generators (RNGs), due to use of virtual machine (VM) snapshots as well as fewer and believed-to-be lower quality entropy sources. Despite this, we are unaware of any published analysis of the security of critical RNGs when running in VMs. We fill this gap, using measurements of Linux's RNG systems (without the aid of hardware RNGs, the most common use case today) on Xen, VMware, and Amazon EC2. Despite CPU cycle counters providing a significant source of entropy, various deficiencies in the design of the Linux RNG makes its first output vulnerable during VM boots and, more critically, makes it suffer from catastrophic reset vulnerabilities. We show cases in which the RNG will output the exact same sequence of bits each time it is resumed from the same snapshot. This can compromise, for example, cryptographic secrets generated after resumption. We explore legacy-compatible countermeasures, as well as a clean-slate solution. The latter is a new RNG called Whirlwind that provides a simpler, more-secure solution for providing system randomness.
 

As any veteran of the editor wars can attest, Unix users can be fiercely and irrationally attached to the commands they use and the manner in which they use them. In this work, we investigate the problem of identifying users out of a large set of candidates (25-97) through their command-line histories. Using standard algorithms and feature sets inspired by natural language authorship attribution literature, we demonstrate conclusively that individual users can be identified with a high degree of accuracy through their command-line behavior. Further, we report on the best performing feature combinations, from the many thousands that are possible, both in terms of accuracy and generality. We validate our work by experimenting on three user corpora comprising data gathered over three decades at three distinct locations. These are the Greenberg user profile corpus (168 users), Schonlau masquerading corpus (50 users) and Cal Poly command history corpus (97 users). The first two are well known corpora published in 1991 and 2001 respectively. The last is developed by the authors in a year-long study in 2014 and represents the most recent corpus of its kind. For a 50 user configuration, we find feature sets that can successfully identify users with over 90% accuracy on the Cal Poly, Greenberg and one variant of the Schonlau corpus, and over 87% on the other Schonlau variant.

Mobile Voice over Internet Protocol (mVoIP) applications have gained increasing popularity in the last few years, with millions of users communicating using such applications (e.g. Skype). Similar to other forms of Internet and telecommunications, mVoIP communications are vulnerable to both lawful and unauthorized interceptions. Encryption is a common way of ensuring the privacy of mVoIP users. To the best of our knowledge, there has been no academic study to determine whether mVoIP applications provide encrypted communications. In this paper, we examine Skype and nine other popular mVoIP applications for Android mobile devices, and analyze the intercepted communications to determine whether the captured voice and text communications are encrypted (or not). The results indicate that most of the applications encrypt text communications. However, voice communications may not be encrypted in six of the ten applications examined.

Fingerprint-based Audio recognition system must address concurrent objectives. Indeed, fingerprints must be both robust to distortions and discriminative while their dimension must remain to allow fast comparison. This paper proposes to restate these objectives as a penalized sparse representation problem. On top of this dictionary-based approach, we propose a structured sparsity model in the form of a probabilistic distribution for the sparse support. A practical suboptimal greedy algorithm is then presented and evaluated on robustness and recognition tasks. We show that some existing methods can be seen as particular cases of this algorithm and that the general framework allows to reach other points of a Pareto-like continuum.

In this paper, we consider the security of exact-repair regenerating codes operating at the minimum-storage-regenerating (MSR) point. The security requirement (introduced in Shah et. al.) is that no information about the stored data file must be leaked in the presence of an eavesdropper who has access to the contents of ℓ1 nodes as well as all the repair traffic entering a second disjoint set of ℓ2 nodes. We derive an upper bound on the size of a data file that can be securely stored that holds whenever ℓ2 ≤ d - k + 1. This upper bound proves the optimality of the product-matrix-based construction of secure MSR regenerating codes by Shah et. al.

This paper investigates the vulnerability of power grids based on the complex networks combining the information entropy. The difference of current directions for a link is considered, and it is characterized by the information entropy. By combining the information entropy, the electrical betweenness is improved to evaluate the vulnerability of power grids. Attacking the link based on the largest electrical betweenness with the information can get the larger size of the largest cluster and the lower lost of loads, compared with the electrical betweenness without the information entropy. Finally, IEEE 118 bus system is tested to validate the effectiveness of the novel index to characterize the the vulnerability of power grids.

In this paper, we consider the security of exact-repair regenerating codes operating at the minimum-storage-regenerating (MSR) point. The security requirement (introduced in Shah et. al.) is that no information about the stored data file must be leaked in the presence of an eavesdropper who has access to the contents of ℓ1 nodes as well as all the repair traffic entering a second disjoint set of ℓ2 nodes. We derive an upper bound on the size of a data file that can be securely stored that holds whenever ℓ2 ≤ d - k + 1. This upper bound proves the optimality of the product-matrix-based construction of secure MSR regenerating codes by Shah et. al.