Skip to main content
main-content
Top

About this book

This book constitutes the proceedings of the 7th International Workshop on Design, Modeling, and Evaluation of Cyber Physical Systems, CyPhy2017, held in conjunction with ESWeek 2017, in Seoul, South Korea, in October 2017.
The 10 papers presented together with 1 extended and 1 invited abstracts in this volume were carefully reviewed and selected from 16 submissions. The conference presents a wide range of domains including robotics; smart homes, vehicles, and buildings; medical implants; and future-generation sensor networks.

Table of Contents

Frontmatter

Keynote

Frontmatter

Nonstandard Static Analysis: Literal Transfer of Deductive Verification Frameworks from Discrete to Hybrid

Abstract
The talk summarizes our series of work [4, 7, 10, 11]. Special thanks are due to my collaborators: Kohei Suenaga (Kyoto University), Swarat Chaudhuri (Rice University), and my (former) students Kengo Kido and Hiroyoshi Sekine (The University of Tokyo).
Ichiro Hasuo

Design

Frontmatter

Local Descent for Temporal Logic Falsification of Cyber-Physical Systems

Abstract
One way to analyze Cyber-Physical Systems is by modeling them as hybrid automata. Since reachability analysis for hybrid nonlinear automata is a very challenging and computationally expensive problem, in practice, engineers try to solve the requirements falsification problem. In one method, the falsification problem is solved by minimizing a robustness metric induced by the requirements. This optimization problem is usually a non-convex non-smooth problem that requires heuristic and analytical guidance to be solved. In this paper, functional gradient descent for hybrid systems is utilized for locally decreasing the robustness metric. The local descent method is combined with Simulated Annealing as a global optimization method to search for unsafe behaviors.
Shakiba Yaghoubi, Georgios Fainekos

Memory Access Pattern-Aware DRAM Controller Design for Mixed-Criticality Systems

Abstract
Mixed-criticality systems integrate tasks with various levels of criticality onto the same hardware platform. Critical tasks require tight bounding of worst case latency at any cost, yet for non-critical tasks it is important to provide high performance as much as possible. In this paper, we take workload-driven approach and propose a novel workload-aware DRAM controller design for mixed-criticality system that can successfully achieve both of the conflicting demands in the presence of memory-intensive workloads. By using bank partitioning and request batching with prioritization, we provide tighter worst case latency bound for critical tasks and high performance and fairness for non-critical tasks. Our evaluation shows that the design achieves maximum 18% of performance improvement.
Jeongyoon Eo, Kang-Wook Kim, Chang-Gun Lee

Increasing Safety by Combining Multiple Declarative Rules in Robotic Perception Systems

Abstract
Advanced cyber-physical systems such as mobile, networked robots are increasingly finding use in everyday society. A critical aspect of mobile robotics is the ability to react to a dynamically changing environment, which imposes significant requirements on the robot perception system. The perception system is key to maintaining safe navigation and operation for the robot and is often considered a safety-critical aspect of the system as a whole. To allow the system to operate in a public area the perception system thus has to be certified. The key issue that we address is how to have safety-compliant systems while keeping implementation transparency high and complexity low. In this paper we present an evaluation of different methods for modelling combinations of simple explicit computer vision rules designed to increase the trustworthiness of the perception system. We utilise the best-performing method, focusing on keeping the models of the perception pipeline transparent and understandable. We find that it is possible to improve the safety of the system with some performance cost, depending on the acceptable risk level.
Johann Thor Mogensen Ingibergsson, Dirk Kraft, Ulrik Pagh Schultz

Simulation

Frontmatter

Template-Based Monte-Carlo Test Generation for Simulink Models

Abstract
In this paper, we propose a Monte-Carlo test generation method that is able to conduct decision, condition and MC/DC coverage testing for practical Simulink models. To generate a test suite efficiently for models with dozens of thousands blocks, we introduce several techniques. Firstly, we propose using templates of input signals, which characterize shapes of entire waveforms of the signals with a few parameters. By using templates, we can easily generate candidate test cases and reduce a search space to plausible one. Secondly, we propose biased sampling framework to get efficiently test cases meeting uncovered objectives. In the framework, a biased distribution generating new candidate test cases is iteratively refined based on fitness values of the previous candidates. We performed two experiments for each of the techniques and confirmed that they are effective enough for Simulink models which cannot be dealt with a de-facto standard tool SLDV.
Takashi Tomita, Daisuke Ishii, Toru Murakami, Shigeki Takeuchi, Toshiaki Aoki

Reliable Simulation and Monitoring of Hybrid Systems Based on Interval Analysis

(Extended Abstract)
Abstract
Hybrid systems serve as a high-level model of cyber-physical systems. Formal methods for hybrid systems have been studied energetically for around three decades and various methods for reachability analysis and approximation of continuous states/behaviors have been proposed (e.g., [1, 8]). Another line of technology, e.g., MATLAB/Simulink and Modelica, has been developed in the simulation of hybrid systems and has driven the rise of model-based development in the industry. While reachability analysis methods aim to analyze whole behaviors of a given system with carefully taking care of numerical computation errors, the latter technology focuses on efficient simulation of an approximated trajectory of a practical model.
Daisuke Ishii, Alexandre Goldsztejn, Naoki Yonezaki

An Integrated Simulation Tool for Computer Architecture and Cyber-Physical Systems

Abstract
Simulating computer architecture as a cyber-physical system has many potential use cases including simulation of side channels and software-in-the-loop modeling and simulation. This paper presents an integrated simulation tool using a computer architecture simulator, gem5 and Ptolemy II. As a case study of this tool, we build a power and thermal model for a DRAM using the proposed tool integration approach where architectural aspects are modeled in gem5 and physical aspects are modeled in Ptolemy II. We also demonstrate simulation results of power and temperature of a DRAM with software benchmarks.
Hokeun Kim, Armin Wasicek, Edward A. Lee

Safe At Any Speed: A Simulation-Based Test Harness for Autonomous Vehicles

Abstract
The testing of Autonomous Vehicles (AVs) requires driving the AV billions of miles under varied scenarios in order to find bugs, accidents and otherwise inappropriate behavior. Because driving a real AV that many miles is too slow and costly, this motivates the use of sophisticated ‘world simulators’, which present the AV’s perception pipeline with realistic input scenes, and present the AV’s control stack with realistic traffic and physics to which to react. Thus the simulator is a crucial piece of any CAD toolchain for AV testing. In this work, we build a test harness for driving an arbitrary AV’s code in a simulated world. We demonstrate this harness by using the game Grand Theft Auto V (GTA) as world simulator for AV testing. Namely, our AV code, for both perception and control, interacts in real-time with the game engine to drive our AV in the GTA world, and we search for weather conditions and AV operating conditions that lead to dangerous situations. This goes beyond the current state-of-the-art where AVs are tested under ideal weather conditions, and lays the ground work for a more comprehensive testing effort. We also propose and demonstrate necessary analyses to validate the simulation results relative to the real world. The results of such analyses allow the designers and verification engineers to weigh the results of simulation-based testing.
Houssam Abbas, Matthew O’Kelly, Alena Rodionova, Rahul Mangharam

Formal Methods

Frontmatter

Switching Delays and the Skorokhod Distance in Incrementally Stable Switched Systems

Abstract
We introduce an approximate bisimulation-based framework that gives an upper bound of the Skorokhod metric between a switched system with delays and its delay-free model. To establish the approximate bisimulation relation, we rely on an incremental stability assumption. We showcase our framework using an example of a boost DC-DC converter. The obtained upper bound of the Skorokhod metric can be used to reduce the reachability analysis (or the safety controller synthesis) of the switched system with delays to that of the delay-free model.
Kengo Kido, Sean Sedwards, Ichiro Hasuo

Formal Analysis of Robotic Cell Injection Systems Using Theorem Proving

Abstract
Cell injection is an approach used for the delivery of small sample substances into a biological cell and is widely used in drug development, gene injection, intracytoplasmic sperm injection (ICSI) and in-virto fertilization (IVF). Robotic cell injection systems provide the automation of the process as opposed to the manual and semi-automated cell injection systems, which require expert operators and involve time consuming processes and also have lower success rates. The automation of the cell injection process is achieved by controlling the injection force and planning the motion of the injection pipette. Traditionally, these systems are analyzed using paper-and-pencil proof and computer simulation methods. However, the former is human-error prone and the later is based on the numerical algorithms, where the approximation of the mathematical expressions introduces inaccuracies in the analysis. Formal methods can overcome these limitations and thus provide an accurate analysis of the cell injection systems. Model checking, i.e., a state-based formal method, has been recently proposed for the analysis of these systems. However, it involves the discretization of the differential equations that are used for modeling the dynamics of the system and thus compromises on the completeness of the analysis of these safety-critical systems. In this paper, we propose to use higher-order-logic theorem proving, a deductive-reasoning based formal method, for the modeling and analysis of the dynamical behaviour of the robotic cell injection systems. The proposed analysis, based on the HOL Light theorem prover, enabled us to identify some discrepancies in the simulation and model checking based analysis of the same robotic cell injection system.
Adnan Rashid, Osman Hasan

Workshop on Embedded and Cyber-Physical Systems Education

Frontmatter

FPGA Based Big Data Accelerator Design in Teaching Computer Architecture and Organization

Abstract
In the past few years big data applications are becoming diverse and ubiquitous. There is a renewed interest in teaching senior level students to be professional in accelerator based computer architecture design and engineering. However, it poses a significant challenge to tutor the students with sufficient knowledge and practical skills in this area. In this paper, we propose a big data accelerator design project implemented on field-programmable gate array (FPGA) in teaching a computer architecture and organization course. The experimental system is carried out on a heterogeneous architecture using Xilinx Virtex 5 development boards. To achieve a modular accelerator implementation, several milestones are set to facilitate the on-time complete of the project. With the assistance of the FPGA-based experiment, most students have obtained a much more comprehensive understanding of the processor architecture and the accelerator design paradigm. Student feedback and survey illustrates the effectiveness and popularity of the FPGA-based project with milestones over simulation based experiments.
Chao Wang, Yuming Cheng, Lei Gong, Bo Wan, Aili Wang, Xi Li, Xuehai Zhou

Backmatter

Additional information

Premium Partner

    image credits