@inproceedings {345, title = {Metasploit for Cyber-Physical Security Testing with Real-Time Constraints}, booktitle = {5th International Conference on Science of Cyber Security (SciSec)}, year = {2022}, address = {Matsue, Japan}, author = {Sulav Lal Shrestha and Taylor Lee and Sebastian Fischmeister} } @inproceedings {343, title = {Powertrace-based Fuzzing of CAN Connected Hardware}, booktitle = {IEEE International Conference on Cyber Security and Resilience (CSR)}, year = {2022}, publisher = {IEEE}, organization = {IEEE}, address = {Rhodes, Greece}, doi = {10.1109/CSR54599.2022.9850299}, author = {Murray Dunne and Sebastian Fischmeister} } @inproceedings {344, title = {Work-in-Progress: Boot Sequence Integrity Verification with Power Analysis}, booktitle = {ACM SIGBED International Conference on Embedded Software (EMSOFT)}, year = {2022}, publisher = {ACM}, organization = {ACM}, address = {Shanghai, China}, author = {Arthur Grisel-Davy and Milan Bhogayata and Srijan Pabbi and Apurva Narayan and Sebastian Fischmeister} } @inproceedings {346, title = {The Boy Who Cried Wolf: On Precision in CAN Bus Intrusion Detection }, booktitle = {Embedded Security in Cars}, year = {2021}, address = {Michigan, USA}, author = {Shikhar Sakhuja and Murray Dunne and Sebastian Fischmeister} } @inbook {332, title = {Secure Dynamic Nonlinear Heterogeneous Vehicle Platooning: Denial-of-Service Cyber-Attack Case}, booktitle = {Security and Privacy in Cyber-Physical Systems: Threats and Defenses. Studies in Systems, Decision and Control}, year = {2021}, publisher = {Springer}, organization = {Springer}, abstract = {

Connected and Automated Vehicles (CAVs), as a large class of cyberphysical systems, have recently emerged as an effective autonomous driving mechanism in intelligent transportation systems in terms of improvement in safety, fuel economy, road throughput, and driving comfort. This chapter deals with a Secure Distributed Nonlinear Model Predictive Control (Secure\–DNMPC) algorithm consisting of i) detection and ii) mitigation phases to securely control a string of CAVs, namely vehicle platoons. The approach ensures the desired control performance of a nonlinear heterogeneous platoon equipped by different communication topologies under the premise of the existence of Denial-of-Service (DoS) attacks. The proposed method is also capable of providing safe and secure control of dynamic platoons in which arbitrary vehicles might perform cut-in and/or cut-out maneuvers. Convergence time and stability analysis of the system are also investigated in some cases.\  Furthermore, to handle DoS attacks modeled by an exceeding time delay in intervehicular data transmission, we propose the integration of an Unscented Kalman Filter (UKF) design within the controller resulting in a novel Secure\–DNMPC\–UKF co-design. This, in essence, estimates the delayed system states and feeds the predicted values to the Secure\–DNMPC, which efficiently mitigates the attack effects.\  Simulation results demonstrate the fruitfulness of the proposed method.

}, author = {Mohammad Hossein Basiri and Nasser L. Azad and Sebastian Fischmeister} } @article {342, title = {Security-aware optimal actuator placement in vehicle platooning}, journal = {Asian Journal Of Control}, year = {2021}, abstract = {

Vehicle platooning, as a large class of cyber-physical
systems, is prone to be under the risk of cyber attacks. One (or more)
external intelligent intruder(s) might attack one (or more) of the vehicles
participating in a platoon. This paper proposes a general approach to find
an optimal actuator placement strategy according to the Stackelberg game
between the attacker and the defender. The game payoff is the energy needed
by the attacker to steer the consensus follower\–leader dynamics of the
system towards his desired direction. The attacker tries to minimize this
energy while the defender attempts to maximize it. Thus, based on the
defined game and its optimal equilibrium point, the defender(s) selects
optimal actuator placement action to face the attacker(s). Both cases of
single attacker\–single defender and multiple attackers\–multiple defenders
cases are investigated. Furthermore, we study the effects of different
information flow topologies, namely, the unidirectional and bidirectional
data transfer structures. Besides, the impacts of increasing the
connectivity among the nodes on the security level of the platoon are
presented. Simulation results for h\–nearest neighbor platoon formations
along with experimental results using the scaled cars governed by robotic
operating system (ROS) verify the effectiveness of the method.

}, doi = {10.1002/asjc.2567}, author = {Basiri, Mohammad Hossein and Pirani, Mohammad and Nasser L. Azad and Fischmeister, Sebastian} } @article {336, title = {What Can We Monitor Over Unreliable Channels?}, journal = {International Journal on Software Tools for Technology Transfer}, volume = {23}, year = {2021}, pages = {579--600}, abstract = {

This article addresses the question of what properties can be monitored over an unreliable communication channel.\  We model unreliable communications as mutations to finite traces and define what it means for a property to be immune to such a mutation.\  We also introduce the idea of a trustworthy verdict, which is a verdict guaranteed to be correct in the presence of a trace mutation.\  We show that the trustworthiness of a verdict or immunity of a property for a single mutation is equivalent to the trustworthiness or immunity for any number of mutations.\  We classify trustworthy verdicts on $\omega$-regular properties by updating a recently proposed monitorability-focused refinement of the safety-liveness taxonomy.\  The article also includes a fixed-parameter tractable algorithm to test an $\omega$-regular property for immunity to a trace mutation.\  Our results show that many of the most common properties can be monitored over unreliable channels.

}, issn = {1433-2779}, doi = {10.1007/s10009-021-00625-z}, author = {Sean Kauffman and Klaus Havelund and Sebastian Fischmeister} } @inproceedings {328, title = {Attack Resilient Heterogeneous Vehicle Platooning Using Secure Distributed Nonlinear Model Predictive Control}, booktitle = {28th Mediterranean Conference on Control and Automation (MED)}, year = {2020}, publisher = {IEEE}, organization = {IEEE}, address = {Saint-Raphael, France}, abstract = {

Recently, vehicle platoons have offered significant enhancements in traffic management, energy consumption and safety in intelligent transportation systems. Despite the benefits brought by the platoons, they potentially suffer from insecure networks which provide the connectivity among the vehicles participating in the platoon. This paper deals with the secure control of vehicle platoons under the risk of a common cyber attack, namely Denial of Service (DoS) attack. A DoS intruder can endanger the security of platoon by jamming the communication network among the vehicles which is responsible to transmit inter-vehicular data throughout the platoon. This can potentially result in huge performance degradation or even hazardous collisions. We propose a secure distributed nonlinear model predictive control algorithm consisting of i) detection and ii) mitigation phases. The algorithm is capable of handling DoS attack performed on a platoon equipped by different communication topologies and at the same time it guarantees the desired formation control performance. Stability analysis of the attacked platoon running the given algorithm is also presented. Simulation results on a sample heterogeneous attacked platoon exploiting two-predecessor follower communication environment demonstrates the effectiveness of the method.

}, author = {Basiri, Mohammad Hossein and Azad, Nasser and Fischmeister, Sebastian} } @inproceedings {331, title = {Distributed Nonlinear Model Predictive Control and Metric Learning for Heterogeneous Vehicle Platooning with Cut-in/Cut-out Maneuvers}, booktitle = {59th Conference on Decision and Control (CDC)}, year = {2020}, publisher = {IEEE}, organization = {IEEE}, address = {Jeju Island, Republic of Korea}, abstract = {

Vehicle platooning has been shown to be quite fruitful in the transportation industry to enhance fuel economy, road throughput, and driving comfort. Model Predictive Control (MPC) is widely used in literature for platoon control to achieve certain objectives, such as safely reducing the distance among consecutive vehicles while following the leader vehicle. In this paper, we propose a Distributed Nonlinear MPC (DNMPC), based upon an existing approach, to control a heterogeneous dynamic platoon with unidirectional topologies, handling possible cut-in/cut-out maneuvers. The introduced method addresses a collision-free driving experience while tracking the desired speed profile and maintaining a safe desired gap among the vehicles. The time of convergence in the dynamic platooning is derived based on the time of cut-in and/or cut-out maneuvers. In addition, we analyze the improvement level of driving comfort, fuel economy, and absolute and relative convergence of the method by using distributed metric learning and distributed optimization with Alternating Direction Method of Multipliers (ADMM). Simulation results on a dynamic platoon with cut-in and cut-out maneuvers and with different unidirectional topologies show the effectiveness of the introduced method.

}, author = {Mohammad Hossein Basiri and Benyamin Ghojogh and Nasser L. Azad and Sebastian Fischmeister and Fakhri Karray and Mark Crowley} } @inproceedings {329, title = {Distributed Time-varying Kalman Filter Design and Estimation over Wireless Sensor Networks Using OWA Sensor Fusion Technique}, booktitle = {28th Mediterranean Conference on Control and Automation (MED)}, year = {2020}, publisher = {IEEE}, organization = {IEEE}, address = {Saint-Raphael, France}, abstract = {

In this paper, a novel estimation procedure is proposed, which consists of designing a distributed class of time-varying Kalman filter based on wireless sensor networks topology along with a new sensor fusion method. The proposed technique is employed to estimate the states and outputs of a linear time-varying system with a high level of accuracy. Both the dynamics of the system and the measurements are assumed to be contaminated by external noises. The notion of Orness and Ordered Weighted Averaging (OWA) operator technique are utilized to fuse the estimation of the sensors. O\’Hagan method, along with the gradient descent method, is employed to find the optimal weights. In the introduced approach, OWA weights are learned for each observation such that they efficiently minimize the estimation error for that particular observation. This will result in an outstanding high accurate sensor fusion outcome. In addition, two optimistic and pessimistic exponential OWA operators are used and compared together to achieve a pre-specified level of Orness. The simulation results are shown on a given linear time-varying system to verify the effectiveness of the proposed sensor fusion distributed filtering design method.

}, author = {Basiri, Mohammad Hossein and Azad, Nasser and Fischmeister, Sebastian} } @inproceedings {334, title = {A Generalizable Saliency Map-based Interpretation of Model Outcome}, booktitle = {International Conference on Pattern Recognition (CPR)}, year = {2020}, address = {Milano, Italy}, abstract = {

One of the significant challenges of deep neural networks is that the complex nature of the network prevents human comprehension of the outcome of the network. Consequently, the applicability of complex machine learning models is limited in the safety-critical domains, which incurs risk to life and property.\  To fully exploit the capabilities of complex neural networks, we propose a non-intrusive interpretability technique that uses the input and output of the model to generate a saliency map. The method works by empirically optimizing a randomly initialized input mask by localizing and weighing individual pixels according to their sensitivity towards the target class. Our experiments show that the proposed model interpretability approach performs better than the existing saliency map-based approaches methods at localizing the relevant input pixels.

Furthermore, to obtain a global perspective on the targetspecific explanation, we propose a saliency map reconstruction approach to generate acceptable variations of the salient inputs from the space of input data distribution for which the model outcome remains unaltered. Experiments show that our interpretability method can reconstruct the salient part of the input with a classification accuracy of 89\%.

}, author = {Shailja Thakur and Sebastian Fischmeister} } @article {335, title = {Palisade: A Framework for Anomaly Detection in Embedded Systems}, journal = {Journal of Systems Architecture}, year = {2020}, pages = {1--17}, abstract = {

In this article, we propose Palisade, a distributed framework for streaming anomaly detection. Palisade is motivated by the need to apply multiple detection algorithms for distinct anomalies in the same scenario. Our solution blends low latency detection with deployment flexibility and ease-of-modification. This work includes a thorough description of the choices made in designing Palisade and the reasons for making those choices. We carefully define symptoms of anomalies that may be detected, and we use this taxonomy in characterizing our work. The article includes two case studies using a variety of anomaly detectors on streaming data to demonstrate the effectiveness of our approach in an embedded setting.

}, issn = {1383-7621}, doi = {10.1016/j.sysarc.2020.101876}, author = {Sean Kauffman and Murray Dunne and Giovani Gracioli and Waleed Khan and Nirmal Benann and Sebastian Fischmeister} } @inproceedings {337, title = {Parameterless Semi-Supervised Anomaly Detection in Univariate Time Series}, booktitle = {Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML)}, year = {2020}, author = {Oleg Iegorov and Sebastian Fischmeister} } @inproceedings {330, title = {Assessing the Robustness of Arrival Curves Models for Real-time Systems}, booktitle = {Intl. Conference on Formal Modeling and Analysis of Timed Systems}, year = {2019}, pages = {23--40}, address = {Amsterdam, The Netherlands}, abstract = {

Design of real-time systems is prone to uncertainty due to software and hardware changes throughout their deployment. In this context, both industry and academia have shown interest in new trace mining approaches for diagnosis and prognosis of complex embedded systems. Trace mining techniques construct empirical models that mainly target achieving high accuracy in detecting anomalies. However, when applied to safety-critical systems, such models lack in providing theoretical bounds on the system resilience to variations from these anomalies. This paper presents the first work that derives robustness criteria on a trace mining approach that constructs arrival-curves models from dataset of traces collected from real-time systems. Through abstracting arrivalcurves models to the demand-bound functions of a sporadic task under an EDF scheduler, the analysis presented in the paper enables designers to quantify the permissible change to the parameters of a given task model by relating to the variation expressed within the empirical model. The result is a methodology to evaluate a system to dynamically changing workloads. We evaluate the proposed approach on an industrial cyberphysical system that generates traces of timestamped QNX events.

}, doi = {10.1007/978-3-030-29662-9_2}, author = {Mahmoud Salem and Gonzalo Carvajal and Tong Liu and Sebastian Fischmeister} } @inproceedings {320, title = {Deep Learning for System Trace Restoration}, booktitle = {International Joint Conference on Neural Networks (IJCNN)}, year = {2019}, address = {Budapest, Hungary}, abstract = {

Most real-world datasets, and particularly those collected from physical systems, are full of noise, packet loss, and other imperfections. However, most specification mining, anomaly detection and other such algorithms assume, or even require, perfect data quality to function properly. Such algorithms may work in lab conditions when given clean, controlled data, but will fail in the field when given imperfect data. We propose a method for accurately reconstructing discrete temporal or sequential system traces affected by data loss, using Long Short- Term Memory Networks (LSTMs). The model works by learning to predict the next event in a sequence of events, and uses its own output as an input to continue predicting future events. As a result, this method can be used for data restoration even with streamed data. Such a method can reconstruct even long sequence of missing events, and can also help validate and improve data quality for noisy data. The output of the model will be a close reconstruction of the true data, and can be fed to algorithms that rely on clean data. We demonstrate our method by reconstructing automotive CAN traces consisting of long sequences of discrete events. We show that given even small parts of a CAN trace, our LSTM model can predict future events with an accuracy of almost 90\%, and can successfully reconstruct large portions of the original trace, greatly outperforming a Markov Model benchmark. We separately feed the original, lossy, and reconstructed traces into a specification mining framework to perform downstream analysis of the effect of our method on state-of-the-art models that use these traces for understanding the behavior of complex systems.

}, author = {Ilia Sucholutsky and Apurva Narayan and Matthias Schonlau and Sebastian Fischmeister} } @inproceedings {323, title = {Event Stream Abstraction Using Nfer: Demo Abstract}, booktitle = {International Conference on Cyber-Physical Systems}, year = {2019}, pages = {332 to 333}, publisher = {ACM}, organization = {ACM}, address = {Montreal, Canada}, abstract = {

We propose to demonstrate the open source implementation of nfer (http://nfer.io), a language and system for abstracting event streams.\  The tool is applicable to a wide variety of cyber-physical systems, and supports both manual and mined specifications.\  In addition to basic operation, we will demonstrate standalone monitor generation and integration with the popular R and Python languages.\  The demonstration will use real-world data captured from applications such as an autonomous vehicle and a hexacopter.

}, doi = {10.1145/3302509.3313327}, author = {Sean Kauffman and Sebastian Fischmeister} } @inproceedings {318, title = {Kalman Filter Based Secure State Estimation and Individual Attacked Sensor Detection in Cyber-Physical Systems}, booktitle = {Annual American Control Conference (ACC)}, year = {2019}, address = {Philadelphia, USA}, abstract = {

In this paper we propose two real-time attack detection and secure state estimation algorithms, namely Rolling Window Detector (RWD) and Novel Residual Detector (NRD). \ These algorithms are basically developed based on Kalman state estimation. In the former, we present a statistical testing approach which is handled over a finite time horizon T to detect individual attacked sensors. The latter extends the χ2 \–detector to be able to detect individual compromised sensors. Both methods then will be employed together with a modified version of Kalman filter to perform a secure state estimation with a relatively low estimation error. Efficiency of the algorithms will be assessed in both unstealthy and stealthy scenarios. \ Productivity of the methods will be underlined in the stealthy case, which is of much more significance among cyber-security challenges. Simulation results on an IEEE 14-bus power grid test system along with a comprehensive comparison between the performance of RWD and NRD with a recently introduced tool, which is the only other method that tries to detect individual attacked sensors, proves the effectiveness of the algorithms.

}, author = {M.H. Basiri and J.G. Thistle and J.W. Simpson-Porco and S. Fischmeister} } @inproceedings {324, title = {Monitorability Over Unreliable Channels}, booktitle = {International Conference on Runtime Verification (RV)}, year = {2019}, pages = {256 to 272}, address = {Porto, Portugal}, abstract = {

In Runtime Verification (RV), monitoring a program means checking an execution trace of the program for satisfactions and violations of properties. \ The question of which properties can be effectively monitored over ideal channels has mostly been answered by prior work. \ However, program monitoring is often deployed for remote systems where communications may be unreliable.

In this work, we address the question of what properties are monitorable over an unreliable communication channel. \ We describe the different types of mutations that may be introduced to an execution trace and examine their effects on program monitoring. \ We propose a fixed-parameter tractable algorithm for determining the immunity of a finite automaton to a trace mutation and show how it can be used to classify omega-regular properties as monitorable over channels with that mutation.

}, doi = {10.1007/978-3-030-32079-9_15}, author = {Sean Kauffman and Klaus Havelund and Sebastian Fischmeister} } @inproceedings {319, title = {Safety and Security Analysis of AEB for L4 Autonomous Vehicle Using STPA}, booktitle = {Workshop on Autonomous Systems Design (ASD 2019)}, year = {2019}, address = {Florence, Italy}, abstract = {

Autonomous vehicles (AVs) are coming to our streets. Due to the presence of highly complex software systems in AVs, there is a need for a new hazard analysis technique to meet stringent safety standards. System Theoretic Process Analysis (STPA), based on Systems Theoretic Accident Modeling and Processes (STAMP), is a powerful tool that can identify, define, analyze and mitigate hazards from the earliest conceptual stage deployment to the operation of a system. Applying STPA to autonomous vehicles demonstrates STPA\&$\#$39;s applicability to preliminary hazard analysis, alternative available, developmental tests, organizational design, and functional design of each unique safety operation.


This paper describes the STPA process used to generate system design requirements for an Autonomous Emergency Braking (AEB) system using a top-down analysis approach to system safety. The paper makes the following contributions to practicing STPA for safety and security:
1. It describes the incorporation of safety and security analysis in one process and discusses the benefits of this;
2. It provides an improved, structural approach for scenario analysis, concentrating on safety and security;
3. It demonstrates the utility of STPA for gap analysis of existing designs in the automotive domain;
4. It provides lessons learned throughout the process of applying STPA and STPA.

}, author = {Shefali Sharma and Adan Flores and Chris Hobbs and Jeff Stafford and Sebastian Fischmeister} } @article {326, title = {Security of Vehicle Platooning: A Game-Theoretic Approach}, journal = {IEEE Access}, volume = {7}, year = {2019}, pages = {185565--185579}, abstract = {

In this paper, we study the security of a vehicle platoon exposed to cyber attacks using a game-theoretic approach. The platoon topologies under investigation are directed (called predecessor following) or undirected (bidirectional) weighted graphs. The edge weights specify the quality of the communication links between the vehicles in both the unidirectional/bidirectional data transfer environments. The attacker-detector game is defined as follows. The attacker targets some vehicles in the platoon to attack and the detector deploys monitoring sensors on the vehicles. The attacker\’s objective is to be as stealthy to the sensors as possible while the detector tries to place the monitoring sensors to detect the attack impact as much as it can. The existence of Nash Equilibrium (NE) strategies for this game is investigated based on which the detector can choose specific vehicles to put his sensors on and increase the security level of the system. Moreover, we study the effect of adding (or removing) communication weights between vehicles on the game value. The simulation and experimental results conducted on a vehicle platoon setup using Robotic Operating System (ROS) demonstrate the effectiveness of our analyses.

}, doi = {10.1109/ACCESS.2019.2961002}, author = {Basiri, Mohammad H. and Pirani, Mohammad and Azad, Nasser and Fischmeister, Sebastian} } @inproceedings {338, title = {Sender Authentication for Automotive In-Vehicle Networks through Dual Analog Measurements to Determine the Location of the Transmitter}, booktitle = {5th International Conference on Information Systems Security and Privacy (ICISSP)}, year = {2019}, address = {Prague, Czech Republic}, abstract = {

Controller Area Network (CAN) is a fundamentally insecure communications bus. Its intrinsic lack of sender
authentication makes impersonation attacks a severe threat to the security of systems that rely on CAN for
communication between devices. In this paper, we propose a novel technique to enforce sender authenticity
on a CAN bus. The technique is reliable, robust, and reasonably easy and inexpensive to implement, as it relies
on non-clonable physical characteristics of the transmitted signals. In particular, we measure the analog signal
at two different locations on the CAN bus physical wire; the signal corresponding to the transmitted message
travels through the wire at a certain speed, which allows us to determine the physical location (i.e., position
along the wire) of the transmitter as a function of the relative delay between the two analog measurements.
Our work includes an experimental evaluation on an actual vehicle, with results that suggest that the technique
is effective and practical.

}, author = {Carlos Moreno and Sebastian Fischmeister} } @inproceedings {309, title = {A Comparison of Data Streaming Frameworks for Anomaly Detection in Embedded Systems}, booktitle = {International Workshop on Security and Privacy for the Internet-of-Things (IoTSec)}, year = {2018}, address = {Orlando, USA}, abstract = {

As IoT devices are integrated into our daily lives, verification and security become of increasing concern. Using anomaly detection methods, we can identify damaged and compromised devices by examining traces of their activity. Collecting these traces with minimal overhead is a core requirement of any anomaly detection system. We evaluate four publish-subscribe broker systems on their viability for trace collection in the context of IoT devices. Our comparison considers ordering and delivery guarantees, client language support, data structure support, intended use case, and maturity. We run each system on original Raspberry Pis and collect network performance statistics, measuring their capability to collected traces in a resource-constrained embedded systems environment. \ We conclude with recommendations for designing an anomaly detection system for IoT devices.

}, author = {Murray Dunne and Giovani Gracioli and Sebastian Fischmeister} } @article {316, title = {Energy-efficient Multiple Producer-Consumer}, journal = {IEEE Transactions on Parallel and Distributed Systems}, year = {2018}, abstract = {

Hardware energy efficiency has been one of the prominent objectives of system design in the last two decades. However, with the recent explosion in mobile computing and the increasing demand for green data centers, software energy efficiency has also risen to be an equally important factor. The majority of classic concurrency control algorithms were designed in an era when energy efficiency was not an important dimension in algorithm design. Concurrency control algorithms are applied to solve a wide range of problems from kernel-level primitives in operating systems to networking devices and web services. These primitives and services are constantly and heavily invoked in any computing system and by a larger scale in networking devices and data centers. Thus, even a small change in their energy spectrum can make a huge impact on overall energy consumption for long periods of time.

}, doi = {10.1109/TPDS.2018.2867853}, author = {Ramy Medhat and Borzoo Bonakdarpour and Sebastian Fischmeister} } @inproceedings {317, title = {A Framework for Inference and Identification of Hybrid-System Models: Mixed Event-Time-driven Systems (METS)}, booktitle = {IFAC-PapersOnLine (Proceedings of 18th IFAC Symposium on System Identification)}, volume = {51}, year = {2018}, pages = {292--297}, address = {Stockholm, Sweden}, abstract = {

This paper proposes a simplified framework for the experimental inference and identification of models of hybrid systems. A problematic feature of such system identification is the presence of different {\textquoteleft}{\textquoteleft}modes\&$\#$39;\&$\#$39; of evolution of continuous state variables: this may necessitate not only the identification of the dynamics of the different modes, but also the identification of changes of mode. Inspired by the idea that the physics underlying the system is often invariant, this paper proposes a simplified framework that models hybrid systems in the form of separate untimed, {\textquoteleft}{\textquoteleft}event-driven\&$\#$39;\&$\#$39; and dynamical, {\textquoteleft}{\textquoteleft}time-driven\&$\#$39;\&$\#$39; components that are coupled only through input and output signals. Signals from the event-driven component are assumed to affect the dynamics of the time-driven component only in a relatively limited manner -- either as direct inputs, or by modulating output feedback within the time-driven component; the {\textquoteleft}{\textquoteleft}intrinsic,\&$\#$39;\&$\#$39; {\textquoteleft}{\textquoteleft}open-loop\&$\#$39;\&$\#$39; dynamics of the time-driven component do not change. These assumptions largely decouple the estimation of the event- and time-driven components, avoiding the problem of distinguishing separate modes, and permitting the leveraging of standard system-identification methods. Two well known examples serve to illustrate the approach.

}, author = {Basiri, Mohammad Hossein and Thistle, John and Fischmeister, Sebastian} } @article {308, title = {Inferring Event Stream Abstractions}, journal = {Formal Methods in System Design}, year = {2018}, pages = {29}, chapter = {1}, abstract = {

We propose a formalism for specifying event stream abstractions for use in spacecraft telemetry processing. Our work is motivated by the need to quickly process streams with millions of events generated by the Curiosity rover on Mars. \ The approach builds a hierarchy of event abstractions for telemetry visualization and querying to aid human comprehension. \ Such abstractions can also be used as input to other runtime verification tools. Our notation is inspired by Allen\&$\#$39;s Temporal Logic, and provides a rule-based declarative way to express event abstractions. We present an algorithm for applying specifications to an event stream and explore modifications to improve the algorithm\&$\#$39;s asymptotic complexity. The system is implemented in both Scala and C, with the specification language implemented as internal as well as external DSLs. We illustrate the solution with several examples, a performance evaluation, and a real telemetry analysis scenario.

}, issn = {1572-8102}, doi = {10.1007/s10703-018-0317-z}, author = {Sean Kauffman and Klaus Havelund and Rajeev Joshi and Sebastian Fischmeister} } @inproceedings {311, title = {Lessons-learned from Applying STAMP Safety and Security Analysis on AEB for L4 Autonomous Driving}, booktitle = {STAMP Workshop}, year = {2018}, abstract = {

Abstract\—Autonomous vehicles (AV) are coming to our streets. Due to the presence of highly complex software systems in AVs, there is a need for a new hazard analysis technique to meet stringent safety standards. System Theoretic Process Analysis (STPA) based on Systems Theoretic Accident Modeling and Processes (STAMP) is a powerful tool to identify, define, analyze and mitigate hazards from the earliest conceptual stage of development to the operation of a system. Applying STPA to autonomous vehicles demonstrates STPA\&$\#$39;s applicability for the preliminary hazard analysis, alternative available, developmental test, organizational design, and functional design to each unique safety operation.
This paper describes the STPA process used to generate system design requirements for an Autonomous Emergency Braking (AEB) system using a top-down analysis approach to system safety.
The paper makes the following contributions to practicing STPA for safety and security:
1) It describes the incorporation of safety and security analysis in one process and discusses the benefits of doing so;
2) It provides an improved structured approach for scenario analysis concentrating on safety and security; 3) It demonstrates the utility of STPA
analysis for gap analysis of existing designs in the automotive domain;
4) It provides lessons learned throughout the process of applying STPA and STPA-sec.

}, author = {Shefali Sharma and Adan Flores and Carlos Moreno and Chris Hobbs and Jeff Stafford and Kamal Lamichhane and Waleed Khan and Sebastian Fischmeister} } @inproceedings {307, title = {Mining Task Precedence Graphs from Real-Time Embedded System Traces}, booktitle = {Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2018}, address = {Porto, Portugal}, abstract = {

Real-time embedded systems have evolved from simple, self-contained single-processor computers to distributed multiprocessor systems that are extremely hard to develop and maintain. Execution tracing has proved itself to be a useful technology to gain a detailed knowledge of runtime behavior of software systems. However, the size and complexity of execution traces generated by modern embedded systems make manual trace analysis impossible. Therefore, software developers need tools to extract high-level system models from raw trace data. \ In this paper, we address the problem of mining task precedence graphs (TPG) from embedded system traces. A TPG can be helpful in performing several crucial software development and maintenance activities: understanding legacy systems, finding runtime bugs, and detect and diagnose anomalies in running systems. We rely on the recurrent nature of real-time systems to solve the TPG mining problem.
We propose algorithms to train a TPG on a set of system traces, as well as an algorithm to detect anomalies in trace streams using a TPG. We evaluate our algorithms on industrial execution traces generated on production cars

}, author = {Oleg Iegorov and Sebastian Fischmeister} } @article {313, title = {Mining Timed Regular Specifications from System Traces}, journal = {ACM Transactions on Embedded Computing Systems}, volume = {17}, year = {2018}, abstract = {

Temporal properties define the order of occurrence and timing constraints on event occurrence. Such specifi- cations are important for safety-critical real-time systems. We propose a framework for automatically mining temporal properties that are in the form of timed regular expressions (TREs) from system traces. Using an abstract structure of the property, the framework constructs a finite state machine to serve as an acceptor. We analytically derive speedup for the fragment and confirm the speedup using empirical validation with syn- thetic traces. The framework is evaluated on industrial-strength safety-critical real-time applications using traces with more than 1 million entries.

}, doi = {10.1145/3147660}, author = {Apurva Narayan and Greta Cutulenco and Yogi Joshi and Sebastian Fischmeister} } @inproceedings {306, title = {Non-Intrusive Program Tracing of Non-Preemptive Multitasking Systems Using Power Consumption}, booktitle = {Design, Automation and Test in Europe Conference and Exhibition (DATE)}, year = {2018}, address = {Dresden, Germany}, abstract = {

System tracing, runtime monitoring, execution reconstruction are useful techniques for protecting the safety and integrity of systems. Furthermore, with time-aware or overheadaware techniques being available, these techniques can also be used to monitor and secure production systems. As operating systems gain in popularity, even in deeply embedded systems, these techniques face the challenge to support multitasking.

In this paper, we propose a novel non-intrusive technique, which efficiently reconstructs the execution trace of nonpreemptive multitasking system by observing power consumption characteristics. Our technique uses the control-flow graph (CFG) of the application program to identify the most likely block of code that the system is executing at any given point in time. For the purpose of the experimental evaluation, we first instrument the source code to obtain power consumption information for each basic block, which is used as the training data for our Dynamic Time Warping and k-Nearest Neighbours (k-NN) classifier. \ Once the system is trained, this technique is used to identify live code-block execution (LCBE). We show that the technique can reconstruct the execution flow of programs in a multi-tasking environment with high accuracy.

}, author = {Kamal Lamichhane and Carlos Moreno and Sebastian Fischmeister} } @inproceedings {310, title = {Prevent: a Predictive Run-time Verification Framework Using Statistical Learning}, booktitle = {16th International Conference on Software Engineering and Formal Methods}, year = {2018}, address = {Toulouse, France}, abstract = {

Run-time Verification (RV) is an essential component of developing cyber-physical systems, where often the actual model of the system is infeasible to obtain or is not available. In the absence of a model, i.e., black-box systems, RV techniques evaluate a property on the execution path of the system and reach a verdict that the current state of the system satisfies or violates a given property.
In this paper, we introduce Prevent, a predictive runtime verification framework, in which if a property is not currently satisfied, the monitor generates the probability based on the finite extensions of the execution path, that satisfy the specification property. We use Hidden Markov Model (HMM) to extend the partially observable paths of the system. \ The HMM is trained on a set of iid samples generated by the system. \ We then use reachability analysis to construct a tabular monitor that provides the probability that the extended path satisfies or violates the specification from the current state. The current state is estimated at run-time using Viterbi algorithm which gives the most probable state. \ We show the empirical evaluation of Prevent on a modified version of randomized dining philosopher and on the QNX Neutrino kernel traces collected from the autopilot software of a hexacopter.

}, author = {Reza Babaee and Arie Gurfinkel and Sebastian Fischmeister} } @article {273, title = {Accurate Measurement of Small Execution Times {\textendash} Getting Around Measurement Errors}, number = {TR-2017-cmoreno-001}, year = {2017}, institution = {University of Waterloo}, address = {Waterloo, Canada}, abstract = {

Engineers and researchers often require accurate measurements of small execution times or duration of events in a program. Errors in the measurement facility can introduce important challenges, especially when measuring small intervals. Mitigating approaches commonly used exhibit several issues; in particular, they only reduce the effect of the error, and never eliminate it. \ In this technical report, we propose a technique to effectively eliminate measurement errors and obtain a robust statistical estimate of execution time or duration of events in a program. The technique is simple to implement, yet it entirely eliminates the systematic (non-random) component of the measurement error, as opposed to simply reduce it. Experimental results con rm the effectiveness of the proposed method.

This technical report is an extended version of the letter submitted to IEEE Embedded Systems Letters on May 2016, revised version submitted on November 2016, accepted for publication on January 2017.

}, author = {Carlos Moreno and Sebastian Fischmeister} } @article {292, title = {Accurate Measurement of Small Execution Times -- Getting Around Measurement Errors}, journal = {Embedded Systems Letters (ESL)}, year = {2017}, abstract = {

Engineers and researchers often require accurate measurements of small execution times or duration of events in a program. Errors in the measurement facility can introduce important challenges, especially when measuring small intervals. \ Mitigating approaches commonly used exhibit several issues; in particular, they only reduce the effect of the error, and never eliminate it. In this letter, we propose a technique to effectively eliminate measurement errors and obtain a robust statistical estimate of execution time or duration of events in a program. \ The technique is simple to implement, yet it entirely eliminates the systematic (non-random) component of the measurement error, as opposed to simply reduce it. Experimental results confirm the effectiveness of the proposed method.

}, author = {Carlos Moreno and Sebastian Fischmeister} } @inproceedings {294, title = {Debugging Behaviour of Embedded-Software Developers: An Exploratory Study}, booktitle = {IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC)}, year = {2017}, address = {Raleigh, USA}, abstract = {

Many researchers have studied the behaviour of successful developers\ while debugging desktop software. In this paper, we investigate the\ embedded-software debugging by intermediate programmers through an\ exploratory study. The bugs are semantic low-level errors, and the\ participants are students who completed a real-time operating systems\ course in addition to five other programming courses. We compare between the behaviour involved in successful debugging attempts versus\ 
unsuccessful ones. We describe some characteristics of smooth and \ successful debugging behaviour.

}, author = {Pansy Arafa and Daniel Solomon and Samaneh Navabpour and Sebastian Fischmeister} } @article {304, title = {Enabling Rapid Construction of Arrival Curves From Execution Traces}, journal = {IEEE Design \& Test}, volume = {PP}, year = {2017}, abstract = {

Arrival curves are a widely used abstraction for modeling temporal workloads in real-time systems. Multiple frameworks derived from Network Calculus theory operate over arrival curves to perform exhaustive analysis of real-time systems at design-time. While there is extensive literature targeting the manipulation of pre-computed generic curves, the computational challenges for obtaining curves from actual execution traces remain overlooked. As complex heterogeneous real-time systems proliferate across multiple application domains, it is important to develop effective techniques for characterizing non-trivial system behaviors that cannot be predicted at design time. This paper presents a parallelizable algorithm for constructing empirical arrival curves from execution traces. By leveraging parallel hardware, the method enables constructing curves from traces with over two million events. Rapid construction of empirical arrival curves extends the application scope of wellestablished frameworks for real-time systems analysis, and also unveils new applications of these curves in anomaly detection and behavioral analysis.

}, doi = {10.1109/MDAT.2017.2771210}, author = {Gonzalo Carvajal and Mahmoud Salem and Nirmal Benann and Sebastian Fischmeister} } @inproceedings {291, title = {Fast and Energy-Efficient Digital Filters for Signal Conditioning in Low-Power Microcontrollers}, booktitle = {Design Automation Conference (DAC)}, year = {2017}, address = {Austin, USA}, abstract = {

Embedded systems often use digital filtering after analogto-digital conversion when signal conditioning is required. However, digital filters are computationally demanding, making them unsuitable for low-power microcontrollers.

In this paper, we propose a fast and energy-efficient digital filtering technique based on look-up tables. The novelty in our technique is the use of multiple small LUTs, with a novel way to combine them to reduce the quantization error. As an additional novelty element, we propose a new inputcentric efficient implementation, specific to LUT-based software filters. Experimental results confirm the technique\&$\#$39;s remarkable potential for speed as well as its energy efficiency.

}, doi = {10.1145/3061639.3062245}, author = {Carlos Moreno and Sebastian Fischmeister} } @inproceedings {296, title = {Intersert: Assertions on Distributed Process Interaction Sessions}, booktitle = {IEEE International Conference on Software Quality, Reliability \& Security (QRS)}, year = {2017}, address = {Prague, Czech Republic}, abstract = {

Program assertions typically operate on available program state such as global and local variables. To support sophisticated assert statements such as invariants on control flow or inter-process communication patterns, developers must design and maintain supporting infrastructure. It is non-obvious how to realize this infrastructure: how to maintain the data, how to access it, how to use it in assertions, how to keep the overhead low enough for embedded systems, and how to manage assertions across a distributed system.

This work demonstrates the utility of assertions on interaction history among distributed system components and solves the challenges of efficiently maintaining interaction data while providing an expressive interface for assertions. Our toolchain enables developers to program assertions on interaction history written in regular expressions that incorporate inter-process and inter-thread behavior amongst multiple components in a distributed system. We demonstrate that the interaction tracking and property verification systems incur negligible overhead, measured with several benchmarks. This work discusses our toolchain with a real-world safety-critical embedded system.

}, author = {Zack Newsham and Augusto Oliveira and JC Petkovich and Ahmad Rehman and G.M. Tchamgoue and Sebastian Fischmeister} } @inproceedings {299, title = {Mining Specifications using Nested Words}, booktitle = {Proceedings of the 6th International Workshop on Software Mining}, year = {2017}, address = {Urbana-Champaign, USA}, abstract = {

Parameter mining of traces identifies formal properties that describe a program\’s dynamic behaviour. These properties are useful for developers to understand programs, to identify defects, and, in general, to reason about them. The dynamic behavior of programs typically follows a distinct pattern of calls and returns. Prior work uses general logic to identify properties from a given set of templates. Consequently, either the properties are inadequate since the logic is not expressive enough, or the approach fails to scale due to the generality of the logic. \ This paper uses nested words and nested word automata that are especially well suited for describing the dynamic behaviour of a program. Specifically, these nested words can describe pre/post conditions and inter-procedural data-flow and have constant memory requirements.
We propose a framework for mining properties that are in the form of nested words from system traces. As a part of the framework, we propose a novel scalable algorithm optimized for mining nested words. The framework is evaluated on traces from real world applications.

}, author = {Apurva Narayan and Nirmal Benann and Sebastian Fischmeister} } @inproceedings {300, title = {Mining Temporal Intervals from Real-time System Traces}, booktitle = {6th International Workshop on Software Mining}, year = {2017}, address = {Champaign, USA}, abstract = {

We introduce a novel algorithm for mining temporal intervals from real-time system traces with linear complexity using passive, black-box learning. Our interest is in mining nfer specifications from spacecraft telemetry to improve human and machine comprehension. Nfer is a recently proposed formalism for inferring event stream abstractions with a rule notation based on Allen Logic. The problem of mining Allen\&$\#$39;s relations from a multivariate interval series is well studied, but little attention has been paid to generating such a series from symbolic time sequences such as system traces. We propose a method to automatically generate an interval series from real-time system traces so that they may be used as inputs to existing algorithms to mine nfer rules. Our algorithm has linear runtime and constant space complexity in the length of the trace and can mine infrequent intervals of arbitrary length from incomplete traces. The paper includes results from case studies using logs from the Curiosity rover on Mars and two other realistic datasets.

}, author = {Sean Kauffman and Sebastian Fischmeister} } @article {297, title = {Non-Intrusive Runtime Monitoring Through Power Consumption to Enforce Safety and Security Properties in Embedded Systems}, journal = {Formal Methods in Software Design (FMSD)}, year = {2017}, abstract = {

The increasing complexity and connectivity of modern em-
bedded systems highlight the importance of runtime monitoring to en-
sure correctness and security. This poses a significant challenge, since
monitoring tools can break extra-functional requirements such as timing
constraints. Non-intrusive program tracing through side-channel analy-
sis techniques have recently appeared in the literature and constitute
a promising approach. Existing techniques, however, exhibit important
limitations.
In this paper, we present a novel technique for non-intrusive program
tracing from power consumption, based on a signals and system analy-
sis approach: we view the power consumption signal as the output of a
system with the power consumption of training samples as input. Using
spectral analysis, we compute the impulse response to identify the sys-
tem; the intuition is that for the correct training sample, the system will
appear close to a system that outputs a shifted copy of the input signal,
for which the impulse response is an impulse at the position correspond-
ing to the shift. We also use the Control Flow Graph (CFG) from the
source code to constrain the classifier to valid sequences only, leading to
substantial performance improvements over previous works.
Experimental results confirm the effectiveness of our technique and show
its applicability to runtime monitoring. The experiments include tracing
programs that execute randomly generated sequences of functions as well
as tracing a real application developed with SCADE. The experimental
evaluation also includes a case-study as evidence of the usability of our
technique to detect anomalous execution through runtime monitoring.

}, author = {Carlos Moreno and Sebastian Fischmeister} } @inproceedings {295, title = {Periodic Task Mining in Embedded System Traces}, booktitle = {IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2017}, pages = {331-340}, address = {Pittsburgh, USA}, abstract = {

Modern systems are growing in complexity beyond deep comprehension of developers. Increasing difficulties of keeping software projects on schedule and increasing recall rates are symptoms of this development. \ Consequently, developers need new methods and tools to build embedded systems, such as tools that dynamically analyze systems and recover comprehensible specifications of particular aspects. In this paper, we address the problem of discovering temporal behavior of real-time systems by mining periodic task sets and their temporal characteristics from system execution traces. We leverage the periodic nature of real-time systems to achieve this goal in an automatic way.
We propose PeTaMi (PEriodic TAsk MIner) - a novel approach and a tool to mine periodic tasks along with information on their periods and response time profiles from execution traces of real-time systems. PeTaMi embraces an important observation we make about operation of periodic tasks: their individual jobs are usually followed by intervals of task inactivity of a considerable duration. We evaluated PeTaMi on two case studies (unmanned aerial vehicle and a commercial car in operation) using traces containing tens of thousands of recorded execution events.

}, doi = {10.1109/RTAS.2017.5}, author = {Oleg Iegorov and Reinier Torres and Sebastian Fischmeister} } @inproceedings {286, title = {Perphecy: Performance Regression Test Selection Made Simple but Effective}, booktitle = {Proc. of the 10th IEEE International Conference on Software Testing, Verification and Validation (ICST)}, year = {2017}, address = {Tokyo, Japan}, abstract = {

Developers of performance sensitive production software are in a dilemma: performance regression tests are too costly to run at each commit, but skipping the tests delays and complicates performance regression detection. Ideally, developers would have a system that predicts whether a given commit is likely to impact performance and suggests which tests to run to detect a potential performance regression. Prior approaches towards this problem require static or dynamic analyses that limit their generality and applicability. This paper presents an approach that is simple and general, and that works surprisingly well for real applications.

}, author = {Augusto Oliveira and Sebastian Fischmeister and Amer Diwan and Matthias Hauswirth and Peter Sweeney} } @inproceedings {293, title = {QDIME: QoS-aware Dynamic Binary Instrumentation}, booktitle = {IEEE International Symposium on the Modeling, Analysis, and Simulation of Computer and Telecommunication Systems}, year = {2017}, address = {Banff, Canada}, abstract = {

Software systems with quality of service (QoS), such as database management systems and web servers, are ubiquitous. Such systems must meet strict performance requirements. Instrumentation is a useful technique for the analysis and debugging of QoS systems. Dynamic binary instrumentation (DBI) extracts runtime information to comprehend system\&$\#$39;s behavior and detect performance bottlenecks. However, existing DBI tools are intrusive; adding unacceptable delay to the program execution. Such delay alters the performance requirements and degrades the overall quality and the user experience of the system. Moreover, the delay may change the system behavior, thus, producing misleading run-time information.\ 
\ This paper presents QDIME, a QoS-aware dynamic binary instrumentation technique that respects system\&$\#$39;s performance requirements. QDIME takes a user-defined QoS threshold as an input and periodically gathers QoS feedback from the system under analysis to decide its instrumentation budget.\ 
\ We implemented QDIME on top of PIN, a popular DBI framework. We evaluated QDIME with Gzip, MySQL server, Apache HTTP server, and Redis. The experiments show that QDIME respects the user-defined QoS threshold and, thus, improves the performance of the monitored application by manifolds. QDIME is able to provide up to 100\% instrumentation coverage with an average of 92\% when compared to PIN. Moreover, QDIME reduces the slow-down factor of the instrumented application by 1.41, 5.67, and 10.26 folds for Sys-trace, Call-trace, and Branch-profile respectively. A release of QDIME is available for down- load at https://github.com/pansy-arafa/qdime

}, author = {Pansy Arafa and Guy M. Tchamgoue and Hany Kashif and Sebastian Fischmeister} } @inproceedings {269, title = {Runtime Verification of LTL on Lossy Traces}, booktitle = {32nd ACM Symposium on Applied Computing (SAC)}, year = {2017}, pages = {1379-1386}, address = {Marrakech, Morocco}, abstract = {

Runtime verification techniques mostly assume the existence of complete execution traces. However, real-world systems often produce lossy traces due to network issues, partial instrumentation, sampling, and logging failures. A few verification techniques have recently emerged to handle systems with incomplete traces. Some of these techniques sacrifice soundness and may produce imprecise verdicts. The others depend on the recovery of lost events for a sound and meaningful verdict. In this paper, we present an offine algorithm that identifies whether an Ltl (Linear Temporal Logic) formula can be soundly monitored in the presence of a transient loss of events in a trace and constructs a monitor accordingly. More, we introduce the concept of monotonicity to express the persistence of the verdicts of a loss-tolerant monitor regardless of the recovery of the lost events. \ Our evaluation demonstrates the applicability, effciency and practicality of the technique on common LTL patterns, but also on traces from Google Clusters and MPlayer.

}, doi = {10.1145/3019612.3019827}, author = {Yogi Joshi and Guy M. Tchamgoue and Sebastian Fischmeister} } @inproceedings {267, title = {On the Security of Safety-Critical Embedded Systems: Who Watches the Watchers? Who Reprograms the Watchers?}, booktitle = {International Conference on Information Systems Security and Privacy (ICISSP)}, year = {2017}, note = {

(Associated poster nominated for Best Poster Award)

}, address = {Porto, Portugal.}, abstract = {

The increased level of connectivity makes security an essential aspect to ensure that safety-critical embedded systems deliver the level of safety for which they were designed. However, embedded systems designers face unique technological and economics challenges when incorporating security into their products. In this paper, we focus on two of these challenges unique to embedded systems, and propose novel approaches to address them. We first deal with the difficulties in successfully implementing runtime monitoring to ensure correctness in the presence of security threats. We highlight the necessity to implement runtime monitors as physically isolated subsystems, preferably with no (direct) connectivity, and we propose the use of program tracing through power consumption to this end. A second critical aspect is that of remote firmware upgrades: this is an essential mechanism to ensure the continuing security of a system, yet the mechanism itself can introduce severe security vulnerabilities. We propose a novel approach to ensure secure remote upgrades and sketch the details of an eventual implementation. It is our goal and hope that the computer security and embedded systems communities will discuss and evaluate the ideas that we present in this paper, to assess their effectiveness and applicability in practice.

}, author = {Carlo Moreno and Sebastian Fischmeister} } @inproceedings {288, title = {System Call Logs with Natural Random Faults: Experimental Design and Application}, booktitle = {Silicon Errors in Logic -- System Effects (SELSE)}, year = {2017}, address = {Boston, USA}, abstract = {

In this paper we present a large dataset for use in embedded systems research which has been gathered from a realistic development environment operating in the path of an accelerated neutron beam. The dataset contains traces with events from a real-time operating system as well as user events from a safety critical application. All data is carefully timestamped and in human understandable form. We present two use cases for this dataset: mining timed regular expressions to extract system specifications from clean and possibly anomalous data generated during the operation of the neutron beam, and runtime monitoring to extract information from traces with incomplete information.

}, author = {Apurva Narayan and Sean Kauffman and Jack Morgan and Guy Martin Tchamgoue and Yogi Joshi and Sebastian Fischmeister and Chris Hobbs} } @inproceedings {289, title = {Transferring Performance Prediction Models Across Different Hardware Platforms}, booktitle = {International Conference on Performance Engineering (ICPE)}, year = {2017}, address = {L{\textquoteright}Aquila, Italy}, abstract = {

Many software systems provide configuration options relevant to users, which are often called features. Features influence functional properties of software systems as well as non-functional ones, such as performance and memory consumption. Researchers have successfully demonstrated the correlation between feature selection and performance. \ However, the generality of these performance models across different hardware platforms has not yet been evaluated.

We propose a technique for enhancing generality of performance models across different hardware environments using linear transformation. Empirical studies on three real-world software systems show that our approach is computationally efficient and can achieve high accuracy (less than 10\% mean relative error) when predicting system performance across 23 different hardware platforms. Moreover, we investigate why the approach works by comparing performance distributions of systems and structure of performance models across different platforms.

}, author = {Pavol Valov and Jean-Christophe Petkovich and Jianmei Guo and Sebastian Fischmeister and Czarnecki, Krzysztof} } @inproceedings {298, title = {TREM: A Tool for Mining Timed Regular Specifications from System Traces}, booktitle = {Proceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering}, year = {2017}, address = {Urbana-Champaign, USA}, abstract = {

Software specifications are useful for software vali- dation, model checking, runtime verification, debugging, monitoring, etc. In context of safety-critical real-time systems, temporal properties play an important role. However, temporal properties are rarely present due to the complexity and evolutionary nature of software systems.
We propose Timed Regular Expression Mining (TREM) a hosted tool for specification mining using timed regular expressions (TREs). It is designed for easy and robust mining of dominant temporal properties. TREM uses an abstract structure of the property; the framework constructs a finite state machine to serve as an acceptor. TREM is scalable, easy to access/use, and platform independent specification mining framework. The tool is tested on industrial strength software system traces such as the QNX real-time operating system using traces with more than 1.5 Million entries. The tool demonstration video can be accessed here: youtu.be/cSd_aj3_LH8

}, author = {Lukas Schmidt and Apurva Narayan and Sebastian Fischmeister} } @inproceedings {283, title = {Accelerated Runtime Verification of LTL Specifications with Counting Semantics}, booktitle = {International Conference on Runtime Verification}, year = {2016}, pages = {251--267}, address = {Madrid, Spain}, doi = {10.1007/978-3-319-46982-9_16}, author = {Ramy Medhat and Borzoo Bonakdarpour and Sebastian Fischmeister and Yogi Joshi} } @inproceedings {253, title = {Anomaly Detection Using Inter-Arrival Curves for Real-time Systems}, booktitle = {International Euromicro Conference on Real-Time Systems (ECRTS)}, year = {2016}, address = {Toulouse, France}, abstract = {

Real-time embedded systems are a significant class of applications, poised to grow even further as automated vehicles and the Internet of Things become a reality. An important problem for these systems is to detect anomalies during operation. \ Anomaly detection is a form of classification, which can be driven by data collected from the system at execution time. \ We propose inter-arrival curves as a novel analytic modelling technique for discrete event traces. Our approach relates to the existing technique of arrival curves and expands the technique to anomaly detection. Inter-arrival curves analyze the behaviour of events within a trace by providing upper and lower bounds to their inter-arrival occurrence. We exploit inter-arrival curves in a classification framework that detects deviations within these bounds for anomaly detection. Also, we show how inter-arrival curves act as good features to extract recurrent behaviour that these systems often exhibit. We demonstrate the feasibility and viability of the fully implemented approach with an industrial automotive case study (CAN traces) as well as a deployed aerospace case study (RTOS kernel traces).

}, author = {Mahmoud Salem and Mark Crowley and Sebastian Fischmeister} } @article {276, title = {DataMill: a distributed heterogeneous infrastructure for robust experimentation}, journal = {Software Practice and Experience}, volume = {46}, year = {2016}, pages = {29}, abstract = {

Empirical systems research is facing a dilemma. Minor aspects of an experimental setup can have a significant impact on its associated performance measurements and potentially invalidate conclusions drawn from them. Examples of such influences, often called hidden factors, include binary link order, process environment size, compiler generated randomized symbol names, or group scheduler assignments. The growth in complexity and size of modern systems will further aggravate this dilemma, especially with the given time pressure of producing results. How can one trust any reported empirical analysis of a new idea or concept in computer science? DataMill is a community-based services-oriented open benchmarking infrastructure for rigorous performance evaluation. DataMill facilitates producing robust, reliable, and reproducible results. The infrastructure incorporates the latest results on hidden factors and automates the variation of these factors. DataMill is also of interest for research on performance evaluation. The infrastructure supports quantifying the effect of hidden factors, disseminating the research results beyond mere reporting. It provides a platform for investigating interactions and composition of hidden factors. This paper discusses experience earned through creating and using an open benchmarking infrastructure. Multiple research groups participate and have used DataMill. Furthermore, DataMill has been used for a performance competition at the International Conference on Runtime Verification (RV) 2014 and is currently hosting the RV 2015 competition. This paper includes a summary of our experience hosting the first RV competition.

}, doi = {10.1002/spe.2382}, author = {Jean-Christophe Petkovich and Augusto Oliveira and Yuguang Zhang and Thomas Reidemeister and Sebastian Fischmeister} } @inproceedings {287, title = {Efficient mode changes in multi-mode systems}, booktitle = {International Conference on Computer Design (ICCD)}, year = {2016}, pages = {592--599}, abstract = {

Multi-mode systems work in configurations, but face the challenge of ensuring timing guarantees during mode changes. In a multi-mode system, a mode-change request occurs when the system wants to operate in a new mode, but is already running in one. One mode may include some tasks that are same as that of another mode. Therefore, the new mode may have tasks that are same as the old mode. Changing modes in such a way to skip some already completed tasks can decrease the workload of the new mode. Traditional protocols for changing modes always look forward in time to schedule tasks, although using already completed tasks may avoid re-executing them in the new mode. Reusing common tasks reduces the time to re-execute them while switching modes. In this paper, we introduce the concept and design considerations for a mode-change technique that may use completed tasks stored in checkpoints to avoid unnecessary re-execution and facilitate faster execution of new mode tasks. Through an example case-study, experimental results demonstrate that the overhead of using checkpoints is low, and using rollback facilitates faster execution of new mode tasks if completed tasks stored in checkpoints can be reused.

}, doi = {10.1109/ICCD.2016.7753345}, author = {Akramul Azim and Sebastian Fischmeister} } @inproceedings {245, title = {Efficient Program Tracing and Monitoring Through Power Consumption -- With A Little Help From The Compiler}, booktitle = {Proc. of Design, Automation, and Test (DATE)}, year = {2016}, address = {Dresden, Germany}, abstract = {

Ensuring correctness and enforcing security are growing concerns given the complexity of modern connected devices and safety-critical systems. A promising approach is non-intrusive runtime monitoring through reconstruction of program execution traces from power consumption measurements. \ This can be used for verification, validation, debugging, and security purposes.

In this paper, we propose a framework for increasing the effectiveness of power-based program tracing techniques. These systems determine the most likely block of source code that produced an observed power trace (CPU power consumption as a function of time). Our framework maximizes distinguishability between power traces for different code blocks. To this end, we provide a special compiler optimization stage that reorders intermediate representation (IR) and determines the reorderings that lead to power traces with highest distances between each other, thus reducing the probability of misclassification. Our work includes an experimental evaluation, using LLVM for an ARM architecture. Experimental results confirm the effectiveness of our technique.

}, author = {Moreno, Carlos and Kauffman, Sean and Fischmeister, Sebastian} } @article {246, title = {Integrating Dynamic-TDMA Communication Channels into COTS Ethernet Networks}, journal = {IEEE Transactions on Industrial Informatics}, volume = {12}, year = {2016}, pages = {1806-1816}, abstract = {

Real-time Ethernet is widely recognized for its potential to provide a unified communication backbone for nextgeneration highly-heterogeneous distributed systems. However, most of the research in the area has traditionally focused on formal models and analyzes and tends to omit the associated implementation challenges. This gap between theory and practice prevents practical validation of the claimed properties, which in turn hinders the pace of innovation, development of new standards, and adoption of the technology in industrial settings. This paper aims at narrowing the existing gap by characterizing a comprehensive open-source framework that explores emerging challenges in real-time networking, including the provision of ultra-low latency and jitter,\ dynamic\ bandwidth management, and segmentation within large networks. This work integrates research on formal abstractions for\ dynamic-TDMA arbitration and technological insights from modern hardware infrastructure, and uses a representative distributed video processing casestudy to provide experimental and reproducible evidence of the achieved properties in multi-hop Ethernet settings. By leveraging readily available technology and an open-source design, the proposed framework facilitates further exploration and experimental testing and validation of properties that are beyond the scope of current commercial technologies, encouraging evidencebased discussions to accelerate development and adoption of nextgeneration standards for industrial networking.

}, doi = {10.1109/TII.2016.2535255}, author = {Carvajal, Gonzalo and Araneda, Luis and Wolf, Alejandro and Figueroa, Miguel and Fischmeister, Sebastian} } @inproceedings {268, title = {Lessons Learned on Assumptions and Scalability with Time-Aware Instrumentation}, booktitle = {International Conference on Embedded Software (EMSOFT)}, year = {2016}, pages = {1 - 7}, address = {Pittsburgh, USA}, abstract = {

Software instrumentation is a key technique in many stages of the development process. Instrumentation is particularly important for profiling, debugging, performance evaluation, and security analysis of real-time and embedded systems. Unfortunately, typical software-based instrumentation methods, while useful to extract high-level information from programs, concentrate on preserving only logical correctness and are thus inadequate for time-sensitive applications for which timing must also be preserved. \ Time-aware instrumentation is a new view on code instrumentation, one that considers extra-functional properties and specifically timing constraints of instrumented programs. Time-aware instrumentation enables instrumenting software systems while still guaranteeing their timing requirements. This paper summarizes the work on time-aware instrumentation and highlights the lessons learned on assumptions and scalability. Specifically, it shows how strict assumptions enable a strong formal model at the expense of applicability. Subsequent relaxing of assumptions then permits scaling the concept and applying it to large real-word applications with millions lines of code. We believe that these lessons may help steer other research projects in the systems area.

}, doi = {10.1145/2968478.2975584}, author = {Guy Martin Tchamgoue and Sebastian Fischmeister} } @inproceedings {256, title = {Mining Timed Regular Expressions from System Traces}, booktitle = {Proceedings of the 5th International Workshop on Software Mining}, year = {2016}, pages = {3 - 10}, address = {Singapore}, abstract = {

Dynamic behavior of a program can be assessed through examination of events emitted by the program during execution. Temporal properties define the order of occurrence and timing constraints on event occurrence. Such specifica- tions are important for safety-critical real-time systems for which a delayed response to an emitted event may lead to a fault in the system. Since temporal properties are rarely specified for programs and due to the complexity of the formalisms, it is desirable to suggest properties by extracting them from traces of program execution for testing, verification, anomaly detection, and debugging purposes.

We propose a framework for automatically mining proper- ties that are in the form of timed regular expressions (TREs) from system traces. Using an abstract structure of the property, the framework constructs a finite state machine to serve as an acceptor. As part of the framework, we propose two novel algorithms optimized for mining general TREs and a fragment without negation. The framework is evaluated on industrial strength safety-critical real-time applications (a deployed autonomous hexacopter system and a commercial vehicle in operation) using traces with more than 1 Million entries. Our framework is open source and available online: https://bitbucket.org/sfischme/tre-mining

}, doi = {10.1145/2975961.2975962}, author = {Cutulenco, Greta and Joshi, Yogi and Narayan, Apurva and Fischmeister, Sebastian} } @inproceedings {255, title = {Non-Intrusive Runtime Monitoring Through Power Consumption: A Signals and System Analysis Approach to Reconstruct the Trace}, booktitle = {Proc. of the International Conference on Runtime Verification (RV)}, year = {2016}, address = {Madrid, Spain}, abstract = {

The increasing complexity and connectivity of modern embedded systems highlight the importance of runtime monitoring to ensure correctness and security. This poses a significant challenge, since monitoring tools can break extra-functional requirements such as timing constraints. Non-intrusive program tracing through side-channel analysis techniques have recently appeared in the literature and constitute a promising approach. Existing techniques, however, exhibit important limitations.
In this paper, we present a novel technique for non-intrusive program tracing from power consumption, based on a signals and system analysis approach: we view the power consumption signal as the output of a system with the power consumption of training samples as input. Using spectral analysis, we compute the impulse response to identify the system; the intuition is that for the correct training sample, the system will appear close to a system that outputs a shifted copy of the input signal, for which the impulse response is an impulse at the position corresponding to the shift. We also use the Control Flow Graph (CFG) from the source code to constrain the classifier to valid sequences only, leading to substantial performance improvements over previous works.
Experimental results confirm the effectiveness of our technique and show its applicability to runtime monitoring. The experiments include tracing programs that execute randomly generated sequences of functions as well as tracing a real application developed with SCADE. The experimental evaluation also includes a case-study as evidence of the usability of our technique to detect anomalous execution through runtime monitoring.

}, author = {Moreno, Carlos and Fischmeister, Sebastian} } @article {275, title = {Path Selection for Real-Time Communication on Priority-Aware NoCs}, journal = {ACM Transactions on Design Automation of Electronic Systems }, volume = {21}, year = {2016}, pages = {1-25}, doi = {10.1145/2866572}, author = {Hany Kashif and Hiren Patel and Sebastian Fischmeister} } @inproceedings {254, title = {Static Transformation of Power Consumption for Software Attestation}, booktitle = {IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)}, year = {2016}, address = {Daegu, South Korea}, abstract = {

Software attestation seeks to verify the authenticity
of a system without the aid of trusted hardware, and has
important applications in the field of security. Such attestation
schemes are of particular interest in the embedded domain, where
simplicity and limited resources constrain more complex security
solutions. At the same time, these properties enable attestation
approaches that rely on predictable side-effects. Most software
attestation schemes aim to verify the integrity of memory using
a combination of cryptographic schemes, internal side-effects
like TLB misses, and known timing constraints. However, little
attention has been paid to leveraging non-traditional side-effects,
in particular, externally observable side-effects such as power
consumption.


In this paper we introduce a method for software attestation
using power consumption as the side-effect. We show how to
circumvent the undecidable nature of program execution for
this purpose and present a static compiler transformation which
implements the technique. Our approach is less intrusive than
traditional software attestation because the system does not
require interruption to compute a cryptographic checksum. It
is particularly well suited to real-time systems where consistent
timing is more important than speed.

}, author = {Kauffman, Sean and Moreno, Carlos and Fischmeister, Sebastian} } @article {274, title = {The Truth, The Whole Truth, and Nothing But the Truth: A Pragmatic Guide to Assessing Empirical Evaluations}, journal = {ACM Transactions on Programming Languages and Systems (TOPLAS)}, volume = {38}, year = {2016}, pages = {1-15}, abstract = {

An unsound claim can misdirect a field, encouraging the pursuit of unworthy ideas and the abandonment of promising ideas. An inadequate description of a claim can make it difficult to reason about the claim, for example, to determine whether the claim is sound. Many practitioners will acknowledge the threat of unsound claims or inadequate descriptions of claims to their field. We believe that this situation is exacerbated, and even encouraged, by the lack of a systematic approach to exploring, exposing, and addressing the source of unsound claims and poor exposition.

This article proposes a framework that identifies three sins of reasoning that lead to unsound claims and two sins of exposition that lead to poorly described claims and evaluations. Sins of exposition obfuscate the objective of determining whether or not a claim is sound, while sins of reasoning lead directly to unsound claims.

Our framework provides practitioners with a principled way of critiquing the integrity of their own work and the work of others. We hope that this will help individuals conduct better science and encourage a cultural shift in our research community to identify and promulgate sound claims.

}, doi = {10.1145/2983574}, author = {Stephen M. Blackburn and Amer Diwan and Matthias Hauswirth and Peter Sweeney and Jose Nelson Amaral and Tim Brecht and Lubomir Bulej and Cliff Click and Lieven Eeckhout and Sebastian Fischmeister and Daniel Frampton and Laurie Hendren and Michael Hind and Antony Hosking and Richard Jones and Tomas Kalibera and Nathan Keynes and Nathaniel Nystrom and Andreas Zeller} } @inproceedings {227, title = {Exp-HE: A Family of Fast Exponentiation Algorithms Resistant to SPA, Fault, and Combined Attacks}, booktitle = {International Conference on Embedded Software (EMSOFT)}, year = {2015}, author = {Moreno, Carlos and Hasan, M. Anwar and Fischmeister, Sebastian} } @inproceedings {226, title = {A Framework for Mining Hybrid Automata from Input/Output Traces}, booktitle = {International Conference on Embedded Software (EMSOFT)}, year = {2015}, author = {Ramy Medhat and Ramesh S. and Borzoo Bonakdarpour and Sebastian Fischmeister} } @inproceedings {229, title = {Generation of Communication Schedules Using Component Interfaces}, booktitle = {Proc. of the International Conference on Emerging Technologies and Factory Automation (ETFA)}, year = {2015}, address = {Luxembourg}, abstract = {

With the growing demand in embedded systems, safety and non-safety critical parts are integrated together although guaranteeing safety is a hard problem to tackle due to the complexity of possible interactions between components involving communication. However, it is sufficiently recognized that separation of computation and communication can reduce the complexity of guaranteeing safety involved in interactions between components. In this work, we propose to use component interfaces derived from periodic resource supplies that can meet the demand of components experiencing bounded delays. The advantage of using interfaces is to provide minimal information of components without requiring the entire task specifications to generate a multi-mode communication schedule. We use integer linear programming to find assignments in generating schedules that are guaranteed to have low average mode change delay. A video monitoring case study demonstrates the advantages on using our approach in generating communication schedules.

}, author = {Akramul Azim and Rodolfo Pellizzoni and Sebastian Fischmeister} } @inproceedings {216, title = {Instrumentation and Preservation of Extra-functional Properties of Simulink Models}, booktitle = {Proceedings of the Symposium on Theory of Modeling and Simulation - DEVS Integrative M\&S Symposium}, year = {2015}, address = {Alexandria, USA}, author = {Joachim Denil and Hany Kashif and Pansy Arafa and Hans Vangheluwe and Sebastian Fischmeister} } @inproceedings {228, title = {Performance Prediction upon Toolchain Migration in Model-Based Software}, booktitle = {International Conference on Model Driven Engineering Languages and Systems (MODELS)}, year = {2015}, pages = {302 - 311}, address = {Ottawa, Canada}, abstract = {

Changing the development environment can have severe impacts on the system behavior such as the execution-time performance. Since it can be costly to migrate a software application, engineers would like to predict the performance parameters of the application under the new environment with as little effort as possible. In this paper, we concentrate on model-driven development and provide a methodology to estimate the execution-time performance of application models under different toolchains. Our approach has low cost compared to the migration effort of an entire application. As part of the approach, we provide methods for characterizing model-driven applications, an algorithm for generating application-specific microbenchmarks, and results on using different methods for estimating the performance. In the work, we focus on SCADE as the development toolchain and use a Cruise Control and a Water Level application as case studies to confirm the technical feasibility and viability of our technique.

}, doi = {10.1109/MODELS.2015.7338261}, author = {Ketata, Aymen and Moreno, Carlos and Fischmeister, Sebastian and Liang, Jia and Czarnecki, Krzysztof} } @inproceedings {224, title = {Predicting SAT Solver Performance on Heterogeneous Hardware}, booktitle = {Proceedings of the Workshop on the Pragmatics of SAT at the International Conference on Theory and Applications of Satisfiability Testing (SAT)}, year = {2015}, address = {Austin, USA}, author = {Newsham, Zack and Ganesh, VIjay and Fischmeister, Sebastian} } @article {242, title = {Runtime Monitoring of Cyber-Physical Systems Under Timing and Memory Constraints}, journal = {ACM Transactions on Embedded Computing Systems (TECS)}, volume = {14}, year = {2015}, pages = {79}, abstract = {

The goal of\ runtime monitoring\ is to inspect the well-being of a system by employing a\ monitor process\ that reads the state of the system during execution and evaluates a set of properties expressed in some specification language. The main challenge in runtime monitoring is dealing with the costs imposed in terms of resource utilization. In the context of cyber-physical systems, it is crucial for a software monitoring solution to be\ time predictable\ to improve scheduling, as well as support composition of monitoring solutions with an overall predictable behavior. Moreover, a small memory footprint is often required in components of cyber-physical systems, especially in deeply embedded systems. In this article, we propose a novel control-theoretic software monitoring solution for coordinating time predictability and memory utilization in runtime monitoring of systems that interact with the physical world. The controllers attempt to reduce monitoring jitter and maximize memory utilization while simultaneously ensuring the soundness of evaluation of properties. For systems where multiple properties are required to be monitored simultaneously, we construct a buffer sharing mechanism in which controllers dynamically share the memory space to negate the effect of bursts of environment actions, thus reducing jitter due to transient high loads.

To validate our design choices, we present three case studies: (1) a Bluetooth mobile payment system, which shows a sporadic rate of events during peak hours; (2) a laser beam stabilizer for target tracking, and (3) a monitoring system for air/fuel ratio in a car engine exhaust and the CAM inlet position in the engine\’s cylinders. The experimental results of the case studies demonstrate up to 40\% improvement in time predictability of the monitoring solution when compared to a basic event-triggered approach. Moreover, memory utilization reaches an average of 90\% when using our dynamic buffer resizing mechanism.

}, doi = {10.1145/2744196}, author = {Ramy Medhat and Borzoo Bonakdarpour and Deepak Kumar and Sebastian Fischmeister} } @article {222, title = {Runtime Verification with Minimal Intrusion Through Parallelism}, journal = {Formal Methods in System Design}, year = {2015}, pages = {1-32}, abstract = {

Runtime verification is a monitoring technique to gain assurance about well-being of a program at run time. Most existing approaches use sequential monitors; i.e., when the state of the program with respect to an event of interest changes, the monitor interrupts the program execution, evaluates a set of logical properties, and finally resumes the program execution. In this paper, we propose a GPU-based method for design and implementation of monitors that enjoy two levels of parallelism: the monitor (1) works along with the program in parallel, and (2) evaluates a set of properties in a parallel fashion as well. Our parallel monitoring algorithms effectively exploit the many-core platform available in the GPU. In addition to parallel processing, our approach benefits from a true separation of monitoring and functional concerns, as it isolates the monitor in the GPU. Thus, our monitoring approach incurs minimal intrusion, as executing monitoring tasks take place in a different computing hardware from execution of the program under inspection. Our method is fully implemented for parametric and non-parametric 3-valued linear temporal logic. Our experimental results show significant reduction in monitoring overhead, monitoring interference, and power consumption due to leveraging the GPU technology. In particular, we observe that our parallel verification algorithms are indeed scalable.

}, keywords = {Formal methods, Parallel algorithms, Runtime monitoring, Temporal logic}, issn = {0925-9856}, doi = {10.1007/s10703-015-0226-3}, author = {Berkovich, Shay and Bonakdarpour, Borzoo and Fischmeister, Sebastian} } @inproceedings {225, title = {SATGraf: Visualizing the Evolution of SAT Formula Structure in Solvers}, booktitle = {International Conference on Theory and Applications of Satisfiability Testing (SAT)}, year = {2015}, month = {62 - 70}, publisher = {Springer}, organization = {Springer}, address = {Austin, USA}, abstract = {

In this paper, we present\ SATGraf, a tool for visualizing the evolution of the structure of a Boolean SAT formula in real time as it is being processed by a conflict-driven clause-learning (CDCL) solver. The tool is parametric, allowing the user to define the structure to be visualized. In particular, the tool can visualize the community structure of real-world Boolean satisfiability (SAT) instances and their evolution during solving. Such visualizations have been the inspiration for several hypotheses about the connection between community structure and the running time of CDCL SAT solvers, some which we have already empirically verified.\ SATGraf\ has enabled us in making the following empirical observations regarding CDCL solvers: First, we observe that the Variable State Independent Decaying Sum (VSIDS) branching heuristic consistently chooses variables with a high number of inter-community edges, i.e., high-centrality bridge variables. Second, we observe that the VSIDS branching heuristic and hence the CDCL search procedure is highly focused, i.e., VSIDS disproportionately picks variables from a few communities in the community-structure of input SAT formulas.

}, doi = {10.1007/978-3-319-24318-4_6}, author = {Newsham, Zack and Lindsay, William and Ganesh, VIjay and Liang, Jia Hui and Fischmeister, Sebastian and Czarnecki, Krzysztof} } @inproceedings {221, title = {Static Slack-Based Instrumentation of Programs}, booktitle = {Proc. of the 20th IEEE International Conference on Emerging Technologies \& Factory Automation (ETFA)}, year = {2015}, month = {September}, address = {Luxembourg}, doi = {10.1109/ETFA.2015.7301505}, author = {Hany Kashif and Johnson Thomas and Hiren Patel and Sebastian Fischmeister} } @inproceedings {223, title = {A Survey of Electrical and Electronic (E/E) Notifications for Motor Vehicles}, booktitle = {24th International Technical Conference on the Enhanced Safety of Vehicles (ESV)}, year = {2015}, pages = {1--15}, address = {Gothenburg, Sweden}, abstract = {

Modern motor vehicles are becoming increasingly dominated by electrical and electronics (E/E) systems. While this trend is clear, its implications are uncertain. In this paper, we investigate data on safety-related notifications from the United States, Canada, and Europe to analyze questions and trends related to E/E systems. The data analysis indicates that E/E systems are a growing issue for motor vehicle safety, that the time delay for E/E notifications is longer than that for other notifications, and that specific subsystems are more prone to E/E problems than others.

}, author = {Taylor T. Johnson and Raghunath Gannamaraju and Sebastian Fischmeister} } @inproceedings {189, title = {Bounding Buffer Space Requirements for Real-Time Priority-Aware Networks}, booktitle = {Proceedings of the Asia South Pacific Design Automation Conference (ASPDAC)}, year = {2014}, note = {

(Best Paper Candidate)

}, month = {January}, address = {SunTec, Singapore}, abstract = {

One implementation alternative for network interconnects in modern chip-multiprocessor systems is priority-aware arbitration networks. To enable the deployment of real-time applications to priority-aware networks, recent research proposes worst-case latency (WCL) analyses for such networks. Buffer space requirements in priority-aware networks, however, are seldom addressed. In this work, we bound the buffer space required for valid WCL analyses and consequently optimize router design for application specifications by computing the required buffer space at each virtual channel in priority-aware routers. In addition to the obvious advantage of bounding buffer space while providing valid WCL bounds, buffer space reduction decreases chip area and saves energy in priority-aware networks. Our experiments show that the proposed buffer space computation reduces the number of unfeasible implementations by 42\% compared to an existing buffer space analysis technique. It also reduces the required buffer space in priority-aware routers by up to 79\%.

}, author = {Hany Kashif and Hiren Patel} } @inproceedings {214, title = {D-RES: Correct Transitive Distributed Service Sharing}, booktitle = {Proc. of the Work-in-Progress Session of the Conference on Emerging Technologies and Factory Automation (ETFA), Work in Progress}, year = {2014}, address = {Barcelona, Spain}, abstract = {

With the growth of complexity in the embedded domain, the use of distributed systems to support multiple real-time applications has become commonplace. These applications may share processor and network resources, and real-time scheduling policies can guarantee that these applications do not interfere with each other?s ability to meet their temporal constraints. We believe that these applications should also be able to transparently share services and chains of services, without the coupling that such sharing typically implies. To solve this problem, we propose D-RES, a resource management system that guarantees temporal isolation between service sharing applications in a distributed system. D-RES transparently tracks which application uses which service, billing the correct application even in case of nested service calls. We implemented D-RES, and demonstrate its ability to isolate service-sharing applications even in case of overload.

}, author = {Augusto Oliveira and Akramul Azim and Sebastian Fischmeister and Ricardo Marau and Luis Almeida} } @article {188, title = {DTS: Dynamic TDMA Scheduling for Networked Control Systems}, journal = {Journal of Systems Architecture}, year = {2014}, pages = {194-205}, abstract = {

Networked Control Systems (NCSs) are pervasively applied in modern industry. With increasing functionalities, modern NCSs tend to have dynamic workload by holding a variety of applications via a shared network. To handle workload variations and provide performance guarantees, dynamic network scheduling scheme is highly desired in NCSs. In this paper, we propose a network scheduling scheme, referred to as DTS, that can make on-the-fly decisions to schedule the applications in NCSs. DTS aims at NCSs that use time-triggered network as shared medium and Time division multiple access (TDMA) as network access method. DTS dynamically changes the network accessing sequence of the applications in a way to provide optimal system performance and maintain control stability in NCSs. DTS adopts a decentralized schedule mechanism where each application can make its local schedule decision, enhancing the scalability of NCSs. Simulation results demonstrate the effectiveness of the proposed scheme by improving the network bandwidth and providing better system performance in NCS comparing with the existing time-triggered scheduling schemes.

}, issn = {1383-7621}, doi = {10.1016/j.sysarc.2013.10.012}, author = {Xi Chen and Akramul Azim and Xue Liu and Sebastian Fischmeister and Jun Ma} } @inproceedings {204, title = {em-SPADE: A Compiler Extension for Checking Rules Extracted from Processor Specifications}, booktitle = {SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems (LCTES)}, year = {2014}, pages = {105--114}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, abstract = {

Traditional compilers ignore processor specifications, thousands of pages of which are available for modern processors. To bridge this gap, em-SPADE analyzes processor specifications and creates processor-specific rules to reduce low-level programming er- rors. This work shows the potential of automatically analyzing processor- and other hardware specifications to detect low-level programming errors at compile time.

em-SPADE is a compiler extension to automatically detect software bugs in low-level programs. From processor specifications, a preprocessor extracts target-specific rules such as register use and read-only or reserved registers. A special LLVM pass then uses these rules to detect incorrect register assignments. Our experiments with em-SPADE have correctly extracted 652 rules from 15 specifications and consequently found 20 bugs in ten software projects. The work is generalizable to other types of specifications and shows the clear prospects of using hardware specifications to enhance compilers.

}, keywords = {compiler, embedded systems, llvm, static analysis}, isbn = {978-1-4503-2877-7}, doi = {10.1145/2597809.2597823}, url = {http://doi.acm.org/10.1145/2597809.2597823}, author = {Chaudhary, Sandeep and Fischmeister, Sebastian and Tan, Lin} } @inproceedings {187, title = {Generation of Communication Schedules for Multi-Mode Distributed Real-Time Applications}, booktitle = {Proceedings of Design, Automation and Test in Europe (DATE)}, year = {2014}, month = {March}, pages = {1--6}, address = {Grenoble, France}, abstract = {

A key problem in designing multi-mode real-time systems is the generation of schedules to reduce the complexities of transforming the model semantics to code. Moreover, distributed multi-mode applications are prone to suffer from delays incurred during mode changes. We therefore aim to generate communication schedules that have low average mode-change delay for multi-mode real-time distributed applications.

In this paper, we use optimisation constraints associated to timing requirements to generate state-based schedules for multi-mode communication systems, and illustrate the workflow for generating schedules from specifications through a real-time video monitoring case-study. Our experiments in the case-study demonstrate that schedules generated using the proposed method reduce the average mode-change delay in relation to a randomised algorithm and the well-known EDF scheduling algorithm.

}, author = {Akramul Azim and Gonzalo Carvajal and Rodolfo Pellizzoni and Sebastian Fischmeister} } @inproceedings {196, title = {How Much Does Memory Layout Impact Performance? A Wide Study}, booktitle = {Proceedings of the International Workshop on Reproducible Research Methodologies (REPRODUCE)}, year = {2014}, month = {February}, pages = {23{\textendash}28}, address = {Orlando, USA}, abstract = {

Memory layout variations are often cited as a threat to the reproducibility of computer performance experiments. Previous research has shown worst-case effects as large as 300\% of execution time, among other surprising cases. While these are worrying results, how frequent and widespread are these large effects?\  To answer this question, this paper presents a wide-scale evaluation of memory layout effects on the performance of a large subset of the SPECCPU2006 benchmark suite on a wide array of diverse machines. We find that on average, these benchmarks are not as susceptible to memory layout effects as the worst-case analysis found in the literature suggests. Finally, we re-execute our own experiment and demonstrate why the reproducibility of an experiment\&$\#$39;s result should not depend on its data being perfectly reproducible.

}, author = {Augusto Oliveira and Jean-Christophe Petkovich and Sebastian Fischmeister} } @inproceedings {203, title = {Impact of Community Structure on SAT Solver Performance}, booktitle = {17th International Conference on Theory and Applications of Satisfiability Testing (SAT)}, year = {2014}, note = {

(best student paper award)

}, pages = {252-268}, address = {Vienna, Austria}, abstract = {

Modern CDCL SAT solvers routinely solve very large industrial SAT instances in relatively short periods of time. It is clear that these solvers somehow exploit the structure of real-world instances. However, to-date there have been few results that precisely characterise this structure. In this paper, we provide evidence that the community structure of real-world SAT instances is correlated with the running time of CDCL SAT solvers. It has been known for some time that real-world SAT instances, viewed as graphs, have natural communities in them. A community is a sub-graph of the graph of a SAT instance, such that this sub-graph has more internal edges than outgoing to the rest of the graph. The community structure of a graph is often characterised by a quality metric called Q. Intuitively, a graph with high-quality community structure (high Q) is easily separable into smaller communities, while the one with low Q is not.

We provide three results based on empirical data which show that community structure of real-world industrial instances is a better predictor of the running time of CDCL solvers than other commonly considered factors such as variables and clauses. First, we show that there is a strong correlation between the Q value and Literal Block Distance metric of quality of conflict clauses used in clause-deletion policies in Glucose-like solvers. Second, using regression analysis, we show that the the number of communities and the Q value of the graph of real-world SAT instances is more predictive of the running time of CDCL solvers than traditional metrics like number of variables or clauses. Finally, we show that randomly-generated SAT instances with 0.05 \<= Q \<= 0.13 are dramatically harder to solve for CDCL solvers than otherwise.

}, author = {Newsham, Zack and Ganesh, VIjay and Fischmeister, Sebastian and Audemard, Gilles and Simon, Laurent} } @inproceedings {190, title = {Power-efficient Multiple Producer-Consumer}, booktitle = {IEEE 28th International Symposium on Parallel \& Distributed Processing (IPDPS)}, year = {2014}, pages = { 669--678}, address = {Phoenix, USA}, abstract = {

Power efficiency has been one of the main objectives of hardware design in the last two decades. However, with the recent explosion of mobile computing and the increasing demand for green data centers, software power efficiency has also risen to be an equally important factor. We argue that most classic concurrency control algorithms were designed in an era when power efficiency was not an important dimension in algorithm design. Such algorithms are applied to solve a wide range of problems from kernel-level primitives in operating systems to networking devices and web services. These primitives and services are constantly and heavily invoked in any computer system and by larger scale in networking devices and data centers. Thus, even a small change in their power spectrum can make a huge impact on overall power consumption in long periods of time.

This paper focuses on the classic producer-consumer problem. First, we study the power efficiency of different existing implementations of the producer-consumer problem. In particular, we present evidence that these implementations behave drastically differently with respect to power consumption. Secondly, we present a dynamic algorithm for the multiple producer-consumer problem, where consumers in a multicore system use learning mechanisms to predict the rate of production, and effectively utilize this prediction to attempt to latch onto previously scheduled CPU wake-ups.\  Such group latching results in minimizing the overall number of CPU wakeups and in effect, power consumption. We enable consumers to dynamically reserve more pre-allocated memory in cases where the production rate is too high. Consumers may compete for the extra space and dynamically release it when it is no longer needed. Our experiments show that our algorithm provides up to 40\% decrease in the number of CPU wakeups, and 30\% decrease in power consumption. We validate the scalability of our algorithm with an increasing number of consumers.

}, doi = {10.1109/IPDPS.2014.75}, author = {Medhat, Ramy and Bonakdarpour, Borzoo and Fischmeister, Sebastian} } @inproceedings {194, title = {Sacrificing a Little Space Can Significantly Improve Monitoring of Time-sensitive Cyber-physical Systems}, booktitle = {ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS)}, year = {2014}, pages = {115--126}, publisher = {IEEE}, organization = {IEEE}, address = {Berlin, Germany}, abstract = {

The goal of runtime verification is to inspect the correctness of a system by incorporating a monitor during its execution. Predictability of time distribution of monitor invocations and memory usage are two indicators of the quality of a monitoring solution, specially in cyber-physical systems, where the physical environment is a part of the system dynamics. In our previous work, we proposed a control-theoretic approach for coordinating time predictability and memory utilization in runtime verification of time-sensitive systems. To this end, we designed controllers that attempt to improve time predictability, while ensuring the soundness of verification by incorporating a maximally utilized bounded memory buffer that accumulates events.

Since the frequency of occurrence of environment actions in cyber-physical systems is not known a priori, the system may run into situations, where the buffer is full, but a monitor invocation has not yet been scheduled. In control theory, this is called the overshooting phenomenon, which inherently decreases time predictability.\  In this paper, we address the issue of overshoots, by employing a second controller that allows limited memory reservations to temporarily extend the size of the event buffer when the system is subject to bursts of environment actions. We apply our solution to the verification of the air/fuel ratio in an engine exhaust. The acceptable ratio varies depending on the driving circumstances, and monitoring that ratio is important to control emissions in a vehicle. A highly predictable monitor imposes uniform load on the engine control unit (ECU), thus, not negatively or sporadically affecting its control tasks. The experimental results exhibit two significant contributions: we (1) demonstrate the advantages of applying our approach to achieve low variation in the frequency of monitor invocations for verification, while maintaining maximum memory utilization, and (2) clearly illustrate that by negligible temporary increases in the size of the event buffer, the number of overshoots decreases significantly, which in turn substantially increases time predictability of runtime verification.

}, doi = {10.1109/ICCPS.2014.6843716}, author = {Medhat, Ramy and Kumar, Deepak and Bonakdarpour, Borzoo and Fischmeister, Sebastian} } @inproceedings {206, title = {SiPTA: Signal Processing for Trace-based Anomaly Detection}, booktitle = {Proc. of the International Conference on Embedded Software (EMSOFT)}, year = {2014}, month = {Oct.}, pages = {1--6}, address = {New Dehli, India}, abstract = {

Given a set of historic good traces, trace-based anomaly detection deals with the problem of determining whether or not a specific trace represents a normal execution scenario. Most current approaches mainly focus on application areas outside of the embedded systems domain and thus do not take advantage of the intrinsic properties of this domain.

This work introduces SiPTA, a novel technique for offline trace-based anomaly detection that utilizes the intrinsic feature of periodicity found in embedded systems. SiPTA uses signal processing as the underlying processing algorithm. The paper describes a generic framework for mapping execution traces to channels and signals for further processing. The classification stage of SiPTA uses a comprehensive set of metrics adapted from standard signal processing. The system is particularly useful for embedded systems, and the paper demonstrates this by comparing SiPTA with state-of-the-art approaches based on Markov Model and Neural Networks. The paper shows the technical feasibility and viability of SiPTA through multiple case studies using traces from a field-tested hexacopter, a mobile phone platform, and a car infotainment unit.\  In the experiments, our approach outperformed every other tested method.

}, author = {Mohammad Mehdi Zeinali Zadeh and Mahmoud Salem and Neeraj Kumar and Greta Cutulenco and Sebastian Fischmeister} } @article {195, title = {SLA: A Stage-level Latency Analysis for Real-time Communication in a Pipelined Resource Model}, journal = {IEEE Transactions on Computers}, volume = {PP}, year = {2014}, month = {April}, chapter = {1}, abstract = {

We present a communication analysis for hard real-time systems interconnects. The objective is to provide tight estimates on the worst-case communication latency between communicating processing elements that use a priority-aware communication medium for data transmission. The communication model consists of communication tasks transmitting data across a series of pipelined resources. The analysis incorporates interferences caused by multiple communication tasks requesting the pipelined resources, and it captures parallel transmission of data between multiple pipeline stages. We call this analysis a stage-level analysis. We evaluate the proposed analysis through simulation of synthetic benchmarks, and we apply the analysis to an instantiation of a platform proposed by Shi and Burns. Our experiments confirm that stage-level analysis provides tight upper-bounds when compared to previous work and improves schedulability by 34\%.

}, issn = {0018-9340}, doi = {10.1109/TC.2014.2315617}, author = {Hany Kashif and Sina Gholamian and Hiren Patel} } @article {215, title = {The use of mTags for mandatory security: a case study}, journal = {Software: Practice and Experience}, volume = {44}, year = {2014}, pages = {1511--1523}, keywords = {microkernels, research, security}, issn = {1097-024X}, doi = {10.1002/spe.2222}, url = {http://dx.doi.org/10.1002/spe.2222}, author = {Rehman, Ahmad and Oliveira, Augusto and Tripunitara, Mahesh and Fischmeister, Sebastian} } @inproceedings {156, title = {Atacama: An Open FPGA-based Platform for Mixed-Criticality Communication in Multi-segmented Ethernet Networks}, booktitle = {Proc. of the 21st IEEE International Symposium on Field-Programmable Custom Computing Machines (FCCM)}, year = {2013}, month = {April}, pages = {121--128}, abstract = {

Ethernet is widely recognized as an attractive networking technology for modern distributed real-time systems. However, standard Ethernet components require specific modifications and hardware support to provide strict latency guarantees necessary for safety-critical applications. Although this is a well-stated fact, the design of hardware components for real-time communication remains mostly unexplored. This becomes evident from the few solutions reporting prototypes and experimental validation, which hinders the consolidation of Ethernet in real-world distributed applications. This paper presents Atacama, the first open-source framework based on reconfigurable hardware for mixed-criticality communication in multi-segmented Ethernet networks. Atacamauses specialized modules for time-triggered communication of real-time data, which seamlessly integrate with a standard infrastructure using regular best-effort traffic. Atacama enables low and highly predictable communication latency on multi-segmented 1Gbps networks, easy optimization of devices for specific application scenarios, and rapid prototyping of new protocol characteristics. Researchers can use the open-source design to verify our results and build upon the framework, which aims to accelerate the development, validation, and adoption of Ethernet-based solutions in real-time applications.

}, keywords = {real-time ethernet, real-time networking}, doi = {10.1109/FCCM.2013.54}, author = {Gonzalo Carvajal and Miguel Figueroa and Robert Trausmuth and Sebastian Fischmeister} } @article {191, title = {A Comparison of Compositional Schedulability Analysis Techniques for Hierarchical Real-time Systems}, journal = {ACM Transactions on Embedded Computing Systems}, volume = {13}, year = {2013}, month = {Aug}, pages = {1 -- 37}, abstract = {

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.

}, keywords = {Compositionality, real-time systems, state-based scheduling}, issn = {1539-9087}, doi = {10.1145/2501626.2501629}, author = {Anand, Madhukar and Fischmeister, Sebastian and Lee, Insup} } @inproceedings {151, title = {DataMill: Rigorous Performance Evaluation Made Easy}, booktitle = {Proc. of the 4th ACM/SPEC International Conference on Performance Engineering (ICPE)}, year = {2013}, month = {April}, pages = {137--149}, address = {Prague, Czech Republic}, abstract = {

Empirical systems research is facing a dilemma. Minor aspects of an experimental setup can have a significant impact on its associated performance measurements and potentially invalidate conclusions drawn from them. Examples of such influences, often called hidden factors, include binary link order, process environment size, compiler generated randomized symbol names, or group scheduler assignments. The growth in complexity and size of modern systems will further aggravate this dilemma, especially with the given time pressure of producing results. So how can one trust any reported empirical analysis of a new idea or concept in computer science?

This paper introduces DataMill, a community-based easy-to-use services-oriented open benchmarking infrastructure for performance evaluation. DataMill facilitates producing robust, reliable, and reproducible results. The infrastructure incorporates the latest results on hidden factors and automates the variation of these factors. Multiple research groups already participate in DataMill.

DataMill is also of interest for research on performance evaluation. The infrastructure supports identifying new hidden factors, disseminating the research results beyond mere reporting. It provides a platform for investigating interactions and composition of hidden factors.

}, keywords = {benchmarking, empirical evaluation, systems}, author = {Augusto Oliveira and Jean-Christophe Petkovich and Thomas Reidemeister and Sebastian Fischmeister} } @inproceedings {172, title = {DIME: Time-aware Dynamic Binary Instrumentation Using Rate-based Resource Allocation}, booktitle = {Proc. of the 13th International Conference on Embedded Software (EMSOFT)}, year = {2013}, month = {Sept}, address = {Montreal, Canada}, abstract = {

Program analysis tools are essential for understanding programs, analyzing performance, and optimizing code. Some of these tools use code instrumentation to extract information at runtime. The instrumentation process can alter program behavior such as timing behavior and memory consumption. Time-sensitive programs, however, must meet specific timing constraints and thus require that the instrumentation process, for instance, bounds the timing overhead. Time-aware instrumentation techniques try to honor the timing constraints of such programs. All previous techniques, however, support only static and source-code instrumentation methods. Hence, they become impractical beyond microcontroller code for instrumenting large programs along with all their library dependencies.
In this work, we propose DIME, a time-aware dynamic binary instrumentation technique that adds an adjustable bound on the timing overhead to the program under analysis. We implement DIME using the dynamic instrumentation framework, Pin. Quantitative evaluation of the three implementation alternatives shows an average reduction of the instrumentation overhead by 3, 9, and 16 folds for complex instrumentation objectives. Instrumenting the VLC media player and a laser beam stabilization experiment demonstrate the practicality and scalability of DIME.

}, author = {Pansy Arafa and Hany Kashif and Sebastian Fischmeister} } @inproceedings {154, title = {An Efficient Periodic Resource Supply Model for Workloads with Transient Overloads}, booktitle = {Proc. of the Euromicro Conference on Real-Time Systems (ECRTS)}, year = {2013}, month = {Jul}, pages = {249 -- 258}, address = {Paris, France}, abstract = {

Real-time applications have deadline constraints.\  The system should provision sufficient resources for the appli- cation to meet the deadlines, and use supply and demand bound functions to analyze the schedulability of workloads. The concept of the demand bound function describes the upper bound on the resources required by the application, while the supply-bound function specifies the lower bound on the resources supplied to the tasks. If the system provides fewer resources than required, the application will experience an overload. Most work concentrates on designing systems that cannot experience short periods of overloads.

This work explores resource provisioning for control applica- tions that can tolerate overloads. It introduces analysis techniques for supply and demand bound functions that specifically consider overloads and delays in a periodic resource model. With this ex- tended model, the work addresses three problems: (1) determine the worst-case delay for a given resource demand and supply under a periodic resource model, (2) find a periodic resource supply for a given workload and worst-case tolerable delay, and (3) for a control system with a given robustness criterion, identify a periodic resource supply with a worst-case delay.

}, doi = {10.1109/ECRTS.2013.34}, author = {Akramul Azim and Shreyas Sundaram and Sebastian Fischmeister} } @inproceedings {157, title = {GPU-based Runtime Verification}, booktitle = {IEEE International Parallel \& Distributed Processing Symposium (IPDPS)}, year = {2013}, month = {May}, abstract = {

Runtime verification is a monitoring technique to gain assurance about well-being of a program at run time. Most existing approaches use sequential monitors; i.e., when the state of the program with respect to an event of interest changes, the monitor interrupts the program execution, evaluates a set of logical properties, and finally resumes the program execution. In this paper, we propose a GPU-based method for design and implementation of monitors that enjoy two levels of parallelism: the monitor (1) works along with the program in parallel, and (2) evaluates a set of properties in a parallel fashion as well. Our parallel monitoring algorithms effectively exploit the many-core platform available in the GPU. In addition to parallel processing, our approach benefits from a true separation of monitoring and functional concerns, as it isolates the monitor in the GPU. Our method is fully implemented and experimental results show significant reduction in monitoring overhead, monitoring interference, and power consumption due to leveraging the GPU technology.

}, keywords = {GPU, Runtime verification}, author = {Shay Berkovich and Borzoo Bonakdarpour and Sebastian Fischmeister} } @article {158, title = {Implementation and Evaluation of Global and Partitioned Scheduling in a Real-Time OS}, journal = {Real-Time Systems}, year = {2013}, pages = {1-46}, abstract = {

In this work, we provide an experimental comparison between Global-EDF and Partitioned-EDF, considering the run-time overhead of a real-time operating system (RTOS). Recent works have confirmed that OS implementation aspects, such as the choice of scheduling data structures and interrupt handling mechanisms, impact real-time schedulability as much as scheduling theoretic aspects. However, these studies used real-time patches applied into a general-purpose OS. By measuring the run-time overhead of an RTOS designed from scratch, we show how close the schedulability ratio of task sets is to the theoretical hard real-time schedulability tests. Moreover, we show how a well-designed object-oriented RTOS allows code reuse of scheduling components (e.g., thread, scheduling criteria, and schedulers) and easy real-time scheduling extensions. We compare our RTOS to a real-time patch for Linux in terms of the task set schedulability ratio of several generated task sets. In some cases, Global-EDF considering the overhead of the RTOS is superior to Partitioned-EDF considering the overhead of the patched Linux, which clearly shows how different OSs impact hard real-time schedulers.

}, keywords = {operating systems, real-time systems}, issn = {0922-6443}, doi = {10.1007/s11241-013-9183-3}, author = {Gracioli, G. and Fr{\"o}hlich, A. A. and Pellizzoni, R. and Fischmeister, S.} } @inproceedings {168, title = {INSTEP: A Static Instrumentation Framework for Preserving Extra-functional Properties}, booktitle = {Proc. of the 19th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)}, year = {2013}, month = {August}, address = {Taipei, Taiwan}, abstract = {

Tracing is a well-established method for debugging programs. Current approaches aim only at preserving functional correctness during the instrumentation. Preservation of functional correctness is a necessary feature of all instrumentation tools. However, few existing instrumentation tools preserve extra-functional properties of a program. Specific classes of software are unable to leverage software instrumentation; e.g., timing for real-time systems, memory consumption for embedded software, and tracing bandwidth for on-board software.


We present the first instrumentation framework, INSTEP, that preserves logical correctness and a rich set of extra-functional properties. INSTEP derives instrumentation alternatives based on the developer\’s instrumentation intent (II), abstracts the program and prunes the search space, and then instruments the program based on constraints and cost models of competing properties. We demonstrate and experiment with a fully automated framework of INSTEP with different IIs and extra-functional properties. We also experiment with a large automotive case study to show the scalability of INSTEP.

}, author = {Hany Kashif and Pansy Arafa and Sebastian Fischmeister} } @inproceedings {173, title = {Non-intrusive Program Tracing and Debugging of Deployed Embedded Systems Through Side-channel Analysis}, booktitle = {Proc. of the 14th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems (LCTES)}, year = {2013}, note = {

(best paper award)

}, pages = {77-88}, publisher = {ACM}, organization = {ACM}, address = {Washington, USA}, abstract = {

One of the hardest aspects of embedded software development is that of debugging, especially when faulty behavior is observed at the production or deployment stage. Non-intrusive observation of the system\&$\#$39;s behavior is often insufficient to infer the cause of the problem and identify and fix the bug. In this work, we present a novel approach for non-intrusive program tracing aimed at assisting developers in the task of debugging embedded systems at deployment or production stage, where standard debugging tools are usually no longer available. The technique is rooted in cryptography, in particular the area of side-channel attacks. Our proposed technique expands the scope of these cryptographic techniques so that we recover the sequence of operations from power consumption observations (power traces). To this end, we use digital signal processing techniques (in particular, spectral analysis) combined with pattern recognition techniques to determine blocks of source code being executed given the observed power trace. One of the important highlights of our contribution is the fact that the system works on a standard PC, capturing the power traces through the recording input of the sound card. Experimental results are presented and confirm that the approach is viable.

}, keywords = {debugging, embedded systems, side-channel analysis, simple power analysis, tracing}, isbn = {978-1-4503-2085-6}, doi = {10.1145/2465554.2465570}, url = {http://doi.acm.org/10.1145/2465554.2465570}, author = {Moreno, Carlos and Fischmeister, Sebastian and Hasan, M. Anwar} } @inproceedings {152, title = {An Open Platform for Mixed-Criticality Real-time Ethernet}, booktitle = {Proc. of the Conference on Design, Automation and Test in Europe (DATE)}, year = {2013}, pages = {153-156}, address = {Grenoble, France}, abstract = {

For more than one decade, researchers have considered Ethernet as a natural replacement to legacy fieldbuses in modern distributed applications. However, Ethernet components require special modifications and hardware support to provide strict timing guarantees. In general, the high-cost of deploying hardware components limits the experimental validation of proposed solutions in real-world applications. Despite the vast literature, only a few solutions report real implementations, and they are all closed to the research community, hindering further development for constantly evolving applications.

This paper introduces Atacama, an on-going effort on deploying the first hardware-accelerated and open-source framework for mixed-criticality communication on multi-hop networks. Specialized modules exploit the principles of traditional fieldbus systems to coordinate communication tasks on real-time stations, and can be easily integrated to and coexist with COTS devices operating with best-effort traffic. Experimental characterization of implemented prototypes report minimal jitter on 1Gbps links, and show that real-time guarantees are resilient to injected best-effort traffic. The framework is available as an open-source project, enabling researchers to verify the results, explore, test, and deploy new networking solutions for modern distributed systems in real-world scenarios.

}, keywords = {real-time communication, real-time ethernet}, url = {http://dl.acm.org/citation.cfm?id=2485288.2485326}, author = {Carvajal, Gonzalo and Fischmeister, Sebastian} } @inproceedings {167, title = {ORTAP: An Offset-based Response Time Analysis for a Pipelined Communication Resource Model}, booktitle = {Proc. of the 19th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2013}, month = {April}, pages = {247--258}, address = {Philadelphia, USA}, abstract = {

This work addresses the challenge of computing worst-case response times of hard real-time applications deployed on multiprocessor systems. In particular, the worst-case response time analysis (WCRTA) focuses on the communication between distributed tasks of hard real-time applications. The proposed WCRTA models the communication as a pipelined communication resource model. This model incorporates the effect of pipelining, and the parallel transmission of data. Applications of such a model include multiprocessor systems that use complex interconnects such as network-on-chips (NoC)s with priorities. In this paper, we present an exponential analysis, and a polynomial analysis, and prove its correctness. As an application, we apply the pipelined communication resource model to priority-aware NoCs, and we compare the proposed analyses against prior analysis techniques. Our experimental evaluation on two instances of 4 \× 4 and 8 \× 8 NoCs with 512,000 synthetic benchmarks shows 48.3\% and 66.7\% improvement in schedulability for the two NoC sizes over prior work.

}, doi = {10.1109/RTAS.2013.6531097}, author = {Hany Kashif and Sina Gholamian and Rodolfo Pellizzoni and Hiren D. Patel and Sebastian Fischmeister} } @inproceedings {174, title = {Reducing Monitoring Overhead by Integrating Event- and Time-triggered Techniques}, booktitle = {Proc. of the International Conference on Runtime Verification (RV)}, year = {2013}, month = {Sept}, abstract = {

Runtime verification is a formal technique used to check whether a program under inspection satisfies its specification by using a runtime monitor. Existing monitoring approaches use one of two ways for evaluating a set of logical properties: (1) event-triggered, where the program invokes the monitor when the state of the program changes, and (2) time-triggered, where the monitor periodically preempts the program and reads its state. Realizing the former is straightforward, but the runtime behaviour of event-triggered monitors are difficult to predict. Time-triggered monitoring (designed for real-time embedded systems), on the other hand, provides predictable monitoring behavior and overhead bounds at run time. Our previous work shows that time-triggered monitoring can potentially reduce the runtime overhead provided that the monitor samples the program state at a low frequency.

In this paper, we propose a hybrid method that leverages the benefits of both event- and time-triggered methods to reduce the overall monitoring overhead. We formulate an optimization problem, whose solution is a set of instrumentation instructions that switches between event-triggered and time-triggered modes of monitoring at run time; the solution may indicate the use of exactly one mode or a combination of the two modes. We fully implemented this method to produce instrumentation schemes for C programs that run on an ARM Cortex-M3 processor, and experimental results validate the effectiveness of this approach.

}, author = {Wallace Wu and Deepak Kumar and Borzoo Bonakdarpour and Sebastian Fischmeister} } @inproceedings {175, title = {RiTHM: A Tool for Enabling Time-triggered Runtime Verification for C Programs}, booktitle = {Proc. of the ACM Symposium on the Foundations of Software Engineering (FSE)}, year = {2013}, address = {St. Petersburg, Russia}, author = {Samaneh Navabpour and Yogi Joshi and Chun Wah Wallace and Shay Berkovich and Ramy Medhat and Borzoo Bonakdarpour and Sebastian Fischmeister} } @article {146, title = {Time-triggered Runtime Verification}, journal = {Formal Methods in System Design (FMSD)}, volume = {43}, year = {2013}, month = {2013}, pages = {29--60}, abstract = {

The goal of runtime verification is to monitor the behavior of a system to check its conformance to a set of desirable logical properties. The literature of runtime verification mostly focuses on event-triggered solutions, where a monitor is invoked when an event of interest occurs (e.g., change in the value of some variable). At invocation, the monitor evaluates the set of properties of the system that are affected by the occurrence of the event. This constant invocation introduces two major defects to the system under scrutiny at run time: (1) significant overhead, and (2) unpredictability of behavior. These defects are serious obstacles when applying runtime verification on safety-critical systems that are time-sensitive by nature.

To circumvent the aforementioned defects in runtime verification, in this article, we introduce a novel time-triggered approach, where the monitor takes samples from the system with a constant frequency, in order to analyze the system\&$\#$39;s health. We describe the formal semantics of time-triggered monitoring and discuss how to optimize the sampling period using minimum auxiliary memory. We show that such optimization is NP-complete and consequently introduce a mapping to Integer Linear Programming. Experiments on a real-time benchmark suite show that our approach introduces bounded overhead and effectively reduces the involvement of the monitor at run time by using negligible auxiliary memory. We also show that in some cases it is even possible to reduce the overall overhead of runtime verification by using our time-triggered approach when the structure of the system allows choosing a long enough sampling period.

}, issn = {0925-9856}, doi = {10.1007/s10703-012-0182-0}, author = {Borzoo Bonakdarpour and Samaneh Navabpour and Sebastian Fischmeister} } @inproceedings {150, title = {Why You Should Care About Quantile Regression}, booktitle = {Proceedings of the Eighteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)}, year = {2013}, month = {March}, address = {Houston, USA}, abstract = {

Research has shown that correctly conducting and analysing computer performance experiments is difficult. This paper investigates what is necessary to conduct successful computer performance evaluation by attempting to repeat a prior experiment: the comparison between two schedulers.

In our efforts, we found that exploring an experimental space through a series of incremental experiments can be inconclusive, and there may be no indication of how much experimentation will be enough. Analysis of variance (ANOVA), a traditional analysis method, is able to partly solve the problems with the previous approach, but we demonstrate that ANOVA might be insufficient for proper analysis due to the requirements it imposes on the data.

Finally, we demonstrate the successful application of quantile regression, a recent development in statistics, to computer performance experiments. Quantile regression can provide more insight into the experiment than ANOVA, with the additional benefit of being applicable to data from any distribution. This property makes it especially useful in our field, since non-normally distributed data is common in computer experiments.

}, author = {Augusto Oliveira and Sebastian Fischmeister and Amer Diwan and Matthias Hauswirth and Peter Sweeney} } @inproceedings {147, title = {CSS: Conditional State-Based Scheduling for Networked Control Systems}, booktitle = {International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) }, year = {2012}, pages = {78-87}, address = {Seoul, Korea}, abstract = {

Modern industrial networked control systems (NCSs) tend to be complicated and have dynamic workload by holding a variety of applications via a shared network. The static network scheduling algorithms fit most NCSs due to their deterministic characteristics and timing guarantees, but they cannot handle dynamic workloads for lack of making on the-fly decisions. The conditional state-based scheduling adds the dynamism in the static scheduling algorithms by automata or more explicitly state chart like formalisms with conditional transitions. In this paper, we propose CSS scheme that applies the conditional state-based scheduling to dynamically schedule different applications in the industrial NCSs. CSS aims at the time-triggered network in the NCSs and uses time division multiple access (TDMA) method to let the applications access the network. To enhance the scalability of the NCSs, we design CSS as a decentralized scheme where each application in NCSs has a local scheduler to make its schedule decisions. Appropriate algorithms are applied to ensure the scheduling decisions made by the local schedulers are consistent and the desired system performance can be achieved. Simulation results demonstrate the effectiveness of the proposed scheme compared to the static TDMA used in real-time networks.

}, doi = {10.1109/RTCSA.2012.13}, author = {Xi Chen and Akramul Azim and Xue Liu and Sebastian Fischmeister} } @article {72, title = {Evaluation of Communication Architectures for Switched Real-time Ethernet}, journal = {IEEE Transactions on Computers}, year = {2012}, abstract = {

Safety-critical distributed real-time applications operating with strict temporal constraints rely on deterministic networks with low latency and jitter. Traditional fieldbus systems deliver these guarantees, but they have limited compatibility with open infrastructures and limited support for high transmission rates. Ethernet technology rises as a low-cost, high-speed, and ubiquitous alternative to fieldbus systems; however, standard Ethernet requires special arbitration mechanisms to support real-time traffic because of the standard\’s inherent non-deterministic behavior. This work explores the associated trade-offs for three different solutions for real-time communication over switched Ethernet. The paper presents and discusses three architectures that modify different network components, enhancing them with additional customized modules to support time-triggered communication based on Network Code. Using the NetFPGA platform as the unified prototyping technology for all the components, we developed an open-source framework to characterize each solution using experimental data for the latency, jitter, throughput, robustness, and cost in logical resources. The results provide insights to help future developers of real-time communication technology decide which components to modify according to the requirements of their applications.

}, keywords = {NCM, state-based scheduling}, doi = {10.1109/TC.2012.177}, url = {http://www.computer.org/portal/web/csdl/doi/10.1109/TC.2012.177}, author = {Gonzalo Carvajal and Chun W. Wallace Wu and Sebastian Fischmeister} } @article {71, title = {mTags: Augmenting Microkernel Messages with Lightweight Metadata}, journal = {ACM Operating Systems Review}, volume = {46}, year = {2012}, pages = {67-79}, abstract = {

In this work we propose mTags, an efficient mechanism that augments microkernel interprocess messages with lightweight metadata to enable the development of new, system-wide functionality without requiring modification of the application source code. As such it is well suited for systems with a large legacy code base or third-party applications like phone and tablet applications. We explored mTags in a variety of different contexts in local and distributed system scenarios. For example, we detail use cases in areas including messaging-induced deadlocks and mode propagation. To demonstrate that mTags is technically feasible and practical, we implemented it in a commercial microkernel and executed multiple sets of standard benchmarks on two different computing architectures. The results clearly demonstrate that mTags has only negligible overhead and strong potential for many applications.

}, keywords = {tagging}, doi = {10.1145/2331576.2331587}, author = {Augusto Oliveira and Ahmad Saif Ur Rehman and Sebastian Fischmeister} } @inproceedings {145, title = {Path-aware Time-triggered Runtime Verification}, booktitle = {Third International Conference on Runtime Verification (RV)}, year = {2012}, month = {September}, pages = {199-213}, address = {Istanbul, Turkey}, abstract = {

Time-triggered runtime verification aims at establishing a framework that provides bounded overhead and predictable behavior at run time. A time-triggered monitor runs in parallel with the program under inspection and periodically samples the program state to evaluate a set of properties. However, a time-triggered monitor working with a fixed sampling frequency often suffers from redundant sampling, which results in excessive overhead. In this paper, we propose an effective approach to reduce redundant sampling.\  Our approach calculates the sampling frequency with respect to the program behavior at run time. We further advance this approach to dynamically adjust the sampling frequency at run time by predicting the program behavior using symbolic execution. Our approach is fully implemented in a tool chain. Experiments on the SNU benchmark suit show that our approach reduces the sampling frequency, runtime overhead, and the number of redundant samples by up to 3.5 times, 69\%, and 86\%, respectively.

}, url = {http://link.springer.com/chapter/10.1007/978-3-642-35632-2_21}, author = {Samaneh Navabpour and Borzoo Bonakdarpour and Sebastian Fischmeister} } @inproceedings {74, title = {Program Transformation for Time-aware Instrumentation}, booktitle = {Proc. of the 17th IEEE International Conference on Emerging Technologies \& Factory Automation (ETFA)}, year = {2012}, month = {September}, pages = {1-8}, address = {Krakow, Poland}, abstract = {

Instrumentation is an important technique to gain insight into a program\’s behavior. Safety-critical real-time embedded applications are time sensitive and so instrumentation techniques for this domain must especially consider timing. This work establishes the basis for measuring the effectiveness of approaches for time-aware instrumentation in addition to coverage. We define a metric and define its optimality criterion. We identify locations in the program where program transformation techniques can be applied to increase the instrumentability of the program. We subsequently use the proposed metric to evaluate two tranformation methods that improve the effectiveness and coverage of current techniques for time-aware instrumentation by a factor of five.

}, keywords = {Instrumentation, time-aware instrumentation, tracing}, doi = {10.1109/ETFA.2012.6489580}, author = {Hany Kashif and Sebastian Fischmeister} } @article {39, title = {State-based scheduling with tree schedules: analysis and evaluation}, journal = {Real-Time Systems}, volume = {48}, year = {2012}, pages = {430 - 462}, abstract = {
Distributed real-time systems require bounded communication delays and achieve them by means of a predictable and verifiable control mechanism for the communication medium. Real-time bus arbitration mechanisms control access to the medium and guarantee bounded communication delays. These arbitration mechanisms can be static dispatch tables or dynamic, algorithmic approaches.
In this work, we introduce a real-time bus arbitration mechanism called tree schedules that takes the best parts of both sides: It can be analyzed like static dispatch tables, and it provides a certain degree of flexibility similar to algorithmic approaches. We present tree schedules as a framework to specify real-time traffic and introduce mechanisms to analyze it. We discuss how tree schedules can capture application-specific behavior in a time-triggered state-based supply model by means of conditional branching built into the model. We present analysis results for this model specifically aiming at schedulability in fixed and dynamic priority schemes and waiting time analysis. Finally, we demonstrate the advantages of state-based supply over stateless supply by means of two case studies.
}, keywords = {network code}, issn = {0922-6443}, doi = {10.1007/s11241-012-9151-3}, author = {Madhukar Anand and Sebastian Fischmeister and Insup Lee and Linh T. X. Phan} } @inproceedings {76, title = {Time-triggered Program Self-monitoring}, booktitle = {Proc. of 18th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)}, year = {2012}, pages = {260-269}, address = {Seoul, Korea}, abstract = {

Runtime monitoring aims at analyzing the well-being of a system at run time in order to detect errors and steer the system towards a healthy behavior. Such monitoring is a complementary technique to other approaches for ensuring correctness, such as formal verification and testing. In time-triggered runtime monitoring, a monitor runs as a separate process in parallel with an application program under scrutiny and samples the program\’s state periodically to evaluate a set of properties. Applying this technique in a computing system results in obtaining bounded and predictable overhead. Gaining such characteristics for overhead is highly desirable for designing and engineering time-critical applications, such as safety-critical embedded systems. However, a time-triggered monitor requires certain synchronization features at operating system level and may suffer from various concurrency and synchronization dependencies and overheads as well as possible unreliability of synchronization primitives in a real-time setting. In this paper, we propose a new method, where the program under inspection is instrumented, so that it self-samples its state in a periodic fashion without requiring assistance from an external monitor or internal timer. We call this technique time-triggered self-monitoring. First, we formulate an optimization problem for minimizing the number of points in a program, where self-sampling instrumentation instructions must be inserted. We show that this problem is NP-complete. Consequently, we propose a SAT-based solution and a heuristic to cope with the exponential complexity. Our experimental results show that a time-triggered self-monitored program performs significantly better than the same program monitored by an external time-triggered monitor.

}, keywords = {Runtime verification, TTRV}, doi = {10.1109/RTCSA.2012.16}, author = {Borzoo Bonakdarpour and Johnson Thomas and Sebastian Fischmeister} } @article {69, title = {Tracing and Recording Interrupts in Embedded Software}, journal = {Journal of Systems Architecture}, volume = {58}, year = {2012}, month = {Oct}, pages = {372-385}, abstract = {

During the system development, developers often must correct wrong behavior in the software\–-an activity colloquially called program debugging. Debugging is a complex activity, especially in real-time embedded systems because such systems interact with the physical world and make heavy use of interrupts for timing and driving I/O devices. Debugging interrupts is difficult, because they cause non-linear control flow in programs which is hard to reproduce in software. Record/replay mechanisms have proven their use to debugging embedded systems, because they provide means to recreate control flows offline where they can be debugged. In this work, we present the data tracing part of the record/replay mechanism that is specifically targeted to record interrupt behavior. To tune our tracing mechanism, we use the observed principle of return address clustering and a formal model for quantitative reasoning about the tracing mechanism. The presented heuristic and mechanisms show surprisingly good results\–-with higher fingerprint widths an 800 percent speedup on the selector function and a 300 percent reduction on duplicates for non-optimal selector functions\–-considering the leanness of the approach. Using an equal portion for the fingerprint and for the return address lead to the best results in our experiments.

}, keywords = {debugging, embedded systems, record and replay, tracing}, issn = {1383-7621}, doi = {10.1016/j.sysarc.2012.06.003}, url = {http://www.sciencedirect.com/science/article/pii/S1383762112000574}, author = {Giovani Gracioli and Sebastian Fischmeister} } @inproceedings {73, title = {Using Link-level Latency Analysis for Path Selection for Real-time Communication on NoCs}, booktitle = {Proceedings of the Asia South Pacific Design Automation Conference (ASPDAC)}, year = {2012}, month = {February}, pages = {499-504}, address = {Sydney, Australia}, abstract = {

We present a path selection algorithm that is used when deploying hard real-time traffic flows onto a chip- multiprocessor system. This chip-multiprocessor system uses a priority-based real-time network-on-chip interconnect between the multiple processors. The problem we address is the following: given a mapping of the tasks onto a chip-multiprocessor system, we need to determine the paths that the traffic flows take such that the flows meet there deadlines. Furthermore, we must ensure that the deadline is met even in the presence of direct and indirect interference from other flows sharing network links on the path. To achieve this, our algorithm utilizes a link-level analysis to determine the impact of a link being used by a flow, and its affect on other flows sharing the link. Our experimental results show that we can improve schedulability by about 8\% and 15\% over Minimum Interference Routing and Widest Shortest Path algorithms, respectively.

}, keywords = {NOC, shortest path algorithm}, isbn = {2153-6961}, doi = {10.1109/ASPDAC.2012.6165004}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6165004}, author = {Hany Kashif and Hiren D. Patel and Fischmeister, Sebastian} } @inproceedings {66, title = {Efficient Techniques for Near-optimal Instrumentation in Time-triggered Runtime Verification}, booktitle = {Proc. of the 2nd International Conference on Runtime Verification (RV)}, year = {2011}, month = {September}, pages = {208-222}, address = {San Francisco, USA}, abstract = {

Time-triggered runtime verification aims at tackling two defects associated with runtime overhead normally incurred in event-triggered approaches: unboundedness and unpredictability. In the time-triggered approach, a monitor runs in parallel with the program and periodically samples the program state to evaluate a set of properties. In our previous work, we showed that to increase the sampling period of the monitor (and hence decrease involvement of the monitor), one can employ auxiliary memory to build a history of state changes between subsequent samples. We also showed that the problem of optimization of the size of history and sampling period is NP-complete. In this paper, we propose a set of heuristics that find near-optimal solutions to the problem. Our experiments show that by employing negligible extra memory at run time, we can solve the optimization problem significantly faster, while maintaining a similar level of overhead as the optimal solution. We conclude from our experiments that the NP-completeness of the optimization problem is not an obstacle when applying time-triggered runtime verification in practice.

}, keywords = {Runtime verification, TTRV}, doi = {10.1007/978-3-642-29860-8_16}, url = {http://www.springerlink.com/content/q8812w5u506844u6/}, author = {Samaneh Navabpour and Chun Wah Wallace Wu and Borzoo Bonakdarpour and Fischmeister, Sebastian} } @inproceedings {64, title = {Lowering Overhead in Sampling-based Execution Monitoring and Tracing}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)}, year = {2011}, pages = {101-110}, address = {Chicago, USA}, abstract = {

Debugging is an important phase in the embedded software development cycle because of its high proportion in the overall cost in the product development. Debugging is difficult for real-time applications as such programs are time-sensitive and must meet deadlines in often a resource constrained environment. A common approach for real-time systems is to monitor the execution instead of stepping through the program, because stepping will usually violate all deadline constraints. We consider a sampling-based approach for monitoring, because of its predictable overhead for the system compared to traditional monitoring. However, the sampling-based approach can easily have high overhead depending on the length of branches and the granularity of the monitoring effort. To reduce this overhead, we instrument the program with markers that will permit us to sample less frequently and thus reduce the overhead. This leads to the interesting problems of (a) where to place the markers in the code and (b) how to manipulate the markers. While related work investigates the first part, in this work, we investigate the second component of the problem. We investigate different instrumentation schemes and propose two new schemes based on bitvectors that significantly reduce the overhead for sampling-based execution monitoring.

}, keywords = {debugging, embedded, monitoring, sampling, tracing}, isbn = {978-1-4503-0555-6}, doi = {10.1145/1967677.1967692}, url = {http://dl.acm.org/citation.cfm?id=1967692}, author = {Johnson Thomas and Fischmeister, Sebastian and Deepak Kumar} } @inproceedings {67, title = {Optimal Instrumentation of Data-flow in Concurrent Data Structures}, booktitle = {Proc. of the 15th International Conference On Principles Of Distributed Systems (OPODIS)}, year = {2011}, month = {December}, pages = {497-512}, address = {Toulouse, France}, abstract = {

In this paper, we propose an automated technique for optimal instrumentation of multi-threaded programs for debugging and testing of concurrent data structures. We define a notion of observability that enables debuggers to trace back and locate errors through data-flow instrumentation. Observability in a concurrent program enables a debugger to extract the value of a set of desired variables through instrumenting another (possibly smaller) set of variables. We formulate an optimization problem that aims at minimizing the size of the latter set. In order to cope with the exponential complexity of the problem, we present a SAT-based solution. Our approach is fully implemented and experimental results on popular concurrent data structures (e.g., linked lists and red-black trees) show significant performance improvement in optimally-instrumented programs using our method as compared to ad-hoc over-instrumented programs.

}, keywords = {debugging, Instrumentation}, doi = {10.1007/978-3-642-25873-2_34}, url = {http://www.springerlink.com/content/dh336633w17613jp/}, author = {Samaneh Navabpour and Borzoo Bonakdarpour and Fischmeister, Sebastian} } @inproceedings {63, title = {Resolving State Inconsistency in Distributed Fault-Tolerant Real-Time Dynamic TDMA Architectures}, booktitle = {Proc. of the 16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)}, year = {2011}, month = {September}, pages = {1-9}, address = {Toulouse, France}, abstract = {

State consistency in safety-critical distributed systems is mandatory for synchronizing distributed decisions as found in dynamic time division multiple access (TDMA) schedules in the presence of faults. A TDMA schedule that supports networked systems making decisions at run time is sensitive to transient faults, because stations can make incorrect local decisions at run time and cause state inconsistency and collisions. We refer to this type of TDMA schedule as a dynamic TDMA schedule. Faulty decisions are especially undesirable for safety-critical systems with hard real-time constraints. Hence, real-time communication schedules must have the capability of detecting state inconsistency within a fixed amount of time. In this paper, we show through experimentation that state inconsistency is a real problem, and we propose a solution for resolving state inconsistency in TDMA schedules.

}, keywords = {Distributed system, Scheduling, TDMA}, isbn = {978-1-4577-0016-3}, doi = {10.1109/ETFA.2011.6059022}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6059022}, author = {Akramul Azim and Fischmeister, Sebastian} } @inproceedings {68, title = {Runtime Monitoring of Time-sensitive Systems --- Tutorial Supplement}, booktitle = {Proc. of the 2nd International Conference on Runtime Verification (RV)}, year = {2011}, address = {San Francisco, USA}, abstract = {

This tutorial focuses on issues involved in runtime monitoring of time-sensitive systems, where violation of timing constraints are undesired. Our goal is to describe the challenges in instrumenting, measuring, and monitoring such systems and present our solutions developed in the past few years to deal with these challenges. The tutorial consists of two parts. First, we present challenge problems and corresponding solutions on instrumenting real-time systems so that timing constraints of the system are respected. The second part of the tutorial will focus on time-triggered runtime monitoring, where a monitor is invoked at equal time intervals, allowing designers to schedule regular and monitoring tasks hand-in-hand.

}, author = {Borzoo Bonakdarpour and Fischmeister, Sebastian} } @inproceedings {61, title = {Sampling-based Runtime Verification}, booktitle = {Proceedings of the 17th International Conference on Formal Methods (FM)}, year = {2011}, month = {June}, pages = {88-102}, address = {Limerick, Ireland}, abstract = {

The literature of runtime verification mostly focuses on event-triggered solutions, where a monitor is invoked by every change in the state of the system and evaluates properties of the system. This constant invocation introduces two major drawbacks to the system under scrutiny at run time: (1) significant overhead and (2) unpredictability. To circumvent the latter drawback, in this paper, we introduce a time-triggered approach, where the monitor frequently takes samples from the system to analyze the system\’s health. We propose formal semantics of sampling-based monitoring and discuss how to optimize the sampling period using minimum auxiliary memory. We show that such optimization is NP-complete and consequently introduce a mapping to Integer Linear Programming. Experiments on benchmark applications show that our approach introduces bounded overhead and effectively reduces involvement of the monitor at run time using negligible auxiliary memory.

}, keywords = {monitoring, predictability, Runtime verification, time-triggered}, isbn = {978-3-642-21436-3}, doi = {10.1007/978-3-642-21437-0_9}, url = {http://www.springerlink.com/content/b5304khkjh338720/}, author = {Borzoo Bonakdarpour and Samaneh Navabpour and Fischmeister, Sebastian} } @inproceedings {65, title = {Software Debugging and Testing using the Abstract Diagnosis Theory}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, Tools and Theory for Embedded Systems (LCTES)}, year = {2011}, month = {April}, pages = {111-120}, address = {Chicago, USA}, abstract = {

In this paper, we present a notion of observability and controllability in the context of software testing and debugging. Our view of observability is based on the ability of developers, testers, and debuggers to trace back a data dependency chain and observe the value of a variable by starting from a set of variables that are naturally observable (e.g., input/output variables). Likewise, our view of controllability enables one to modify and control the value of a variable through a data dependency chain by starting from a set of variables that can be modified (e.g., input variables). Consequently, the problem that we study in this paper is to identify the minimum number of variables that have to be made observable/controllable in order for a tester or debugger to observe/control the value of another set of variables of interest, given the source code. We show that our problem is an instance of the well-known abstract diagnosis problem, where the objective is to find the minimum number of faulty components in a digital circuit, given the system description and value of input/output variables. We show that our problem is NP-complete even if the length of data dependencies is at most 2. In order to cope with the inevitable exponential complexity, we propose a mapping from the general problem, where the length of data dependency chains is unknown a priori, to integer linear programming. Our method is fully implemented in a tool chain for MISRA-C compliant source codes. Our experiments with several real-world applications show that in average, a significant number of debugging points can be reduced using our methods. This result is our motivation to apply our approach in debugging and instrumentation of embedded software, where changes must be minimal as they can perturb the timing constraints and resource consumption. Another interesting application of our results is in data logging of non-terminating embedded systems, where axillary data storage devices are slow and have limited size.

}, keywords = {diagnosis, logging, software debugging, testing}, isbn = {978-1-4503-0555-6}, doi = {10.1145/1967677.1967693}, url = {http://dl.acm.org/citation.cfm?id=1967693}, author = {Samaneh Navabpour and Borzoo Bonakdarpour and Fischmeister, Sebastian} } @inproceedings {62, title = {Design Choices for High-Confidence Distributed Real-time Software}, booktitle = {Proc. of the International Symposium On Leveraging Applications of Formal Methods, Verification and Validation (ISoLA)}, year = {2010}, month = {October}, pages = {327-342}, address = {Heraclion, Crete, Greece}, abstract = {

Safety-critical distributed real-time systems, such as networked medical devices, must operate according to their specification, because incorrect behaviour can have fatal consequences. A system\’s design and architecture influences how difficult it is to provide confidence that the system follows the specification. In this work, we summarize and discuss three design choices and the underlying concepts that aim at increasing predictability and analyzability. We investigate mandatory resource reservation to guarantee resource availability, separation of resource consumptions to better manage resource inter-dependency, and enumerative reconfiguration. We use the example of a distributed monitoring system for the human cardiovascular system to substantiate our arguments.

}, keywords = {network code, safety, state based schedule}, isbn = {3-642-16560-5 978-3-642-16560-3}, doi = {10.1007/978-3-642-16561-0_32}, url = {http://www.springerlink.com/content/414j200175704528/}, author = {Fischmeister, Sebastian and Akramul Azim} } @article {59, title = {Generating Reliable Code from Hybrid-Systems Models}, journal = {IEEE Transactions on Computers}, volume = {59}, year = {2010}, month = {July}, pages = {1281{\textendash}1294}, abstract = {

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.

}, keywords = {Formal languages, network code, software engineering}, issn = {0018-9340}, doi = {10.1109/TC.2010.84}, url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5453343}, author = {Anand, Madhukar and Fischmeister, Sebastian and Hur, Yerang and Kim, Jesung and Lee, Insup} } @inproceedings {58, title = {Model-based Programming of Modular Robots}, booktitle = {Proc. of the 13th IEEE International Symposium on Object/component/service-oriented Real-time Distributed Computing (ISORC)}, year = {2010}, month = {May}, pages = {66-74}, address = {Carmona, Spain}, abstract = {

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 programing 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.

}, keywords = {automation, Model based programming, modular, robotics}, doi = {10.1109/ISORC.2010.16}, url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5479573}, author = {Arney, David and Fischmeister, Sebastian and Lee, Insup and Takashima, Yoshihito and Yim, Mark} } @inproceedings {57, title = {Sampling-based Program Execution Monitoring}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES)}, year = {2010}, month = {April}, pages = {133-142}, address = {Stockholm, Sweden}, abstract = {

For its high overall cost during product development, program debugging is an important aspect of system development. Debugging is a hard and complex activity, especially in time-sensitive systems which have limited resources and demanding timing constraints. System tracing is a frequently used technique for debugging embedded systems. A specific use of system tracing is to monitor and debug control-flow problems in programs. However, it is difficult to implement because of the potentially high overhead it might introduce to the system and the changes which can occur to the system behaviour due to tracing. To solve the above problems, in this work, we present a sampling-based approach to execution monitoring which specifically helps developers debug time-sensitive systems such as real-time applications. We build the system model and propose three theorems to determine the sampling period in different scenarios. We also design seven heuristics and an instrumentation framework to extend the sampling period which can reduce the monitoring overhead and achieve an optimal tradeoff between accuracy and overhead introduced by instrumentation. Using this monitoring framework, we can use the information extracted through sampling to reconstruct the system state and execution paths to locate the deviation.

}, keywords = {debugging, embedded, monitoring, sampling, tracing}, isbn = {978-1-60558-953-4}, doi = {10.1145/1755888.1755908}, url = {http://dl.acm.org/citation.cfm?id=1755908}, author = {Fischmeister, Sebastian and Ba, Yanmeng} } @inproceedings {56, title = {Semantics-Preserving Implementation of Synchronous Specifications Over Dynamic TDMA Distributed Architectures}, booktitle = {Proc. of the International Conference on Embedded Software (EMSOFT)}, year = {2010}, month = {October}, pages = {199-208}, address = {Scottsdale, Arizona, USA}, abstract = {

We propose a technique to automatically synthesize programs and schedules for hard real-time distributed (embedded) systems from synchronous data-flow models. Our technique connects the SynDEx scheduling tool and the Network Code toolchain in a seamless flow of automatic model transformations that go all the way from specification to implementation. Our contribution is the non-trivial connection between the models manipulated by SynDEx and by the Network Code toolchain, at both formal and tool level. We provide an algorithm for converting the data-dependent schedule tables output by SynDEx into Network Code programs which can be seen as an \‘\‘assembly code\’\’ level for time-driven distributed real-time systems. The main difficulty is to ensure the preservation of both functionality and the real-time guarantees computed by SynDEx in the presence of clock drifts (which are abstracted away in the scheduling model of SynDEx). Existing tools can convert the resulting Network Code programs into software and hardware-accelerated execution units.

}, keywords = {clock synchronization, Clocked Graphs, distributed real-time implementation, dynamic TDMA, network code, synchronous model, SynDEx}, isbn = {978-1-60558-904-6}, doi = {10.1145/1879021.1879048}, url = {http://dl.acm.org/citation.cfm?doid=1879021.1879048}, author = {Dumitru Potop-Butucaru and Akramul Azim and Fischmeister, Sebastian} } @inproceedings {55, title = {A TDMA Ethernet Switch for Dynamic Real-Time Communication}, booktitle = {Proc. of the 18th IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM)}, year = {2010}, month = {May}, pages = {119{\textendash}126}, address = {Charlotte, United States}, abstract = {

A real-time communication medium must provide a special coordination mechanism to guarantee bounded communication delays. Implementing this mechanism in software offers flexibility but reduces reliability and performance. On the other hand, customized hardware solutions deliver high throughput and predictability, but they increase the implementation cost and are unable to adapt to the specific needs of individual applications. In this work, we introduce a switch that implements a programmable dedicated time-triggered packet switching mechanism on top of Ethernet. The switch, called the Network Code Switch bases on the NetFPGA system and executes flexible but verifiable state-based schedules encoded in the Network Code programming language. This permits the user to tailor the communication behavior to the needs of the distributed application with verifiable performance. We discuss our experience starting at the designing to the implementation of the prototype, and describe how we exploited modularity and code reutilization to reduce the implementation costs and increase the flexibility of the architecture. We also validate our design by evaluating the overhead and throughput of the implemented prototype.

}, keywords = {NCM, NCM Switch, netfpga}, isbn = {978-0-7695-4056-6}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5474059}, author = {Gonzalo Carvajal and Fischmeister, Sebastian} } @article {60, title = {Time-Aware Instrumentation of Embedded Software}, journal = {IEEE Transactions on Industrial Informatics}, volume = {6}, year = {2010}, month = {August}, pages = {652{\textendash}663}, abstract = {

Software instrumentation is a key technique in many stages of the development process. It is particularly important for debugging embedded systems. Instrumented programs produce data traces which enable the developer to locate the origins of misbehaviours in the system under test. However, producing data traces incurs runtime overhead in the form of additional computation resources for capturing and copying the data. The instrumentation may therefore interfere with the system\’s timing and perturb its behavior. In this work, we propose an instrumentation technique for applications with temporal constraints, specifically targetting background/foreground or cyclic executive systems. Our framework permits reasoning about space and time and enables the composition of software instrumentations. In particular, we propose a definition for trace reliability, which enables us to instrument real-time applications which aggressively push their time budgets. Using the framework, we present a method with low perturbation by optimizing the number of insertion points and trace buffer size with respect to code size and time budgets. Finally, we apply the theory to two concrete case studies: we instrument the OpenEC firmware for the keyboard controller of the One Laptop Per Child project, as well as an implementation of a flash filesystem.

}, keywords = {debugging, Instrumentation, real-time, tracing}, issn = {1551-3203}, doi = {10.1109/TII.2010.2068304}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5559440}, author = {Fischmeister, Sebastian and Lam, Patrick} } @article {53, title = {Hardware Acceleration for Conditional State-Based Communication Scheduling on Real-Time Ethernet}, journal = {IEEE Transactions on Industrial Informatics}, volume = {5}, year = {2009}, pages = {325{\textendash}337}, abstract = {

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.

}, keywords = {ASTM demo, NCM, real-time, state-based scheduling}, issn = {1551-3203}, doi = {10.1109/TII.2009.2026642}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5196857}, author = {Fischmeister, Sebastian and Trausmuth, Robert and Lee, Insup} } @article {52, title = {Plug-and-Play for Medical Devices: Experiences from a Case Study}, journal = {Biomedical Instrumentation \& Technology}, volume = {43}, year = {2009}, keywords = {ASTM demo, medical devices, NCM, real-time, state-based scheduling}, doi = {10.2345/0899-8205-43.4.313}, author = {Arney, David and Fischmeister, Sebastian and Julian M. Goldman and Lee, Insup and Trausmuth, Robert} } @inproceedings {51, title = {Resource Scopes: Toward Language Support for Compositional Determinism}, booktitle = {Proc. of the 12th IEEE International Symposium on Object/component/service-oriented Real-time Distributed Computing (ISORC)}, year = {2009}, month = {March}, pages = {295{\textendash}304}, address = {Tokyo, Japan}, abstract = {

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.

}, keywords = {determinism, distributed computing, real-time}, isbn = {978-0-7695-3573-9}, doi = {10.1109/ISORC.2009.42}, url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5232027}, author = {Anand, Madhukar and Fischmeister, Sebastian and Lee, Insup} } @inproceedings {50, title = {Specification and Analysis of Network Resource Requirements of Control Systems}, booktitle = {Proc. of the 12th International Conference on Hybrid Systems: Computation and Control (HSCC)}, year = {2009}, month = {April}, pages = {381{\textendash}395}, address = {Los Angeles, USA CA}, abstract = {

We focus on spatially distributed control systems in which measurement and actuation data is sent via a bus shared with other applications. An approach is proposed for specifying and implementing dynamic scheduling policies for the bus with performance guarantees. Specifically, we propose an automata-based scheduler which we automatically generate from a model of the controlled plant and the controller. We show that, in addition to ensuring performance, our approach allows adjustments to dynamic conditions such as varying disturbances and network load. We present a full development path from performance specifications (exponential stability) to a control design and its implementation using Controller Area Network (CAN).

}, keywords = {NCM, real-time, state-based scheduling}, isbn = {978-3-642-00601-2}, doi = {10.1007/978-3-642-00602-9_27}, url = {http://dl.acm.org/citation.cfm?id=1538216}, author = {Gera Weiss and Fischmeister, Sebastian and Anand, Madhukar and Rajeev Alur} } @inproceedings {49, title = {On Time-Aware Instrumentation of Programs}, booktitle = {Proc. of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2009}, month = {April}, pages = {305{\textendash}314}, address = {San Francisco, USA}, abstract = {

Software instrumentation is a key technique in many stages of the development process. It is of particular importance for debugging embedded systems. Instrumented programs produce data traces which enable the developer to locate the origins of misbehaviours in the system under test. However, producing data traces incurs runtime overhead in the form of additional computation resources for capturing and copying the data. The instrumentation may therefore interfere with the system\&$\#$39;s timing and perturb its behavior. In the worst case, this perturbation leads to new system behaviours that prevent the developer from locating the original misbehaviours. In this work, we propose an instrumentation technique for applications with temporal constraints, specifically targetting background/foreground systems. Our framework permits reasoning about space and time for software instrumentations. In particular, we propose a definition for trace reliability, which enables us to instrument real-time applications which aggressively push their time budgets. Using the framework, we present a method with low perturbation by optimizing the number of insertion points and trace buffer size for code size and time budgets. Finally, we apply the theory to a concrete case study and instrument the OpenEC firmware for the keyboard controller of the One Laptop Per Child project. This publication has been superseeded by an article in the IEEE Transactions on Industrial Informatics to be published soon.

}, keywords = {debugging, real-time, tracing}, isbn = {9780769536361}, doi = {10.1109/RTAS.2009.26}, url = {http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=04840591}, author = {Fischmeister, Sebastian and Lam, Patrick} } @inproceedings {54, title = {Tracing Interrupts in Embedded Software}, booktitle = {Proc. of the ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES)}, year = {2009}, note = {

(best in research forum award)

}, month = {June}, pages = {137{\textendash}146}, address = {Dublin, Ireland}, abstract = {

During the system development, developers often must correct wrong behavior in the software\–-an activity colloquially called program debugging. Debugging is a complex activity, especially in real-time embedded systems because such systems interact with the physical world and make heavy use of interrupts for timing and driving I/O devices. Debugging interrupts is difficult, because they cause non-linear control flow in programs which is hard to reproduce in software. Record/replay mechanisms have proven their use to debugging embedded systems, because they provide means to recreate control flows offline where they can be debugged. In this work, we present the data tracing part of the record/replay mechanism that is specifically targeted to record interrupt behavior. To tune our tracing mechanism, we use the observed principle of return address clustering and a formal model for quantitative reasoning about the tracing mechanism. The presented heuristic and mechanisms show surprisingly good results\–-up to an 800 percent speedup on the selector function and a 300 percent reduction on duplicates for non-optimal selector functions\–-considering the leanness of the approach.

}, keywords = {debugging, real-time, tracing}, isbn = {978-1-60558-356-3}, doi = {10.1145/1542452.1542471}, url = {http://dl.acm.org/citation.cfm?doid=1542452.1542471}, author = {Giovani Gracioli and Fischmeister, Sebastian} } @inproceedings {47, title = {Compositional Feasibility Analysis of Conditional Real-Time Task Models}, booktitle = {Proc. of the IEEE International Symposium on Object/Component/Service-oriented Real-Time Computing (ISORC)}, year = {2008}, month = {May}, pages = {391{\textendash}398}, address = {Orlando, USA}, abstract = {

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.

}, keywords = {real-time, state-based scheduling}, isbn = {978-0-7695-3132-8}, doi = {10.1109/ISORC.2008.47}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4519608}, author = {Anand, Madhukar and Arvind Easwaran and Fischmeister, Sebastian and Lee, Insup} } @inproceedings {46, title = {Generating Sound and Resource-Aware Code from Hybrid System Models}, booktitle = {Model-Driven Development of Reliable Automotive Services}, year = {2008}, month = {August}, pages = {48{\textendash}66}, address = {San Diego, USA}, abstract = {

Modern real-time embedded systems are complex, distributed, feature-rich applications. Model-based development of real-time embedded systems promises to simplify and accelerate the implementation process. Although there are appropriate models to design such systems and some tools that support automatic code generation from such models, several issues related to ensuring correctness of the implementation with respect to the model remain to be addressed. In this work, we investigate how we can derive sampling rates for distributed real-time systems generated from a hybrid systems model such that there are no switching discrepancies and the resources spent in achieving this are a minimum. Of particular interest are the resulting mode switching semantics and we propose an approach to handle faulty transitions and compute execution rates for minimizing missed transitions. As a guiding example for our approach, we describe a hybrid systems model for vehicle coordination in which one vehicle acts as a leader and a second follows the leader

}, keywords = {charon, hybrid systems, real-time}, isbn = {ISBN: 978-3-540-70929-9}, doi = {10.1007/978-3-540-70930-5_4}, url = {http://dl.acm.org/citation.cfm?id=1422807}, author = {Anand, Madhukar and Kim, Jesung and Fischmeister, Sebastian and Lee, Insup} } @inproceedings {45, title = {Hardware Acceleration for Verifiable, Adaptive Real-Time Communication}, booktitle = {Proc. of the 13th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)}, year = {2008}, month = {September}, pages = {1425{\textendash}1432}, address = {Hamburg, Germany}, abstract = {

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.

}, keywords = {NCM, real-time, state-based scheduling}, isbn = {978-1-4244-1505-2}, doi = {10.1109/ETFA.2008.4638584}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4638584}, author = {Fischmeister, Sebastian and Lee, Insup and Trausmuth, Robert} } @inproceedings {48, title = {A Programmable Arbitration Layer For Adaptive Real-Time Systems}, booktitle = {Proc. of the Intl. Workshop on Adaptive and Reconfigurable Embedded Systems (APRES)}, year = {2008}, month = {April}, pages = {27{\textendash}31}, address = {St. Luis, USA}, abstract = {

Adaptive real-time systems can respond to changes in the environment and thus allow for an extended range of operations and for improved efficiency in the use of system resources. Building such adaptive real-time systems requires flexibility at each layer in the system stack. In this paper, we introduce and discuss our on-going effort to build a programmable arbitration layer. It builds on the Network Code language and enables the developer to program application-specific arbitration mechanisms which optimize bandwidth or encodes specific properties such as data redundancy, collision-free communication, and temporal isolation.

}, keywords = {NCM, real-time, state-based scheduling}, url = {http://www.artist-embedded.org/artist/IMG/pdf/ProceedAPRES08dinA4-final.pdf}, author = {Fischmeister, Sebastian and Trausmuth, Robert} } @inproceedings {43, title = {Composition Techniques for Tree Communication Schedules}, booktitle = {Proc. of the 19th Euromicro Conference on Real-Time Systems (ECRTS)}, year = {2007}, month = {July}, pages = {235{\textendash}246}, address = {Pisa, Italy}, abstract = {

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. Network 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.

}, keywords = {NCM, real-time, state-based scheduling}, doi = {10.1109/ECRTS.2007.88}, author = {Anand, Madhukar and Fischmeister, Sebastian and Lee, Insup} } @inproceedings {42, title = {A Dynamic Scheduling Approach to Designing Flexible Safety-Critical Systems}, booktitle = {Proc. of the 7th Annual ACM Conference on Embedded Software (EMSOFT)}, year = {2007}, month = {October}, pages = {67--74}, address = {Salzburg, Austria}, abstract = {

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. This paper analyses the development of systems that exhibit such level of flexibility, allowing the system configuration to evolve within a well-defined space. Two options are possible, one starting from the typical static approach but introducing choice points that are evaluated only at runtime, and another one starting from an open systems approach but delimiting the space of possible adaptations. The paper follows the latter and presents a specific contribution, namely, the concept of local utilization bound, which supports a fast and efficient schedulability analysis for on-line resource management that assures continued safe operation. Such local bound is derived off-line for the specific set of possible configurations, and can be significantly higher than any generic non-necessary utilization bound such as the well known Liu and Layland\’s bound for Rate-Monotonic scheduling.

}, keywords = {aptivity, real-time}, isbn = {978-1-59593-825-1}, doi = {10.1145/1289927.1289942}, url = {http://dl.acm.org/citation.cfm?id=1289942}, author = {Luis Almeida and Anand, Madhukar and Fischmeister, Sebastian and Lee, Insup} } @inbook {44, title = {Temporal Control in Real-Time Systems: Languages and Systems}, booktitle = {Handbook of Real-Time and Embedded Systems}, year = {2007}, pages = {10-1 to 10-18}, publisher = {CRC Press}, organization = {CRC Press}, chapter = {10}, abstract = {

Temporal control is an important concept for real-time systems, and several systems and languages provide means for setting temporal constrains on the program. However, the way temporal constraints are placed on the program, the granularity, and the supported kinds of temporal constraints differ from system to system. This chapter provides an introduction to temporal control in real-time systems on the basis of temporal constraints. First, it introduces the notion and nature of a temporal constraint and presents a generic model of the task life cycle. Second, it discusses six different systems and languages with temporal control by adapting the generic model to the individual system and by presenting a short example of a stopwatch task. Finally and third, a summary and discussion of the differences among these systems conclude the chapter.

}, keywords = {real-time}, isbn = {9781584886785}, url = {http://www.crcpress.com/product/isbn/9781584886785}, author = {Fischmeister, Sebastian and Lee, Insup} } @article {41, title = {A Verifiable Language for Programming Real-Time Communication Schedules}, journal = {IEEE Transactions on Computers}, volume = {56}, year = {2007}, month = {11/2007}, pages = {1505 - 1519}, keywords = {network code}, issn = {0018-9340}, doi = {10.1109/TC.2007.70747}, author = {Fischmeister, Sebastian and Sokolsky, Oleg and Lee, Insup} } @inproceedings {37, title = {An Analysis Framework for Network-Code Programs}, booktitle = {Proc. of the ACM \& IEEE International Conference on Embedded Software (EMSOFT)}, year = {2006}, month = {October}, pages = {122{\textendash}131}, address = {Seoul, South Korea}, abstract = {

Distributed real-time systems require a predictable and verifiable mechanism to control the communication medium. Current real-time communication protocols are typically independent 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 flexible 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 flexibility also incurrs 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 benefits. 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.

}, keywords = {NCM, real-time, state-based scheduling}, isbn = {1-59593-542-8}, doi = {10.1145/1176887.1176905}, url = {http://dl.acm.org/citation.cfm?id=1176905}, author = {Anand, Madhukar and Fischmeister, Sebastian and Lee, Insup} } @inproceedings {38, title = {Network-Code Machine: Programmable Real-Time Communication Schedules}, booktitle = {Proc. of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2006}, month = {April}, pages = {311{\textendash}324}, address = {San Jose, USA}, abstract = {

Distributed hard real-time systems require guaranteed communication. One common approach is to restrict network access by enforcing a time-division multiple access (TDMA) schedule.The typical data representation of offline-generated TDMA schedules is table-like structures. This representation, however, does not permit applications with dynamic communication demands, because the table-like structure prevents on-the-fly changes during execution. A common approach for applications with dynamic communication behavior is dynamic TDMA schedules. However, such schedules are hard to verify, because they are usually implemented in a programming language, which does not support verification. Network code is a behavioral model for specifying real-time communication schedules. It allows modeling arbitrary time-triggered communication schedules with on-the-fly choices, and it is also apt for formal verification. In this work, we present network code and show how we can use a model checker to verify safety properties such as collision-free communication, schedulability, and guaranteed message reception. We also discuss its implementation in RTLinux and provide performance measurements.

}, keywords = {NCM, real-time, state-based scheduling}, isbn = {0769525164}, doi = {10.1109/RTAS.2006.31}, url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1613346}, author = {Fischmeister, Sebastian and Sokolsky, Oleg and Lee, Insup} } @inproceedings {36, title = {Distributed Code Generation from Hybrid Systems Models for Time-delayed Multirate Systems}, booktitle = {Proc. of the ACM Conference on Embedded Software (EMSOFT)}, year = {2005}, month = {September}, pages = {210{\textendash}213}, address = {New York, USA}, abstract = {

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, and 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.

}, keywords = {charon, hybrid systems, real-time}, isbn = {1-59593-091-4}, doi = {10.1145/1086228.1086267}, url = {http://dl.acm.org/citation.cfm?id=1086267}, author = {Anand, Madhukar and Fischmeister, Sebastian and Kim, Jesung and Lee, Insup} } @inproceedings {33, title = {Multi-Dimensional Schedules for Media-Access Control in Time-Triggered Communication}, booktitle = {Proc. of the IEEE Symposium on Computers and Communications (ISCC)}, year = {2005}, month = {June}, pages = {664--670}, address = {Murcia, Cartagena, Spain}, abstract = {

A shared communication medium is characterized by multiple entities that use this medium by reading and writing from and to it. Write operations on the shared communication medium must be coordinated and collision-avoidance schemes are one technique to achieve this - for example time-division multiple access (TDMA). Common solutions for TDMA include descriptive tables or algorithm-based client/server mechanisms. Yet, they are all limited in their expressiveness: at the beginning of the communication period at most one write operation can be scheduled for a specific time slot. In this work, we propose a system that allows for scheduling several write operations for the same time slot but guarantee that at most one will be performed though. It does not deal with scheduling algorithms per se, it deals with describing and implementing a computed schedule. The consequences of this added expressiveness allow for parallel and stateful communication schedules merged and serialized in an ad-hoc way. The contribution is the proposed more expressive yet still value and time-deterministic way of describing communication schedules for time-triggered communication plus a description of its implementation in an interpreter implemented as infrastructure in RTLinuxPro.

}, keywords = {NCM, real-time, state-based scheduling}, doi = {10.1109/ISCC.2005.48}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1493796}, author = {Fischmeister, Sebastian} } @inproceedings {34, title = {Non-blocking Deterministic Replacement of Functionality, Timing, and Data-Flow for Hard Real-Time Systems at Runtime}, booktitle = {Proc. of the Euromicro Conference on Real-Time Systems (ECRTS)}, year = {2005}, month = {July}, pages = {106--114}, address = {Las Palmas, Spain}, abstract = {

Embedded systems are usually an integral component of a larger system and are used to control and/or directly monitor this system by using special hardware devices. The complexity of the whole system, which the embedded control system monitors, increases steadily. Consequently, the initial version of the control software that is used at the time of deployment may be inadequate and may need to be updated. Often this requires the whole system to be shut down to have the software replaced. This is not a desirable solution. In this work, we propose a non-blocking mechanism embedded into an infrastructure for RTLinuxPro for determin- istic replacement of system functionality, task timing, and data-flow for hard real-time systems. We explain the mechanism, discuss its implementation using RTLinuxPro, and present a case study of a stop watch in which we replace single functionality and timing behavior at runtime without compromising the timeliness of tasks or the correctness of the output values. The contribution is to show how such a mechanism can work, how it can be implemented, and what problems arise in multi-mode real-time applications.

}, keywords = {adaptivity, real-time}, isbn = {0-7695-2400-1}, doi = {10.1109/ECRTS.2005.20}, url = {http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=01508452}, author = {Fischmeister, Sebastian and Klemens Winkler} } @inproceedings {35, title = {Towards Efficient Use of Shared Communication Media in the Timed Model}, booktitle = {Proc. of the 11th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)}, year = {2005}, month = {March}, pages = {342{\textendash}351}, address = {San Francisco, USA}, abstract = {

Embedded computers are increasingly tighter integrated with each other forming distributed embedded systems that interact through a shared communication medium. Often these embedded systems perform services for safety-critical operations that require deterministic computation and predictable communication. However, since these systems are embedded, they must cope with limited resources. One fundamental challenge is to make efficient use of the shared communication medium, especially in the timed model, in which communication tends to cumulate at the end of harmonic periods of tasks. In this article, we present an approach that uses Micro-tasks for splitting computation and communication into several sequentially executed steps to allow for better balanced load on the communication medium in the timed model. We discuss the approach and describe its implementation in OSEK/Works with TTCAN.

}, keywords = {distributed LET, modecs, real-time}, isbn = {0-7695-2302-1}, doi = {10.1109/RTAS.2005.57}, url = {http://dl.acm.org/citation.cfm?id=1049923}, author = {Guido Menkhaus and Fischmeister, Sebastian and Michael Holzmann and Claudiu Farcas} } @inproceedings {31, title = {Adaptation for Device-independent Authoring}, booktitle = {Developing User Interfaces with XML: Advances on User Interface Description Languages Workshop at Advanced Visual Interface (AVI)}, year = {2004}, address = {Gallipoli, Italy}, abstract = {

The impact of device independent authoring on software engineering manifests itself mainly at the middleware level. Until recently middleware platforms were targeted at vertical coverage of specific scenarios. Consumer devices with integrated Internet-access are becoming more popular and their diversity grows with their market penetration and with the extension of the mobile communication infrastructure. This requires software architectures that are capable of supporting horizontal coverage of a wide range of devices and scenarios. This paper presents the Multi User Interface, Single Application project. It provides a feasable approach for multiplatform support through the introduction of an adaptable and abstract interaction-oriented user interface language.

}, keywords = {coding, Device Independent Authoring, User Interface Adaptation, xml}, doi = {10.1.1.2.7282}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.7282}, author = {Guido Menkhaus and Fischmeister, Sebastian} } @inbook {30, title = {EmBase: Strength, Weakness, Opportunities, and Threats Analysis}, booktitle = {Embedded Systems Knowledge Base {\textendash} Austria and Surrounding Regions}, volume = {182}, year = {2004}, pages = {61{\textendash}75}, publisher = {Austrian Computer Society}, organization = {Austrian Computer Society}, keywords = {embase, real-time}, author = {Barbara Birke and Klaus-Michael Koch and Fischmeister, Sebastian and Helmut Hafner and Daniel Karlsson}, editor = {Fischmeister, Sebastian} } @book {29, title = {Embedded Systems Knowledge Base --- Austria and Surrounding Regions}, series = {OCG-Schriftenreihe}, volume = {182}, year = {2004}, pages = {200}, publisher = {Austrian Computer Society}, organization = {Austrian Computer Society}, keywords = {embase, real-time}, author = {Fischmeister, Sebastian} } @inbook {28, title = {Research Directions in Embedded Systems}, booktitle = {EmBase News as Web Portal}, volume = {182}, year = {2004}, pages = {75{\textendash}93}, publisher = {Austrian Computer Society}, organization = {Austrian Computer Society}, keywords = {embase, real-time}, author = {Emilia Coste and Claudiu Farcas and Fischmeister, Sebastian and Wolfgang Pree} } @inproceedings {27, title = {Task Sequencing for Optimizing the Computation Cycle in a Timed Computation Model}, booktitle = {Proceedings of the International Digital Avionics Systems Conference (DASC)}, year = {2004}, month = {October}, publisher = {IEEE Press}, organization = {IEEE Press}, address = {Salt Lake City, UT, USA}, abstract = {

Recent developments in embedded control systems promote the timed computation model following the principles of logical execution time (LET). Resulting control applications are time deterministic, value deterministic, and their properties may be subject to formal verification against a mathematical model of the control design. However, the timed computation model introduces inefficiencies to computation cycles. As the LET of a real-time control task requires being greater than its worst-case execution time and computed values are always propagated at the end of the LET, actuator updates are unnecessarily delayed. This makes the control cycle less responsive. In this paper, we present an approach that allows the definition of task sequences for a timed computation model implemented by the timing definition language (TDL). Task sequences help minimizing timing delays between sensor readings and actuator updates (e.g., in estimator-based control systems), managing startup and shutdown phases of control systems, and providing mechanisms for error-detection in fault-tolerant systems.

}, keywords = {control systems, distributed LET, modecs, real-time, timed computation model}, isbn = {0-7803-8539-X}, doi = {10.1109/DASC.2004.1390783}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1390783}, author = {Fischmeister, Sebastian and Guido Menkhaus} } @inproceedings {26, title = {Time-triggered Communication for Distributed Control Applications in a Timed Computation Model}, booktitle = {23rd International Digital Avionics Systems Conference (DASC)}, year = {2004}, month = {October}, publisher = {IEEE Press}, organization = {IEEE Press}, address = {Salt Lake City, USA}, abstract = {

Distributed real-time control applications consist of sets of tasks that interact with the physical world through sensors and actuators and are executed on a dispersed set of locations that are interconnected by a communication subsystem. Timeliness and safety requirements of the application demand deterministic execution of tasks and predictive communication. Deterministic and predictable systems can be build, and if upper bounds for processing and communication latencies are known and event arrivals have deterministic distributions. In this paper we describe the timing definition language (TDL) system architecture implementing time-triggered computation and time-triggered communication. The TDL system implements the timed computation model and its architecture consists of two parts: TDL-Exe (for time and value deterministic execution of tasks) and TDL-Com (for predictive communication of values). The paper presents TDL-Exe and describes implementation details of TDL-Com.

}, keywords = {distributed LET, modecs, real-time control systems, system architecture, time-triggered communication, timed computation model}, isbn = {0-7803-8539-X}, doi = {10.1109/DASC.2004.1390786}, url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1390786}, author = {Guido Menkhaus and Michael Holzmann and Fischmeister, Sebastian} } @inbook {32, title = {Web-Service basierte Software (Web-Services)}, booktitle = {Software Engineering}, year = {2004}, pages = {217{\textendash}237}, publisher = {Hanser Verlag}, organization = {Hanser Verlag}, edition = {3rd}, keywords = {web services}, author = {Fischmeister, Sebastian} } @inproceedings {24, title = {Dialog Model Clustering for User Interface Adaptation}, booktitle = {Proceedings of the International Conference on Web Engineering}, year = {2003}, month = {June}, publisher = {Springer-Verlag Heidelberg}, organization = {Springer-Verlag Heidelberg}, address = {Oviedo, Spain}, abstract = {

In recent years, the dramatic growth of the PDA and mobile phone market demonstrates that users are willing to be constrained to small displays, limited storage and battery life, slow CPU speeds and data transfer, in the hope of achieving truly portable access to electronic data. Most of the limitations that users experience with current devices will disappear in future generations. These changes will not have an e ect on the primary user interface constraint: the display size. The actual screen size will not change, since users demand devices that can be easily carried around and held in one hand. The article presents a hybrid approach to the generation of adaptive UIs based on a linking strategy of hierarchies of graphs. The nodes of this graph consist of clustered UI elements.

}, keywords = {adaptive UI}, isbn = {3-540-40522-4}, url = {http://dl.acm.org/citation.cfm?id=1758300}, author = {Guido Menkhaus and Fischmeister, Sebastian} } @inproceedings {23, title = {Embedded Systems Knowledge Base}, booktitle = {Proc. of the 3rd International Conference on Knowledge Management}, year = {2003}, month = {September}, publisher = {J.UCS Journal of Universal Computer Science}, organization = {J.UCS Journal of Universal Computer Science}, address = {Graz, Austria}, abstract = {

Embedded systems play an increasingly important role in today\’s society. The spectrum of embedded systems ranges, for example, from mobile phones to X-by-wire control systems in cars and airplanes. The regional embedded systems knowledge base, called EmBase, is a comprehensive project which investigates and maps the knowledgebase in embedded systems with a focus on Austria and Central Europe. EmBase supports individuals, private and public institutions and companies that implement, develop, support, purchase or sell embedded systems so that they can successfully identify key market trends and directions and align themselves and their activities with these trends.

}, keywords = {embase, real-time}, url = {http://i-know.tugraz.at/blog/2003/11/embedded-systems-knowledge-base}, author = {Klaus-Michael Koch and Monja Loge and Wolfgang Pree and Fischmeister, Sebastian} } @inproceedings {22, title = {Evaluation of User Interface Transcoding Systems}, booktitle = {Proc. of the 7th World Multiconference on Systemics, Cybernetics and Informatics}, year = {2003}, month = {July}, address = {Orlando, Florida, USA}, abstract = {

Users access the Web through an increasingly diverse set of devices, such as mobile telephones, personal digital assistants, notebooks and tablet PCs. Services and content need to be accessible by anyone, anywhere, anytime, and anyhow. Device independent authoring is the goal of service providers. This paper presents an abstract model in form of a finite state machine (FSM). The FSM is the basis for the comparison of user interface transcoding systems (UITS). Based on this abstract model we identify the strengths and weaknesses of these approaches on an architectural level.

}, keywords = {adaptive UI}, doi = {10.1.1.57.9947}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.9947}, author = {Guido Menkhaus and Fischmeister, Sebastian} } @inproceedings {18, title = {Location-Detection Strategies in Pervasive Computing Environments}, booktitle = {Proc. of the IEEE Conference on Pervasive Computing (PERCOM)}, year = {2003}, month = {March}, publisher = {IEEE Press}, organization = {IEEE Press}, address = {Texas, USA}, abstract = {

Pervasive computing environments accommodate interconnected and communicating mobile devices. Mobility is a vital aspect of everyday life and technology must offer support for moving users, objects, and devices. Their growing number has strong implications on the bandwidth of wireless and wired networks. Network bandwidth becomes a scare resource and its efficient use is crucial for the quality of service in pervasive computing. In this article we study process models for detecting location changes of moving objects and their effect on the network bandwidth. We simulate a scenario of pow(10,4) moving objects for a period of pow(10,7) time cycles while monitoring the quality of service with respect to network bandwidth for different location detection strategies. The simulation shows that the class of strategies implementing a synchronous model offers better quality of service than the timed model. We conclude the article with a set of guidelines for the application of the strategies we have investigated.

}, keywords = {location-based systems, mobile shadow}, isbn = {0-7695-1893-1}, doi = {10.1109/PERCOM.2003.1192750}, url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1192750}, author = {Fischmeister, Sebastian and Guido Menkhaus and Alexander Stumpfl} } @article {25, title = {Middleware fuer eingebettete Systeme (Middleware for Embedded Systems)}, journal = {Noeo}, year = {2003}, keywords = {distributed LET, modecs, real-time}, author = {Wolfgang Pree and Fischmeister, Sebastian and Guido Menkhaus and Gerald Stieglbauer} } @article {16, title = {A Comparison of Software Architectures for Location-Based Systems}, year = {2002}, author = {Fischmeister, Sebastian} } @inproceedings {77, title = {Hermes---A Lean M-Commerce Software Platform Utilizing Electronic Signatures}, booktitle = {Proc. of the 35th Hawaiian Conference on System Sciences (HICSS)}, year = {2002}, month = {January}, publisher = {IEEE Computer Society}, organization = {IEEE Computer Society}, address = {Island of Hawaii}, abstract = {

The world-wide growth of the mobile-telephony market opens the door for mobile commerce (m-commerce). For the restricted target platforms used for m-commerce such as mobile phones or personal digital assistants, domain solutions need to be lean but still secure. Especially mobile contracting and mobile payment as parts of m-commerce require solutions resting upon a sound legal basis. Electronic contracts and slips require solutions that are admitted as evidence in court. This is considered a key aspect for m-commerce applications to be widely accepted. This paper presents the Hermes platform developed at the University of Constance. It is a lean and secure trading platform that utilizes digital signatures for authentication conforming with the European electronic-signature laws.

}, keywords = {mobile computing}, doi = {10.1109/HICSS.2002.994536}, url = {http://doi.ieeecomputersociety.org/10.1109/HICSS.2002.994536}, author = {Fischmeister, Sebastian and Gunther Hagleitner and Wolfgang Pree} } @mastersthesis {15, title = {Location Context in Mobile and Pervasive Computing Systems: Technologies, Architectures \& Implementation}, year = {2002}, month = {11/2002}, pages = {146}, school = {University of Salzburg}, type = {mastersmastersphd}, address = {Salzburg}, abstract = {

Technological advances allow manufacturing of smaller and more portable, yet increasingly powerful computing devices, which are equipped with wireless communicating capabilities. The integration of information processing into wirelessly interconnected everyday objects is the primary goal of pervasive computing. A pragmatic variant of the pervasive computing paradigm has been described by IBM chairman Lou Gerstner: a billion people interacting with a million e-businesses through a trillion interconnected intelligent devices. Persons move around, and therefore it is important for such a scenario to operate so that e-businesses and the interconnected devices know where they are and what other objects are in their vicinity. Location information seems crucial information for e-businesses and services. The pervasive environment is strongly interconnected, and the participants profit from this fact by detecting their surroundings and offering proactive service to objects in their vicinity. This work examines the location context in mobile and pervasive computing systems. Thereby, it investigates the impact of mobile and pervasive computing on location-based systems, and especially concentrates on proactive services, i.e., services that act on behalf of the user. To begin, the thesis probes standard locating algorithms and determines their applicability for proactive services. Then, it proposes adaptations to these algorithms through a novel mapping between locations and objects (formalizing the difference between locating and location systems). Next, it presents the proof-of-concept implementation (called Mobile Shadow) in detail to support the claims made in the first part. It starts with presenting the computation and data model for Mobile Shadow. Then, it shows by simulation that the model is sound and that the adaptations are valid and improve the overall quality of service. Finally, it presents implementation details such as the location system and how to create a new service. After presenting the proof-of-concept implementation, this thesis evaluates in detail the software architectures of Mobile Shadow and two more architecture prototypes suitable for location-based systems. Based on this evaluation and the discussion, and the thesis concludes with presenting a set of guidelines for choosing between these three architecture prototypes for developing a location-based system.

}, keywords = {location-based systems, mobile shadow}, author = {Fischmeister, Sebastian} } @inproceedings {14, title = {Mobile Software Agents for Location-based Systems}, booktitle = {Agent Technologies, Infrastructures, Tools, and Applications for E-Services}, year = {2002}, publisher = {Springer-Verlag Heidelberg}, organization = {Springer-Verlag Heidelberg}, abstract = {

As mobile computing matures, location-awareness as part of context-awareness gains more attention - especially, location-aware services for mobile users. This paper concentrates on the software engineering issues of location-aware services and presents Mobile Shadow as an successful example of a design and an implementation of a scalable, fault tolerant, and component-based service infrastructure for location-aware services. The paper presents the basic concepts used in Mobile Shadow, the requirements, and the resulting component architecture.

}, keywords = {location-based systems, mobile computing, mobile shadow}, isbn = {3-540-00742-3}, url = {http://dl.acm.org/citation.cfm?id=1756350}, author = {Fischmeister, Sebastian}, editor = {R. Kowalczyk and J.P. M{\"u}ller and H. Tianfield and R. Unland} } @inproceedings {20, title = {MUSA-Shadow: Concepts, Implementation, and Sample Applications; A Location-Based Service Supporting Multiple Devices}, booktitle = {Proc. of the TOOLS Pacific}, year = {2002}, month = {February}, publisher = {Australian Computer Society Press}, organization = {Australian Computer Society Press}, address = {Sydney, Australia}, abstract = {

The proliferation of mobile devices has refocused interest on location-information exploiting applications. The most prominent problems are the support of devices with widely varying computing and user interface capabilities and a programming model, which promotes the development of location-based services. The article presents the concepts and implementation of MUSA-Shadow, which addresses both issues through a service infrastructure that provides high-level programming abstraction for the development of location-based applications. Furthermore the system introduces novel concepts for user/service interaction via adaptable event graphs and implicit location information via mobile agents.

}, keywords = {adaptive UI, location-based systems, mobile computing, mobile shadow}, isbn = {0-909925-88-7}, url = {http://dl.acm.org/citation.cfm?id=564103}, author = {Fischmeister, Sebastian and Guido Menkhaus and Wolfgang Pree} } @inproceedings {12, title = {Evaluating the Security Of Three Java-Based Mobile Agent Systems}, booktitle = {Mobile Agents}, year = {2001}, address = {Atlanta, USA}, abstract = {

The goal of mobile agent systems is to provide a distributed computing infrastructure supporting applications whose components can move between different execution environments. The design and implementation of mechanisms to relocate computations requires a careful assessment of security issues. If these issues are not addressed properly, mobile agent technology cannot be used to implement real-world applications. This paper describes the initial steps of a research effort to design and implement security middleware for mobile code systems in general and mobile agent systems in particular. This initial phase focused on understanding and evaluating the security mechanisms of existing mobile agent systems. The evaluation was performed by deploying several mobile agents systems in a testbed network, implementing attacks on the systems, and evaluating the results. The long term goal for this research is to develop guidelines for the security analysis of mobile agent systems and to determine if existing systems provide the security abstractions and mechanisms needed to develop real-world applications.

}, keywords = {mobile agents, security}, isbn = {3-540-42952-2}, url = {http://dl.acm.org/citation.cfm?id=732589}, author = {Sebastian Fischmeister and Giovani Vigna and Richard Kemmerer}, editor = {Gian Pietro Picco} } @inproceedings {13, title = {Symbolon---A Novel Concept for Secure E-Commerce}, booktitle = {Towards the E-Society: E-Commerce, E-Business, and E-Government}, year = {2001}, publisher = {Kluwer Academic Publishers}, organization = {Kluwer Academic Publishers}, address = {Z{\"u}rich}, abstract = {

Electronic-banking applications (EBAs) are among the pioneers of electronic-commerce (e-commerce) applications. Like other e-commerce applications, they require sophisticated security mechanisms and intuitive usability so customers put trust in them and therefore use EBAs. Although EBAs have been existing for a long time and their concepts are well understood, current EBAs have severe security and usability restrictions. Also the authors claim that it is necessary to build secure and small e-commerce applications with intuitive usability in order to be able to create complex and still secure ones with good user acceptance. The paper shows the usability and security problems of related technologies and introduces a new approach that is based on asymmetric encryption. The results of the evaluation show that it meets the intended criteria. Finally the work also includes examples that show how this approach can be used to build secure e-business and e-commerce applications while retaining intuitive usability.

}, keywords = {digital signature, mobile computing, security, software architecture}, isbn = {0-7923-7529-7}, url = {http://dl.acm.org/citation.cfm?id=647853.737576}, author = {Sebastian Fischmeister and Gunther Hagleitner and Wolfgang Pree and Gustav Pomberger}, editor = {B. {Schmidt} and K. {Stanoevska-Slabeva} and V. {Tschammer}} } @mastersthesis {11, title = {Building Secure Mobile Agents: The Supervisor-Worker Framework}, year = {2000}, month = {03/2000}, pages = {94}, school = {Technical University Vienna}, type = {masters}, address = {Vienna}, abstract = {

Servers being visited by mobile agents are often a target of an attack. The mobile agent might steal resources, confidential data or use the server as starting point for a new attack. Accordingly many researchers devote their time to this area. However, another main problem of mobile agent security is nearly neglected: the attack of a malicious server against a mobile agent. The server can steal resources and confidential data, too. Due to the fact that the server has in general no access restrictions this problem is even harder to attack. This thesis presents a solution for this particular aspect of mobile agent security: the Supervisor-Worker Framework. The evaluation of the framework and the case study application showed that the framework effectively prevents tampering and eavesdropping and, additionally, boosts several other key aspects of mobile agents.

}, keywords = {mobile agents, mobile computing, security}, author = {Sebastian Fischmeister} } @inproceedings {75, title = {The Supervisor--Worker Pattern}, booktitle = {6th Annual Conference on Patters Languages of Programming (PLOP)}, year = {1999}, address = {Monticello, Illinois}, abstract = {

Mobile agents and mobile computing have grown in importance recently. The Supervisor-Worker pattern is an architectural pattern that helps architects solving the problem of protecting the mobile agent from leakage and tampering. The fundamental Master-Slave Pattern is widespread and heavily used in traditional applications. The Supervisor-Worker pattern inherits many of the Master-Slave pattern\’s benefits. It also solves several of the security issues of mobile agents.

}, keywords = {mobile agents, mobile computing, security}, author = {Sebastian Fischmeister and Wolfgang Lugmayr} }