OpenRaiser/Intern-Atlas huggingface dataset:
$μ$AFL: Non-intrusive Feedback-driven Fuzzing for Microcontroller Firmware
Venue: arXiv cs.CR 2022
Year: 2022

Fuzzing is one of the most effective approaches to finding software flaws. However, applying it to microcontroller firmware incurs many challenges. For example, rehosting-based solutions cannot accurately model peripheral behaviors and thus cannot be used to fuzz the corresponding driver code. In this work, we present $μ$AFL, a hardware-in-the-loop approach to fuzzing microcontroller firmware. It leverages debugging tools in existing embedded system development to construct an AFL-compatible fuzzing framework. Specifically, we use the debug dongle to bridge the fuzzing environment on the PC and the target firmware on the microcontroller device. To collect code coverage information without costly code instrumentation, $μ$AFL relies on the ARM ETM hardware debugging feature, which transparently collects the instruction trace and streams the results to the PC. However, the raw ETM data is obscure and needs enormous computing resources to recover the actual instruction flow. We therefore propose an alternative representation of code coverage, which retains the same path sensitivity as the original AFL algorithm, but can directly work on the raw ETM data without matching them with disassembled instructions. To further reduce the workload, we use the DWT hardware feature to selectively collect runtime information of interest. We evaluated $μ$AFL on two real evaluation boards from two major vendors: NXP and STMicroelectronics. With our prototype, we discovered ten zero-day bugs in the driver code shipped with the SDK of STMicroelectronics and three zero-day bugs in the SDK of NXP. Eight CVEs have been allocated for them. Considering the wide adoption of vendor SDKs in real products, our results are alarming.
Broadcast Approach Meets Network Coding for Data Streaming
Venue: arXiv cs.IT 2022
Year: 2022

For data streaming applications, existing solutions are not yet able to close the gap between high data rates and low delay. This work considers the problem of data streaming under mixed delay constraints over a single communication channel with delayed feedback. We propose a novel layered adaptive causal random linear network coding (LAC-RLNC) approach with forward error correction. LAC-RLNC is a variable-to-variable coding scheme, i.e., variable recovered information data at the receiver over variable short block length and rate is proposed. Specifically, for data streaming with base and enhancement layers of content, we characterize a high dimensional throughput-delay trade-off managed by the adaptive causal layering coding scheme. The base layer is designed to satisfy the strict delay constraints, as it contains the data needed to allow the streaming service. Then, the sender can manage the throughput-delay trade-off of the second layer by adjusting the retransmission rate a priori and posterior as the enhancement layer, that contains the remaining data to augment the streaming service's quality, is with the relax delay constraints. We numerically show that the layered network coding approach can dramatically increase performance. We demonstrate that LAC-RLNC compared with the non-layered approach gains a factor of three in mean and maximum delay for the base layer, close to the lower bound, and factor two for the enhancement layer.
The Input and Output Entropies of the $k$-Deletion/Insertion Channel
Venue: arXiv cs.IT 2022
Year: 2022

The channel output entropy of a transmitted word is the entropy of the possible channel outputs and similarly, the input entropy of a received word is the entropy of all possible transmitted words. The goal of this work is to study these entropy values for the k-deletion, k-insertion channel, where exactly k symbols are deleted, and inserted in the transmitted word, respectively. If all possible words are transmitted with the same probability then studying the input and output entropies is equivalent. For both the 1-insertion and 1-deletion channels, it is proved that among all words with a fixed number of runs, the input entropy is minimized for words with a skewed distribution of their run lengths and it is maximized for words with a balanced distribution of their run lengths. Among our results, we establish a conjecture by Atashpendar et al. which claims that for the binary 1-deletion, the input entropy is maximized for the alternating words. This conjecture is also verified for the 2-deletion channel, where it is proved that constant words with a single run minimize the input entropy.
Towards Learning Through Open-Domain Dialog
Venue: arXiv cs.CL 2022
Year: 2022

The development of artificial agents able to learn through dialog without domain restrictions has the potential to allow machines to learn how to perform tasks in a similar manner to humans and change how we relate to them. However, research in this area is practically nonexistent. In this paper, we identify the modifications required for a dialog system to be able to learn from the dialog and propose generic approaches that can be used to implement those modifications. More specifically, we discuss how knowledge can be extracted from the dialog, used to update the agent's semantic network, and grounded in action and observation. This way, we hope to raise awareness for this subject, so that it can become a focus of research in the future.
Metric-valued regression
Venue: arXiv cs.LG 2022
Year: 2022

We propose an efficient algorithm for learning mappings between two metric spaces, $\X$ and $\Y$. Our procedure is strongly Bayes-consistent whenever $\X$ and $\Y$ are topologically separable and $\Y$ is "bounded in expectation" (our term; the separability assumption can be somewhat weakened). At this level of generality, ours is the first such learnability result for unbounded loss in the agnostic setting. Our technique is based on metric medoids (a variant of Fréchet means) and presents a significant departure from existing methods, which, as we demonstrate, fail to achieve Bayes-consistency on general instance- and label-space metrics. Our proofs introduce the technique of {\em semi-stable compression}, which may be of independent interest.
Edge-computing Enabled Next Generation Wireless Networks: A Novel Approach to Provide Secure Multicast Services
Venue: arXiv cs.NI 2022
Year: 2022

Smart grids have received much attention in recent years in order to optimally manage the resources, transmission and consumption of electric power.In these grids, one of the most important communication services is the multicast service. Providing multicast services in the smart communicative grid poses several challenges, including the heterogeneity of different communication media and the strict requirements of reliability, security and latency. Wireless technologies and PLC connections are the two most important media used in this grid, among which PLC connections are very unstable, which makes it difficult to provide reliability. In this research, the problem of geographically flooding of multicast data has been considered. First, this problem has been modeled as an optimization problem which is used as a reference model in evaluating the proposed approaches. Then, two MKMB and GCBT multicast tree formation algorithms have been developed based on geographical information according to the characteristics of smart grids. Comparison of these two approaches shows the advantages and disadvantages of forming a core-based tree compared to a source-based tree. Evaluation of these approaches shows a relative improvement in tree cost and the amount of end-to-end delay compared to basic algorithms. In the second part, providing security and reliability in data transmission has been considered. Both Hybrid and Multiple algorithms have been developed based on the idea of multiple transmission tree. In the Hybrid algorithm, the aim is to provide higher security and reliability, but in the Multiple algorithms, minimization of message transmission delay is targeted. In the section of behavior evaluation, these two algorithms have been studied in different working conditions, which indicates the achievement of the desired goals.
Modular representation and control of floppy networks
Venue: arXiv cs.RO 2022
Year: 2022

Geometric graph models of systems as diverse as proteins, robots, and mechanical structures from DNA assemblies to architected materials point towards a unified way to represent and control them in space and time. While much work has been done in the context of characterizing the behavior of these networks close to critical points associated with bond and rigidity percolation, isostaticity, etc., much less is known about floppy, under-constrained networks that are far more common in nature and technology. Here we combine geometric rigidity and algebraic sparsity to provide a framework for identifying the zero-energy floppy modes via a representation that illuminates the underlying hierarchy and modularity of the network, and thence the control of its nestedness and locality. Our framework allows us to demonstrate a range of applications of this approach that include robotic reaching tasks with motion primitives, and predicting the linear and nonlinear response of elastic networks based solely on infinitesimal rigidity and sparsity, which we test using physical experiments. Our approach is thus likely to be of use broadly in dissecting the geometrical properties of floppy networks using algebraic sparsity to optimize their function and performance.
Approaches to Artificial General Intelligence: An Analysis
Venue: arXiv cs.AI 2022
Year: 2022

This paper is an analysis of the different methods proposed to achieve AGI, including Human Brain Emulation, AIXI and Integrated Cognitive Architecture. First, the definition of AGI as used in this paper has been defined, and its requirements have been stated. For each proposed method mentioned, the method in question was summarized and its key processes were detailed, showcasing how it functioned. Then, each method listed was analyzed, taking various factors into consideration, such as technological requirements, computational ability, and adequacy to the requirements. It was concluded that while there are various methods to achieve AGI that could work, such as Human Brain Emulation and Integrated Cognitive Architectures, the most promising method to achieve AGI is Integrated Cognitive Architectures. This is because Human Brain Emulation was found to require scanning technologies that will most likely not be available until the 2030s, making it unlikely to be created before then. Moreover, Integrated Cognitive Architectures has reduced computational requirements and a suitable functionality for General Intelligence, making it the most likely way to achieve AGI.
Towards Loosely-Coupling Knowledge Graph Embeddings and Ontology-based Reasoning
Venue: arXiv cs.AI 2022
Year: 2022

Knowledge graph completion (a.k.a.~link prediction), i.e.,~the task of inferring missing information from knowledge graphs, is a widely used task in many applications, such as product recommendation and question answering. The state-of-the-art approaches of knowledge graph embeddings and/or rule mining and reasoning are data-driven and, thus, solely based on the information the input knowledge graph contains. This leads to unsatisfactory prediction results which make such solutions inapplicable to crucial domains such as healthcare. To further enhance the accuracy of knowledge graph completion we propose to loosely-couple the data-driven power of knowledge graph embeddings with domain-specific reasoning stemming from experts or entailment regimes (e.g., OWL2). In this way, we not only enhance the prediction accuracy with domain knowledge that may not be included in the input knowledge graph but also allow users to plugin their own knowledge graph embedding and reasoning method. Our initial results show that we enhance the MRR accuracy of vanilla knowledge graph embeddings by up to 3x and outperform hybrid solutions that combine knowledge graph embeddings with rule mining and reasoning up to 3.5x MRR.
Knowledge-Integrated Informed AI for National Security
Venue: arXiv cs.AI 2022
Year: 2022

The state of artificial intelligence technology has a rich history that dates back decades and includes two fall-outs before the explosive resurgence of today, which is credited largely to data-driven techniques. While AI technology has and continues to become increasingly mainstream with impact across domains and industries, it's not without several drawbacks, weaknesses, and potential to cause undesired effects. AI techniques are numerous with many approaches and variants, but they can be classified simply based on the degree of knowledge they capture and how much data they require; two broad categories emerge as prominent across AI to date: (1) techniques that are primarily, and often solely, data-driven while leveraging little to no knowledge and (2) techniques that primarily leverage knowledge and depend less on data. Now, a third category is starting to emerge that leverages both data and knowledge, that some refer to as "informed AI." This third category can be a game changer within the national security domain where there is ample scientific and domain-specific knowledge that stands ready to be leveraged, and where purely data-driven AI can lead to serious unwanted consequences. This report shares findings from a thorough exploration of AI approaches that exploit data as well as principled and/or practical knowledge, which we refer to as "knowledge-integrated informed AI." Specifically, we review illuminating examples of knowledge integrated in deep learning and reinforcement learning pipelines, taking note of the performance gains they provide. We also discuss an apparent trade space across variants of knowledge-integrated informed AI, along with observed and prominent issues that suggest worthwhile future research directions. Most importantly, this report suggests how the advantages of knowledge-integrated informed AI stand to benefit the national security domain.
Introducing explainable supervised machine learning into interactive feedback loops for statistical production system
Venue: arXiv cs.LG 2022
Year: 2022

Statistical production systems cover multiple steps from the collection, aggregation, and integration of data to tasks like data quality assurance and dissemination. While the context of data quality assurance is one of the most promising fields for applying machine learning, the lack of curated and labeled training data is often a limiting factor. The statistical production system for the Centralised Securities Database features an interactive feedback loop between data collected by the European Central Bank and data quality assurance performed by data quality managers at National Central Banks. The quality assurance feedback loop is based on a set of rule-based checks for raising exceptions, upon which the user either confirms the data or corrects an actual error. In this paper we use the information received from this feedback loop to optimize the exceptions presented to the National Central Banks thereby improving the quality of exceptions generated and the time consumed on the system by the users authenticating those exceptions. For this approach we make use of explainable supervised machine learning to (a) identify the types of exceptions and (b) to prioritize which exceptions are more likely to require an intervention or correction by the NCBs. Furthermore, we provide an explainable AI taxonomy aiming to identify the different explainable AI needs that arose during the project.
Towards an Analytical Definition of Sufficient Data
Venue: arXiv cs.LG 2022
Year: 2022

We show that, for each of five datasets of increasing complexity, certain training samples are more informative of class membership than others. These samples can be identified a priori to training by analyzing their position in reduced dimensional space relative to the classes' centroids. Specifically, we demonstrate that samples nearer the classes' centroids are less informative than those that are furthest from it. For all five datasets, we show that there is no statistically significant difference between training on the entire training set and when excluding up to 2% of the data nearest to each class's centroid.
Asynchronous Parallel Incremental Block-Coordinate Descent for Decentralized Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning (ML) is a key technique for big-data-driven modelling and analysis of massive Internet of Things (IoT) based intelligent and ubiquitous computing. For fast-increasing applications and data amounts, distributed learning is a promising emerging paradigm since it is often impractical or inefficient to share/aggregate data to a centralized location from distinct ones. This paper studies the problem of training an ML model over decentralized systems, where data are distributed over many user devices and the learning algorithm run on-device, with the aim of relaxing the burden at a central entity/server. Although gossip-based approaches have been used for this purpose in different use cases, they suffer from high communication costs, especially when the number of devices is large. To mitigate this, incremental-based methods are proposed. We first introduce incremental block-coordinate descent (I-BCD) for the decentralized ML, which can reduce communication costs at the expense of running time. To accelerate the convergence speed, an asynchronous parallel incremental BCD (API-BCD) method is proposed, where multiple devices/agents are active in an asynchronous fashion. We derive convergence properties for the proposed methods. Simulation results also show that our API-BCD method outperforms state of the art in terms of running time and communication costs.
Do Developers Refactor Data Access Code? An Empirical Study
Venue: arXiv cs.SE 2022
Year: 2022

Developers often refactor code to improve the maintainability and comprehension of the software. There are many studies on refactoring activities in traditional software systems. However, refactoring in data-intensive systems is not well explored. Understanding the refactoring practices of developers is important to develop efficient tool support.We conducted a longitudinal study of refactoring activities in data access classes using 12 data-intensive subject systems. We investigated the prevalence and evolution of refactorings and the association of refactorings with data access smells. We also conducted a manual analysis of over 378 samples of data access refactoring instances to identify the functionalities of the code that are targeted by such refactorings. Our results show that (1) data access refactorings are prevalent and different in type. \textit{Rename variable} is the most prevalent data access refactoring. (2) The prevalence and type of refactorings vary as systems evolve in time. (3) Most data access refactorings target codes that implement data fetching and insertion. (4) Data access refactorings do not generally touch SQL queries. Overall, the results show that data access refactorings focus on improving the code quality but not the underlying data access operations. Hence, more work is needed from the research community on providing awareness and support to practitioners on the benefits of addressing data access smells with refactorings.
Reducing the Vertex Cover Number via Edge Contractions
Venue: arXiv cs.DS 2022
Year: 2022

The CONTRACTION(vc) problem takes as input a graph $G$ on $n$ vertices and two integers $k$ and $d$, and asks whether one can contract at most $k$ edges to reduce the size of a minimum vertex cover of $G$ by at least $d$. Recently, Lima et al. [JCSS 2021] proved, among other results, that unlike most of the so-called blocker problems, CONTRACTION(vc) admits an XP algorithm running in time $f(d) \cdot n^{O(d)}$. They left open the question of whether this problem is FPT under this parameterization. In this article, we continue this line of research and prove the following results: 1. CONTRACTION(vc) is W[1]-hard parameterized by $k + d$. Moreover, unless the ETH fails, the problem does not admit an algorithm running in time $f(k + d) \cdot n^{o(k + d)}$ for any function $f$. In particular, this answers the open question stated in Lima et al. [JCSS 2021] in the negative. 2. It is NP-hard to decide whether an instance $(G, k, d)$ of CONTRACTION(vc) is a yes-instance even when $k = d$, hence enhancing our understanding of the classical complexity of the problem. 3. CONTRACTION(vc) can be solved in time $2^{O(d)} \cdot n^{k - d + O(1)}$. This XP algorithm improves the one of Lima et al. [JCSS 2021], which uses Courcelle's theorem as a subroutine and hence, the $f(d)$-factor in the running time is non-explicit and probably very large. On the other hard, it shows that when $k=d$, the problem is FPT parameterized by $d$ (or by $k$).
Policy Optimization for Stochastic Shortest Path
Venue: arXiv cs.LG 2022
Year: 2022

Policy optimization is among the most popular and successful reinforcement learning algorithms, and there is increasing interest in understanding its theoretical guarantees. In this work, we initiate the study of policy optimization for the stochastic shortest path (SSP) problem, a goal-oriented reinforcement learning model that strictly generalizes the finite-horizon model and better captures many applications. We consider a wide range of settings, including stochastic and adversarial environments under full information or bandit feedback, and propose a policy optimization algorithm for each setting that makes use of novel correction terms and/or variants of dilated bonuses (Luo et al., 2021). For most settings, our algorithm is shown to achieve a near-optimal regret bound. One key technical contribution of this work is a new approximation scheme to tackle SSP problems that we call \textit{stacked discounted approximation} and use in all our proposed algorithms. Unlike the finite-horizon approximation that is heavily used in recent SSP algorithms, our new approximation enables us to learn a near-stationary policy with only logarithmic changes during an episode and could lead to an exponential improvement in space complexity.
Membership Inference Attacks and Defenses in Neural Network Pruning
Venue: arXiv cs.CR 2022
Year: 2022

Neural network pruning has been an essential technique to reduce the computation and memory requirements for using deep neural networks for resource-constrained devices. Most existing research focuses primarily on balancing the sparsity and accuracy of a pruned neural network by strategically removing insignificant parameters and retraining the pruned model. Such efforts on reusing training samples pose serious privacy risks due to increased memorization, which, however, has not been investigated yet. In this paper, we conduct the first analysis of privacy risks in neural network pruning. Specifically, we investigate the impacts of neural network pruning on training data privacy, i.e., membership inference attacks. We first explore the impact of neural network pruning on prediction divergence, where the pruning process disproportionately affects the pruned model's behavior for members and non-members. Meanwhile, the influence of divergence even varies among different classes in a fine-grained manner. Enlighten by such divergence, we proposed a self-attention membership inference attack against the pruned neural networks. Extensive experiments are conducted to rigorously evaluate the privacy impacts of different pruning approaches, sparsity levels, and adversary knowledge. The proposed attack shows the higher attack performance on the pruned models when compared with eight existing membership inference attacks. In addition, we propose a new defense mechanism to protect the pruning process by mitigating the prediction divergence based on KL-divergence distance, whose effectiveness has been experimentally demonstrated to effectively mitigate the privacy risks while maintaining the sparsity and accuracy of the pruned models.