OpenRaiser/Intern-Atlas huggingface dataset:
TorMult: Introducing a Novel Tor Bandwidth Inflation Attack
Venue: arXiv cs.CR 2023
Year: 2023

The Tor network is the most prominent system for providing anonymous communication to web users, with a daily user base of 2 million users. However, since its inception, it has been constantly targeted by various traffic fingerprinting and correlation attacks aiming at deanonymizing its users. A critical requirement for these attacks is to attract as much user traffic to adversarial relays as possible, which is typically accomplished by means of bandwidth inflation attacks. This paper proposes a new inflation attack vector in Tor, referred to as TorMult, which enables inflation of measured bandwidth. The underlying attack technique exploits resource sharing among Tor relay nodes and employs a cluster of attacker-controlled relays with coordinated resource allocation within the cluster to deceive bandwidth measurers into believing that each relay node in the cluster possesses ample resources. We propose two attack variants, C-TorMult and D-TorMult, and test both versions in a private Tor test network. Our evaluation demonstrates that an attacker can inflate the measured bandwidth by a factor close to n using C-TorMult and nearly half n*N using D-TorMult, where n is the size of the cluster hosted on one server and N is the number of servers. Furthermore, our theoretical analysis reveals that gaining control over half of the Tor network's traffic can be achieved by employing just 10 dedicated servers with a cluster size of 109 relays running the TorMult attack, each with a bandwidth of 100MB/s. The problem is further exacerbated by the fact that Tor not only allows resource sharing but, according to recent reports, even promotes it.
FedCME: Client Matching and Classifier Exchanging to Handle Data Heterogeneity in Federated Learning
Venue: arXiv cs.LG 2023
Year: 2023

Data heterogeneity across clients is one of the key challenges in Federated Learning (FL), which may slow down the global model convergence and even weaken global model performance. Most existing approaches tackle the heterogeneity by constraining local model updates through reference to global information provided by the server. This can alleviate the performance degradation on the aggregated global model. Different from existing methods, we focus the information exchange between clients, which could also enhance the effectiveness of local training and lead to generate a high-performance global model. Concretely, we propose a novel FL framework named FedCME by client matching and classifier exchanging. In FedCME, clients with large differences in data distribution will be matched in pairs, and then the corresponding pair of clients will exchange their classifiers at the stage of local training in an intermediate moment. Since the local data determines the local model training direction, our method can correct update direction of classifiers and effectively alleviate local update divergence. Besides, we propose feature alignment to enhance the training of the feature extractor. Experimental results demonstrate that FedCME performs better than FedAvg, FedProx, MOON and FedRS on popular federated learning benchmarks including FMNIST and CIFAR10, in the case where data are heterogeneous.
BuboGPT: Enabling Visual Grounding in Multi-Modal LLMs
Venue: arXiv cs.CV 2023
Year: 2023

LLMs have demonstrated remarkable abilities at interacting with humans through language, especially with the usage of instruction-following data. Recent advancements in LLMs, such as MiniGPT-4, LLaVA, and X-LLM, further enlarge their abilities by incorporating multi-modal inputs, including image, video, and speech. Despite their effectiveness at generating precise and detailed language understanding of the given modality signal, these LLMs give up the ability to ground specific parts of inputs, thus only constructing a coarse-grained mapping. However, explicit and informative correspondence between text and other modalities will not only improve the user experience but also help to expand the application scenario of multi-modal LLMs. Therefore, we propose BuboGPT, a multi-modal LLM with visual grounding that can perform cross-modal interaction between vision, audio and language, providing fine-grained understanding of visual objects and other given modalities. As a result, BuboGPT is able to point out the specific location of an object in the image, when it is generating response or description for that object. Our contributions are two-fold: 1) An off-the-shelf visual grounding module based on SAM that extracts entities in a sentence and find corresponding masks in the image. 2) A two-stage training scheme and instruction dataset to endow joint text-image-audio understanding. Our experiments show that BuboGPT achieves impressive multi-modality understanding and visual grounding abilities during the interaction with human. It performs consistently well when provided by arbitrary modality combinations (either aligned or unaligned). Our code, model and dataset are available at https://bubo-gpt.github.io .
Tight Bounds for Budgeted Maximum Weight Independent Set in Bipartite and Perfect Graphs
Venue: arXiv cs.DS 2023
Year: 2023

We consider the classic budgeted maximum weight independent set (BMWIS) problem. The input is a graph $G = (V,E)$, a weight function $w:V \rightarrow \mathbb{R}_{\geq 0}$, a cost function $c:V \rightarrow \mathbb{R}_{\geq 0}$, and a budget $B \in \mathbb{R}_{\geq 0}$. The goal is to find an independent set $S \subseteq V$ in $G$ such that $\sum_{v \in S} c(v) \leq B$, which maximizes the total weight $\sum_{v \in S} w(v)$. Since the problem on general graphs cannot be approximated within ratio $|V|^{1-\varepsilon}$ for any $\varepsilon>0$, BMWIS has attracted significant attention on graph families for which a maximum weight independent set can be computed in polynomial time. Two notable such graph families are bipartite and perfect graphs. BMWIS is known to be NP-hard on both of these graph families; however, the best possible approximation guarantees for these graphs are wide open. In this paper, we give a tight $2$-approximation for BMWIS on perfect graphs and bipartite graphs. In particular, we give We a $(2-\varepsilon)$ lower bound for BMWIS on bipartite graphs, already for the special case where the budget is replaced by a cardinality constraint, based on the Small Set Expansion Hypothesis (SSEH). For the upper bound, we design a $2$-approximation for BMWIS on perfect graphs using a Lagrangian relaxation based technique. Finally, we obtain a tight lower bound for the capacitated maximum weight independent set (CMWIS) problem, the special case of BMWIS where $w(v) = c(v)~\forall v \in V$. We show that CMWIS on bipartite and perfect graphs is unlikely to admit an efficient polynomial-time approximation scheme (EPTAS). Thus, the existing PTAS for CMWIS is essentially the best we can expect.
Omnipotent Adversarial Training in the Wild
Venue: arXiv cs.LG 2023
Year: 2023

Adversarial training is an important topic in robust deep learning, but the community lacks attention to its practical usage. In this paper, we aim to resolve a real-world challenge, i.e., training a model on an imbalanced and noisy dataset to achieve high clean accuracy and adversarial robustness, with our proposed Omnipotent Adversarial Training (OAT) strategy. OAT consists of two innovative methodologies to address the imperfection in the training set. We first introduce an oracle into the adversarial training process to help the model learn a correct data-label conditional distribution. This carefully-designed oracle can provide correct label annotations for adversarial training. We further propose logits adjustment adversarial training to overcome the data imbalance issue, which can help the model learn a Bayes-optimal distribution. Our comprehensive evaluation results show that OAT outperforms other baselines by more than 20% clean accuracy improvement and 10% robust accuracy improvement under complex combinations of data imbalance and label noise scenarios. The code can be found in https://github.com/GuanlinLee/OAT.
Temporal and Geographical Analysis of Real Economic Activities in the Bitcoin Blockchain
Venue: arXiv cs.SI 2023
Year: 2023

We study the real economic activity in the Bitcoin blockchain that involves transactions from/to retail users rather than between organizations such as marketplaces, exchanges, or other services. We first introduce a heuristic method to classify Bitcoin players into three main categories: Frequent Receivers (FR), Neighbors of FR, and Others. We show that most real transactions involve Frequent Receivers, representing a small fraction of the total value exchanged according to the blockchain, but a significant fraction of all payments, raising concerns about the centralization of the Bitcoin ecosystem. We also conduct a weekly pattern analysis of activity, providing insights into the geographical location of Bitcoin users and allowing us to quantify the bias of a well-known dataset for actor identification.
Managing Write Access without Token Fees in Leaderless DAG-based Ledgers
Venue: arXiv cs.NI 2023
Year: 2023

A significant portion of research on distributed ledgers has focused on circumventing the limitations of leader-based blockchains mainly in terms of scalability, decentralization and power consumption. Leaderless architectures based on directed acyclic graphs (DAGs) avoid many of these limitations altogether, but their increased flexibility and performance comes at the cost of increased design complexity, so their potential has remained largely unexplored. Management of write access to these ledgers presents a major challenge because ledger updates may be made in parallel, hence transactions cannot simply be serialised and prioritised according to token fees paid to validators. In this work, we propose an access control scheme for leaderless DAG-based ledgers which is based on consuming credits rather than paying fees in the base token. We outline a general model for this new approach and provide some simulation results showing promising performance boosts.
Deep Cross-Modal Steganography Using Neural Representations
Venue: arXiv cs.CR 2023
Year: 2023

Steganography is the process of embedding secret data into another message or data, in such a way that it is not easily noticeable. With the advancement of deep learning, Deep Neural Networks (DNNs) have recently been utilized in steganography. However, existing deep steganography techniques are limited in scope, as they focus on specific data types and are not effective for cross-modal steganography. Therefore, We propose a deep cross-modal steganography framework using Implicit Neural Representations (INRs) to hide secret data of various formats in cover images. The proposed framework employs INRs to represent the secret data, which can handle data of various modalities and resolutions. Experiments on various secret datasets of diverse types demonstrate that the proposed approach is expandable and capable of accommodating different modalities.
Do Models Explain Themselves? Counterfactual Simulatability of Natural Language Explanations
Venue: arXiv cs.CL 2023
Year: 2023

Large language models (LLMs) are trained to imitate humans to explain human decisions. However, do LLMs explain themselves? Can they help humans build mental models of how LLMs process different inputs? To answer these questions, we propose to evaluate $\textbf{counterfactual simulatability}$ of natural language explanations: whether an explanation can enable humans to precisely infer the model's outputs on diverse counterfactuals of the explained input. For example, if a model answers "yes" to the input question "Can eagles fly?" with the explanation "all birds can fly", then humans would infer from the explanation that it would also answer "yes" to the counterfactual input "Can penguins fly?". If the explanation is precise, then the model's answer should match humans' expectations. We implemented two metrics based on counterfactual simulatability: precision and generality. We generated diverse counterfactuals automatically using LLMs. We then used these metrics to evaluate state-of-the-art LLMs (e.g., GPT-4) on two tasks: multi-hop factual reasoning and reward modeling. We found that LLM's explanations have low precision and that precision does not correlate with plausibility. Therefore, naively optimizing human approvals (e.g., RLHF) may not be a sufficient solution.
COLLIE: Systematic Construction of Constrained Text Generation Tasks
Venue: arXiv cs.CL 2023
Year: 2023

Text generation under constraints have seen increasing interests in natural language processing, especially with the rapidly improving capabilities of large language models. However, existing benchmarks for constrained generation usually focus on fixed constraint types (e.g.,generate a sentence containing certain words) that have proved to be easy for state-of-the-art models like GPT-4. We present COLLIE, a grammar-based framework that allows the specification of rich, compositional constraints with diverse generation levels (word, sentence, paragraph, passage) and modeling challenges (e.g.,language understanding, logical reasoning, counting, semantic planning). We also develop tools for automatic extraction of task instances given a constraint structure and a raw text corpus. Using COLLIE, we compile the COLLIE-v1 dataset with 2080 instances comprising 13 constraint structures. We perform systematic experiments across five state-of-the-art instruction-tuned language models and analyze their performances to reveal shortcomings. COLLIE is designed to be extensible and lightweight, and we hope the community finds it useful to develop more complex constraints and evaluations in the future.
Robotic Exploration for Mapping
Venue: arXiv cs.RO 2023
Year: 2023

Robotic Exploration has evolved rapidly in the past two decades as new and more complex techniques have been created to explore unknown regions efficiently. Exciting advancements in exploration, autonomous navigation, and sensor technology have created opportunities for robots to be utilized in new environments and for new objectives ranging from mapping of abandon mines and deep oceans to the efficient creation of indoor models for navigation and search. In this paper we present and discuss a number of examples in research literature of these recent advancements, specifically focusing on robotic exploration algorithms for unmanned vehicles.
Zone-Based Privacy-Preserving Billing for Local Energy Market Based on Multiparty Computation
Venue: arXiv cs.CR 2023
Year: 2023

This paper proposes a zone-based privacy-preserving billing protocol for local energy markets that takes into account energy volume deviations of market participants from their bids. Our protocol incorporates participants' locations on the grid for splitting the deviations cost. The proposed billing model employs multiparty computation so that the accurate calculation of individual bills is performed in a decentralised and privacy-preserving manner. We also present a security analysis as well as performance evaluations for different security settings. The results show superiority of the honest-majority model to the dishonest majority in terms of computational efficiency. They also show that the billing can be executed for 5000 users in less than nine seconds in the online phase for all security settings, demonstrating its feasibility to be deployed in real local energy markets.
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
Venue: arXiv cs.DS 2023
Year: 2023

Grammar compression is a general compression framework in which a string $T$ of length $N$ is represented as a context-free grammar of size $n$ whose language contains only $T$. In this paper, we focus on studying the limitations of algorithms and data structures operating on strings in grammar-compressed form. Previous work focused on proving lower bounds for grammars constructed using algorithms that achieve the approximation ratio $ρ=\mathcal{O}(\text{polylog }N)$. Unfortunately, for the majority of grammar compressors, $ρ$ is either unknown or satisfies $ρ=ω(\text{polylog }N)$. In their seminal paper, Charikar et al. [IEEE Trans. Inf. Theory 2005] studied seven popular grammar compression algorithms: RePair, Greedy, LongestMatch, Sequential, Bisection, LZ78, and $α$-Balanced. Only one of them ($α$-Balanced) is known to achieve $ρ=\mathcal{O}(\text{polylog }N)$. We develop the first technique for proving lower bounds for data structures and algorithms on grammars that is fully general and does not depend on the approximation ratio $ρ$ of the used grammar compressor. Using this technique, we first prove that $Ω(\log N/\log \log N)$ time is required for random access on RePair, Greedy, LongestMatch, Sequential, and Bisection, while $Ω(\log\log N)$ time is required for random access to LZ78. All these lower bounds hold within space $\mathcal{O}(n\text{ polylog }N)$ and match the existing upper bounds. We also generalize this technique to prove several conditional lower bounds for compressed computation. For example, we prove that unless the Combinatorial $k$-Clique Conjecture fails, there is no combinatorial algorithm for CFG parsing on Bisection (for which it holds $ρ=\tildeΘ(N^{1/2})$) that runs in $\mathcal{O}(n^c\cdot N^{3-ε})$ time for all constants $c>0$ and $ε>0$. Previously, this was known only for $c<2ε$.
Quantum Tutte Embeddings
Venue: arXiv cs.DS 2023
Year: 2023

Using the framework of Tutte embeddings, we begin an exploration of \emph{quantum graph drawing}, which uses quantum computers to visualize graphs. The main contributions of this paper include formulating a model for quantum graph drawing, describing how to create a graph-drawing quantum circuit from a given graph, and showing how a Tutte embedding can be calculated as a quantum state in this circuit that can then be sampled to extract the embedding. To evaluate the complexity of our quantum Tutte embedding circuits, we compare them to theoretical bounds established in the classical computing setting derived from a well-known classical algorithm for solving the types of linear systems that arise from Tutte embeddings. We also present empirical results obtained from experimental quantum simulations.
AI for the Generation and Testing of Ideas Towards an AI Supported Knowledge Development Environment
Venue: arXiv cs.AI 2023
Year: 2023

New systems employ Machine Learning to sift through large knowledge sources, creating flexible Large Language Models. These models discern context and predict sequential information in various communication forms. Generative AI, leveraging Transformers, generates textual or visual outputs mimicking human responses. It proposes one or multiple contextually feasible solutions for a user to contemplate. However, generative AI does not currently support traceability of ideas, a useful feature provided by search engines indicating origin of information. The narrative style of generative AI has gained positive reception. People learn from stories. Yet, early ChatGPT efforts had difficulty with truth, reference, calculations, and aspects like accurate maps. Current capabilities of referencing locations and linking to apps seem to be better catered by the link-centric search methods we've used for two decades. Deploying truly believable solutions extends beyond simulating contextual relevance as done by generative AI. Combining the creativity of generative AI with the provenance of internet sources in hybrid scenarios could enhance internet usage. Generative AI, viewed as drafts, stimulates thinking, offering alternative ideas for final versions or actions. Scenarios for information requests are considered. We discuss how generative AI can boost idea generation by eliminating human bias. We also describe how search can verify facts, logic, and context. The user evaluates these generated ideas for selection and usage. This paper introduces a system for knowledge workers, Generate And Search Test, enabling individuals to efficiently create solutions previously requiring top collaborations of experts.
Disentangling Node Attributes from Graph Topology for Improved Generalizability in Link Prediction
Venue: arXiv cs.LG 2023
Year: 2023

Link prediction is a crucial task in graph machine learning with diverse applications. We explore the interplay between node attributes and graph topology and demonstrate that incorporating pre-trained node attributes improves the generalization power of link prediction models. Our proposed method, UPNA (Unsupervised Pre-training of Node Attributes), solves the inductive link prediction problem by learning a function that takes a pair of node attributes and predicts the probability of an edge, as opposed to Graph Neural Networks (GNN), which can be prone to topological shortcuts in graphs with power-law degree distribution. In this manner, UPNA learns a significant part of the latent graph generation mechanism since the learned function can be used to add incoming nodes to a growing graph. By leveraging pre-trained node attributes, we overcome observational bias and make meaningful predictions about unobserved nodes, surpassing state-of-the-art performance (3X to 34X improvement on benchmark datasets). UPNA can be applied to various pairwise learning tasks and integrated with existing link prediction models to enhance their generalizability and bolster graph generative models.
Towards the Sparseness of Projection Head in Self-Supervised Learning
Venue: arXiv cs.LG 2023
Year: 2023

In recent years, self-supervised learning (SSL) has emerged as a promising approach for extracting valuable representations from unlabeled data. One successful SSL method is contrastive learning, which aims to bring positive examples closer while pushing negative examples apart. Many current contrastive learning approaches utilize a parameterized projection head. Through a combination of empirical analysis and theoretical investigation, we provide insights into the internal mechanisms of the projection head and its relationship with the phenomenon of dimensional collapse. Our findings demonstrate that the projection head enhances the quality of representations by performing contrastive loss in a projected subspace. Therefore, we propose an assumption that only a subset of features is necessary when minimizing the contrastive loss of a mini-batch of data. Theoretical analysis further suggests that a sparse projection head can enhance generalization, leading us to introduce SparseHead - a regularization term that effectively constrains the sparsity of the projection head, and can be seamlessly integrated with any self-supervised learning (SSL) approaches. Our experimental results validate the effectiveness of SparseHead, demonstrating its ability to improve the performance of existing contrastive methods.