OpenRaiser/Intern-Atlas huggingface dataset:
FastSpec: Scalable Generation and Detection of Spectre Gadgets Using Neural Embeddings
Venue: arXiv cs.CR 2021
Year: 2021

Several techniques have been proposed to detect vulnerable Spectre gadgets in widely deployed commercial software. Unfortunately, detection techniques proposed so far rely on hand-written rules which fall short in covering subtle variations of known Spectre gadgets as well as demand a huge amount of time to analyze each conditional branch in software. Moreover, detection tool evaluations are based only on a handful of these gadgets, as it requires arduous effort to craft new gadgets manually. In this work, we employ both fuzzing and deep learning techniques to automate the generation and detection of Spectre gadgets. We first create a diverse set of Spectre-V1 gadgets by introducing perturbations to the known gadgets. Using mutational fuzzing, we produce a data set with more than 1 million Spectre-V1 gadgets which is the largest Spectre gadget data set built to date. Next, we conduct the first empirical usability study of Generative Adversarial Networks (GANs) in the context of assembly code generation without any human interaction. We introduce SpectreGAN which leverages masking implementation of GANs for both learning the gadget structures and generating new gadgets. This provides the first scalable solution to extend the variety of Spectre gadgets. Finally, we propose FastSpec which builds a classifier with the generated Spectre gadgets based on a novel high dimensional Neural Embeddings technique (BERT). For the case studies, we demonstrate that FastSpec discovers potential gadgets with a high success rate in OpenSSL libraries and Phoronix benchmarks. Further, FastSpec offers much greater flexibility and time-related performance gain compared to the existing tools and therefore can be used for gadget detection in large-scale software.
A Canonical Transform for Strengthening the Local $L^p$-Type Universal Approximation Property
Venue: arXiv cs.LG 2021
Year: 2021

Most $L^p$-type universal approximation theorems guarantee that a given machine learning model class $\mathscr{F}\subseteq C(\mathbb{R}^d,\mathbb{R}^D)$ is dense in $L^p_μ(\mathbb{R}^d,\mathbb{R}^D)$ for any suitable finite Borel measure $μ$ on $\mathbb{R}^d$. Unfortunately, this means that the model's approximation quality can rapidly degenerate outside some compact subset of $\mathbb{R}^d$, as any such measure is largely concentrated on some bounded subset of $\mathbb{R}^d$. This paper proposes a generic solution to this approximation theoretic problem by introducing a canonical transformation which "upgrades $\mathscr{F}$'s approximation property" in the following sense. The transformed model class, denoted by $\mathscr{F}\text{-tope}$, is shown to be dense in $L^p_{μ,\text{strict}}(\mathbb{R}^d,\mathbb{R}^D)$ which is a topological space whose elements are locally $p$-integrable functions and whose topology is much finer than usual norm topology on $L^p_μ(\mathbb{R}^d,\mathbb{R}^D)$; here $μ$ is any suitable $σ$-finite Borel measure $μ$ on $\mathbb{R}^d$. Next, we show that if $\mathscr{F}$ is any family of analytic functions then there is always a strict "gap" between $\mathscr{F}\text{-tope}$'s expressibility and that of $\mathscr{F}$, since we find that $\mathscr{F}$ can never dense in $L^p_{μ,\text{strict}}(\mathbb{R}^d,\mathbb{R}^D)$. In the general case, where $\mathscr{F}$ may contain non-analytic functions, we provide an abstract form of these results guaranteeing that there always exists some function space in which $\mathscr{F}\text{-tope}$ is dense but $\mathscr{F}$ is not, while, the converse is never possible. Applications to feedforward networks, convolutional neural networks, and polynomial bases are explored.
APX-Hardness and Approximation for the k-Burning Number Problem
Venue: arXiv cs.CC 2021
Year: 2021

Consider an information diffusion process on a graph $G$ that starts with $k>0$ burnt vertices, and at each subsequent step, burns the neighbors of the currently burnt vertices, as well as $k$ other unburnt vertices. The \emph{$k$-burning number} of $G$ is the minimum number of steps $b_k(G)$ such that all the vertices can be burned within $b_k(G)$ steps. Note that the last step may have smaller than $k$ unburnt vertices available, where all of them are burned. The $1$-burning number coincides with the well-known burning number problem, which was proposed to model the spread of social contagion. The generalization to $k$-burning number allows us to examine different worst-case contagion scenarios by varying the spread factor $k$. In this paper we prove that computing $k$-burning number is APX-hard, for any fixed constant $k$. We then give an $O((n+m)\log n)$-time 3-approximation algorithm for computing $k$-burning number, for any $k\ge 1$, where $n$ and $m$ are the number of vertices and edges, respectively. Finally, we show that even if the burning sources are given as an input, computing a burning sequence itself is an NP-hard problem.
AvE: Assistance via Empowerment
Venue: arXiv cs.AI 2021
Year: 2021

One difficulty in using artificial agents for human-assistive applications lies in the challenge of accurately assisting with a person's goal(s). Existing methods tend to rely on inferring the human's goal, which is challenging when there are many potential goals or when the set of candidate goals is difficult to identify. We propose a new paradigm for assistance by instead increasing the human's ability to control their environment, and formalize this approach by augmenting reinforcement learning with human empowerment. This task-agnostic objective preserves the person's autonomy and ability to achieve any eventual state. We test our approach against assistance based on goal inference, highlighting scenarios where our method overcomes failure modes stemming from goal ambiguity or misspecification. As existing methods for estimating empowerment in continuous domains are computationally hard, precluding its use in real time learned assistance, we also propose an efficient empowerment-inspired proxy metric. Using this, we are able to successfully demonstrate our method in a shared autonomy user study for a challenging simulated teleoperation task with human-in-the-loop training.
Not all Failure Modes are Created Equal: Training Deep Neural Networks for Explicable (Mis)Classification
Venue: arXiv cs.LG 2021
Year: 2021

Deep Neural Networks are often brittle on image classification tasks and known to misclassify inputs. While these misclassifications may be inevitable, all failure modes cannot be considered equal. Certain misclassifications (eg. classifying the image of a dog to an airplane) can perplex humans and result in the loss of human trust in the system. Even worse, these errors (eg. a person misclassified as a primate) can have odious societal impacts. Thus, in this work, we aim to reduce inexplicable errors. To address this challenge, we first discuss methods to obtain the class-level semantics that capture the human's expectation ($M^h$) regarding which classes are semantically close {\em vs.} ones that are far away. We show that for popular image benchmarks (like CIFAR-10, CIFAR-100, ImageNet), class-level semantics can be readily obtained by leveraging either human subject studies or publicly available human-curated knowledge bases. Second, we propose the use of Weighted Loss Functions (WLFs) to penalize misclassifications by the weight of their inexplicability. Finally, we show that training (or fine-tuning) existing classifiers with the proposed methods lead to Deep Neural Networks that have (1) comparable top-1 accuracy, (2) more explicable failure modes on both in-distribution and out-of-distribution (OOD) test data, and (3) incur significantly less cost in the gathering of additional human labels compared to existing works.
MMF: A loss extension for feature learning in open set recognition
Venue: arXiv cs.LG 2021
Year: 2021

Open set recognition (OSR) is the problem of classifying the known classes, meanwhile identifying the unknown classes when the collected samples cannot exhaust all the classes. There are many applications for the OSR problem. For instance, the frequently emerged new malware classes require a system that can classify the known classes and identify the unknown malware classes. In this paper, we propose an add-on extension for loss functions in neural networks to address the OSR problem. Our loss extension leverages the neural network to find polar representations for the known classes so that the representations of the known and the unknown classes become more effectively separable. Our contributions include: First, we introduce an extension that can be incorporated into different loss functions to find more discriminative representations. Second, we show that the proposed extension can significantly improve the performances of two different types of loss functions on datasets from two different domains. Third, we show that with the proposed extension, one loss function outperforms the others in terms of training time and model accuracy.
State Complexity of Permutation and Related Decision Problems on Alphabetical Pattern Constraints
Venue: arXiv cs.FL 2021
Year: 2021

We investigate the state complexity of the permutation operation, or the commutative closure, on Alphabetical Pattern Constraints (APC). This class corresponds to level $3/2$ of the Straubing-Th{é}rien Hierarchy and includes the finite, the piecewise-testable, or $\mathcal J$-trivial, and the $\mathcal R$-trivial and $\mathcal L$-trivial languages. We give a sharp state complexity bound expressed in terms of the longest strings in the unary projection languages of an associated finite language and which is already sharp for the subclass of finite languages. Additionally, for two subclasses, we give sharp bounds expressed in terms of the size of a recognizing input automaton and the size of the alphabet. Lastly, we investigate the inclusion and universality problem on APCs up to permutational equivalence, two problems known to be PSPACE-complete on APCs even for fixed alphabets in general, and show them to be decidable in polynomial time for fixed alphabets in this case.
Traditional and accelerated gradient descent for neural architecture search
Venue: arXiv cs.LG 2021
Year: 2021

In this paper we introduce two algorithms for neural architecture search (NASGD and NASAGD) following the theoretical work by two of the authors [5] which used the geometric structure of optimal transport to introduce the conceptual basis for new notions of traditional and accelerated gradient descent algorithms for the optimization of a function on a semi-discrete space. Our algorithms, which use the network morphism framework introduced in [2] as a baseline, can analyze forty times as many architectures as the hill climbing methods [2, 14] while using the same computational resources and time and achieving comparable levels of accuracy. For example, using NASGD on CIFAR-10, our method designs and trains networks with an error rate of 4.06 in only 12 hours on a single GPU.
Symbol-Level Precoding Made Practical for Multi-Level Modulations via Block-Level Rescaling
Venue: arXiv cs.IT 2021
Year: 2021

In this paper, we propose an interference exploitation symbol-level precoding (SLP) method for multi-level modulations via an in-block power allocation scheme to greatly reduce the signaling overhead. Existing SLP approaches require the symbol-level broadcast of the rescaling factor to the users for correct demodulation, which hinders the practical implementation of SLP. The proposed approach allows a block-level broadcast of the rescaling factor as done in traditional block-level precoding, greatly reducing the signaling overhead for SLP without sacrificing the performance. Our derivations further show that the proposed in-block power allocation enjoys an exact closed-form solution and thus does not increase the complexity at the base station (BS). In addition to the significant alleviation of the signaling overhead validated by the effective throughput result, numerical results demonstrate that the proposed power allocation approach also improves the error-rate performance of the existing SLP. Accordingly, the proposed approach enables the practical use of SLP in multi-level modulations.
Evolving Metric Learning for Incremental and Decremental Features
Venue: arXiv cs.LG 2021
Year: 2021

Online metric learning has been widely exploited for large-scale data classification due to the low computational cost. However, amongst online practical scenarios where the features are evolving (e.g., some features are vanished and some new features are augmented), most metric learning models cannot be successfully applied to these scenarios, although they can tackle the evolving instances efficiently. To address the challenge, we develop a new online Evolving Metric Learning (EML) model for incremental and decremental features, which can handle the instance and feature evolutions simultaneously by incorporating with a smoothed Wasserstein metric distance. Specifically, our model contains two essential stages: a Transforming stage (T-stage) and a Inheriting stage (I-stage). For the T-stage, we propose to extract important information from vanished features while neglecting non-informative knowledge, and forward it into survived features by transforming them into a low-rank discriminative metric space. It further explores the intrinsic low-rank structure of heterogeneous samples to reduce the computation and memory burden especially for highly-dimensional large-scale data. For the I-stage, we inherit the metric performance of survived features from the T-stage and then expand to include the new augmented features. Moreover, a smoothed Wasserstein distance is utilized to characterize the similarity relationships among the heterogeneous and complex samples, since the evolving features are not strictly aligned in the different stages. In addition to tackling the challenges in one-shot case, we also extend our model into multishot scenario. After deriving an efficient optimization strategy for both T-stage and I-stage, extensive experiments on several datasets verify the superior performance of our EML model.
VPNet: Variable Projection Networks
Venue: arXiv cs.LG 2021
Year: 2021

We introduce VPNet, a novel model-driven neural network architecture based on variable projection (VP). Applying VP operators to neural networks results in learnable features, interpretable parameters, and compact network structures. This paper discusses the motivation and mathematical background of VPNet and presents experiments. The VPNet approach was evaluated in the context of signal processing, where we classified a synthetic dataset and real electrocardiogram (ECG) signals. Compared to fully connected and one-dimensional convolutional networks, VPNet offers fast learning ability and good accuracy at a low computational cost of both training and inference. Based on these advantages and the promising results obtained, we anticipate a profound impact on the broader field of signal processing, in particular on classification, regression and clustering problems.
Geometry-Inspired Top-k Adversarial Perturbations
Venue: arXiv cs.CV 2021
Year: 2021

The brittleness of deep image classifiers to small adversarial input perturbations has been extensively studied in the last several years. However, the main objective of existing perturbations is primarily limited to change the correctly predicted Top-1 class by an incorrect one, which does not intend to change the Top-k prediction. In many digital real-world scenarios Top-k prediction is more relevant. In this work, we propose a fast and accurate method of computing Top-k adversarial examples as a simple multi-objective optimization. We demonstrate its efficacy and performance by comparing it to other adversarial example crafting techniques. Moreover, based on this method, we propose Top-k Universal Adversarial Perturbations, image-agnostic tiny perturbations that cause the true class to be absent among the Top-k prediction for the majority of natural images. We experimentally show that our approach outperforms baseline methods and even improves existing techniques of finding Universal Adversarial Perturbations.
Lachesis: Automatic Partitioning for UDF-Centric Analytics
Venue: arXiv cs.DB 2021
Year: 2021

Persistent partitioning is effective in avoiding expensive shuffling operations. However it remains a significant challenge to automate this process for Big Data analytics workloads that extensively use user defined functions (UDFs), where sub-computations are hard to be reused for partitionings compared to relational applications. In addition, functional dependency that is widely utilized for partitioning selection is often unavailable in the unstructured data that is ubiquitous in UDF-centric analytics. We propose the Lachesis system, which represents UDF-centric workloads as workflows of analyzable and reusable sub-computations. Lachesis further adopts a deep reinforcement learning model to infer which sub-computations should be used to partition the underlying data. This analysis is then applied to automatically optimize the storage of the data across applications to improve the performance and users' productivity.
On the Fundamental Limits of Coded Caching Systems with Restricted Demand Types
Venue: arXiv cs.IT 2021
Year: 2021

Caching is a technique to reduce the communication load in peak hours by prefetching contents during off-peak hours. An information-theoretic framework for coded caching was introduced by Maddah-Ali and Niesen in a recent work, where it was shown that significant improvement can be obtained compared to uncoded caching. Considerable efforts have been devoted to identify the precise information-theoretic fundamental limits of the coded caching systems, however the difficulty of this task has also become clear. One of the reasons for this difficulty is that the original coded caching setting allows all possible multiple demand types during delivery, which in fact introduces tension in the coding strategy. In this paper, we seek to develop a better understanding of the fundamental limits of coded caching by investigating systems with certain demand type restrictions. We first consider the canonical three-user three-file system, and show that, contrary to popular beliefs, the worst demand type is not the one in which all three files are requested. Motivated by these findings, we focus on coded caching systems where every file must be requested by at least one user. A novel coding scheme is proposed, which can provide new operating points that are not covered by any previously known schemes.
Statistical Mechanical Analysis of Neural Network Pruning
Venue: arXiv cs.LG 2021
Year: 2021

Deep learning architectures with a huge number of parameters are often compressed using pruning techniques to ensure computational efficiency of inference during deployment. Despite multitude of empirical advances, there is a lack of theoretical understanding of the effectiveness of different pruning methods. We inspect different pruning techniques under the statistical mechanics formulation of a teacher-student framework and derive their generalization error (GE) bounds. It has been shown that Determinantal Point Process (DPP) based node pruning method is notably superior to competing approaches when tested on real datasets. Using GE bounds in the aforementioned setup we provide theoretical guarantees for their empirical observations. Another consistent finding in literature is that sparse neural networks (edge pruned) generalize better than dense neural networks (node pruned) for a fixed number of parameters. We use our theoretical setup to prove this finding and show that even the baseline random edge pruning method performs better than the DPP node pruning method. We also validate this empirically on real datasets.
Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2
Venue: arXiv cs.CC 2021
Year: 2021

We study the problem of computing the parity of the number of homomorphisms from an input graph $G$ to a fixed graph $H$. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class $\oplus\mathrm{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on $4$ vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\oplus\mathrm{P}$-complete cases, assuming the randomised Exponential Time Hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph $H$. Using this, we subsume all prior progress towards resolving the conjecture (Faben and Jerrum [ToC'15]; Göbel, Goldberg and Richerby [ToCT'14,'16]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most $3$, as well as a full classification for the problem of counting list homomorphisms, modulo $2$.
FairRec: Fairness-aware News Recommendation with Decomposed Adversarial Learning
Venue: arXiv cs.IR 2021
Year: 2021

News recommendation is important for online news services. Existing news recommendation models are usually learned from users' news click behaviors. Usually the behaviors of users with the same sensitive attributes (e.g., genders) have similar patterns and news recommendation models can easily capture these patterns. It may lead to some biases related to sensitive user attributes in the recommendation results, e.g., always recommending sports news to male users, which is unfair since users may not receive diverse news information. In this paper, we propose a fairness-aware news recommendation approach with decomposed adversarial learning and orthogonality regularization, which can alleviate unfairness in news recommendation brought by the biases of sensitive user attributes. In our approach, we propose to decompose the user interest model into two components. One component aims to learn a bias-aware user embedding that captures the bias information on sensitive user attributes, and the other aims to learn a bias-free user embedding that only encodes attribute-independent user interest information for fairness-aware news recommendation. In addition, we propose to apply an attribute prediction task to the bias-aware user embedding to enhance its ability on bias modeling, and we apply adversarial learning to the bias-free user embedding to remove the bias information from it. Moreover, we propose an orthogonality regularization method to encourage the bias-free user embeddings to be orthogonal to the bias-aware one to better distinguish the bias-free user embedding from the bias-aware one. For fairness-aware news ranking, we only use the bias-free user embedding. Extensive experiments on benchmark dataset show that our approach can effectively improve fairness in news recommendation with minor performance loss.