OpenRaiser/Intern-Atlas huggingface dataset:
DPack: Efficiency-Oriented Privacy Budget Scheduling
Venue: arXiv cs.CR 2024
Year: 2024

Machine learning (ML) models can leak information about users, and differential privacy (DP) provides a rigorous way to bound that leakage under a given budget. This DP budget can be regarded as a new type of compute resource in workloads of multiple ML models training on user data. Once it is used, the DP budget is forever consumed. Therefore, it is crucial to allocate it most efficiently to train as many models as possible. This paper presents the scheduler for privacy that optimizes for efficiency. We formulate privacy scheduling as a new type of multidimensional knapsack problem, called privacy knapsack, which maximizes DP budget efficiency. We show that privacy knapsack is NP-hard, hence practical algorithms are necessarily approximate. We develop an approximation algorithm for privacy knapsack, DPack, and evaluate it on microbenchmarks and on a new, synthetic private-ML workload we developed from the Alibaba ML cluster trace. We show that DPack: (1) often approaches the efficiency-optimal schedule, (2) consistently schedules more tasks compared to a state-of-the-art privacy scheduling algorithm that focused on fairness (1.3-1.7x in Alibaba, 1.0-2.6x in microbenchmarks), but (3) sacrifices some level of fairness for efficiency. Therefore, using DPack, DP ML operators should be able to train more models on the same amount of user data while offering the same privacy guarantee to their users.
Multimodal Explainability via Latent Shift applied to COVID-19 stratification
Venue: arXiv cs.AI 2024
Year: 2024

We are witnessing a widespread adoption of artificial intelligence in healthcare. However, most of the advancements in deep learning in this area consider only unimodal data, neglecting other modalities. Their multimodal interpretation necessary for supporting diagnosis, prognosis and treatment decisions. In this work we present a deep architecture, which jointly learns modality reconstructions and sample classifications using tabular and imaging data. The explanation of the decision taken is computed by applying a latent shift that, simulates a counterfactual prediction revealing the features of each modality that contribute the most to the decision and a quantitative score indicating the modality importance. We validate our approach in the context of COVID-19 pandemic using the AIforCOVID dataset, which contains multimodal data for the early identification of patients at risk of severe outcome. The results show that the proposed method provides meaningful explanations without degrading the classification performance.
$π$QLB: A Privacy-preserving with Integrity-assuring Query Language for Blockchain
Venue: arXiv cs.CR 2024
Year: 2024

The increase in the adoption of blockchain technology in different application domains e.g., healthcare systems, supplychain management, has raised the demand for a data query mechanism on blockchain. Since current blockchain systems lack the support for querying data with embedded security and privacy guarantees, there exists inherent security and privacy concerns on those systems. In particular, existing systems require users to submit queries to blockchain operators (e.g., a node validator) in plaintext. This directly jeopardizes users' privacy as the submitted queries may contain sensitive information, e.g., location or gender preferences, that the users may not be comfortable sharing. On the other hand, currently, the only way for users to ensure integrity of the query result is to maintain the entire blockchain database and perform the queries locally. Doing so incurs high storage and computational costs on the users, precluding this approach to be practically deployable on common light-weight devices (e.g., smartphones). To this end, this paper proposes $π$QLB, a query language for blockchain systems that ensures both confidentiality of query inputs and integrity of query results. Additionally, $π$QLB enables SQL-like queries over the blockchain data by introducing relational data semantics into the existing blockchain database. $π$QLB has applied the recent cryptography primitive, i.e., function secret sharing (FSS), to achieve confidentiality. To support integrity, we extend the traditional FSS setting in such a way that integrity of FSS results can be efficiently verified. Successful verification indicates absence of malicious behaviors on the servers, allowing the user to establish trust from the result. To the best of our knowledge, $π$QLB is the first query model designed for blockchain databases with support for confidentiality, integrity, and SQL-like queries.
An algorithm for clustering with confidence-based must-link and cannot-link constraints
Venue: arXiv cs.LG 2024
Year: 2024

We study here the semi-supervised $k$-clustering problem where information is available on whether pairs of objects are in the same or in different clusters. This information is either available with certainty or with a limited level of confidence. We introduce the PCCC (Pairwise-Confidence-Constraints-Clustering) algorithm, which iteratively assigns objects to clusters while accounting for the information provided on the pairs of objects. Our algorithm uses integer programming for the assignment of objects which allows to include relationships as hard constraints that are guaranteed to be satisfied or as soft constraints that can be violated subject to a penalty. This flexibility distinguishes our algorithm from the state-of-the-art in which all pairwise constraints are either considered hard, or all are considered soft. We developed an enhanced multi-start approach and a model-size reduction technique for the integer program that contributes to the effectiveness and the efficiency of the algorithm. Unlike existing algorithms, our algorithm scales to large-scale instances with up to 60,000 objects, 100 clusters, and millions of cannot-link constraints (which are the most challenging constraints to incorporate). We compare the PCCC algorithm with state-of-the-art approaches in an extensive computational study. Even though the PCCC algorithm is more general than the state-of-the-art approaches in its applicability, it outperforms the state-of-the-art approaches on instances with all hard or all soft constraints both in terms of runtime and various metrics of solution quality. The code of the PCCC algorithm is publicly available on GitHub.
Detecting Change Intervals with Isolation Distributional Kernel
Venue: arXiv cs.LG 2024
Year: 2024

Detecting abrupt changes in data distribution is one of the most significant tasks in streaming data analysis. Although many unsupervised Change-Point Detection (CPD) methods have been proposed recently to identify those changes, they still suffer from missing subtle changes, poor scalability, or/and sensitivity to outliers. To meet these challenges, we are the first to generalise the CPD problem as a special case of the Change-Interval Detection (CID) problem. Then we propose a CID method, named iCID, based on a recent Isolation Distributional Kernel (IDK). iCID identifies the change interval if there is a high dissimilarity score between two non-homogeneous temporal adjacent intervals. The data-dependent property and finite feature map of IDK enabled iCID to efficiently identify various types of change-points in data streams with the tolerance of outliers. Moreover, the proposed online and offline versions of iCID have the ability to optimise key parameter settings. The effectiveness and efficiency of iCID have been systematically verified on both synthetic and real-world datasets.
A Latent Space Correlation-Aware Autoencoder for Anomaly Detection in Skewed Data
Venue: arXiv cs.LG 2024
Year: 2024

Unsupervised learning-based anomaly detection in latent space has gained importance since discriminating anomalies from normal data becomes difficult in high-dimensional space. Both density estimation and distance-based methods to detect anomalies in latent space have been explored in the past. These methods prove that retaining valuable properties of input data in latent space helps in the better reconstruction of test data. Moreover, real-world sensor data is skewed and non-Gaussian in nature, making mean-based estimators unreliable for skewed data. Again, anomaly detection methods based on reconstruction error rely on Euclidean distance, which does not consider useful correlation information in the feature space and also fails to accurately reconstruct the data when it deviates from the training distribution. In this work, we address the limitations of reconstruction error-based autoencoders and propose a kernelized autoencoder that leverages a robust form of Mahalanobis distance (MD) to measure latent dimension correlation to effectively detect both near and far anomalies. This hybrid loss is aided by the principle of maximizing the mutual information gain between the latent dimension and the high-dimensional prior data space by maximizing the entropy of the latent space while preserving useful correlation information of the original data in the low-dimensional latent space. The multi-objective function has two goals -- it measures correlation information in the latent feature space in the form of robust MD distance and simultaneously tries to preserve useful correlation information from the original data space in the latent space by maximizing mutual information between the prior and latent space.
Honeypot Implementation in a Cloud Environment
Venue: arXiv cs.CR 2024
Year: 2024

In this age of digitalization, Internet services face more attacks than ever. An attacker's objective is to exploit systems and use them for malicious purposes. Such efforts are rising as vulnerable systems can be discovered and compromised through Internet-wide scanning. One known methodology besides traditional security leverages is to learn from those who attack it. A honeypot helps to collect information about an attacker by pretending to be a vulnerable target. Thus, how honeypots can contribute to a more secure infrastructure makes an interesting topic of research. This thesis will present a honeypot solution to investigate malicious activities in heiCLOUD and show that attacks have increased significantly. To detect attackers in restricted network zones at Heidelberg University, a new concept to discover leaks in the firewall will be created. Furthermore, to consider an attacker's point of view, a method for detecting honeypots at the transport level will be introduced. Lastly, a customized OpenSSH server that works as an intermediary instance will be presented to mitigate these efforts.
Informed Down-Sampled Lexicase Selection: Identifying productive training cases for efficient problem solving
Venue: arXiv cs.NE 2024
Year: 2024

Genetic Programming (GP) often uses large training sets and requires all individuals to be evaluated on all training cases during selection. Random down-sampled lexicase selection evaluates individuals on only a random subset of the training cases allowing for more individuals to be explored with the same amount of program executions. However, creating a down-sample randomly might exclude important cases from the current down-sample for a number of generations, while cases that measure the same behavior (synonymous cases) may be overused despite their redundancy. In this work, we introduce Informed Down-Sampled Lexicase Selection. This method leverages population statistics to build down-samples that contain more distinct and therefore informative training cases. Through an empirical investigation across two different GP systems (PushGP and Grammar-Guided GP), we find that informed down-sampling significantly outperforms random down-sampling on a set of contemporary program synthesis benchmark problems. Through an analysis of the created down-samples, we find that important training cases are included in the down-sample consistently across independent evolutionary runs and systems. We hypothesize that this improvement can be attributed to the ability of Informed Down-Sampled Lexicase Selection to maintain more specialist individuals over the course of evolution, while also benefiting from reduced per-evaluation costs.
Beyond Inverted Pendulums: Task-optimal Simple Models of Legged Locomotion
Venue: arXiv cs.RO 2024
Year: 2024

Reduced-order models (ROM) are popular in online motion planning due to their simplicity. A good ROM for control captures critical task-relevant aspects of the full dynamics while remaining low dimensional. However, planning within the reduced-order space unavoidably constrains the full model, and hence we sacrifice the full potential of the robot. In the community of legged locomotion, this has lead to a search for better model extensions, but many of these extensions require human intuition, and there has not existed a principled way of evaluating the model performance and discovering new models. In this work, we propose a model optimization algorithm that automatically synthesizes reduced-order models, optimal with respect to a user-specified distribution of tasks and corresponding cost functions. To demonstrate our work, we optimized models for a bipedal robot Cassie. We show in simulation that the optimal ROM reduces the cost of Cassie's joint torques by up to 23% and increases its walking speed by up to 54%. We also show hardware result that the real robot walks on flat ground with 10% lower torque cost. All videos and code can be found at https://sites.google.com/view/ymchen/research/optimal-rom.
TrojanPuzzle: Covertly Poisoning Code-Suggestion Models
Venue: arXiv cs.CR 2024
Year: 2024

With tools like GitHub Copilot, automatic code suggestion is no longer a dream in software engineering. These tools, based on large language models, are typically trained on massive corpora of code mined from unvetted public sources. As a result, these models are susceptible to data poisoning attacks where an adversary manipulates the model's training by injecting malicious data. Poisoning attacks could be designed to influence the model's suggestions at run time for chosen contexts, such as inducing the model into suggesting insecure code payloads. To achieve this, prior attacks explicitly inject the insecure code payload into the training data, making the poison data detectable by static analysis tools that can remove such malicious data from the training set. In this work, we demonstrate two novel attacks, COVERT and TROJANPUZZLE, that can bypass static analysis by planting malicious poison data in out-of-context regions such as docstrings. Our most novel attack, TROJANPUZZLE, goes one step further in generating less suspicious poison data by never explicitly including certain (suspicious) parts of the payload in the poison data, while still inducing a model that suggests the entire payload when completing code (i.e., outside docstrings). This makes TROJANPUZZLE robust against signature-based dataset-cleansing methods that can filter out suspicious sequences from the training data. Our evaluation against models of two sizes demonstrates that both COVERT and TROJANPUZZLE have significant implications for practitioners when selecting code used to train or tune code-suggestion models.
Assigning Agents to Increase Network-Based Neighborhood Diversity
Venue: arXiv cs.DS 2024
Year: 2024

Motivated by real-world applications such as the allocation of public housing, we examine the problem of assigning a group of agents to vertices (e.g., spatial locations) of a network so that the diversity level is maximized. Specifically, agents are of two types (characterized by features), and we measure diversity by the number of agents who have at least one neighbor of a different type. This problem is known to be NP-hard, and we focus on developing approximation algorithms with provable performance guarantees. We first present a local-improvement algorithm for general graphs that provides an approximation factor of 1/2. For the special case where the sizes of agent subgroups are similar, we present a randomized approach based on semidefinite programming that yields an approximation factor better than 1/2. Further, we show that the problem can be solved efficiently when the underlying graph is treewidth-bounded and obtain a polynomial time approximation scheme (PTAS) for the problem on planar graphs. Lastly, we conduct experiments to evaluate the per-performance of the proposed algorithms on synthetic and real-world networks.
Representing Matroids over the Reals is $\exists \mathbb R$-complete
Venue: arXiv cs.CC 2024
Year: 2024

A matroid $M$ is an ordered pair $(E,I)$, where $E$ is a finite set called the ground set and a collection $I\subset 2^{E}$ called the independent sets which satisfy the conditions: (i) $\emptyset \in I$, (ii) $I'\subset I \in I$ implies $I'\in I$, and (iii) $I_1,I_2 \in I$ and $|I_1| < |I_2|$ implies that there is an $e\in I_2$ such that $I_1\cup \{e\} \in I$. The rank $rank(M)$ of a matroid $M$ is the maximum size of an independent set. We say that a matroid $M=(E,I)$ is representable over the reals if there is a map $φ\colon E \rightarrow \mathbb{R}^{rank(M)}$ such that $I\in I$ if and only if $φ(I)$ forms a linearly independent set. We study the problem of matroid realizability over the reals. Given a matroid $M$, we ask whether there is a set of points in the Euclidean space representing $M$. We show that matroid realizability is $\exists \mathbb R$-complete, already for matroids of rank 3. The complexity class $\exists \mathbb R$ can be defined as the family of algorithmic problems that is polynomial-time is equivalent to determining if a multivariate polynomial with integers coefficients has a real root. Our methods are similar to previous methods from the literature. Yet, the result itself was never pointed out and there is no proof readily available in the language of computer science.
Toward an AI-enabled Connected Industry: AGV Communication and Sensor Measurement Datasets
Venue: arXiv cs.NI 2024
Year: 2024

This paper presents two wireless measurement campaigns in industrial testbeds: industrial Vehicle-to-vehicle (iV2V) and industrial Vehicle-to-infrastructure plus Sensor (iV2I+), together with detailed information about the two captured datasets. iV2V covers sidelink communication scenarios between Automated Guided Vehicles (AGVs), while iV2I+ is conducted at an industrial setting where an autonomous cleaning robot is connected to a private cellular network. The combination of different communication technologies within a common measurement methodology provides insights that can be exploited by Machine Learning (ML) for tasks such as fingerprinting, line-of-sight detection, prediction of quality of service or link selection. Moreover, the datasets are publicly available, labelled and prefiltered for fast on-boarding and applicability.
The Algebra of Nondeterministic Finite Automata
Venue: arXiv cs.FL 2024
Year: 2024

A process algebra is proposed, whose semantics maps a term to a nondeterministic finite automaton (NFA, for short). We prove a representability theorem: for each NFA $N$, there exists a process algebraic term $p$ such that its semantics is an NFA isomorphic to $N$. Moreover, we provide a concise axiomatization of language equivalence: two NFAs $N_1$ and $N_2$ recognize the same language if and only if the associated terms $p_1$ and $p_2$, respectively, can be equated by means of a set of axioms, comprising 7 axioms plus 3 conditional axioms, only.
Toward Multi-Layer Networking for Satellite Network Operations
Venue: arXiv cs.NI 2024
Year: 2024

Recent advancements in low-Earth-orbit (LEO) satellites aim to bring resilience, ubiquitous, and high-quality service to future Internet infrastructure. However, the soaring number of space assets, increasing dynamics of LEO satellites and expanding dimensions of network threats call for an enhanced approach to efficient satellite operations. To address these pressing challenges, we propose an approach for satellite network operations based on multi-layer satellite networking (MLSN), called "SatNetOps". Two SatNetOps schemes are proposed, referred to as LEO-LEO MLSN (LLM) and GEO-LEO MLSN (GLM). The performance of the proposed schemes is evaluated in 24-hr satellite scenarios with typical payload setups in simulations, where the key metrics such as latency and reliability are discussed with the consideration of the Consultative Committee for Space Data Systems (CCSDS) standard-compliant telemetry and telecommand missions. Although the SatNetOps approach is promising, we analyze the factors affecting the performance of the LLM and GLM schemes. The discussions on the results and conclusive remarks are made in the end.
Transfer learning for conflict and duplicate detection in software requirement pairs
Venue: arXiv cs.SE 2024
Year: 2024

Consistent and holistic expression of software requirements is important for the success of software projects. In this study, we aim to enhance the efficiency of the software development processes by automatically identifying conflicting and duplicate software requirement specifications. We formulate the conflict and duplicate detection problem as a requirement pair classification task. We design a novel transformers-based architecture, SR-BERT, which incorporates Sentence-BERT and Bi-encoders for the conflict and duplicate identification task. Furthermore, we apply supervised multi-stage fine-tuning to the pre-trained transformer models. We test the performance of different transfer models using four different datasets. We find that sequentially trained and fine-tuned transformer models perform well across the datasets with SR-BERT achieving the best performance for larger datasets. We also explore the cross-domain performance of conflict detection models and adopt a rule-based filtering approach to validate the model classifications. Our analysis indicates that the sentence pair classification approach and the proposed transformer-based natural language processing strategies can contribute significantly to achieving automation in conflict and duplicate detection
Contact graphs of boxes with unidirectional contacts
Venue: arXiv cs.DM 2024
Year: 2024

This paper is devoted to the study of particular geometrically defined intersection classes of graphs. Those were previously studied by Magnant and Martin, who proved that these graphs have arbitrary large chromatic number, while being triangle-free. We give several structural properties of these graphs, and we raise several questions.
Maximum Centre-Disjoint Mergeable Disks
Venue: arXiv cs.CG 2024
Year: 2024

Given a set of disks in the plane, the goal of the problem studied in this paper is to choose a subset of these disks such that none of its members contains the centre of any other. Each disk not in this subset must be merged with one of its nearby disks that is, increasing the latter's radius. This problem has applications in labelling rotating maps and in visualizing the distribution of entities in static maps. We prove that this problem is NP-hard. We also present an ILP formulation for this problem, and a polynomial-time algorithm for the special case in which the centres of all disks are on a line.