OpenRaiser/Intern-Atlas huggingface dataset:
Attack detection based on machine learning algorithms for different variants of Spectre attacks and different Meltdown attack implementations
Venue: arXiv cs.CR 2022
Year: 2022

To improve the overall performance of processors, computer architects use various performance optimization techniques in modern processors, such as speculative execution, branch prediction, and chaotic execution. Both now and in the future, these optimization techniques are critical for improving the execution speed of processor instructions. However, researchers have discovered that these techniques introduce hidden inherent security flaws, such as meltdown and ghost attacks in recent years. They exploit techniques such as chaotic execution or speculative execution combined with cache-based side-channel attacks to leak protected data. The impact of these vulnerabilities is enormous because they are prevalent in existing or future processors. However, until today, meltdown and ghost have not been effectively addressed, but instead, multiple attack variants and different attack implementations have evolved from them. This paper proposes to optimize four different hardware performance events through feature selection and use machine learning algorithms to build a real-time detection mechanism for Spectre v1,v2,v4, and different implementations of meltdown attacks, ultimately achieving an accuracy rate of over 99\%. In order to verify the practicality of the attack detection model, this paper is tested with a variety of benign programs and different implementations of Spectre attacks different from the modeling process, and the absolute accuracy also exceeds 99\%, showing that this paper can cope with different attack variants and different implementations of the same attack that may occur daily.
The Role of Feedback in AoI Optimization Under Limited Transmission Opportunities
Venue: arXiv cs.IT 2022
Year: 2022

Scheduling updates from remote sensors is a key task for the internet of things (IoT). In this context, the mathematical concept of age of information is often used to capture the freshness of received data. This is, in turn, relevant to optimize the frequency of the exchanges, especially for resource constrained (e.g., energy-limited) sensors. Most investigations on the subject assume that the transmitter can leverage knowledge of the age of information at the receiver side to decide when to send data, even when the communication channel is unreliable. In reality, tracking the outcome of the updates would require additional consumption of resources to acquire a feedback. We investigate the optimal schedule of updates over a finite time horizon for a resource-constrained sensor that is allowed to perform a limited number of updates, as typical of IoT devices. We discuss the role of the feedback from the receiver, and whether it is convenient to ask for it whenever this causes additional energy consumption and consequently allows the transmission of a lower number of updates. We analytically identify regions for the feedback cost and the reliability of the channel where making use of feedback may or may not be beneficial.
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
Venue: arXiv cs.DS 2022
Year: 2022

We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system $(V,\mathcal{F},\mathcal{B})$ with two families $\mathcal{F},\mathcal{B}$ of subsets of $V$. The task is to find a hitting set for $\mathcal{F}$ that minimizes the maximum number of elements in any of the sets of $\mathcal{B}$. Our focus is on determining the complexity of some special cases of Sparse-HS with respect to the sparseness $k$, which is the optimum number of hitting set elements in any set of $\mathcal{B}$. For the Sparse Vertex Cover (Sparse-VC) problem, $V$ is given by the vertex set of a graph, and $\mathcal{F}$ is its edge set. We prove NP-hardness for sparseness $k\geq 2$ and polynomial time solvability for $k=1$. We also provide a polynomial-time $2$-approximation for any $k$. A special case of Sparse-VC is Fair Vertex Cover (Fair-VC), where the family $\mathcal{B}$ is given by vertex neighbourhoods. For this problem we prove NP-hardness for constant $k$ and provide a polynomial-time $(2-\frac{1}{k})$-approximation. This is better than any approximation possible for Sparse-VC or Vertex Cover (under UGC). We then consider two problems derived from Sparse-HS related to the highway dimension, a graph parameter modelling transportation networks. Most algorithms for graphs of low highway dimension compute solutions to the $r$-Shortest Path Cover ($r$-SPC) problem, where $r>0$, $\mathcal{F}$ contains all shortest paths of length between $r$ and $2r$, and $\mathcal{B}$ contains all balls of radius $2r$. There is an XP algorithm that computes solutions to $r$-SPC of sparseness at most $h$ if the input graph has highway dimension $h$, but the existence if an FPT algorithm was open. We prove that $r$-SPC and also the related $r$-Highway Dimension ($r$-HD) problem are both W[1]-hard. Furthermore, we prove that $r$-SPC admits a polynomial-time $O(\log n)$-approximation.
Building the Learning Environment for Sustainable Development: a Co-creation approach
Venue: arXiv cs.CY 2022
Year: 2022

Education for sustainable development supports the improvement of knowledge, skills, attitudes and behaviors related to global challenges such as climate change, global warming and environmental degradation, among others. It is increasingly taking place through projects based on information and communication technologies. The effectiveness of the actions taken depends not only on the quality of the project activities or the sophistication of the innovative tools used. Social commitment also depends on the beliefs and moral judgements manifested by potential recipients of educational activities on environmental issues. This study aimed to identify the beliefs and moral judgements that may facilitate or hinder the implementation of educational activities based on information and communication technology, shaping pro-environmental attitudes and behavior among city dwellers. Based on the co-creation workshops conducted, five general categories emerged: responsibility, sense of empowerment, local leadership, real eco-approach, and eco-knowledge. The research findings may contribute to the design of educational activities dedicated to shaping the pro-environmental behavior of city dwellers.
FuncFooler: A Practical Black-box Attack Against Learning-based Binary Code Similarity Detection Methods
Venue: arXiv cs.CR 2022
Year: 2022

The binary code similarity detection (BCSD) method measures the similarity of two binary executable codes. Recently, the learning-based BCSD methods have achieved great success, outperforming traditional BCSD in detection accuracy and efficiency. However, the existing studies are rather sparse on the adversarial vulnerability of the learning-based BCSD methods, which cause hazards in security-related applications. To evaluate the adversarial robustness, this paper designs an efficient and black-box adversarial code generation algorithm, namely, FuncFooler. FuncFooler constrains the adversarial codes 1) to keep unchanged the program's control flow graph (CFG), and 2) to preserve the same semantic meaning. Specifically, FuncFooler consecutively 1) determines vulnerable candidates in the malicious code, 2) chooses and inserts the adversarial instructions from the benign code, and 3) corrects the semantic side effect of the adversarial code to meet the constraints. Empirically, our FuncFooler can successfully attack the three learning-based BCSD models, including SAFE, Asm2Vec, and jTrans, which calls into question whether the learning-based BCSD is desirable.
Learned k-NN Distance Estimation
Venue: arXiv cs.DB 2022
Year: 2022

Big data mining is well known to be an important task for data science, because it can provide useful observations and new knowledge hidden in given large datasets. Proximity-based data analysis is particularly utilized in many real-life applications. In such analysis, the distances to k nearest neighbors are usually employed, thus its main bottleneck is derived from data retrieval. Much efforts have been made to improve the efficiency of these analyses. However, they still incur large costs, because they essentially need many data accesses. To avoid this issue, we propose a machine-learning technique that quickly and accurately estimates the k-NN distances (i.e., distances to the k nearest neighbors) of a given query. We train a fully connected neural network model and utilize pivots to achieve accurate estimation. Our model is designed to have useful advantages: it infers distances to the k-NNs at a time, its inference time is O(1) (no data accesses are incurred), but it keeps high accuracy. Our experimental results and case studies on real datasets demonstrate the efficiency and effectiveness of our solution.
AVMiner: Expansible and Semantic-Preserving Anti-Virus Labels Mining Method
Venue: arXiv cs.CR 2022
Year: 2022

With the increase in the variety and quantity of malware, there is an urgent need to speed up the diagnosis and the analysis of malware. Extracting the malware family-related tokens from AV (Anti-Virus) labels, provided by online anti-virus engines, paves the way for pre-diagnosing the malware. Automatically extract the vital information from AV labels will greatly enhance the detection ability of security enterprises and equip the research ability of security analysts. Recent works like AVCLASS and AVCLASS2 try to extract the attributes of malware from AV labels and establish the taxonomy based on expert knowledge. However, due to the uncertain trend of complicated malicious behaviors, the system needs the following abilities to face the challenge: preserving vital semantics, being expansible, and free from expert knowledge. In this work, we present AVMiner, an expansible malware tagging system that can mine the most vital tokens from AV labels. AVMiner adopts natural language processing techniques and clustering methods to generate a sequence of tokens without expert knowledge ranked by importance. AVMiner can self-update when new samples come. Finally, we evaluate AVMiner on over 8,000 samples from well-known datasets with manually labeled ground truth, which outperforms previous works.
Multi-Hop Network with Multiple Decision Centers under Expected-Rate Constraints
Venue: arXiv cs.IT 2022
Year: 2022

We consider a multi-hop distributed hypothesis testing problem with multiple decision centers (DCs) for testing against independence and where the observations obey some Markov chain. For this system, we characterize the fundamental type-II error exponents region, i.e., the type-II error exponents that the various DCs can achieve simultaneously, under expected rate-constraints. Our results show that this fundamental exponents region is boosted compared to the region under maximum-rate constraints, and that it depends on the permissible type-I error probabilities. When all DCs have equal permissible type-I error probabilities, the exponents region is rectangular and all DCs can simultaneously achieve their optimal type-II error exponents. When the DCs have different permissible type-I error probabilities, a tradeoff between the type-II error exponents at the different DCs arises. New achievability and converse proofs are presented. For the achievability, a new multiplexing and rate-sharing strategy is proposed. The converse proof is based on applying different change of measure arguments in parallel and on proving asymptotic Markov chains. For the special cases $K = 2$ and $K = 3$, we provide simplified expressions for the exponents region; a similar simplification is conjectured for arbitrary $K\geq 2$.
Program Equivalence in an Untyped, Call-by-value Lambda Calculus with Uncurried Recursive Functions
Venue: arXiv cs.PL 2022
Year: 2022

We aim to reason about the correctness of behaviour-preserving transformations of Erlang programs. Behaviour preservation is characterised by semantic equivalence. Based upon our existing formal semantics for Core Erlang, we investigate potential definitions of suitable equivalence relations. In particular we adapt a number of existing approaches of expression equivalence to a simple functional programming language that carries the main features of sequential Core Erlang; we then examine the properties of the equivalence relations and formally establish connections between them. The results presented in this paper, including all theorems and their proofs, have been machine checked using the Coq proof assistant.
Controllable 3D Generative Adversarial Face Model via Disentangling Shape and Appearance
Venue: arXiv cs.CV 2022
Year: 2022

3D face modeling has been an active area of research in computer vision and computer graphics, fueling applications ranging from facial expression transfer in virtual avatars to synthetic data generation. Existing 3D deep learning generative models (e.g., VAE, GANs) allow generating compact face representations (both shape and texture) that can model non-linearities in the shape and appearance space (e.g., scatter effects, specularities, etc.). However, they lack the capability to control the generation of subtle expressions. This paper proposes a new 3D face generative model that can decouple identity and expression and provides granular control over expressions. In particular, we propose using a pair of supervised auto-encoder and generative adversarial networks to produce high-quality 3D faces, both in terms of appearance and shape. Experimental results in the generation of 3D faces learned with holistic expression labels, or Action Unit labels, show how we can decouple identity and expression; gaining fine-control over expressions while preserving identity.
Approximation Algorithms for Drone Delivery Packing Problem
Venue: arXiv cs.DS 2022
Year: 2022

Recent advancements in unmanned aerial vehicles, also known as drones, have motivated logistics to use drones for multiple operations. Collaboration between drones and trucks in a last-mile delivery system has numerous benefits and reduces a number of challenges. In this paper, we introduce \textit{drone-delivery packing problem} (DDP), where we have a set of deliveries and respective customers with their prescribed locations, delivery time intervals, associated cost for deliveries, and a set of drones with identical battery budgets. The objective of the DDP is to find an assignment for all deliveries to the drones by using the minimum number of drones subject to the battery budget and compatibility of the assignment of each drone. We prove that DDP is NP-Hard and formulate the integer linear programming (ILP) formulation for it. We proposed two greedy approximation algorithms for DDP. The first algorithm uses at most $2OPT + (Δ+ 1)$ drones. The second algorithm uses at most $2OPT + ω$ drones, where OPT is the optimum solution for DDP, $ω$ is the maximum clique size, and $Δ$ is the maximum degree of the interval graph $G$ constructed from the delivery time intervals.
Analysis of Distributed Deep Learning in the Cloud
Venue: arXiv cs.LG 2022
Year: 2022

We aim to resolve this problem by introducing a comprehensive distributed deep learning (DDL) profiler, which can determine the various execution "stalls" that DDL suffers from while running on a public cloud. We have implemented the profiler by extending prior work to additionally estimate two types of communication stalls - interconnect and network stalls. We train popular DNN models using the profiler to characterize various AWS GPU instances and list their advantages and shortcomings for users to make an informed decision. We observe that the more expensive GPU instances may not be the most performant for all DNN models and AWS may sub-optimally allocate hardware interconnect resources. Specifically, the intra-machine interconnect can introduce communication overheads up to 90% of DNN training time and network-connected instances can suffer from up to 5x slowdown compared to training on a single instance. Further, we model the impact of DNN macroscopic features such as the number of layers and the number of gradients on communication stalls. Finally, we propose a measurement-based recommendation model for users to lower their public cloud monetary costs for DDL, given a time budget.
Towards robust music source separation on loud commercial music
Venue: arXiv cs.SD 2022
Year: 2022

Nowadays, commercial music has extreme loudness and heavily compressed dynamic range compared to the past. Yet, in music source separation, these characteristics have not been thoroughly considered, resulting in the domain mismatch between the laboratory and the real world. In this paper, we confirmed that this domain mismatch negatively affect the performance of the music source separation networks. To this end, we first created the out-of-domain evaluation datasets, musdb-L and XL, by mimicking the music mastering process. Then, we quantitatively verify that the performance of the state-of-the-art algorithms significantly deteriorated in our datasets. Lastly, we proposed LimitAug data augmentation method to reduce the domain mismatch, which utilizes an online limiter during the training data sampling process. We confirmed that it not only alleviates the performance degradation on our out-of-domain datasets, but also results in higher performance on in-domain data.
Explaining Ontology-Mediated Query Answers using Proofs over Universal Models (Technical Report)
Venue: arXiv cs.LO 2022
Year: 2022

In ontology-mediated query answering, access to incomplete data sources is mediated by a conceptual layer constituted by an ontology, which can be formulated in a description logic (DL) or using existential rules. In the literature, there exists a multitude of complex techniques for incorporating ontological knowledge into queries. However, few of these approaches were designed for explainability of the query answers. We tackle this challenge by adapting an existing proof framework toward conjunctive query answering, based on the notion of universal models. We investigate the data and combined complexity of determining the existence of a proof below a given quality threshold, which can be measured in different ways. By distinguishing various parameters such as the shape of the query, we obtain an overview of the complexity of this problem for several Horn DLs.
k-MS: A novel clustering algorithm based on morphological reconstruction
Venue: arXiv cs.LG 2022
Year: 2022

This work proposes a clusterization algorithm called k-Morphological Sets (k-MS), based on morphological reconstruction and heuristics. k-MS is faster than the CPU-parallel k-Means in worst case scenarios and produces enhanced visualizations of the dataset as well as very distinct clusterizations. It is also faster than similar clusterization methods that are sensitive to density and shapes such as Mitosis and TRICLUST. In addition, k-MS is deterministic and has an intrinsic sense of maximal clusters that can be created for a given input sample and input parameters, differing from k-Means and other clusterization algorithms. In other words, given a constant k, a structuring element and a dataset, k-MS produces k or less clusters without using random/ pseudo-random functions. Finally, the proposed algorithm also provides a straightforward means for removing noise from images or datasets in general.
Biased Bytes: On the Validity of Estimating Food Consumption from Digital Traces
Venue: arXiv cs.SI 2022
Year: 2022

Given that measuring food consumption at a population scale is a challenging task, researchers have begun to explore digital traces (e.g., from social media or from food-tracking applications) as potential proxies. However, it remains unclear to what extent digital traces reflect real food consumption. The present study aims to bridge this gap by quantifying the link between dietary behaviors as captured via social media (Twitter) v.s. a food-tracking application (MyFoodRepo). We focus on the case of Switzerland and contrast images of foods collected through the two platforms, by designing and deploying a novel crowdsourcing framework for estimating biases with respect to nutritional properties and appearance. We find that the food type distributions in social media v.s. food tracking diverge; e.g., bread is 2.5 times more frequent among consumed and tracked foods than on Twitter, whereas cake is 12 times more frequent on Twitter. Controlling for the different food type distributions, we contrast consumed and tracked foods of a given type with foods shared on Twitter. Across food types, food posted on Twitter is perceived as tastier, more caloric, less healthy, less likely to have been consumed at home, more complex, and larger-portioned, compared to consumed and tracked foods. The fact that there is a divergence between food consumption as measured via the two platforms implies that at least one of the two is not a faithful representation of the true food consumption in the general Swiss population. Thus, researchers should be attentive and aim to establish evidence of validity before using digital traces as a proxy for the true food consumption of a general population. We conclude by discussing the potential sources of these biases and their implications, outlining pitfalls and threats to validity, and proposing actionable ways for overcoming them.
Several classes of optimal $p$-ary cyclic codes with minimal distance four
Venue: arXiv cs.IT 2022
Year: 2022

Cyclic codes are a subclass of linear codes and have wide applications in data storage systems, communication systems and consumer electronics due to their efficient encoding and decoding algorithms. Let $p\ge 5$ be an odd prime and $m$ be a positive integer. Let $\mathcal{C}_{(1,e,s)}$ denote the $p$-ary cyclic code with three nonzeros $α$, $α^e$, and $α^s$, where $α$ is a generator of ${\mathbb F}_{p^m}^*$, $s=\frac{p^m-1}{2}$, and $2\le e\le p^m-2$. In this paper, we present four classes of optimal $p$-ary cyclic codes $\mathcal{C}_{(1,e,s)}$ with parameters $[p^m-1,p^m-2m-2,4]$ by analyzing the solutions of certain polynomials over finite fields. Some previous results about optimal quinary cyclic codes with parameters $[5^m-1,5^m-2m-2,4]$ are special cases of our constructions. In addition, by analyzing the irreducible factors of certain polynomials over ${\mathbb F}_{5^m}$, we present two classes of optimal quinary cyclic codes $\mathcal{C}_{(1,e,s)}$.
Correct-by-Construction Runtime Enforcement in AI -- A Survey
Venue: arXiv cs.AI 2022
Year: 2022

Runtime enforcement refers to the theories, techniques, and tools for enforcing correct behavior with respect to a formal specification of systems at runtime. In this paper, we are interested in techniques for constructing runtime enforcers for the concrete application domain of enforcing safety in AI. We discuss how safety is traditionally handled in the field of AI and how more formal guarantees on the safety of a self-learning agent can be given by integrating a runtime enforcer. We survey a selection of work on such enforcers, where we distinguish between approaches for discrete and continuous action spaces. The purpose of this paper is to foster a better understanding of advantages and limitations of different enforcement techniques, focusing on the specific challenges that arise due to their application in AI. Finally, we present some open challenges and avenues for future work.