OpenRaiser/Intern-Atlas huggingface dataset:
Provably Robust Adversarial Examples
Venue: arXiv cs.LG 2022
Year: 2022

We introduce the concept of provably robust adversarial examples for deep neural networks - connected input regions constructed from standard adversarial examples which are guaranteed to be robust to a set of real-world perturbations (such as changes in pixel intensity and geometric transformations). We present a novel method called PARADE for generating these regions in a scalable manner which works by iteratively refining the region initially obtained via sampling until a refined region is certified to be adversarial with existing state-of-the-art verifiers. At each step, a novel optimization procedure is applied to maximize the region's volume under the constraint that the convex relaxation of the network behavior with respect to the region implies a chosen bound on the certification objective. Our experimental evaluation shows the effectiveness of PARADE: it successfully finds large provably robust regions including ones containing $\approx 10^{573}$ adversarial examples for pixel intensity and $\approx 10^{599}$ for geometric perturbations. The provability enables our robust examples to be significantly more effective against state-of-the-art defenses based on randomized smoothing than the individual attacks used to construct the regions.
Energy-aware Relay Positioning in Flying Networks
Venue: arXiv cs.NI 2022
Year: 2022

The ability to move and hover has made rotary-wing Unmanned Aerial Vehicles (UAVs) suitable platforms to act as Flying Communications Relays (FCR), aiming at providing on-demand, temporary wireless connectivity when there is no network infrastructure available or a need to reinforce the capacity of existing networks. However, since UAVs rely on their on-board batteries, which can be drained quickly, they typically need to land frequently for recharging or replacing them, limiting their endurance and the flying network availability. The problem is exacerbated when a single FCR UAV is used. The FCR UAV energy is used for two main tasks: communications and propulsion. The literature has been focused on optimizing both the flying network performance and energy-efficiency from the communications point of view, overlooking the energy spent for the UAV propulsion. Yet, the energy spent for communications is typically negligible when compared with the energy spent for the UAV propulsion. In this article we propose Energy-aware RElay Positioning (EREP), an algorithm for positioning the FCR taking into account the energy spent for the UAV propulsion. Building upon the conclusion that hovering is not the most energy-efficient state, EREP defines the trajectory and speed that minimize the energy spent by the FCR UAV on propulsion, without compromising in practice the Quality of Service offered by the flying network. The EREP algorithm is evaluated using simulations. The obtained results show gains up to 26% in the FCR UAV endurance for negligible throughput and delay degradation.
Multi-Level Local SGD for Heterogeneous Hierarchical Networks
Venue: arXiv cs.LG 2022
Year: 2022

We propose Multi-Level Local SGD, a distributed gradient method for learning a smooth, non-convex objective in a heterogeneous multi-level network. Our network model consists of a set of disjoint sub-networks, with a single hub and multiple worker nodes; further, worker nodes may have different operating rates. The hubs exchange information with one another via a connected, but not necessarily complete communication network. In our algorithm, sub-networks execute a distributed SGD algorithm, using a hub-and-spoke paradigm, and the hubs periodically average their models with neighboring hubs. We first provide a unified mathematical framework that describes the Multi-Level Local SGD algorithm. We then present a theoretical analysis of the algorithm; our analysis shows the dependence of the convergence error on the worker node heterogeneity, hub network topology, and the number of local, sub-network, and global iterations. We back up our theoretical results via simulation-based experiments using both convex and non-convex objectives.
Deep Multi-Scale Resemblance Network for the Sub-class Differentiation of Adrenal Masses on Computed Tomography Images
Venue: arXiv cs.CV 2022
Year: 2022

The accurate classification of mass lesions in the adrenal glands (adrenal masses), detected with computed tomography (CT), is important for diagnosis and patient management. Adrenal masses can be benign or malignant and benign masses have varying prevalence. Classification methods based on convolutional neural networks (CNNs) are the state-of-the-art in maximizing inter-class differences in large medical imaging training datasets. The application of CNNs, to adrenal masses is challenging due to large intra-class variations, large inter-class similarities and imbalanced training data due to the size of the mass lesions. We developed a deep multi-scale resemblance network (DMRN) to overcome these limitations and leveraged paired CNNs to evaluate the intra-class similarities. We used multi-scale feature embedding to improve the inter-class separability by iteratively combining complementary information produced at different scales of the input to create structured feature descriptors. We augmented the training data with randomly sampled paired adrenal masses to reduce the influence of imbalanced training data. We used 229 CT scans of patients with adrenal masses for evaluation. In a five-fold cross-validation, our method had the best results (89.52% in accuracy) when compared to the state-of-the-art methods (p<0.05). We conducted a generalizability analysis of our method on the ImageCLEF 2016 competition dataset for medical subfigure classification, which consists of a training set of 6,776 images and a test set of 4,166 images across 30 classes. Our method achieved better classification performance (85.90% in accuracy) when compared to the existing methods and was competitive when compared with methods that require additional training data (1.47% lower in accuracy). Our DMRN sub-classified adrenal masses on CT and was superior to state-of-the-art approaches.
Dynamic Defense Against Byzantine Poisoning Attacks in Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning, as a distributed learning that conducts the training on the local devices without accessing to the training data, is vulnerable to Byzatine poisoning adversarial attacks. We argue that the federated learning model has to avoid those kind of adversarial attacks through filtering out the adversarial clients by means of the federated aggregation operator. We propose a dynamic federated aggregation operator that dynamically discards those adversarial clients and allows to prevent the corruption of the global learning model. We assess it as a defense against adversarial attacks deploying a deep learning classification model in a federated learning setting on the Fed-EMNIST Digits, Fashion MNIST and CIFAR-10 image datasets. The results show that the dynamic selection of the clients to aggregate enhances the performance of the global learning model and discards the adversarial and poor (with low quality models) clients.
Sybil-Resilient Coin Minting
Venue: arXiv cs.SI 2022
Year: 2022

We describe a distributed coin minting protocol that mints one coin per time unit for each member in a digital community. The protocol assumes that community members use a trust-graph to determine the genuineness of digital identities, and that doing so bounds the number of sybils (fake or duplicate identities) in the community, but does not completely eliminate them. The main goal of the protocol is to be resilient to the sybils that penetrate the community, in the sense that, in the long run, only genuine identities mint coins. The protocol accepts that sybils penetrate the community from time to time (by gaining enough trust within the trust-graph), yet assumes that every sybil is eventually exposed. Since coins minted by a sybil will most probably circulate by the time it is exposed, the protocol puts the responsibility for introducing a sybil onto its trusting neighbours and confiscates subsequent coins minted by them, until the coins minted by that sybil are accounted for. In particular, the protocol confiscates two coins for each coin minted by the sybil: one to recover what was wrongly minted and one as a fine for introducing the sybil in the first place. We argue that this approach constitutes a mechanism to deter the introduction of sybils into the community and to incentivize sybil hunting (using part of the confiscated money as a reward).
Imitative Planning using Conditional Normalizing Flow
Venue: arXiv cs.RO 2022
Year: 2022

A popular way to plan trajectories in dynamic urban scenarios for Autonomous Vehicles is to rely on explicitly specified and hand crafted cost functions, coupled with random sampling in the trajectory space to find the minimum cost trajectory. Such methods require a high number of samples to find a low-cost trajectory and might end up with a highly suboptimal trajectory given the planning time budget. We explore the application of normalizing flows for improving the performance of trajectory planning for autonomous vehicles (AVs). Our key insight is to learn a sampling policy in a low-dimensional latent space of expert-like trajectories, out of which the best sample is selected for execution. By modeling the trajectory planner's cost manifold as an energy function, we learn a scene conditioned mapping from the prior to a Boltzmann distribution over the AV control space. Finally, we demonstrate the effectiveness of our approach on real-world datasets over IL and hand-constructed trajectory sampling techniques.
CROSSLINE: Breaking "Security-by-Crash" based Memory Isolation in AMD SEV
Venue: arXiv cs.CR 2022
Year: 2022

AMD's Secure Encrypted Virtualization (SEV) is an emerging security feature on AMD processors that allows virtual machines to run on encrypted memory and perform confidential computing even with an untrusted hypervisor. This paper first demystifies SEV's improper use of address space identifier (ASID) for controlling accesses of a VM to encrypted memory pages, cache lines, and TLB entries. We then present the CROSSLINE attacks, a novel class of attacks against SEV that allow the adversary to launch an attacker VM and change its ASID to that of the victim VM to impersonate the victim. We present two variants of CROSSLINE attacks: CROSSLINE V1 decrypts victim's page tables or memory blocks following the format of a page table entry; CROSSLINE V2 constructs encryption and decryption oracles by executing instructions of the victim VM. We have successfully performed CROSSLINE attacks on SEV and SEV-ES processors.
The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures
Venue: arXiv cs.CR 2022
Year: 2022

The concept of learned index structures relies on the idea that the input-output functionality of a database index can be viewed as a prediction task and, thus, be implemented using a machine learning model instead of traditional algorithmic techniques. This novel angle for a decades-old problem has inspired numerous exciting results in the intersection of machine learning and data structures. However, the main advantage of learned index structures, i.e., the ability to adjust to the data at hand via the underlying ML-model, can become a disadvantage from a security perspective as it could be exploited. In this work, we present the first study of poisoning attacks on learned index structures. The required poisoning approach is different from all previous works since the model under attack is trained on a cumulative distribution function (CDF) and, thus, every injection on the training set has a cascading impact on multiple data values. We formulate the first poisoning attacks on linear regression models trained on the CDF, which is a basic building block of the proposed learned index structures. We generalize our poisoning techniques to attack a more advanced two-stage design of learned index structures called recursive model index (RMI), which has been shown to outperform traditional B-Trees. We evaluate our attacks on real-world and synthetic datasets under a wide variety of parameterizations of the model and show that the error of the RMI increases up to $300\times$ and the error of its second-stage models increases up to $3000\times$.
Distributed Dispatching in the Parallel Server Model
Venue: arXiv cs.DC 2022
Year: 2022

With the rapid increase in the size and volume of cloud services and data centers, architectures with multiple job dispatchers are quickly becoming the norm. Load balancing is a key element of such systems. Nevertheless, current solutions to load balancing in such systems admit a paradoxical behavior in which more accurate information regarding server queue lengths degrades performance due to herding and detrimental incast effects. Indeed, both in theory and in practice, there is a common doubt regarding the value of information in the context of multi-dispatcher load balancing. As a result, both researchers and system designers resort to more straightforward solutions, such as the power-of-two-choices to avoid worst-case scenarios, potentially sacrificing overall resource utilization and system performance. A principal focus of our investigation concerns the value of information about queue lengths in the multi-dispatcher setting. We argue that, at its core, load balancing with multiple dispatchers is a distributed computing task. In that light, we propose a new job dispatching approach, called Tidal Water Filling, which addresses the distributed nature of the system. Specifically, by incorporating the existence of other dispatchers into the decision-making process, our protocols outperform previous solutions in many scenarios. In particular, when the dispatchers have complete and accurate information regarding the server queues, our policies significantly outperform all existing solutions.
Accuracy and Fairness Trade-offs in Machine Learning: A Stochastic Multi-Objective Approach
Venue: arXiv cs.LG 2022
Year: 2022

In the application of machine learning to real-life decision-making systems, e.g., credit scoring and criminal justice, the prediction outcomes might discriminate against people with sensitive attributes, leading to unfairness. The commonly used strategy in fair machine learning is to include fairness as a constraint or a penalization term in the minimization of the prediction loss, which ultimately limits the information given to decision-makers. In this paper, we introduce a new approach to handle fairness by formulating a stochastic multi-objective optimization problem for which the corresponding Pareto fronts uniquely and comprehensively define the accuracy-fairness trade-offs. We have then applied a stochastic approximation-type method to efficiently obtain well-spread and accurate Pareto fronts, and by doing so we can handle training data arriving in a streaming way.
Channel Estimation for RIS-Empowered Multi-User MISO Wireless Communications
Venue: arXiv cs.IT 2022
Year: 2022

Reconfigurable Intelligent Surfaces (RISs) have been recently considered as an energy-efficient solution for future wireless networks due to their fast and low-power configuration, which has increased potential in enabling massive connectivity and low-latency communications. Accurate and low-overhead channel estimation in RIS-based systems is one of the most critical challenges due to the usually large number of RIS unit elements and their distinctive hardware constraints. In this paper, we focus on the uplink of a RIS-empowered multi-user Multiple Input Single Output (MISO) uplink communication systems and propose a channel estimation framework based on the parallel factor decomposition to unfold the resulting cascaded channel model. We present two iterative estimation algorithms for the channels between the base station and RIS, as well as the channels between RIS and users. One is based on alternating least squares (ALS), while the other uses vector approximate message passing to iteratively reconstruct two unknown channels from the estimated vectors. To theoretically assess the performance of the ALS-based algorithm, we derived its estimation Cramér-Rao Bound (CRB). We also discuss the downlink achievable sum rate computation with estimated channels and different precoding schemes for the base station. Our extensive simulation results show that our algorithms outperform benchmark schemes and that the ALS technique achieves the CRB. It is also demonstrated that the sum rate using the estimated channels always reach that of perfect channels under various settings, thus, verifying the effectiveness and robustness of the proposed estimation algorithms.
Proof complexity and the binary encoding of combinatorial principles
Venue: arXiv cs.LO 2022
Year: 2022

We consider Proof Complexity in light of the unusual binary encoding of certain combinatorial principles. We contrast this Proof Complexity with the normal unary encoding in several refutation systems, based on Resolution and Integer Linear Programming. Please consult the article for the full abstract.
Privacy Guarantees for De-identifying Text Transformations
Venue: arXiv cs.CL 2022
Year: 2022

Machine Learning approaches to Natural Language Processing tasks benefit from a comprehensive collection of real-life user data. At the same time, there is a clear need for protecting the privacy of the users whose data is collected and processed. For text collections, such as, e.g., transcripts of voice interactions or patient records, replacing sensitive parts with benign alternatives can provide de-identification. However, how much privacy is actually guaranteed by such text transformations, and are the resulting texts still useful for machine learning? In this paper, we derive formal privacy guarantees for general text transformation-based de-identification methods on the basis of Differential Privacy. We also measure the effect that different ways of masking private information in dialog transcripts have on a subsequent machine learning task. To this end, we formulate different masking strategies and compare their privacy-utility trade-offs. In particular, we compare a simple redact approach with more sophisticated word-by-word replacement using deep learning models on multiple natural language understanding tasks like named entity recognition, intent detection, and dialog act classification. We find that only word-by-word replacement is robust against performance drops in various tasks.
How Trustworthy are Performance Evaluations for Basic Vision Tasks?
Venue: arXiv cs.CV 2022
Year: 2022

This paper examines performance evaluation criteria for basic vision tasks involving sets of objects namely, object detection, instance-level segmentation and multi-object tracking. The rankings of algorithms by an existing criterion can fluctuate with different choices of parameters, e.g. Intersection over Union (IoU) threshold, making their evaluations unreliable. More importantly, there is no means to verify whether we can trust the evaluations of a criterion. This work suggests a notion of trustworthiness for performance criteria, which requires (i) robustness to parameters for reliability, (ii) contextual meaningfulness in sanity tests, and (iii) consistency with mathematical requirements such as the metric properties. We observe that these requirements were overlooked by many widely-used criteria, and explore alternative criteria using metrics for sets of shapes. We also assess all these criteria based on the suggested requirements for trustworthiness.
A Large-Scale Chinese Short-Text Conversation Dataset
Venue: arXiv cs.CL 2022
Year: 2022

The advancements of neural dialogue generation models show promising results on modeling short-text conversations. However, training such models usually needs a large-scale high-quality dialogue corpus, which is hard to access. In this paper, we present a large-scale cleaned Chinese conversation dataset, LCCC, which contains a base version (6.8million dialogues) and a large version (12.0 million dialogues). The quality of our dataset is ensured by a rigorous data cleaning pipeline, which is built based on a set of rules and a classifier that is trained on manually annotated 110K dialogue pairs. We also release pre-training dialogue models which are trained on LCCC-base and LCCC-large respectively. The cleaned dataset and the pre-training models will facilitate the research of short-text conversation modeling. All the models and datasets are available at https://github.com/thu-coai/CDial-GPT.
Finding Efficient Domination for $S_{1,3,3}$-Free Bipartite Graphs in Polynomial Time
Venue: arXiv cs.DM 2022
Year: 2022

A vertex set $D$ in a finite undirected graph $G$ is an {\em efficient dominating set} (\emph{e.d.s.}\ for short) of $G$ if every vertex of $G$ is dominated by exactly one vertex of $D$. The \emph{Efficient Domination} (ED) problem, which asks for the existence of an e.d.s.\ in $G$, is \NP-complete for various $H$-free bipartite graphs, e.g., Lu and Tang showed that ED is \NP-complete for chordal bipartite graphs and for planar bipartite graphs; actually, ED is \NP-complete even for planar bipartite graphs with vertex degree at most 3 and girth at least $g$ for every fixed $g$. Thus, ED is \NP-complete for $K_{1,4}$-free bipartite graphs and for $C_4$-free bipartite graphs. In this paper, we show that ED can be solved in polynomial time for $S_{1,3,3}$-free bipartite graphs.
Expected Performance and Worst Case Scenario Analysis of the Divide-and-Conquer Method for the 0-1 Knapsack Problem
Venue: arXiv cs.DS 2022
Year: 2022

In this paper we furnish quality certificates for the Divide-and-Conquer method solving the 0-1 Knapsack Problem: the worst case scenario and estimates for the expected performance. The probabilistic setting is given and the main random variables are defined for the analysis of the expected performance. The efficiency is rigorously approximated for one iteration of the method then, these values are used to derive analytic estimates for the performance of a general Divide-and-Conquer tree. All the theoretical results are verified with statistically suited numerical experiments for a wider illustration of the method.
GRIMGEP: Learning Progress for Robust Goal Sampling in Visual Deep Reinforcement Learning
Venue: arXiv cs.LG 2022
Year: 2022

Designing agents, capable of learning autonomously a wide range of skills is critical in order to increase the scope of reinforcement learning. It will both increase the diversity of learned skills and reduce the burden of manually designing reward functions for each skill. Self-supervised agents, setting their own goals, and trying to maximize the diversity of those goals have shown great promise towards this end. However, a currently known limitation of agents trying to maximize the diversity of sampled goals is that they tend to get attracted to noise or more generally to parts of the environments that cannot be controlled (distractors). When agents have access to predefined goal features or expert knowledge, absolute Learning Progress (ALP) provides a way to distinguish between regions that can be controlled and those that cannot. However, those methods often fall short when the agents are only provided with raw sensory inputs such as images. In this work we extend those concepts to unsupervised image-based goal exploration. We propose a framework that allows agents to autonomously identify and ignore noisy distracting regions while searching for novelty in the learnable regions to both improve overall performance and avoid catastrophic forgetting. Our framework can be combined with any state-of-the-art novelty seeking goal exploration approaches. We construct a rich 3D image based environment with distractors. Experiments on this environment show that agents using our framework successfully identify interesting regions of the environment, resulting in drastically improved performances. The source code is available at https://sites.google.com/view/grimgep.