OpenRaiser/Intern-Atlas huggingface dataset:
PassGAN: A Deep Learning Approach for Password Guessing
Venue: arXiv cs.CR 2019
Year: 2019

State-of-the-art password guessing tools, such as HashCat and John the Ripper, enable users to check billions of passwords per second against password hashes. In addition to performing straightforward dictionary attacks, these tools can expand password dictionaries using password generation rules, such as concatenation of words (e.g., "password123456") and leet speak (e.g., "password" becomes "p4s5w0rd"). Although these rules work well in practice, expanding them to model further passwords is a laborious task that requires specialized expertise. To address this issue, in this paper we introduce PassGAN, a novel approach that replaces human-generated password rules with theory-grounded machine learning algorithms. Instead of relying on manual password analysis, PassGAN uses a Generative Adversarial Network (GAN) to autonomously learn the distribution of real passwords from actual password leaks, and to generate high-quality password guesses. Our experiments show that this approach is very promising. When we evaluated PassGAN on two large password datasets, we were able to surpass rule-based and state-of-the-art machine learning password guessing tools. However, in contrast with the other tools, PassGAN achieved this result without any a-priori knowledge on passwords or common password structures. Additionally, when we combined the output of PassGAN with the output of HashCat, we were able to match 51%-73% more passwords than with HashCat alone. This is remarkable, because it shows that PassGAN can autonomously extract a considerable number of password properties that current state-of-the art rules do not encode.
Squeeze-and-Excitation Networks
Venue: arXiv cs.CV 2019
Year: 2019

The central building block of convolutional neural networks (CNNs) is the convolution operator, which enables networks to construct informative features by fusing both spatial and channel-wise information within local receptive fields at each layer. A broad range of prior research has investigated the spatial component of this relationship, seeking to strengthen the representational power of a CNN by enhancing the quality of spatial encodings throughout its feature hierarchy. In this work, we focus instead on the channel relationship and propose a novel architectural unit, which we term the "Squeeze-and-Excitation" (SE) block, that adaptively recalibrates channel-wise feature responses by explicitly modelling interdependencies between channels. We show that these blocks can be stacked together to form SENet architectures that generalise extremely effectively across different datasets. We further demonstrate that SE blocks bring significant improvements in performance for existing state-of-the-art CNNs at slight additional computational cost. Squeeze-and-Excitation Networks formed the foundation of our ILSVRC 2017 classification submission which won first place and reduced the top-5 error to 2.251%, surpassing the winning entry of 2016 by a relative improvement of ~25%. Models and code are available at https://github.com/hujie-frank/SENet.
Wyner's Common Information under Rényi Divergence Measures
Venue: arXiv cs.IT 2019
Year: 2019

We study a generalized version of Wyner's common information problem (also coined the distributed source simulation problem). The original common information problem consists in understanding the minimum rate of the common input to independent processors to generate an approximation of a joint distribution when the distance measure used to quantify the discrepancy between the synthesized and target distributions is the normalized relative entropy. Our generalization involves changing the distance measure to the unnormalized and normalized Rényi divergences of order $α=1+s\in[0,2]$. We show that the minimum rate needed to ensure the Rényi divergences between the distribution induced by a code and the target distribution vanishes remains the same as the one in Wyner's setting, except when the order $α=1+s=0$. This implies that Wyner's common information is rather robust to the choice of distance measure employed. As a byproduct of the proofs used to the establish the above results, the exponential strong converse for the common information problem under the total variation distance measure is established.
The Capacity of $T$-Private Information Retrieval with Private Side Information
Venue: arXiv cs.IT 2019
Year: 2019

We consider the problem of $T$-Private Information Retrieval with private side information (TPIR-PSI). In this problem, $N$ replicated databases store $K$ independent messages, and a user, equipped with a local cache that holds $M$ messages as side information, wishes to retrieve one of the other $K-M$ messages. The desired message index and the side information must remain jointly private even if any $T$ of the $N$ databases collude. We show that the capacity of TPIR-PSI is $\left(1+\frac{T}{N}+\cdots+\left(\frac{T}{N}\right)^{K-M-1}\right)^{-1}$. As a special case obtained by setting $T=1$, this result settles the capacity of PIR-PSI, an open problem previously noted by Kadhe et al. We also consider the problem of symmetric-TPIR with private side information (STPIR-PSI), where the answers from all $N$ databases reveal no information about any other message besides the desired message. We show that the capacity of STPIR-PSI is $1-\frac{T}{N}$ if the databases have access to common randomness (not available to the user) that is independent of the messages, in an amount that is at least $\frac{T}{N-T}$ bits per desired message bit. Otherwise, the capacity of STPIR-PSI is zero.
A Neural Network Architecture Combining Gated Recurrent Unit (GRU) and Support Vector Machine (SVM) for Intrusion Detection in Network Traffic Data
Venue: arXiv cs.NE 2019
Year: 2019

Gated Recurrent Unit (GRU) is a recently-developed variation of the long short-term memory (LSTM) unit, both of which are types of recurrent neural network (RNN). Through empirical evidence, both models have been proven to be effective in a wide variety of machine learning tasks such as natural language processing (Wen et al., 2015), speech recognition (Chorowski et al., 2015), and text classification (Yang et al., 2016). Conventionally, like most neural networks, both of the aforementioned RNN variants employ the Softmax function as its final output layer for its prediction, and the cross-entropy function for computing its loss. In this paper, we present an amendment to this norm by introducing linear support vector machine (SVM) as the replacement for Softmax in the final output layer of a GRU model. Furthermore, the cross-entropy function shall be replaced with a margin-based function. While there have been similar studies (Alalshekmubarak & Smith, 2013; Tang, 2013), this proposal is primarily intended for binary classification on intrusion detection using the 2013 network traffic data from the honeypot systems of Kyoto University. Results show that the GRU-SVM model performs relatively higher than the conventional GRU-Softmax model. The proposed model reached a training accuracy of ~81.54% and a testing accuracy of ~84.15%, while the latter was able to reach a training accuracy of ~63.07% and a testing accuracy of ~70.75%. In addition, the juxtaposition of these two final output layers indicate that the SVM would outperform Softmax in prediction time - a theoretical implication which was supported by the actual training and testing time in the study.
The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing: Extended Survey
Venue: arXiv cs.DB 2019
Year: 2019

Graph processing is becoming increasingly prevalent across many application domains. In spite of this prevalence, there is little research about how graphs are actually used in practice. We performed an extensive study that consisted of an online survey of 89 users, a review of the mailing lists, source repositories, and whitepapers of a large suite of graph software products, and in-person interviews with 6 users and 2 developers of these products. Our online survey aimed at understanding: (i) the types of graphs users have; (ii) the graph computations users run; (iii) the types of graph software users use; and (iv) the major challenges users face when processing their graphs. We describe the participants' responses to our questions highlighting common patterns and challenges. Based on our interviews and survey of the rest of our sources, we were able to answer some new questions that were raised by participants' responses to our online survey and understand the specific applications that use graph data and software. Our study revealed surprising facts about graph processing in practice. In particular, real-world graphs represent a very diverse range of entities and are often very large, scalability and visualization are undeniably the most pressing challenges faced by participants, and data integration, recommendations, and fraud detection are very popular applications supported by existing graph software. We hope these findings can guide future research.
Denoising Autoencoders for Overgeneralization in Neural Networks
Venue: arXiv cs.AI 2019
Year: 2019

Despite the recent developments that allowed neural networks to achieve impressive performance on a variety of applications, these models are intrinsically affected by the problem of overgeneralization, due to their partitioning of the full input space into the fixed set of target classes used during training. Thus it is possible for novel inputs belonging to categories unknown during training or even completely unrecognizable to humans to fool the system into classifying them as one of the known classes, even with a high degree of confidence. Solving this problem may help improve the security of such systems in critical applications, and may further lead to applications in the context of open set recognition and 1-class recognition. This paper presents a novel way to compute a confidence score using denoising autoencoders and shows that such confidence score can correctly identify the regions of the input space close to the training distribution by approximately identifying its local maxima.
Learning Ground Traversability from Simulations
Venue: arXiv cs.RO 2019
Year: 2019

Mobile ground robots operating on unstructured terrain must predict which areas of the environment they are able to pass in order to plan feasible paths. We address traversability estimation as a heightmap classification problem: we build a convolutional neural network that, given an image representing the heightmap of a terrain patch, predicts whether the robot will be able to traverse such patch from left to right. The classifier is trained for a specific robot model (wheeled, tracked, legged, snake-like) using simulation data on procedurally generated training terrains; the trained classifier can be applied to unseen large heightmaps to yield oriented traversability maps, and then plan traversable paths. We extensively evaluate the approach in simulation on six real-world elevation datasets, and run a real-robot validation in one indoor and one outdoor environment.
Keeping Context In Mind: Automating Mobile App Access Control with User Interface Inspection
Venue: arXiv cs.CR 2019
Year: 2019

Recent studies observe that app foreground is the most striking component that influences the access control decisions in mobile platform, as users tend to deny permission requests lacking visible evidence. However, none of the existing permission models provides a systematic approach that can automatically answer the question: Is the resource access indicated by app foreground? In this work, we present the design, implementation, and evaluation of COSMOS, a context-aware mediation system that bridges the semantic gap between foreground interaction and background access, in order to protect system integrity and user privacy. Specifically, COSMOS learns from a large set of apps with similar functionalities and user interfaces to construct generic models that detect the outliers at runtime. It can be further customized to satisfy specific user privacy preference by continuously evolving with user decisions. Experiments show that COSMOS achieves both high precision and high recall in detecting malicious requests. We also demonstrate the effectiveness of COSMOS in capturing specific user preferences using the decisions collected from 24 users and illustrate that COSMOS can be easily deployed on smartphones as a real-time guard with a very low performance overhead.
Drawing Graphs on Few Circles and Few Spheres
Venue: arXiv cs.CG 2019
Year: 2019

Given a drawing of a graph, its \emph{visual complexity} is defined as the number of geometrical entities in the drawing, for example, the number of segments in a straight-line drawing or the number of arcs in a circular-arc drawing (in 2D). Recently, Chaplick et al. [GD 2016] introduced a different measure for the visual complexity, the \emph{affine cover number}, which is the minimum number of lines (or planes) that together cover a crossing-free straight-line drawing of a graph $G$ in 2D (3D). In this paper, we introduce the \emph{spherical cover number}, which is the minimum number of circles (or spheres) that together cover a crossing-free circular-arc drawing in 2D (or 3D). It turns out that spherical covers are sometimes significantly smaller than affine covers. Moreover, there are highly symmetric graphs that have symmetric optimum spherical covers but apparently no symmetric optimum affine cover. For complete, complete bipartite, and platonic graphs, we analyze their spherical cover numbers and compare them to their affine cover numbers as well as their segment and arc numbers. We also link the spherical cover number to other graph parameters such as chromatic number, treewidth, and linear arboricity.
Agile Autonomous Driving using End-to-End Deep Imitation Learning
Venue: arXiv cs.RO 2019
Year: 2019

We present an end-to-end imitation learning system for agile, off-road autonomous driving using only low-cost sensors. By imitating a model predictive controller equipped with advanced sensors, we train a deep neural network control policy to map raw, high-dimensional observations to continuous steering and throttle commands. Compared with recent approaches to similar tasks, our method requires neither state estimation nor on-the-fly planning to navigate the vehicle. Our approach relies on, and experimentally validates, recent imitation learning theory. Empirically, we show that policies trained with online imitation learning overcome well-known challenges related to covariate shift and generalize better than policies trained with batch imitation learning. Built on these insights, our autonomous driving system demonstrates successful high-speed off-road driving, matching the state-of-the-art performance.
GP-SUM. Gaussian Processes Filtering of non-Gaussian Beliefs
Venue: arXiv cs.RO 2019
Year: 2019

This work studies the problem of stochastic dynamic filtering and state propagation with complex beliefs. The main contribution is GP-SUM, a filtering algorithm tailored to dynamic systems and observation models expressed as Gaussian Processes (GP), and to states represented as a weighted sum of Gaussians. The key attribute of GP-SUM is that it does not rely on linearizations of the dynamic or observation models, or on unimodal Gaussian approximations of the belief, hence enables tracking complex state distributions. The algorithm can be seen as a combination of a sampling-based filter with a probabilistic Bayes filter. On the one hand, GP-SUM operates by sampling the state distribution and propagating each sample through the dynamic system and observation models. On the other hand, it achieves effective sampling and accurate probabilistic propagation by relying on the GP form of the system, and the sum-of-Gaussian form of the belief. We show that GP-SUM outperforms several GP-Bayes and Particle Filters on a standard benchmark. We also demonstrate its use in a pushing task, predicting with experimental accuracy the naturally occurring non-Gaussian distributions.
Multi-Rack Distributed Data Storage Networks
Venue: arXiv cs.IT 2019
Year: 2019

The majority of works in distributed storage networks assume a simple network model with a collection of identical storage nodes with the same communication cost between the nodes. In this paper, we consider a realistic multi-rack distributed data storage network and present a code design framework for this model. Considering the cheaper data transmission within the racks, our code construction method is able to locally repair the nodes failure within the same rack by using only the survived nodes in the same rack. However, in the case of severe failure patterns when the information content of the survived nodes is not sufficient to repair the failures, other racks will participate in the repair process. By employing the criteria of our multi-rack storage code, we establish a linear programming bound on the size of the code in order to maximize the code rate.
Colored fused filament fabrication
Venue: arXiv cs.CG 2019
Year: 2019

Fused filament fabrication is the method of choice for printing 3D models at low cost and is the de-facto standard for hobbyists, makers, and schools. Unfortunately, filament printers cannot truly reproduce colored objects. The best current techniques rely on a form of dithering exploiting occlusion, that was only demonstrated for shades of two base colors and that behaves differently depending on surface slope. We explore a novel approach for 3D printing colored objects, capable of creating controlled gradients of varying sharpness. Our technique exploits off-the-shelves nozzles that are designed to mix multiple filaments in a small melting chamber, obtaining intermediate colors once the mix is stabilized. We apply this property to produce color gradients. We divide each input layer into a set of strata, each having a different constant color. By locally changing the thickness of the stratum, we change the perceived color at a given location. By optimizing the choice of colors of each stratum, we further improve quality and allow the use of different numbers of input filaments. We demonstrate our results by building a functional color printer using low cost, off-the-shelves components. Using our tool a user can paint a 3D model and directly produce its physical counterpart, using any material and color available for fused filament fabrication.
Colonel Blotto Game for Secure State Estimation in Interdependent Critical Infrastructure
Venue: arXiv cs.SY 2019
Year: 2019

Securing the physical components of a city's interdependent critical infrastructure (ICI) such as power, natural gas, and water systems is a challenging task due to their interdependence and a large number of involved sensors. In this paper, using a novel integrated state-space model that captures the interdependence, a two-stage cyber attack on an ICI is studied in which the attacker first compromises the ICI's sensors by decoding their messages, and, subsequently, it alters the compromised sensors' data to cause state estimation errors. To thwart such attacks, the administrator of each critical infrastructure (CI) must assign protection levels to the sensors based on their importance in the state estimation process. To capture the interdependence between the attacker and the ICI administrator's actions and analyze their interactions, a Colonel Blotto game framework is proposed. The mixed-strategy Nash equilibrium of this game is derived analytically. At this equilibrium, it is shown that the administrator can strategically randomize between the protection levels of the sensors to deceive the attacker. Simulation results coupled with theoretical analysis show that, using the proposed game, the administrator can reduce the state estimation error by at least $ 50\% $ compared to a non-strategic approach that assigns protection levels proportional to sensor values.
Distributions of Centrality on Networks
Venue: arXiv cs.SI 2019
Year: 2019

We provide a framework for determining the centralities of agents in a broad family of random networks. Current understanding of network centrality is largely restricted to deterministic settings, but practitioners frequently use random network models to accommodate data limitations or prove asymptotic results. Our main theorems show that on large random networks, centrality measures are close to their expected values with high probability. We illustrate the economic consequences of these results by presenting three applications: (1) In network formation models based on community structure (called stochastic block models), we show network segregation and differences in community size produce inequality. Benefits from peer effects tend to accrue disproportionately to bigger and better-connected communities. (2) When link probabilities depend on geography, we can compute and compare the centralities of agents in different locations. (3) In models where connections depend on several independent characteristics, we give a formula that determines centralities 'characteristic-by-characteristic'. The basic techniques from these applications, which use the main theorems to reduce questions about random networks to deterministic calculations, extend to many network games.
ObliDB: Oblivious Query Processing for Secure Databases
Venue: arXiv cs.CR 2019
Year: 2019

Hardware enclaves such as Intel SGX are a promising technology for improving the security of databases outsourced to the cloud. These enclaves provide an execution environment isolated from the hypervisor/OS, and encrypt data in RAM. However, for applications that use large amounts of memory, including most databases, enclaves do not protect against access pattern leaks, which let attackers gain a large amount of information about the data. Moreover,the naive way to address this issue, using Oblivious RAM (ORAM) primitives from the security literature, adds substantial overhead. A number of recent works explore trusted hardware enclaves as a path toward secure, access-pattern oblivious outsourcing of data storage and analysis. While these works efficiently solve specific subproblems (e.g. building secure indexes or running analytics queries that always scan entire tables), no prior work has supported oblivious query processing for general query workloads on a DBMS engine with multiple access methods. Moreover, applying these techniques individually does not guarantee that an end-to-end workload, such as a complex SQL query over multiple tables, will be oblivious. In this paper, we introduce ObliDB, an oblivious database engine design that is the first system to provide obliviousness for general database read workloads over multiple access methods. ObliDB supports a broad range of queries, including aggregation, joins, insertions, deletions and point queries. We implement ObliDB and show that, on analytics work-loads, ObliDB ranges from 1.1-19x faster than Opaque,a previous oblivious, enclave-based system designed only for analytics, and comes within 2.6x of Spark SQL. ObliDB supports point queries with 3-10ms latency, which runs over 7x faster than HIRB, a previous encryption-based oblivious index system.