OpenRaiser/Intern-Atlas huggingface dataset:
Cross Site Request Forgery on Android WebView
Venue: arXiv cs.CR 2014
Year: 2014

Android has always been about connectivity and providing great browsing experience. Web-based content can be embedded into the Android application using WebView. It is a User Interface component that displays webpages. It can either display a remote webpage or can also load static HTML data. This encompasses the functionality of a browser that can be integrated to application. WebView provides a number of APIs which enables the applications to interact with the web content inside WebView. In the current paper Cross site request forgery or XSRF attack specific to android WebView is investigated. In XSRF attack the trusts of a web application in its authenticated users is exploited by letting the attacker make arbitrary HTTP requests on behalf of a victim user. When the user is logged into the trusted site through the WebView the site authenticates the WebView and not application. The application can launch attacks on the behalf of user with the APIs of Webview exploiting user credentials resulting in Cross site request forgery. Attacks can also be launched by setting cookies as HTTP headers and making malicious HTTP Request on behalf of victim.
Part Detector Discovery in Deep Convolutional Neural Networks
Venue: arXiv cs.CV 2014
Year: 2014

Current fine-grained classification approaches often rely on a robust localization of object parts to extract localized feature representations suitable for discrimination. However, part localization is a challenging task due to the large variation of appearance and pose. In this paper, we show how pre-trained convolutional neural networks can be used for robust and efficient object part discovery and localization without the necessity to actually train the network on the current dataset. Our approach called "part detector discovery" (PDD) is based on analyzing the gradient maps of the network outputs and finding activation centers spatially related to annotated semantic parts or bounding boxes. This allows us not just to obtain excellent performance on the CUB200-2011 dataset, but in contrast to previous approaches also to perform detection and bird classification jointly without requiring a given bounding box annotation during testing and ground-truth parts during training. The code is available at http://www.inf-cv.uni-jena.de/part_discovery and https://github.com/cvjena/PartDetectorDisovery.
Deciding what to display: maximizing the information value of social media
Venue: arXiv cs.CY 2014
Year: 2014

In information-rich environments, the competition for users' attention leads to a flood of content from which people often find hard to sort out the most relevant and useful pieces. Using Twitter as a case study, we applied an attention economy solution to generate the most informative tweets for its users. By considering the novelty and popularity of tweets as objective measures of their relevance and utility, we used the Huberman-Wu algorithm to automatically select the ones that will receive the most attention in the next time interval. Their predicted popularity was confirmed by using Twitter data collected for a period of 2 months.
Statistically Significant Detection of Linguistic Change
Venue: arXiv cs.CL 2014
Year: 2014

We propose a new computational approach for tracking and detecting statistically significant linguistic shifts in the meaning and usage of words. Such linguistic shifts are especially prevalent on the Internet, where the rapid exchange of ideas can quickly change a word's meaning. Our meta-analysis approach constructs property time series of word usage, and then uses statistically sound change point detection algorithms to identify significant linguistic shifts. We consider and analyze three approaches of increasing complexity to generate such linguistic property time series, the culmination of which uses distributional characteristics inferred from word co-occurrences. Using recently proposed deep neural language models, we first train vector representations of words for each time period. Second, we warp the vector spaces into one unified coordinate system. Finally, we construct a distance-based distributional time series for each word to track it's linguistic displacement over time. We demonstrate that our approach is scalable by tracking linguistic change across years of micro-blogging using Twitter, a decade of product reviews using a corpus of movie reviews from Amazon, and a century of written books using the Google Book-ngrams. Our analysis reveals interesting patterns of language usage change commensurate with each medium.
A Comparative Study of Techniques of Distant Reconstruction of Displacement Fields by using DISTRESS Simulator
Venue: arXiv cs.CV 2014
Year: 2014

Reconstruction and monitoring of displacement and strain fields is an important problem in engineering. We analyze the remote and non-obtrusive methods of strain measurement based on photogrammetry and Digital Image Correlation (DIC). The method is based on covering the photographed surface with a pattern of speckles and comparing the images taken before and after the deformation. In this study, a comprehensive literature review and comparative analysis of photogrammetric solutions is presented. The analysis is based on a specially developed Digital Image Synthesizer To Reconstruct Strain in Solids (DISTRESS) Simulator to generate synthetic images of displacement and stress fields in order to investigate the intrinsic accuracy of the existing variants of DIC. We investigated the Basic DIC and a commercial software VIC 2D, both based on displacement field reconstruction with post processing strain determination based on numerical differentiation. We also investigated what we call the Extended DIC where the strain field is determined independently of the displacement field. While the Basic DIC and VIC 2D are faster, the Extended DIC delivers the best accuracy of strain reconstruction. The speckle pattern is found to be playing a critical role in achieving high accuracy for DIC. Increase in subset size for DIC does not significantly improves the accuracy, while the smallest subset size depends on the speckle pattern and speckle size. Increase in the overall image size provides more details but does not play significant role in improving the accuracy, while significantly increasing the computation cost.
Window-Based Descriptors for Arabic Handwritten Alphabet Recognition: A Comparative Study on a Novel Dataset
Venue: arXiv cs.CV 2014
Year: 2014

This paper presents a comparative study for window-based descriptors on the application of Arabic handwritten alphabet recognition. We show a detailed experimental evaluation of different descriptors with several classifiers. The objective of the paper is to evaluate different window-based descriptors on the problem of Arabic letter recognition. Our experiments clearly show that they perform very well. Moreover, we introduce a novel spatial pyramid partitioning scheme that enhances the recognition accuracy for most descriptors. In addition, we introduce a novel dataset for Arabic handwritten isolated alphabet letters, which can serve as a benchmark for future research.
Network installation and recovery: approximation lower bounds and faster exact formulations
Venue: arXiv cs.DM 2014
Year: 2014

We study the Neighbor Aided Network Installation Problem (NANIP) introduced previously which asks for a minimal cost ordering of the vertices of a graph, where the cost of visiting a node is a function of the number of neighbors that have already been visited. This problem has applications in resource management and disaster recovery. In this paper we analyze the computational hardness of NANIP. In particular we show that this problem is NP-hard even when restricted to convex decreasing cost functions, give a linear approximation lower bound for the greedy algorithm, and prove a general sub-constant approximation lower bound. Then we give a new integer programming formulation of NANIP and empirically observe its speedup over the original integer program.
Jamming Bandits
Venue: arXiv cs.IT 2014
Year: 2014

Can an intelligent jammer learn and adapt to unknown environments in an electronic warfare-type scenario? In this paper, we answer this question in the positive, by developing a cognitive jammer that adaptively and optimally disrupts the communication between a victim transmitter-receiver pair. We formalize the problem using a novel multi-armed bandit framework where the jammer can choose various physical layer parameters such as the signaling scheme, power level and the on-off/pulsing duration in an attempt to obtain power efficient jamming strategies. We first present novel online learning algorithms to maximize the jamming efficacy against static transmitter-receiver pairs and prove that our learning algorithm converges to the optimal (in terms of the error rate inflicted at the victim and the energy used) jamming strategy. Even more importantly, we prove that the rate of convergence to the optimal jamming strategy is sub-linear, i.e. the learning is fast in comparison to existing reinforcement learning algorithms, which is particularly important in dynamically changing wireless environments. Also, we characterize the performance of the proposed bandit-based learning algorithm against multiple static and adaptive transmitter-receiver pairs.
The Implementation of a Real-Time Polyphase Filter
Venue: arXiv cs.DC 2014
Year: 2014

In this article we study the suitability of dierent computational accelerators for the task of real-time data processing. The algorithm used for comparison is the polyphase filter, a standard tool in signal processing and a well established algorithm. We measure performance in FLOPs and execution time, which is a critical factor for real-time systems. For our real-time studies we have chosen a data rate of 6.5GB/s, which is the estimated data rate for a single channel on the SKAs Low Frequency Aperture Array. Our findings how that GPUs are the most likely candidate for real-time data processing. GPUs are better in both performance and power consumption.
Power Allocation in the Energy Harvesting Full-Duplex Gaussian Relay Channels
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we propose a general model to study the full-duplex non-coherent decode-and-forward Gaussian relay channel with energy harvesting (EH) nodes, called NC-EH-$\mathcal{RC}$, in three cases: $i)$ no energy transfer (ET), $ii)$ one-way ET from the source (S) to the relay (R), and $iii)$ two-way ET. We consider the problem of optimal power allocation in NC-EH-$\mathcal{RC}$ in order to maximize the total transmitted bits from S to the destination in a given time duration. General stochastic energy arrivals at S and R with known EH times and values are assumed. In NC-EH-$\mathcal{RC}$ with no ET, the complicated min-max optimization form along with its constraints make the problem intractable. It is shown that this problem can be transformed to a solvable convex form; however, convex optimization solution does not provide the structural properties of the optimal solution. Therefore, following an alternative perspective, we investigate conditions on harvesting process of S and R where we find optimal algorithmic solution. Further, we propose some suboptimal algorithms and provide some examples, in which the algorithms are optimal. Moreover, we find a class of problems for NC-EH-$\mathcal{RC}$ with one-way ET from S to R, where the optimal algorithmic solution is devised. For NC-EH-$\mathcal{RC}$ with two-way ET, we propose \emph{general} optimal algorithmic solution. Furthermore, the performance of the proposed algorithms are evaluated numerically and compared with optimal numerical convex optimization tools.
Monotonic Abstraction Techniques: from Parametric to Software Model Checking
Venue: arXiv cs.LO 2014
Year: 2014

Monotonic abstraction is a technique introduced in model checking parameterized distributed systems in order to cope with transitions containing global conditions within guards. The technique has been re-interpreted in a declarative setting in previous papers of ours and applied to the verification of fault tolerant systems under the so-called "stopping failures" model. The declarative reinterpretation consists in logical techniques (quantifier relativizations and, especially, quantifier instantiations) making sense in a broader context. In fact, we recently showed that such techniques can over-approximate array accelerations, so that they can be employed as a meaningful (and practically effective) component of CEGAR loops in software model checking too.
A Language Support for Exhaustive Fault-Injection in Message-Passing System Models
Venue: arXiv cs.SE 2014
Year: 2014

This paper presents an approach towards specifying and verifying adaptive distributed systems. We here take fault-handling as an example of adaptive behavior and propose a modeling language Sandal for describing fault-prone message-passing systems. One of the unique mechanisms of the language is a linguistic support for abstracting typical faults such as unexpected termination of processes and random loss of messages. The Sandal compiler translates a model into a set of NuSMV modules. During the compilation process, faults specified in the model will be woven into the output. One can thus enjoy full-automatic exhaustive fault-injection without writing faulty behaviors explicitly. We demonstrate the advantage of the language by verifying a model of the two-phase commit protocol under faulty environment.
Fundamental Limits of Blind Deconvolution Part I: Ambiguity Kernel
Venue: arXiv cs.IT 2014
Year: 2014

Blind deconvolution is an ubiquitous non-linear inverse problem in applications like wireless communications and image processing. This problem is generally ill-posed, and there have been efforts to use sparse models for regularizing blind deconvolution to promote signal identifiability. Part I of this two-part paper characterizes the ambiguity space of blind deconvolution and shows unidentifiability of this inverse problem for almost every pair of unconstrained input signals. The approach involves lifting the deconvolution problem to a rank one matrix recovery problem and analyzing the rank two null space of the resultant linear operator. A measure theoretically tight (parametric and recursive) representation of the key rank two null space is stated and proved. This representation is a novel foundational result for signal and code design strategies promoting identifiability under convolutive observation models. Part II of this paper analyzes the identifiability of sparsity constrained blind deconvolution and establishes surprisingly strong negative results on scaling laws for the sparsity-ambiguity trade-off.
Analog Signal Processing Solution for Image Alignment
Venue: arXiv cs.AR 2014
Year: 2014

Imaging and Image sensors is a field that is continuously evolving. There are new products coming into the market every day. Some of these have very severe Size, Weight and Power constraints whereas other devices have to handle very high computational loads. Some require both these conditions to be met simultaneously. Current imaging architectures and digital image processing solutions will not be able to meet these ever increasing demands. There is a need to develop novel imaging architectures and image processing solutions to address these requirements. In this work we propose analog signal processing as a solution to this problem. The analog processor is not suggested as a replacement to a digital processor but it will be used as an augmentation device which works in parallel with the digital processor, making the system faster and more efficient. In order to show the merits of analog processing the highly computational Normalized Cross Correlation algorithm is implemented. We propose two novel modifications to the algorithm and a new imaging architecture which, significantly reduces the computation time.
Sub-computable Boundedness Randomness
Venue: arXiv cs.LO 2014
Year: 2014

This paper defines a new notion of bounded computable randomness for certain classes of sub-computable functions which lack a universal machine. In particular, we define such versions of randomness for primitive recursive functions and for PSPACE functions. These new notions are robust in that there are equivalent formulations in terms of (1) Martin-Löf tests, (2) Kolmogorov complexity, and (3) martingales. We show these notions can be equivalently defined with prefix-free Kolmogorov complexity. We prove that one direction of van Lambalgen's theorem holds for relative computability, but the other direction fails. We discuss statistical properties of these notions of randomness.
Isn't Hybrid ARQ Sufficient?
Venue: arXiv cs.IT 2014
Year: 2014

In practical systems, reliable communication is often accomplished by coding at different network layers. We question the necessity of this approach and examine when it can be beneficial. Through conceptually simple probabilistic models (based on coin tossing), we argue that multicast scenarios and protocol restrictions may make concatenated multi-layer coding preferable to physical layer coding alone, which is mostly not the case in point-to-point communications.
GASP : Geometric Association with Surface Patches
Venue: arXiv cs.CV 2014
Year: 2014

A fundamental challenge to sensory processing tasks in perception and robotics is the problem of obtaining data associations across views. We present a robust solution for ascertaining potentially dense surface patch (superpixel) associations, requiring just range information. Our approach involves decomposition of a view into regularized surface patches. We represent them as sequences expressing geometry invariantly over their superpixel neighborhoods, as uniquely consistent partial orderings. We match these representations through an optimal sequence comparison metric based on the Damerau-Levenshtein distance - enabling robust association with quadratic complexity (in contrast to hitherto employed joint matching formulations which are NP-complete). The approach is able to perform under wide baselines, heavy rotations, partial overlaps, significant occlusions and sensor noise. The technique does not require any priors -- motion or otherwise, and does not make restrictive assumptions on scene structure and sensor movement. It does not require appearance -- is hence more widely applicable than appearance reliant methods, and invulnerable to related ambiguities such as textureless or aliased content. We present promising qualitative and quantitative results under diverse settings, along with comparatives with popular approaches based on range as well as RGB-D data.
Interference Reduction in Multi-Cell Massive MIMO Systems II: Downlink Analysis for a Finite Number of Antennas
Venue: arXiv cs.IT 2014
Year: 2014

Sharing global channel information at base stations (BSs) is commonly assumed for downlink multi-cell precoding. In the context of massive multi-input multi-output (MIMO) systems where each BS is equipped with a large number of antennas, sharing instant fading channel coefficients consumes a large amount of resource. To consider practically implementable methods, we study in this paper interference reduction based on precoding using the large-scale fading coefficients that depend on the path-loss model and are independent of a specific antenna. We focus on the downlink multi-cell precoding designs when each BS is equipped with a practically finite number of antennas. In this operation regime, pilot contamination is not the dominant source of interference, and mitigation of all types of interference is required. This paper uses an optimization approach to design precoding methods for equal qualities of service (QoS) to all users in the network, i.e.,maximizing the minimum signal-to-interference-plus-noise ratios (SINRs) among all users. The formulated optimization is proved to be quasi-convex, and can be solved optimally. We also propose low-complexity suboptimal algorithms through uplink and downlink duality. Simulation results show that the proposed precoding methods improve 5% outage rate for more than 1000 times, compared to other known interference mitigation techniques.
Hitting forbidden subgraphs in graphs of bounded treewidth
Venue: arXiv cs.DS 2014
Year: 2014

We study the complexity of a generic hitting problem H-Subgraph Hitting, where given a fixed pattern graph $H$ and an input graph $G$, the task is to find a set $X \subseteq V(G)$ of minimum size that hits all subgraphs of $G$ isomorphic to $H$. In the colorful variant of the problem, each vertex of $G$ is precolored with some color from $V(H)$ and we require to hit only $H$-subgraphs with matching colors. Standard techniques shows that for every fixed $H$, the problem is fixed-parameter tractable parameterized by the treewidth of $G$; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of $G$ is tightly governed by $μ(H)$, the maximum size of a minimal vertex separator in $H$. That is, we show for every fixed $H$ that, on a graph of treewidth $t$, the colorful problem can be solved in time $2^{\mathcal{O}(t^{μ(H)})}\cdot|V(G)|$, but cannot be solved in time $2^{o(t^{μ(H)})}\cdot |V(G)|^{O(1)}$, assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H-Subgraph Hitting is much richer.
Introduction to ROSS: A New Representational Scheme
Venue: arXiv cs.AI 2014
Year: 2014

ROSS ("Representation, Ontology, Structure, Star") is introduced as a new method for knowledge representation that emphasizes representational constructs for physical structure. The ROSS representational scheme includes a language called "Star" for the specification of ontology classes. The ROSS method also includes a formal scheme called the "instance model". Instance models are used in the area of natural language meaning representation to represent situations. This paper provides both the rationale and the philosophical background for the ROSS method.
GreMuTRRR: A Novel Genetic Algorithm to Solve Distance Geometry Problem for Protein Structures
Venue: arXiv cs.NE 2014
Year: 2014

Nuclear Magnetic Resonance (NMR) Spectroscopy is a widely used technique to predict the native structure of proteins. However, NMR machines are only able to report approximate and partial distances between pair of atoms. To build the protein structure one has to solve the Euclidean distance geometry problem given the incomplete interval distance data produced by NMR machines. In this paper, we propose a new genetic algorithm for solving the Euclidean distance geometry problem for protein structure prediction given sparse NMR data. Our genetic algorithm uses a greedy mutation operator to intensify the search, a twin removal technique for diversification in the population and a random restart method to recover stagnation. On a standard set of benchmark dataset, our algorithm significantly outperforms standard genetic algorithms.