OpenRaiser/Intern-Atlas huggingface dataset:
A Dataset of Dockerfiles
Venue: arXiv cs.SE 2020
Year: 2020

Dockerfiles are one of the most prevalent kinds of DevOps artifacts used in industry. Despite their prevalence, there is a lack of sophisticated semantics-aware static analysis of Dockerfiles. In this paper, we introduce a dataset of approximately 178,000 unique Dockerfiles collected from GitHub. To enhance the usability of this data, we describe five representations we have devised for working with, mining from, and analyzing these Dockerfiles. Each Dockerfile representation builds upon the previous ones, and the final representation, created by three levels of nested parsing and abstraction, makes tasks such as mining and static checking tractable. The Dockerfiles, in each of the five representations, along with metadata and the tools used to shepard the data from one representation to the next are all available at: https://doi.org/10.5281/zenodo.3628771.
An iterative splitting method for pricing European options under the Heston model
Venue: arXiv cs.CE 2020
Year: 2020

In this paper, we propose an iterative splitting method to solve the partial differential equations in option pricing problems. We focus on the Heston stochastic volatility model and the derived two-dimensional partial differential equation (PDE). We take the European option as an example and conduct numerical experiments using different boundary conditions. The iterative splitting method transforms the two-dimensional equation into two quasi one-dimensional equations with the variable on the other dimension fixed, which helps to lower the computational cost. Numerical results show that the iterative splitting method together with an artificial boundary condition (ABC) based on the method by Li and Huang (2019) gives the most accurate option price and Greeks compared to the classic finite difference method with the commonly-used boundary conditions in Heston (1993).
A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits
Venue: arXiv cs.CC 2020
Year: 2020

We show that there is a defining equation of degree at most $\mathsf{poly}(n)$ for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field $\mathbb{F}$, there is a non-zero $n^2$-variate polynomial $P \in \mathbb{F}[x_{1, 1}, \ldots, x_{n, n}]$ of degree at most $\mathsf{poly}(n)$ such that every matrix $M$ which can be written as a sum of a matrix of rank at most $n/100$ and a matrix of sparsity at most $n^2/100$ satisfies $P(M) = 0$. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [GHIL16] and improves the best upper bound known for this problem down from $\exp(n^2)$ [KLPS14, GHIL16] to $\mathsf{poly}(n)$. We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices $M$ such that the linear transformation represented by $M$ can be computed by an algebraic circuit with at most $n^2/200$ edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [SV15] to construct low degree "universal" maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [KI04].
Analytical Framework of Beamwidth Selection for RT-ICM Millimeter-Wave Clusters
Venue: arXiv cs.IT 2020
Year: 2020

Beamforming for mmWave communications is well-studied in the PHY based on the channel parameters to develop optimum receiver processing techniques. However, even before signal processing, antenna structure and radiation parameters affect the beamforming performance primarily. For example, in contrast to common belief, narrow beamwidth (bmW) may result in degraded beamforming performance. In order to address the impairments such as beam misalignments, outage loss, tracking inability, blockage, etc., an optimum value of the bmW must be determined. In this paper, assuming a communication system that creates a beam per cluster, we theoretically investigate the bmW and received power relation in the cluster level mmWave channels. We adopt ULA structure and formulate its antenna gain with respect to the bmW. Two beam models are considered for the main lobe of the array pattern, rectangular and triangular. We derive bmW-dependent extracted power expressions for two intra-cluster channel models, 802.11ad and our previous work, RT-ICM. Combining antenna and channel gains, in case of a beam misalignment, we find that the optimum bmW that maximizes the received power is larger than the alignment error when the error itself is larger than the standard deviation of the cluster power-angle spectrum. Once the alignment error is smaller than the standard deviation, we confirm that the optimum bmW converges zero. Performing asymptotic analysis of the received power, we give the formulation and insights that the practical nonzero bmW values can be achieved although sacrificing subtle from the maximum received power. Our analysis shows that to reach 95% of the maximum power for an indoor mmWave cluster, a practical bmW of 7-10 degrees is enough, which can be created with 18-20 antenna elements. In the simulation section, we show that the expressions given by the analysis match to the simulated results.
Overlay Satellite-Terrestrial Networks for IoT under Hybrid Interference Environments
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, we consider an overlay satellite-terrestrial network (OSTN) where an opportunistically selected terrestrial internet-of-things (IoT) network assists the primary satellite communications as well as accesses the spectrum for its own communications under hybrid interference received from extra-terrestrial sources (ETSs) and terrestrial sources (TSs). Herein, the IoT network adopts power-domain multiplexing to amplify-and-forward the superposed satellite and IoT signals. Considering a unified analytical framework for shadowed-Rician fading with integer/non-integer Nakagami-\emph{m} parameter for satellite and interfering ETSs links along with the integer/non-integer Nakagami-\emph{m} fading for terrestrial IoT and interfering TSs links, we derive the outage probability (OP) of both satellite and IoT networks. Further, we derive the respective asymptotic OP expressions to reveal the diversity order of both satellite and IoT networks under the two conditions, namely when the transmit power of interferers: $(a)$ remains fixed; and $(b)$ varies proportional to the transmit powers of main satellite and IoT users. We show that the proposed OSTN with adaptive power-splitting factor benefits the IoT network while guaranteeing certain quality-of-service (QoS) of satellite network. We verify the numerical results by simulations.
Clickbait Detection using Multiple Categorization Techniques
Venue: arXiv cs.SI 2020
Year: 2020

Clickbaits are online articles with deliberately designed misleading titles for luring more and more readers to open the intended web page. Clickbaits are used to tempted visitors to click on a particular link either to monetize the landing page or to spread the false news for sensationalization. The presence of clickbaits on any news aggregator portal may lead to unpleasant experience to readers. Automatic detection of clickbait headlines from news headlines has been a challenging issue for the machine learning community. A lot of methods have been proposed for preventing clickbait articles in recent past. However, the recent techniques available in detecting clickbaits are not much robust. This paper proposes a hybrid categorization technique for separating clickbait and non-clickbait articles by integrating different features, sentence structure, and clustering. During preliminary categorization, the headlines are separated using eleven features. After that, the headlines are recategorized using sentence formality, syntactic similarity measures. In the last phase, the headlines are again recategorized by applying clustering using word vector similarity based on t-Stochastic Neighbourhood Embedding (t-SNE) approach. After categorization of these headlines, machine learning models are applied to the data set to evaluate machine learning algorithms. The obtained experimental results indicate the proposed hybrid model is more robust, reliable and efficient than any individual categorization techniques for the real-world dataset we used.
Efficient Tuning-Free $\ell_1$-Regression of Nonnegative Compressible Signals
Venue: arXiv cs.IT 2020
Year: 2020

In compressed sensing the goal is to recover a signal from as few as possible noisy, linear measurements. The general assumption is that the signal has only a few non-zero entries. The recovery can be performed by multiple different decoders, however most of them rely on some tuning. Given an estimate for the noise level a common convex approach to recover the signal is basis pursuit denoising. If the measurement matrix has the robust null space property with respect to the $\ell_2$-norm, basis pursuit denoising obeys stable and robust recovery guarantees. In the case of unknown noise levels, nonnegative least squares recovers non-negative signals if the measurement matrix fulfills an additional property (sometimes called the $M^+$-criterion). However, if the measurement matrix is the biadjacency matrix of a random left regular bipartite graph it obeys with a high probability the null space property with respect to the $\ell_1$-norm with optimal parameters. Therefore, we discuss non-negative least absolute deviation (NNLAD). For these measurement matrices, we prove a uniform, stable and robust recovery guarantee without the need for tuning. Such guarantees are important, since binary expander matrices are sparse and thus allow for fast sketching and recovery. We will further present a method to solve the NNLAD numerically and show that this is comparable to state of the art methods. Lastly, we explain how the NNLAD can be used for viral detection in the recent COVID-19 crisis.
On amenability of constraint satisfaction problems
Venue: arXiv cs.LO 2020
Year: 2020

Recent results show that a constraint satisfaction problem (CSP) defined over rational numbers with their natural ordering has a solution if and only if it has a definable solution. The proof uses advanced results from topology and modern model theory. The aim of this paper is threefold. (1) We give a simple purely-logical proof of the claim and show that the advanced results from topology and model theory are not needed; (2) we introduce an intrinsic characterisation of the statement "definable CSP has a solution iff it has a definable solution" and investigate it in general intuitionistic set theories (3) we show that the results from modern model theory are indeed needed, but for the implication reversed: we prove that "definable CSP has a solution iff it has a definable solution" holds over a countable structure if and only if the automorphism group of the structure is extremely amenable.
Scene-Aware Error Modeling of LiDAR/Visual Odometry for Fusion-based Vehicle Localization
Venue: arXiv cs.RO 2020
Year: 2020

Localization is an essential technique in mobile robotics. In a complex environment, it is necessary to fuse different localization modules to obtain more robust results, in which the error model plays a paramount role. However, exteroceptive sensor-based odometries (ESOs), such as LiDAR/visual odometry, often deliver results with scene-related error, which is difficult to model accurately. To address this problem, this research designs a scene-aware error model for ESO, based on which a multimodal localization fusion framework is developed. In addition, an end-to-end learning method is proposed to train this error model using sparse global poses such as GPS/IMU results. The proposed method is realized for error modeling of LiDAR/visual odometry, and the results are fused with dead reckoning to examine the performance of vehicle localization. Experiments are conducted using both simulation and real-world data of experienced and unexperienced environments, and the experimental results demonstrate that with the learned scene-aware error models, vehicle localization accuracy can be largely improved and shows adaptiveness in unexperienced scenes.
Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement
Venue: arXiv cs.CL 2020
Year: 2020

We propose the Recursive Non-autoregressive Graph-to-Graph Transformer architecture (RNGTr) for the iterative refinement of arbitrary graphs through the recursive application of a non-autoregressive Graph-to-Graph Transformer and apply it to syntactic dependency parsing. We demonstrate the power and effectiveness of RNGTr on several dependency corpora, using a refinement model pre-trained with BERT. We also introduce Syntactic Transformer (SynTr), a non-recursive parser similar to our refinement model. RNGTr can improve the accuracy of a variety of initial parsers on 13 languages from the Universal Dependencies Treebanks, English and Chinese Penn Treebanks, and the German CoNLL2009 corpus, even improving over the new state-of-the-art results achieved by SynTr, significantly improving the state-of-the-art for all corpora tested.
Graphical Games and Decomposition
Venue: arXiv cs.GT 2020
Year: 2020

We consider graphical games as introduced by Kearns et al. (2001). First we analyse the interaction of graphicality with a notion of strategic equivalence of games, providing a minimal complexity graphical description for games. Then we study the interplay between graphicality and the classical decomposition of games proposed by Candogan et al. (2011), characterizing the graphical properties of each part of the decomposition.
Topological Data Analysis in Text Classification: Extracting Features with Additive Information
Venue: arXiv cs.LG 2020
Year: 2020

While the strength of Topological Data Analysis has been explored in many studies on high dimensional numeric data, it is still a challenging task to apply it to text. As the primary goal in topological data analysis is to define and quantify the shapes in numeric data, defining shapes in the text is much more challenging, even though the geometries of vector spaces and conceptual spaces are clearly relevant for information retrieval and semantics. In this paper, we examine two different methods of extraction of topological features from text, using as the underlying representations of words the two most popular methods, namely word embeddings and TF-IDF vectors. To extract topological features from the word embedding space, we interpret the embedding of a text document as high dimensional time series, and we analyze the topology of the underlying graph where the vertices correspond to different embedding dimensions. For topological data analysis with the TF-IDF representations, we analyze the topology of the graph whose vertices come from the TF-IDF vectors of different blocks in the textual document. In both cases, we apply homological persistence to reveal the geometric structures under different distance resolutions. Our results show that these topological features carry some exclusive information that is not captured by conventional text mining methods. In our experiments we observe adding topological features to the conventional features in ensemble models improves the classification results (up to 5\%). On the other hand, as expected, topological features by themselves may be not sufficient for effective classification. It is an open problem to see whether TDA features from word embeddings might be sufficient, as they seem to perform within a range of few points from top results obtained with a linear support vector classifier.
Byzantine Agreement, Broadcast and State Machine Replication with Near-optimal Good-case Latency
Venue: arXiv cs.CR 2020
Year: 2020

This paper investigates the problem \textit{good-case latency} of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty parties have the same input (or in BB/SMR when the sender/leader is non-faulty). Previous result implies a lower bound showing that any Byzantine agreement or broadcast protocol tolerating more than $n/3$ faults must have a good-case latency of at least $Δ$, where $Δ$ is the assumed maximum message delay bound. Our first result is a family of protocols we call $1Δ$ that have near-optimal good-case latency. We propose a protocol $1Δ$-BA that solves Byzantine agreement in the synchronous and authenticated setting with near-optimal good-case latency of $Δ+2δ$ and optimal resilience $f<n/2$, where $δ$ is the actual (unknown) delay bound. We then extend our protocol and present $1Δ$-BB and $1Δ$-SMR for Byzantine fault tolerant broadcast and state machine replication, respectively, in the same setting and with the same good-case latency of $Δ+2δ$ and $f<n/2$ fault tolerance. Our $1Δ$-SMR upper bound improves the gap between the best current solution, Sync HotStuff, which obtains a good-case latency of $2Δ$ per command and the lower bound of $Δ$ on good-case latency. Finally, we investigate weaker notions of the synchronous setting and show how to adopt the $1Δ$ approach to these models.
Analytical Estimation and Localization of Hardware Trojan Vulnerability in RTL Designs
Venue: arXiv cs.CR 2020
Year: 2020

Offshoring the proprietary Intellectual property (IP) has recently increased the threat of malicious logic insertion in the form of Hardware Trojan (HT). A potential and stealthy HT is triggered with nets that switch rarely during regular circuit operation. Detection of HT in the host design requires exhaustive simulation to activate the HT during pre- and postsilicon. Although the nets with variable switching probability less than a threshold are primarily chosen as a good candidate for Trojan triggering, there is no systematic fine-grained approach for earlier detection of rare nets from word-level measures of input signals. In this paper, we propose a high-level technique to estimate the nets with the rare activity of arithmetic modules from word-level information. Specifically, for a given module, we use the knowledge of internal construction of the architecture to detect "low activity" and "local regions" without resorting to expensive RTL and other low-level simulations. The presented heuristic method abstracts away from the low-level details of design and describes the rare activity of bits (modules) in a word (architecture) as a function of signal statistics. The resulting quick estimates of nets in rare regions allows a designer to develop a compact test generation algorithm without the knowledge of the bit-level activity. We determine the effect of different positions of the breakpoint in the input signal to calculate the accuracy of the approach. We conduct a set of experiments on six adder architectures and four multiplier architectures. The average error to calculate the rare nets between RTL simulation and estimated values are below 2% in all architectures.
Learning Contextualized Sentence Representations for Document-Level Neural Machine Translation
Venue: arXiv cs.CL 2020
Year: 2020

Document-level machine translation incorporates inter-sentential dependencies into the translation of a source sentence. In this paper, we propose a new framework to model cross-sentence dependencies by training neural machine translation (NMT) to predict both the target translation and surrounding sentences of a source sentence. By enforcing the NMT model to predict source context, we want the model to learn "contextualized" source sentence representations that capture document-level dependencies on the source side. We further propose two different methods to learn and integrate such contextualized sentence embeddings into NMT: a joint training method that jointly trains an NMT model with the source context prediction model and a pre-training & fine-tuning method that pretrains the source context prediction model on a large-scale monolingual document corpus and then fine-tunes it with the NMT model. Experiments on Chinese-English and English-German translation show that both methods can substantially improve the translation quality over a strong document-level Transformer baseline.
SmartCert: Redesigning Digital Certificates with Smart Contracts
Venue: arXiv cs.CR 2020
Year: 2020

The Transport Layer Security (TLS) protocol and its public-key infrastructure (PKI) are widely used in the Internet to achieve secure communication. Validating domain ownership by trusted certification authorities (CAs) is a critical step in issuing digital certificates, but unfortunately, this process provides a poor security level. In this work, we present SmartCert, a novel approach based on smart contracts to improve digital certificates. A certificate in SmartCert conveys detailed information about its validation state which is constantly changing but only with respect to the specified smart contract code and individual domain policies. CAs issuing and updating certificates are kept accountable and their actions are transparent and monitored by the code. We present the implementation and evaluation of SmartCert, and discuss its deployability.
Performance Benchmarking of State-of-the-Art Software Switches for NFV
Venue: arXiv cs.NI 2020
Year: 2020

With the ultimate goal of replacing proprietary hardware appliances with Virtual Network Functions (VNFs) implemented in software, Network Function Virtualization (NFV) has been gaining popularity in the past few years. Software switches route traffic between VNFs and physical Network Interface Cards (NICs). It is of paramount importance to compare the performance of different switch designs and architectures. In this paper, we propose a methodology to compare fairly and comprehensively the performance of software switches. We first explore the design spaces of seven state-of-the-art software switches and then compare their performance under four representative test scenarios. Each scenario corresponds to a specific case of routing NFV traffic between NICs and/or VNFs. In our experiments, we evaluate the throughput and latency between VNFs in two of the most popular virtualization environments, namely virtual machines (VMs) and containers. Our experimental results show that no single software switch prevails in all scenarios. It is, therefore, crucial to choose the most suitable solution for the given use case. At the same time, the presented results and analysis provide a deeper insight into the design tradeoffs and identifies potential performance bottlenecks that could inspire new designs.