OpenRaiser/Intern-Atlas huggingface dataset:
Given Enough Eyeballs, All Bugs Are Shallow? Revisiting Eric Raymond with Bug Bounty Programs
Venue: arXiv cs.CR 2017
Year: 2017

Bug bounty programs offer a modern platform for organizations to crowdsource their software security and for security researchers to be fairly rewarded for the vulnerabilities they find. Little is known however on the incentives set by bug bounty programs: How they drive new bug discoveries, and how they supposedly improve security through the progressive exhaustion of discoverable vulnerabilities. Here, we recognize that bug bounty programs create tensions, for organizations running them on the one hand, and for security researchers on the other hand. At the level of one bug bounty program, security researchers face a sort of St-Petersburg paradox: The probability of finding additional bugs decays fast, and thus can hardly be matched with a sufficient increase of monetary rewards. Furthermore, bug bounty program managers have an incentive to gather the largest possible crowd to ensure a larger pool of expertise, which in turn increases competition among security researchers. As a result, we find that researchers have high incentives to switch to newly launched programs, for which a reserve of low-hanging fruit vulnerabilities is still available. Our results inform on the technical and economic mechanisms underlying the dynamics of bug bounty program contributions, and may in turn help improve the mechanism design of bug bounty programs that get increasingly adopted by cybersecurity savvy organizations.
Caching Policy Toward Maximal Success Probability and Area Spectral Efficiency of Cache-enabled HetNets
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we investigate the optimal caching policy respectively maximizing the success probability and area spectral efficiency (ASE) in a cache-enabled heterogeneous network (HetNet) where a tier of multi-antenna macro base stations (MBSs) is overlaid with a tier of helpers with caches. Under the probabilistic caching framework, we resort to stochastic geometry theory to derive the success probability and ASE. After finding the optimal caching policies, we analyze the impact of critical system parameters and compare the ASE with traditional HetNet where the MBS tier is overlaid by a tier of pico BSs (PBSs) with limited-capacity backhaul. Analytical and numerical results show that the optimal caching probability is less skewed among helpers to maximize the success probability when the ratios of MBS-to-helper density, MBS-to-helper transmit power, user-to-helper density, or the rate requirement are small, but is more skewed to maximize the ASE in general. Compared with traditional HetNet, the helper density is much lower than the PBS density to achieve the same target ASE. The helper density can be reduced by increasing cache size. With given total cache size within an area, there exists an optimal helper node density that maximizes the ASE.
Generative Knowledge Transfer for Neural Language Models
Venue: arXiv cs.LG 2017
Year: 2017

In this paper, we propose a generative knowledge transfer technique that trains an RNN based language model (student network) using text and output probabilities generated from a previously trained RNN (teacher network). The text generation can be conducted by either the teacher or the student network. We can also improve the performance by taking the ensemble of soft labels obtained from multiple teacher networks. This method can be used for privacy conscious language model adaptation because no user data is directly used for training. Especially, when the soft labels of multiple devices are aggregated via a trusted third party, we can expect very strong privacy protection.
Parallel Non-divergent Flow Accumulation For Trillion Cell Digital Elevation Models On Desktops Or Clusters
Venue: arXiv cs.DC 2017
Year: 2017

Continent-scale datasets challenge hydrological algorithms for processing digital elevation models. Flow accumulation is an important input for many such algorithms; here, I parallelize its calculation. The new algorithm works on one or many cores, or multiple machines, and can take advantage of large memories or cope with small ones. Unlike previous parallel algorithms, the new algorithm guarantees a fixed number of memory access and communication events per raster cell. In testing, the new algorithm ran faster and used fewer resources than previous algorithms, exhibiting ~30% strong and weak scaling efficiencies up to 48 cores and linear scaling across datasets ranging over three orders of magnitude. The largest dataset tested had two trillion (2*10^12) cells. With 48 cores, processing required 24 minutes wall-time (14.5 compute-hours). This test is three orders of magnitude larger than any previously performed in the literature. Complete, well-commented source code and correctness tests are available on Github.
On the Asymptotic Equivalence of Circulant and Toeplitz Matrices
Venue: arXiv cs.IT 2017
Year: 2017

Any sequence of uniformly bounded $N\times N$ Hermitian Toeplitz matrices $\{\boldsymbol{H}_N\}$ is asymptotically equivalent to a certain sequence of $N\times N$ circulant matrices $\{\boldsymbol{C}_N\}$ derived from the Toeplitz matrices in the sense that $\left\| \boldsymbol{H}_N - \boldsymbol{C}_N \right\|_F = o(\sqrt{N})$ as $N\rightarrow \infty$. This implies that certain collective behaviors of the eigenvalues of each Toeplitz matrix are reflected in those of the corresponding circulant matrix and supports the utilization of the computationally efficient fast Fourier transform (instead of the Karhunen-Loève transform) in applications like coding and filtering. In this paper, we study the asymptotic performance of the individual eigenvalue estimates. We show that the asymptotic equivalence of the circulant and Toeplitz matrices implies the individual asymptotic convergence of the eigenvalues for certain types of Toeplitz matrices. We also show that these estimates asymptotically approximate the largest and smallest eigenvalues for more general classes of Toeplitz matrices.
$μ$Puppet: A Declarative Subset of the Puppet Configuration Language
Venue: arXiv cs.PL 2017
Year: 2017

Puppet is a popular declarative framework for specifying and managing complex system configurations. The Puppet framework includes a domain-specific language with several advanced features inspired by object-oriented programming, including user-defined resource types, 'classes' with a form of inheritance, and dependency management. Like most real-world languages, the language has evolved in an ad hoc fashion, resulting in a design with numerous features, some of which are complex, hard to understand, and difficult to use correctly. We present an operational semantics for $μ$Puppet, a representative subset of the Puppet language that covers the distinctive features of Puppet, while excluding features that are either deprecated or work-in-progress. Formalising the semantics sheds light on difficult parts of the language, identifies opportunities for future improvements, and provides a foundation for future analysis or debugging techniques, such as static typechecking or provenance tracking. Our semantics leads straightforwardly to a reference implementation in Haskell. We also discuss some of Puppet's idiosyncrasies, particularly its handling of classes and scope, and present an initial corpus of test cases supported by our formal semantics.
In-Place Sparse Suffix Sorting
Venue: arXiv cs.DS 2017
Year: 2017

Suffix arrays encode the lexicographical order of all suffixes of a text and are often combined with the Longest Common Prefix array (LCP) to simulate navigational queries on the suffix tree in reduced space. In space-critical applications such as sparse and compressed text indexing, only information regarding the lexicographical order of a size-$b$ subset of all $n$ text suffixes is often needed. Such information can be stored space-efficiently (in $b$ words) in the sparse suffix array (SSA). The SSA and its relative sparse LCP array (SLCP) can be used as a space-efficient substitute of the sparse suffix tree. Very recently, Gawrychowski and Kociumaka [SODA 2017] showed that the sparse suffix tree (and therefore SSA and SLCP) can be built in asymptotically optimal $O(b)$ space with a Monte Carlo algorithm running in $O(n)$ time. The main reason for using the SSA and SLCP arrays in place of the sparse suffix tree is, however, their reduced space of $b$ words each. This leads naturally to the quest for in-place algorithms building these arrays. Franceschini and Muthukrishnan [ICALP 2007] showed that the full suffix array can be built in-place and in optimal running time. On the other hand, finding sub-quadratic in-place algorithms for building the SSA and SLCP for \emph{general} subsets of suffixes has been an elusive task for decades. In this paper, we give the first solution to this problem. We provide the first in-place algorithm building the full LCP array in $O(n\log n)$ expected time and the first Monte Carlo in-place algorithms building the SSA and SLCP in $O(n + b\log^2 n)$ expected time. We moreover describe the first in-place solution for the suffix selection problem: to compute the $i$-th smallest text suffix.
Tree-decomposable and Underconstrained Geometric Constraint Problems
Venue: arXiv cs.GR 2017
Year: 2017

In this paper, we are concerned with geometric constraint solvers, i.e., with programs that find one or more solutions of a geometric constraint problem. If no solution exists, the solver is expected to announce that no solution has been found. Owing to the complexity, type or difficulty of a constraint problem, it is possible that the solver does not find a solution even though one may exist. Thus, there may be false negatives, but there should never be false positives. Intuitively, the ability to find solutions can be considered a measure of solver's competence. We consider static constraint problems and their solvers. We do not consider dynamic constraint solvers, also known as dynamic geometry programs, in which specific geometric elements are moved, interactively or along prescribed trajectories, while continually maintaining all stipulated constraints. However, if we have a solver for static constraint problems that is sufficiently fast and competent, we can build a dynamic geometry program from it by solving the static problem for a sufficiently dense sampling of the trajectory of the moving element(s). The work we survey has its roots in applications, especially in mechanical computer-aided design (MCAD). The constraint solvers used in MCAD took a quantum leap in the 1990s. These approaches solve a geometric constraint problem by an initial, graph-based structural analysis that extracts generic subproblems and determines how they would combine to form a complete solution. These subproblems are then handed to an algebraic solver that solves the specific instances of the generic subproblems and combines them.
Slicing Concurrent Constraint Programs
Venue: arXiv cs.LO 2017
Year: 2017

Concurrent Constraint Programming (CCP) is a declarative model for concurrency where agents interact by telling and asking constraints (pieces of information) in a shared store. Some previous works have developed (approximated) declarative debuggers for CCP languages. However, the task of debugging concurrent programs remains difficult. In this paper we define a dynamic slicer for CCP and we show it to be a useful companion tool for the existing debugging techniques. Our technique starts by considering a partial computation (a trace) that shows the presence of bugs. Often, the quantity of information in such a trace is overwhelming, and the user gets easily lost, since she cannot focus on the sources of the bugs. Our slicer allows for marking part of the state of the computation and assists the user to eliminate most of the redundant information in order to highlight the errors. We show that this technique can be tailored to timed variants of CCP. We also develop a prototypical implementation freely available for making experiments.
Accelerating Exact and Approximate Inference for (Distributed) Discrete Optimization with GPUs
Venue: arXiv cs.AI 2017
Year: 2017

Discrete optimization is a central problem in artificial intelligence. The optimization of the aggregated cost of a network of cost functions arises in a variety of problems including (W)CSP, DCOP, as well as optimization in stochastic variants such as the tasks of finding the most probable explanation (MPE) in belief networks. Inference-based algorithms are powerful techniques for solving discrete optimization problems, which can be used independently or in combination with other techniques. However, their applicability is often limited by their compute intensive nature and their space requirements. This paper proposes the design and implementation of a novel inference-based technique, which exploits modern massively parallel architectures, such as those found in Graphical Processing Units (GPUs), to speed up the resolution of exact and approximated inference-based algorithms for discrete optimization. The paper studies the proposed algorithm in both centralized and distributed optimization contexts. The paper demonstrates that the use of GPUs provides significant advantages in terms of runtime and scalability, achieving up to two orders of magnitude in speedups and showing a considerable reduction in execution time (up to 345 times faster) with respect to a sequential version.
We Can "See" You via Wi-Fi - WiFi Action Recognition via Vision-based Methods
Venue: arXiv cs.CV 2017
Year: 2017

Recently, Wi-Fi has caught tremendous attention for its ubiquity, and, motivated by Wi-Fi's low cost and privacy preservation, researchers have been putting lots of investigation into its potential on action recognition and even person identification. In this paper, we offer an comprehensive overview on these two topics in Wi-Fi. Also, through looking at these two topics from an unprecedented perspective, we could achieve generality instead of designing specific ad-hoc features for each scenario. Observing the great resemblance of Channel State Information (CSI, a fine-grained information captured from the received Wi-Fi signal) to texture, we proposed a brand-new framework based on computer vision methods. To minimize the effect of location dependency embedded in CSI, we propose a novel de-noising method based on Singular Value Decomposition (SVD) to eliminate the background energy and effectively extract the channel information of signals reflected by human bodies. From the experiments conducted, we demonstrate the feasibility and efficacy of the proposed methods. Also, we conclude factors that would affect the performance and highlight a few promising issues that require further deliberation.
Extending the OpenAI Gym for robotics: a toolkit for reinforcement learning using ROS and Gazebo
Venue: arXiv cs.RO 2017
Year: 2017

This paper presents an extension of the OpenAI Gym for robotics using the Robot Operating System (ROS) and the Gazebo simulator. The content discusses the software architecture proposed and the results obtained by using two Reinforcement Learning techniques: Q-Learning and Sarsa. Ultimately, the output of this work presents a benchmarking system for robotics that allows different techniques and algorithms to be compared using the same virtual conditions.
phi-LSTM: A Phrase-based Hierarchical LSTM Model for Image Captioning
Venue: arXiv cs.CL 2017
Year: 2017

A picture is worth a thousand words. Not until recently, however, we noticed some success stories in understanding of visual scenes: a model that is able to detect/name objects, describe their attributes, and recognize their relationships/interactions. In this paper, we propose a phrase-based hierarchical Long Short-Term Memory (phi-LSTM) model to generate image description. The proposed model encodes sentence as a sequence of combination of phrases and words, instead of a sequence of words alone as in those conventional solutions. The two levels of this model are dedicated to i) learn to generate image relevant noun phrases, and ii) produce appropriate image description from the phrases and other words in the corpus. Adopting a convolutional neural network to learn image features and the LSTM to learn the word sequence in a sentence, the proposed model has shown better or competitive results in comparison to the state-of-the-art models on Flickr8k and Flickr30k datasets.
Resolution of ranking hierarchies in directed networks
Venue: arXiv cs.SI 2017
Year: 2017

Identifying hierarchies and rankings of nodes in directed graphs is fundamental in many applications such as social network analysis, biology, economics, and finance. A recently proposed method identifies the hierarchy by finding the ordered partition of nodes which minimises a score function, termed agony. This function penalises the links violating the hierarchy in a way depending on the strength of the violation. To investigate the resolution of ranking hierarchies we introduce an ensemble of random graphs, the Ranked Stochastic Block Model. We find that agony may fail to identify hierarchies when the structure is not strong enough and the size of the classes is small with respect to the whole network. We analytically characterise the resolution threshold and we show that an iterated version of agony can partly overcome this resolution limit.
Automated Synthesis of Semantic Malware Signatures using Maximum Satisfiability
Venue: arXiv cs.CR 2017
Year: 2017

This paper proposes a technique for automatically learning semantic malware signatures for Android from very few samples of a malware family. The key idea underlying our technique is to look for a maximally suspicious common subgraph (MSCS) that is shared between all known instances of a malware family. An MSCS describes the shared functionality between multiple Android applications in terms of inter-component call relations and their semantic metadata (e.g., data-flow properties). Our approach identifies such maximally suspicious common subgraphs by reducing the problem to maximum satisfiability. Once a semantic signature is learned, our approach uses a combination of static analysis and a new approximate signature matching algorithm to determine whether an Android application matches the semantic signature characterizing a given malware family. We have implemented our approach in a tool called ASTROID and show that it has a number of advantages over state-of-the-art malware detection techniques. First, we compare the semantic malware signatures automatically synthesized by ASTROID with manually-written signatures used in previous work and show that the signatures learned by ASTROID perform better in terms of accuracy as well as precision. Second, we compare ASTROID against two state-of-the-art malware detection tools and demonstrate its advantages in terms of interpretability and accuracy. Finally, we demonstrate that ASTROID's approximate signature matching algorithm is resistant to behavioral obfuscation and that it can be used to detect zero-day malware. In particular, we were able to find 22 instances of zero-day malware in Google Play that are not reported as malware by existing tools.
Comparison among dimensionality reduction techniques based on Random Projection for cancer classification
Venue: arXiv cs.LG 2017
Year: 2017

Random Projection (RP) technique has been widely applied in many scenarios because it can reduce high-dimensional features into low-dimensional space within short time and meet the need of real-time analysis of massive data. There is an urgent need of dimensionality reduction with fast increase of big genomics data. However, the performance of RP is usually lower. We attempt to improve classification accuracy of RP through combining other reduction dimension methods such as Principle Component Analysis (PCA), Linear Discriminant Analysis (LDA), and Feature Selection (FS). We compared classification accuracy and running time of different combination methods on three microarray datasets and a simulation dataset. Experimental results show a remarkable improvement of 14.77% in classification accuracy of FS followed by RP compared to RP on BC-TCGA dataset. LDA followed by RP also helps RP to yield a more discriminative subspace with an increase of 13.65% on classification accuracy on the same dataset. FS followed by RP outperforms other combination methods in classification accuracy on most of the datasets.
The specific shapes of gender imbalance in scientific authorships: a network approach
Venue: arXiv cs.SI 2017
Year: 2017

Gender differences in collaborative research have received little attention when compared with the growing importance that women hold in academia and research. Unsurprisingly, most of bibliometric databases have a strong lack of directly available information by gender. Although empirical-based network approaches are often used in the study of research collaboration, the studies about the influence of gender dissimilarities on the resulting topological outcomes are still scarce. Here, networks of scientific subjects are used to characterize patterns that might be associated to five categories of authorships which were built based on gender. We find enough evidence that gender imbalance in scientific authorships brings a peculiar trait to the networks induced from papers published in Web of Science (WoS) indexed journals of Economics over the period 2010-2015 and having at least one author affiliated to a Portuguese institution. Our results show the emergence of a specific pattern when the network of co-occurring subjects is induced from a set of papers exclusively authored by men. Such a male-exclusive authorship condition is found to be the solely responsible for the emergence that particular shape in the network structure. This peculiar trait might facilitate future network analyses of research collaboration and interdisciplinarity.
Curvature Integration in a 5D Kernel for Extracting Vessel Connections in Retinal Images
Venue: arXiv cs.CV 2017
Year: 2017

Tree-like structures such as retinal images are widely studied in computer-aided diagnosis systems for large-scale screening programs. Despite several segmentation and tracking methods proposed in the literature, there still exist several limitations specifically when two or more curvilinear structures cross or bifurcate, or in the presence of interrupted lines or highly curved blood vessels. In this paper, we propose a novel approach based on multi-orientation scores augmented with a contextual affinity matrix, which both are inspired by the geometry of the primary visual cortex (V1) and their contextual connections. The connectivity is described with a five-dimensional kernel obtained as the fundamental solution of the Fokker-Planck equation modelling the cortical connectivity in the lifted space of positions, orientations, curvatures and intensity. It is further used in a self-tuning spectral clustering step to identify the main perceptual units in the stimuli. The proposed method has been validated on several easy and challenging structures in a set of artificial images and actual retinal patches. Supported by quantitative and qualitative results, the method is capable of overcoming the limitations of current state-of-the-art techniques.
Where is my Phone ? Personal Object Retrieval from Egocentric Images
Venue: arXiv cs.IR 2017
Year: 2017

This work presents a retrieval pipeline and evaluation scheme for the problem of finding the last appearance of personal objects in a large dataset of images captured from a wearable camera. Each personal object is modelled by a small set of images that define a query for a visual search engine.The retrieved results are reranked considering the temporal timestamps of the images to increase the relevance of the later detections. Finally, a temporal interleaving of the results is introduced for robustness against false detections. The Mean Reciprocal Rank is proposed as a metric to evaluate this problem. This application could help into developing personal assistants capable of helping users when they do not remember where they left their personal belongings.