Cyber-Physical Systems

Two MPI-SWS faculty awarded DFG grants

December 2017
Two MPI-SWS faculty members have received 3-year research grants from DFG, the German Research Organization.

Eva Darulova has received a single-PI DFG grant entitled "Automated Rigorous Verification and Synthesis of Approximations." Björn Brandenburg has received a DFG grant entitled "RT-Proofs: Formal proofs for real-time systems." This award is for a collaborative grant, with co-PIs at INRIA (Grenoble), Verimag (Grenoble), ONERA (Toulouse), and TU Braunschweig (Germany).

Both projects are actively recruiting doctoral students. Interested students can apply online.

Automated Rigorous Verification and Synthesis of Approximations

Computing resources are fundamentally limited and sometimes an exact solution may not even exist. Thus, when implementing real-world systems, approximations are inevitable, as are the errors introduced by them. The magnitude of errors is problem-dependent but higher accuracy generally comes at a cost in terms of memory, energy or runtime, effectively creating an accuracy-efficiency tradeoff. To take advantage of this tradeoff, we need to ensure that the computed results are sufficiently accurate, otherwise we risk disastrously incorrect results or system failures. Unfortunately, the current way of programming with approximations is mostly manual, and consequently costly, error prone and often produces suboptimal results.

The goal of this project is to develop an end-to-end system which approximates numerical programs in an automated and trustworthy fashion. The programmer will be able to write exact high-level code and our `approximating compiler' will generate an efficient implementation satisfying a given accuracy specification. In order to achieve this vision, we will develop novel sound techniques for verifying the accuracy of approximate numerical programs, as well as new synthesis approaches to generate such approximations automatically.

RT-Proofs: Formal proofs for real-time systems

Real-time systems, i.e., computer systems subject to stringent timing constraints, are at the heart of most modern safety-critical technologies, including automotive systems, avionics, robotics, and factory automation, to name just a few prominent domains in which incorrect timing can have potentially catastrophic consequences. To assure the always-correct operation of such systems, i.e., to make sure that they always react in a timely fashion even in a worst-case scenario, rigorous validation efforts are required prior to deployment. However, establishing that all timing constraints are met is far from trivial --- and requires sophisticated analysis techniques --- because software timing varies in complex and difficult to predict ways, e.g., due to scheduling delays, shared resources, or communication, even when executing on a dedicated processor. Unfortunately, the theoretical foundations of current analysis methods are not nearly as rock-solid as one might expect.

The key problem is that the state-of-the-art methods are backed by only informal or abbreviated proofs, which are typically difficult to understand, check, adapt, or reuse. As a result, there is a non-trivial risk of subtle, but fatal mistakes, either lingering in the published literature, or arising when combining results with unstated, inconsistent assumptions. And indeed, this is not just a hypothetical concern --- most famously, the timing analysis of the CAN real-time bus (widely deployed in virtually all modern cars) was refuted in 2007, 13 years after initial publication. Similarly, other lesser-known examples of incorrect worst-case analyses abound in the literature, including off-by-one errors, incorrect generalizations, and even claims that are simply wrong. Worse, even if the underlying theory is indeed flawless, there is still no guarantee that it is actually implemented correctly in the toolchains used in practice. In short, the state of the art in the analysis of safety-critical real-time systems leaves a lot to be desired --- informal "pen and paper" proofs are simply inadequate.

There is a better way: timing analysis results should be formally proved, machine-checkable, and independently verifiable. To this end, the RT-proofs project will lay the foundations for the computer-assisted verification of schedulability analysis results by (i) formalizing foundational real-time concepts using the Coq proof assistant and (ii) mechanizing proofs of busy-window-based end-to-end latency analysis, the analysis approach of greatest practical relevance (e.g., used by SymTA/S). Additionally, we will (iii) demonstrate with a practical prototype how trust in a vendor's toolchain can be established by certifying the produced analysis results (rather than the tool itself). Leading by example, RT-proofs will fundamentally raise the level of rigor, to the benefit of the academic community, tool vendors, and real-time systems engineers in practice.

MPI-SWS researchers win RTAS 2017 Best Paper award

December 2017
Pratyush Patel, Manohar Vanga, and Björn Brandenburg have won the Best Paper award at the 23rd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2017) for their paper entitled "TimerShield: Protecting High-Priority Tasks from Low-Priority Timer Interference".

MPI-SWS paper accepted into RTSS'17

July 2017
The paper entitled "An Exact and Sustainable Analysis of Non-Preemptive Scheduling" by MPI-SWS researchers Mitra Nasri and Björn Brandenburg was accepted into the program of the 38th IEEE Real-Time Systems Symposium (RTSS 2017).

RTSS 2017 will be held from December 6 to December 8 in Paris, France.


MPI-SWS researchers win RTAS 2017 Outstanding Paper award

April 2017
Mitra Nasri and Björn Brandenburg have won an Outstanding Paper award at the 23rd IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2017) for their paper entitled "Offline Equivalence: A Non-Preemptive Scheduling Technique for Resource-Constrained Embedded Real-Time Systems".

Principles of Cyber-Physical Systems Course at TU Kaiserslautern

April 2017
Sadegh Soudjani is teaching Principles of Cyber-physical Systems at the University of Kaiserslautern in Summer 2017.

The course meets Tuesdays 11:45-13:15 and Thursdays 10:00-11:30 in 11-260.

Advanced Automata Theory Course at TU Kaiserslautern

April 2017
Rupak Majumdar and Daniel Neider are co-teaching Advanced Automata Theory at the University of Kaiserslautern in the Summer 2017 semester.

The course meets Tuesdays 08:15-09:45 in room 48-210 and Wednesdays 13:45-15:15 in room 46-280 on the University of Kaiserslautern campus.

MPI-SWS researchers win RTSS 2016 best paper award

December 2016
Björn Brandenburg and Mahircan Gül have won the best paper award at the 37th IEEE Real-Time Systems Symposium (RTSS 2016) for their paper entitled "Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations".

Program Analysis course at TU Kaiserslautern

November 2016
Rayna Dimitrova is teaching Program Analysis at the University of Kaiserslautern in the Winter 2016-17 semester.

The course meets Mondays 17:15-18:45 in room 48-379 on the University of Kaiserslautern campus.

More information about the course

Björn Brandenburg will chair EMSOFT'17

October 2016
Robert de Simone (INRIA) and Björn Brandenburg are co-chairs of the 2017  ACM SIGBED International Conference on Embedded Software (EMSOFT'17), to be held in conjunction with Embedded Systems Week (ESWEEK) from October 15 until October 20 in Seoul, South Korea.

EMSOFT brings together researchers and developers from academia, industry, and government to advance the science, engineering, and technology of embedded software development. Since 2001, EMSOFT has been the premier venue for cutting-edge research in the design and analysis of software that interacts with physical processes, with a long-standing tradition for results on cyber-physical systems, which compose computation, networking, and physical dynamics. See the ESWEEK homepage for further details.

Rupak Majumdar will chair CAV 2017

October 2016
Rupak Majumdar and Viktor Kuncak (EPFL) are co-chairs of the 29th International Conference on Computer-Aided Verification (CAV 2017), to be held between July 22 and 28, 2017 in Heidelberg, Germany.

CAV 2017 is the 29th in a series dedicated to the advancement of the theory and practice of computer-aided formal analysis and synthesis methods for hardware and software systems. The CAV home page has more information.

Two MPI-SWS papers accepted at RTNS'16

September 2016
Two MPI-SWS papers were accepted into the program of the 24th International Conference on Real-Time Networks and Systems (RTNS 2016):
  • Quantifying the Effect of Period Ratios on Schedulability of Rate Monotonic
  • On the Problem of Finding Optimal Harmonic Periods

RTNS 2016 will be held from October 19 to October 21 in Brest, France.

Two MPI-SWS papers accepted into RTSS'16

September 2016
Two papers of MPI-SWS researchers were accepted into the program of the 37th IEEE Real-Time Systems Symposium (RTSS 2016):
  • A Blocking Bound for Nested FIFO Spin Locks
  • Global Scheduling Not Required: Simple, Near-Optimal Multiprocessor Real-Time Scheduling with Semi-Partitioned Reservations
RTSS 2016 will be held from November 29 until December 2 in Porto, Portugal.

MPI-SWS researchers win ECRTS best paper award

July 2016
Felipe Cerqueira, Felix Stutz, and Björn Brandenburg have received the best paper award at ECRTS 2016, for their paper "Prosa: A Case for Readable Mechanized Schedulability Analysis." Read more about Prosa.

Mitra Nasri wins Humboldt fellowship

July 2016
MPI-SWS postdoctoral fellow Mitra Nasri has won a two-year Humboldt postdoctoral fellowship. The fellowship enables highly-qualified scientists from abroad to spend extended periods of research in Germany. Dr. Nasrabadi will be spending her fellowship years with the MPI-SWS Real Time Systems research group.

MPI-SWS student selected to attend Heidelberg Laureate Forum

May 2014
MPI-SWS Ph.D. student Arpan Gujarati has been selected to attend the 2nd annual Heidelberg Laureate Forum in September 2014. An international committee of experts seleted Arpan for one of only 100 spots reserved for young computer scientists from around the world. In addition to participating in the forum, he will be one of 40 students given the opportunity to present his research in a poster session.

The Heidelberg Laureate Forum gives young computer science and math researchers the opportunity to interact with some of the world's top scientists. The speakers for the 2014 Forum, for example, include 14 different Turing Award winners, as well as numerous winners of the Fields Medal and the Abel Prize.

MPI-SWS researchers win SIES best paper award

June 2013
MPI-SWS faculty member Björn Brandenburg and PhD student Alexander Wieder have won the 2013 SIES (IEEE Symposium on Industrial Embedded Systems) Best Paper Award for their paper "Efficient Partitioning of Sporadic Real-Time Tasks with Shared Resources and Spin Locks".

MPI-SWS researchers win ECRTS outstanding paper award

June 2013
MPI-SWS faculty member Björn Brandenburg and PhD students Arpan Gujarati and Felipe Cerqueira have won a 2013 ECRTS Outstanding Paper Award for their paper "Schedulability Analysis of the Linux Push and Pull Scheduler with Arbitrary Processor Affinities."

Björn Brandenburg receives EDAA dissertation award

February 2013
MPI-SWS faculty member Björn Brandenburg has won the 2012 EDAA Outstanding Dissertations Award in the category "New directions in embedded system design and embedded software", to be presented at the DATE 2013 conference in March. This marks the third award Brandenburg has received for his dissertation.

Björn Brandenburg receives North American dissertation award

December 2012
Björn Brandenburg, an MPI-SWS faculty member, has been awarded the Council of Graduate Schools/ProQuest Distinguished Dissertation Award in the area of mathematics, physical sciences, and engineering. The award—North America's most prestigious honor for doctoral dissertations—recognizes recent doctoral recipients who have already made unusually significant and original contributions to their fields.

Brandenburg's dissertation, "Scheduling and Locking in Multiprocessor Real-Time Operating Systems," was also selected for the 2012 Linda Dykstra Distinguished Dissertation Award, which recognizes the best dissertation among all graduates in the fields of mathematics, physical sciences, and engineering at the University of North Carolina at Chapel Hill.

Two new faculty to join MPI-SWS

June 2012
We are pleased to announce that two new faculty will join MPI-SWS.


Allen Clement obtained his Ph.D. at the University of Texas at Austin in 2011. Allen's research aims at designing and building systems that continue to work despite the myriad of things that go 'wrong' in deployed systems, including broken components, malicious adversaries, and benign race conditions. His research builds on techniques from distributed systems, security, fault tolerance, and game theory.


Cristian Danescu-Niculescu-Mizil is joining us from Cornell University, where he obtained his PhD in computer science. Cristian's research aims at developing computational frameworks that can lead to a better understanding of human social behavior, by unlocking the unprecedented potential of the large amounts of natural language data generated online. His work tackles problems related to conversational behavior, opinion mining, computational semantics and computational advertising.

Björn Brandenburg wins EMSOFT best paper award

November 2011
MPI-SWS faculty member Björn Brandenburg, along with James H. Anderson (UNC), has received the ACM SIGBED EMSOFT 2011 best paper award for his paper "Real-time resource-sharing under clustered scheduling: mutex, reader-writer, and k-exclusion locks."


Three new faculty to join MPI-SWS

July 2011

We are pleased to announce that three new faculty will join MPI-SWS this fall.

Björn Brandenburg is joining us from the University of North Carolina at Chapel Hill (UNC), where he obtained his Ph.D. in computer science. Björn's research interests include multiprocessor real-time system, real-time synchronization protocols, and operating systems. Björn is the lead designer and developer of LITMUSRT, an extension of the Linux kernel for real-time scheduling and synchronization on multicore platforms.

Deepak Garg is joining us from the Cybersecurity Lab (CyLab) at Carnegie Mellon University, where he was a post-doctoral researcher. He obtained his Ph.D. from Carnegie Mellon's Computer Science Department. His research interests are in the areas of computer security and privacy, formal logic and programming languages. He is specifically interested in logic-based models of secure systems and formal analysis of security properties of systems.

Ruzica Piskac is joining us from EPFL, where she has completed her Ph.D. in computer science. The goal of her research is to make software development easier and software more reliable via automated reasoning techniques. She is specifically interested in decision procedures, their combinations and applications in program verification and software synthesis.

Rupak Majumdar joins the MPI-SWS faculty

June 2010
Rupak Majumdar joins the institute's faculty as a scientific director. Rupak's research interests are in computer-aided verification and control of reactive, real-time, hybrid, and probabilistic systems; software verification and programming languages; and logic and automata theory.

Rupak's research spans the spectrum of formal verification techniques, ranging from theoretical foundations of logic and automata theory to practical software engineering tools that systematically analyze thousands of lines of code for programmer errors. In the field of software model checking, Rupak has made major contributions. Rupak, along with Ranjit Jhala, wrote the the model checker Blast, which is able to analyze over 100,000 lines of code for complex temporal properties. This achievement was a major milestone and proof of feasibility in the field of software verification and led to a flurry of academic and industrial activity in the area.

Rupak joins MPI-SWS from the University of California, Los Angeles, where he was on the faculty of the computer science department. Prior to that, Rupak received his Ph.D. degree in Computer Science from the University of California at Berkeley, and his B.Tech. degree in Computer Science from the Indian Institute of Technology at Kanpur.