OpenRaiser/Intern-Atlas huggingface dataset:
Robot Hacking Manual (RHM)
Venue: arXiv cs.RO 2022
Year: 2022

Robots are often shipped insecure and in some cases fully unprotected. The rationale behind is fourfold: first, defensive security mechanisms for robots are still on their early stages, not covering the complete threat landscape. Second, the inherent complexity of robotic systems makes their protection costly, both technically and economically. Third, robot vendors do not generally take responsibility in a timely manner, extending the zero-days exposure window (time until mitigation of a zero-day) to several years on average. Fourth, contrary to the common-sense expectations in 21st century and similar to Ford in the 1920s with cars, most robot manufacturers oppose or difficult robot repairs. The Robot Hacking Manual (RHM) is an introductory series about cybersecurity for robots, with an attempt to provide comprehensive case studies and step-by-step tutorials with the intent to raise awareness in the field and highlight the importance of taking a security-first approach. The material available here is also a personal learning attempt and it's disconnected from any particular organization. Content is provided as is and by no means it's encouraged or promoted the unauthorized tampering of robotic systems or related technologies.
The Philos Trust Algorithm: Preventing Exploitation of Distributed Trust
Venue: arXiv cs.DC 2022
Year: 2022

The Philos Marketplace blockchain system is a proposed hierarchical blockchain architecture which allows a large number of individual blockchains to operate in parallel. These parallel chains achieve consensus among one another on a limited set of core operations, while allowing each on-chain application to manage its own data independently of others. This architecture addresses the scalability issues of traditional linear blockchains, but requires novel consensus mechanisms. A central feature of the Philos consensus mechanism is its trust algorithm, which assigns each network node a numerical trust value (or score) indicating the quality of recent past performance. This trust value is then used to determine a node's voting weight at the higher levels of consensus. In this paper, we formally define the Philos trust algorithm, and provide several illustrations of its operation, both theoretically and empirically. We also ask whether a misbehaving node can strategically exploit the algorithm for its personal gain, and show that this type of exploitation can be universally prevented simply by enforcing a mild limit on the number of participants in each of the parallel chains.
One-Shot Learning from a Demonstration with Hierarchical Latent Language
Venue: arXiv cs.CL 2022
Year: 2022

Humans have the capability, aided by the expressive compositionality of their language, to learn quickly by demonstration. They are able to describe unseen task-performing procedures and generalize their execution to other contexts. In this work, we introduce DescribeWorld, an environment designed to test this sort of generalization skill in grounded agents, where tasks are linguistically and procedurally composed of elementary concepts. The agent observes a single task demonstration in a Minecraft-like grid world, and is then asked to carry out the same task in a new map. To enable such a level of generalization, we propose a neural agent infused with hierarchical latent language--both at the level of task inference and subtask planning. Our agent first generates a textual description of the demonstrated unseen task, then leverages this description to replicate it. Through multiple evaluation scenarios and a suite of generalization tests, we find that agents that perform text-based inference are better equipped for the challenge under a random split of tasks.
Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
Venue: arXiv cs.DS 2022
Year: 2022

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time $2^{\mathcal{O}(\sqrt{n}\log n)}$ and a quasipolynomial-time approximation scheme with improved running time $2^{\mathcal{O}(\varepsilon^{-1} \log^{5} n)}$. The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in $P_t$-free graphs, ensures that given an $n$-vertex $P_t$-free graph, in polynomial time we can find a set $P$ of at most $t-1$ vertices, such that every connected component of $G-N[P]$ has at most $n/2$ vertices. Our main technical contribution is an analog of this result for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, in polynomial time we can find a set $P$ of $\mathcal{O}(t \log n)$ vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of $G-N[P]$ such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most $n/2$ vertices.
Binary Classification Under $\ell_0$ Attacks for General Noise Distribution
Venue: arXiv cs.LG 2022
Year: 2022

Adversarial examples have recently drawn considerable attention in the field of machine learning due to the fact that small perturbations in the data can result in major performance degradation. This phenomenon is usually modeled by a malicious adversary that can apply perturbations to the data in a constrained fashion, such as being bounded in a certain norm. In this paper, we study this problem when the adversary is constrained by the $\ell_0$ norm; i.e., it can perturb a certain number of coordinates in the input, but has no limit on how much it can perturb those coordinates. Due to the combinatorial nature of this setting, we need to go beyond the standard techniques in robust machine learning to address this problem. We consider a binary classification scenario where $d$ noisy data samples of the true label are provided to us after adversarial perturbations. We introduce a classification method which employs a nonlinear component called truncation, and show in an asymptotic scenario, as long as the adversary is restricted to perturb no more than $\sqrt{d}$ data samples, we can almost achieve the optimal classification error in the absence of the adversary, i.e. we can completely neutralize adversary's effect. Surprisingly, we observe a phase transition in the sense that using a converse argument, we show that if the adversary can perturb more than $\sqrt{d}$ coordinates, no classifier can do better than a random guess.
Unsupervised Alignment of Distributional Word Embeddings
Venue: arXiv cs.CL 2022
Year: 2022

Cross-domain alignment play a key roles in tasks ranging from machine translation to transfer learning. Recently, purely unsupervised methods operating on monolingual embeddings have successfully been used to infer a bilingual lexicon without relying on supervision. However, current state-of-the art methods only focus on point vectors although distributional embeddings have proven to embed richer semantic information when representing words. In this paper, we propose stochastic optimization approach for aligning probabilistic embeddings. Finally, we evaluate our method on the problem of unsupervised word translation, by aligning word embeddings trained on monolingual data. We show that the proposed approach achieves good performance on the bilingual lexicon induction task across several language pairs and performs better than the point-vector based approach.
KPE: Keypoint Pose Encoding for Transformer-based Image Generation
Venue: arXiv cs.CV 2022
Year: 2022

Transformers have recently been shown to generate high quality images from text input. However, the existing method of pose conditioning using skeleton image tokens is computationally inefficient and generate low quality images. Therefore we propose a new method; Keypoint Pose Encoding (KPE); KPE is 10 times more memory efficient and over 73% faster at generating high quality images from text input conditioned on the pose. The pose constraint improves the image quality and reduces errors on body extremities such as arms and legs. The additional benefits include invariance to changes in the target image domain and image resolution, making it easily scalable to higher resolution images. We demonstrate the versatility of KPE by generating photorealistic multiperson images derived from the DeepFashion dataset. We also introduce a evaluation method People Count Error (PCE) that is effective in detecting error in generated human images.
On-Robot Learning With Equivariant Models
Venue: arXiv cs.RO 2022
Year: 2022

Recently, equivariant neural network models have been shown to improve sample efficiency for tasks in computer vision and reinforcement learning. This paper explores this idea in the context of on-robot policy learning in which a policy must be learned entirely on a physical robotic system without reference to a model, a simulator, or an offline dataset. We focus on applications of Equivariant SAC to robotic manipulation and explore a number of variations of the algorithm. Ultimately, we demonstrate the ability to learn several non-trivial manipulation tasks completely through on-robot experiences in less than an hour or two of wall clock time.
An Empirical Eye-Tracking Study of Feature Model Comprehension
Venue: arXiv cs.SE 2022
Year: 2022

Software Product Lines (SPLs) are families of related software systems which are distinguished by the set of features each system provides. Feature Models are the de facto standard for modelling the variability of SPLs because they describe the features, their relations, and all the combinations of features that constitute a SPL. Because of their key role, feature models are at the core of many tasks in SPL engineering. Our work presents an empirical study on the comprehension of feature models for the task of checking the validity of configurations. Our study explored the relation between the number of features and the number of cross-tree constraints with the accuracy of participants' answers to validity checking questions, and used eye fixations for analyzing the difficulty in interpreting fixated information and the amount of cognitive processing of the different parts of the feature model stimuli. We found that answer accuracy does not relate individually to the number of features or to the number of cross-tree constrains of a feature model, but both factors do show an interaction on accuracy. Additionally, our study identified differences in feature models with cross-tree constraints in both number of fixations and fixation time, but no differences in those models without cross-tree constraints.
Census TopDown: The Impacts of Differential Privacy on Redistricting
Venue: arXiv cs.CY 2022
Year: 2022

The 2020 Decennial Census will be released with a new disclosure avoidance system in place, putting differential privacy in the spotlight for a wide range of data users. We consider several key applications of Census data in redistricting, developing tools and demonstrations for practitioners who are concerned about the impacts of this new noising algorithm called TopDown. Based on a close look at reconstructed Texas data, we find reassuring evidence that TopDown will not threaten the ability to produce districts with tolerable population balance or to detect signals of racial polarization for Voting Rights Act enforcement.
Model-Architecture Co-Design for High Performance Temporal GNN Inference on FPGA
Venue: arXiv cs.AR 2022
Year: 2022

Temporal Graph Neural Networks (TGNNs) are powerful models to capture temporal, structural, and contextual information on temporal graphs. The generated temporal node embeddings outperform other methods in many downstream tasks. Real-world applications require high performance inference on real-time streaming dynamic graphs. However, these models usually rely on complex attention mechanisms to capture relationships between temporal neighbors. In addition, maintaining vertex memory suffers from intrinsic temporal data dependency that hinders task-level parallelism, making it inefficient on general-purpose processors. In this work, we present a novel model-architecture co-design for inference in memory-based TGNNs on FPGAs. The key modeling optimizations we propose include a light-weight method to compute attention scores and a related temporal neighbor pruning strategy to further reduce computation and memory accesses. These are holistically coupled with key hardware optimizations that leverage FPGA hardware. We replace the temporal sampler with an on-chip FIFO based hardware sampler and the time encoder with a look-up-table. We train our simplified models using knowledge distillation to ensure similar accuracy vis-á-vis the original model. Taking advantage of the model optimizations, we propose a principled hardware architecture using batching, pipelining, and prefetching techniques to further improve the performance. We also propose a hardware mechanism to ensure the chronological vertex updating without sacrificing the computation parallelism. We evaluate the performance of the proposed hardware accelerator on three real-world datasets.
Improving Neural ODEs via Knowledge Distillation
Venue: arXiv cs.CV 2022
Year: 2022

Neural Ordinary Differential Equations (Neural ODEs) construct the continuous dynamics of hidden units using ordinary differential equations specified by a neural network, demonstrating promising results on many tasks. However, Neural ODEs still do not perform well on image recognition tasks. The possible reason is that the one-hot encoding vector commonly used in Neural ODEs can not provide enough supervised information. We propose a new training based on knowledge distillation to construct more powerful and robust Neural ODEs fitting image recognition tasks. Specially, we model the training of Neural ODEs into a teacher-student learning process, in which we propose ResNets as the teacher model to provide richer supervised information. The experimental results show that the new training manner can improve the classification accuracy of Neural ODEs by 24% on CIFAR10 and 5% on SVHN. In addition, we also quantitatively discuss the effect of both knowledge distillation and time horizon in Neural ODEs on robustness against adversarial examples. The experimental analysis concludes that introducing the knowledge distillation and increasing the time horizon can improve the robustness of Neural ODEs against adversarial examples.
A Tighter Approximation Guarantee for Greedy Minimum Entropy Coupling
Venue: arXiv cs.IT 2022
Year: 2022

We examine the minimum entropy coupling problem, where one must find the minimum entropy variable that has a given set of distributions $S = \{p_1, \dots, p_m \}$ as its marginals. Although this problem is NP-Hard, previous works have proposed algorithms with varying approximation guarantees. In this paper, we show that the greedy coupling algorithm of [Kocaoglu et al., AAAI'17] is always within $\log_2(e)$ ($\approx 1.44$) bits of the minimum entropy coupling. In doing so, we show that the entropy of the greedy coupling is upper-bounded by $H\left(\bigwedge S \right) + \log_2(e)$. This improves the previously best known approximation guarantee of $2$ bits within the optimal [Li, IEEE Trans. Inf. Theory '21]. Moreover, we show our analysis is tight by proving there is no algorithm whose entropy is upper-bounded by $H\left(\bigwedge S \right) + c$ for any constant $c<\log_2(e)$. Additionally, we examine a special class of instances where the greedy coupling algorithm is exactly optimal.
Internet-augmented language models through few-shot prompting for open-domain question answering
Venue: arXiv cs.CL 2022
Year: 2022

In this work, we aim to capitalize on the unique few-shot capabilities of large-scale language models (LSLMs) to overcome some of their challenges with respect to grounding to factual and up-to-date information. Motivated by semi-parametric language models (LMs), which ground their decisions in external retrieved evidence, we use few-shot prompting to learn to condition LMs on information returned from the web using Google Search, a broad and constantly updated knowledge source. Our approach does not involve fine-tuning or learning additional parameters, thus making it applicable to any LM, offering therefore a strong baseline. Indeed, we find that LMs conditioned on the web surpass performance of closed-book models of similar, or even larger, model sizes in open-domain question answering. Finally, we find that increasing the inference-time compute of models, achieved via using multiple retrieved evidences to generate multiple answers followed by a reranking stage that uses scores generated by the same LMs, leads to better performance and alleviates lower performance of smaller few-shot LMs. All in all, our findings suggest that it might be beneficial to slow down the race towards the biggest model and instead shift attention towards finding more effective ways to use models, including but not limited to, better prompting or increasing inference-time compute.
Semi-supervision semantic segmentation with uncertainty-guided self cross supervision
Venue: arXiv cs.CV 2022
Year: 2022

As a powerful way of realizing semi-supervised segmentation, the cross supervision method learns cross consistency based on independent ensemble models using abundant unlabeled images. However, the wrong pseudo labeling information generated by cross supervision would confuse the training process and negatively affect the effectiveness of the segmentation model. Besides, the training process of ensemble models in such methods also multiplies the cost of computation resources and decreases the training efficiency. To solve these problems, we propose a novel cross supervision method, namely uncertainty-guided self cross supervision (USCS). In addition to ensemble models, we first design a multi-input multi-output (MIMO) segmentation model which can generate multiple outputs with shared model and consequently impose consistency over the outputs, saving the cost on parameters and calculations. On the other hand, we employ uncertainty as guided information to encourage the model to focus on the high confident regions of pseudo labels and mitigate the effects of wrong pseudo labeling in self cross supervision, improving the performance of the segmentation model. Extensive experiments show that our method achieves state-of-the-art performance while saving 40.5% and 49.1% cost on parameters and calculations.
Multi-Task Adversarial Learning for Treatment Effect Estimation in Basket Trials
Venue: arXiv cs.LG 2022
Year: 2022

Estimating treatment effects from observational data provides insights about causality guiding many real-world applications such as different clinical study designs, which are the formulations of trials, experiments, and observational studies in medical, clinical, and other types of research. In this paper, we describe causal inference for application in a novel clinical design called basket trial that tests how well a new drug works in patients who have different types of cancer that all have the same mutation. We propose a multi-task adversarial learning (MTAL) method, which incorporates feature selection multi-task representation learning and adversarial learning to estimate potential outcomes across different tumor types for patients sharing the same genetic mutation but having different tumor types. In our paper, the basket trial is employed as an intuitive example to present this new causal inference setting. This new causal inference setting includes, but is not limited to basket trials. This setting has the same challenges as the traditional causal inference problem, i.e., missing counterfactual outcomes under different subgroups and treatment selection bias due to confounders. We present the practical advantages of our MTAL method for the analysis of synthetic basket trial data and evaluate the proposed estimator on two benchmarks, IHDP and News. The results demonstrate the superiority of our MTAL method over the competing state-of-the-art methods.
Determining Existence of Logical Obstructions to the Distributed Task Solvability
Venue: arXiv cs.DC 2022
Year: 2022

To study the distributed task solvability, Goubault, Ledent, and Rajsbaum devised a model of dynamic epistemic logic that is equivalent to the topological model for distributed computing. In the logical model, the unsolvability of a particular distributed task can be proven by finding a formula, called logical obstruction. This logical method is very appealing because the concrete formulas that prevent to solve task would have implications of intuitive factors for the unsolvability. However, it has not been well studied when a logical obstruction exists and how to systematically construct a concrete logical obstruction formula, if any. In addition, it is proved that there are some tasks that are solvable but do not admit logical obstructions. In this paper, we propose a method to prove the non-existence of logical obstructions to the solvability of distributed tasks, based on the technique of simulation. Moreover, we give a method to determine whether a logical obstruction exists or not for a finite protocol and a finite task, and if it exists, construct a concrete obstruction. Using this method, we demonstrate that the language of the standard epistemic logic, without distributed knowledge, does not admit logical obstruction to the solvability of $k$-set agreement tasks. We also show that there is no logical obstruction for multi-round immediate snapshot even in the language of epistemic logic with distributed knowledge. In addition, for the know-all model, we provide a concrete obstruction formula that shows the unsolvability of the $k$-set agreement task.
Scaling Blockchain Consensus via a Robust Shared Mempool
Venue: arXiv cs.DC 2022
Year: 2022

There is a resurgence of interest in Byzantine fault-tolerant (BFT) systems due to blockchains. However, leader-based BFT consensus protocols used by permissioned blockchains have limited scalability and robustness. To alleviate the leader bottleneck in BFT consensus, we introduce Stratus, a robust shared mempool protocol that decouples transaction distribution from consensus. Our idea is to have replicas disseminate transactions in a distributed manner and have the leader only propose transaction ids. Stratus uses a provably available broadcast (PAB) protocol to ensure the availability of the referenced transactions. We implemented and evaluated Stratus by integrating it with state-of-the-art BFT-based blockchain protocols and evaluated these protocols in both LAN and WAN settings. Our results show that Stratus-based protocols achieve up to $5\sim20\times$ more throughput than their native counterparts in a network with hundreds of replicas. In addition, the performance of Stratus degrades gracefully in the presence of network asynchrony, Byzantine attackers, and unbalanced workloads. Our design provides easy-to-use APIs so that other BFT systems suffering from leader bottlenecks can use Stratus.