OpenRaiser/Intern-Atlas huggingface dataset:
SmartSeed: Smart Seed Generation for Efficient Fuzzing
Venue: arXiv cs.CR 2019
Year: 2019

Fuzzing is an automated application vulnerability detection method. For genetic algorithm-based fuzzing, it can mutate the seed files provided by users to obtain a number of inputs, which are then used to test the objective application in order to trigger potential crashes. As shown in existing literature, the seed file selection is crucial for the efficiency of fuzzing. However, current seed selection strategies do not seem to be better than randomly picking seed files. Therefore, in this paper, we propose a novel and generic system, named SmartSeed, to generate seed files towards efficient fuzzing. Specifically, SmartSeed is designed based on a machine learning model to learn and generate high-value binary seeds. We evaluate SmartSeed along with American Fuzzy Lop (AFL) on 12 open-source applications with the input formats of mp3, bmp or flv. We also combine SmartSeed with different fuzzing tools to examine its compatibility. From extensive experiments, we find that SmartSeed has the following advantages: First, it only requires tens of seconds to generate sufficient high-value seeds. Second, it can generate seeds with multiple kinds of input formats and significantly improves the fuzzing performance for most applications with the same input format. Third, SmartSeed is compatible to different fuzzing tools. In total, our system discovers more than twice unique crashes and 5,040 extra unique paths than the existing best seed selection strategy for the evaluated 12 applications. From the crashes found by SmartSeed, we discover 16 new vulnerabilities and have received their CVE IDs.
Dynamic Pricing with Finitely Many Unknown Valuations
Venue: arXiv cs.LG 2019
Year: 2019

Motivated by posted price auctions where buyers are grouped in an unknown number of latent types characterized by their private values for the good on sale, we investigate revenue maximization in stochastic dynamic pricing when the distribution of buyers' private values is supported on an unknown set of points in [0,1] of unknown cardinality $K$. This setting can be viewed as an instance of a stochastic $K$-armed bandit problem where the location of the arms (the $K$ unknown valuations) must be learned as well. In the distribution-free case, we prove that our setting is just as hard as $K$-armed stochastic bandits: no algorithm can achieve a regret significantly better than $\sqrt{KT}$, (where T is the time horizon); we present an efficient algorithm matching this lower bound up to logarithmic factors. In the distribution-dependent case, we show that for all $K>2$ our setting is strictly harder than $K$-armed stochastic bandits by proving that it is impossible to obtain regret bounds that grow logarithmically in time or slower. On the other hand, when a lower bound $γ>0$ on the smallest drop in the demand curve is known, we prove an upper bound on the regret of order $(1/Δ+(\log \log T)/γ^2)(K\log T)$. This is a significant improvement on previously known regret bounds for discontinuous demand curves, that are at best of order $(K^{12}/γ^8)\sqrt{T}$. When $K=2$ in the distribution-dependent case, the hardness of our setting reduces to that of a stochastic $2$-armed bandit: we prove that an upper bound of order $(\log T)/Δ$ (up to $\log\log$ factors) on the regret can be achieved with no information on the demand curve. Finally, we show a $O(\sqrt{T})$ upper bound on the regret for the setting in which the buyers' decisions are nonstochastic, and the regret is measured with respect to the best between two fixed valuations one of which is known to the seller.
Suburban Fixed Wireless Access Channel Measurements and Models at 28 GHz for 90% Outdoor Coverage
Venue: arXiv cs.IT 2019
Year: 2019

Achieving adequate coverage with high gain antennas is key to realizing the full promise of the wide bandwidth available at cm/mm bands. We report extensive outdoor measurements at 28 GHz in suburban residential areas in New Jersey and Chile, with over 2000 links measured for same-street link types (vegetation blocked LOS) from 13 streets and other-street link types (true NLOS) from 7 streets, using a specialized narrowband channel sounder at ranges reaching 200 m. The measurements, applicable to fixed wireless access, involved a 55$^\circ$ transmit antenna placed on the exterior of a street-facing window and a 10$^\circ$ receive horn antenna spinning on top of a van mast at 3 m height, emulating a lamppost-mounted base station. Measured path gain-distance dependence is well represented by power-law models, and azimuth gains at the base are degraded through scattering by more than 4.3 dB for 10% of links. It was found that, with 51 dBm EIRP at the base station and 11 dBi antenna at an outdoor mounted terminal, 1 Gbps downlink rate can be delivered up to 100 m from a base station deployed in the same street with 90% coverage guarantee.
Universal Transformers
Venue: arXiv cs.CL 2019
Year: 2019

Recurrent neural networks (RNNs) sequentially process data by updating their state with each new data point, and have long been the de facto choice for sequence modeling tasks. However, their inherently sequential computation makes them slow to train. Feed-forward and convolutional architectures have recently been shown to achieve superior results on some sequence modeling tasks such as machine translation, with the added advantage that they concurrently process all inputs in the sequence, leading to easy parallelization and faster training times. Despite these successes, however, popular feed-forward sequence models like the Transformer fail to generalize in many simple tasks that recurrent models handle with ease, e.g. copying strings or even simple logical inference when the string or formula lengths exceed those observed at training time. We propose the Universal Transformer (UT), a parallel-in-time self-attentive recurrent sequence model which can be cast as a generalization of the Transformer model and which addresses these issues. UTs combine the parallelizability and global receptive field of feed-forward sequence models like the Transformer with the recurrent inductive bias of RNNs. We also add a dynamic per-position halting mechanism and find that it improves accuracy on several tasks. In contrast to the standard Transformer, under certain assumptions, UTs can be shown to be Turing-complete. Our experiments show that UTs outperform standard Transformers on a wide range of algorithmic and language understanding tasks, including the challenging LAMBADA language modeling task where UTs achieve a new state of the art, and machine translation where UTs achieve a 0.9 BLEU improvement over Transformers on the WMT14 En-De dataset.
A feature agnostic approach for glaucoma detection in OCT volumes
Venue: arXiv cs.CV 2019
Year: 2019

Optical coherence tomography (OCT) based measurements of retinal layer thickness, such as the retinal nerve fibre layer (RNFL) and the ganglion cell with inner plexiform layer (GCIPL) are commonly used for the diagnosis and monitoring of glaucoma. Previously, machine learning techniques have utilized segmentation-based imaging features such as the peripapillary RNFL thickness and the cup-to-disc ratio. Here, we propose a deep learning technique that classifies eyes as healthy or glaucomatous directly from raw, unsegmented OCT volumes of the optic nerve head (ONH) using a 3D Convolutional Neural Network (CNN). We compared the accuracy of this technique with various feature-based machine learning algorithms and demonstrated the superiority of the proposed deep learning based method. Logistic regression was found to be the best performing classical machine learning technique with an AUC of 0.89. In direct comparison, the deep learning approach achieved a substantially higher AUC of 0.94 with the additional advantage of providing insight into which regions of an OCT volume are important for glaucoma detection. Computing Class Activation Maps (CAM), we found that the CNN identified neuroretinal rim and optic disc cupping as well as the lamina cribrosa (LC) and its surrounding areas as the regions significantly associated with the glaucoma classification. These regions anatomically correspond to the well established and commonly used clinical markers for glaucoma diagnosis such as increased cup volume, cup diameter, and neuroretinal rim thinning at the superior and inferior segments.
Extracting Contact and Motion from Manipulation Videos
Venue: arXiv cs.CV 2019
Year: 2019

When we physically interact with our environment using our hands, we touch objects and force them to move: contact and motion are defining properties of manipulation. In this paper, we present an active, bottom-up method for the detection of actor-object contacts and the extraction of moved objects and their motions in RGBD videos of manipulation actions. At the core of our approach lies non-rigid registration: we continuously warp a point cloud model of the observed scene to the current video frame, generating a set of dense 3D point trajectories. Under loose assumptions, we employ simple point cloud segmentation techniques to extract the actor and subsequently detect actor-environment contacts based on the estimated trajectories. For each such interaction, using the detected contact as an attention mechanism, we obtain an initial motion segment for the manipulated object by clustering trajectories in the contact area vicinity and then we jointly refine the object segment and estimate its 6DOF pose in all observed frames. Because of its generality and the fundamental, yet highly informative, nature of its outputs, our approach is applicable to a wide range of perception and planning tasks. We qualitatively evaluate our method on a number of input sequences and present a comprehensive robot imitation learning example, in which we demonstrate the crucial role of our outputs in developing action representations/plans from observation.
Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
Venue: arXiv cs.SI 2019
Year: 2019

Focusing on coupling between edges, we generalize the relationship between the normalized graph Laplacian and random walks on graphs by devising an appropriate normalization for the Hodge Laplacian -- the generalization of the graph Laplacian for simplicial complexes -- and relate this to a random walk on edges. Importantly, these random walks are intimately connected to the topology of the simplicial complex, just as random walks on graphs are related to the topology of the graph. This serves as a foundational step towards incorporating Laplacian-based analytics for higher-order interactions. We demonstrate how to use these dynamics for data analytics that extract information about the edge-space of a simplicial complex that complements and extends graph-based analysis. Specifically, we use our normalized Hodge Laplacian to derive spectral embeddings for examining trajectory data of ocean drifters near Madagascar and also develop a generalization of personalized PageRank for the edge-space of simplicial complexes to analyze a book co-purchasing dataset.
IntRepair: Informed Repairing of Integer Overflows
Venue: arXiv cs.SE 2019
Year: 2019

Integer overflows have threatened software applications for decades. Thus, in this paper, we propose a novel technique to provide automatic repairs of integer overflows in C source code. Our technique, based on static symbolic execution, fuses detection, repair generation and validation. This technique is implemented in a prototype named IntRepair. We applied IntRepair to 2,052C programs (approx. 1 million lines of code) contained in SAMATE's Juliet test suite and 50 synthesized programs that range up to 20KLOC. Our experimental results show that IntRepair is able to effectively detect integer overflows and successfully repair them, while only increasing the source code (LOC) and binary (Kb) size by around 1%, respectively. Further, we present the results of a user study with 30 participants which shows that IntRepair repairs are more than 10x efficient as compared to manually generated code repairs
The Trailer of Blockchain Governance Game
Venue: arXiv cs.CR 2019
Year: 2019

This paper deals with the design of the secure blockchain network framework to prevent damages from an attacker. The decentralized network design called the Blockchain Governance Game is a new hybrid theoretical model and it provides the stochastic game framework to find best strategies towards preparation for preventing a network malfunction by an attacker. Analytically tractable results are obtained by using the fluctuation theory and the mixed strategy game theory. These results enable to predict the moment for operations and deliver the optimal portion of backup nodes to protect the blockchain network. This research helps for whom considers the initial coin offering or launching new blockchain based services with enhancing the security features.
A Lyra2 FPGA Core for Lyra2REv2-Based Cryptocurrencies
Venue: arXiv cs.CR 2019
Year: 2019

Lyra2REv2 is a hashing algorithm that consists of a chain of individual hashing algorithms and it is used as a proof-of-work function in several cryptocurrencies that aim to be ASIC-resistant. The most crucial hashing algorithm in the Lyra2REv2 chain is a specific instance of the general Lyra2 algorithm. In this work we present the first FPGA implementation of the aforementioned instance of Lyra2 and we explain how several properties of the algorithm can be exploited in order to optimize the design.
What is algebraic about algebraic effects and handlers?
Venue: arXiv cs.LO 2019
Year: 2019

This note recapitulates and expands the contents of a tutorial on the mathematical theory of algebraic effects and handlers which I gave at the Dagstuhl seminar 18172 "Algebraic effect handlers go mainstream". It is targeted roughly at the level of a doctoral student with some amount of mathematical training, or at anyone already familiar with algebraic effects and handlers as programming concepts who would like to know what they have to do with algebra. We draw an uninterrupted line of thought between algebra and computational effects. We begin on the mathematical side of things, by reviewing the classic notions of universal algebra: signatures, algebraic theories, and their models. We then generalize and adapt the theory so that it applies to computational effects. In the last step we replace traditional mathematical notation with one that is closer to programming languages.
Generative Adversarial Imitation from Observation
Venue: arXiv cs.LG 2019
Year: 2019

Imitation from observation (IfO) is the problem of learning directly from state-only demonstrations without having access to the demonstrator's actions. The lack of action information both distinguishes IfO from most of the literature in imitation learning, and also sets it apart as a method that may enable agents to learn from a large set of previously inapplicable resources such as internet videos. In this paper, we propose both a general framework for IfO approaches and also a new IfO approach based on generative adversarial networks called generative adversarial imitation from observation (GAIfO). We conduct experiments in two different settings: (1) when demonstrations consist of low-dimensional, manually-defined state features, and (2) when demonstrations consist of high-dimensional, raw visual data. We demonstrate that our approach performs comparably to classical imitation learning approaches (which have access to the demonstrator's actions) and significantly outperforms existing imitation from observation methods in high-dimensional simulation environments.
On Computing Centroids According to the $p$-Norms of Hamming Distance Vectors
Venue: arXiv cs.CC 2019
Year: 2019

In this paper we consider the $p$-Norm Hamming Centroid problem which asks to determine whether some given binary strings have a centroid with a bound on the $p$-norm of its Hamming distances to the strings. Specifically, given a set of strings $S$ and a real $k$, we consider the problem of determining whether there exists a string $s^*$ with $\big(\sum_{s \in S}d^p(s^*,s)\big)^{1/p} \leq k$, where $d(,)$ denotes the Hamming distance metric. This problem has important applications in data clustering, and is a generalization of the well-known polynomial-time solvable \textsc{Consensus String} $(p=1)$ problem, as well as the NP-hard \textsc{Closest String} $(p=\infty)$ problem. Our main result shows that the problem is NP-hard for all fixed rational $p > 1$, closing the gap for all rational values of $p$ between $1$ and $\infty$. Under standard complexity assumptions the reduction also implies that the problem has no $2^{o(n+m)}$-time or $2^{o(k^{\frac{p}{(p+1)}})}$-time algorithm, where $m$ denotes the number of input strings and $n$ denotes the length of each string, for any fixed $p > 1$. Both running time lower bounds are tight. In particular, we provide a $2^{k^{\frac{p}{(p+1)}+\varepsilon}}$-time algorithm for each fixed $\varepsilon > 0$. In the last part of the paper, we complement our hardness result by presenting a fixed-parameter algorithm and a factor-$2$ approximation algorithm for the problem.
The parameterised complexity of computing the maximum modularity of a graph
Venue: arXiv cs.DS 2019
Year: 2019

The maximum modularity of a graph is a parameter widely used to describe the level of clustering or community structure in a network. Determining the maximum modularity of a graph is known to be NP-complete in general, and in practice a range of heuristics are used to construct partitions of the vertex-set which give lower bounds on the maximum modularity but without any guarantee on how close these bounds are to the true maximum. In this paper we investigate the parameterised complexity of determining the maximum modularity with respect to various standard structural parameterisations of the input graph G. We show that the problem belongs to FPT when parameterised by the size of a minimum vertex cover for G, and is solvable in polynomial time whenever the treewidth or max leaf number of G is bounded by some fixed constant; we also obtain an FPT algorithm, parameterised by treewidth, to compute any constant-factor approximation to the maximum modularity. On the other hand we show that the problem is W[1]-hard (and hence unlikely to admit an FPT algorithm) when parameterised simultaneously by pathwidth and the size of a minimum feedback vertex set.
Linear Programming Approximations for Index Coding
Venue: arXiv cs.IT 2019
Year: 2019

Index coding, a source coding problem over broadcast channels, has been a subject of both theoretical and practical interest since its introduction (by Birk and Kol, 1998). In short, the problem can be defined as follows: there is an input $\textbf{x} \triangleq (\textbf{x}_1, \dots, \textbf{x}_n)$, a set of $n$ clients who each desire a single symbol $\textbf{x}_i$ of the input, and a broadcaster whose goal is to send as few messages as possible to all clients so that each one can recover its desired symbol. Additionally, each client has some predetermined "side information," corresponding to certain symbols of the input $\textbf{x}$, which we represent as the "side information graph" $\mathcal{G}$. The graph $\mathcal{G}$ has a vertex $v_i$ for each client and a directed edge $(v_i, v_j)$ indicating that client $i$ knows the $j$th symbol of the input. Given a fixed side information graph $\mathcal{G}$, we are interested in determining or approximating the "broadcast rate" of index coding on the graph, i.e. the fewest number of messages the broadcaster can transmit so that every client gets their desired information. Using index coding schemes based on linear programs (LPs), we take a two-pronged approach to approximating the broadcast rate. First, extending earlier work on planar graphs, we focus on approximating the broadcast rate for special graph families such as graphs with small chromatic number and disk graphs. In certain cases, we are able to show that simple LP-based schemes give constant-factor approximations of the broadcast rate, which seem extremely difficult to obtain in the general case. Second, we provide several LP-based schemes for the general case which are not constant-factor approximations, but which strictly improve on the prior best-known schemes.
On normality in shifts of finite type
Venue: arXiv cs.FL 2019
Year: 2019

In this paper we consider the notion of normality of sequences in shifts of finite type. A sequence is normal if the frequency of each block exists and is equal to the Parry measure of the block. We give a characterization of normality in terms of incompressibility by lossless transducers. The result was already known in the case of the full shift.
Prophet Secretary Through Blind Strategies
Venue: arXiv cs.DS 2019
Year: 2019

In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. In the late seventies, Krengel and Sucheston, and Gairing (1977) established that this worst case ratio is a universal constant equal to 1/2. In the last decade prophet inequalities has resurged as an important problem due to its connections to posted price mechanisms, frequently used in online sales. A very interesting variant is the Prophet Secretary problem, in which the only difference is that the samples arrive in a uniformly random order. For this variant several algorithms achieve a constant of 1-1/e and very recently this barrier was slightly improved. This paper analyzes strategies that set a nonincreasing sequence of thresholds to be applied at different times. The gambler stops the first time a sample surpasses the corresponding threshold. Specifically we consider a class of strategies called blind quantile strategies. They consist in fixing a function which is used to define a sequence of thresholds once the instance is revealed. Our main result shows that they can achieve a constant of 0.665, improving upon the best known result of Azar et al. (2018), and on Beyhaghi et al. (2018) (order selection). Our proof analyzes precisely the underlying stopping time distribution, relying on Schur-convexity theory. We further prove that blind strategies cannot achieve better than 0.675. Finally we prove that no algorithm for the gambler can achieve better than 0.732.
Hierarchical Reinforcement Learning for Zero-shot Generalization with Subtask Dependencies
Venue: arXiv cs.LG 2019
Year: 2019

We introduce a new RL problem where the agent is required to generalize to a previously-unseen environment characterized by a subtask graph which describes a set of subtasks and their dependencies. Unlike existing hierarchical multitask RL approaches that explicitly describe what the agent should do at a high level, our problem only describes properties of subtasks and relationships among them, which requires the agent to perform complex reasoning to find the optimal subtask to execute. To solve this problem, we propose a neural subtask graph solver (NSGS) which encodes the subtask graph using a recursive neural network embedding. To overcome the difficulty of training, we propose a novel non-parametric gradient-based policy, graph reward propagation, to pre-train our NSGS agent and further finetune it through actor-critic method. The experimental results on two 2D visual domains show that our agent can perform complex reasoning to find a near-optimal way of executing the subtask graph and generalize well to the unseen subtask graphs. In addition, we compare our agent with a Monte-Carlo tree search (MCTS) method showing that our method is much more efficient than MCTS, and the performance of NSGS can be further improved by combining it with MCTS.