In safe reinforcement learning (SRL), there exists an inherent conflict between maximizing reward and minimizing cost. We propose a novel approach that effectively resolve the conflict between maximizing reward and minimizing cost in joint optimization.When the cost exceeds the threshold, we perform cost-reducing updates. Otherwise, we compute policy gradients that maximize expected rewards, while using second-order Taylor approximation to evaluate whether these reward-maximizing gradients would violate the cost constraint. If constraint violation is detected, we adjust the gradient direction to maintain safety compliance; otherwise, we execute standard reward-increasing policy updates. This approach helps ensure that reward-seeking updates do not inadvertently increase costs, thereby reducing the likelihood of constraint violations. Empirical tests show our framework successfully manages reward-cost trade-offs through reward augmentation and cost shaping, improving both performance and safety without switching optimization strategies. Results demonstrate that concurrent treatment of both objectives in one policy gradient update is viable for improving safe reinforcement learning methods.

The European-funded HAL4SDV project aims to advance European solutions in software-defined vehicles by introducing a hardware abstraction layer positioned between executed software and execution units. HAL4SDV includes over 60 partners across 12 countries and receives funding within the Chips Joint Undertaking under Horizon Europe since April 2024 and is coordinated by TTTech Computertechnik. The proposed hardware abstraction layer includes safety-critical scheduling and platform deployment of software tasks, and is motivated by the requirement for abstracted hardware with unified interfaces in centralized automotive architectures.This work presents a correct-by-construction workflow which is developed by academic partners to schedule and deploy periodic software tasks onto diverse execution units. The workflow facilitates the execution of the same task stack on multiple unit architectures and consists of a task model and scheduling algorithm, which is followed by platform deployment for diverse hardware units, ensuring safe execution. In this multi-partner project, a bandwidth regulation unit for hardware accelerators and a RISC-V-based multicore system with tightly coupled memories are used as target platforms.A RoboRacer driving stack is chosen for evaluation, showing the viability of our workflow to schedule autonomous driving functions. To show generalization capability, synthetic task sets are additionally used to validate our deployment workflow.

This study presents a comprehensive benchmarking framework for time-series clustering, addressing the lack of standardized guidelines for selecting appropriate approach for clustering tasks. The framework derives and evaluates 15 clustering pipelines comprising multiple well-known clustering techniques and diverse distance metrics, with the constraint of using the same number of clusters for all pipelines to ensure comparability and consistency in the evaluation process. The procedure for standardizing clustering labels, generating ensemble outcomes, and incorporating a stability score is introduced to provide a comprehensive and rigorous evaluation of clustering pipelines. The challenge posed by arbitrary label assignments across different pipelines is resolved through a standardization process that aligns the clusters for meaningful comparison. The ensemble approach mitigates inconsistencies in clustering results and addresses the limitations of traditional clustering validity metrics, leading to more stable and reliable groupings. Additionally, the inclusion of a novel stability score adds a critical layer of evaluation, enabling the identification of the most consistent and accurate clustering outcomes. The results highlight limitations of traditional quality metrics, while showcasing the strong performance for various pipelines with more than 90% of similarity with ensemble results. This would aid in informed selection of the best pipelines for specific applications. The framework is further discussed in the context of optimizing clustering for demand response strategies in smart grids, highlighting its real-world relevance. To support transparency and reproducibility, the study provides open-source code for validating and applying it to various time-series datasets, offering a robust tool for benchmarking clustering across domains.

Coordinated control of residential air-conditioning systems is a promising demand response scheme to reduce peak loads and lower energy bills at a district level. Existing schemes have achieved only limited real-world success due to infrastructural requirements and low consumer adoption. In this paper, a scalable method for the coordinated control of air-conditioners in a group of hundreds of buildings is proposed in which consumers are allowed to override control signals based on their local thermal comfort. The control is based on a novel Split-Input Actor–Critic Reinforcement Learning architecture with a neural network that suggests temperature setpoints for each consumer. It is trained on a grey-box model of the system developed using historical smart meter data. The approach notably does not require behind-the-meter inputs during deployment. In a test system, the controller is able to reduce peak loads by up to 20% without increasing the total energy consumption compared to the baseline case with local control only. The robustness of the controller to different reinforcement learning architecture, inputs, model accuracy and stochasticity is studied. Additionally, the learnt policies are visualized, providing insights about the decision-making of the controller.

An issue concerning the use of deep reinforcement learning (RL) agents is whether they can be trusted to perform reliably when deployed, as training environments may not reflect real-life environments. Anticipating instances outside their training scope, learning-enabled systems are often equipped with out-of-distribution (OOD) detectors that alert when a trained system encounters a state it does not recognize or in which it exhibits uncertainty. There exists limited work conducted on the problem of OOD detection within RL, with prior studies being unable to achieve a consensus on the definition of OOD execution within the context of RL. By framing our problem using a Markov Decision Process, we assume there is a transition distribution mapping each state-action pair to another state with some probability. Based on this, we consider the following definition of OOD execution within RL: A transition is OOD if its probability during real-life deployment differs from the transition distribution encountered during training. As such, we utilize conditional variational autoencoders (CVAE) to approximate the transition dynamics of the training environment and implement a conformity-based detector using reconstruction loss that is able to guarantee OOD detection with a pre-determined confidence level. We evaluate our detector by adapting existing benchmarks and compare it with existing OOD detection models for RL.

In this study, we derive Probably Approximately Correct (PAC) bounds on the asymptotic sample-complexity for RL within the infinite-horizon Markov Decision Process (MDP) setting that are sharper than those in existing literature. The aim of PAC learning is to converge to a near-optimal value function with guarantees on the ‘nearness’, i.e. ϵ, of the synthesized solution. With this, the premise of our study is twofold: firstly, the further two states are from each other, transition-wise, the less relevant the value of the first state is when learning the ϵ-optimal value of the second; secondly, the amount of ‘effort’, sample-complexity-wise, expended in learning the ϵ-optimal value of a state is independent of the number of samples required to learn the ϵ-optimal value of a second state that is a sufficient number of transitions away from the first. Inversely, states within each other’s vicinity have values that are dependent on each other and will require a similar number of samples to learn. By approximating the original MDP using smaller MDPs constructed using subsets of the original state-space, we are able to reduce the sample-complexity by a logarithmic factor to O(SA log A) timesteps, where S and A are the state and action space sizes. We are able to extend these results to an infinite-horizon, model-free setting by constructing a PAC-MDP algorithm with the aforementioned sample-complexity.

Out-of-distribution (OOD) detection attempts to distinguish outlier samples to prevent models trained on the in-distribution (ID) dataset from producing unavailable outputs. Most OOD detection methods require many ID samples for training, which seriously limits their real-world applications. To this end, we target a challenging setting: few-shot OOD detection, where only a few labeled ID samples are available. Therefore, few-shot OOD detection is much more challenging than the traditional OOD detection setting. Previous few-shot OOD detection works ignore the distinct diversity between different classes. In this paper, we propose a novel network: Adaptive Multi-prompt Contrastive Network (AMCN), which adapts the ID-OOD separation boundary by learning inter- and intra-class distribution. To compensate for the absence of OOD and scarcity of ID image samples, we leverage CLIP, connecting text with images, engineering learnable ID and OOD textual prompts. Specifically, we first generate adaptive prompts (learnable ID prompts, label-fixed OOD prompts, and label-adaptive OOD prompts). Then, we generate an adaptive class boundary for each class by introducing a class-wise threshold. Finally, we propose a prompt-guided ID-OOD separation module to control the margin between ID and OOD prompts. Experimental results show that AMCN outperforms other state-of-the-art works.

This paper addresses the deadline-constrained task offloading and resource allocation problem in multi-access edge computing. We aim to determine where each task is offloaded and processed, as well as corresponding communication and computation resource allocations, to maximize the total saved energy for IoT devices, while considering task deadline and system resource constraints. Especially, our system allows each task to be offloaded to one of its accessible access points (APs) and processed on a server that is not co-located with its offloading AP. We formulate this problem as an Integer Nonlinear Programming problem and show it is NP-Hard. To address this problem, we propose a Graph-Matching-based Approximation Algorithm (GMA), the first approximation algorithm of its kind. GMA leverages linear relaxation, tripartite graph construction, and a Linear Programming rounding technique. We prove that GMA is a$\frac{1-\alpha}{2+\epsilon}$-approximation algorithm, where$\epsilon$is a small positive value, and$\alpha(0 \leq \alpha<1)$is a system parameter that ensures the resource allocated to any task by an AP or a server cannot exceed$\alpha$times its resource capacity. Experiments show that, in practice, GMA's energy saving achieves 97% of the optimal value on average.

Vehicular Edge Computing (VEC) has emerged as a promising paradigm for enhancing the computational efficiency and service quality in intelligent transportation systems by enabling vehicles to wirelessly offload computation-intensive tasks to nearby Roadside Units. However, efficient task offloading and resource allocation for time-critical applications in VEC remain challenging due to constrained network bandwidth and computational resources, stringent task deadlines, and rapidly changing network conditions. To address these challenges, we formulate a Deadline-Constrained Task Offloading and Resource Allocation Problem (DOAP), denoted as P, in VEC with both bandwidth and computational resource constraints, aiming to maximize the total vehicle utility. To solve$\mathbf{P}$, we propose SARound, an approximation algorithm based on Linear Program rounding and local-ratio techniques, that improves the best-known approximation ratio for DOAP from$\frac{1}{6}$to$\frac{1}{4}$. Additionally, we design an online service subscription and offloading control framework to address the challenges of short task deadlines and rapidly changing wireless network conditions. To validate our approach, we develop a comprehensive VEC simulator, VecSim, using the open-source simulation libraries OMNeT++ and Simu5G. VecSim integrates our designed framework to manage the full life-cycle of real-time vehicular tasks. Experimental results, based on profiled object detection applications and real-world taxi trace data, show that SARound consistently outperforms state-of-the-art baselines under varying network conditions while maintaining runtime efficiency.

This work studies fixed priority (FP) scheduling of real-time jobs with end-to-end deadlines in a distributed system. Specifically, given a multi-stage pipeline with multiple heterogeneous resources of the same type at each stage, the problem is to assign priorities to a set of real-time jobs with different release times to access a resource at each stage of the pipeline subject to the end-to-end deadline constraints. Note, in such a system, jobs may compete with different sets of jobs at different stages of the pipeline depending on the job-to-resource mapping. To this end, following are the two major contributions of this work. We show that an OPA-compatible schedulability test based on the delay composition algebra can be constructed, which we then use with an optimal priority assignment algorithm to compute a priority ordering. Further, we establish the versatility of pairwise priority assignment in such a multi-stage multi-resource system, compared to a total priority ordering. In particular, we show that a pairwise priority assignment may be feasible even if a priority ordering does not exist. We propose an integer linear programming formulation and a scalable heuristic to compute a pairwise priority assignment. We also show through simulation experiments that the proposed approaches can be used for the holistic scheduling of real-time jobs in edge computing systems.

Decision Trees (DTs) constitute one of the major highly non-linear AI models, valued, e.g., for their efficiency on tabular data. Learning accurate DTs is, however, complicated, especially for oblique DTs, and does take a significant training time. Further, DTs suffer from overfitting, e.g., they proverbially “do not generalize” in regression tasks. Recently, some works proposed ways to make (oblique) DTs differentiable. This enables highly efficient gradient-descent algorithms to be used to learn DTs. It also enables generalizing capabilities by learning regressors at the leaves simultaneously with the decisions in the tree. Prior approaches to making DTs differentiable rely either on probabilistic approximations at the tree’s internal nodes (soft DTs) or on approximations in gradient computation at the internal node (quantized gradient descent). In this work, we propose DTSemNet, a novel semantically equivalent and invertible encoding for (hard, oblique) DTs as Neural Networks (NNs), that uses standard vanilla gradient descent. Experiments across various classification and regression benchmarks show that oblique DTs learned using DTSemNet are more accurate than oblique DTs of similar size learned using state-of-the-art techniques. Further, DT training time is significantly reduced. We also experimentally demonstrate that DTSemNet can learn DT policies as efficiently as NN policies in the Reinforcement Learning (RL) setup with physical inputs (dimensions ≤32). The code is available at https://github.com/CPS-research-group/dtsemnet.

Out-of-distribution (OOD) detectors can act as safety monitors in embedded cyber-physical systems by identifying samples outside a machine learning model’s training distribution to prevent potentially unsafe actions. However, OOD detectors are often implemented using deep neural networks, which makes it difficult to meet real-time deadlines on embedded systems with memory and power constraints. We consider the class of variational autoencoder (VAE) based OOD detectors where OOD detection is performed in latent space, and apply quantization, pruning, and knowledge distillation. These techniques have been explored for other deep models, but no work has considered their combined effect on latent space OOD detection. While these techniques increase the VAE’s test loss, this does not correspond to a proportional decrease in OOD detection performance and we leverage this to develop lean OOD detectors capable of real-time inference on embedded CPUs and GPUs. We propose a design methodology that combines all three compression techniques and yields a significant decrease in memory and execution time while maintaining AUROC for a given OOD detector. We demonstrate this methodology with two existing OOD detectors on a Jetson Nano and reduce GPU and CPU inference time by 20% and 28% respectively while keeping AUROC within 5% of the baseline.

Mobile-edge computing (MEC) has emerged as a promising paradigm for enabling Internet of Things (IoT) devices to handle computation-intensive jobs. Due to the imperfect parallelization of algorithms for job processing on servers and the impact of IoT device mobility on data communication quality in wireless networks, it is crucial to jointly consider server resource allocation and IoT device mobility during job scheduling to fully benefit from MEC, which is often overlooked in existing studies. By jointly considering job scheduling, server resource allocation, and IoT device mobility, we investigate the deadlineconstrained job offloading and resource management problem in MEC with both communication and computation contentions, aiming to maximize the total energy saved for IoT devices. For the offline version of the problem, where job information is known in advance, we formulate it as an Integer Linear Programming problem and propose an approximation algorithm, LHJS, with a constant performance guarantee. For the online version, where job information is only known upon release, we propose a heuristic algorithm, LBS, that is invoked whenever a job is released. Finally, we conduct experiments with parameters from real-world applications to evaluate their performance.

Deep neural networks (DNNs) are effective tools for learning-enabled cyber-physical systems (CPSs) that handle high-dimensional image data. However, DNNs may make incorrect decisions when presented with inputs outside the distribution of their training data. These inputs can compromise the safety of CPSs. So, it becomes crucial to detect inputs as out-of-distribution (OOD) and interpret the reasons for their classification as OOD. In this study, we propose an interpretable learning method to detect OOD caused by meteorological features like darkness, lightness, and rain. To achieve this, we employ a variational autoencoder (VAE) to map high-dimensional image data to a lower-dimensional latent space. We then focus on a specific latent dimension and encourage it to classify different intensities of a particular meteorological feature in a monotonically increasing manner. This is accomplished by incorporating two additional terms into the VAE’s loss function: a classification loss and a positional loss. During training, we optimize the utilization of label information for classification. Remarkably, our results demonstrate that using only 25% of the training data labels is sufficient to train a single pre-selected latent dimension to classify different intensities of a specific meteorological feature. We evaluate the proposed method on two distinct datasets, CARLA and Duckietown, employing two different rain-generation methods. We show that our approach outperforms existing approaches by at least 15 in the F1 score and precision when trained and tested on CARLA dataset.

Industrial control systems (ICSs) consist of a large number of control applications that are associated with periodic real-time flows with hard deadlines. To facilitate large-scale integration, remote control, and co-ordination, wireless sensor and actuator networks form the main communication framework in most ICSs. Among the existing wireless sensor and actuator network protocols, WirelessHART is the most suitable protocol for real-time applications in ICSs. The communications in a WirelessHART network are time-division multiple access based. To satisfy the hard deadlines of the real-time flows, the schedule in a WirelessHART network is pre-computed. The same schedule is repeated over every hyperperiod (i.e., lowest common multiple of the periods of the flows). However, a malicious attacker can exploit the repetitive behavior of the flow schedules to launch timing attacks (e.g., selective jamming attacks). To mitigate timing attacks, we propose an online distributed schedule randomization strategy that randomizes the time-slots in the schedules at each network device without violating the flow deadlines, while ensuring the closed-loop control stability. To increase the extent of randomization in the schedules further, and to reduce the energy consumption of the system, we incorporate a period adaptation strategy that adjusts the transmission periods of the flows depending on the stability of the control loops at runtime. We use Kullback-Leibler divergence and prediction probability of slots as two metrics to evaluate the performance of our proposed strategy. We compare our strategy with an offline centralized schedule randomization strategy. Experimental results show that the schedules generated by our strategy are 10% to 15% more diverse and 5% to 10% less predictable on average compared to the offline strategy when the number of base schedules and keys vary between 4 and 6 and 12 and 32, respectively, under all slot utilization (number of occupied slots in a hyperperiod). On incorporating period adaptation, the divergence in the schedules reduceat each period increase with 46% less power consumption on average.

Ultra-reliable low-latency communication (URLLC) in 5G networks is designed to support time-critical applications such as industrial control systems (ICSs), where user equipment (UEs) communicate with a base station (BS) with very high reliability and low latency. Most of these communications in ICSs are periodic and associated with hard deadlines. To provide a reliable service while satisfying the hard deadlines, the BS usually reserves slots and frequencies and precomputes the schedule for such UEs. The same schedule repeats over time, which makes the slots and frequencies predictable. However, an attacker can exploit this aspect and launch timing attacks disrupting specific communication, thereby, undermining the safety of the system. To mitigate such attacks, we present an online strategy that randomizes the scheduled slots and frequencies over time without violating the flow deadlines. We use Kullback-Leibler divergence to measure the randomness in the schedules generated by our strategy with reference to a hypothetical truly random strategy. We perform security analysis of our proposed strategy using Prediction Probability to measure the predictability in the slots of the generated schedules. We evaluate the performance of our strategy against a state-of-the-art baseline, and show that our strategy performs better than the baseline across all parameter settings.

In an edge-cloud system, mobile devices can offload their computation intensive tasks to an edge or cloud server to guarantee the quality of service or satisfy task deadline requirements. However, it is challenging to determine where tasks should be offloaded and processed, and how much network and computation resources should be allocated to them, such that a system with limited resources can obtain a maximum profit while meeting the deadlines. A key challenge in this problem is that the network and computation resources could be allocated on different servers, since the server to which a task is offloaded (e.g., a server with an access point) may be different from the server on which the task is eventually processed. To address this challenge, we first formulate the task mapping and resource allocation problem as a non-convex Mixed-Integer Nonlinear Programming (MINLP) problem, known as NP-hard. We then propose a zero-slack based greedy algorithm (ZSG) and a linear discretization method (LDM) to solve this MINLP problem. Experiment results with various synthetic tasksets show that ZSG has an average of 2.98% worse performance than LDM with a minimum unit of 5 but has an average of 6.88% better performance than LDM with a minimum unit of 15.

When machine learning (ML) models are supplied with data outside their training distribution, they are more likely to make inaccurate predictions; in a cyber-physical system (CPS), this could lead to catastrophic system failure. To mitigate this risk, an out-of-distribution (OOD) detector can run in parallel with an ML model and flag inputs that could lead to undesirable outcomes. Although OOD detectors have been well studied in terms of accuracy, there has been less focus on deployment to resource constrained CPSs. In this study, a design methodology is proposed to tune deep OOD detectors to meet the accuracy and response time requirements of embedded applications. The methodology uses genetic algorithms to optimize the detector’s preprocessing pipeline and selects a quantization method that balances robustness and response time. It also identifies several candidate task graphs under the Robot Operating System (ROS) for deployment of the selected design. The methodology is demonstrated on two variational autoencoder based OOD detectors from the literature on two embedded platforms. Insights into the trade-offs that occur during the design process are provided, and it is shown that this design methodology can lead to a drastic reduction in response time in relation to an unoptimized OOD detector while maintaining comparable accuracy.

In an edge-cloud system, end devices can offload computation intensive tasks to servers for processing, to satisfy deadline requirements of time-critical tasks, or maintain a good quality of service. Because the system has limited bandwidth and computation resource, it can be very challenging to determine where tasks should be offloaded and processed (task mapping), and how much bandwidth and computation resource should be allocated to each task (resource allocation). In this paper, we propose a task mapping and multi-resource allocation problem with both communication and computation contentions in an edge-cloud system, which aims to maximize the total profit gained by the system while meeting the deadlines of mapped tasks. Besides, the backhaul network of the proposed edge-cloud system is modeled as a directed incomplete graph with bandwidth contention on every edge of the graph. We formulate the problem into a nonconvex Mixed-Integer Nonlinear Programming (MINLP) problem and provide a linearization method to reformulate the MINLP problem into an Integer Linear Programming (ILP) problem formulation, which can be solved with ILP solvers.

Deep Neural Networks are actively being used in the design of autonomous Cyber-Physical Systems (CPSs). The advantage of these models is their ability to handle high-dimensional state-space and learn compact surrogate representations of the operational state spaces. However, the problem is that the sampled observations used for training the model may never cover the entire state space of the physical environment, and as a result, the system will likely operate in conditions that do not belong to the training distribution. These conditions that do not belong to training distribution are referred to as Out-of-Distribution (OOD). Detecting OOD conditions at runtime is critical for the safety of CPS. In addition, it is also desirable to identify the context or the feature(s) that are the source of OOD to select an appropriate control action to mitigate the consequences that may arise because of the OOD condition. In this article, we study this problem as a multi-labeled time series OOD detection problem over images, where the OOD is defined both sequentially across short time windows (change points) as well as across the training data distribution. A common approach to solving this problem is the use of multi-chained one-class classifiers. However, this approach is expensive for CPSs that have limited computational resources and require short inference times. Our contribution is an approach to design and train a single β -Variational Autoencoder detector with a partially disentangled latent space sensitive to variations in image features. We use the feature sensitive latent variables in the latent space to detect OOD images and identify the most likely feature(s) responsible for the OOD. We demonstrate our approach using an Autonomous Vehicle in the CARLA simulator and a real-world automotive dataset called nuImages.

Time synchronization of devices in Internet-of-Things (IoT) networks is one of the challenging problems and a pre-requisite for the design of low-latency applications. Although many existing solutions have tried to address this problem, almost all solutions assume all the devices (nodes) in the network are faultless. Furthermore, these solutions exchange a large number of messages to achieve synchronization, leading to significant communication and energy overhead. To address these short-comings, we propose C-sync, a clustering-based decentralized time synchronization protocol that provides resilience against several types of faults with energy-efficient communication. C-sync achieves scalability by introducing multiple reference nodes in the network that restrict the maximum number of hops any node can have to its time source. The protocol is designed with a modular structure on the Contiki platform to allow application transitions. We evaluate C-sync on a real testbed that comprises over 40 Tmote Sky hardware nodes distributed across different levels in a building and show through experiments the fault resilience, energy efficiency, and scalability of the protocol. C-sync detects and isolates faults to a cluster and recovers quickly. The evaluation makes a qualitative comparison with state-of-the-art protocols and a quantitative comparison with a class of decentralized protocols (derived from GTSP) that provide synchronization with no/limited fault-tolerance. Results also show a reduction of 56.12% and 75.75% in power consumption in the worst-case and best-case scenarios, respectively, compared to GTSP, while achieving similar accuracy.

Uncertainties in machine learning are a significant roadblock for its application in safety-critical cyber-physical systems (CPS). One source of uncertainty arises from distribution shifts in the input data between training and test scenarios. Detecting such distribution shifts in real-time is an emerging approach to address the challenge. The high dimensional input space in CPS applications involving imaging adds extra difficulty to the task. Generative learning models are widely adopted for the task, namely out-of-distribution (OoD) detection. To improve the state-of-the-art, we studied existing proposals from both machine learning and CPS fields. In the latter, safety monitoring in real-time for autonomous driving agents has been a focus. Exploiting the spatiotemporal correlation of motion in videos, we can robustly detect hazardous motion around autonomous driving agents. Inspired by the latest advances in the Variational Autoencoder (VAE) theory and practice, we tapped into the prior knowledge in data to further boost OoD detection’s robustness. Comparison studies over nuScenes and Synthia data sets show our methods significantly improve detection capabilities of OoD factors unique to driving scenarios, 42% better than state-of-the-art approaches. Our model also generalized near-perfectly, 97% better than the state-of-the-art across the real-world and simulation driving data sets experimented. Finally, we customized one proposed method into a twin-encoder model that can be deployed to resource limited embedded devices for real-time OoD detection. Its execution time was reduced over four times in low-precision 8-bit integer inference, while detection capability is comparable to its corresponding floating-point model.

With rapid advancements in the Internet of Things (IoT) paradigm, electrical devices in the near future is expected to have IoT capabilities. This enables fine-grained tracking of individual energy consumption data of such devices, offering location-independent per-device billing. Thus, it is more fine-grained than the location-based metering of state-of-the-art infrastructure, which traditionally aggregates on a building or household level, defining the entity to be billed. However, such in-device energy metering is susceptible to manipulation and fraud. As a remedy, we propose a decentralized metering architecture that enables devices with IoT capabilities to measure their own energy consumption. In this architecture, the device-level consumption is additionally reported to a system-level aggregator that verifies distributed information and provides secure data storage using Blockchain, preventing data manipulation by untrusted entities. Using evaluations on an experimental testbed, we show that the proposed architecture supports device mobility and enables location-independent monitoring of energy consumption.

Perception-based deep neural networks used in Cyber Physical Systems are known to fail when faced with inputs that are out-of-distribution (ODD). ODD detection is a complex problem as we need to first identify the shift in the test data from the training distribution and then we need to isolate the responsible generative factor(s) (weather, lighting levels, traffic density, etc.), Unlike the state of the art that uses multi-chained one-class classifiers, we propose an efficient single monitor that uses the principle of disentanglement to train the latent space of a variational autoencoder to be sensitive to distribution shifts in different generative factors. We demonstrate our approach using an end-to-end driving controller in the CARLA simulator.

Maintaining peer-to-peer connectivity with low energy overhead is a key requirement for several emerging Internet of Things (IoT) applications. It is also desirable to develop such connectivity solutions for non-static network topologies, so that resilience to device failures can be fully realized. De-centralized clustering has emerged as a promising technique to address this critical challenge. Clustering of nodes around cluster heads (CHs) provides an energy-efficient two-tier framework for peer-to-peer communication. At the same time, decentralization ensures that the framework can quickly adapt to a dynamically changing network topology. Although some decentralized clustering solutions have been proposed in the literature, they either lack guarantees on connectivity or incur significant energy overhead to maintain the clusters. In this paper, we present Decentralized Connected Resilient IoT Clustering (DeCoRIC), an energy-efficient clustering scheme that is self-organizing and resilient to network changes while guaranteeing connectivity. Using experiments implemented on the Contiki simulator, we show that our clustering scheme adapts itself to node faults in a time-bound manner. Our experiments show that DeCoRIC achieves 100% connectivity among all nodes while improving the power efficiency of nodes in the system compared to the state-of-the-art techniques BEEM and LEACH by up to 110% and 70%, respectively. The improved power efficiency also translates to longer lifetime before first node death with a best-case of 109% longer than BEEM and 42% longer than LEACH.

Time synchronization is paramount for communication in Internet of Things (IoT) networks. Existing synchronization protocols in the IoT are designed to be accurate, energy-efficient and scalable with absolute trust on the time source(s). If a byzantine node becomes a time source, it can cause synchronization errors with false time, leading to system mal-functions or network crashes. In this paper, we introduce C-Sync: a clustering time synchronization protocol for decentralized IoT networks that incorporates resilience against byzantine nodes. We show that C-sync achieves a worst-case synchronization accuracy of a few tens of microseconds (µs).

Ensuring communication security in real-time automotive networks is of paramount importance given the sensitivity of the exchanged information and highly safety critical nature of its operation. The first step towards ensuring security is to securely authenticate all the computational nodes through use of authentication protocols based on public-key cryptography. But, traditional public-key cryptographic primitives we use today are believed to be breakable by large scale quantum computers of the future. Thus, NIST is currently running a global global level standardization process for quantum-resistant public-key cryptography, better known as post-quantum cryptography. In this work, we perform a first of its kind practical implementation of a secure authentication protocol for automotive systems with post-quantum cryptographic algorithms and perform a detailed comparative evaluation of the speed and communication bandwidth performance against their pre-quantum counterparts.

In-memory computing has gained significant attention due to the potential for dramatic improvement in speed and energy. Redox-based resistive RAMs (ReRAMs), capable of non-volatile storage and logic operations simultaneously have been used for logic-in-memory computing approaches. To this effect, we propose ReRAM based VLIW Architecture for in-Memory comPuting (ReVAMP), supported by a detailed device-accurate simulation setup with peripheral circuitry. We present theoretical bounds on the minimum area required for in-memory computation of arbitrary Boolean functions specified using structural representation (And-Inverter Graph and Majority-Inverter Graph) and two-level representation (Exclusive-Sum-of-Product). To support the ReVAMP architecture, we present two technology mapping flows that fully exploit the bit-level parallelism offered by the execution of logic using ReRAM crossbar array. The area-constrained mapping (ArC) generates feasible mapping for a variety of crossbar dimensions while the delay-constrained mapping (DeC) focuses primarily on minimizing the latency of mapping. We evaluate the proposed mappings against two state-of-the-art technology in-memory computing architectures, PLiM and MAGIC along with their automation flows (SIMPLE and COMPACT). ArC and DeC outperform state-of-the-art PLiM architecture by 1.46x and 4.3x on average in latency. ArC offers significantly lower area (on average 25.27x and 6.57x), while improving the area-delay product by 1.37x and 1.12x against two mapping approaches for MAGIC respectively. In contrast, DeC achieves average area (1.45x and 3.06x) and area-delay product (1.12x and 6.36x) improvements over the mapping approaches for MAGIC architecture respectively. The proposed mapping techniques allow a variety of runtime efficiency trade-offs.

In this article, we present a novel model checking approach to finite-time safety verification of black-box continuous-time dynamical systems within the framework of probably approximately correct (PAC) learning. The black-box dynamical systems are the ones, for which no model is given but whose states changing continuously through time within a finite-time interval can be observed at some discrete-time instants for a given input. The new model checking approach is termed as the PAC model checking due to the incorporation of learned models with correctness guarantees expressed using the terms error probability and confidence. Based on the error probability and confidence level, our approach provides statistically formal guarantees that the time-evolving trajectories of the black-box dynamical system over finite-time horizons fall within the range of the learned model plus a bounded interval, contributing to insights on the reachability of the black-box system and thus on the satisfiability of its safety requirements. The learned model together with the bounded interval is obtained by scenario optimization, which boils down to a linear programming problem. Three examples demonstrate the performance of our approach.

This article presents a novel solution technique for scheduling multi-energy system (MES) in a commercial urban building to perform price-based demand response and reduce energy costs. The MES scheduling problem is formulated as a mixed integer nonlinear program (MINLP), a nonconvex NP-hard problem with uncertainties due to renewable generation and demand. A model predictive control approach is used to handle the uncertainties and price variations. This in-turn requires solving a time-coupled multitime step MINLP during each time-epoch, which is computationally intensive. This investigation proposes an approach called the scenario-based branch-and-bound (SB3), a light-weight solver to reduce the computational complexity. It combines the simplicity of convex programs with the ability of meta-heuristic techniques to handle complex nonlinear problems. The performance of the SB3 solver is validated in the Cleantech building, Singapore and the results demonstrate that the proposed algorithm reduces energy cost by about 17.26% and 22.46% as against solving a multi-time step heuristic optimization model.

Naturally occurring disturbances and malicious attacks can lead to faults in synchronizing the clocks of two network nodes. In this article, we investigate the fundamental resilience bounds of network clock synchronization for a system of N nodes against the peer-to-peer synchronization faults. Our analysis is based on practical synchronization algorithms with time complexity down to O ( N 3 ) that attempt to correct the faults by checking the consistency among the following three types of data: (1) the estimated faults, (2) the estimated clock offsets among the nodes, and (3) the measured clock offsets from the potentially faulty peer-to-peer synchronization sessions. Our analysis gives the following three major results. First, the maximum number of faults that can be corrected by the algorithms has a tight bound of ⌊ N /2 ⌋ − 1 when every node pair performs a synchronization session. Second, by converting the fault resilience problem to a graph-theoretic edge connectivity problem and applying Menger’s theorem, we develop an algorithm to compute the tight bound when not every node pair performs a synchronization session. Third, the number of synchronization sessions to achieve the capability of correcting any K faults has a lower bound of ⌈ N (2 K +1) / 2 ⌉ ; we also develop an algorithm to schedule the synchronization sessions to approach the lower bound. The above results provide basic understanding and useful guidelines to the design of resilient clock synchronization systems. For instance, our results suggest that, the four-node network achieves the highest degree of resilience that is defined as the ratio of the maximum number of correctable faults to the number of synchronization sessions. Therefore, by organizing a large-scale clock synchronization system into a hierarchy of multiple tiers with each consisting of four-node synchronization groups, we can achieve satisfactory and understood resilience against faults with reduced synchronization sessions.

Recently, several parallel frameworks have emerged to utilize the increasing computational capacity of multiprocessors. Parallel tasks are distinguished from traditional sequential tasks in that the subtasks contained in a single parallel task can simultaneously execute on multiple processors. In this study, we consider the scheduling problem of minimizing the number of processors on which the parallel real-time tasks feasibly run. In particular, we focus on scheduling sporadic parallel real-time tasks, in which precedence constraints between subtasks of each parallel task are expressed using a directed acyclic graph (DAG). To address the problem, we formulate an optimization problem that aims to minimize the maximum processing capacity for executing the given tasks. We then suggest a polynomial solution consisting of three steps: (1) transform each parallel real-time task into a series of multithreaded segments, while respecting the precedence constraints of the DAG; (2) selectively extend the segment lengths; and (3) interpret the problem as a flow network to balance the flows on the terminal edges. We also provide the schedulability bound of the proposed solution: it has acapacity augmentation boundof 2. Our experimental results show that the proposed approach yields higher performance than one developed in a recent study.

Different scheduling algorithms for mixed criticality systems have been recently proposed. The common denominator of these algorithms is to discard low critical tasks whenever high critical tasks are in lack of computation resources. This is achieved upon a switch of the scheduling mode from Normal to Critical. We distinguish two main categories of the algorithms: system-level mode switch and task-level mode switch. System-level mode algorithms allow low criticality (LC) tasks to execute only in normal mode. Task-level mode switch algorithms enable to switch the mode of an individual high criticality task (HC), from low (LO) to high (HI), to obtain priority over all LC tasks. This paper investigates an online scheduling algorithm for mixed-criticality systems that supports dynamic mode switches for both task level and system level. When a HC task job overruns its LC budget, then only that particular job is switched to HI mode. If the job cannot be accommodated, then the system switches to Critical mode. To accommodate for resource availability of the HC jobs, the LC tasks are degraded by stretching their periods until the Critical mode exhibiting job complete its execution. The stretching will be carried out until the resource availability is met. We have mechanized and implemented the proposed algorithm using Uppaal. To study the efficiency of our scheduling algorithm, we examine a case study and compare our results to the state of the art algorithms.

Digital twin is a virtual replica of a real-world object that lives simultaneously with its physical counterpart. Since its first introduction in 2003 by Grieves, digital twin has gained momentum in a wide range of applications such as industrial manufacturing, automotive and artificial intelligence. However, many digital-twin-related approaches, found in industries as well as literature, mainly focus on modelling individual physical things with high-fidelity methods with limited scalability. In this paper, we introduce a digital-twin architecture called TiLA (Twin-in-the-Loop Architecture). TiLA employs heterogeneous models and online data to create a digital twin, which follows a Globally Asynchronous Locally Synchronous (GALS) model of computation. It facilitates the creation of a scalable digital twin with different levels of modelling abstraction as well as giving GALS formalism for execution strategy. Furthermore, TiLA provides facilities to develop applications around the twin as well as an interface to synchronise the twin with the physical system through an industrial communication protocol. A digital twin for a manufacturing line has been developed as a case study using TiLA. It demonstrates the use of digital twin models together with online data for monitoring and analysing failures in the physical system.

Medical cyber-physical systems in which multiple medical devices co-ordinate with each other and provide closed-loop control to the patient, have come into prominence in the recent past. One of the main challenges for such systems is guaranteeing their safety even in the presence of significant physiological variabilities among patients. Formal verification based on well-established models of patient physiology has emerged as a potential solution to this problem. However, such techniques face a significant hurdle in terms of scalability due to two main reasons; non-linearity in the physiological models, and large variations in the model parameters due to intra and inter-patient variabilities. In this work, we considered a case-study system of pre-operative and intra-operative care for diabetic patients based on a well-established insulin-infusion protocol. The system comprises a physiological model of the glucose-insulin regulatory system based on Dallaman's model integrated with a proportional-derivative controller that encodes the insulin-infusion protocol. Towards addressing the verification scalability problem, we present a solution for this case-study based on well-known model linearization techniques. We also calculated the error in linearization and incorporated the error into the linearized model. We have constructed both hybrid system model and the corresponding linearized model along with the error and have verified them using dReach and SAL verification tools, respectively. The non-linear model remained non-verifiable for a depth of 8 even after running the verification for more than 20 hours. However, the linearized model was found to be fully verifiable for all the cases and also 2x times faster than the non-linear model for a depth of 7. Therefore, safety of the nonlinear model can be verified with some approximation using the corresponding linearized model.

Existing Mixed Criticality System (MCS) task models consider criticality as the relative importance of a task and use it to achieve graceful degradation of the system either by suspending or degrading tasks with relatively lower criticality level than the overloading task. Graceful degradation based on this notion of criticality as a relative parameter may not always be desired. In this paper, we propose a Context-Aware Mixed Criticality System (CA-MCS) model with which each task can be specified with multiple degraded budgets. To handle a system overload due to timing faults i.e. budget overrun of a task, tasks that need to be degraded are chosen irrespective of their criticality level. However, to handle system overload when multiple tasks overrun their budgets, a specific degraded budget of the task chosen for degradation is decided based on the criticality level of the overrun tasks. Experiments performed in a realistic automotive testbed confirm the benefit of CA-MCS model when compared with the state-of-the art degradation strategies. Results show that contextaware degradation gives the ability to degrade the performance in a controlled manner by effectively isolating the effects of degradation between applications. Finally, we derive a sufficient schedulability test under fixed priority scheduling scheme for the CA-MCS model.

Recent technological advances have fostered the development of complex industrial cyber-physical systems with communication delay requirements. The consequences of delay requirement violation in such systems may become increasingly severe. In this paper, we propose a contract-based fault-resilient methodology which aims at managing the communication delays of network flows in industries. With this objective, we present a lightweight mechanism to estimate end-to-end communication delays in the network where the clocks of the switches are not synchronized. The mechanism aims at providing high level of accuracy with little communication overhead. We then propose a contract-based framework using software-defined networking (SDN) where the components are associated with delay contracts and a resilience manager. The proposed resilience management framework contains: (1) contracts which state requirements about components' behaviors, (2) observers which are responsible to detect contract failure (fault), (3) monitors to detect events such as run-time changes in the delay requirements and link failure, (4) control logic to take suitable decisions based on the type of the fault, (5) resilience manager to decide response strategies containing the best course of action as per the control logic decision. Finally, we present a delay-aware path finding algorithm which is used to route/reroute the network flows to provide resilience in the case of faults and, to adapt to the changes in the network state. Performance of the proposed framework is evaluated with the Ryu SDN controller and Mininet network emulator.

With the growing scale of Cyber-Physical Systems (CPSs), it is challenging to maintain their stability under all operating conditions. How to reduce the downtime and locate the failures becomes a core issue in system design. In this paper, we employ a hierarchical contract-based resilience framework to guarantee the stability of CPS. In this framework, we use Assume Guarantee (A-G) contracts to monitor the non-functional properties of individual components (e.g., power and latency), and hierarchically compose such contracts to deduce information about faults at the system level. The hierarchical contracts enable rapid fault detection in large-scale CPS. However, due to the vast number of components in CPS, manually designing numerous contracts and the hierarchy becomes challenging. To address this issue, we propose a technique to automatically decompose a root contract into multiple lower-level contracts depending on I/O dependencies between components. We then formulate a multi-objective optimization problem to search the optimal parameters of each lower-level contract. This enables automatic contract refinement taking into consideration the communication overhead between components. Finally, we use a case study from the manufacturing domain to experimentally demonstrate the benefits of the proposed framework.

Recent studies exploited external periodic synchronous signals to synchronize a pair of network nodes to address a threat of delaying the communications between the nodes. However, the sensing-based synchronization may yield faults due to nonmalicious signal and sensor noises. This paper considers a system of N nodes that will fuse their peer-to-peer synchronization results to correct the faults. Our analysis gives the lower bound of the number of faults that the system can tolerate when N is up to 12. If the number of faults is no greater than the lower bound, the faults can be identified and corrected. We also prove that the system cannot tolerate more than N - 2 faults. Our results can guide the design of resilient sensing-based clock synchronization systems.

Industrial cyber-infrastructure is normally a multilayered architecture. The purpose of the layered architecture is to hide complexity and allow independent evolution of the layers. In this paper, we argue that this traditional strict layering results in poor transparency across layers affecting the ability to significantly improve resiliency. We propose a contract-based methodology where components across and within the layers of the cyber-infrastructure are associated with contracts and a light-weight resilience manager. This allows the system to detect faults (contract violation monitored using observers) and react (change contracts dynamically) effectively. It results in (1) improving transparency across layers; helps resiliency, (2) decoupling fault-handling code from application code; helps code maintenance, (3) systematically generate error-free fault handling code; reduces development time. Using an industrial case study, we demonstrate the proposed methodology.

This paper considers Dual Priority (DP) scheduling of constrained deadline sporadic tasks on uniprocessor. The initial fixed priority of each job of a task is promoted to a higher priority (called, promoted priority) after a fixed time interval (called, promotion point) relative to the release time of that job. DP scheduling alters the default preemptive behavior of traditional fixed priority (FP) scheduling to efficiently utilize the processor as close as possible to that of the optimal earliest deadline first (EDF) scheduler. In this paper, we address some of the main challenges of DP scheduling including derivation of a sufficient schedulability test, determination of promotion point of each task1. To the best of our knowledge, this test is the first schedulability test for DP scheduling applicable to constrained deadline sporadic tasks. The test is applicable for any given promotion points of the tasks and has pseudo-polynomial time complexity. We also propose two different heuristics to assign the promotion points, and experimental results show that the proposed test achieves performance very close to that of EDF scheduling.

Quality of control is a critical concern in Cyber-Physical Systems (CPS) which are comprised of multiple intercommunicating control applications. Due to complex timing behaviour of these systems, poor quality of control can lead to catastrophe. Recent studies showed that, conflict miss increment in the processor cache memory shared by concurrently running control applications can degrade control quality in CPS significantly. Increasing cache associativity can help to reduce conflict misses. However, the existing reconfigurable cache architectures that allow runtime modification of cache associativity are not capable to guaranty a newly chosen associativity's suitability for the forthcoming control quality requirement. Moreover, they have timing and energy related overheads. In this regard, this paper presents a novel, self-reconfiguring cache memory architecture "SeReMo". When conflict misses increase significantly, SeReMo reconfigures its associativity to better suit the current as well as future control quality demand. To trigger reconfiguration, a low overhead, non-strictly inclusive cache hierarchy-specific approach is used. Configurations with different associativity are generated using modules made of 4 cache lines and 7 special bits. Special replacement policy and indexing scheme are used to suit modular reconfiguration. SPEC CPU 2006 benchmark trace-driven simulation reveals that SeReMo reduces average number of conflict misses per line to 1/12951 of the state-of-the-art reconfigurable cache architecture at maximum (to 1/830 on average). As a result, execution time and energy consumption reduce by 48 hours at maximum (by 2/3 on average) and by 2907 Joules at maximum (86% on average) respectively.

Mixed-criticality (MC) systems are composed of tasks with varying criticality co-hosted on a single shared platform. In conventional MC systems, upon criticality change, the lower criticality tasks are penalized to guarantee resources for the higher criticality ones. However, in practice, penalizing lower criticality tasks have adverse effects and hence, the system is often under-utilized. In this paper, we consider the problem of reservation-based scheduling of mixed-criticality systems on a homogeneous multiprocessor platform to guarantee full service to the lower criticality tasks when one of the processors switches to the critical state. We explore the semi-partitioned scheduling model for dual-criticality systems in which the low criticality tasks executing on a processor are migrated to another processor upon mode switch to improve the service offered to them in the high criticality mode. We present the scheduling strategy of the proposed algorithm and derive its utilization bound. To evaluate the proposed algorithm, we use randomly generated task sets to compare the schedulability performance of the algorithm with the existing algorithms. Our results show that the proposed algorithm improves both schedulability and low criticality support when compared to existing algorithms for implicit-deadline task systems.

Owing to growing complexity and scale, safety-critical real-time systems are generally designed using the concept of mixed-criticality, wherein applications with different criticality or importance levels are hosted on the same hardware platform. To guarantee non-interference between these applications, the hardware resources, in particular the processor, are statically partitioned among them. To overcome the inefficiencies in resource utilization of such a static scheme, the concept of mixed-criticality real-time scheduling has emerged as a promising solution. Although there are several studies on such scheduling strategies for uniprocessor platforms, the problem of efficient scheduling for the multiprocessor case has largely remained open. In this work, we design a fluid-model based mixed-criticality scheduling algorithm for multiprocessors, in which multiple tasks are allowed to execute on the same processor simultaneously. We derive an exact schedulability test for this algorithm, and also present an optimal strategy for assigning the fractional execution rates to tasks. Since fluid-model based scheduling is not implementable on real hardware, we also present a transformation algorithm from fluid-schedule to a non-fluid one. We also show through experimental evaluation that the designed algorithms outperform existing scheduling algorithms in terms of their ability to schedule a variety of task systems.

Missing the deadline of an application task can be catastrophic in real-time systems. Therefore, to ensure timely completion of tasks, offline worst-case execution time and schedulability analysis is often performed for such real-time systems. One of the important inputs to this analysis is a safe upper bound of misses in each processor cache memory used by the system. Cache miss prediction techniques have matured significantly for private caches in single-core processors; however, remained as a challenge for unified, shared caches in multicore processors. According to prior studies, a task's miss upper bound on a shared cache can be predicted using available private cache prediction techniques only if the shared cache maintains core-based independent static partitions. The problem is, such partitions require the use of infeasible “write-update consistency protocol” and wastes valuable cache space by duplicate caching. In this regard, this paper presents a novel cache replacement policy called “predictable variable isolation in shared antipodal memory (PVISAM).” Its replacement decisions generate virtual core-based partitions that support demand-based runtime size adjustment and line sharing to better utilize space. Moreover, these partitions require no consistency protocol. Tracedriven experimental results for Parsec benchmark applications reveal that performance of a unified shared cache memory improves by 101.68x on average (minimum 1.09x and maximum 1138.50x) when PVISAM is used instead of either the aforementioned write-update protocol-based predictable partitioning or the widely used write-invalidate consistency protocol-based partitioning. PVISAM can improve cache performance by 0.74x on average (minimum 0.02x and maximum 1.12x) compared to having no partitions at all. Both predictable partitioning and PVISAM improve unified, shared cache predictability by 63.44% (minimum 26.89% and maximum 99.99%) and 19.36% (minimum 1.58% and maximum 72.51%) on average compared to no partitions and write-invalidate protocol-based partitioning, respectively. Experimental results for synthetic traces show that PVISAM remarkably improves cache performance and predictability when compared to its three competitors even in scenarios that stress the cache.

A significant amount of research has been conducted in the past on compositional real-time scheduling as it has become a useful foundational theory for real-time operating systems and hypervisors. However, compositional frameworks suffer from abstraction overhead in composing components. In this paper, we decompose the abstraction overhead into: 1) supply abstraction overhead associated with the supply from a resource provider and 2) demand abstraction overhead associated with the component workload. Then, we provide sufficient conditions for each abstraction overhead to be eliminated. In addition, this paper provides a heuristic technique that transforms a component to satisfy the sufficient conditions so that the abstraction overhead can be minimized. In experiments, we show that our technique outperforms two prior overhead-reducing techniques. The reduction in overhead is about 10% on average when compared to a technique that uses a single global period and about 8% on average when compared to a technique based on harmonicity.

Systems in many safety-critical application domains are subject to certification requirements. In such a system, there are typically different applications providing functionalities that have varying degrees of criticality. Consequently, the certification requirements for functionalities at these different criticality levels are also varying, with very high levels of assurance required for a highly critical functionality, whereas relatively low levels of assurance are required for a less critical functionality. Considering the timing assurance given to various applications in the form of guaranteed budgets within deadlines, a theory of real-time scheduling for such multi-criticality systems has been recently under development. In particular, an algorithm called Earliest Deadline First with Virtual Deadlines (EDF-VD) has shown a lot of promise for systems with two criticality levels, especially in terms of practical performance demonstrated through experiment results. In this article, we design a new schedulability test for EDF-VD that extends these performance benefits to multi-criticality systems. We propose a new test based on demand bound functions and also present a novel virtual deadline assignment strategy. Through extensive experiments, we show that the proposed technique significantly outperforms existing strategies for a variety of generic real-time systems.

In-memory computing platforms, such as Resistive RAM (ReRAM), offer natural advantage to data-intensive applications. The benefits of data locality and capability to perform native Boolean operations is exploited for significant performance advantage in multiple contexts ranging across neuromorphic computing, associative memory-based computing, arithmetic benchmarks and general-purpose programmable logic-in-memory computing. Despite these advances, design automation tools supporting in-memory computing are still in a nascent phase. In this work, we investigate for the first time, the problem of minimizing delay under arbitrary area constraint of ReRAM devices. We formulate the problem of area-constrained delay minimization as an Integer Linear Programming (ILP) formulation and further propose heuristics that offers scalability as well as solution close to optimal performance. Area-constrained mapping technology mappings enables unlocking significantly large design space trade-offs.

Security in Cyber-Physical Systems (CPS) has become a serious concern owing to the rapid adoption of technologies such as plug-and-play connectivity, robotics and remote coordination and control. It is well understood that the performance overhead incurred due to security considerations is rather high, which needs to be captured holistically for a real-time CPS with strict timing budget and hard deadlines. Additionally, attacks in real-time CPS may only alter the timing behaviour of system components without any changes in functionality, resulting in serious consequences due to missed deadlines. To address this challenging issue, it is necessary to understand the role of diverse components in a real-time CPS and how those expose the system to a malicious attacker. In this paper, we propose a systematic security analysis flow, using a novel Attack Sequence Diagram (ASD), which links the sources, intermediate components and final manifestations of an attack, thereby clearly delineating the attack surfaces of a complex real-time CPS. Based on the ASD, it is possible to evaluate the complexity of an attack, performance overhead of a countermeasure and explore different design trade-offs for a realtime CPS. With the help of real-world and synthetic examples, we demonstrate that ASD seamlessly enables one to map the existing vulnerabilities and uncover new attack possibilities.

Mixed-Criticality (MC) systems consolidate multiple functionalities with different criticalities onto a single hardware platform. Such systems improve the overall resource utilization while guaranteeing resources to critical tasks. In this paper, we focus on the problem of partitioned multiprocessor MC scheduling, in particular the problem of designing efficient partitioning strategies. We develop two new partitioning strategies based on the principle of evenly distributing the difference between total high-critical utilization and total low-critical utilization for the critical tasks among all processors. By balancing this difference, we are able to reduce the pessimism in uniprocessor MC schedulability tests that are applied on each processor, thus improving overall schedulability. To evaluate the schedulability performance of the proposed strategies, we compare them against existing partitioned algorithms using extensive experiments. We show that the proposed strategies are effective with both dynamic-priority Earliest Deadline First with Virtual Deadlines (EDF-VD) and fixed-priority Adaptive Mixed-Criticality (AMC) algorithms. Specifically, our results show that the proposed strategies improve schedulability by as much as 28.1% and 36.2% for implicit and constrained-deadline task systems respectively.

Among series-connected cells in large battery packs, such as those found in electric vehicles, a charge imbalance develops over time due to manufacturing and temperature variations. Therefore, active balancing strategies can be employed in Battery Management Systems (BMSs) to attain a charge balance among cells by transferring charge between them, maximizing the usable capacity of the battery pack. Recently, decentralized BMS architectures with smart battery cells have been developed, in which balancing strategies can operate by local cooperation between the cells without requiring global coordination. In this paper, we propose a decentralized active balancing strategy for smart cells where we identify boundary cells having special properties. These boundary cells enable to divide the global balancing problem into independent subproblems, where local decisions on charge transfers eventually converge to a globally balanced battery pack. The proposed strategy is implemented in a simulator framework and compared with two decentralized state-of-the-art strategies. Our results show significantly improved performance and scalability of the proposed strategy in terms of charge transfer losses and communication overhead between cells, while maintaining a comparable time to balance.

With the widespread adoption of multi-core architectures, it is becoming more important to develop software in ways that takes advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced for targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to parallel task models, including DAG models, on multi-core platforms, without knowing an optimal schedule. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in global EDF schedulability analysis for parallel tasks. In particular, we identify that our proposed schedulability tests are adaptive to different degrees of thread-level parallelism and scalable to the number of processors, resulting in substantial improvement of schedulability for parallel tasks on multi-core platforms.

In the mixed-criticality job model, each job is characterized by two execution time parameters, representing a smaller (less conservative) estimate and a larger (more conservative) estimate on its actual, unknown, execution time. Each job is further classified as being either less critical or more critical. The desired execution semantics are that all jobs should execute correctly provided all jobs complete upon being allowed to execute for up to the smaller of their execution time estimates, whereas if some jobs need to execute beyond their smaller execution time estimates (but not beyond their larger execution time estimates), then only the jobs classified as being more critical are required to execute correctly. The scheduling of collections of such mixed-criticality jobs upon identical multiprocessor platforms in order to minimize the makespan is considered here.

Summary form only given. With the increasing complexity of real-time embedded applications and the availability of Commercial-Off-The-Shelf (COTS) multi-cores, time-predictable execution on these platforms has become a necessity. However, there are several challenges to achieving this predictability, primarily arising due to hardware resources shared between the cores (memory controllers, caches and shared interconnect). In this demo, we present a novel System-on-Chip (SoC) architecture based on COTS multi-cores that address some of these challenges. Specifically, we develop an architecture that enables COTS multi-cores to predictably access external memory. This SoC is designed using hybrid hardware platforms comprising a COTS multi-core and closely coupled Field Programmable Gate Array (FPGA), e.g., Xilinx Zynq ZC706. In our design, the COTS multi-core (ARM Cortex-A9 dual-core) is integrated using a high-speed interconnect with an arbiter module and the Memory Interface Generator (MIG) Xilinx memory controller on the FPGA. Through experiments we show that the proposed architecture has a precisely predictable worst-case memory access latency when compared to a COTS-only design.

Many existing studies on mixed-criticality (MC) scheduling assume that low-criticality budgets for high-criticality applications are known apriori. These budgets are primarily used as guidance to determine when the scheduler should switch the system mode from low to high. Based on this key observation, in this paper we propose a dynamic MC scheduling model under which low-criticality budgets for individual high-criticality applications are determined at runtime as opposed to being fixed offline. To ensure sufficient budget for high-criticality applications at all times, we use offline schedulability analysis to determine a system-wide total low-criticality budget allocation for all the high-criticality applications combined. This total budget is used as guidance in our model to determine the need for a mode-switch. The runtime strategy then distributes this total budget among the various applications depending on their execution requirement and with the objective of postponing mode-switch as much as possible. We show that this runtime strategy is able to postpone mode-switches for a longer time than any strategy that uses a fixed low-criticality budget allocation for each application. Finally, since we are able to control the total budget allocation for high-criticality applications before mode-switch, we also propose techniques to determine these budgets considering system-wide objectives such as schedulability and service guarantee for low-criticality applications.

Mixed-criticality real-time scheduling has been developed to improve resource utilization while guaranteeing safe execution of critical applications. These studies use optimistic resource reservation for all the applications to improve utilization, but prioritize critical applications when the reservations become insufficient at runtime. Many of them however share an impractical assumption that all the critical applications will simultaneously demand additional resources. As a consequence, they under-utilize resources by penalizing all the low-criticality applications. In this paper we overcome this shortcoming using a novel mechanism that comprises a parameter to model the expected number of critical applications simultaneously demanding more resources, and an execution strategy based on the parameter to improve resource utilization. Since most mixed criticality systems in practice are component-based, we design our mechanism such that the component boundaries provide the isolation necessary to support the execution of low-criticality applications, and at the same time protect the critical ones. We also develop schedulability tests for the proposed mechanism under both a flat as well as a hierarchical scheduling framework. Finally, through simulations, we compare the performance of the proposed approach with existing studies in terms of schedulability and the capability to support low-criticality applications.

The fluid scheduling model allows for schedules in which an individual task may be assigned a fraction of a processor at each time instant. These assignments are subject to the constraints that no fraction exceeds one and the sum of all the assigned fractions do not exceed the sum of the computing capacities of all the processors at any instant. An algorithm, MC-Fluid, has recently been proposed for scheduling systems of mixed-criticality implicit-deadline sporadic tasks under the fluid scheduling model. MC-Fluid has been shown to have a speedup bound no worse than (1 + √5)/2 or ≈ 1.618 for scheduling dual-criticality systems. We derive here a simplified variant of MC-Fluid called MCF, that has run-time linear in the number of tasks. We prove that this simplified variant has a speedup bound no worse than 4/3 for dual-criticality systems, and show that this implies that MC-Fluid, too, has a speedup bound no worse than 4/3. We know from prior results in uniprocessor mixed-criticality scheduling that no algorithm may have a speedup bound smaller than 4/3, allowing us to conclude that MCF and MC-Fluid are in fact speedup-optimal for dual-criticality scheduling.

With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms often comes with several different schedulability tests, especially when it is difficult to find exact schedulability tests for the algorithm. Such tests usually find different task sets deemed schedulable even under the same scheduling algorithm. While these different tests have been compared with each other in terms of schedulability performance, little has been done on how to combine such different tests to improve the overall schedulability of a given scheduling algorithm beyond a simple union of their individual schedulability. Motivated by this, we propose a composition theory for schedulability tests with two new methods. The first method composes task-level timing guarantees derived from different schedulability tests, and the second one derives system-level schedulability results from a single schedulability test. The unified composition theory with these two methods then utilizes existing schedulability tests effectively so as to cover additional schedulable task sets. The proposed composition theory is shown to be applicable to most existing preemptive/non-preemptive scheduling algorithms. We also present three case-studies, demonstrating how and by how much the theory can improve schedulability by composing existing schedulability tests. Our evaluation results also show that the composition theory makes it possible to cover up to 181.7 percent additional schedulable task sets for preemptive fpEDF, preemptive EDF and non-preemptive EDF scheduling algorithms beyond their existing tests.

A mixed-criticality system consists of multiple components with different criticalities. While mixed-criticality scheduling has been extensively studied for the uniprocessor case, the problem of efficient scheduling for the multiprocessor case has largely remained open. We design a fluid model-based multiprocessor mixed-criticality scheduling algorithm, called MC-Fluid, in which each task is executed in proportion to its criticality-dependent rate. We propose an exact schedulability condition for MC-Fluid and an optimal assignment algorithm for criticality-dependent execution rates with polynomial complexity. Since MC-Fluid cannot construct a schedule on real hardware platforms due to the fluid assumption, we propose MC-DP-Fair algorithm, which can generate a non-fluid schedule while preserving the same schedulability properties as MC-Fluid. We show that MC-Fluid has a speedup factor of (1 + v 5)/2 ( 1.618), which is best known in multiprocessor MC scheduling, and simulation results show that MC-DP-Fair outperforms all existing algorithms.

A time slot is defined as contention-free if the number of jobs with remaining executions in the slot is no larger than the number of processors, or contending , otherwise. Then an important property holds that in any contention-free slot, all jobs with remaining executions are guaranteed to be scheduled as long as the scheduler is work-conserving. This article aims at improving schedulability by utilizing the contention-free slots. To achieve this, this article presents a policy (called CF policy) that moves some job executions from contending slots to contention-free ones. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from jobs is reduced when their executions are postponed to contention-free slots. Simulation results demonstrate that the CF policy, incorporated into existing algorithms, significantly improves schedulability of those existing algorithms.

The trend towards multi-core/many-core architectures is well underway. It is therefore becoming very important to develop software in ways that take advantage of such parallel architectures. This particularly entails a shift in programming paradigms towards fine-grained, thread-parallel computing. Many parallel programming models have been introduced targeting such intra-task thread-level parallelism. However, most successful results on traditional multi-core real-time scheduling are focused on sequential programming models. For example, thread-level parallelism is not properly captured into the concept of interference, which is key to many schedulability analysis techniques. Thereby, most interference-based analysis techniques are not directly applicable to parallel programming models. Motivated by this, we extend the notion of interference to capture thread-level parallelism more accurately. We then leverage the proposed notion of parallelism-aware interference to derive efficient EDF schedulability tests that are directly applicable to synchronous parallel task models on multi-core platforms. Our evaluation results indicate that the proposed analysis significantly advances the state-of-the-art in EDF schedulability analysis for synchronous parallel tasks.

Strategies that artificially tighten high-criticality task deadlines in low-criticality behaviors have been successfully employed for scheduling mixed-criticality systems. Although efficient scheduling algorithms have been developed for implicit deadline task systems, the same is not true for more general sporadic tasks. In this paper we develop a new demand-based schedulability test for such general mixed-criticality task systems, in which we collectively bound the low- and high-criticality demand of tasks. We show that the new test strictly dominates the only other known demand-based test for such systems. We also propose a new deadline tightening strategy based on this test, and show through simulations that the strategy significantly outperforms all known scheduling algorithms for a variety of sporadic task systems.

In global real-time multiprocessor scheduling, a recent analysis technique for Task-level Fixed-Priority (TFP) scheduling has been shown to outperform many of the analyses for Job-level Fixed-Priority (JFP) scheduling on average. Since JFP is a generalization of TFP scheduling, and the TFP analysis technique itself has been adapted from an earlier JFP analysis, this result is counter-intuitive and in our opinion highlights the lack of good JFP scheduling techniques. Towards generalizing the superior TFP analysis to JFP scheduling, we propose the Smallest Pseudo-Deadline First (SPDF) JFP scheduling algorithm. SPDF uses a simple task-level parameter called pseudo-deadline to prioritize jobs, and hence can behave as a TFP or JFP scheduler depending on the values of the pseudodeadlines. This natural transition from TFP to JFP scheduling has enabled us to incorporate the superior TFP analysis technique in an SPDF schedulability test. We also present a pseudo-deadline assignment algorithm for SPDF scheduling that extends the well-known Optimal Priority Assignment (OPA) algorithm for TFP scheduling. We show that our algorithm is optimal for the derived schedulability test, and also present a heuristic to overcome the computational complexity issue of the optimal algorithm. Our simulation results show that the SPDF algorithm with the new analysis significantly outperforms state-of-the-art TFP and JFP analysis.

It is widely assumed that scheduling real-time tasks becomes more difficult as their deadlines get shorter. With deadlines shorter, however, tasks potentially compete less with each other for processors, and this could produce more contention-free slots at which the number of competing tasks is smaller than or equal to the number of available processors. This paper presents a policy (called CF policy) that utilizes such contention-free slots effectively. This policy can be employed by any work-conserving, preemptive scheduling algorithm, and we show that any algorithm extended with this policy dominates the original algorithm in terms of schedulability. We also present improved schedulability tests for algorithms that employ this policy, based on the observation that interference from tasks is reduced when their executions are postponed to contention-free slots. Finally, using the properties of the CF policy, we derive a counter-intuitive claim that shortening of task deadlines can help improve schedulability of task systems. We present heuristics that effectively reduce task deadlines for better scheduability without performing any exhaustive search.

The current industry trend is towards using Commercially available Off-The-Shelf (COTS) based multicores for developing real time embedded systems, as opposed to the usage of custom-made hardware. In typical implementation of such COTS-based multicores, multiple cores access the main memory via a shared bus. This often leads to contention on this shared channel, which results in an increase of the response time of the tasks. Analyzing this increased response time, considering the contention on the shared bus, is challenging on COTS-based systems mainly because bus arbitration protocols are often undocumented and the exact instants at which the shared bus is accessed by tasks are not explicitly controlled by the operating system scheduler; they are instead a result of cache misses. This paper makes three contributions towards analyzing tasks scheduled on COTS-based multicores. Firstly, we describe a method to model the memory access patterns of a task. Secondly, we apply this model to analyze the worst case response time for a set of tasks. Although the required parameters to obtain the request profile can be obtained by static analysis, we provide an alternative method to experimentally obtain them by using performance monitoring counters (PMCs). We also compare our work against an existing approach and show that our approach outperforms it by providing tighter upper-bound on the number of bus requests generated by a task.

In distributed soft real-time systems, maximizing the aggregate quality-of-service (QoS) is a typical system-wide goal, and addressing the problem through distributed optimization is challenging. Subtasks are subject to unpredictable failures in many practical environments, and this makes the problem much harder. In this paper, we present a robust optimization framework for maximizing the aggregate QoS in the presence of random failures. We introduce the notion of K-failure to bound the effect of random failures on schedulability. Using this notion we define the concept of K-robustness that quantifies the degree of robustness on QoS guarantee in a probabilistic sense. The parameter K helps to tradeoff achievable QoS versus robustness. The proposed robust framework produces optimal solutions through distributed computations on the basis of Lagrangian duality, and we present some implementation techniques. Our simulation results show that the proposed framework can probabilistically guarantee sub-optimal QoS which remains feasible even in the presence of random failures.

LLF (Least Laxity First) scheduling, which assigns a higher priority to a task with smaller laxity, has been known as an optimal preemptive scheduling algorithm on a single processor platform. However, its characteristics upon multiprocessor platforms have been little studied until now. Orthogonally, it has remained open how to efficiently schedule general task systems, including constrained deadline task systems, upon multiprocessors. Recent studies have introduced zero laxity (ZL) policy, which assigns a higher priority to a task with zero laxity, as a promising scheduling approach for such systems (e.g., EDZL). Towards understanding the importance of laxity in multiprocessor scheduling, this paper investigates the characteristics of ZL policy and presents the first ZL schedulability test for any work-conserving scheduling algorithm that employs this policy. It then investigates the characteristics of LLF scheduling, which also employs the ZL policy, and derives the first LLF-specific schedulability test on multiprocessors. It is shown that the proposed LLF test dominates the ZL test as well as the state-of-art EDZL test.

ARINC specification 653-2 describes the interface between application software and underlying middleware in a distributed real-time avionics system. The real-time workload in this system comprises of partitions, where each partition consists of one or more processes. Processes incur blocking and preemption overheads and can communicate with other processes in the system. In this work we develop compositional techniques for automated scheduling of such partitions and processes. At present, system designers manually schedule partitions based on interactions they have with the partition vendors. This approach is not only time consuming, but can also result in under utilization of resources. In contrast, the technique proposed in this paper is a principled approach for scheduling ARINC-653 partitions and therefore should facilitate system integration.

In this paper we consider global fixed-priority preemptive multiprocessor scheduling of constrained-deadline sporadic tasks that share resources in a non-nested manner. We develop a novel resource-sharing protocol and a corresponding schedulability test for this system. We also develop the first schedulability analysis of priority inheritance protocol for the aforementioned system. Finally, we show that these protocols are efficient (based on the developed schedulability tests) for a class of priority-assignments called reasonable priority-assignments.

Scheduling of sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and globalscheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster areglobally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize processor utilization of individual clusters. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved utilization bounds.

Conditional real-time task models, which are generalizations of periodic, sporadic, and multi-frame tasks, represent real world applications more accurately. These models can be classified based on a tradeoff in two dimensions - expressivity and hardness of schedulability analysis. In this work, we introduce a class of conditional task models and derive efficient schedulability analysis techniques for them. These models are more expressive than existing models for which efficient analysis techniques are known. In this work, we also lay the groundwork for schedulability analysis of hierarchical scheduling frameworks with conditional task models. We propose techniques that abstract timing requirements of conditional task models, and support compositional analysis using these abstractions.

Embedded systems are complex as a whole but consist of smaller independent modules interacting with each other. This structure makes them amenable to compositional design. Real-time embedded systems consist of realtime workloads having deadlines. Compositional design of such systems can be done using real-time components arranged in a scheduling hierarchy. Each component consists of some real-time workload and a scheduling policy for the workload. To simplify schedulability analysis for such systems, analysis should be done compositionally using interfaces that abstract timing requirement of components. To facilitate analysis of dynamically changing systems, the framework should also support incremental analysis. In this paper, we overview our approach to compositional and incremental schedulability analysis of hierarchical real-time systems. We describe a compositional analysis technique that abstracts resource requirement of components using periodic resource models. To support incremental analysis and resource bandwidth minimization, we describe an extension to this interface model. Each extended interface consists of multiple periodic resource models for different periods. This allows the selection of a periodic model that can schedule the system using minimum bandwidth. We also account for context switch overhead of components in these extended interfaces. We then describe an associative composition technique for such interfaces, that supports incremental analysis

Compositional schedulability analysis of hierarchical scheduling frameworks is a well studied problem, as it has wide-ranging applications in the embedded systems domain. Several techniques, such as periodic resource model based abstraction and composition, have been proposed for this problem. However these frameworks are sub-optimal because they incur bandwidth overhead. In this work, we introduce the explicit deadline periodic (EDP) resource model, and present compositional analysis techniques under EDF and DM. We show that these techniques are bandwidth optimal, in that they do not incur any bandwidth overhead in abstraction or composition. Hence, this framework is more efficient when compared to existing approaches.

Embedded systems are complex as a whole but consist of smaller independent modules minimally interacting with each other. This structure makes embedded systems amenable to compositional system design. Compositional design of real-time embedded systems can be done using hierarchical systems which consist of real-time components arranged in a scheduling hierarchy. Each component consists of a real-time workload and a scheduling policy for the workload. To simplify schedulability analysis of hierarchical systems, analysis can be done compositionally using interfaces that abstract the timing requirements of components. Associative composition will facilitate analysis of systems in which components are modified on the fly. In this paper, we propose efficient algorithms to abstract the resource requirements of components in the form of periodic resource models. Each component interface consists of a set of periodic resource models for different values of period, which allows the selection of a periodic interface that minimizes the collective real-time requirements of hierarchical components. We also describe an interface composition algorithm which accounts for context switch overheads incurred by components and is associative.