OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Sequential Optimization Under Observability Don't Cares
Venue: arXiv cs.LO 2023
Year: 2023

Sequential logic synthesis can provide better Power-Performance-Area (PPA) than combinational logic synthesis since it explores a larger solution space. As the gate cost in advanced technologies keeps rising, sequential logic synthesis provides a powerful alternative that is gaining momentum in the EDA community. In this work, we present a new scalable algorithm for don't-care-based sequential logic synthesis. Our new approach is based on sequential k-step induction and can apply both redundancy removal and resubstitution transformations under Sequential Observability Don't Cares (SODCs). Using SODC-based optimizations with induction is a challenging problem due to dependencies and alignment of don't cares among the base case and the inductive case. We propose a new approach utilizing the full power of SODCs without limiting the solution space. Our algorithm is implemented as part of an industrial tool and achieves 6.9% average area improvement after technology mapping when compared to state-of-the-art sequential synthesis methods. Moreover, all the new sequential optimizations can be verified using state-of-the-art sequential verification tools.
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata
Venue: arXiv cs.FL 2023
Year: 2023

Nonuniform families of polynomial-size finite automata, which are series of indexed finite automata having polynomially many inner states, are used in the past literature to solve nonuniform families of promise decision problems. Among such nonuniform families of finite automata, we focus our attention, in particular, on the variants of nondeterministic finite automata, which have at most "one" (unambiguous), "polynomially many" (few) accepting computation paths, or unambiguous/few computation paths leading to each fixed configuration. When such machines are limited to make only one-way head moves, we can prove with no unproven hardness assumptions that some of these variants are different in computational power from each other. As for two-way machines restricted to instances of polynomially-bounded length, families of two-way polynomial-size nondeterministic finite automata are equivalent in power to families of polynomial-size unambiguous finite automata.
Straggler-resilient Federated Learning: Tackling Computation Heterogeneity with Layer-wise Partial Model Training in Mobile Edge Network
Venue: arXiv cs.LG 2023
Year: 2023

Federated Learning (FL) enables many resource-limited devices to train a model collaboratively without data sharing. However, many existing works focus on model-homogeneous FL, where the global and local models are the same size, ignoring the inherently heterogeneous computational capabilities of different devices and restricting resource-constrained devices from contributing to FL. In this paper, we consider model-heterogeneous FL and propose Federated Partial Model Training (FedPMT), where devices with smaller computational capabilities work on partial models (subsets of the global model) and contribute to the global model. Different from Dropout-based partial model generation, which removes neurons in hidden layers at random, model training in FedPMT is achieved from the back-propagation perspective. As such, all devices in FedPMT prioritize the most crucial parts of the global model. Theoretical analysis shows that the proposed partial model training design has a similar convergence rate to the widely adopted Federated Averaging (FedAvg) algorithm, $\mathcal{O}(1/T)$, with the sub-optimality gap enlarged by a constant factor related to the model splitting design in FedPMT. Empirical results show that FedPMT significantly outperforms the existing benchmark FedDrop. Meanwhile, compared to the popular model-homogeneous benchmark, FedAvg, FedPMT reaches the learning target in a shorter completion time, thus achieving a better trade-off between learning accuracy and completion time.
Graph models for Cybersecurity -- A Survey
Venue: arXiv cs.CR 2023
Year: 2023

Graph models are helpful means of analyzing computer networks as well as complex system architectures for security. In this paper we evaluate the current state of research for representing and analysing cyber-attack using graph models, i.e. attack graph (AG) formalisms. We propose a taxonomy on attack graph formalisms, based on 70 models, which we analysed with respect to their \textit{graph semantic}, involved agents and analysis features. Additionally, we adress which formalisms allow for automatic attack graph generation from raw or processes data inputs. Our taxonomy is especially designed to help users and applied researchers identify a suitable AG model for their needs. A summary of the individual AG formalisms is provided as supplementary material.
The Minimum Clique Routing Problem on Cycles
Venue: arXiv cs.DS 2023
Year: 2023

In the Minimum Clique Routing Problem on Cycles \textsc{MCRPC} we are given a cycle together with a set of demands (weighted origin-destination pairs) and the goal is to route all the pairs minimizing the maximum weighted clique of the intersection graph induced by the routing. The vertices of this graph are the demands with their corresponding weights and two demands are adjacent when their routes share at least one arc. In this work we are not only interested in the \textsc{MCRPC} but also in two natural subproblems. First, we consider the situation where the demands are disjoint, in the sense that every two demands do not share any of their corresponding ends. Second, we analyze the subproblem where the weights of the routes are all equal. We first show that the problem is NP-complete even in the subproblem of disjoint demands. For the case of arbitrary weights, we exhibit a simple combinatorial 2-approximation algorithm and a $\frac{3}{2}$-approximation algorithm based on rounding a solution of a relaxation of an integer linear programming formulation of our problem. Finally, we give a Fixed Parameter Tractable algorithm for the case of uniform weights, whose parameter is related to the maximum degree of the intersection graph induced by any routing.
ChatGPT-3.5, ChatGPT-4, Google Bard, and Microsoft Bing to Improve Health Literacy and Communication in Pediatric Populations and Beyond
Venue: arXiv cs.CL 2023
Year: 2023

Purpose: Enhanced health literacy has been linked to better health outcomes; however, few interventions have been studied. We investigate whether large language models (LLMs) can serve as a medium to improve health literacy in children and other populations. Methods: We ran 288 conditions using 26 different prompts through ChatGPT-3.5, Microsoft Bing, and Google Bard. Given constraints imposed by rate limits, we tested a subset of 150 conditions through ChatGPT-4. The primary outcome measurements were the reading grade level (RGL) and word counts of output. Results: Across all models, output for basic prompts such as "Explain" and "What is (are)" were at, or exceeded, a 10th-grade RGL. When prompts were specified to explain conditions from the 1st to 12th RGL, we found that LLMs had varying abilities to tailor responses based on RGL. ChatGPT-3.5 provided responses that ranged from the 7th-grade to college freshmen RGL while ChatGPT-4 outputted responses from the 6th-grade to the college-senior RGL. Microsoft Bing provided responses from the 9th to 11th RGL while Google Bard provided responses from the 7th to 10th RGL. Discussion: ChatGPT-3.5 and ChatGPT-4 did better in achieving lower-grade level outputs. Meanwhile Bard and Bing tended to consistently produce an RGL that is at the high school level regardless of prompt. Additionally, Bard's hesitancy in providing certain outputs indicates a cautious approach towards health information. LLMs demonstrate promise in enhancing health communication, but future research should verify the accuracy and effectiveness of such tools in this context. Implications: LLMs face challenges in crafting outputs below a sixth-grade reading level. However, their capability to modify outputs above this threshold provides a potential mechanism to improve health literacy and communication in a pediatric population and beyond.
Improving Unimodal Inference with Multimodal Transformers
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes an approach for improving performance of unimodal models with multimodal training. Our approach involves a multi-branch architecture that incorporates unimodal models with a multimodal transformer-based branch. By co-training these branches, the stronger multimodal branch can transfer its knowledge to the weaker unimodal branches through a multi-task objective, thereby improving the performance of the resulting unimodal models. We evaluate our approach on tasks of dynamic hand gesture recognition based on RGB and Depth, audiovisual emotion recognition based on speech and facial video, and audio-video-text based sentiment analysis. Our approach outperforms the conventionally trained unimodal counterparts. Interestingly, we also observe that optimization of the unimodal branches improves the multimodal branch, compared to a similar multimodal model trained from scratch.
Towards Improving Robustness Against Common Corruptions using Mixture of Class Specific Experts
Venue: arXiv cs.LG 2023
Year: 2023

Neural networks have demonstrated significant accuracy across various domains, yet their vulnerability to subtle input alterations remains a persistent challenge. Conventional methods like data augmentation, while effective to some extent, fall short in addressing unforeseen corruptions, limiting the adaptability of neural networks in real-world scenarios. In response, this paper introduces a novel paradigm known as the Mixture of Class-Specific Expert Architecture. The approach involves disentangling feature learning for individual classes, offering a nuanced enhancement in scalability and overall performance. By training dedicated network segments for each class and subsequently aggregating their outputs, the proposed architecture aims to mitigate vulnerabilities associated with common neural network structures. The study underscores the importance of comprehensive evaluation methodologies, advocating for the incorporation of benchmarks like the common corruptions benchmark. This inclusion provides nuanced insights into the vulnerabilities of neural networks, especially concerning their generalization capabilities and robustness to unforeseen distortions. The research aligns with the broader objective of advancing the development of highly robust learning systems capable of nuanced reasoning across diverse and challenging real-world scenarios. Through this contribution, the paper aims to foster a deeper understanding of neural network limitations and proposes a practical approach to enhance their resilience in the face of evolving and unpredictable conditions.
Sobol Sequence Optimization for Hardware-Efficient Vector Symbolic Architectures
Venue: arXiv cs.LG 2023
Year: 2023

Hyperdimensional computing (HDC) is an emerging computing paradigm with significant promise for efficient and robust learning. In HDC, objects are encoded with high-dimensional vector symbolic sequences called hypervectors. The quality of hypervectors, defined by their distribution and independence, directly impacts the performance of HDC systems. Despite a large body of work on the processing parts of HDC systems, little to no attention has been paid to data encoding and the quality of hypervectors. Most prior studies have generated hypervectors using inherent random functions, such as MATLAB`s or Python`s random function. This work introduces an optimization technique for generating hypervectors by employing quasi-random sequences. These sequences have recently demonstrated their effectiveness in achieving accurate and low-discrepancy data encoding in stochastic computing systems. The study outlines the optimization steps for utilizing Sobol sequences to produce high-quality hypervectors in HDC systems. An optimization algorithm is proposed to select the most suitable Sobol sequences for generating minimally correlated hypervectors, particularly in applications related to symbol-oriented architectures. The performance of the proposed technique is evaluated in comparison to two traditional approaches of generating hypervectors based on linear-feedback shift registers and MATLAB random function. The evaluation is conducted for two applications: (i) language and (ii) headline classification. Our experimental results demonstrate accuracy improvements of up to 10.79%, depending on the vector size. Additionally, the proposed encoding hardware exhibits reduced energy consumption and a superior area-delay product.
Retrieval Augmented Generation of Symbolic Music with LLMs
Venue: arXiv cs.SD 2023
Year: 2023

We explore the use of large language models (LLMs) for music generation using a retrieval system to select relevant examples. We find promising initial results for music generation in a dialogue with the user, especially considering the ease with which such a system can be implemented. The code is available online.
Optimized Deep Learning Models for AUV Seabed Image Analysis
Venue: arXiv cs.CV 2023
Year: 2023

Using autonomous underwater vehicles, or AUVs, has completely changed how we gather data from the ocean floor. AUV innovation has advanced significantly, especially in the analysis of images, due to the increasing need for accurate and efficient seafloor mapping. This blog post provides a detailed summary and comparison of the most current advancements in AUV seafloor image processing. We will go into the realm of undersea technology, covering everything through computer and algorithmic advancements to advances in sensors and cameras. After reading this page through to the end, you will have a solid understanding of the most up-to-date techniques and tools for using AUVs to process seabed photos and how they could further our comprehension of the ocean floor
Collaborative Grid Mapping for Moving Object Tracking Evaluation
Venue: arXiv cs.RO 2023
Year: 2023

Perception of other road users is a crucial task for intelligent vehicles. Perception systems can use on-board sensors only or be in cooperation with other vehicles or with roadside units. In any case, the performance of perception systems has to be evaluated against ground-truth data, which is a particularly tedious task and requires numerous manual operations. In this article, we propose a novel semi-automatic method for pseudo ground-truth estimation. The principle consists in carrying out experiments with several vehicles equipped with LiDAR sensors and with fixed perception systems located at the roadside in order to collaboratively build reference dynamic data. The method is based on grid mapping and in particular on the elaboration of a background map that holds relevant information that remains valid during a whole dataset sequence. Data from all agents is converted in time-stamped observations grids. A data fusion method that manages uncertainties combines the background map with observations to produce dynamic reference information at each instant. Several datasets have been acquired with three experimental vehicles and a roadside unit. An evaluation of this method is finally provided in comparison to a handmade ground truth.
DynaPipe: Optimizing Multi-task Training through Dynamic Pipelines
Venue: arXiv cs.DC 2023
Year: 2023

Multi-task model training has been adopted to enable a single deep neural network model (often a large language model) to handle multiple tasks (e.g., question answering and text summarization). Multi-task training commonly receives input sequences of highly different lengths due to the diverse contexts of different tasks. Padding (to the same sequence length) or packing (short examples into long sequences of the same length) is usually adopted to prepare input samples for model training, which is nonetheless not space or computation efficient. This paper proposes a dynamic micro-batching approach to tackle sequence length variation and enable efficient multi-task model training. We advocate pipeline-parallel training of the large model with variable-length micro-batches, each of which potentially comprises a different number of samples. We optimize micro-batch construction using a dynamic programming-based approach, and handle micro-batch execution time variation through dynamic pipeline and communication scheduling, enabling highly efficient pipeline training. Extensive evaluation on the FLANv2 dataset demonstrates up to 4.39x higher training throughput when training T5, and 3.25x when training GPT, as compared with packing-based baselines. DynaPipe's source code is publicly available at https://github.com/awslabs/optimizing-multitask-training-through-dynamic-pipelines.
UA-Radar: Exploring the Impact of User Agents on the Web
Venue: arXiv cs.CR 2023
Year: 2023

In the early days of the web, giving the same web page to different browsers could provide very different results. As the rendering engine behind each browser would differ, some elements of a page could break or be positioned in the wrong location. At that time, the User Agent (UA) string was introduced for content negotiation. By knowing the browser used to connect to the server, a developer could provide a web page that was tailored for that specific browser to remove any usability problems. Over the past three decades, the UA string remained exposed by browsers, but its current usefulness is being debated. Browsers now adopt the exact same standards and use the same languages to display the same content to users, bringing the question if the content of the UA string is still relevant today, or if it is a relic of the past. Moreover, the diversity of means to browse the web has become so large that the UA string is one of the top contributors to tracking users in the field of browser fingerprinting, bringing a sense of urgency to deprecate it. In this paper, our goal is to understand the impact of the UA on the web and if this legacy string is still actively used to adapt the content served to users. We introduce UA-Radar, a web page similarity measurement tool that compares in-depth two web pages from the code to their actual rendering, and highlights the similarities it finds. We crawled 270, 048 web pages from 11, 252 domains using 3 different browsers and 2 different UA strings to observe that 100% of the web pages were similar before any JavaScript was executed, demonstrating the absence of differential serving. Our experiments also show that only a very small number of websites are affected by the lack of UA information, which can be fixed in most cases by updating code to become browser-agnostic. Our study brings some proof that it may be time to turn the page on the UA string and retire it from current web browsers.
Memory Management Strategies for an Internet of Things System
Venue: arXiv cs.SE 2023
Year: 2023

The rise of the Internet has brought about significant changes in our lives, and the rapid expansion of the Internet of Things (IoT) is poised to have an even more substantial impact by connecting a wide range of devices across various application domains. IoT devices, especially low-end ones, are constrained by limited memory and processing capabilities, necessitating efficient memory management within IoT operating systems. This paper delves into the importance of memory management in IoT systems, with a primary focus on the design and configuration of such systems, as well as the scalability and performance of scene management. Effective memory management is critical for optimizing resource usage, responsiveness, and adaptability as the IoT ecosystem continues to grow. The study offers insights into memory allocation, scene execution, memory reduction, and system scalability within the context of an IoT system, ultimately highlighting the vital role that memory management plays in facilitating a seamless and efficient IoT experience.
A Formalisation of Core Erlang, a Concurrent Actor Language
Venue: arXiv cs.PL 2023
Year: 2023

In order to reason about the behaviour of programs described in a programming language, a mathematically rigorous definition of that language is needed. In this paper, we present a machine-checked formalisation of concurrent Core Erlang (a subset of Erlang) based on our previous formalisations of its sequential sublanguage. We define a modular, frame stack semantics, show how program evaluation is carried out with it, and prove a number of properties (e.g. determinism, confluence). Finally, we define program equivalence based on bisimulations and prove that side-effect-free evaluation is a bisimulation. This research is part of a wider project that aims to verify refactorings to prove that particular program code transformations preserve program behaviour.
A Large-Scale Study on the Prevalence and Usage of TEE-based Features on Android
Venue: arXiv cs.CR 2023
Year: 2023

In the realm of mobile security, where OS-based protections have proven insufficient against robust attackers, Trusted Execution Environments (TEEs) have emerged as a hardware-based security technology. Despite the industry's persistence in advancing TEE technology, the impact on end users and developers remains largely unexplored. This study addresses this gap by conducting a large-scale analysis of TEE utilization in Android applications, focusing on the key areas of cryptography, digital rights management, biometric authentication, and secure dialogs. To facilitate our extensive analysis, we introduce Mobsec Analytika, a framework tailored for large-scale app examinations, which we make available to the research community. Through the analysis of 170,550 popular Android apps, our analysis illuminates the implementation of TEE-related features and their contextual usage. Our findings reveal that TEE features are predominantly utilized indirectly through third-party libraries, with only 6.7% of apps directly invoking the APIs. Moreover, the study reveals the underutilization of the recent TEE-based UI feature Protected Confirmation.
Efficient Profit Maximization in Reliability Concerned Static Vehicular Cloud System
Venue: arXiv cs.DC 2023
Year: 2023

Modern electric VUs are equipped with a variety of increasingly potent computing, communication, and storage resources, and with this tremendous computation power in their arsenal can be used to enhance the computing power of regular cloud systems, which is termed as vehicular cloud. Unlike in the traditional cloud computing resources, these vehicular cloud resource moves around and participates in the vehicular cloud for a sporadic duration at parking places, shopping malls, etc. This introduces the dynamic nature of vehicular resource participation in the vehicular cloud. As the user-submitted task gets allocated on these vehicular units for execution and the dynamic stay nature of vehicular units, enforce the system to ensure the reliability of task execution by allocating multiple redundant vehicular units for the task. In this work, we are maximizing the profit of vehicular cloud by ensuring the reliability of task execution where user tasks come online manner with different revenue, execution, and deadline. We propose an efficient approach to solve this problem by considering (a) task classification based on the deadline and laxity of the task, (b) ordering of tasks for task admission based on the expected profit of the task, (c) classification of vehicular units based in expected residency time and reliability concerned redundant allocation of tasks of vehicular units considering this classification and (d) handing dynamic scenario of the vehicular unit leaving the cloud system by copying the maximum percentage of executed virtual machine of the task to the substitute unit. We compared our proposed profit maximization approach with the state of art approach and showed that our approach outperforms the state of art approach with an extra 10\% to 20\% profit margin.