OpenRaiser/Intern-Atlas huggingface dataset:
The Curious Case of the PDF Converter that Likes Mozart: Dissecting and Mitigating the Privacy Risk of Personal Cloud Apps
Venue: arXiv cs.CY 2016
Year: 2016

Third party apps that work on top of personal cloud services such as Google Drive and Dropbox, require access to the user's data in order to provide some functionality. Through detailed analysis of a hundred popular Google Drive apps from Google's Chrome store, we discover that the existing permission model is quite often misused: around two thirds of analyzed apps are over-privileged, i.e., they access more data than is needed for them to function. In this work, we analyze three different permission models that aim to discourage users from installing over-privileged apps. In experiments with 210 real users, we discover that the most successful permission model is our novel ensemble method that we call Far-reaching Insights. Far-reaching Insights inform the users about the data-driven insights that apps can make about them (e.g., their topics of interest, collaboration and activity patterns etc.) Thus, they seek to bridge the gap between what third parties can actually know about users and users perception of their privacy leakage. The efficacy of Far-reaching Insights in bridging this gap is demonstrated by our results, as Far-reaching Insights prove to be, on average, twice as effective as the current model in discouraging users from installing over-privileged apps. In an effort for promoting general privacy awareness, we deploy a publicly available privacy oriented app store that uses Far-reaching Insights. Based on the knowledge extracted from data of the store's users (over 115 gigabytes of Google Drive data from 1440 users with 662 installed apps), we also delineate the ecosystem for third-party cloud apps from the standpoint of developers and cloud providers. Finally, we present several general recommendations that can guide other future works in the area of privacy for the cloud.
Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimization
Venue: arXiv cs.LG 2016
Year: 2016

We consider the problem of solving mixed random linear equations with $k$ components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the case where the labels (which sample corresponds to which model) are not observed. We give a tractable algorithm for the mixed linear equation problem, and show that under some technical conditions, our algorithm is guaranteed to solve the problem exactly with sample complexity linear in the dimension, and polynomial in $k$, the number of components. Previous approaches have required either exponential dependence on $k$, or super-linear dependence on the dimension. The proposed algorithm is a combination of tensor decomposition and alternating minimization. Our analysis involves proving that the initialization provided by the tensor method allows alternating minimization, which is equivalent to EM in our setting, to converge to the global optimum at a linear rate.
Non-Orthogonal Multiple Access (NOMA) in Cellular Uplink and Downlink: Challenges and Enabling Techniques
Venue: arXiv cs.NI 2016
Year: 2016

By combining the concepts of superposition coding at the transmitter(s) and successive interference cancellation (SIC) at the receiver(s), non-orthogonal multiple access (NOMA) has recently emerged as a promising multiple access technique for 5G wireless technology. In this article, we first discuss the fundamentals of uplink and downlink NOMA transmissions and outline their key distinctions (in terms of implementation complexity, detection and decoding at the SIC receiver(s), incurred intra-cell and inter-cell interferences). Later, for both downlink and uplink NOMA, we theoretically derive the NOMA dominant condition for each individual user in a two-user NOMA cluster. NOMA dominant condition refers to the condition under which the spectral efficiency gains of NOMA are guaranteed compared to conventional orthogonal multiple access (OMA). The derived conditions provide direct insights on selecting appropriate users in two-user NOMA clusters. The conditions are distinct for uplink and downlink as well as for each individual user. Numerical results show the significance of the derived conditions for the user selection in uplink/downlink NOMA clusters and provide a comparison to the random user selection. A brief overview of the recent research investigations is then provided to highlight the existing research gaps. Finally, we discuss the potential applications and key challenges of NOMA transmissions.
Capacity of the Energy Harvesting Gaussian MAC
Venue: arXiv cs.IT 2016
Year: 2016

We consider an energy harvesting multiple access channel (MAC) where the transmitters are powered by an exogenous stochastic energy harvesting process and equipped with finite batteries. We characterize the capacity region of this channel as n-letter mutual information rate and develop inner and outer bounds that differ by a constant gap. An interesting conclusion that emerges from our results is that the sum-capacity approaches that of a standard AWGN MAC (with only an average constraint on the transmitted power), as the number of users in the MAC becomes large.
Computation Offloading Decisions for Reducing Completion Time
Venue: arXiv cs.DC 2016
Year: 2016

We analyze the conditions in which offloading computation reduces completion time. We extend the existing literature by deriving an inequality (Eq. 4) that relates computation offloading system parameters to the bits per instruction ratio of a computational job. This ratio is the inverse of the arithmetic intensity. We then discuss how this inequality can be used to determine the computations that can benefit from offloading as well as the computation offloading systems required to make offloading beneficial for particular computations.
Managing The Dynamics Of A Harmonic Potential Field-Guided Robot In A Cluttered Environment
Venue: arXiv cs.RO 2016
Year: 2016

This paper demonstrates the ability of the harmonic potential field, HPF, planning method to generate a well-behaved constrained path for a robot with second order dynamics in a cluttered environment. It is shown that HPF-based controllers may be developed for holonomic as well as nonholonomic robots to effectively suppress the effect of inertial forces on the robot trajectory while maintaining all the attractive features of a purely kinematic HPF planner. The capabilities of the suggested navigation controller are demonstrated using simulation results. Comparisons are also supplied with other approaches used for converting the guidance signal from a purely kinematic HPF planner into a navigation control signal.
Quality Analysis of a Chaotic Proven Keyed Hash Function
Venue: arXiv cs.CR 2016
Year: 2016

Hash functions are cryptographic tools, which are notably involved in integrity checking and password storage. They are of primary importance to improve the security of exchanges through the Internet. However, as security flaws have been recently identified in the current standard in this domain, new ways to hash digital data must be investigated. In this document an original keyed hash function is evaluated. It is based on asynchronous iterations leading to functions that have been proven to be chaotic. It thus possesses various topological properties as uniformity and sensibility to its initial condition. These properties make our hash function satisfies established security requirements in this field. This claim is qualitatively proven and experimentally verified in this research work, among other things by realizing a large number of simulations.
Two Security Layers for Hierarchical Data Aggregation in Sensor Networks
Venue: arXiv cs.DC 2016
Year: 2016

Due to resource restricted sensor nodes, it is important to minimize the amount of data transmission among sensor networks. To reduce the amount of sending data, an aggregation approach can be applied along the path from sensors to the sink. However, as sensor networks are often deployed in untrusted and even hostile environments, sensor nodes are prone to node compromise attacks. Hence, an end-to-end secure aggregation approach is required to ensure a healthy data reception. In this paper, we propose two layers for secure data aggregation in sensor networks. Firstly, we provide an end-to-end encryption scheme that supports operations over cypher-text. It is based on elliptic curve cryptography that exploits a smaller key size, allows the use of higher number of operations on cypher-texts, and prevents the distinction between two identical texts from their cryptograms. Secondly, we propose a new watermarking-based authentication that enables sensor nodes to ensure the identity of other nodes they are communicating with. Our experiments show that our hybrid approach of secure data aggregation enhances the security, significantly reduces computation and communication overhead, and can be practically implemented in on-the-shelf sensor platforms.
Distributed Probabilistic Bisection Search using Social Learning
Venue: arXiv cs.SI 2016
Year: 2016

We present a novel distributed probabilistic bisection algorithm using social learning with application to target localization. Each agent in the network first constructs a query about the target based on its local information and obtains a noisy response. Agents then perform a Bayesian update of their beliefs followed by an averaging of the log beliefs over local neighborhoods. This two stage algorithm consisting of repeated querying and averaging runs until convergence. We derive bounds on the rate of convergence of the beliefs at the correct target location. Numerical simulations show that our method outperforms current state of the art methods.
The Random Access Zipper: Simple, Purely-Functional Sequences
Venue: arXiv cs.DS 2016
Year: 2016

We introduce the Random Access Zipper (RAZ), a simple, purely-functional data structure for editable sequences. A RAZ combines the structure of a zipper with that of a tree: like a zipper, edits at the cursor require constant time; by leveraging tree structure, relocating the edit cursor in the sequence requires logarithmic time. While existing data structures provide these time bounds, none do so with the same simplicity and brevity of code as the RAZ. The simplicity of the RAZ provides the opportunity for more programmers to extend the structure to their own needs, and we provide some suggestions for how to do so.
Deterministic and Fast Randomized Test-and-Set in Optimal Space
Venue: arXiv cs.DC 2016
Year: 2016

The test-and-set object is a fundamental synchronization primitive for shared memory systems. A test-and-set object stores a bit, initialized to 0, and supports one operation, test&set(), which sets the bit's value to 1 and returns its previous value. This paper studies the number of atomic registers required to implement a test-and-set object in the standard asynchronous shared memory model with n processes. The best lower bound is log(n)-1 for obstruction-free (Giakkoupis and Woelfel, 2012) and deadlock-free (Styer and Peterson, 1989) implementations. Recently a deterministic obstruction-free implementation using O(sqrt(n)) registers was presented (Giakkoupis, Helmi, Higham, and Woelfel, 2013). This paper closes the gap between these known upper and lower bounds by presenting a deterministic obstruction-free implementation of a test-and-set object from Theta(log n) registers of size Theta(log n) bits. We also provide a technique to transform any deterministic obstruction-free algorithm, in which, from any configuration, any process can finish if it runs for b steps without interference, into a randomized wait-free algorithm for the oblivious adversary, in which the expected step complexity is polynomial in n and b. This transformation allows us to combine our obstruction-free algorithm with the randomized test-and-set algorithm by Giakkoupis and Woelfel (2012), to obtain a randomized wait-free test-and-set algorithm from Theta(log n) registers, with expected step-complexity Theta(log* n) against the oblivious adversary.
Computing Zigzag Persistent Cohomology
Venue: arXiv cs.CG 2016
Year: 2016

Zigzag persistent homology is a powerful generalisation of persistent homology that allows one not only to compute persistence diagrams with less noise and using less memory, but also to use persistence in new fields of application. However, due to the increase in complexity of the algebraic treatment of the theory, most algorithmic results in the field have remained of theoretical nature. This article describes an efficient algorithm to compute zigzag persistence, emphasising on its practical interest. The algorithm is a zigzag persistent cohomology algorithm, based on the dualisation of reflections and transpositions transformations within the zigzag sequence. We provide an extensive experimental study of the algorithm. We study the algorithm along two directions. First, we compare its performance with zigzag persistent homology algorithm and show the interest of cohomology in zigzag persistence. Second, we illustrate the interest of zigzag persistence in topological data analysis by comparing it to state of the art methods in the field, specifically optimised algorithm for standard persistent homology and sparse filtrations. We compare the memory and time complexities of the different algorithms, as well as the quality of the output persistence diagrams.
Hybrid Duplex Switching in Heterogeneous Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, a novel hybrid-duplex scheme based on received power is proposed for heterogeneous networks (HetNets). In the proposed scheme, the duplex mode (half- or full-duplex) of each user is switchable according to the received power from its serving base station (BS). The signal-to-interference-plus-noise-ratio (SINR) and spectral efficiency are analyzed for both downlink and uplink channels by using the tools of \emph{inhomogeneous} Poisson point process. Furthermore, determining power threshold for duplex mode switching is investigated for sum rate maximization, which is formulated as a nonlinear integer programming problem and a greedy algorithm is proposed to solve this problem. The theoretical analysis and the proposed algorithm are evaluated by numerical simulations. Simulation results show that the proposed hybrid-duplex scheme outperforms the half-duplex or full-duplex HetNet schemes.
Estimating Maximum Error Impact in Dynamic Data-driven Applications for Resource-aware Adaption of Software-based Fault-Tolerance
Venue: arXiv cs.DC 2016
Year: 2016

The rise of transient faults in modern hardware requires system designers to consider errors occurring at runtime. Both hardware- and software-based error handling must be deployed to meet application reliability requirements. The level of required reliability can vary for system components and depend on input and state, so that a selective use of resilience methods is advised, especially for resource-constrained platforms as found in embedded systems. If an error occurring at runtime can be classified as having negligible or tolerable impact, less effort can be spent on correcting it. As the actual impact of an error is often dependent on the state of a system at time of occurrence, it can not be determined precisely for highly dynamic workloads in data-driven applications. We present a concept to estimate error propagation in sets of tasks with variable data dependencies. This allows for a coarse grained analysis of the impact a failed task may have on the overall output. As an application example, we demonstrate our method for a typical dynamic embedded application, namely a decoder for the H.264 video format.
Monadic Datalog Containment on Trees Using the Descendant-Axis
Venue: arXiv cs.LO 2016
Year: 2016

In their AMW14-paper, Frochaux, Grohe, and Schweikardt showed that the query containment problem for monadic datalog on finite unranked labeled trees is Exptime-complete when (a) considering unordered trees using the child-axis, and when (b) considering ordered trees using the axes firstchild, nextsibling, and child. Furthermore, when allowing to use also the descendant-axis, the query containment problem was shown to be solvable in 2-fold exponential time, but it remained open to determine the problems exact complexity in presence of the descendant-axis. The present paper closes this gap by showing that, in the presence of the descendant-axis, the problem is 2Exptime-hard.
Squares of Low Maximum Degree
Venue: arXiv cs.DS 2016
Year: 2016

A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n^4)-time solvable for graphs of maximum degree at most 6.
MISO: An intermediate language to express parallel and dependable programs
Venue: arXiv cs.DC 2016
Year: 2016

One way to write fast programs is to explore the potential parallelism and take advantage of the high number of cores available in microprocessors. This can be achieved by manually specifying which code executes on which thread, by using compiler parallelization hints (such as OpenMP or Cilk), or by using a parallel programming language (such as X10, Chapel or Aeminium. Regardless of the approach, all of these programs are compiled to an intermediate lower-level language that is sequential, thus preventing the backend compiler from optimizing the program and observing its parallel nature. This paper presents MISO, an intermediate language that expresses the parallel nature of programs and that can be targeted by front-end compilers. The language defines 'cells', which are composed by a state and a transition function from one state to the next. This language can express both sequential and parallel programs, and provides information for a backend- compiler to generate efficient parallel programs. Moreover, MISO can be used to automatically add redundancy to a program, by replicating the state or by taking advantage of different processor cores, in order to provide fault tolerance for programs running on unreliable hardware.
Analytical Investigations on Carrier Phase Recovery in Dispersion-Unmanaged n-PSK Coherent Optical Communication Systems
Venue: arXiv cs.IT 2016
Year: 2016

Using coherent optical detection and digital signal processing, laser phase noise and equalization enhanced phase noise can be effectively mitigated using the feed-forward and feed-back carrier phase recovery approaches. In this paper, theoretical analyses of feed-back and feed-forward carrier phase recovery methods have been carried out in the long-haul high-speed n-level phase shift keying (n-PSK) optical fiber communication systems, involving a one-tap normalized least-mean-square (LMS) algorithm, a block-wise average algorithm, and a Viterbi-Viterbi algorithm. The analytical expressions for evaluating the estimated carrier phase and for predicting the bit-error-rate (BER) performance (such as the BER floors) have been presented and discussed in the n-PSK coherent optical transmission systems by considering both the laser phase noise and the equalization enhanced phase noise. The results indicate that the Viterbi-Viterbi carrier phase recovery algorithm outperforms the one-tap normalized LMS and the block-wise average algorithms for small phase noise variance (or effective phase noise variance), while the one-tap normalized LMS algorithm shows a better performance than the other two algorithms for large phase noise variance (or effective phase noise variance). In addition, the one-tap normalized LMS algorithm is more sensitive to the level of modulation formats.
A Survey on Honeypot Software and Data Analysis
Venue: arXiv cs.CR 2016
Year: 2016

In this survey, we give an extensive overview on honeypots. This includes not only honeypot software but also methodologies to analyse honeypot data.
Job Placement Advisor Based on Turnaround Predictions for HPC Hybrid Clouds
Venue: arXiv cs.DC 2016
Year: 2016

Several companies and research institutes are moving their CPU-intensive applications to hybrid High Performance Computing (HPC) cloud environments. Such a shift depends on the creation of software systems that help users decide where a job should be placed considering execution time and queue wait time to access on-premise clusters. Relying blindly on turnaround prediction techniques will affect negatively response times inside HPC cloud environments. This paper introduces a tool to make job placement decisions in HPC hybrid cloud environments taking into account the inaccuracy of execution and waiting time predictions. We used job traces from real supercomputing centers to run our experiments, and compared the performance between environments using real speedup curves. We also extended a state-of-the-art machine learning based predictor to work with data from the cluster scheduler. Our main findings are: (i) depending on workload characteristics, there is a turning point where predictions should be disregarded in favor of a more conservative decision to minimize job turnaround times and (ii) scheduler data plays a key role in improving predictions generated with machine learning using job trace data---our experiments showed around 20% prediction accuracy improvements.
Large-scale Continuous Gesture Recognition Using Convolutional Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

This paper addresses the problem of continuous gesture recognition from sequences of depth maps using convolutional neutral networks (ConvNets). The proposed method first segments individual gestures from a depth sequence based on quantity of movement (QOM). For each segmented gesture, an Improved Depth Motion Map (IDMM), which converts the depth sequence into one image, is constructed and fed to a ConvNet for recognition. The IDMM effectively encodes both spatial and temporal information and allows the fine-tuning with existing ConvNet models for classification without introducing millions of parameters to learn. The proposed method is evaluated on the Large-scale Continuous Gesture Recognition of the ChaLearn Looking at People (LAP) challenge 2016. It achieved the performance of 0.2655 (Mean Jaccard Index) and ranked $3^{rd}$ place in this challenge.
Design and Analysis of Downlink Channel Estimation Based on Parametric Model for Massive MIMO in FDD Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates downlink channel estimation in frequency-division duplex (FDD)-based massive multiple-input multiple-output (MIMO) systems. To reduce the overhead of downlink channel estimation and uplink feedback in FDD systems, cascaded precoding has been used in massive MIMO such that only a low-dimensional effective channel needs to be estimated and fed back. On the other hand, traditional channel estimations can hardly achieve the minimum mean-square-error (MMSE) performance due to lack of the a priori knowledge of the channels. In this paper, we design and analyze a strategy for downlink channel estimation based on the parametric model in massive MIMO with cascaded precoding. For a parametric model, channel frequency responses are expressed using the path delays and the associated complex amplitudes. The path delays of uplink channels are first estimated and quantized at the base station, then fed forward to the user equipment (UE) through a dedicated feedforward link. In this manner, the UE can obtain the a priori knowledge of the downlink channel in advance since it has been demonstrated that the downlink and the uplink channels can have identical path delays. Our analysis and simulation results show that the proposed approach can achieve near-MMSE performance.