Conformal prediction constructs a set of labels instead of a single point prediction, while providing a probabilistic coverage guarantee. Beyond the coverage guarantee, adaptiveness to example difficulty is an important property. It means that the method should produce larger prediction sets for more difficult examples, and smaller ones for easier examples. Existing evaluation methods for adaptiveness typically analyze coverage rate violation or average set size across bins of examples grouped by difficulty. However, these approaches often suffer from imbalanced binning, which can lead to inaccurate estimates of coverage or set size. To address this issue, we propose a binning method that leverages input transformations to sort examples by difficulty, followed by uniform-mass binning. Building on this binning, we introduce two metrics to better evaluate adaptiveness. These metrics provide more reliable estimates of coverage rate violation and average set size due to balanced binning, leading to more accurate adaptivity assessment. Through experiments, we demonstrate that our proposed metric correlates more strongly with the desired adaptiveness property compared to existing ones. Furthermore, motivated by our findings, we propose a new adaptive prediction set algorithm that groups examples by estimated difficulty and applies group-conditional conformal prediction. This allows us to determine appropriate thresholds for each group. Experimental results on both (a) an Image Classification (ImageNet) (b) a medical task (visual acuity prediction) show that our method outperforms existing approaches according to the new metrics.

While large language models (LLMs) have recently made tremendous progress towards solving challenging AI problems, they have done so at increasingly steep computational and API costs. We propose a novel strategy where we combine multiple LLM models with varying cost/accuracy tradeoffs in an agentic manner, where models and tools are run in sequence as determined by an orchestration model to minimize cost subject to a user-specified level of reliability; this constraint is formalized using conformal prediction to provide guarantees. To solve this problem, we propose Conformal Constrained Policy Optimization (CCPO), a training paradigm that integrates constrained policy optimization with off-policy reinforcement learning and recent advances in online conformal prediction. CCPO jointly optimizes a cost-aware policy (score function) and an adaptive threshold. Across two multi-hop question answering benchmarks, CCPO achieves up to a 30% cost reduction compared to other cost-aware baselines and LLM-guided methods without compromising reliability. Our approach provides a principled and practical framework for deploying LLM agents that are significantly more cost-effective while maintaining reliability.

Backdoor attacks pose significant risks to applications based on deep neural networks (DNNs). Current defenses fail to achieve good performance with lightweight (compact) models, limited defense data, and low poisoning rates. To address these challenges, we propose Purified Distillation Slimming (PDS), a novel knowledge distillation approach equipped with iterative pruning. Specifically, we initialize the student model from the backdoored teacher model and iteratively prune the student's neurons until the trigger pattern is deactivated. Such an approach leverages the efficacy of knowledge distillation to transfer purified knowledge from a potentially compromised teacher model to a student model, thereby filtering out backdoor triggers embedded within the training data. Concurrently, we employ network slimming to prune backdoored neurons, enhancing the model's resilience to backdoor attacks by reducing the neurons that adversaries can exploit. Through comprehensive experiments against 17 SOTA backdoor attacks, we demonstrate that our proposed method not only effectively mitigates the impact of backdoor attacks but also preserves, and in some cases even enhances, the model's performance on benign tasks. The effectiveness of PDS has been verified on multiple datasets (Cifar-10, GTSRB, and ImageNet) across several network architectures (ResNet, VGG, MobileNet, EfficientNet, and GoogLeNet).

Prolonged loneliness in older adults increases the risk of dementia, cardiovascular diseases, and premature death. However, timely detection and behavioral pattern analysis are challenging due to the slow progression of loneliness and diverse individual lifestyles. To address these barriers, we propose SMILE, an end-to-end framework for sensor-driven detection and counterfactual pattern analysis of loneliness. Our approach uses non-intrusive sensors to passively observe behavior and build a personalized profile over time. When SMILE detects meaningful changes in activity patterns, it employs generative models to produce counterfactual sensor profiles—synthetic representations of behavior predicted to result in lower loneliness scores. Suggested pattern changes are identified as the difference between observed and counterfactual profiles, highlighting the behaviors most associated with loneliness. We conducted a 6-month feasibility study with 18 participants from the United States and 15 from Japan to develop and evaluate SMILE. Our framework integrates a Time-series Transformer (TST) model for loneliness detection, which achieved 96.25% accuracy, and a diffusion model for generating behavioral explanations, which outperformed a baseline by up to 76.69%. These findings highlight the potential of SMILE to support sensor-driven, personalized loneliness detection and behavioral explanation in aging populations.

Multimodal large language models (MLLMs) can simultaneously process visual, textual, and auditory data, capturing insights that complement human analysis. However, existing video question-answering (VidQA) benchmarks and datasets often exhibit a bias toward a single modality, despite the goal of requiring advanced reasoning skills that integrate diverse modalities to answer the queries. In this work, we introduce the modality importance score (MIS) to identify such bias. It is designed to assess which modality embeds the necessary information to answer the question. Additionally, we propose an innovative method using state-of-the-art MLLMs to estimate the modality importance, which can serve as a proxy for human judgments of modality perception. With this MIS, we demonstrate the presence of unimodal bias and the scarcity of genuinely multimodal questions in existing datasets. We further validate the modality importance score with multiple ablation studies to evaluate the performance of MLLMs on permuted feature sets. Our results indicate that current models do not effectively integrate information due to modality imbalance in existing datasets. Our proposed MLLM-derived MIS can guide the curation of modality-balanced datasets that advance multimodal learning and enhance MLLMs' capabilities to understand and utilize synergistic relations across modalities.

Large Language Models (LLMs) are susceptible to adversarial attacks such as jailbreaking, which can elicit harmful or unsafe behaviors.This vulnerability is exacerbated in multilingual settings, where multilingual safetyaligned data is often limited.Thus, developing a guardrail capable of detecting and filtering unsafe content across diverse languages is critical for deploying LLMs in real-world applications.In this work, we introduce a multilingual guardrail with reasoning for prompt classification.Our method consists of: (1) synthetic multilingual data generation incorporating culturally and linguistically nuanced variants, (2) supervised fine-tuning, and (3) a curriculum-based Group Relative Policy Optimization (GRPO) framework that further improves performance.Experimental results demonstrate that our multilingual guardrail, Mr-Guard, consistently outperforms recent baselines across both in-domain and out-of-domain languages by more than 15%.We also evaluate MrGuard's robustness to multilingual variations, such as code-switching and low-resource language distractors in the prompt, and demonstrate that it preserves safety judgments under these challenging conditions.The multilingual reasoning capability of our guardrail enables it to generate explanations, which are particularly useful for understanding languagespecific risks and ambiguities in multilingual content moderation.

A particularly challenging problem in AI safety is providing guarantees on the behavior of high-dimensional autonomous systems. Verification approaches centered around reachability analysis fail to scale, and purely statistical approaches are constrained by the distributional assumptions about the sampling process. Instead, we pose a distributionally robust version of the statistical verification problem for black-box systems, where our performance guarantees hold over a large family of distributions. This paper proposes a novel approach based on uncertainty quantification using concepts from imprecise probabilities. A central piece of our approach is an ensemble technique called Imprecise Neural Networks, which provides the uncertainty quantification. Additionally, we solve the allied problem of exploring the input set using active learning. The active learning uses an exhaustive neural-network verification tool Sherlock to collect samples. An evaluation on multiple physical simulators in the openAI gym Mujoco environments with reinforcement-learned controllers demonstrates that our approach can provide useful and scalable guarantees for high-dimensional systems.

Building generalist agents that can rapidly adapt to new environments is a key challenge for deploying AI in the digital and real worlds. Is scaling current agent architectures the most effective way to build generalist agents? We propose a novel approach to pre-train relatively small policies on relatively small datasets and adapt them to unseen environments via in-context learning, without any finetuning. Our key idea is that retrieval offers a powerful bias for fast adaptation. Indeed, we demonstrate that even a simple retrieval-based 1-nearest neighbor agent offers a surprisingly strong baseline for today's state-of-the-art generalist agents. From this starting point, we construct a semi-parametric agent, REGENT, that trains a transformer-based policy on sequences of queries and retrieved neighbors. REGENT can generalize to unseen robotics and game-playing environments via retrieval augmentation and in-context learning, achieving this with up to 3x fewer parameters and up to an order-of-magnitude fewer pre-training datapoints, significantly outperforming today's state-of-the-art generalist agents.

Eye blink dynamics offer crucial insights into physiological and cognitive states. Existing solutions either require specialized equipment for detailed measurements or sacrifice temporal resolution for accessibility. We present BlinkWise, the first system that transforms everyday eyewear into a wise device for detailed blink dynamics tracking as a tiny add-on. BlinkWise measures eye openness in real-time on resource-constrained edge devices by leveraging both RF modality's inherent efficiency and novel computational optimizations—including recurrentization of convolutional network operations, quantization-aware normalization, and a lightweight proposal algorithm. Evaluation with 20 subjects and more than 18,000 blink measurements demonstrated BlinkWise's high accuracy in capturing subtle blink dynamics at millisecond resolution, achieving a Pearson correlation of 0.981 with ground truth. Through three real-world application studies, we demonstrate BlinkWise's potential for monitoring cognitive states and ocular health. Code, datasets, and demo videos are available on our website.

Medical cyber-physical systems (MCPS) are increasingly adopting learning-enabled components (LECs) to enhance their decision-making capabilities. Due to the safety-critical nature of MCPS, these systems must maintain high performance on both expected and unexpected input data. Therefore, ensuring the robustness of LE-MCPS is crucial for their successful deployment. Existing research predominantly focuses on robustness to synthetic adversarial examples , crafted by adding imperceptible perturbations to clean input data. However, these synthetic adversarial examples do not accurately reflect the most challenging real-world scenarios, especially in the context of healthcare data. Consequently, robustness to synthetic adversarial examples may not necessarily translate to robustness against naturally occurring adversarial examples . We propose a method to evaluate the robustness of LE-MCPS to natural adversarial examples. The method curates naturally adversarial datasets leveraging probabilistic labels obtained from automated weakly supervised labeling which combines noisy and cheap-to-obtain labeling heuristics. Based on these labels, the method adversarially orders the input data and uses this ordering to construct a sequence of increasingly adversarial datasets for assessing robustness. Our evaluation on six MCPS case studies and two non-medical case studies demonstrates (1) the efficacy and statistical validity of our approach to generating naturally adversarial datasets and (2) the utility of our robustness evaluation in classifying robust and non-robust LE-MCPS.

Conformal prediction is a statistical tool for producing prediction regions of machine learning models that are valid with high probability. However, applying conformal prediction to time series data leads to conservative prediction regions. In fact, to obtain prediction regions over T time steps with confidence 1--delta, previous works require that each individual prediction region is valid with confidence 1--delta/T. We propose an optimization-based method for reducing this conservatism to enable long horizon planning and verification when using learning-enabled time series predictors. Instead of considering prediction errors individually at each time step, we consider a parameterized prediction error over multiple time steps. By optimizing the parameters over an additional dataset, we find prediction regions that are not conservative. We show that this problem can be cast as a mixed integer linear complementarity program (MILCP), which we then relax into a linear complementarity program (LCP). Additionally, we prove that the relaxed LP has the same optimal cost as the original MILCP. Finally, we demonstrate the efficacy of our method on case studies using pedestrian trajectory predictors and F16 fighter jet altitude predictors.

Advances in wearable technology have enabled ubiquitous use of wearable devices in remote patient monitoring, particularly in clinical trials. Because of the reliance on highquality data in these endeavors, the first and often the most time-consuming step is to build a data collection system. While many systems have been developed to address this, they are often highly specific and customized to the task at hand, and are often not generalized enough to support other tasks. To remedy this, we developed Raproto, an open-source easy-to-use rapid prototyping platform that does not require the time, effort, and expertise needed for custom development. The Raproto platform consists of three components, the wearable device(s), communication protocol, and remote storage. These components support the collection, transmission, storage, analysis, and visualization of large-scale data with applications from smaller-scale research studies to large clinical trials. To reduce the burden of device and application development, we created multipurpose and customizable smartwatch applications on both the Android and Tizen operating systems. We evaluate our platform in a lab setting as well as in two real-world case studies. Overall, we find that we can collect data using our application for over 24 hours on a single charge and there is little to no data loss, thus making it an ideal tool to preface customized device development for real-world impact and commercialization.

Xinmeng Huang, Shuo Li, Mengxin Yu, Matteo Sesia, Hamed Hassani, Insup Lee, Osbert Bastani, Edgar Dobriban. Proceedings of the 2024 Conference on Empirical Methods in Natural Language Processing. 2024.

Prediction sets capture uncertainty by predicting sets of labels rather than individual labels, enabling downstream decisions to conservatively account for all plausible outcomes. Conformal inference algorithms construct prediction sets guaranteed to contain the true label with high probability. These guarantees fail to hold in the face of distribution shift, which is precisely when reliable uncertainty quantification can be most useful. We propose a novel algorithm for constructing prediction sets with PAC guarantees in the label shift setting, where the probabilities of labels can differ between the source and target distributions. Our algorithm relies on constructing confidence intervals for importance weights by propagating uncertainty through a Gaussian elimination algorithm. We evaluate our approach on four datasets: the CIFAR-10 and ChestX-Ray image datasets, the tabular CDC Heart Dataset, and the AGNews text dataset. Our algorithm satisfies the PAC guarantee while producing smaller prediction set sizes compared to several baselines.

Imitation learning considerably simplifies policy synthesis compared to alternative approaches by exploiting access to expert demonstrations. For such imitation policies, errors away from the training samples are particularly critical. Even rare slip-ups in the policy action outputs can compound quickly over time, since they lead to unfamiliar future states where the policy is still more likely to err, eventually causing task failures. We revisit simple supervised "behavior cloning" for conveniently training the policy from nothing more than pre-recorded demonstrations, but carefully design the model class to counter the compounding error phenomenon. Our "memory-consistent neural network" (MCNN) outputs are hard-constrained to stay within clearly specified permissible regions anchored to prototypical "memory" training samples. We provide a guaranteed upper bound for the sub-optimality gap induced by MCNN policies. Using MCNNs on 10 imitation learning tasks, with MLP, Transformer, and Diffusion backbones, spanning dexterous robotic manipulation and driving, proprioceptive inputs and visual inputs, and varying sizes and types of demonstration data, we find large and consistent gains in performance, validating that MCNNs are better-suited than vanilla deep neural networks for imitation learning applications. Website: https://sites.google.com/view/mcnn-imitation

Reaching a target safely and quickly is a control goal pursued by various applications, such as post-disaster rescue robots and industrial shipment. However, it is hard to formally guarantee safety and time-optimality under unknown dynamics via model-free controller synthesis algorithms. As a response, we propose a model-free reinforcement learning (RL) algorithm that synthesize a controller to reach a predefined target set of states with a probabilistic guarantee of time optimality, i.e., the actual reaching time is bounded close to the shortest time possible with high probability, and the bound becomes tighter when more training data is sampled. Our algorithm leverages a reward function that based on signal temporal logic (STL) robustness to reward fast reaching. With this reward function, we prove that Probably Approximately Correct (PAC) optimality in the state-value function implies PAC optimality in reach time. Then, we build our algorithm by extending Deplayed Gaussian Process Q learning (DGPQ) algorithm with a safety margin to protect the controlled agent. Consequently, our algorithm guarantees safety and a PAC bound in recovery time. Experiments show our method can achieve $\mathbf{9 7. 7 \%}$ success rate to reach the target with in the maximum time tolerance and outperform baselines.

Recent advancements in person recognition have raised concerns about identity privacy leaks.Gait recognition through millimeterwave radar provides a privacy-centric method.However, it is challenged by lower accuracy due to the sparse data these sensors capture.We are the first to investigate a cross-modal method, Iden-tityKD, to enhance gait-based person recognition with the assistance of facial data.IdentityKD involves a training process using both gait and facial data, while the inference stage is conducted exclusively with gait data.To effectively transfer facial knowledge to the gait model, we create a composite feature representation using contrastive learning.This method integrates facial and gait features into a unified embedding that captures the unique identityspecific information from both modalities.We employ two distinct contrastive learning losses.One minimizes the distance between embeddings of data pairs from the same person, enhancing intraclass compactness, while the other maximizes the distance between embeddings of data pairs from different individuals, improving inter-class separability.Additionally, we use an identity-wise distillation strategy, which tailors the training process for each individual, ensuring that the model learns to distinguish between different identities more effectively.Our experiments on a dataset of 36 subjects, each providing over 5000 face-gait pairs, demonstrate that IdentityKD improves identity recognition accuracy by 6.5% compared to baseline methods.

Shuo Li, Sangdon Park, Insup Lee, Osbert Bastani. Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2024.

Anomaly detection is widely used for identifying critical errors and suspicious behaviors, but current methods lack interpretability. We leverage common properties of existing methods and recent advances in generative models to introduce counterfactual explanations for anomaly detection. Given an input, we generate its counterfactual as a diffusion-based repair that shows what a non-anomalous version $\textit{should have looked like}$. A key advantage of this approach is that it enables a domain-independent formal specification of explainability desiderata, offering a unified framework for generating and evaluating explanations. We demonstrate the effectiveness of our anomaly explainability framework, AR-Pro, on vision (MVTec, VisA) and time-series (SWaT, WADI, HAI) anomaly datasets. The code used for the experiments is accessible at: https://github.com/xjiae/arpro.

Meeting deadlines is a fundamental requirement of cyber-physical systems (CPS) in real-time applications to consolidate their reliability and effectiveness in executing timecritical tasks. Recent research have focused on applying reinforcement learning to synthesize controllers for real-time systems, particularly in terms of achieving fast reach-avoid. However, achieving fast behavior does not necessarily equate to meeting deadlines. Sometimes reinforcement learning agents are trying to maximize the total reward by exploiting the reward function, and thus performing unwanted behavior, known as reward hacking. Therefore, depending on the deadlines, it is possible to have fast controllers that miss the deadlines and slow controllers that meet the deadlines. To address the misalignment between fast and meeting deadlines, we investigate the relationship between as soon as possible (ASAP) and deadline-safe. Additionally, we formulate the problem into a new Markov decision process R-MDP including time to avoid non-Markovian rewards when considering deadlines. Furthermore, we have designed new reward functions that encourage the agent to meet the deadlines. Moreover, we evaluate our method on various benchmarks. The experiment results show the effectiveness of our method in ensuring deadline compliance without compromising safety.

Uncertainty in the predictions of learning-enabled components hinders their deployment in safety-critical cyber-physical systems (CPS). A shift from the training distribution of a learning-enabled component (LEC) is one source of uncertainty in the LEC’s predictions. Detection of this shift or out-of-distribution (OOD) detection on individual datapoints has therefore gained attention recently. But in many applications, inputs to CPS form a temporal sequence. Existing techniques for OOD detection in time-series data for CPS either do not exploit temporal relationships in the sequence or do not provide any guarantees on detection. We propose using deviation from the in-distribution temporal equivariance as the non-conformity measure in conformal anomaly detection framework for OOD detection in time-series data for CPS. Computing independent predictions from multiple conformal detectors based on the proposed measure and combining these predictions by Fisher’s method leads to the proposed detector CODiT with bounded false alarms. CODiT performs OOD detection on fixed-length windows of consecutive time-series datapoints by using Fisher value of the input window. We further propose performing OOD detection on real-time time-series traces of variable lengths with bounded false alarms. This can be done by using CODiT to compute Fisher values of the sliding windows in the input trace and combining these values by a merging function. Merging functions such as Harmonic Mean, Arithmetic Mean, Geometric Mean, Bonferroni Method, and so on, can be used to combine Fisher values of the sliding windows in the input trace, and the combined value can be used for OOD detection on the trace with bounded false alarm rate guarantees. We illustrate the efficacy of CODiT by achieving state-of-the-art results in two case studies for OOD detection on fixed-length windows. The first one is on an autonomous driving system with perception (or vision) LEC. The second case study is on a medical CPS for walking pattern or GAIT analysis where physiological (non-vision) data is collected with force-sensitive resistors attached to the subject’s body. For OOD detection on variable length traces, we consider the same case studies on the autonomous driving system and medical CPS for GAIT analysis. We report our results with four merging functions on the Fisher values computed by CODiT on the sliding windows of the input trace. We also compare the false alarm rate guarantees by these four merging functions in the autonomous driving system case study. Code, data, and trained models are available at https://github.com/kaustubhsridhar/time-series-OOD .

Incorporating learning based components in the current state-of-the-art cyber-physical systems (CPS) has been a challenge due to the brittleness of the underlying deep neural networks. On the bright side, if executed correctly with safety guarantees, this has the ability to revolutionize domains like autonomous systems, medicine, and other safety-critical domains. This is because it would allow system designers to use high-dimensional outputs from sensors like camera and LiDAR. The trepidation in deploying systems with vision and LiDAR components comes from incidents of catastrophic failures in the real world. Recent reports of self-driving cars running into difficult to handle scenarios is ingrained in the software components which handle such sensor inputs. The ability to handle such high-dimensional signals is due to the explosion of algorithms which use deep neural networks. Sadly, the reason behind the safety issues is also due to deep neural networks themselves. The pitfalls occur due to possible over-fitting and lack of awareness about the blind spots induced by the training distribution. Ideally, system designers would wish to cover as many scenarios during training as possible. However, achieving a meaningful coverage is impossible. This naturally leads to the following question: is it feasible to flag out-of-distribution (OOD) samples without causing too many false alarms? Such an OOD detector should be executable in a fashion that is computationally efficient. This is because OOD detectors often are executed as frequently as the sensors are sampled. Our aim in this article is to build an effective anomaly detector. To this end, we propose the idea of a memory bank to cache data samples which are representative enough to cover most of the in-distribution data. The similarity with respect to such samples can be a measure of familiarity of the test input. This is made possible by an appropriate choice of distance function tailored to the type of sensor we are interested in. Additionally, we adapt conformal anomaly detection framework to capture the distribution shifts with a guarantee of false alarm rate. We report the performance of our technique on two challenging scenarios: a self-driving car setting implemented inside the simulator CARLA with image inputs and autonomous racing car navigation setting with LiDAR inputs. From the experiments, it is clear that a deviation from the in-distribution setting can potentially lead to unsafe behavior. It should be noted that not all OOD inputs lead to precarious situations in practice, but staying in-distribution is akin to staying within a safety bubble and predictable behavior. An added benefit of our memory-based approach is that the OOD detector produces interpretable feedback for a human designer. This is of utmost importance since it recommends a potential fix for the situation as well. In other competing approaches, such feedback is difficult to obtain due to reliance on techniques which use variational autoencoders.

Deep learning models have shown extreme vulnerability to distribution shifts such as synthetic perturbations and spatial transformations. In this work, we explore whether we can adopt the characteristics of adversarial attack methods to help improve robustness of object detection to distribution shifts such as synthetic perturbations and spatial transformations. We study a class of realistic object detection settings wherein the target objects have control over their appearance. To this end, we propose a reversed Fast Gradient Sign Method (FGSM) to obtain these angelic patches that significantly increase the detection probability, even without pre-knowledge of the perturbations. In detail, we apply the patch to each object instance simultaneously, strengthening not only classification, but also bounding box accuracy. Experiments demonstrate the efficacy of the partial-covering patch in solving the complex bounding box problem. More importantly, the performance is also transferable to different detection models even under severe affine transformations and deformable shapes. To the best of our knowledge, we are the first object detection patch that achieves both cross-model efficacy and multiple patches. We observed average accuracy improvements of 30% in the real-world experiments. Our code is available at: https://github.com/averysi224/angelic_patches.

BabyBERTa, a language model trained on small-scale child-directed speech while none of the words are unmasked during training, has been shown to achieve a level of grammaticality comparable to that of RoBERTa-base, which is trained on 6,000 times more words and 15 times more parameters (Huebner et al., 2021).Relying on this promising result, we explore in this paper the performance of BabyBERTabased models in downstream tasks, focusing on Semantic Role Labeling (SRL) and two Extractive Question Answering tasks, with the aim of building more efficient systems that rely on less data and smaller models.We investigate the influence of these models both alone and as a starting point to larger pre-trained models, separately examining the contribution of the pre-training data, the vocabulary, and the masking policy on the downstream task performance.Our results show that BabyBERTa trained with unmasking-removal policy is a much stronger starting point for downstream tasks compared to the use of RoBERTa masking policy when 10M words are used for training and that this tendency persists, although to a lesser extent, when adding more training data. 1

Social interaction quality ratings derived from short natural conversations can differentiate children with and without autism at the group level. In this work, we explored conversations between children and an unfamiliar adult who rated their social interaction success on six dimensions. Using hand-crafted acoustic and lexical features, we built different classifiers to predict children's dimensional conversation quality. The best classifier achieved 61% accuracy, which outperformed human raters (49%). Follow-up analyses revealed that a subset of features determined communication quality scores. Additionally, we extracted acoustic features using a pretrained audio transformer and improved our prediction to 68%. This study suggests that automatically predicting conversation quality could be an inexpensive and objective way to monitor intervention progress in children with communication challenges, and could be used to identify intervention targets for improving conversational success.

Cyber-physical systems (CPSs) leverage computations to operate physical objects in real-world environments, and increasingly more CPS-based applications have been designed for life-critical applications. Therefore, any vulnerability in such a system can lead to severe consequences if exploited by adversaries. In this paper, we present a data predictive recovery system to safeguard the CPS from sensor attacks, assuming that we can identify compromised sensors from data. Our recovery system guarantees that the CPS will never encounter unsafe states and will smoothly recover to a target set within a conservative deadline. It also guarantees that the CPS will remain within the target set for a specified period. Major highlights of our paper include (i) the recovery procedure works on nonlinear systems, (ii) the method leverages uncorrupted sensors to relieve uncertainty accumulation, and (iii) an extensive set of experiments on various nonlinear benchmarks that demonstrate our framework’s performance and efficiency.

Machine learning methods such as deep neural networks (DNNs), despite their success across different domains, are known to often generate incorrect predictions with high confidence on inputs outside their training distribution. The deployment of DNNs in safety-critical domains requires detection of out-of-distribution (OOD) data so that DNNs can abstain from making predictions on those. A number of methods have been recently developed for OOD detection, but there is still room for improvement. We propose the new method iDECODe, leveraging in-distribution equivariance for conformal OOD detection. It relies on a novel base non-conformity measure and a new aggregation method, used in the inductive conformal anomaly detection framework, thereby guaranteeing a bounded false detection rate. We demonstrate the efficacy of iDECODe by experiments on image and audio datasets, obtaining state-of-the-art results. We also show that iDECODe can detect adversarial examples. Code, pre-trained models, and data are available at https://github.com/ramneetk/iDECODe.

Real-world software is usually built on top of other software provided as packages that are managed by package managers. Package managers facilitate code reusability and programmer productivity but incur significant software bloat by installing excessive dependent packages. This dependency hell increases potential security issues and hampers rapid response to newly discovered vulnerabilities. We propose a package-oriented debloating framework, PacJam, for adaptive and security-aware management of an application's dependent packages. PacJam improves upon existing debloating techniques by providing a configurable fallback mechanism via post-deployment policies. It also elides the need to completely specify the application's usage scenarios and does not require runtime support. Moreover, PacJam enables to rapidly mitigate newly discovered vulnerabilities with minimal impact on the application's functionality. We evaluate PacJam on 10 popular and diverse Linux applications comprising 575K-39M SLOC each. Compared to a state-of-the-art approach, piecewise debloating, PacJam debloats 66% of the packages per application on average, reducing the attack surface by removing 46% of CVEs and 69% (versus 66%) of gadgets, with significantly less runtime overhead and without the need to install a custom loader.

A standard assumption in supervised learning is that the training data and test data are from the same distribution. However, this assumption often fails to hold in practice, which can cause the learned model to perform poorly. We consider the problem of detecting covariate shift, where the covariate distribution shifts but the conditional distribution of labels given covariates remains the same. This problem can naturally be solved using a two-sample test{—}i.e., test whether the current test distribution of covariates equals the training distribution of covariates. Our algorithm builds on classifier tests, which train a discriminator to distinguish train and test covariates, and then use the accuracy of this discriminator as a test statistic. A key challenge is that classifier tests assume given a fixed set of test covariates. In practice, test covariates often arrive sequentially over time{—}e.g., a self-driving car observes a stream of images while driving. Furthermore, covariate shift can occur multiple times{—}i.e., shift and then shift back later or gradually shift over time. To address these challenges, our algorithm trains the discriminator online. Additionally, it evaluates test accuracy using each new covariate before taking a gradient step; this strategy avoids constructing a held-out test set, which can improve sample efficiency. We prove that this optimization preserves the correctness{—}i.e., our algorithm achieves a desired bound on the false positive rate. In our experiments, we show that our algorithm efficiently detects covariate shifts on multiple datasets{—}ImageNet, IWildCam, and Py150.

This paper addresses a safe planning and control problem for mobile robots operating in communication- and sensor-limited dynamic environments. In this case the robots cannot sense the objects around them and must instead rely on intermittent, external information about the environment, as e.g., in underwater applications. The challenge in this case is that the robots must plan using only this stale data, while accounting for any noise in the data or uncertainty in the environment. To address this challenge we propose a compositional technique which leverages neural networks to quickly plan and control a robot through crowded and dynamic environments using only intermittent information. Specifically, our tool uses reachability analysis and potential fields to train a neural network that is capable of generating safe control actions. We demonstrate our technique both in simulation with an underwater vehicle crossing a crowded shipping channel and with real experiments with ground vehicles in communication-and sensor-limited environments.

Anomaly detection is essential for preventing hazardous outcomes for safety-critical applications like autonomous driving. Given their safety-criticality, these applications benefit from provable bounds on various errors in anomaly detection. To achieve this goal in the semi-supervised setting, we propose to provide Probably Approximately Correct (PAC) guarantees on the false negative and false positive detection rates for anomaly detection algorithms. Our method (PAC-Wrap) can wrap around virtually any existing semi-supervised and unsupervised anomaly detection method, endowing it with rigorous guarantees. Our experiments with various anomaly detectors and datasets indicate that PAC-Wrap is broadly effective.

Uncertainty quantification is a key component of machine learning models targeted at safety-critical systems such as in healthcare or autonomous vehicles. We study this problem in the context of meta learning, where the goal is to quickly adapt a predictor to new tasks. In particular, we propose a novel algorithm to construct \emph{PAC prediction sets}, which capture uncertainty via sets of labels, that can be adapted to new tasks with only a few training examples. These prediction sets satisfy an extension of the typical PAC guarantee to the meta learning setting; in particular, the PAC guarantee holds with high probability over future tasks. We demonstrate the efficacy of our approach on four datasets across three application domains: mini-ImageNet and CIFAR10-C in the visual domain, FewRel in the language domain, and the CDC Heart Dataset in the medical domain. In particular, our prediction sets satisfy the PAC guarantee while having smaller size compared to other baselines that also satisfy this guarantee.

In Cyber-Physical Systems (CPS), integrating new technologies that interact with and control physical systems raises new security risks beyond the classical cyber security domain. These risks motivated many attack detectors that focus on the binary outcome. However, one pressing risk in CPS is hidden sensor attacks that are well-designed by powerful attackers who gained full knowledge of our systems and detector. The hidden attacks inject such a small malicious signal into sensor measurement that they can stay undetected but eventually lead to a significant deviation. Thus, to secure the CPS, we propose a detection framework to identify these sensor attacks that can drive the system's physical states to an unsafe state within a given period, even if they are not detected. First, we solve optimization problems to find the optimal hidden sensor attack that leads to the minimal distance to a pre-defined unsafe state region within an observation window for a given system and detector. Then, based on this algorithm, we perform offline profiling to search for a conditionally safe region, where the system states are guaranteed to be safe within the observation window as long as the detector does not raise any alerts. Finally, the framework can online discover potential hidden sensor attacks that endanger the system by checking if the current system state moves out of the region and raising a yellow alert. The evaluation shows that the optimal hidden sensor attack results in the minimum distance to unsafe, within a given observation window among existing hidden sensor attacks. We implemented our method on four linear simulators to show the effectiveness of our method. Additionally, we provided a discussion on the challenges of applying the proposed method to non-linear systems.

The emergence of vehicle connectivity technologies and associated applications have paved the way for increased consumer interest in connected vehicles. These modern day vehicles are now capable of sending/receiving vast amounts of data and offloading computation (which is one possible service) to servers thereby improving safety, comfort, driving experience, etc. In the early stages of connectivity, all the data communication and computation offloading happened between the cloud server and the vehicles. However, this is not feasible in scenarios having strict timing requirements and bandwidth cost constraints. Vehicular Edge Computing (VEC) demonstrated an efficient way to tackle the above problem. In order to optimally utilize the resources of the edge servers for data delivery, an efficient edge resource allocation framework needs to be developed. In a recent work, data/service delivery to connected vehicles assumed a worst-case scenario that all vehicles with routes passing through an edge appear in the edge coverage region simultaneously. However, this worst-case scenario is very pessimistic, which results in overestimation of edge resources. We address this by precisely computing the set of vehicles which simultaneously appear in the coverage region of an edge (which we call vehicle overlaps). In this work, we first propose an optimization framework for edge resource allocation that minimizes the bandwidth cost of data delivery to connected vehicles while considering the traffic flow and vehicle overlaps. Then, we propose an efficient heuristic to deliver data based on minimizing global edge bandwidth cost gradient under vehicle overlaps. We demonstrate the improvement in resource allocation considering vehicle overlaps. Using real world traffic data, we also demonstrate reduction in data delivery times using the proposed heuristic.

No abstract available.

Classification of clinical alarms is at the heart of prioritization, suppression, integration, postponement, and other methods of mitigating alarm fatigue. Since these methods directly affect clinical care, alarm classifiers, such as intelligent suppression systems, need to be evaluated in terms of their sensitivity and specificity, which is typically calculated on a labeled dataset of alarms. Unfortunately, the collection and particularly labeling of such datasets requires substantial effort and time, thus deterring hospitals from investigating mitigations of alarm fatigue. This article develops a lightweight method for evaluating alarm classifiers without perfect alarm labels. The method relies on probabilistic labels obtained from data programming—a labeling paradigm based on combining noisy and cheap-to-obtain labeling heuristics. Based on these labels, the method produces confidence bounds for the sensitivity/specificity values from a hypothetical evaluation with manual labeling. Our experiments on five alarm datasets collected at Children’s Hospital of Philadelphia show that the proposed method provides accurate bounds on the classifier’s sensitivity/specificity, appropriately reflecting the uncertainty from noisy labeling and limited sample sizes.

Providing reliable model uncertainty estimates is imperative to enabling robust decision making by autonomous agents and humans alike. While recently there have been significant advances in confidence calibration for trained models, examples with poor calibration persist in most calibrated models. Consequently, multiple techniques have been proposed that leverage label-invariant transformations of the input (i.e., an input manifold) to improve worst-case confidence calibration. However, manifold-based confidence calibration techniques generally do not scale and/or require expensive retraining when applied to models with large input spaces (e.g., ImageNet). In this paper, we present the recursive lossy label-invariant calibration (ReCal) technique that leverages label-invariant transformations of the input that induce a loss of discriminatory information to recursively group (and calibrate) inputs – without requiring model retraining. We show that ReCal outperforms other calibration methods on multiple datasets, especially, on large-scale datasets such as ImageNet.

Abstract This paper presents Verisig 2.0, a verification tool for closed-loop systems with neural network (NN) controllers. We focus on NNs with tanh/sigmoid activations and develop a Taylor-model-based reachability algorithm through Taylor model preconditioning and shrink wrapping. Furthermore, we provide a parallelized implementation that allows Verisig 2.0 to efficiently handle larger NNs than existing tools can. We provide an extensive evaluation over 10 benchmarks and compare Verisig 2.0 against three state-of-the-art verification tools. We show that Verisig 2.0 is both more accurate and faster, achieving speed-ups of up to 21x and 268x against different tools, respectively.

With the rise in state-of-the-art communication modes for vehicles such as vehicle to vehicle (V2V), vehicle to infrastructure (V2I) and vehicle to cloud (V2C), modern vehicles are increasingly being connected to cloud and fog/edge nodes. These vehicle connectivity modes have enabled the realization of Vehicular Edge Computing (VEC) paradigm, whereby vehicles can leverage fog/edge node resources for storage/computation. In a VEC system, vehicles receive very important and large quantity of data from edge nodes, which is termed as data delivery. In addition, edge nodes can execute some services and send the results back to the vehicle, which is called service delivery. Fast and efficient edge resource allocation for data/service delivery is important in order to serve as many vehicles as possible in the VEC system. However, edge resource allocation is complex with large number of edges and vehicles, while also considering vehicle flow parameters. In this work, we propose Edge-Pairwise Optimal Data/Service Delivery (E-PODS), which is a fast and efficient heuristic for data/service delivery. Through experiments with synthetic and real vehicular traces, we demonstrate that E-PODS is considerably faster than the optimal approach, while making resource allocations that are close to optimal in terms of total edge bandwidth cost and number of serviced vehicles.

This article addresses the problem of verifying the safety of autonomous systems with neural network (NN) controllers. We focus on NNs with sigmoid/tanh activations and use the fact that the sigmoid/tanh is the solution to a quadratic differential equation. This allows us to convert the NN into an equivalent hybrid system and cast the problem as a hybrid system verification problem, which can be solved by existing tools. Furthermore, we improve the scalability of the proposed method by approximating the sigmoid with a Taylor series with worst-case error bounds. Finally, we provide an evaluation over four benchmarks, including comparisons with alternative approaches based on mixed integer linear programming as well as on star sets.

The increasing autonomy and connectivity in cyber-physical systems (CPS) come with new security vulnerabilities that are easily exploitable by malicious attackers to spoof a system to perform dangerous actions. While the vast majority of existing works focus on attack prevention and detection, the key question is “what to do after detecting an attack?”. This problem attracts fairly rare attention though its significance is emphasized by the need to mitigate or even eliminate attack impacts on a system. In this article, we study this attack response problem and propose novel real-time recovery for securing CPS. First, this work’s core component is a recovery control calculator using a Linear-Quadratic Regulator (LQR) with timing and safety constraints. This component can smoothly steer back a physical system under control to a target state set before a safe deadline and maintain the system state in the set once it is driven to it. We further propose an Alternating Direction Method of Multipliers (ADMM) based algorithm that can fast solve the LQR-based recovery problem. Second, supporting components for the attack recovery computation include a checkpointer, a state reconstructor, and a deadline estimator. To realize these components respectively, we propose (i) a sliding-window-based checkpointing protocol that governs sufficient trustworthy data, (ii) a state reconstruction approach that uses the checkpointed data to estimate the current system state, and (iii) a reachability-based approach to conservatively estimate a safe deadline. Finally, we implement our approach and demonstrate its effectiveness in dealing with totally 15 experimental scenarios which are designed based on 5 CPS simulators and 3 types of sensor attacks.

Reliable uncertainty estimates are an important tool for helping autonomous agents or human decision makers understand and lever-age predictive models. However, existing approaches to estimating uncertainty largely ignore the possibility of covariate shift—i.e.,where the real-world data distribution may differ from the training distribution. As a consequence, existing algorithms can overestimate certainty, possibly yielding a false sense of confidence in the predictive model. We pro-pose an algorithm for calibrating predictions that accounts for the possibility of covariate shift, given labeled examples from the train-ing distribution and unlabeled examples from the real-world distribution. Our algorithm uses importance weighting to correct for the shift from the training to the real-world distribution. However, importance weighting relies on the training and real-world distributions to be sufficiently close. Building on ideas from domain adaptation, we additionally learn a feature map that tries to equalize these two distributions. In an empirical evaluation, we show that our proposed approach outperforms existing approaches to calibrated prediction when there is covariate shift.

This paper describes a verification case study on an autonomous racing car with a neural network (NN) controller. Although several verification approaches have been recently proposed, they have only been evaluated on low-dimensional systems or systems with constrained environments. To explore the limits of existing approaches, we present a challenging benchmark in which the NN takes raw LiDAR measurements as input and outputs steering for the car. We train a dozen NNs using reinforcement learning (RL) and show that the state of the art in verification can handle systems with around 40 LiDAR rays. Furthermore, we perform real experiments to investigate the benefits and limitations of verification with respect to the sim2real gap, i.e., the difference between a system's modeled and real performance. We identify cases, similar to the modeled environment, in which verification is strongly correlated with safe behavior. Finally, we illustrate LiDAR fault patterns that can be used to develop robust and safe RL algorithms.

Model-based design offers a promising approach for assisting developers to build reliable and secure cyber-physical systems in a systematic manner. In this methodology, a designer first constructs a model, with mathematically precise semantics, of the system under design, and performs extensive analysis with respect to correctness requirements before generating the implementation from the model. However, as new vulnerabilities are discovered, requirements evolve aimed at ensuring resiliency. There is currently a shortage of an inexpensive, automated software that can effectively repair the initial design, and a model-based system developer regularly needs to redesign and reimplement the system from scratch. In this paper, we propose a new methodology along with a MATLAB software called REAFFIRM to facilitate the model-based repair for improving the resiliency of cyber-physical systems. REAFFIRM takes as inputs 1) an original hybrid system modeled as a Simulink/Stateflow diagram, 2) a given resiliency pattern specified as a model transformation script, and 3) a safety requirement expressed as a Signal Temporal Logic formula, and outputs a repaired model which satisfies the requirement. The tool consists of two main modules, model transformation followed by model synthesis. While the latter component is built on top of the falsification tool Breach, to implement the former, we introduce a new model transformation language for hybrid systems, which we call HATL, to allow a designer to specify resiliency patterns. To evaluate the proposed approach, we use REAFFIRM to automatically synthesize the repaired models of four different case studies.

Runtime monitoring is a vital part of safety-critical systems. However, early stage assurance of monitoring quality is currently limited: it relies either on complex models that might be inaccurate in unknown ways or on data that would only be available once the system has been built. To address this issue, we propose a compositional framework for modeling and analysis of noisy monitoring systems. Our novel 3-value detector model uses probability spaces to represent atomic (noncomposite) detectors, and it composes them into a temporal logic-based monitor. The error rates of these monitors are estimated by our analysis engine, which combines symbolic probability algebra, independence inference, and estimation from labeled detection data. Our evaluation on an autonomous underwater vehicle found that our framework produces accurate estimates of error rates while using only detector traces, without any monitor traces. Furthermore, when data are scarce, our approach shows higher accuracy than noncompositional data-driven estimates from monitor traces. Thus, this article enables accurate evaluation of logical monitors in early design stages before deploying them.

This paper presents Verisig, a hybrid system approach to verifying safety properties of closed-loop systems using neural networks as controllers. We focus on sigmoid-based networks and exploit the fact that the sigmoid is the solution to a quadratic differential equation, which allows us to transform the neural network into an equivalent hybrid system. By composing the network's hybrid system with the plant's, we transform the problem into a hybrid system verification problem which can be solved using state-of-the-art reachability tools. We show that reachability is decidable for networks with one hidden layer and decidable for general networks if Schanuel's conjecture is true. We evaluate the applicability and scalability of Verisig in two case studies, one from reinforcement learning and one in which the neural network is used to approximate a model predictive controller.

Information flow analysis is an effective way to check useful security properties, such as whether secret information can leak to adversaries. Despite being widely investigated in the realm of programming languages, information-flow-based security analysis has not been widely studied in the domain of cyber-physical systems (CPS). CPS provide interesting challenges to traditional type-based techniques, as they model mixed discrete-continuous behaviors and are usually expressed as a composition of state machines. In this paper, we propose a lightweight static analysis methodology that enables information security properties for CPS models. We introduce a set of security rules for hybrid automata that characterizes the property of non-interference. Based on those rules, we propose an algorithm that generates security constraints between each sub-component of hybrid automata, and then transforms these constraints into a directed dependency graph to search for non-interference violations. The proposed algorithm can be applied directly to parallel compositions of automata without resorting to model-flattening techniques. Our static checker works on hybrid systems modeled in Simulink/Stateflow format and decides whether or not the model satisfies non-interference given a user-provided security annotation for each variable. Moreover, our approach can also infer the security labels of variables, allowing a designer to verify the correctness of partial security annotations. We demonstrate the potential benefits of the proposed methodology on two case studies.

This paper presents CaM, a holistic cache and memory bandwidth resource allocation strategy for multicore real-time systems. CaM is designed for partitioned scheduling, where tasks are mapped onto cores, and the shared cache and memory bandwidth resources are partitioned among cores to reduce resource interferences due to concurrent accesses. Based on our extension of LITMUSRT with Intel's Cache Allocation Technology and MemGuard, we present an experimental evaluation of the relationship between the allocation of cache and memory bandwidth resources and a task's WCET. Our resource allocation strategy exploits this relationship to map tasks onto cores, and to compute the resource allocation for each core. By grouping tasks with similar characteristics (in terms of resource demands) to the same core, it enables tasks on each core to fully utilize the assigned resources. In addition, based on the tasks' execution time behaviors with respect to their assigned resources, we can determine a desirable allocation that maximizes schedulability under resource constraints. Extensive evaluations using real-world benchmarks show that CaM offers near optimal schedulability performance while being highly efficient, and that it substantially outperforms existing solutions.

In the model-based development of controller software, the use of an unverified code generator/transformer may result in introducing unintended bugs in the controller implementation. To assure the correctness of the controller software in the absence of verified code generator/transformer, we develop Linear Controller Verifier (LCV), a tool to verify a linear controller implementation against its original linear controller model. LCV takes as input a Simulink block diagram model and a C code implementation, represents them as linear time-invariant system models respectively, and verifies an input-output equivalence between them. We demonstrate that LCV successfully detects a known bug of a widely used code generator and an unknown bug of a code transformer. We also demonstrate the scalability of LCV and a real-world case study with the controller of a quadrotor system.

A cyber–physical system (CPS) consists of physical devices and operations that are closely controlled and monitored by computational processes. This concrete connection involves the real-time actuation of physical devices, real-time sensing of physical quantities, and modeling and control of the overall system. A CPS may be connected to the Internet of Things (IoT) and, if so, should be considered in that context; the IoT is essential to realize a vision of future CPSs, where numerous devices are connected over the Internet, allowing them to collect information about the real world in real time, and share it with other systems and physical devices.

Safety-critical embedded systems often need to meet dependability requirements such as strict input/output timing constraints. To meet the timing requirements, the code generation (e.g., C code) from timed models needs to determine the timing parameters that indicate when the code has to perform I/O with its platform. We propose a novel framework to determine such timing parameters from platform-independent timed models. Our framework involves two transformations. The first transformation systematically extends the platform-independent model by explicitly modeling input/output processing (e.g., sampling or interrupt-based) and the code invocation (e.g., periodic or aperiodic) mechanisms. Then, we verify if the resulting platform-specific model meets the timing requirements. In the case that the resulting model does not satisfy the timing requirements, we apply the second transformation to compensate the platform delay via adjusting the timing parameters at the code level. We formulate the adjustment mechanism using integer linear programming. If such an adjustment is feasible, generating the code with the new timing parameters guarantees the implemented system to meet the timing requirements. We validate our framework with case studies running on Patient-Controlled Analgesia (PCA) infusion pump platforms.

The paradigm of connected vehicles is fast gaining lot of attraction in the automotive industry. Recently, a lot of technological innovation has been pushed through to realize this paradigm using vehicle to cloud (V2C), infrastructure (V2I) and vehicle (V2V) communications. This has also opened the doors for efficient delivery of data/service to the vehicles via edge devices that are closer to the vehicles. In this work, we propose an optimization framework that can be used to deliver data/service to the connected vehicles such that a bandwidth cost objective is optimized. For the first time, we also integrate a vehicle flow model in the optimization framework to model the traffic flow in the coverage area of the edges. Using the optimization framework, we study the variation of the optimal bandwidth cost for varying problem sizes and vehicle flow model parameter values for both data and service delivery.

The disruptive vision of Medical Cyber-Physical Systems (MCPS) enables the promising next-generation of eHealth systems that are intended to interoperate efficiently, safely, and securely. Safety-critical interconnected systems that analyze patients' vital signs gathered from medical devices, infer the state of the patient's health, and start treatments issuing information to doctors and medical actuators should improve the patients' safety in a cost-efficient fashion. Despite the benefits provided by the MCPS vision, it also opens the door to critical challenges like the security and privacy, Quality of Service (QoS), and high availability of the devices composed to support the MCPS scenario. The Integrated Clinical Environment (ICE) standard is a significant step toward promoting open coordination of heterogeneous medical devices by considering the previous challenges. However, a lot of effort is still required in order to cover the whole aspects of these challenges and enable the future eHealth. In this context, we identify critical shortcomings of ICE using challenge scenarios regarding security, QoS, and high availability. According to these concerns and following the ICE standard, we propose the novel ICE++ architecture, which is oriented to the Mobile Edge Computing paradigm and combines SDN and NFV techniques to manage efficiently and automatically the MCPS elements taking into account its security, QoS, and high availability. Finally, we perform experiments that demonstrate the potential usefulness of our solution regarding the efficient and automatic management of the ICE components.

Signal Temporal Logic (STL) is a prominent specification formalism for real-time systems, and monitoring these specifications, specially when (for different reasons such as learning) behavior of systems can change over time, is quite important. There are three main challenges in this area: (1) full observation of system state is not possible due to noise or nuisance parameters, (2) the whole execution is not available during the monitoring, and (3) computational complexity of monitoring continuous time signals is very high. Although, each of these challenges has been addressed by different works, to the best of our knowledge, no one has addressed them all together. In this paper, we show how to extend any parameter invariant test procedure for single points in time to a parameter invariant test procedure for efficiently monitoring continuous time executions of a system against STL properties. We also show, how to extend probabilistic error guarantee of the input test procedure to a probabilistic error guarantee for the constructed test procedure.

We present a compositional framework for the specification and analysis of hierarchical scheduling systems (HSS). Firstly we provide a generic formal model, which can be used to describe any type of scheduling system. The concept of Job automata is introduced in order to model job instantiation patterns. We model the interaction between different levels in the hierarchy through the use of state-based resource models. Our notion of resource model is general enough to capture multi-core architectures, preemptiveness and non-determinism.

In many application scenarios, data consumed by real-time tasks are required to meet a maximum age, or freshness, guarantee. In this paper, we consider the end-to-end freshness constraint of data that is passed along a chain of tasks in a uniprocessor setting. We do so with few assumptions regarding the scheduling algorithm used. We present a method for selecting the periods of tasks in chains of length two and three such that the end-to-end freshness requirement is satisfied, and then extend our method to arbitrary chains. We perform evaluations of both methods using parameters from an embedded benchmark suite (E3S) and several schedulers to support our result.

The Internet of Medical Things (IoMT) is poised to revolutionize medicine. However, medical device communication, coordination, and interoperability present challenges for IoMT applications due to safety, security, and privacy concerns. These challenges can be addressed by developing an open platform for IoMT that can provide guarantees on safety, security and privacy. As a first step, we introduce OpenICE-lite, a middleware for medical device interoperability that also provides security guarantees and allows other IoMT applications to view/analyze the data in real time. We describe two applications that currently utilize OpenICE-lite, namely (i) a critical pulmonary shunt predictor for infants during surgery; (ii) a remote pulmonary monitoring systems (RePulmo). Implementations of both systems are utilized by the Children's Hospital of Philadelphia (CHOP) as quality improvements to patient care.

Real-time virtualization is an emerging technology for embedded systems integration and latency-sensitive cloud applications. Earlier real-time virtualization platforms require offline configuration of the scheduling parameters of virtual machines (VMs) based on their worst-case workloads, but this static approach results in pessimistic resource allocation when the workloads in the VMs change dynamically. Here, we present Multi-Mode-Xen (M2-Xen), a real-time virtualization platform for dynamic real-time systems where VMs can operate in modes with different CPU resource requirements at run-time. M2-Xen has three salient capabilities: (1) dynamic allocation of CPU resources among VMs in response to their mode changes, (2) overload avoidance at both the VM and host levels during mode transitions, and (3) fast mode transitions between different modes. M2-Xen has been implemented within Xen 4.8 using the real-time deferrable server (RTDS) scheduler. Experimental results show that M2-Xen maintains real-time performance in different modes, avoids overload during mode changes, and performs fast mode transitions.

The tight interaction between information technology and the physical world inherent in cyber-physical systems (CPS) can challenge traditional approaches for monitoring safety and security. Data collected for robust CPS monitoring is often sparse and may lack rich training data describing critical events/attacks. Moreover, CPS often operate in diverse environments that can have significant inter/intra-system variability. Furthermore, CPS monitors that are not robust to data sparsity and inter/intra-system variability may result in inconsistent performance and may not be trusted for monitoring safety and security. Towards overcoming these challenges, this paper presents recent work on the design of parameter-invariant (PAIN) monitors for CPS. PAIN monitors are designed such that unknown events and system variability minimally affect the monitor performance. This work describes how PAIN designs can achieve a constant false alarm rate (CFAR) in the presence of data sparsity and intra/inter system variance in real-world CPS. To demonstrate the design of PAIN monitors for safety monitoring in CPS with different types of dynamics, we consider systems with networked dynamics, linear-time invariant dynamics, and hybrid dynamics that are discussed through case studies for building actuator fault detection, meal detection in type I diabetes, and detecting hypoxia caused by pulmonary shunts in infants. In all applications, the PAIN monitor is shown to have (significantly) less variance in monitoring performance and (often) outperforms other competing approaches in the literature. Finally, an initial application of PAIN monitoring for CPS security is presented along with challenges and research directions for future security monitoring deployments.

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.

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.

No abstract available.

Cyber-physical systems (CSPs) are demanding energy-efficient design not only of hardware (HW), but also of software (SW). Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Manage (DPM) are most popular techniques to improve the energy efficiency. However, contemporary complicated HW and SW designs requires more elaborate and sophisticated energy management and efficiency evaluation techniques. This paper is concerned about energy supply planning for real-time scheduling systems (units) of which tasks need to meet deadlines. This paper presents a model-based compositional energy planning technique that computes a minimal ratio of processor frequency that preserves schedulability of independent and preemptive tasks. The minimal ratio of processor frequency can be used to plan the energy supply of real-time components. Our model-based technique is extensible by refining our model with additional features so that energy management techniques and their energy efficiency can be evaluated by model checking techniques. We exploit the compositional framework for hierarchical scheduling systems and provide a new resource model for the frequency computation. As results, our use-case for avionics software components shows that our new method outperforms the classical real-time calculus (RTC) method, requiring 36.21% less frequency ratio on average for scheduling units under RM than the RTC method.

This paper presents vCAT, a novel design for dynamic shared cache management on multicore virtualization platforms based on Intel's Cache Allocation Technology (CAT). Our design achieves strong isolation at both task and VM levels through cache partition virtualization, which works in a similar way as memory virtualization, but has challenges that are unique to cache and CAT. To demonstrate the feasibility and benefits of our design, we provide a prototype implementation of vCAT, and we present an extensive set of microbenchmarks and performance evaluation results on the PARSEC benchmarks and synthetic workloads, for both static and dynamic allocations. The evaluation results show that (i) vCAT can be implemented with minimal overhead, (ii) it can be used to mitigate shared cache interference, which could have caused task WCET increased by up to 7.2×, (iii) static management in vCAT can increase system utilization by up to 7× compared to a system without cache management, and (iv) dynamic management substantially outperforms static management in terms of schedulable utilization (increase by up to 3× in our multi-mode example use case).

TrapFetch is trained by monitoring the read requests issued by an application. It detects bursts of disk reads, determines the appropriate addresses at which breakpoints should be inserted in the application and library codes prior to the bursts of reads, and then logs this information with the data requested during the interval between each consecutive pair of breakpoints. When the application and library codes are loaded from the disk into memory, TrapFetch inserts breakpoints at the designated addresses based on the logs. During subsequent runs, TrapFetch is invoked at each breakpoint when it prefetches the corresponding data into the page cache. This approach is effective during both launch and run-time. TrapFetch operates at the user level, thus avoiding interference with other applications. In experiments on five popular applications (FlightGear, SpeedDreams 2, Pillars of Eternity, Eclipse, and VegaStrike), TrapFetch reduced the time for launch by up to 39.7% and time for run-time data-loading by up to 63.7%.

The global mobile traffic is exponentially growing and more than 90% of the Internet traffic uses Transmission Control Protocol (TCP) for reliable transmission. However, TCP is known to perform poorly over unreliable wireless networks. One of the promising families of solutions to improve the performance of TCP is centered on Split-TCP. However, while Split-TCP may improve the protocol performance, it is vulnerable due to the broken end-to-end semantics. Several variants have been proposed to overcome this pitfall, but while they address the broken semantics, they also defeat the main purpose by compromising the TCP performance gains. In this paper, we propose a novel Enhanced Split-TCP (ES-TCP) mechanism, which significantly improves the application throughput without breaking the end-to-end TCP semantics. Experimental results show that the proposed ES-TCP may boost the TCP throughput by more than 60% in average when exercised over an operational 4G LTE network. Furthermore, the TCP throughput performance improvement may be even over 200%, depending on the network and usage conditions. We expect such throughput gains may be even greater when advanced radio technologies, such as 5G, are deployed. For these reasons, the ES-TCP is a promising transport layer solution for the current and next generation networks.

This article is concerned with the security of modern Cyber-Physical Systems in the presence of transient sensor faults. We consider a system with multiple sensors measuring the same physical variable, where each sensor provides an interval with all possible values of the true state. We note that some sensors might output faulty readings and others may be controlled by a malicious attacker. Differing from previous works, in this article, we aim to distinguish between faults and attacks and develop an attack detection algorithm for the latter only. To do this, we note that there are two kinds of faults—transient and permanent; the former are benign and short-lived, whereas the latter may have dangerous consequences on system performance. We argue that sensors have an underlying transient fault model that quantifies the amount of time in which transient faults can occur. In addition, we provide a framework for developing such a model if it is not provided by manufacturers. Attacks can manifest as either transient or permanent faults depending on the attacker’s goal. We provide different techniques for handling each kind. For the former, we analyze the worst-case performance of sensor fusion over time given each sensor’s transient fault model and develop a filtered fusion interval that is guaranteed to contain the true value and is bounded in size. To deal with attacks that do not comply with sensors’ transient fault models, we propose a sound attack detection algorithm based on pairwise inconsistencies between sensor measurements. Finally, we provide a real-data case study on an unmanned ground vehicle to evaluate the various aspects of this article.

Recent embedded systems are becoming integrated systems with components of different criticality. To tackle this, mixed-criticality systems aim to provide different levels of timing assurance to components of different criticality levels while achieving efficient resource utilization. Many approaches have been proposed to execute more lower-criticality tasks without affecting the timeliness of higher-criticality tasks. Those previous approaches however have at least one of the two limitations; i) they penalize all lower-criticality tasks at once upon a certain situation, or ii) they make the decision how to penalize lower-criticality tasks at design time. As a consequence, they under-utilize resources by imposing an excessive penalty on low-criticality tasks. Unlike those existing studies, we present a novel framework, called MC-ADAPT, that aims to minimally penalize lower-criticality tasks by fully reflecting the dynamically changing system behavior into adaptive decision making. Towards this, we propose a new scheduling algorithm and develop its runtime schedulability analysis capable of capturing the dynamic system state. Our proposed algorithm adaptively determines which task to drop based on the runtime analysis. To determine the quality of task dropping solution, we propose the speedup factor for task dropping while the conventional use of the speedup factor only evaluates MC scheduling algorithms in terms of the worst-case schedulability. We apply the speedup factor for a newly-defined task dropping problem that evaluates task dropping solution under different runtime scheduling scenarios. We derive that MC-ADAPT has a speedup factor of 1.619 for task drop. This implies that MC-ADAPT can behave the same as the optimal scheduling algorithm with optimal task dropping strategy does under any runtime scenario if the system is sped up by a factor of 1.619.

An increasing amount of distributed real-time systems and other critical infrastructure now rely on Data Distribution Service (DDS) middleware for timely dissementation of data between system nodes. While DDS has been designed specifically for use in distributed real-time systems and exposes a number of QoS properties to programmers, DDS fails to lift time fully into the programming abstraction. The reason for this is simple: DDS cannot directly control the underlying network to ensure that messages always arrive to their destination on time.

The worldwide mobile traffic is growing rapidly and more than 90% of the internet traffic relies on the Transmission Control Protocol (TCP) protocol, which is known to have a poor performance over unreliable wireless networks. One of the promising TCP enhancement mechanisms that are being considered by the wireless network operators is the Split-TCP. It is also quite well known that the Split-TCP suffers from broken end-to-end protocol semantics, and this may be a significant drawback in some scenarios, where large file transmissions may get aborted after consuming a large volume of network resources. There are various enhancements to overcome this pitfall, but at the expense of a loss in performance. In this paper, we propose a novel Advanced Split-TCP (AS-TCP) mechanism, designed with the goal to improve significantly the application throughput while maintaining the end-to-end protocol semantics down to the byte level, as through the conventional TCP. Our findings indicate that the TCP throughput gains achieved through AS-TCP with respect to a conventional TCP may be above 60% over a 4G LTE network. Furthermore, AS-TCP may enable TCP throughput gains in excess of 200% for some network and traffic conditions. The throughput gains are expected to be even greater when advanced radio technologies are deployed. Hence, we anticipate that AS-TCP will enable the Split-TCP mechanism to be widely deployed in both current and next generation networks, such as 5G.

In this paper we consider an online planning problem for unmanned aerial vehicle (UAV) operations. Specifically, a UAV has the task of reaching a goal from a set of possible goals while minimizing the amount of energy required. Due to unforeseen disturbances, it is possible that initially attractive goals might end up being very expensive during the execution. Thus, two main problems are investigated here: i) how to predict and plan the motion of the UAV at run time to minimize its energy consumption and ii) when to schedule next replanning time to avoid unnecessary periodic re-evaluation executions. Our approach considers a nonlinear model of the system for which a model predictive controller is used to determine the desired control inputs for each possible goal. These control inputs are then used to estimate the energy required to reach the different goals. Finally, a self-triggered scheduling policy determines how long to wait before replanning the goal to aim for. The proposed framework is validated through simulations and experiments in which a quadrotor must choose and reach some goal while being subject to external disturbances.

Advances in automation have the potential to reduce the workload required for human planning and execution of missions carried out by robotic systems such as unmanned aerial vehicles (UAVs). However, automation can also result in an increase in system complexity and a corresponding decrease in system transparency, which makes identifying and reasoning about errors in mission plans more difficult. To help explain errors in robotic planning systems, we define a notion of structured probabilistic counterexamples, which provide human-interpretable diagnostic information about requirements violations resulting from complex probabilistic robotic behavior. We propose an approach for generating such counterexamples using mixed integer linear programming and demonstrate the usefulness of our approach via a case study of UAV mission planning demonstrated in the AMASE multi-UAV simulator.

We introduce gFPca, a cache-aware global pre-emptive fixed-priority (FP) scheduling algorithm with dynamic cache allocation for multicore systems, and we present its analysis and implementation. We introduce a new overhead-aware analysis that integrates several novel ideas to safely and tightly account for the cache overhead. Our evaluation shows that the proposed overhead-accounting approach is highly accurate, and that gFPca improves the schedulability of cache-intensive tasksets substantially compared to the cache-agnostic global FP algorithm. Our evaluation also shows that gFPca outperforms the existing cache-aware non- preemptive global FP algorithm in most cases. Through our implementation and empirical evaluation, we demonstrate the feasibility of cache-aware global scheduling with dynamic cache allocation and highlight scenarios in which gFPca is especially useful in practice.

Optional software-based features are increasingly becoming an important cost driver in automotive systems. These include features pertaining to active safety, infotainment, etc. Currently, these optional features are integrated into the vehicles at the factory during assembly. This severely restricts the flexibility of the customer to select and use features on-demand and therefore, the customer will either have to be satisfied with an available set of feature options or pre-order a car with the required features from the manufacturer resulting in considerable delay. In order to increase flexibility and reduce the delay, it is necessary to provide the option to configure the vehicle on-demand at the dealership or remotely. In this paper, we present our vision and challenges involved in developing a platform infrastructure that allows on-demand deployment of automotive safety features and ensures their correct execution.

Since Cyber Physical Systems (CPS) are widely used inmany safety-critical domains these days, critical properties such as robustness and resilience are required for such systems. To increase the robustness and the resilience of CPS, various sensor fusion techniques have been studied [1], [2],[3], [4]. These fusion techniques are based on certain sensor models, which broadly fall into two categories: probabilistic model and abstract model. The probabilistic sensor model [1] uses certain noise distributions on sensors (e.g., Gaussian), which is wellsuited for analyzing the systems' expected performance inthe average case. However, wrong assumptions on noise distributions may be in danger of being vulnerable to sensor attacks. On the other hand, the abstract sensor model [2] usesthe worst-case error bound of sensors. Thus, this model iswell suited for the systems' worst-case performance, whichis highly relevant to the case of sensor attacks [3].In this work, we study a hybrid sensor fusion that usesboth probabilistic and abstract sensor models to be able tobenefit from both. We demonstrate the validation of ourhybrid sensor fusion technique using an unmanned groundvehicle called Jackal.

This article focuses on the design of safe and attack-resilient Cyber-Physical Systems (CPS) equipped with multiple sensors measuring the same physical variable. A malicious attacker may be able to disrupt system performance through compromising a subset of these sensors. Consequently, we develop a precise and resilient sensor fusion algorithm that combines the data received from all sensors by taking into account their specified precisions. In particular, we note that in the presence of a shared bus, in which messages are broadcast to all nodes in the network, the attacker’s impact depends on what sensors he has seen before sending the corrupted measurements. Therefore, we explore the effects of communication schedules on the performance of sensor fusion and provide theoretical and experimental results advocating for the use of the Ascending schedule, which orders sensor transmissions according to their precision starting from the most precise. In addition, to improve the accuracy of the sensor fusion algorithm, we consider the dynamics of the system in order to incorporate past measurements at the current time. Possible ways of mapping sensor measurement history are investigated in the article and are compared in terms of the confidence in the final output of the sensor fusion. We show that the precision of the algorithm using history is never worse than the no-history one, while the benefits may be significant. Furthermore, we utilize the complementary properties of the two methods and show that their combination results in a more precise and resilient algorithm. Finally, we validate our approach in simulation and experiments on a real unmanned ground robot.

Clouds have become appealing platforms for not only general-purpose applications, but also real-time ones. However, current clouds cannot provide real-time performance to virtual machines (VMs). We observe the demand and the advantage of co-hosting real-time (RT) VMs with non-real-time (regular) VMs in a same cloud. RT VMs can benefit from the easily deployed, elastic resource provisioning provided by the cloud, while regular VMs effectively utilize remaining resources without affecting the performance of RT VMs through proper resource management at both the cloud and the hyper visor levels. This paper presents RT-Open Stack, a cloud CPU resource management system for co-hosting real-time and regular VMs. RT-Open Stack entails three main contributions: (1) integration of a real-time hyper visor (RT-Xen) and a cloud management system (Open Stack) through a real-time resource interface, (2) a real-time VM scheduler to allow regular VMs to share hosts with RT VMs without interfering the real-time performance of RT VMs, and (3) a VM-to-host mapping strategy that provisions real-time performance to RT VMs while allowing effective resource sharing with regular VMs. Experimental results demonstrate that RT-Open Stack can effectively improve the real-time performance of RT VMs while allowing regular VMs to fully utilize the remaining CPU resources.

We consider the problem of verification of software implementations of linear time-invariant controllers. Commonly, different implementations use different representations of the controller's state, for example due to optimizations in a third-party code generator. To accommodate this variation, we exploit input-output controller specification captured by the controller's transfer function and show how to automatically verify correctness of C code controller implementations using a Frama-C/Why3/Z3 toolchain. Scalability of the approach is evaluated using randomly generated controller specifications of realistic size.

The analysis of probabilistic schedulability explores all possible combinations of the probabilities of task attributes, which can easily lead to exponential computation time [24]. In this paper, we present a flexible schedulability analysis framework for periodic and sporadic tasks having probabilistic attributes where the computation time scales linearly in the size of analyzed systems. The framework is given in terms of a set of Parameterized Stopwatch Automata (PSA) models, which leads to a large degree of flexibility. Probability distributions for response time are generated using statistical model checking (UPPAAL SMC) while the overall schedulability can be checked using symbolic model checking (UPPAAL). We also define PoMD (percentage of missed deadlines) as a measure of the probabilistic schedulability of systems. To evaluate our approach, we compare the time used for computing response times and the analysis results using similar task models to that of a related analytical approach.

To manage design complexity and provide verification tractability, models of complex cyber-physical systems are typically hierarchically organized into multiple abstraction layers. High-level analysis explores interactions of the system with its physical environment, while embedded software is developed separately based on derived requirements. This separation of low-level and high-level analysis also gives hope to scalability, because we are able to use tools that are appropriate for each level. When attempting to perform compositional reasoning in such an environment, care must be taken to ensure that results from one tool can be used in another to avoid errors due to “mismatches” in the semantics of the underlying formalisms. This paper proposes a formal approach for linking high-level continuous time models and lower-level discrete time models.

Many safety-critical real-time embedded systems need to meet stringent timing constraints such as preserving delay bounds between input and output events. In model-based development, a system is often implemented by using a code generator to automatically generate source code from system models, and integrating the generated source code with a platform. It is challenging to guarantee that the implemented systems preserve required timing constraints, because the timed behavior of the source code and the platform is closely intertwined. In this paper, we address this challenge by proposing a model transformation approach for the code generation. Our approach compensates the platform-processing delays by adjusting the timing parameters in system models, based on an Integer Linear Programming problem formulation. We demonstrate the usefulness of our approach via a case study of infusion pump systems. Experimental results show that the code generated using our approach can better preserve the timing constraints.

Wireless insulin pumps have been widely deployed in hospitals and home healthcare systems. Most of them have limited security mechanisms embedded to protect them from malicious attacks. In this paper, two attacks against insulin pump systems via wireless links are investigated: a single acute overdose with a significant amount of medication and a chronic overdose with a small amount of extra medication over a long time period. They can be launched unobtrusively and may jeopardize patients' lives. It is very urgent to protect patients from these attacks. We propose a novel personalized patient infusion pattern based access control scheme (PIPAC) for wireless insulin pumps. This scheme employs supervised learning approaches to learn normal patient infusion patterns in terms of the dosage amount, rate, and time of infusion, which are automatically recorded in insulin pump logs. The generated regression models are used to dynamically configure a safe infusion range for abnormal infusion identification. This model includes two sub models for bolus (one type of insulin) abnormal dosage detection and basal abnormal rate detection. The proposed algorithms are evaluated with real insulin pump. The evaluation results demonstrate that our scheme is able to detect the two attacks with a very high success rate.

Increased adoption of electronic health records has lead to a large amount of available patient data. However, these data are often difficult to access and visualize, leading to chokepoints in clinical practice. Wandering Data is a web application designed to deliver useful, intuitive visualizations of patient data, with a focus on efficient communication of information through uniform delivery and thoughtful design. In this paper we describe the system's development, structure, and functionality.

There is scant data regarding thresholds for intraoperative hypo tension (IOH) in children less than 1 year of age. We used anesthesia information management systems (AIMS) data to develop reference values for normal per operative blood pressures (BPs) and IOH in the infant population undergoing thoracic surgery. Manipulating large data sets such as AIMS vital sign data can be challenging, thus, we developed custom software in Python to organize the data, parse the files, perform the appropriate calculations, and output the information in graphical form. In general, the results show that BP values at each percentile gradually increase as the patient's age increases. We plan to develop a broader set of reference values for normal BPs under anesthesia and thresholds for IOH, irrespective of the type of surgery. These can be used to ascertain the relationship of IOH to morbidity and mortality in the perioperative period and beyond.

This work considers the problem of attack-resilient sensor fusion in an autonomous system where multiple sensors measure the same physical variable. A malicious attacker may corrupt a subset of these sensors and send wrong measurements to the controller on their behalf, potentially compromising the safety of the system. We formalize the goals and constraints of such an attacker who also wants to avoid detection by the system. We argue that the attacker's capabilities depend on the amount of information she has about the correct sensors' measurements. In the presence of a shared bus where messages are broadcast to all components connected to the network, the attacker may consider all other measurements before sending her own in order to achieve maximal impact. Consequently, we investigate effects of communication schedules on sensor fusion performance. We provide worst- and average-case results in support of the Ascending schedule, where sensors send their measurements in a fixed succession based on their precision, starting from the most precise sensors. Finally, we provide a case study to illustrate the use of this approach.

The model-based implementation is to derive an implementation from a model that has been shown to meet requirements. Even though this approach can be used to guarantee that an implementation satisfies functional requirements that are shown to be correct at the model level, it is still challenging to assure timing requirements at the implementation level. We propose a layered approach in testing timing requirements conformance of implemented systems developed by model-based implementation. In our approach, the abstraction boundary of the implemented system is formally defined using Parnas' four-variables model. Then, the proposed approach tests timing aspects of the interaction between the auto-generated code and the target platform-dependent code based on the four-variables. This approach aims at not only detecting the timing requirement violation, but also at measuring delay-segments that contribute to the timing deviation of the implemented system w.r.t. the model. We show the case study of testing timing requirements of an infusion pump system to illustrate the applicability of the proposed framework.

Recent years have witnessed two major trends in the development of complex real-time embedded systems. First, to reduce cost and enhance flexibility, multiple systems are sharing common computing platforms via virtualization technology, instead of being deployed separately on physically isolated hosts. Second, multicore processors are increasingly being used in real-time systems. The integration of real-time systems as virtual machines (VMs) atop common multicore platforms raises significant new research challenges in meeting the real-time performance requirements of multiple systems. This paper advances the state of the art in real-time virtualization by designing and implementing RT-Xen 2.0, a new real-time multicore VM scheduling framework in the popular Xen virtual machine monitor (VMM). RT-Xen 2.0 realizes a suite of real-time VM scheduling policies spanning the design space. We implement both global and partitioned VM schedulers; each scheduler can be configured to support dynamic or static priorities and to run VMs as periodic or deferrable servers. We present a comprehensive experimental evaluation that provides important insights into real-time scheduling on virtualized multicore platforms: (1) both global and partitioned VM scheduling can be implemented in the VMM at moderate overhead; (2) at the VMM level, while compositional scheduling theory shows partitioned EDF (pEDF) is better than global EDF (gEDF) in providing schedulability guarantees, in our experiments their performance is reversed in terms of the fraction of workloads that meet their deadlines on virtualized multi-core platforms; (3) at the guest OS level, pEDF requests a smaller total VCPU bandwidth than gEDF based on compositional scheduling analysis, and therefore using pEDF at the guest OS level leads to more schedulable workloads in our experiments; (4) a combination of pEDF in the guest OS and gEDF in the VMM -- configured with deferrable server -- leads to the highest fraction of schedulable task sets compared to other real-time VM scheduling policies; and (5) on a platform with a shared last-level cache, the benefits of global scheduling outweigh the cache penalty incurred by VM migration.

In this paper we present a methodology to control ground robots under malicious attack on sensors. Within the term attack we intend any malicious disturbance injection on sensors, actuators, and controller that would compromise the safety of a robot. In order to guarantee resilience against attacks, we use a control-level technique implemented within a recursive algorithm that takes advantage of redundancy in the information received by the controller. We use the case study of a vehicle cruise-control, however, the strategy we present in this work is general for several applications. Our methodology relays on redundancy in the sensor measurements: specifically we consider N velocity measurements and use a recursive filtering technique that estimates the state of the system while being resilient against sensor attacks by acting on the variance of the measurements noise. Finally, we move our focus on hardware validation demonstrating our algorithm through extensive outdoor experiments conducted on two unmanned ground robots.

Middleware designed for use in Distributed Real-Time and Embedded (DRE) systems enable cost and development time reductions by providing simple communications abstractions and hiding operating system-level networking API details from developers. While current middleware technologies can hide many low-level details, designers must provide a static configuration for the system's underlying network in order to achieve required performance characteristics. This has not been a problem for many types of DRE systems where the configuration of the system is relatively fixed from the factory (e.g., aircraft or naval vessels). However for truly open systems (i.e., systems where end users can add or substract components at runtime)the standard static network configuration approach cannot guarantee that required performance will be met because network resource demands are not fully known a priori. Open systems with stringent performance requirements need middleware that can dynamically manage the underlying network configuration automatically in response to changing demands. Fortunately, recent trends in networking have resulted in a wide variety of networking equipment that expose a standardized low-level interface to their configuration via the OpenFlow protocol. In this paper we discuss how OpenFlow can be leveraged by DRE middleware to automatically provide performance guarantees. In order to make the discussion concrete, we describe the architecture of our prototype middleware MIDAS as well as the details of one example network resource management strategy. We demonstrate the feasibility of our approach via performance assesment of a simple DRE application using our MIDAS and commerically available OpenFlow hardware.

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.

Software-based control of life-critical embedded systems has become increasingly complex, and to a large extent has come to determine the safety of the human being. For example, implantable cardiac pacemakers have over 80,000 lines of code which are responsible for maintaining the heart within safe operating limits. As firmware-related recalls accounted for over 41% of the 600,000 devices recalled in the last decade, there is a need for rigorous model-driven design tools to generate verified code from verified software models. To this effect, we have developed the UPP2SF model-translation tool, which facilitates automatic conversion of verified models (in UPPAAL) to models that may be simulated and tested (in Simulink/Stateflow). We describe the translation rules that ensure correct model conversion, applicable to a large class of models. We demonstrate how UPP2SF is used in the model-driven design of a pacemaker whose model is (a) designed and verified in UPPAAL (using timed automata), (b) automatically translated to Stateflow for simulation-based testing, and then (c) automatically generated into modular code for hardware-level integration testing of timing-related errors. In addition, we show how UPP2SF may be used for worst-case execution time estimation early in the design stage. Using UPP2SF, we demonstrate the value of integrated end-to-end modeling, verification, code-generation and testing process for complex software-controlled embedded systems.

In modern hospitals, patients are treated using a wide array of medical devices that are increasingly interacting with each other over the network, thus offering a perfect example of a cyber-physical system. We study the safety of a medical device system for the physiologic closed-loop control of drug infusion. The main contribution of the paper is the verification approach for the safety properties of closed-loop medical device systems. We demonstrate, using a case study, that the approach can be applied to a system of clinical importance. Our method combines simulation-based analysis of a detailed model of the system that contains continuous patient dynamics with model checking of a more abstract timed automata model. We show that the relationship between the two models preserves the crucial aspect of the timing behavior that ensures the conservativeness of the safety analysis. We also describe system design that can provide open-loop safety under network failure.

Code generation for embedded systems is challenging, since the generated code (e.g., C code) is expected to run on a heterogeneous set of target platforms with different characteristics, such as hardware/software architectures and programming interfaces. We propose a code generation framework that provides the flexibility to generate different source code that is executable on each target platform. In our framework, the platform-dependent characteristics of a target platform are explicitly specified by an Architectural Analysis Description Language (AADL) model and a code snippet repository. The AADL model captures hardware/software architectural aspects of the platform, such as periodic/aperiodic threads and their interactions with sensors and actuators. The code snippet repository contains platform-dependent code snippets that are categorized according to the functions required to implement the components of the AADL model. These two elements of the platform capability are then used by the code generation algorithm to generate platform-dependent code for the given platform. We demonstrate the applicability of our framework using a case study of code generation for two infusion pump systems.

Wireless insulin pumps have been widely deployed in hospitals and home healthcare systems. Most of these insulin pump systems have limited security mechanisms embedded to protect them from malicious attacks. In this paper, two attacks against insulin pump systems via wireless links are investigated: a single acute overdose with a significant amount of medication, and chronic overdose with an insignificant amount of extra medication over a long time period, e.g., several months. These attacks can be launched unobtrusively and may jeopardize patients' lives. It is very important and urgent to protect patients from these attacks. To address this issue, we propose a novel patient infusion pattern based access control scheme (PIPAC) for wireless insulin pumps. This scheme employs a supervised learning approach to learn normal patient infusions pattern with the dosage amount, rate, and time of infusion, which are automatically recorded in insulin pump logs. The generated regression models are used to dynamically configure a safety infusion range for abnormal infusion identification. The proposed algorithm is evaluated with real insulin pump logs used by several patients for up to 6 months. The evaluation results demonstrate that our scheme can reliably detect the single overdose attack with a success rate up to 98% and defend against the chronic overdose attack with a very high success rate.

Observing the success of the open source software movement, the Adaptive Vehicle Make (AVM) is a program run by the Defense Advanced Project Agency (DARPA) with the goal of applying crowd-sourced and component-based engineering to the design of military vehicles. In this paper, we present a credentialing system called TrustForge, which enables effective and flexible access control for the AVMcrowd-sourced repository. Credentialing systems are essential in crowdsourcing to ensure quality, since it is potentially open to contributions made by anyone. The open source software community has developed elaborate manual approaches of managing its contributor community, which are often very labor-intensive and inefficient. Our aim with TrustForge is to improve the automation of the credentialing and access control process in the context of component-based systems, where users contribute components at various levels of abstraction. TrustForge takes a hybrid approach that combines trust policy and reputation to address this problem. In TrustForge, a policy language is used to specify the access control rules for users in the system to contribute components. In addition, reputation values computed for users based on the quality of their past component contributions are used to tune the static policies to enable flexibility and adaptiveness. The contributions of this work are as follows: (1) the design of TrustForge - an effective and flexible access control mechanism that combines policy and reputation approaches; (2) the identification of heuristics for component quality measurement and a novel reputation computation algorithm for evaluating user trustworthiness; (3) a data model based on provenance graphs that allows efficient repository information storage and retrieve. We have implemented TrustForge system and integrate it with the VehicleForge repository system to support the operation of the AVM challenge program. The evaluation results based on realworld deployment and systematic simulation demonstrate that TrustForge can effectively discern the trustworthiness of users within the crowd-sourced system.

In this paper, we introduce a technique for improving the schedulability of real-time embedded systems with fixed-priority scheduling. Our technique uses shapers to reduce the resource interference between higher-priority and lower-priority tasks, and thus enables more lower-priority tasks to be scheduled. We present a closed-form solution for the optimal greedy shaper for periodic tasks with jitter, as well as a schedulability condition for tasks in the presence of shapers. We also discuss two applications of greedy shapers: In compositional scheduling frameworks, shapers can help optimize the resource interfaces of real-time components, and in mixed-criticality systems, they can reduce deadline misses of low-criticality tasks while preserving schedulability of high-criticality tasks, even with lower priorities. We demonstrate the utility of our technique through an evaluation based on randomly generated workloads.

Over the past decade, interface-based compositional schedulability analysis has emerged as an effective method for guaranteeing real-time properties in complex systems. Several interfaces and interface computation methods have been developed, and they offer a range of tradeoffs between the complexity and the accuracy of the analysis. However, none of the existing methods consider platform overheads in the component interfaces. As a result, although the analysis results are sound in theory, the systems may violate their timing constraints when running on realistic platforms. This is due to various overheads, such as task release delays, interrupts, cache effects, and context switches. Simple solutions, such as increasing the interface budget or the tasks' worst-case execution times by a fixed amount, are either unsafe (because of the overhead accumulation problem) or they waste a lot of resources. In this paper, we present an overhead-aware compositional analysis technique that can account for platform overheads in the representation and computation of component interfaces. Our technique extends previous overhead accounting methods, but it additionally addresses the new challenges that are specific to the compositional scheduling setting. To demonstrate that our technique is practical, we report results from an extensive evaluation on a realistic platform.

Multicore processors are becoming ubiquitous, and it is becoming increasingly common to run multiple real-time systems on a shared multicore platform. While this trend helps to reduce cost and to increase performance, it also makes it more challenging to achieve timing guarantees and functional isolation. One approach to achieving functional isolation is to use virtualization. However, virtualization also introduces many challenges to the multicore timing analysis, for instance, the overhead due to cache misses becomes harder to predict, since it depends not only on the direct interference between tasks but also on the indirect interference between virtual processors and the tasks executing on them. In this paper, we present a cache-aware compositional analysis technique that can be used to ensure timing guarantees of components scheduled on a multicore virtualization platform. Our technique improves on previous multicore compositional analyses by accounting for the cache-related overhead in the components' interfaces, and it addresses the new virtualization-specific challenges in the overhead analysis. To demonstrate the utility of our technique, we report results from an extensive evaluation based on randomly generated workloads.

Schedulability analysis of hierarchical real-time embedded systems involves defining interfaces that represent the underlying system faithfully and then compositionally analyzing those interfaces. Whereas commonly used abstractions, such as periodic and sporadic tasks and their interfaces, are simple and well studied, results for more complex and expressive abstractions and interfaces based on task graphs and automata are limited. One contributory factor may be the hardness of compositional schedulability analysis with task graphs and automata. Recently, conditional task models, such as the recurring branching task model, have been introduced with the goal of reaching a middle ground in the trade-off between expressivity and ease of analysis. Consequently, techniques for compositional analysis with conditional models have also been proposed, and each offer different advantages. In this work, we revisit those techniques, compare their advantages using an automotive case study, and identify limitations that would need to be addressed before adopting these techniques for use with real-world problems.

In model-based development, executable software (e.g., C or Java code) can be generated from a high-level model using a code generator. However, the execution of the generated software on a target platform remains a challenge due to a mismatch in communication semantics assumed by the model and the platform-dependent software (e.g., sampling/actuation routines). This paper proposes an input/output (I/O) interface module that bridges this semantic gap by means of buffers and interface policies, which explicitly capture the information required to adapt the model's communication semantics to that of the platform. We present a framework that can be used to systematically synthesize - directly from the model - the I/O interfaces and accompanying APIs that the generated software and the platform-dependent software need to communicate with one another. Our interface policies can also encode relaxations of a model semantics that may not be implementable, thus making derivations of the implemented systems from the model traceable. We illustrate the applicability and the benefits of our framework with a case study of an infusion pump.

We present a co-designed scheduling framework and platform architecture that together support compositional scheduling of real-time systems. The architecture is built on the Xen virtualization platform, and relies on compositional scheduling theory that uses periodic resource models as component interfaces. We implement resource models as periodic servers and consider enhancements to periodic server design that significantly improve response times of tasks and resource utilization in the system while preserving theoretical schedulability results. We present an extensive evaluation of our implementation using workloads from an avionics case study as well as synthetic ones.

Model-Driven Design (MDD) of cyber-physical systems advocates for design procedures that start with formal modeling of the real-time system, followed by the model's verification at an early stage. The verified model must then be translated to a more detailed model for simulation-based testing and finally translated into executable code in a physical implementation. As later stages build on the same core model, it is essential that models used earlier in the pipeline are valid approximations of the more detailed models developed downstream. The focus of this effort is on the design and development of a model translation tool, UPP2SF, and how it integrates system modeling, verification, model-based WCET analysis, simulation, code generation and testing into an MDD based framework. UPP2SF facilitates automatic conversion of verified timed automata-based models (in UPPAAL) to models that may be simulated and tested (in Simulink/State flow). We describe the design rules to ensure the conversion is correct, efficient and applicable to a large class of models. We show how the tool enables MDD of an implantable cardiac pacemaker. We demonstrate that UPP2SF preserves behaviors of the pacemaker model from UPPAAL to State flow. The resultant State flow chart is automatically converted into C and tested on a hardware platform for a set of requirements.

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.

Medical cyber-physical systems (MCPS) are life-critical, context-aware, networked systems of medical devices. These systems are increasingly used in hospitals to provide high-quality continuous care for patients. The need to design complex MCPS that are both safe and effective has presented numerous challenges, including achieving high assurance in system software, intoperability, context-aware intelligence, autonomy, security and privacy, and device certifiability. In this paper, we discuss these challenges in developing MCPS, some of our work in addressing them, and several open research issues.

This Special Issue presents papers that cover key features of Cyber - Physical Systems (CPS), including new research and technology advances, open problems, and technical challenges with the papers organized into three categories: theoretical foundations, small-scale applications, and large-scale applications.

This tutorial is concerned with various aspects of component-based design and compositional analysis of real-time embedded systems. It will first give an overview of component-based frameworks and their underlying principles. It will then go in-depth into abstraction methods for real-time components and techniques for computing their optimal interfaces, for both systems implemented on uniprocessor and multiprocessor platforms, as well as extensions to multi-mode systems. Besides theoretical aspects, the tutorial will also present an implementation of the compositional analysis framework on Xen virtualization and a demonstration of the CARTS toolset with several examples seeing the techniques in action. It will also include two case studies highlighting the utility of the framework, including the ARINC-653 avionics software and a smart-phone application. We will conclude the tutorial with a number of open challenges and research opportunities in this domain.

This paper presents our effort of using model-driven engineering to establish a safety-assured implementation of Patient-Controlled Analgesic (PCA) infusion pump software based on the generic PCA reference model provided by the U.S. Food and Drug Administration (FDA). The reference model was first translated into a network of timed automata using the UPPAAL tool. Its safety properties were then assured according to the set of generic safety requirements also provided by the FDA. Once the safety of the reference model was established, we applied the TIMES tool to automatically generate platform-independent code as its preliminary implementation. The code was then equipped with auxiliary facilities to interface with pump hardware and deployed onto a real PCA pump. Experiments show that the code worked correctly and effectively with the real pump. To assure that the code does not introduce any violation of the safety requirements, we also developed a testbed to check the consistency between the reference model and the code through conformance testing. Challenges encountered and lessons learned during our work are also discussed in this paper.

We are considering the challenges that regulators face in approving modern medical devices, which are software intensive and increasingly network enabled. We then consider assurance cases, which offer the means of organizing the evidence into a coherent argument demonstrating the level of assurance provided by a system, and discuss research directions that promise to make construction and evaluation of assurance cases easier and more precise. Finally, we discuss some recent trends that will further complicate the regulatory approval of medical cyber-physical systems.

We examine the problem of reliable networked control when the communication channel between the controller and the actuator periodically drops packets and is faulty (i.e., corrupts/alters data). We first examine the use of a standard triple modular redundancy scheme (where the control input is sent via three independent channels) with majority voting to achieve mean square stability. While such a scheme is able to tolerate a single faulty channel when there are no packet drops, we show that the presence of lossy channels prevents a simple majority-voting approach from stabilizing the system. Moreover, the number of redundant channels that are required in order to maintain stability under majority voting increases with the probability of packet drops. We then propose the use of a reputation management scheme to overcome this problem, where each channel is assigned a reputation score that predicts its potential accuracy based on its past behavior. The reputation system builds on the majority voting scheme and improves the overall probability of applying correct (stabilizing) inputs to the system. Finally, we provide analytical conditions on the probabilities of packet drops and corrupted control inputs under which mean square stability can be maintained, generalizing existing results on stabilization under packet drops.

The hierarchical real-time scheduling framework is a widely accepted model to facilitate the design and analysis of the increasingly complex real-time systems. Interface abstraction and composition are the key issues in the hierarchical scheduling framework analysis. Schedulability is essential to guarantee that the timing requirements of all components are satisfied. In order for the design to be resource efficient, the composition must be bandwidth optimal. Associativity is desirable for open systems in which components may be added or deleted at run time. Previous techniques on compositional scheduling are either not resource efficient in some aspects, or cannot achieve optimality and associativity at the same time. In this paper, several important properties regarding the periodic resource model are identified. Based on those properties, we propose a novel interface abstraction and composition framework which achieves schedulability, optimality, and associativity. Our approach eliminates abstraction overhead in the composition.

We present a unified framework for the specification and analysis of mode-change protocols used in multi-mode real-time systems. We propose a highly expressive formalism, called MCP, to model the system behavior during mode transitions, and show how various existing mode change protocols can be described as MCPs. The explicit representation of the MCP model provides a means to analyze the system state during a mode transition as well as during an intra-mode execution. We introduce the concept of feasibility with respect to the MCP model, and give a decidable method for checking the feasibility of a MCP for a given multi-mode system. The formalization of mode change behaviors using the MCP model allows a range of mode change protocols to be modeled, evaluated, and optimized to the specific operations and performance requirements of the system. Besides feasibility analysis, it is also possible to analyze other system behaviors (e.g., delay between modes, buffer backlog) using automata verification techniques. Our framework can also be used to describe mode change semantics of multi-mode systems whose modes/transitions have different criticality levels, or of systems composed of multiple multi-mode components that require different mode change protocols.

We study the impact of video frame drops in buffer constrained multiprocessor system-on-chip (MPSoC) platforms. Since on-chip buffer memory occupies a significant amount of silicon area, accurate buffer sizing has attracted a lot of research interest lately. However, all previous work studied this problem with the underlying assumption that no video frame drops can be tolerated. In reality, multimedia applications can often tolerate some frame drops without significantly deteriorating their output quality. Although system simulations can be used to perform video quality driven buffer sizing, they are time consuming. In this paper, we first demonstrate a dual-buffer management scheme to drop only the less significant frames. Based on this scheme, we then propose a formal framework to evaluate the buffer size vs. video quality trade-offs, which in turn will help a system designer to perform quality driven buffer sizing. In particular, we mathematically characterize the maximum numbers of frame drops for various buffer sizes and evaluate how they affect the worst-case PSNR value of the decoded video. We evaluate our proposed framework with anMPEG-2 decoder and compare the obtained results with that of a cycle-accurate simulator. Our evaluations show that for an acceptable quality of 30 dB, it is possible to reduce the buffer size by up to 28.6% which amounts to 25.88 megabits.

Among the key characteristics of cyber-physical systems are the ability to adapt to changes during operation, the multidimensional complexity of multi-functionality and the underlying heterogeneous distributed architecture, as well as resource use efficiency. In this paper, we propose a compositional multi-modal approach to modeling, analyzing, and designing such systems. We introduce a general framework for modeling and compositional analysis of multi-mode systems on a distributed architecture that facilitates adaptivity, efficient use of resources, and incremental integration. We present some preliminary results, and we describe some of the remaining challenges and future directions.

IP blacklists are a spam filtering tool employed by a large number of email providers. Centrally maintained and well regarded, blacklists can filter 80+% of spam without having to perform computationally expensive content-based filtering. However, spammers can vary which hosts send spam (often in intelligent ways), and as a result, some percentage of spamming IPs are not actively listed on any blacklist. Blacklists also provide a previously untapped resource of rich historical information. Leveraging this history in combination with spatial reasoning, this paper presents a novel reputation model (PreSTA), designed to aid in spam classification. In simulation on arriving email at a large university mail system, PreSTA is capable of classifying up to 50% of spam not identified by blacklists alone, and 93% of spam on average (when used in combination with blacklists). Further, the system is consistent in maintaining this blockage-rate even during periods of decreased blacklist performance. PreSTA is scalable and can classify over 500,000 emails an hour. Such a system can be implemented as a complementary blacklist service or used as a first-level filter or prioritization mechanism on an email server.

We discuss current trends in the development and use of high-confidence medical cyber-physical systems (MCPS). These trends, including increased reliance on software to deliver new functionality, wider use of network connectivity in MCPS, and demand for continuous patient monitoring, bring new challenges into the process of MCPS development and at the same time create new opportunities for research and development.

Cyber-physical systems (CPS) are physical and engineered systems whose operations are monitored, coordinated, controlled and integrated by a computing and communication core. Just as the internet transformed how humans interact with one another, cyber-physical systems will transform how we interact with the physical world around us. Many grand challenges await in the economically vital domains of transportation, health-care, manufacturing, agriculture, energy, defense, aerospace and buildings. The design, construction and verification of cyber-physical systems pose a multitude of technical challenges that must be addressed by a cross-disciplinary community of researchers and educators.

The paper presents a model for multi-mode real-time applications and develops new techniques for the compositional analysis of systems that contain multiple such applications. An algorithm for constructing an interface for a single multi-mode application is presented. Then, a method for computing an interface of a composite application is presented, which uses only the interfaces of constituent applications. A case study of an adaptive streaming system demonstrates that multi-mode analysis offers more precise results compared to a unimodal worst-case analysis.

Automotive architectures consist of multiple electronic control units (ECUs) which run distributed control applications. Such ECUs are connected to sensors and actuators and communicate via shared buses. Resource arbitration at the ECUs and also in the communication medium, coupled with variabilities in execution requirements of tasks results in jitter in the signal/data streams existing in the system. As a result, buffers are required at the ECUs and bus controllers. However, these buffers often implement different semantics -- FIFO queuing, which is the most straightforward buffering scheme, and data refreshing, where stale data is overwritten by freshly sampled data. Traditional timing and schedulability analysis that are used to compute, e.g., end-to-end delays, in such automotive architectures can only model FIFO buffering. As a result, they return pessimistic delay and resource estimates because in reality paper we propose an analytical framework for accurately modeling such data refresh semantics. Our model exploits a novel feedback control mechanism and is purely functional in nature. As a result, it is scalable and does not involve any explicit state modeling. Using this model we can estimate various timing and performance metrics for automotive ECU networks consisting of buffers implementing different data handling semantics. We illustrate the utility of this model through three case studies from the automotive electronics domain.

Modular robots are a powerful concept for robotics. A modular robot consists of many individual modules so it can adjust its configuration to the problem. However, the fact that a modular robot consists of many individual modules makes it a highly distributed, highly concurrent real-time system, which are notoriously hard to program. In this work, we present our programming framework for writing control applications for modular robots. The framework includes a toolset that allows a model-based programming approach for control application of modular robots with code generation and verification. The framework is characterized by the following three features. First, it provides a complex programming model that is based on standard finite state machines extended in syntax and semantics to support communication, variables, and actions. Second, the framework provides compositionality at the hardware and at the software level and allows building the modular robot and its control application from small building blocks. And third, the framework supports formal verification of the control application to aid the gait and task developer in identifying problems and bugs before the deployment and testing on the physical robot.

Guaranteeing timing properties is an important issue as we develop safety-critical real-time systems such as cardiac pacemakers. We present a safety assured development approach of real-time software using a pacemaker as our case study. Following the model-driven development techniques, measurement-based timing analysis is used to guarantee timing properties in implementation as well as in the formal model. Formal specification with timed automata is checked with respect to timing properties by model checking technique and is transformed into implementation systematically. When timing properties may be violated in the implementation due to timing delay, it is suggested to measure the time deviation and reflect it to the code explicitly by modifying guards. The model is altered according to the modifications in the code. These changes of the code and the model are considered safe if all the properties are still satisfied by the modified model in re-performed model checking. We demonstrate how the suggested approach can be applied to single-threaded and multi-threaded versions of implementation. This approach can provide developers with a useful time-guaranteeing technique applicable to several code generation schemes without imposing many restrictions.

Hybrid systems have emerged as an appropriate formalism to model embedded systems as they capture the theme of continuous dynamics with discrete control. Under this paradigm, distributed embedded systems can be modeled as a network of communicating hybrid automata. Several techniques for code generation from these models have also been proposed and commercially implemented. Providing formal guarantees of the generated code with respect to the model, however, has turned out to be a hard problem. While the model is set in continuous time with concurrent execution and instantaneous switching, the code running on an inherently discrete platform, can be affected by the sampling interval, round-off errors, and communication delays between the sensor, controller, and actuators. Consequently, semantic differences between the model and its code can arise with potentially different system behavior. This paper proposes a criterion for faithful implementation of the hybrid-systems model with a focus on its switching semantics. We discuss different techniques to ensure a faithful implementation of the model, and test the feasibility of our concepts by implementing a model heater system. In this heater case study, we successfully eliminate all fault transitions and, thereby, generate code with correct behavior complying with the specification.

Embedded software should be correctly developed so that it is be compliant with not only functional requirements but also real-time and resource constraints. However, those constraints are often dependent on execution environments that are sometimes revealed in late development phases. In this paper, we propose Timed and Resource-oriented Statecharts (TRoS) to analyze the time and resource-constrained behavior of system in earlier development phases of embedded software development. TRoS extends Statecharts using timed action labeled with resources to represent actions that consume resources. This enables us to describe the competition among processes to use shared resources, and to analyze schedulability of embedded systems. We present a case study of a distance control module that controls train movement to keep the distance between trains for railway control systems.

Complex real-time embedded systems should be compositional and deterministic in the resource, time, and value domains. Determinism eases the engineering of correct systems and compositionality simplifies the assembly of complex systems out of smaller modules. This paper describes the PEACOD framework that is developed to support deterministic behavior for resource consumption, value passing, and timing. The paper introduces the notions of determinism in the context of the resource, value, and temporal domains, and present the resource-scope language construct that can be used to program such deterministic behaviors. Furthermore, the paper also provides semantics for the resource scope construct and uses these semantics to show that the program behavior is preserved under composition. The paper briefly describes the current implementation of PEACOD.

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.

Many embedded systems operate in multiple modes, where mode switches can be both time- as well as event-triggered. While timing and schedulability analysis of the system when it is operating in a single mode has been well studied, it is always difficult to piece together the results from different modes in order to deduce the timing properties of a multi-mode system. As a result, often certain restrictive assumptions are made, e.g., restricting the time instants at which mode changes might occur. The problem becomes more complex when both time- and event-triggered mode changes are allowed. Further, for complex systems that cannot be described by traditional periodic/sporadic event models (i.e., where event streams are more complex/bursty) modeling multiple modes is largely an open problem. In this paper we propose a model and associated analysis techniques to describe embedded systems that process multiple bursty/complex event/data streams and in which mode changes are both time- and event-triggered. Compared to previous studies, our model is very general and can capture a wide variety of real-life systems. Our analysis techniques can be used to determine different performance metrics, such as the maximum fill-levels of different buffers and the delays suffered by the streams being processed by the system. The main novelty in our analysis lies in how we piece together results from the different modes in order to obtain performance metrics for the full system. Towards this, we propose both - exact, but computationally expensive, as well as safe approximation techniques. The utility of our model and analysis has been illustrated using a detailed smart-phone case study.

Distributed real-time applications implement distributed applications with timeliness requirements. Such systems require a deterministic communication medium with bounded communication delays. Ethernet is a widely used commodity network with many appliances and network components and represents a natural fit for real-time application; unfortunately, standard Ethernet provides no bounded communication delays. Conditional state-based communication schedules provide expressive means for specifying and executing with choice points, while staying verifiable. Such schedules implement an arbitration scheme and provide the developer with means to fit the arbitration scheme to the application demands instead of requiring the developer to tweak the application to fit a predefined scheme. An evaluation of this approach as software prototypes showed that jitter and execution overhead may diminish the gains. This work successfully addresses this problem with a synthesized soft processor. We present results around the development of the soft processor, the design choices, and the measurements on throughput and robustness.

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.

Distributed real-time applications implement distributed applications with timeliness requirements. Such systems require a deterministic communication medium with bounded communication delays. Ethernet is a widely used commodity network with a large number of appliances and network components and represents a natural fit for real-time application; unfortunately, standard Ethernet provides no bounded communication delays. Network Code Processor is a soft processor implementation for real-time communication on Ethernet. The system provides a smart network-card functionality and can be seen as a co-processor for time-triggered communication. Its most distinguishing feature, the programmability of the processor via the Network Code language, allows developers to write adaptive but verifiable communication schedules tailored to the application needs. In this work we present results around the development of the soft processor, discuss the specific challenges of how to build a reliable and fast communication system, the tradeoffs involved when moving from a generic software prototype to a programmable hardware implementation.

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.

For real-time systems, most of the analysis involves efficient or exact schedulability checking. While this is important, analysis is often based on the assumption that the task parameters such as execution requirements and inter-arrival times between jobs are known exactly. In most cases, however, only a worst-case estimate of these quantities is available at the time of analysis. It is therefore imperative that schedulability analysis hold for better parameter values (Sustainable Analysis). On the other hand, if the task or system parameters turn out to be worse off, then the analysis should tolerate some deterioration (Robust Analysis). Robust analysis is especially important, because the implication of task schedulability is often weakened in the presence of optimizations that are performed on its code, or dynamic system parameters.\nIn this work, we define and address sustainability and robustness questions for analysis of embedded real-time software that is modeled by conditional real-time tasks. Specifically, we show that, while the analysis is sustainable for changes in the task such as lower job execution times and increased relative deadlines, it is not the case for code changes such as job splitting and reordering. We discuss the impact of these results in the context of common compiler optimizations, and then develop robust schedulability techniques for operations where the original analysis is not sustainable.

Real-time embedded systems are typically constrained in terms of three system performance criteria: space, time, and energy. The performance requirements are directly translated into constraints imposed on the system's resources, such as code size, execution time, and energy consumption. These resource constraints often interact or even conflict with each other in a complex manner, making it difficult for a system developer to apply a well-defined design methodology in developing a real-time embedded system. Motivated by this observation, we propose a design framework that can flexibly balance the tradeoff involving the system's code size, execution time, and energy consumption. Given a system specification and an optimization criteria, the proposed technique generates a set of design parameters in such a way that a system cost function is minimized while the given resource constraints are satisfied. Specifically, the technique derives code generation decision for each task so that a specific version of code is selected among a number of different ones that have distinct characteristics in terms of code size and execution time. In addition, the design framework determines the voltage/frequency setting for a variable voltage processor whose supply voltage can be adjusted at runtime in order to minimize the energy consumption while execution performance is degraded accordingly. The proposed technique formulates this design process as a constrained optimization problem. We show that this optimization problem is NP-hard and then provide a heuristic solution to it. We show that these seemingly conflicting design goals can be pursued by using a simple optimization algorithm that works with a single optimization criteria. Moreover, the optimization is driven by an abstract system specification given by the system developer, so that the system development process can be automated. The results from our simulation show that the proposed algorithm finds a solution that is close to the optimal one with the average error smaller than 1.0%.

It is desirable to develop large complex systems using components based on systematic abstraction and composition. Our goal is to develop a compositional real-time scheduling framework to support abstraction and composition techniques for real-time aspects of components. In this paper, we present a formal description of compositional real-time scheduling problems, which are the component abstraction and composition problems. We identify issues that need be addressed by solutions and provide our framework for the solutions, which is based on the periodic interface . Specifically, we introduce the periodic resource model to characterize resource allocations provided to a single component. We present exact schedulability conditions for the standard Liu and Layland periodic task model and the proposed periodic resource model under EDF and RM scheduling, and we show that the component abstraction and composition problems can be addressed with periodic interfaces through the exact schedulability conditions. We also provide the utilization bounds of a periodic task set over the periodic resource model and the abstraction bounds of periodic interfaces for a periodic task set under EDF and RM scheduling. We finally present the analytical bounds of overheads that our solution incurs in terms of resource utilization increase and evaluate the overheads through simulations.

A critical resource in a distributed real-time system is its shared communication medium. Unrestrained concurrent access to the network can lead to collisions that reduce the system's reliability. Therefore in this area, one goal is to develop effective models for coordinating and controlling access to the shared medium and its channels.\nNetwork Code is a verifiable, executable model for coordinating and controlling access to a shared communication medium in a distributed real-time system. In this paper, we investigate the problem of building an application by composing multiple Network Code programs. To reason about the composition, we model Network Code programs as Tree Schedules (TS) and then consider the composition of schedules that describe how the network is accessed by different applications. Specifically, we first define the notions of compatibility and composability of tree schedules, and then provide algorithms for their composition and reason about overhead of composition. We illustrate the techniques by considering the composition of two control applications.

The design of safety-critical systems has typically adopted static techniques to simplify error detection and fault tolerance. However, economic pressure to reduce costs is exposing the limitations of those techniques in terms of efficiency in the use of system resources. In some industrial domains, such as the automotive, this pressure is too high, and other approaches to safety must be found, e.g., capable of providing some kind of fault tolerance but with graceful degradation to lower costs, or also capable of adapting to instantaneous requirements to better use the computational/communication resources.

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.

Distributed hard real-time systems require predictable communication at the network level and verifiable communication behavior at the application level. At the network level, communication between nodes must be guaranteed to happen within bounded time and one common approach is to restrict the network access by enforcing a time-division multiple access (TDMA) schedule. At the application level, the application's communication behavior should be verified to ensure that the application uses the predictable communication in the intended way. Network code is a domain-specific programming language to write a predictable verifiable distributed communication for distributed real-time applications. In this paper, we present the syntax and semantics of network code, how we can implement different scheduling policies, and how we can use tools such as model checking to formally verify the properties of network code programs. We also present an implementation of a runtime system for executing network code on top of RTLinux and measure the overhead incurred from the runtime system.

There is a growing interest in establishing rules to regulate the privacy of citizens in the treatment of sensitive personal data such as medical and financial records. Such rules must be respected by software used in these sectors. The regulatory statements are somewhat informal and must be interpreted carefully in the software interface to private data. This paper describes techniques to formalize regulatory privacy rules and how to exploit this formalization to analyze the rules automatically. Our formalism, which we call privacy APIs, is an extension of access control matrix operations to include (1) operations for notification and logging and (2) constructs that ease the mapping between legal and formal language. We validate the expressive power of privacy APIs by encoding the 2000 and 2003 HIPAA consent rules in our system. This formalization is then encoded into Promela and we validate the usefulness of the formalism by using the SPIN model checker to verify properties that distinguish the two versions of HIPAA

Distributed real-time systems require a predictable and verifiable mechanism to control the communication medium. Current real-time communication protocols are typically in-dependent of the application and have intrinsic limitations that impede customizing or optimizing them for the application. Therefore, either the developer must adapt her application and work around these subtleties or she must limit the capabilities of the application being developed.Network Code, in contrast, is a more expressive and exible model that specifies real-time communication schedules as programs. By providing a programmable media access layer on the basis of TDMA, Network Code permits creating application-specific protocols that suit the particular needs of the application. However, this gain in exibility also incurs additional costs such as increased communication and run-time overhead. Therefore, engineering an application with network code necessitates that these costs are analyzed, quantified, and weighted against the benefit.In this work, we propose a framework to analyze network-code programs for commonly used metrics such as overhead, schedulability, and average waiting time. We introduce Timed Tree Communication Schedules, based on timed automata to model such programs and define metrics in the context of deterministic and probabilistic communication schedules. To demonstrate the utility of our framework, we study an inverted pendulum system and show that we can decrease the cumulative numeric error in the model's implementation through analyzing and improving the schedule based on the presented metrics.

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.

The paper discusses the use of formal methods for the analysis of architectural models expressed in the modeling language AADL. AADL describes the system as a collection of interacting components. The AADL standard prescribes semantics for the thread components and rules of interaction between threads and other components in the system. We present a semantics-preserving translation of AADL models into the real-time process algebra ACSR, allowing us to perform schedulability analysis of AADL models

The Avionics Full Duplex Switched Ethernet (AFDX) has been developed to provide reliable data exchange with strong data transmission time guarantees in internal communication of the aircraft. The AFDX design is based on the principle of a switched network with physically redundant links to support availability and be tolerant to transmission and link failures in the network. In this work, we develop a formal model of the AFDX frame management to ascertain the reliability properties of the design. To capture the precise temporal semantics, we model the system as a network of timed automata and use Uppaal to model-check for the desired properties expressed in CTL. Our analysis indicates that the design of the AFDX frame management is vulnerable to faults such as network babbling which can trigger unwarranted system resets. We show that these problems can be alleviated by modifying the original design to include a priority queue at the receiver for storing the frames. We also suggest communicating redundant copies of the reset message to achieve tolerance to network babbling.

Hybrid systems are an appropriate formalism to model embedded systems as they capture the theme of continuous dynamics with discrete control. A simple extension, a network of communicating hybrid automata, allows for modeling distributed embedded systems. Although it is possible to generate code from such models, it is difficult to provide formal guarantees in the code with respect to the model. One of the reasons for this is that, the model is set in continuous time and concurrent execution with instantaneous communication, whereas the generated code is set in discrete time with delayed communication. This can introduce semantic differences between the model and the code such as missed transitions, faulty transitions, and altered continuous behavior. The goal of faithful code generation is to minimize these differences.In this paper, we propose a relaxed criteria of faithfulness, coined relative faithful implementation. Based on this criteria, we propose dynamically adjusting the guard at runtime using estimates of errors for preventing faulty transitions. We also identify a sufficient condition to ensure no missed transitions in the code.

Code generation from hybrid system models is a promising approach to producing reliable embedded systems. This approach presents new challenges as the precise semantics of the model are hard to capture in the code. A framework for generating code was introduced for single threaded/processor environments. We extend it by considering code generation for distributed environments. We also define criteria for faithful implementation of the model. To this end, we define faulty and missed transitions. For preventing faulty transitions, we build on the idea of instrumentation we have developed for sound simulation of hybrid systems. Finally, we present sufficient conditions to avoid missed transitions and provide examples.

Correctness of a real-time system depends on its computation as well as its timeliness and its reliability. In recent years, researches have focused on verifying correctness of a real-time system during runtime by monitoring its execution and checking it against its formal specifications. Such verification method is called runtime verification. Most existing runtime verification tools verify computation correctness using qualitative property specifications but do not verify timeliness or reliability correctness. In this paper, we investigate the verification on timeliness and reliability correctness by offering quantitative and probabilistic property specifications and implementing efficient verifiers.

No abstract available.

Our goal is to develop a compositional real-time scheduling framework so that global (system-level) timing properties can be established by composing independently (specified and) analyzed local (component-level) timing properties. The two essential problems in developing such a framework are: (1) to abstract the collective real-time requirements of a component as a single real-time requirement and (2) to compose the component demand abstraction results into the system-level real-time requirement. In our earlier work, we addressed the problems using the Liu and Layland periodic model. In this paper, we address the problems using another well-known model, a bounded-delay resource partition model, as a solution model to the problems. To extend our framework to this model, we develop an exact feasibility condition for a set of bounded-delay tasks over a bounded-delay resource partition. In addition, we present simulation results to evaluate the overheads that the component demand abstraction results incur in terms of utilization increase. We also present utilization bound results on a bounded-delay resource model.

This paper presents a model checking-based approach to dataflow testing. We characterize dataflow oriented coverage criteria in temporal logic such that the problem of test generation is reduced to the problem of finding witnesses for a set of temporal logic formulas. The capability of model checkers to construct witnesses and counterexamples allows test generation to be fully automatic. We discuss complexity issues in minimal cost test generation and describe heuristic test generation algorithms. We illustrate our approach using CTL as temporal logic and SMV as model checker.

We present the modeling and analysis of distributed autonomous robots using the specification language for hybrid systems, called CHARON. Coordination between distributed autonomous robots has attracted researchers of embedded and hybrid systems, since there has been increasing demand for multiple robots working together in a dynamically changing or unknown environment to carry out missions such as search and rescue, cooperative localization, and scouting and reconnaissance. To maximize the capability of performing tasks collaboratively as a team, formation control is one of crucial parts in developing distributed autonomous robots. In this paper formation control of a team of robots is modeled using CHARON and the model is analyzed using simulation with assertion checking capability of the CHARON toolset.

Benefits of high-level modeling and analysis are significantly enhanced if code can be generated automatically from a model such that the correspondence between the model and the code is precisely understood. For embedded control software, hybrid systems is an appropriate modeling paradigm because it can be used to specify continuous dynamics as well as discrete switching between modes. Establishing a formal relationship between the mathematical semantics of a hybrid model and the actual executions of the corresponding code is particularly challenging due to sampling and switching errors. In this paper, we describe an approach to compile the modeling language Charon that allows hierarchical specifications of interacting hybrid systems. We show how to exploit the semantics of Charon to generate code from a model in a modular fashion, and identify sufficient conditions on the model that guarantee the absence of switching errors in the compiled code. The approach is illustrated by compiling a model for coordinated motion of legs for walking onto Sony's AIBO robot.

We address the problem of providing compositional hard real-time guarantees in a hierarchy of schedulers. We first propose a resource model to characterize a periodic resource allocation and present exact schedulability conditions for our proposed resource model under the EDF and RM algorithms. Using the exact schedulability conditions, we then provide methods to abstract the timing requirements that a set of periodic tasks demands under the EDF and RM algorithms as a single periodic task. With these abstraction methods, for a hierarchy of schedulers, we introduce a composition method that derives the timing requirements of a parent scheduler from the timing requirements of its child schedulers in a compositional manner such that the timing requirement of the parent scheduler is satisfied, if and only if the timing requirements of its child schedulers are satisfied.

This paper describes the modeling language CHARON for modular design of interacting hybrid systems. The language allows specification of architectural as well as behavioral hierarchy and discrete as well as continuous activities. The modular structure of the language is not merely syntactic, but is exploited by analysis tools and is supported by a formal semantics with an accompanying compositional theory of refinement. We illustrate the benefits of CHARON in the design of embedded control software using examples from automated highways concerning vehicle coordination.

In addition to real-time requirements, program code size is a critical design factor for real-time embedded systems. To take advantage of the code size vs. execution time trade off provided by reduced bit-width instructions, we propose a design framework that transforms system constraints into task parameters guaranteeing a set of requirements. The goal of our design framework is to derive the temporal parameters and code size parameter of each task in such a way that they collectively guarantee system end-to-end timing requirements while the system code size is minimized. Our design framework is based on asynchronous periodic tasks with pre-period deadlines under EDF scheduling. For schedulability analysis, we present a new feasibility condition that can be more efficiently evaluated than existing ones. When the code size vs. execution time tradeoff can be safely approximated as linear functions, the minimization problem becomes a linear programming problem. However, when the tradeoff is given by a table of possible (code size, execution time) pairs, the problem becomes NP-hard. We provide three heuristic algorithms that can find sub-optimal solutions and evaluate their performance with simulation results.

Network protocols are often analyzed using simulations. We demonstrate how to extend such simulations to check propositions expressing safety properties of network event traces in an extended form of linear temporal logic. Our technique uses the INS simulator together with a component of the MaC system to provide a uniform framework. We demonstrate its effectiveness by analyzing simulations of the ad hoc on-demand distance vector (AODV) routing protocol for packet radio networks. Our analysis finds violations of significant properties and we discuss the faults that cause them. Novel aspects of our approach include modest integration costs with other simulation objectives such as performance evaluation, greatly increased flexibility in specifying properties to be checked and techniques for analyzing complex traces of alarms raised by the monitoring software.

Unpredictable wireless channel errors may cause applications with real-time traffic to receive degraded quality of services due to packet losses. In the presence of such errors, a challenging problem is how to schedule packets to achieve fairness among real-time flows and to maximize the overall system throughput simultaneously. We capture fairness by minimizing the maximum degradation in service over all flows. In this paper, we show that no online algorithm can guarantee a bounded performance ratio with respect to the optimal algorithm. We then compare four different online algorithms and evaluate them using simulations. The first two are EDF (earliest deadline first) and GDF (greatest degradation first) that consider only one aspect of our scheduling goal respectively. EDF is naturally suited for maximizing throughput while GDF seeks to minimize the maximum degradation. The next two are algorithms, called EOG (EDF or GDF) and LFF (lagging flows first), that consider the two aspects of our scheduling goal. EOG simply combines EDF and GDF, whereas LFF tries to favor lagging flows in a non-trivial manner. Our simulation results show that LFF is almost as good as EDF in maximizing the throughput and also is better than GDF in minimizing the maximum degradation. Finally, we also show that there is an optimal polynomial time algorithm for the offline version of the problem.

Why are there so few successful "real-world" programming and testing tools based on academic research? This talk focuses on program analysis tools, and proposes a surprisingly simple explanation with interesting ramifications.

State explosion is a well-known problem that impedes analysis and testing based on state-space exploration. This problem is particularly serious in real time systems because unbounded time values cause the state space to be infinite even for simple systems. The author presents an algorithm that produces a compact representation of the reachable state space of a real time system. The algorithm yields a small state space, but still retains enough information for analysis. To avoid the state explosion which can be caused by simply adding time values to states, our algorithm uses history equivalence and transition bisimulation to collapse states into equivalent classes. Through history equivalence, states are merged into an equivalence class with the same untimed executions up to the states. Using transition bisimulation, the states that have the same future behaviors are further collapsed. The resultant state space is finite and can be used to analyze real time properties. To show the effectiveness of our algorithm, we have implemented the algorithm and have analyzed several example applications.

We describe the Monitoring and Checking (MaC) framework which provides assurance on the correctness of an execution of a real-time system at runtime. Monitoring is performed based on a formal specification of system requirements. MaC bridges the gap between formal specification, which analyzes designs rather than implementations, and testing, which validates implementations but lacks formality. An important aspect of the framework is a clear separation between implementation-dependent description of monitored objects and high-level requirements specification. Another salient feature is automatic instrumentation of executable code. The paper presents an overview of the framework, languages to express monitoring scripts and requirements, and a prototype implementation of MaC targeted at systems implemented in Java.

We propose a unifying method for analysis of scheduling problems in real-time systems. The method is based on ACSR-VP, a real-time process algebra with value-passing capabilities. We use ACSR-VP to describe an instance of a scheduling problem as a process that has parameters of the problem as free variables. The specification is analyzed by means of a symbolic algorithm. The outcome of the analysis is a set of equations, a solution to which yields the values of the parameters that make the system schedulable. Equations are solved using integer programming or constraint logic programming. The paper presents specifications of two scheduling problems as examples.

Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPs are P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems. In this paper, we present two efficient parallel algorithms for RCPP in which its associated label transition system is assumed to have m transitions and n states. The first algorithm runs in O(n/sup 1+/spl epsiv//) time using m/n/sup /spl epsiv// CREW PRAM processors, for any fixed /spl epsiv/<1. This algorithm is analogous to and optimal with respect to the sequential algorithm of P.C. Kanellakis and S.A. Smolka (1990). The second algorithm runs in O(n log n) time using m/n CREW PRAM processors. This algorithm is analogous to and nearly optimal with respect to the sequential algorithm of R. Paige and R.E. Tarjan (1987).

The Graphical Communicating Shared Resources, GCSR, is a specification language with a precise, operational semantics for the specification and analysis of real-time systems. GCSR allows a designer to integrate the functional and temporal requirements of a real-time system along with its run-time resource requirements. The integration is orthogonal in the sense that it produces system models that are easy to modify, e.g., to reflect different resource requirements, allocations and scheduling disciplines. In addition, it renders the verification of resource related requirements natural and straightforward. The formal semantics of GCSR allows the simulation of a system model and the thorough verification of system requirements through equivalence checking and state space exploration. This paper reviews GCSR and reports our experience with the production cell case study.

A real-time process algebra, called ACSR, has been developed to facilitate the specification and analysis of real-time systems. ACSR supports synchronous timed actions and asynchronous instantaneous events. Timed actions are used to represent the usage of resources and to model the passage of time. Events are used to capture synchronization between processes. To be able to specify real-time systems accurately, ACSR supports a notion of priority that can be used to arbitrate among timed actions competing for the use of resources and among events that are ready for synchronization. In addition to operators common to process algebra, ACSR includes the scope operator, which can be used to model timeouts and interrupts. Equivalence between ACSR terms is based on the notion of strong bisimulation. This paper briefly describes the syntax and semantics of ACSR and then presents a set of algebraic laws that can be used to prove equivalence of ACSR processes. The contribution of this paper is the soundness and completeness proofs of this set of laws. The completeness proof is for finite-state ACSR processes, which are defined to be processes without free variables under parallel operator or scope operator.

The correctness of real-time distributed systems depends not only on the function they compute but also on their timing characteristics. Furthermore, those characteristics are strongly influenced by the delays due to synchronization and resource availability. Process algebras have been used successfully to define and prove correctness of distributed systems. More recently, there has been a lot of activity to extend their application to real-time systems. The problem with most current approaches is that they ignore resource constraints and assume either maximum parallelism (i.e., unlimited resources) or pure interleaving (i.e., single resource). Algebra of communicating shared resources (ACSR) is a process algebra designed for the formal specification and manipulation of distributed systems with resources and real-time constraints. A dense time domain provides a more natural way of specifying systems compared to the usual discrete time. Priorities provide a measure of urgency for each action and can be used to ensure that deadlines are met. In ACSR, processes are specified using resource bound, timed actions and instantaneous synchronization events. Processes can be combined using traditional operators such as nondeterministic choice and parallel execution. Specialized operators allow the specification of real-time behavior and constraints. The semantics of ACSR is defined as a labeled transition system. Equivalence between processes is based on the notion of strong bisimulation. A sound and complete set of algebraic laws can be used to transform almost any ACSR process into a normal form.

State explosion is a well-known problem that impedes analysis and testing based on state-space exploration. This problem is particularly serious in real-time systems because unbounded time values cause the state space to be infinite. In this paper, we present an algorithm that produces a compact representation of reachable state space of a real-time system. The algorithm yields a small state space, but still retains enough timing information for analysis. To avoid the state explosion which can be caused by simply adding time values to states, our algorithm first uses history equivalence and transition bisimulation to collapse states into equivalent classes. In this approach, equivalent states have identical observable events although transitions into the states may happen at different times. The algorithm then augments the resultant state space with timing relations that describe time distances between transition executions. For example, the relation @(tr1) + 3 ≤ @(tr2) ≤ @(tr1) + 5 means that transition tr2 is taken 3 to 5 time units before transition tr2 is taken. This is used to analyze timing properties such as minimum and maximum time distances between events. To show the effectiveness of our algorithm, we have implemented the algorithm and are currently comparing it to other existing techniques which generate state space for real-time systems.

Formal methods approaches to software and hardware verification use mathematical models and rigorous proof techniques to describe and analyze system models. Though most formalisms will allow models of unlimited complexity to be constructed, rigorous analysis of realistic models is frequently intractable. In this paper we describe the Algebra of Communicating Shared Resources with Value Passing (ACSR-VP), a process algebra for modeling resource-bound real-time systems, and describe how we are using testing techniques to check functional and real-time properties of realistic systems. Though testing based analysis lacks the certainty of formal analysis, it significantly expands the size of models that can be considered.

This paper describes analysis and simulation for understanding of large Ada-83 real-time software. Ada real-time software is frequently very large in size and very complex. The objective is to describe: (1) discovery of the architecture of the software by decomposing the software into a hierarchical structure, (2) generation of state machines that preserve the real-time properties of the hierarchically organized units, and (3) simulation of the software represented by the state machines. Because of the severe limitation of space, these capabilities are only briefly described, without an example. The first two items above have been exercised in processing over 100,000 lines of Ada-83 code. The third item is still being developed.

Verifying timing properties of real-time systems by tradi-

Graphical communicating shared resources, GCSR, is a formal language for the specification and analysis of real-time systems including their functional and resource requirements. GCSR allows a modular and hierarchical, and thus, scalable specification of a real-time system. GCSR supports notions of communication through events, interrupt, concurrency, and time to describe a real-time system. In addition, GCSR allows the explicit representation of resources and priorities to arbitrate resource contention in a natural way that produces easy to understand and modify specifications. The semantics of GCSR is the algebra of communicating shared resources, a timed process algebra with operational semantics. The process algebra provides behavioral equivalence relations which can be used to verify the correctness of one GCSR specification with respect to the other.

To engineer reliable real-time systems, it is desirable to detect timing anomalies early in the development process. However, there is little work addressing the problem of accurately predicting timing properties of real-time systems before implementations are developed. This paper describes an approach to the specification and schedulability analysis of real-time systems based on the timed process algebra ACSR-VP, which is an extension of algebra of communicating shared resources (ACSR) with value-passing communication and dynamic priorities. Combined with the existing features of ACSR for representing time, synchronization and resource requirements, ACSR-VP is capable of specifying a variety of real-time systems with different scheduling disciplines in a modular fashion. Moreover, we can perform schedulability analysis on real-time systems specified in ACSR-VP automatically by checking for a certain bisimulation relation.

The behavior of concurrent, real-time systems can be specified using a process algebra called CCSR. The underlying computation model of CCSR is a resource-based one in which multiple resources execute synchronously, while processes assigned to the same resource are interleaved according to their priorities. CCSR allows the algebraic specification of timeouts, interrupts, periodic behaviors, and exceptions. This paper develops a natural treatment of preemption, which is based not only on priority, but also on resource utilization and inter-resource synchronization. The preemption ordering leads to a term equivalence based on strong bisimulation, which is also a congruence with respect to the operators. Consequently the equivalence yields a compositional proof system, which is illustrated in the verification of a resource-sharing, producer-consumer problem.

Recently, significant progress has been made in the development of timed process algebras for the specification and analysis of real-time systems. This paper describes a timed process algebra called ACSR, which supports synchronous timed actions and asynchronous instantaneous events. Timed actions are used to represent the usage of resources and to model the passage of time. Events are used to capture synchronization between processes. To be able to specify real systems accurately, ACSR supports a notion of priority that can be used to arbitrate among timed actions competing for the use of resources and among events that are ready for synchronization. The paper also includes a brief overview of other timed process algebras and discusses similarities and differences between them and ACSR.>

The RTC distributed real-time programming system was implemented using AND-OR locking of system resources to meet real-time and concurrency control requirements. Since RTC processes can hold locks while acquiring others, deadlock is possible and therefore a deadlock prevention technique was implemented for AND-OR locking in such systems. The authors briefly discuss the RTC programming system, illustrate the system's use in programming a timed version of the classic dining philosophers example, describe the deadlock prevention technique, and show how it is applied in the RTC dining philosophers example.>

A layered approach to the specification and verification of real-time systems is described. Application processes are specified in the CSR Application Language, which includes high-level language constructs such as timeouts, deadlines, periodic processes, interrupts, and exception handling. A configuration schema is used to map the processes to system resources, and to specify the communication links between them. The authors automatically translate the result of the mapping into the CCSR process algebra, which characterizes CSR's resource-based computation model by a prioritized transition system. For the purposes of verification, a reachability analyzer based on the CCSR semantics has been implemented. This tool mechanically evaluates the correctness of the CSR specification by checking whether an exception state can be reached in its corresponding CCSR term. The effectiveness of this technique is illustrated by a multisensor robot example.>

Language constructs for the expression of timing and concurrency requirements in distributed real-time programs are presented. The approach to concurrent real-time programming is to explicitly express real-time concurrency constraints in a program and allow the run-time system to enforce them. To define these constraints precisely, the authors develop a real-time concurrency model that combines an object-based paradigm for the specification of shared resources, a distributed transaction-based paradigm for the specification of application processes, support for timing constraints, and support for precedence ordering. An implementation of the language constructs with real-time scheduling and locking for concurrency control is also described.>

Timed atomic commitment is defined, protocols to implement it in a realistic operating environment are devised, and its usefulness is shown through an example. In a large class of hard-real-time control applications, components execute concurrently on distributed nodes and must coordinate, under timing constraints, to perform the control task. As such, they perform a type of atomic commitment. Traditional atomic commitment differs, however, because there are no timing constraints; agreement is eventual. The authors define timed atomic commitment (TAC), which requires the processes to be functionally consistent, but allows the outcome to include an exceptional state, indicating that timing constraints have been violated. Centralized and decentralized protocols to implement TAC are presented. Programming constructs for TAC are introduced, and their use is illustrated in a coordinating robots example.>

The authors introduce a proof system for CCSR, a process algebra based on the CSR model. CCSR allows the algebraic specifications of timeouts, interrupts, periodic behaviors and exceptions. A rigorous treatment of preemption, which is based not only on priority but also on resource utilization and inter-resource synchronization, is provided. The theory of preemption leads to a term equivalence based on strong bisimulation, which yields a set of laws forming the proof system. As an illustration, a resource-sharing, producer-consumer problem is presented and the authors use their laws to prove its correctness.>

The performance of two algorithms for timed synchronous communication between a single sender and a single receiver is analyzed. Each weakens the definition of correct timed synchronous communication in a different way, and exhibits a different undesirable behavior. Their sensitivity to various parameters is discussed. These parameters include how long the processes are willing to wait for communication to be successful, how well synchronized the processes are, the assumed upper bound on message delay, and the actual end-to-end message delay distribution. The fault tolerance of the algorithms is discussed and a mixed strategy is proposed that avoids some of the performance problems.>

A model and correctness criteria for timed atomic commitment (TAC) are presented which require the processes to be functionally consistent, but allow the outcome to include an exceptional state, indicating that timing constraints have been violated. Correct TAC behavior is defined by presenting an abstract description of the processes involved in the commitment and minimal correctness criteria for their behavior. The correctness criteria capture the intuitive notion that an exception outcome should only occur in the presence of faults, and an aborted outcome should only occur if faults occur or some process votes no. A centralized two-phase commit protocol was modified to meet the correctness criteria by introducing deadlines on the various stages the participants go through (voting and performing), and on the decision phase for the coordinator. The deadlines are derived using several system parameters: maximum message delay, clock drift, and execution time. The protocol is then shown to be correct.>

A real-time formalism called communicating shared resources (CSR) is presented. CSR consists of a programming language that allows the explicit expression of timing constraints and resources, and a computation model that resolves resource contention based on event priority. A full denotational semantics is provided for the programming language, grounded in a resource-based computation model. To illustrate CSR, a distributed robot system consisting of a robot arm and a sensor is presented.>

The performance of a parallel algorithm depends in part on how well the interconnection topology of the target parallel system matches the communication patterns of the algorithm. We describe how to generate a topology for a network that can be configured into any r-regular topology. The topology generated has small total expansion with respect to a given task graph. The expansion of an edge in a task graph is the length of the shortest path that the edge maps to in the processor graph. The algorithm used to generate the topologies is analyzed and its average case behavior is determined. In addition, this synthesis method is compared to the conventional approach of mapping a task graph onto a fixed processor topology.

The digital multiplexed interface (DMI) specifies the interface requirements for multiplexed data communication over digital facilities between a host computer and a PBX. A part of the DMI's packet-mode data-transfer protocol, which is based on the X.25 packet-level protocols, is specified formally using the selection/resolution (S/R) model. A formal verification of the resetting phase of this protocol, using the S/R-model-based software tool SPANNER, is presented. It is shown that the protocol is not fully correct in the sense that some sequence of events may lead it to unsafe states. These states give rise to a livelock situation. A way to rectify this problem is suggested.>

The performance of a parallel algorithm depends in part on the interconnection topology of the target parallel system. An interconnection network is called reconfigurable if its topology can be changed between different algorithm executions. Since communication patterns vary from one parallel algorithm to another, a reconfigurable network can effectively support algorithms with different communication requirements. It is shown how to generate a network topology that is optimized with respect to the communication patterns of a given task. The algorithm presented takes as input a task graph and generates as output a topology that closely matches the given input graph. The topologies generated by the algorithm are analyzed with respect to optimum interconnection topologies for the best, worst, and average cases. Simulation results verify the average-case performance prediction and confirm that, on the average, the optimum topologies are generated.>

In distributed real-time systems, communicating processes cannot be delayed for arbitrary amounts of time while waiting for messages. Thus, communication primitives used for real-time programming usually allow the inclusion of a deadline or timeout to limit potential delays due to synchronization. This paper interprets timed synchronous communication as having absolute deadlines. Various ways of implementing deadlines are discussed, and two useful timed synchronous communication problems are identified which differ in the number of participating senders and receivers and type of synchronous communication. For each problem, a simple algorithm is presented and shown to be correct. The algorithms are shown to guarantee maximal success and to require the smallest delay intervals during which processes wait for synchronous communication. We also evaluate the number of messages used to reach agreement.

A distributed testbed designed to support the development of a multi-sensory (vision and tactile) system for investigations in "active perception" of three dimensional objects is presented. Active perception means being able to not only see and feel objects but also manipulate and probe them. The nucleus of the testbed is a network of heterogeneous computers designed to support low-level real-time control processes as well as high-level knowledge-based systems. The programming environment of the testbed facilitates the construction and execution of a distributed multi-sensory system from sequential programs written in different programming languages.

Abstract More than 120,000 lines of Pascal programs, written by graduate students and faculty members, have been statically analysed to provide a better understanding of how the language is ‘really’ used. The analysis was done within twelve distinct contexts to discover differences in usage patterns among the various contexts. For example, it was found that 47 per cent of the operands in arguments lists were constants. The results are displayed as tables of frequency counts which show how often each construct is used within a context. Also, we have compared our findings to the results from studies of other languages, such as FORTRAN, SAL and XPL.