OpenRaiser/Intern-Atlas huggingface dataset:
On the Security of the Automatic Dependent Surveillance-Broadcast Protocol
Venue: arXiv cs.CR 2014
Year: 2014

Automatic dependent surveillance-broadcast (ADS-B) is the communications protocol currently being rolled out as part of next generation air transportation systems. As the heart of modern air traffic control, it will play an essential role in the protection of two billion passengers per year, besides being crucial to many other interest groups in aviation. The inherent lack of security measures in the ADS-B protocol has long been a topic in both the aviation circles and in the academic community. Due to recently published proof-of-concept attacks, the topic is becoming ever more pressing, especially with the deadline for mandatory implementation in most airspaces fast approaching. This survey first summarizes the attacks and problems that have been reported in relation to ADS-B security. Thereafter, it surveys both the theoretical and practical efforts which have been previously conducted concerning these issues, including possible countermeasures. In addition, the survey seeks to go beyond the current state of the art and gives a detailed assessment of security measures which have been developed more generally for related wireless networks such as sensor networks and vehicular ad hoc networks, including a taxonomy of all considered approaches.
Network Formation Games with Heterogeneous Players and the Internet Structure
Venue: arXiv cs.GT 2014
Year: 2014

We study the structure and evolution of the Internet's Autonomous System (AS) interconnection topology as a game with heterogeneous players. In this network formation game, the utility of a player depends on the network structure, e.g., the distances between nodes and the cost of links. We analyze static properties of the game, such as the prices of anarchy and stability and provide explicit results concerning the generated topologies. Furthermore, we discuss dynamic aspects, demonstrating linear convergence rate and showing that only a restricted subset of equilibria is feasible under realistic dynamics. We also consider the case where utility (or monetary) transfers are allowed between the players.
Cryptanalyzing a RGB image encryption algorithm based on DNA encoding and chaos map
Venue: arXiv cs.CR 2014
Year: 2014

Recently, a RGB image encryption algorithm based on DNA encoding and chaos map has been proposed. It was reported that the encryption algorithm can be broken with four pairs of chosen plain-images and the corresponding cipher-images. This paper re-evaluates the security of the encryption algorithm, and finds that the encryption algorithm can be broken efficiently with only one known plain-image. The effectiveness of the proposed known-plaintext attack is supported by both rigorous theoretical analysis and experimental results. In addition, two other security defects are also reported.
Computing Similarity Distances Between Rankings
Venue: arXiv cs.DS 2014
Year: 2014

We address the problem of computing distances between rankings that take into account similarities between candidates. The need for evaluating such distances is governed by applications as diverse as rank aggregation, bioinformatics, social sciences and data storage. The problem may be summarized as follows: Given two rankings and a positive cost function on transpositions that depends on the similarity of the candidates involved, find a smallest cost sequence of transpositions that converts one ranking into another. Our focus is on costs that may be described via special metric-tree structures and on complete rankings modeled as permutations. The presented results include a quadratic-time algorithm for finding a minimum cost decomposition for simple cycles, and a quadratic-time, $4/3$-approximation algorithm for permutations that contain multiple cycles. The proposed methods rely on investigating a newly introduced balancing property of cycles embedded in trees, cycle-merging methods, and shortest path optimization techniques.
Smart Streaming for Online Video Services
Venue: arXiv cs.MM 2014
Year: 2014

Bandwidth consumption is a significant concern for online video service providers. Practical video streaming systems usually use some form of HTTP streaming (progressive download) to let users download the video at a faster rate than the video bitrate. Since users may quit before viewing the complete video, however, much of the downloaded video will be "wasted". To the extent that users' departure behavior can be predicted, we develop smart streaming that can be used to improve user QoE with limited server bandwidth or save bandwidth cost with unlimited server bandwidth. Through measurement, we extract certain user behavior properties for implementing such smart streaming, and demonstrate its advantage using prototype implementation as well as simulations.
Bayesian Fusion of Multi-Band Images
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, a Bayesian fusion technique for remotely sensed multi-band images is presented. The observed images are related to the high spectral and high spatial resolution image to be recovered through physical degradations, e.g., spatial and spectral blurring and/or subsampling defined by the sensor characteristics. The fusion problem is formulated within a Bayesian estimation framework. An appropriate prior distribution exploiting geometrical consideration is introduced. To compute the Bayesian estimator of the scene of interest from its posterior distribution, a Markov chain Monte Carlo algorithm is designed to generate samples asymptotically distributed according to the target distribution. To efficiently sample from this high-dimension distribution, a Hamiltonian Monte Carlo step is introduced in the Gibbs sampling strategy. The efficiency of the proposed fusion method is evaluated with respect to several state-of-the-art fusion techniques. In particular, low spatial resolution hyperspectral and multispectral images are fused to produce a high spatial resolution hyperspectral image.
Effect of Spatial Interference Correlation on the Performance of Maximum Ratio Combining
Venue: arXiv cs.IT 2014
Year: 2014

While the performance of maximum ratio combining (MRC) is well understood for a single isolated link, the same is not true in the presence of interference, which is typically correlated across antennas due to the common locations of interferers. For tractability, prior work focuses on the two extreme cases where the interference power across antennas is either assumed to be fully correlated or fully uncorrelated. In this paper, we address this shortcoming and characterize the performance of MRC in the presence of spatially-correlated interference across antennas. Modeling the interference field as a Poisson point process, we derive the exact distribution of the signal-to-interference ratio (SIR) for the case of two receive antennas, and upper and lower bounds for the general case. Using these results, we study the diversity behavior of MRC and characterize the critical density of simultaneous transmissions for a given outage constraint. The exact SIR distribution is also useful in benchmarking simpler correlation models. We show that the full-correlation assumption is considerably pessimistic (up to 30% higher outage probability for typical values) and the no-correlation assumption is significantly optimistic compared to the true performance.
Generalized Wong sequences and their applications to Edmonds' problems
Venue: arXiv cs.CC 2014
Year: 2014

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix M whose entries are homogeneous linear polynomials over the integers. Given a linear subspace B of the n by n matrices over some field F, we consider the following problems: symbolic matrix rank (SMR) is the problem to determine the maximum rank among matrices in B, symbolic determinant identity testing (SDIT) is the question to decide whether there exists a nonsingular matrix in B. The constructive versions of these problems are asking to find a matrix of maximum rank, respectively a nonsingular matrix, if there exists one. Our first algorithm solves the constructive SMR when B is spanned by unknown rank one matrices, answering an open question of Gurvits. Our second algorithm solves the constructive SDIT when B is spanned by triangularizable matrices, but the triangularization is not given explicitly. Both algorithms work over finite fields of size at least n+1 and over the rational numbers, and the first algorithm actually solves (the non-constructive) SMR independently from the field size. Our main tool to obtain these results is to generalize Wong sequences, a classical method to deal with pairs of matrices, to the case of pairs of matrix spaces.
Distributed Blind Calibration via Output Synchronization in Lossy Sensor Networks
Venue: arXiv cs.SY 2014
Year: 2014

In this paper a novel distributed algorithm for blind macro calibration in sensor networks based on output synchronization is proposed. The algorithm is formulated as a set of gradient-type recursions for estimating parameters of sensor calibration functions, starting from local criteria defined as weighted sums of mean square differences between the outputs of neighboring sensors. It is proved, on the basis of an originally developed methodology for treating higher-order consensus (or output synchronization) schemes, that the algorithm achieves asymptotic agreement for sensor gains and offsets, in the mean square sense and with probability one. In the case of additive measurement noise, additive inter-agent communication noise, and communication outages, a modification of the original algorithm based on instrumental variables is proposed. It is proved using stochastic approximation arguments that the modified algorithm achieves asymptotic consensus for sensor gains and offsets, in the mean square sense and with probability one. Special attention is paid to the situation when a subset of sensors in the network remains with fixed characteristics. Illustrative simulation examples are provided.
How far does scientific community look back?
Venue: arXiv cs.DL 2014
Year: 2014

How does the published scientific literature used by scientific community? Many previous studies make analysis on the static usage data. In this research, we propose the concept of dynamic usage data. Based on the platform of realtime.springer.com, we have been monitoring and recording the dynamic usage data of Scientometrics articles round the clock. Our analysis find that papers published in recent four years have many more downloads than papers published four years ago. According to our quantitative calculation, papers down-loaded on one day have an average lifetime of 4.1 years approximately. Classic papers are still being downloaded frequently even long after their publication. Additionally, we find that social media may reboot the attention of old scientific literature in a short time.
On block coherence of frames
Venue: arXiv cs.IT 2014
Year: 2014

Block coherence of matrices plays an important role in analyzing the performance of block compressed sensing recovery algorithms (Bajwa and Mixon, 2012). In this paper, we characterize two block coherence metrics: worst-case and average block coherence. First, we present lower bounds on worst-case block coherence, in both the general case and also when the matrix is constrained to be a union of orthobases. We then present deterministic matrix constructions based upon Kronecker products which obtain these lower bounds. We also characterize the worst-case block coherence of random subspaces. Finally, we present a flipping algorithm that can improve the average block coherence of a matrix, while maintaining the worst-case block coherence of the original matrix. We provide numerical examples which demonstrate that our proposed deterministic matrix construction performs well in block compressed sensing.
Asymmetric-valued Spectrum Auction and Competition in Wireless Broadband Services
Venue: arXiv cs.NI 2014
Year: 2014

We study bidding and pricing competition between two spiteful mobile network operators (MNOs) with considering their existing spectrum holdings. Given asymmetric-valued spectrum blocks are auctioned off to them via a first-price sealed-bid auction, we investigate the interactions between two spiteful MNOs and users as a three-stage dynamic game and characterize the dynamic game's equilibria. We show an asymmetric pricing structure and different market share between two spiteful MNOs. Perhaps counter-intuitively, our results show that the MNO who acquires the less-valued spectrum block always lowers his service price despite providing double-speed LTE service to users. We also show that the MNO who acquires the high-valued spectrum block, despite charing a higher price, still achieves more market share than the other MNO. We further show that the competition between two MNOs leads to some loss of their revenues. By investigating a cross-over point at which the MNOs' profits are switched, it serves as the benchmark of practical auction designs.
Editing to a Connected Graph of Given Degrees
Venue: arXiv cs.DS 2014
Year: 2014

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function δ:V(G)->{1,...,d}, whether it is possible to obtain a connected graph G' from G such that the degree of v is δ(v) for any vertex v by at most k edge editing operations. As the problem is NP-complete even if δ(v)=2, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d+k. For the special case δ(v)=d, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only.
Parameterized Algorithms for Load Coloring Problem
Venue: arXiv cs.DS 2014
Year: 2014

One way to state the Load Coloring Problem (LCP) is as follows. Let $G=(V,E)$ be graph and let $f:V\rightarrow \{{\rm red}, {\rm blue}\}$ be a 2-coloring. An edge $e\in E$ is called red (blue) if both end-vertices of $e$ are red (blue). For a 2-coloring $f$, let $r'_f$ and $b'_f$ be the number of red and blue edges and let $μ_f(G)=\min\{r'_f,b'_f\}$. Let $μ(G)$ be the maximum of $μ_f(G)$ over all 2-colorings. We introduce the parameterized problem $k$-LCP of deciding whether $μ(G)\ge k$, where $k$ is the parameter. We prove that this problem admits a kernel with at most $7k$. Ahuja et al. (2007) proved that one can find an optimal 2-coloring on trees in polynomial time. We generalize this by showing that an optimal 2-coloring on graphs with tree decomposition of width $t$ can be found in time $O^*(2^t)$. We also show that either $G$ is a Yes-instance of $k$-LCP or the treewidth of $G$ is at most $2k$. Thus, $k$-LCP can be solved in time $O^*(4^k).$
MaLeS: A Framework for Automatic Tuning of Automated Theorem Provers
Venue: arXiv cs.AI 2014
Year: 2014

MaLeS is an automatic tuning framework for automated theorem provers. It provides solutions for both the strategy finding as well as the strategy scheduling problem. This paper describes the tool and the methods used in it, and evaluates its performance on three automated theorem provers: E, LEO-II and Satallax. An evaluation on a subset of the TPTP library problems shows that on average a MaLeS-tuned prover solves 8.67% more problems than the prover with its default settings.
Closed-Loop Beam Alignment for Massive MIMO Channel Estimation
Venue: arXiv cs.IT 2014
Year: 2014

Training sequences are designed to probe wireless channels in order to obtain channel state information for block-fading channels. Optimal training sounds the channel using orthogonal beamforming vectors to find an estimate that optimizes some cost function, such as mean square error. As the number of transmit antennas increases, however, the training overhead becomes significant. This creates a need for alternative channel estimation schemes for increasingly large transmit arrays. In this work, we relax the orthogonal restriction on sounding vectors. The use of a feedback channel after each forward channel use during training enables closed-loop sounding vector design. A misalignment cost function is introduced, which provides a metric to sequentially design sounding vectors. In turn, the structure of the sounding vectors aligns the transmit beamformer with the true channel direction, thereby increasing beamforming gain. This beam alignment scheme for massive MIMO is shown to improve beamforming gain over conventional orthogonal training for a MISO channel.
ConXsense - Automated Context Classification for Context-Aware Access Control
Venue: arXiv cs.CR 2014
Year: 2014

We present ConXsense, the first framework for context-aware access control on mobile devices based on context classification. Previous context-aware access control systems often require users to laboriously specify detailed policies or they rely on pre-defined policies not adequately reflecting the true preferences of users. We present the design and implementation of a context-aware framework that uses a probabilistic approach to overcome these deficiencies. The framework utilizes context sensing and machine learning to automatically classify contexts according to their security and privacy-related properties. We apply the framework to two important smartphone-related use cases: protection against device misuse using a dynamic device lock and protection against sensory malware. We ground our analysis on a sociological survey examining the perceptions and concerns of users related to contextual smartphone security and analyze the effectiveness of our approach with real-world context data. We also demonstrate the integration of our framework with the FlaskDroid architecture for fine-grained access control enforcement on the Android platform.
Redundancy Generation in University-Industry-Government Relations: The Triple Helix Modeled, Measured, and Simulated
Venue: arXiv cs.CY 2014
Year: 2014

A Triple Helix (TH) of bi- and trilateral relations among universities, industries, and governments can be considered as an ecosystem in which uncertainty can be reduced auto-catalytically. The correlations among the distributions of relations span a vector space in which two vectors (P and Q) represent "sending" and "receiving," respectively. These vectors can also be understood in terms of the generation versus reduction of uncertainty in the communication field that results from interactions among the three (bi-lateral) communication channels. We specify a set of Lotka-Volterra equations between the vectors that can be solved. Redundancy generation can then be simulated and the results can be decomposed in terms of the TH components. Among other things, we show that the strength and frequency of the relations are independent parameters. Different components in terms of frequencies in triple-helix systems can also be distinguished and interpreted using Fourier analysis of the empirical time-series. The case of co-authorship relations in Japan is analyzed as an empirical example; but "triple contingencies" in an ecosystem of relations can also be considered more generally as a model for redundancy generation by providing meaning to the (Shannon-type) information in inter-human communications.
Adaptive Multi-objective Optimization for Energy Efficient Interference Coordination in Multi-Cell Networks
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we investigate the distributed power allocation for multi-cell OFDMA networks taking both energy efficiency and inter-cell interference (ICI) mitigation into account. A performance metric termed as throughput contribution is exploited to measure how ICI is effectively coordinated. To achieve a distributed power allocation scheme for each base station (BS), the throughput contribution of each BS to the network is first given based on a pricing mechanism. Different from existing works, a biobjective problem is formulated based on multi-objective optimization theory, which aims at maximizing the throughput contribution of the BS to the network and minimizing its total power consumption at the same time. Using the method of Pascoletti and Serafini scalarization, the relationship between the varying parameters and minimal solutions is revealed. Furthermore, to exploit the relationship an algorithm is proposed based on which all the solutions on the boundary of the efficient set can be achieved by adaptively adjusting the involved parameters. With the obtained solution set, the decision maker has more choices on power allocation schemes in terms of both energy consumption and throughput. Finally, the performance of the algorithm is assessed by the simulation results.
Distributed Compressed Sensing For Static and Time-Varying Networks
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of in-network compressed sensing from distributed measurements. Every agent has a set of measurements of a signal $x$, and the objective is for the agents to recover $x$ from their collective measurements using only communication with neighbors in the network. Our distributed approach to this problem is based on the centralized Iterative Hard Thresholding algorithm (IHT). We first present a distributed IHT algorithm for static networks that leverages standard tools from distributed computing to execute in-network computations with minimized bandwidth consumption. Next, we address distributed signal recovery in networks with time-varying topologies. The network dynamics necessarily introduce inaccuracies to our in-network computations. To accommodate these inaccuracies, we show how centralized IHT can be extended to include inexact computations while still providing the same recovery guarantees as the original IHT algorithm. We then leverage these new theoretical results to develop a distributed version of IHT for time-varying networks. Evaluations show that our distributed algorithms for both static and time-varying networks outperform previously proposed solutions in time and bandwidth by several orders of magnitude.
Special Bent and Near-bent Functions
Venue: arXiv cs.IT 2014
Year: 2014

Starting from special near-bent functions in dimension 2t-1 we construct bent functions in dimension 2t having a specific derivative. We deduce new famillies of bent functions
Algorithms and Bounds for Drawing Non-planar Graphs with Crossing-free Subgraphs
Venue: arXiv cs.CG 2014
Year: 2014

We initiate the study of the following problem: Given a non-planar graph G and a planar subgraph S of G, does there exist a straight-line drawing Γ of G in the plane such that the edges of S are not crossed in Γ by any edge of G? We give positive and negative results for different kinds of connected spanning subgraphs S of G. Moreover, in order to enlarge the subset of instances that admit a solution, we consider the possibility of bending the edges of G not in S; in this setting we discuss different trade-offs between the number of bends and the required drawing area.
Reconstruction and uniqueness of moving obstacles
Venue: arXiv cs.DS 2014
Year: 2014

We study the uniqueness and accuracy of the numerical solution of the problem of reconstruction of the shape and trajectory of a reflecting obstacle moving in an inhomogeneous medium from travel times, start and end points, and initial angles of ultrasonic rays reflecting at the obstacle. The speed of sound in the domain when there is no obstacle present is known and provided as an input parameter which together with the other initial data enables the algorithm to trace ray paths and find their reflection points. The reflection points determine with high-resolution the shape and trajectory of the obstacle. The method has predictable computational complexity and performance and is very efficient when it is parallelized and optimized because only a small portion of the domain is reconstructed.