OpenRaiser/Intern-Atlas huggingface dataset:
When Coding Style Survives Compilation: De-anonymizing Programmers from Executable Binaries
Venue: arXiv cs.CR 2017
Year: 2017

The ability to identify authors of computer programs based on their coding style is a direct threat to the privacy and anonymity of programmers. While recent work found that source code can be attributed to authors with high accuracy, attribution of executable binaries appears to be much more difficult. Many distinguishing features present in source code, e.g. variable names, are removed in the compilation process, and compiler optimization may alter the structure of a program, further obscuring features that are known to be useful in determining authorship. We examine programmer de-anonymization from the standpoint of machine learning, using a novel set of features that include ones obtained by decompiling the executable binary to source code. We adapt a powerful set of techniques from the domain of source code authorship attribution along with stylistic representations embedded in assembly, resulting in successful de-anonymization of a large set of programmers. We evaluate our approach on data from the Google Code Jam, obtaining attribution accuracy of up to 96% with 100 and 83% with 600 candidate programmers. We present an executable binary authorship attribution approach, for the first time, that is robust to basic obfuscations, a range of compiler optimization settings, and binaries that have been stripped of their symbol tables. We perform programmer de-anonymization using both obfuscated binaries, and real-world code found "in the wild" in single-author GitHub repositories and the recently leaked Nulled.IO hacker forum. We show that programmers who would like to remain anonymous need to take extreme countermeasures to protect their privacy.
Taming the Noise in Reinforcement Learning via Soft Updates
Venue: arXiv cs.LG 2017
Year: 2017

Model-free reinforcement learning algorithms, such as Q-learning, perform poorly in the early stages of learning in noisy environments, because much effort is spent unlearning biased estimates of the state-action value function. The bias results from selecting, among several noisy estimates, the apparent optimum, which may actually be suboptimal. We propose G-learning, a new off-policy learning algorithm that regularizes the value estimates by penalizing deterministic policies in the beginning of the learning process. We show that this method reduces the bias of the value-function estimation, leading to faster convergence to the optimal value and the optimal policy. Moreover, G-learning enables the natural incorporation of prior domain knowledge, when available. The stochastic nature of G-learning also makes it avoid some exploration costs, a property usually attributed only to on-policy algorithms. We illustrate these ideas in several examples, where G-learning results in significant improvements of the convergence rate and the cost of the learning process.
Low rank approximation and decomposition of large matrices using error correcting codes
Venue: arXiv cs.IT 2017
Year: 2017

Low rank approximation is an important tool used in many applications of signal processing and machine learning. Recently, randomized sketching algorithms were proposed to effectively construct low rank approximations and obtain approximate singular value decompositions of large matrices. Similar ideas were used to solve least squares regression problems. In this paper, we show how matrices from error correcting codes can be used to find such low rank approximations and matrix decompositions, and extend the framework to linear least squares regression problems. The benefits of using these code matrices are the following: (i) They are easy to generate and they reduce randomness significantly. (ii) Code matrices with mild properties satisfy the subspace embedding property, and have a better chance of preserving the geometry of an entire subspace of vectors. (iii) For parallel and distributed applications, code matrices have significant advantages over structured random matrices and Gaussian random matrices. (iv) Unlike Fourier or Hadamard transform matrices, which require sampling $O(k\log k)$ columns for a rank-$k$ approximation, the log factor is not necessary for certain types of code matrices. That is, $(1+ε)$ optimal Frobenius norm error can be achieved for a rank-$k$ approximation with $O(k/ε)$ samples. (v) Fast multiplication is possible with structured code matrices, so fast approximations can be achieved for general dense input matrices. (vi) For least squares regression problem $\min\|Ax-b\|_2$ where $A\in \mathbb{R}^{n\times d}$, the $(1+ε)$ relative error approximation can be achieved with $O(d/ε)$ samples, with high probability, when certain code matrices are used.
The Role of Context Types and Dimensionality in Learning Word Embeddings
Venue: arXiv cs.CL 2017
Year: 2017

We provide the first extensive evaluation of how using different types of context to learn skip-gram word embeddings affects performance on a wide range of intrinsic and extrinsic NLP tasks. Our results suggest that while intrinsic tasks tend to exhibit a clear preference to particular types of contexts and higher dimensionality, more careful tuning is required for finding the optimal settings for most of the extrinsic tasks that we considered. Furthermore, for these extrinsic tasks, we find that once the benefit from increasing the embedding dimensionality is mostly exhausted, simple concatenation of word embeddings, learned with different context types, can yield further performance gains. As an additional contribution, we propose a new variant of the skip-gram model that learns word embeddings from weighted contexts of substitute words.
The Impact of Project Management in Virtual Environment: A Software Industry Perspective
Venue: arXiv cs.CY 2017
Year: 2017

Virtual team in a project within an Organization could achieve optimize project performance by acquiring appropriate human resources, coordination, communication and regular performance evaluation. According to the literature many ICT tools will collaborate to manage virtual teams, but still most of the projects lead to failure in the software industry. Aim of this research is to discover the most affected factors for virtual project human resource management.
Generalized Hamming weights for almost affine codes
Venue: arXiv cs.IT 2017
Year: 2017

We define generalized Hamming weights for almost affine codes. We show how various aspects and applications of generalized Hamming weights for linear codes, such as Wei duality, generalized Kung's bound, profiles, connection to wire-tap channels of type II, apply to the larger class of almost affine codes in general. In addition we discuss duality of almost affine codes,and of the smaller class of multilinear codes. We also give results about weight distributions of infinite series of almost affine codes, each series obtained from a fixed code by extending the code alphabet.
Update or Wait: How to Keep Your Data Fresh
Venue: arXiv cs.IT 2017
Year: 2017

In this work, we study how to optimally manage the freshness of information updates sent from a source node to a destination via a channel. A proper metric for data freshness at the destination is the age-of-information, or simply age, which is defined as how old the freshest received update is since the moment that this update was generated at the source node (e.g., a sensor). A reasonable update policy is the zero-wait policy, i.e., the source node submits a fresh update once the previous update is delivered and the channel becomes free, which achieves the maximum throughput and the minimum delay. Surprisingly, this zero-wait policy does not always minimize the age. This counter-intuitive phenomenon motivates us to study how to optimally control information updates to keep the data fresh and to understand when the zero-wait policy is optimal. We introduce a general age penalty function to characterize the level of dissatisfaction on data staleness and formulate the average age penalty minimization problem as a constrained semi-Markov decision problem (SMDP) with an uncountable state space. We develop efficient algorithms to find the optimal update policy among all causal policies, and establish sufficient and necessary conditions for the optimality of the zero-wait policy. Our investigation shows that the zero-wait policy is far from the optimum if (i) the age penalty function grows quickly with respect to the age, (ii) the packet transmission times over the channel are positively correlated over time, or (iii) the packet transmission times are highly random (e.g., following a heavy-tail distribution).
Stationary signal processing on graphs
Venue: arXiv cs.DS 2017
Year: 2017

Graphs are a central tool in machine learning and information processing as they allow to conveniently capture the structure of complex datasets. In this context, it is of high importance to develop flexible models of signals defined over graphs or networks. In this paper, we generalize the traditional concept of wide sense stationarity to signals defined over the vertices of arbitrary weighted undirected graphs. We show that stationarity is expressed through the graph localization operator reminiscent of translation. We prove that stationary graph signals are characterized by a well-defined Power Spectral Density that can be efficiently estimated even for large graphs. We leverage this new concept to derive Wiener-type estimation procedures of noisy and partially observed signals and illustrate the performance of this new model for denoising and regression.
Inferring Energy Bounds via Static Program Analysis and Evolutionary Modeling of Basic Blocks
Venue: arXiv cs.DC 2017
Year: 2017

The ever increasing number and complexity of energy-bound devices (such as the ones used in Internet of Things applications, smart phones, and mission critical systems) pose an important challenge on techniques to optimize their energy consumption and to verify that they will perform their function within the available energy budget. In this work we address this challenge from the software point of view and propose a novel parametric approach to estimating tight bounds on the energy consumed by program executions that are practical for their application to energy verification and optimization. Our approach divides a program into basic (branchless) blocks and estimates the maximal and minimal energy consumption for each block using an evolutionary algorithm. Then it combines the obtained values according to the program control flow, using static analysis, to infer functions that give both upper and lower bounds on the energy consumption of the whole program and its procedures as functions on input data sizes. We have tested our approach on (C-like) embedded programs running on the XMOS hardware platform. However, our method is general enough to be applied to other microprocessor architectures and programming languages. The bounds obtained by our prototype implementation can be tight while remaining on the safe side of budgets in practice, as shown by our experimental evaluation.
Source-Channel Secrecy for Shannon Cipher System
Venue: arXiv cs.IT 2017
Year: 2017

Recently, a secrecy measure based on list-reconstruction has been proposed [2], in which a wiretapper is allowed to produce a list of $2^{mR_{L}}$ reconstruction sequences and the secrecy is measured by the minimum distortion over the entire list. In this paper, we show that this list secrecy problem is equivalent to the one with secrecy measured by a new quantity \emph{lossy-equivocation}, which is proven to be the minimum optimistic 1-achievable source coding rate (the minimum coding rate needed to reconstruct the source within target distortion with positive probability for \emph{infinitely many blocklengths}) of the source with the wiretapped signal as two-sided information, and also can be seen as a lossy extension of conventional equivocation. Upon this (or list) secrecy measure, we study source-channel secrecy problem in the discrete memoryless Shannon cipher system with \emph{noisy} wiretap channel. Two inner bounds and an outer bound on the achievable region of secret key rate, list rate, wiretapper distortion, and distortion of legitimate user are given. The inner bounds are derived by using uncoded scheme and (operationally) separate scheme, respectively. Thanks to the equivalence between lossy-equivocation secrecy and list secrecy, information spectrum method is leveraged to prove the outer bound. As special cases, the admissible region for the case of degraded wiretap channel or lossless communication for legitimate user has been characterized completely. For both these two cases, separate scheme is proven to be optimal. Interestingly, however, separation indeed suffers performance loss for other certain cases. Besides, we also extend our results to characterize the achievable region for Gaussian communication case. As a side product optimistic lossy source coding has also been addressed.
Interference Alignment in MIMO Interference Channels using SDP Relaxation
Venue: arXiv cs.IT 2017
Year: 2017

Nowadays, providing higher data rate is a momentous goal for wireless communications systems. Interference is one of the important obstacles to reach this purpose. Interference alignment is a management technique that align interference from other transmitters in the least possible dimension subspace at each receiver and as a result, provide the remaining dimensions for free interference signal. An uncoordinated interference is an example of interference which cannot be aligned coordinately with interference from coordinated part and consequently, the performance of interference alignment approaches is degraded. In this paper, we propose two rank minimization methods to enhance the performance of interference alignment in the presence of uncoordinated interference sources. Firstly, a new objective function is chosen then, a new class of convex relaxation is proposed with respect to the uncoordinated interference which leads to decrease the optimal value of our optimization problem. Moreover, we use schatten-p-norm as surrogate of rank function and we implement iteratively reweighted algorithm to solve optimization problem. In addition, we apply our proposed methods to mitigate interference in relay-aided MIMO interference channel, and propose a weighted-sum method to improve the performance of interference alignment in the amplify-and-forward relay-aided MIMO system based on the rank minimization approach. Finally, our simulation results show that our proposed methods can obtain considerably higher multiplexing gain and sum rate than other approaches in the interference alignment framework and the performance of interference alignment is improved.
Partial Sum Minimization of Singular Values Representation on Grassmann Manifolds
Venue: arXiv cs.CV 2017
Year: 2017

As a significant subspace clustering method, low rank representation (LRR) has attracted great attention in recent years. To further improve the performance of LRR and extend its applications, there are several issues to be resolved. The nuclear norm in LRR does not sufficiently use the prior knowledge of the rank which is known in many practical problems. The LRR is designed for vectorial data from linear spaces, thus not suitable for high dimensional data with intrinsic non-linear manifold structure. This paper proposes an extended LRR model for manifold-valued Grassmann data which incorporates prior knowledge by minimizing partial sum of singular values instead of the nuclear norm, namely Partial Sum minimization of Singular Values Representation (GPSSVR). The new model not only enforces the global structure of data in low rank, but also retains important information by minimizing only smaller singular values. To further maintain the local structures among Grassmann points, we also integrate the Laplacian penalty with GPSSVR. An effective algorithm is proposed to solve the optimization problem based on the GPSSVR model. The proposed model and algorithms are assessed on some widely used human action video datasets and a real scenery dataset. The experimental results show that the proposed methods obviously outperform other state-of-the-art methods.
Plausible Deniability over Broadcast Channels
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we introduce the notion of Plausible Deniability in an information theoretic framework. We consider a scenario where an entity that eavesdrops through a broadcast channel summons one of the parties in a communication protocol to reveal their message (or signal vector). It is desirable that the summoned party have enough freedom to produce a fake output that is likely plausible given the eavesdropper's observation. We examine three variants of this problem -- Message Deniability, Transmitter Deniability, and Receiver Deniability. In the first setting, the message sender is summoned to produce the sent message. Similarly, in the second and third settings, the transmitter and the receiver are required to produce the transmitted codeword, and the received vector respectively. For each of these settings, we examine the maximum communication rate that allows a given minimum rate of plausible fake outputs. For the Message and Transmitter Deniability problems, we fully characterise the capacity region for general broadcast channels, while for the Receiver Deniability problem, we give an achievable rate region for physically degraded broadcast channels.
Virtual Machine Warmup Blows Hot and Cold
Venue: arXiv cs.PL 2017
Year: 2017

Virtual Machines (VMs) with Just-In-Time (JIT) compilers are traditionally thought to execute programs in two phases: the initial warmup phase determines which parts of a program would most benefit from dynamic compilation, before JIT compiling those parts into machine code; subsequently the program is said to be at a steady state of peak performance. Measurement methodologies almost always discard data collected during the warmup phase such that reported measurements focus entirely on peak performance. We introduce a fully automated statistical approach, based on changepoint analysis, which allows us to determine if a program has reached a steady state and, if so, whether that represents peak performance or not. Using this, we show that even when run in the most controlled of circumstances, small, deterministic, widely studied microbenchmarks often fail to reach a steady state of peak performance on a variety of common VMs. Repeating our experiment on 3 different machines, we found that at most 43.5% of <VM, benchmark> pairs consistently reach a steady state of peak performance.
Visual descriptors for content-based retrieval of remote sensing images
Venue: arXiv cs.CV 2017
Year: 2017

In this paper we present an extensive evaluation of visual descriptors for the content-based retrieval of remote sensing (RS) images. The evaluation includes global hand-crafted, local hand-crafted, and Convolutional Neural Network (CNNs) features coupled with four different Content-Based Image Retrieval schemes. We conducted all the experiments on two publicly available datasets: the 21-class UC Merced Land Use/Land Cover (LandUse) dataset and 19-class High-resolution Satellite Scene dataset (SceneSat). The content of RS images might be quite heterogeneous, ranging from images containing fine grained textures, to coarse grained ones or to images containing objects. It is therefore not obvious in this domain, which descriptor should be employed to describe images having such a variability. Results demonstrate that CNN-based features perform better than both global and and local hand-crafted features whatever is the retrieval scheme adopted. Features extracted from SatResNet-50, a residual CNN suitable fine-tuned on the RS domain, shows much better performance than a residual CNN pre-trained on multimedia scene and object images. Features extracted from NetVLAD, a CNN that considers both CNN and local features, works better than others CNN solutions on those images that contain fine-grained textures and objects.
On the Semantics of Intensionality
Venue: arXiv cs.LO 2017
Year: 2017

In this paper we propose a categorical theory of intensionality. We first revisit the notion of intensionality, and discuss we its relevance to logic and computer science. It turns out that 1-category theory is not the most appropriate vehicle for studying the interplay of extension and intension. We are thus led to consider the P-categories of Čubrić, Dybjer and Scott, which are categories only up to a partial equivalence relation (PER). In this setting, we introduce a new P-categorical construct, that of exposures. Exposures are very nearly functors, except that they do not preserve the PERs of the P-category. Inspired by the categorical semantics of modal logic, we begin to develop their theory. Our leading examples demonstrate that an exposure is an abstraction of well-behaved intensional devices, such as Gödel numberings. The outcome is a unifying framework in which classic results of Kleene, Gödel, Tarski and Rice find concise, clear formulations, and where each logical device or assumption involved in their proofs can be expressed in the same algebraic manner.
Design of Geometric Molecular Bonds
Venue: arXiv cs.IT 2017
Year: 2017

An example of a nonspecific molecular bond is the affinity of any positive charge for any negative charge (like-unlike), or of nonpolar material for itself when in aqueous solution (like-like). This contrasts specific bonds such as the affinity of the DNA base A for T, but not for C, G, or another A. Recent experimental breakthroughs in DNA nanotechnology demonstrate that a particular nonspecific like-like bond ("blunt-end DNA stacking" that occurs between the ends of any pair of DNA double-helices) can be used to create specific "macrobonds" by careful geometric arrangement of many nonspecific blunt ends, motivating the need for sets of macrobonds that are orthogonal: two macrobonds not intended to bind should have relatively low binding strength, even when misaligned. To address this need, we introduce geometric orthogonal codes that abstractly model the engineered DNA macrobonds as two-dimensional binary codewords. While motivated by completely different applications, geometric orthogonal codes share similar features to the optical orthogonal codes studied by Chung, Salehi, and Wei. The main technical difference is the importance of 2D geometry in defining codeword orthogonality.
Graying the black box: Understanding DQNs
Venue: arXiv cs.LG 2017
Year: 2017

In recent years there is a growing interest in using deep representations for reinforcement learning. In this paper, we present a methodology and tools to analyze Deep Q-networks (DQNs) in a non-blind matter. Moreover, we propose a new model, the Semi Aggregated Markov Decision Process (SAMDP), and an algorithm that learns it automatically. The SAMDP model allows us to identify spatio-temporal abstractions directly from features and may be used as a sub-goal detector in future work. Using our tools we reveal that the features learned by DQNs aggregate the state space in a hierarchical fashion, explaining its success. Moreover, we are able to understand and describe the policies learned by DQNs for three different Atari2600 games and suggest ways to interpret, debug and optimize deep neural networks in reinforcement learning.