02 Sep 2013

Workshop on Probabilistic and Hybrid System Verification

Pictures

01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 G1 G2 G3 G4 G5 G6

About the Workshop

Formal verification techniques have been successfully applied to complex systems such as Microsoft hardware drivers, airborne software at Airbus and consumer electronic protocols. In this context, the properties a system has to satisfy are often specified in temporal logics. The formal verification approach then verifies whether such property holds on a given system model. As an example, a property could be that the system will never reach a configuration in which two hosts share the same IP address. Formal verification of classical transition systems has received considerable attentions in the past decades: the 2007 Turing award was given to three researchers for their pioneering research in this area.

Quantitative verification is an important extension of the basic approach towards verifying systems involving various quantitative aspects, including randomizations, costs, time, and security metrics. These characteristics are the key ingredients for modeling and analyzing networked, embedded, biological and energy systems.

Verification of probabilistic systems with discrete time and discrete state spaces has first been studied in the nineties by Hansson & Jonsson. Afterwards, researchers have investigated the verification of probabilistic systems with continuous time, with nondeterminism, and various combinations of them. Today there is a very rich body of literature on theories attacking the probabilistic verification problem. Based on these theories many software tools have been developed, which are particularly appealing, as one can use them to model and analyze real life case studies. These tools are at most loosely interconnected, which limits their mutual fertilization.

Hybrid system consists of both discrete components and continuous dynamics: continuous dynamics can represent model the evolution of variables like velocity, distance or temperature, while discrete components are often used to model control effects, like the action of turning on or off the heater. Hybrid systems are very suitable for modeling controllable systems with continuous variables. On the other side, the interplay of random phenomena and continuous real-time control deserves increased attention for instance in wireless sensing and control applications. Thus, probabilistic hybrid systems arise as the genuine modeling formalism for such applications. Recently, probabilistic hybrid systems have been applied to the problem of balancing the energy production and consumption in electric power systems under renewable infeed.

The purpose of this symposium is to identify potential techniques that are the most promising to further pursued for analyzing probabilistic hybrid systems, as well as to coin entirely new techniques. The prospective participants represent the researchers in Germany and China very well, working on the probabilistic hybrid systems spectrum spanning from foundations over algorithms to applications. Due to the selection of invitees, we expect a highly cross-fertilizing atmosphere.

In this workshop, we have altogether 9 institutes from Germany and 12 from China as prospective participants. The central goal of this workshop is to form the nucleus for a research network between China and Germany for researchers in the quantitative verification area. Through the technical program, state-of-the-art knowledge will be exchanged between all the partners. Further, the workshop will create the forum for identifying research topics that both sides are interested in so as to make plans for further collaboration projects.

Local Information

  • Participants outside of Beijing will stay in the hotel Holiday Inn, Building A, No.89 Shuangqing Road, Haidian District, Beijing 100085, P.R. China. A map can be found here. Taking a taxi from the airport to the hotel will cost about 100RMB.
  • The workshop will be held at ISCAS, Institute of Software Chinese Academy of Sciences. Here is information about how to get to ISCAS from the hotel.
  • Organizers: Holger Hermanns (), Naijun Zhan () and Lijun Zhang.
  • Local Organizers: Please feel free to contact one of the following local organizers for assistance: Ernst Moritz Hahn () (+86 132 4019 8152), Naijun Zhan () (+86 138 1046 0251), Lijun Zhang (+86 158 0115 0886)

Program

24th
Session 1 (08:30--10:00): Hybrid Systems I
Martin Leucker Runtime Verification of Hybrid Systems
Fei He () (贺飞) Complete and Learning-based Compositional Verification for Probabilistic Systems
Jiang Liu (刘江) Nonlinear Estimation and Hybrid Verification
Session 2 (10:30--12:00): Probabilistic Verification II
Joost-Pieter Katoen () Automated Analysis of Probabilistic Programs
Peter Buchholz Quantitative Analysis of Systems – Beyond Markov Models
Peng Wu (吴鹏) Towards Model Checking of Probabilistic Timed Automata with REDLIB
Session 3 (13:30--15:00): Safety and Abstractions
Wei Dong (董威) Anticipatory Active Monitoring of Safety-Critical Systems
Liqian Chen (陈立前) Extending octagon abstract domain with absolute value
Jing Liu (刘静)
Xuandong Li (李宣东) Hybrid system: modelling and verification
Session 4 (15:30--17:00): Program Verification
Deepak Kapur Program verification and invariant generation
Marcel Kyas Verification and Validation of Systems with Uncertain Measurements for Position Estimation
Zhengbang Chen (陈振邦) Property Guided Dynamic Symbolic Execution
Mingsheng Ying Floyd-Hoare Logic for Quantum Programs
Yuan Feng () Model Checking quantum Markov chains
25th
Session 1 (08:30--10:00): Hybrid Systems II
Alessandro Abate Computable analysis and control synthesis over complex dynamical systems via formal verification
Zhikun She (佘志坤) Discovering Multiple Lyapunov Functions for Switched hybrid Systems
Naijun Zhan () (詹乃军) Hybrid Hoare Logic
Session 2 (10:30--12:00): Markov Chains
Jan Krcál Compositional Verification and Optimization of Interactive Markov Chains
David N. Jansen () More or less true: DCTL for continuous-time MDPs
Ralf Wimmer () Optimal counterexamples for Markov models
afternoon: excursion (Great Wall)
26th
Session 1 (8:30--10:00): Tools and Applications
Holger Hermanns () From Power Domains to Power Grids
Katinka Wolter Validating retry mechanisms using queuing systems with signals
Bin Gu Embedded systems and cybernation in spacecraft
Haifeng Wang (王海峰) Safety verification of railway train control system
Session 2 (10:30--12:00): Modelling and Verification
Yunwei Dong (董云卫) On Reliability Analysis for Embedded Systems with AADL Behavior Model
Zheng Wang (王政) Runtime verification for periodic control systems
Jidong Lv (吕继东) Model Based safety test case Generation method and its application in train
Meng Sun () (孙猛) Modeling and verification of connectors in complex systems
afternoon: excursion (Hutong tour)
27th
Session 1 (08:30--10:00): Hybrid Systems III
Shaofa Yang (杨绍发) Modular discrete time approximations of distributed hybrid automata
Ernst Moritz Hahn () Rewarding probabilistic hybrid automata
Erika Ábrahám () Reachability analysis for hybrid systems
Session 2 (10:30--12:00): Probabilistic Verification II
Markus Siegle State-of-the-art techniques and tools for performability evaluation
Mirco Tribastone Efficient State-Space Aggregations for Large-Scale Dynamical Systems
Lin Zhao (赵琳) Runtime Checking Temporal Properties of System Hybrid Behaviors
Session 3 (13:30--15:00): Bounded Model Checking
Lei Bu (卜磊) SAT-LP-IIS Joint-Directed Path-Oriented Bounded Reachability Analysis of Linear Hybrid Automata
Miaomiao Zhang (张苗苗) Bounded model checking of duration calculus
Wanwei Liu (刘万伟) Bounded Model Checking of Extended Temporal Logic Cooperating Both Finite and Looping Automata Connectives
Session 4 (15:30--17:00): Probabilistic Verification II
Lijun Zhang (张立军) Probabilistic Model Checking for Linear Temporal Logics
Lei Song Late Weak Bisimularity for Markov Automata
Andrea Turrini The Algorithmics of Probabilistic Automata Weak Bisimulation

Sponsorship

We are grateful to Sino-German Center for their generous sponsorship of this event.