OpenRaiser/Intern-Atlas huggingface dataset:
Secured Message Transmission in Mobile AD HOC Networks through Identification and Removal of Byzantine Failures
Venue: arXiv cs.NI 2011
Year: 2011

The emerging need for mobile ad hoc networks and secured data transmission phase is of crucial importance depending upon the environments like military. In this paper, a new way to improve the reliability of message transmission is presented. In the open collaborative MANET environment, any node can maliciously or selfishly disrupt and deny communication of other nodes. Dynamic changing topology makes it hard to determine the adversary nodes that affect the communication in MANET. An SMT protocol provides a way to secure message transmission by dispersing the message among several paths with minimal redundancy. The multiple routes selected are known as APS -Active Path Set. This paper describes a technique for fault discovery process to identify Byzantine failures which include nodes that drop, modify, or mis-route packets in an attempt to disrupt the routing service. An adaptive probing technique detects a malicious link through binary search and according to the nodes behavior, these links are avoided in the active path by multiplicatively increasing their weights. The proposed scheme provides secure communication even with increased number of adversaries.
Bayesian approach for near-duplicate image detection
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we propose a bayesian approach for near-duplicate image detection, and investigate how different probabilistic models affect the performance obtained. The task of identifying an image whose metadata are missing is often demanded for a myriad of applications: metadata retrieval in cultural institutions, detection of copyright violations, investigation of latent cross-links in archives and libraries, duplicate elimination in storage management, etc. The majority of current solutions are based either on voting algorithms, which are very precise, but expensive; either on the use of visual dictionaries, which are efficient, but less precise. Our approach, uses local descriptors in a novel way, which by a careful application of decision theory, allows a very fine control of the compromise between precision and efficiency. In addition, the method attains a great compromise between those two axes, with more than 99% accuracy with less than 10 database operations.
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Quadratic Integer Programming with PSD Objectives
Venue: arXiv cs.CC 2011
Year: 2011

We present an approximation scheme for optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes well known graph problems such as Minimum graph bisection, Edge expansion, Uniform sparsest cut, and Small Set expansion, as well as the Unique Games problem. These problems are notorious for the existence of huge gaps between the known algorithmic results and NP-hardness results. Our algorithm is based on rounding semidefinite programs from the Lasserre hierarchy, and the analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix. For all the above graph problems, we give an algorithm running in time $n^{O(r/ε^2)}$ with approximation ratio $\frac{1+ε}{\min\{1,λ_r\}}$, where $λ_r$ is the $r$'th smallest eigenvalue of the normalized graph Laplacian $\mathcal{L}$. In the case of graph bisection and small set expansion, the number of vertices in the cut is within lower-order terms of the stipulated bound. Our results imply $(1+O(ε))$ factor approximation in time $n^{O(r^\ast/ε^2)}$ where $r^\ast$ is the number of eigenvalues of $\mathcal{L}$ smaller than $1-ε$. For Unique Games, we give a factor $(1+\frac{2+ε}{λ_r})$ approximation for minimizing the number of unsatisfied constraints in $n^{O(r/ε)}$ time. This improves an earlier bound for solving Unique Games on expanders, and also shows that Lasserre SDPs are powerful enough to solve well-known integrality gap instances for the basic SDP. We also give an algorithm for independent sets in graphs that performs well when the Laplacian does not have too many eigenvalues bigger than $1+o(1)$.
Security Through Amnesia: A Software-Based Solution to the Cold Boot Attack on Disk Encryption
Venue: arXiv cs.CR 2011
Year: 2011

Disk encryption has become an important security measure for a multitude of clients, including governments, corporations, activists, security-conscious professionals, and privacy-conscious individuals. Unfortunately, recent research has discovered an effective side channel attack against any disk mounted by a running machine\cite{princetonattack}. This attack, known as the cold boot attack, is effective against any mounted volume using state-of-the-art disk encryption, is relatively simple to perform for an attacker with even rudimentary technical knowledge and training, and is applicable to exactly the scenario against which disk encryption is primarily supposed to defend: an adversary with physical access. To our knowledge, no effective software-based countermeasure to this attack supporting multiple encryption keys has yet been articulated in the literature. Moreover, since no proposed solution has been implemented in publicly available software, all general-purpose machines using disk encryption remain vulnerable. We present Loop-Amnesia, a kernel-based disk encryption mechanism implementing a novel technique to eliminate vulnerability to the cold boot attack. We offer theoretical justification of Loop-Amnesia's invulnerability to the attack, verify that our implementation is not vulnerable in practice, and present measurements showing our impact on I/O accesses to the encrypted disk is limited to a slowdown of approximately 2x. Loop-Amnesia is written for x86-64, but our technique is applicable to other register-based architectures. We base our work on loop-AES, a state-of-the-art open source disk encryption package for Linux.
Serial Concatenation of RS Codes with Kite Codes: Performance Analysis, Iterative Decoding and Design
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose a new ensemble of rateless forward error correction (FEC) codes. The proposed codes are serially concatenated codes with Reed-Solomon (RS) codes as outer codes and Kite codes as inner codes. The inner Kite codes are a special class of prefix rateless low-density parity-check (PRLDPC) codes, which can generate potentially infinite (or as many as required) random-like parity-check bits. The employment of RS codes as outer codes not only lowers down error-floors but also ensures (with high probability) the correctness of successfully decoded codewords. In addition to the conventional two-stage decoding, iterative decoding between the inner code and the outer code are also implemented to improve the performance further. The performance of the Kite codes under maximum likelihood (ML) decoding is analyzed by applying a refined Divsalar bound to the ensemble weight enumerating functions (WEF). We propose a simulation-based optimization method as well as density evolution (DE) using Gaussian approximations (GA) to design the Kite codes. Numerical results along with semi-analytic bounds show that the proposed codes can approach Shannon limits with extremely low error-floors. It is also shown by simulation that the proposed codes performs well within a wide range of signal-to-noise-ratios (SNRs).
On the Complexity of Solving a Bivariate Polynomial System
Venue: arXiv cs.SC 2011
Year: 2011

We study the complexity of computing the real solutions of a bivariate polynomial system using the recently proposed algorithm BISOLVE. BISOLVE is a classical elimination method which first projects the solutions of a system onto the $x$- and $y$-axes and, then, selects the actual solutions from the so induced candidate set. However, unlike similar algorithms, BISOLVE requires no genericity assumption on the input nor it needs any change of the coordinate system. Furthermore, extensive benchmarks from \cite{bes-bisolve-2011} confirm that the algorithm outperforms state of the art approaches by a large factor. In this work, we show that, for two polynomials $f,g\in\mathbb{Z}[x,y]$ of total degree at most $n$ with integer coefficients bounded by $2^τ$, BISOLVE computes isolating boxes for all real solutions of the system $f=g=0$ using $\Otilde(n^8τ^{2})$ bit operations, thereby improving the previous record bound by a factor of at least $n^{2}$.
Attacking and Defending Covert Channels and Behavioral Models
Venue: arXiv cs.LG 2011
Year: 2011

In this paper we present methods for attacking and defending $k$-gram statistical analysis techniques that are used, for example, in network traffic analysis and covert channel detection. The main new result is our demonstration of how to use a behavior's or process' $k$-order statistics to build a stochastic process that has those same $k$-order stationary statistics but possesses different, deliberately designed, $(k+1)$-order statistics if desired. Such a model realizes a "complexification" of the process or behavior which a defender can use to monitor whether an attacker is shaping the behavior. By deliberately introducing designed $(k+1)$-order behaviors, the defender can check to see if those behaviors are present in the data. We also develop constructs for source codes that respect the $k$-order statistics of a process while encoding covert information. One fundamental consequence of these results is that certain types of behavior analyses techniques come down to an {\em arms race} in the sense that the advantage goes to the party that has more computing resources applied to the problem.
Tight Bounds for Black Hole Search with Scattered Agents in Synchronous Rings
Venue: arXiv cs.MA 2011
Year: 2011

We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying destroys all mobile agents visiting that node without leaving any trace. We consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.
Pushing the limits for medical image reconstruction on recent standard multicore processors
Venue: arXiv cs.PF 2011
Year: 2011

Volume reconstruction by backprojection is the computational bottleneck in many interventional clinical computed tomography (CT) applications. Today vendors in this field replace special purpose hardware accelerators by standard hardware like multicore chips and GPGPUs. Medical imaging algorithms are on the verge of employing High Performance Computing (HPC) technology, and are therefore an interesting new candidate for optimization. This paper presents low-level optimizations for the backprojection algorithm, guided by a thorough performance analysis on four generations of Intel multicore processors (Harpertown, Westmere, Westmere EX, and Sandy Bridge). We choose the RabbitCT benchmark, a standardized testcase well supported in industry, to ensure transparent and comparable results. Our aim is to provide not only the fastest possible implementation but also compare to performance models and hardware counter data in order to fully understand the results. We separate the influence of algorithmic optimizations, parallelization, SIMD vectorization, and microarchitectural issues and pinpoint problems with current SIMD instruction set extensions on standard CPUs (SSE, AVX). The use of assembly language is mandatory for best performance. Finally we compare our results to the best GPGPU implementations available for this open competition benchmark.
Distributed Cooperative Spectrum Sensing in Mobile Ad Hoc Networks with Cognitive Radios
Venue: arXiv cs.IT 2011
Year: 2011

In cognitive radio mobile ad hoc networks (CR-MANETs), secondary users can cooperatively sense the spectrum to detect the presence of primary users. In this chapter, we propose a fully distributed and scalable cooperative spectrum sensing scheme based on recent advances in consensus algorithms. In the proposed scheme, the secondary users can maintain coordination based on only local information exchange without a centralized common receiver. We use the consensus of secondary users to make the final decision. The proposed scheme is essentially based on recent advances in consensus algorithms that have taken inspiration from complex natural phenomena including flocking of birds, schooling of fish, swarming of ants and honeybees. Unlike the existing cooperative spectrum sensing schemes, there is no need for a centralized receiver in the proposed schemes, which make them suitable in distributed CR-MANETs. Simulation results show that the proposed consensus schemes can have significant lower missing detection probabilities and false alarm probabilities in CR-MANETs. It is also demonstrated that the proposed scheme not only has proven sensitivity in detecting the primary user's presence, but also has robustness in choosing a desirable decision threshold.
Resource Allocation for Selection-Based Cooperative OFDM Networks
Venue: arXiv cs.IT 2011
Year: 2011

This paper considers resource allocation to achieve max-min fairness in a selection-based orthogonal frequency division multiplexing network wherein source nodes are assisted by fixed decode-and-forward relays. The joint problem of transmission strategy selection, relay assignment, and power allocation is a combinatorial problem with exponential complexity. To develop effective solutions to these questions, we approach these problems in two stages. The first set of problems assume ideal source-relay channels; this simplification helps illustrate our general methodology and also why our solutions provide tight bounds. We then formulate the general problem of transmission strategy selection, relay assignment, and power allocation at the sources and relays considering all communication channels, i.e., finite power source-relay channels. In both sets of problems mentioned so far, transmissions over subcarriers are assumed to be independent. However, given the attendant problems of synchronization and the implementation using a FFT/IFFT pair, resource allocation at the subcarrier level appears impractical. We, therefore, consider resource allocation at the level of an entire OFDM block. While optimal resource management requires an exhaustive search, we develop tight bounds with lower complexity. Finally, we propose a decentralized block-based relaying scheme. Simulation results using the COST-231 channel model show that this scheme yields close-to-optimal performance while offering many computational benefits.
Optimized Spline Interpolation
Venue: arXiv cs.MM 2011
Year: 2011

In this paper, we investigate the problem of designing compact support interpolation kernels for a given class of signals. By using calculus of variations, we simplify the optimization problem from an infinite nonlinear problem to a finite dimensional linear case, and then find the optimum compact support function that best approximates a given filter in the least square sense (l2 norm). The benefit of compact support interpolants is the low computational complexity in the interpolation process while the optimum compact support interpolant gaurantees the highest achivable Signal to Noise Ratio (SNR). Our simulation results confirm the superior performance of the proposed splines compared to other conventional compact support interpolants such as cubic spline.
Full Duplex Wireless Communications for Cognitive Radio Networks
Venue: arXiv cs.IT 2011
Year: 2011

As a key in cognitive radio networks (CRNs), dynamic spectrum access needs to be carefully designed to minimize the interference and delay to the \emph{primary} (licensed) users. One of the main challenges in dynamic spectrum access is to determine when the \emph{secondary} (unlicensed) users can use the spectrum. In particular, when the secondary user is using the spectrum, if the primary user becomes active to use the spectrum, it is usually hard for the secondary user to detect the primary user instantaneously, thus causing unexpected interference and delay to primary users. The secondary user cannot detect the presence of primary users instantaneously because the secondary user is unable to detect the spectrum at the same time while it is transmitting. To solve this problem, we propose the full duplex wireless communications scheme for CRNs. In particular, we employ the Antennas Cancellation (AC), the RF Interference Cancellation (RIC), and the Digital Interference Cancellation (DIC) techniques for secondary users so that the secondary user can scan for active primary users while it is transmitting. Once detecting the presence of primary users, the secondary user will release the spectrum instantaneously to avoid the interference and delay to primary users. We analyze the packet loss rate of primary users in wireless full duplex CRNs, and compare them with the packet loss rate of primary users in wireless half duplex CRNs. Our analyses and simulations show that using our developped wireless full duplex CRNs, the packet loss rate of primary users can be significantly decreased as compared with that of primary users by using the half duplex CRNs.
Base-Station Selections for QoS Provisioning Over Distributed Multi-User MIMO Links in Wireless Networks
Venue: arXiv cs.IT 2011
Year: 2011

We propose the QoS-aware BS-selection and the corresponding resource-allocation schemes for downlink multi-user transmissions over the distributed multiple-input-multiple-output (MIMO) links, where multiple location-independent base-stations (BS), controlled by a central server, cooperatively transmit data to multiple mobile users. Our proposed schemes aim at minimizing the BS usages and reducing the interfering range of the distributed MIMO transmissions, while satisfying diverse statistical delay-QoS requirements for all users, which are characterized by the delay-bound violation probability and the effective capacity technique. Specifically, we propose two BS-usage minimization frameworks to develop the QoS-aware BS-selection schemes and the corresponding wireless resource-allocation algorithms across multiple mobile users. The first framework applies the joint block-diagonalization (BD) and probabilistic transmission (PT) to implement multiple access over multiple mobile users, while the second one employs time-division multiple access (TDMA) approach to control multiple users' links. We then derive the optimal BS-selection schemes for these two frameworks, respectively. In addition, we further discuss the PT-only based BS-selection scheme. Also conducted is a set of simulation evaluations to comparatively study the average BS-usage and interfering range of our proposed schemes and to analyze the impact of QoS constraints on the BS selections for distributed MIMO transmissions.
Requirements of Vertical Handoff Mechanism in 4G Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

The importance of wireless communication is increasing day by day throughout the world due to cellular and broadband technologies. Everyone around the world would like to be connected seamlessly anytime anywhere through the best network. The 4G wireless system must have the capability to provide high data transfer rates, quality of services and seamless mobility. In 4G, there are a large variety of heterogeneous networks. The users for variety of applications would like to utilize heterogeneous networks on the basis of their preferences such as real time, high availability and high bandwidth. When connections have to switch between heterogeneous networks for performance and high availability reasons, seamless vertical handoff is necessary. The requirements like capability of the network, handoff latency, network cost, network conditions, power consumption and user's preferences must be taken into consideration during vertical handoff. In this paper, we have extracted the requirements of a vertical handoff from the literature surveyed. The evaluation of the existing work is also being done on the basis of required parameters for vertical handoff. A sophisticated, adaptive and intelligent approach is required to implement the vertical handoff mechanism in 4G wireless networks to produce an effective service for the user by considering dynamic and non dynamic parameters.
Computational Aspects of Asynchronous CA
Venue: arXiv cs.FL 2011
Year: 2011

This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are "universal", i.e., allowing a (specific family of) ACA to simulate any TM on any input. We also consider the computational cost of such simulations.
Statistical Delay Control and QoS-Driven Power Allocation Over Two-Hop Wireless Relay Links
Venue: arXiv cs.IT 2011
Year: 2011

The time-varying feature of wireless channels usually makes the hard delay bound for data transmissions unrealistic to guarantee. In contrast, the statistically-bounded delay with a small violation probability has been widely used for delay quality-of-service (QoS) characterization and evaluation. While existing research mainly focused on the statistical-delay control in single-hop links, in this paper we propose the QoS-driven power-allocation scheme over two-hop wireless relay links to statistically upper-bound the end-to-end delay under the decodeand- forward (DF) relay transmissions. Specifically, by applying the effective capacity and effective bandwidth theories, we first analyze the delay-bound violation probability over two tops each with independent service processes. Then, we show that an efficient approach for statistical-delay guarantees is to make the delay distributions of both hops identical, which, however, needs to be obtained through asymmetric resource allocations over the two hops. Motivated by this fact, we formulate and solve an optimization problem aiming at minimizing the average power consumptions to satisfy the specified end-to-end delay-bound violation probability over two-hop relay links. Also conducted is a set of simulations results to show the impact of the QoS requirements, traffic load, and position of the relay node on the power allocation under our proposed optimal scheme.