Formal Methods in Outer Space : Essays Dedicated to Klaus Havelund on the Occasion of His 65th Birthday

This Festschrift, dedicated to Klaus Havelund on the occasion of his 65th birthday, celebrated in 2021 due to the COVID-19 pandemic, contains papers written by many of his closest friends and collaborators. After work as a software programmer in various Danish companies, Klaus has held research positions at various institutes, including the Danish Datamatics Center, the Ecole Polytechnique, LIP 6 lab in Paris, Aalborg University, and NASA Ames. Since 2006 he has been working in NASA’s Jet Propulsion Laboratory (JPL), the federally funded center managed by Caltech whose primary function is to construct and operate planetary robotic spacecraft. His professional awards include the Turning Goals Into Reality engineering innovation award, the Outstanding Technology Development award, and the JPL Mariner, Ranger, Voyager, and Magellan awards. Klaus has provided constant and generous service to the formal methods community by organizing, participating in, and chairing numerous committees. His academic awards include the 2020 SIGSOFT Impact Paper Award, the RV 2018 Test of Time award, and the ASE 2014 and ASE 2016 Most Influential Paper awards. His research activities have generated more than 100 publications with more than 100 collaborators, cited over 12,000 times. The book title reflects Klaus’s main research and engineering focus throughout his career: formal methods, often applied at NASA. The contributions, which went through a peer-review process, cover a wide spectrum of the topics related to his scientific interests, including programming language design, static analysis, runtime verification, dynamic assurance, and automata learning. Preface 7 Organization 9 Contents 10 Foundations 12 The K Vision for the Future of Programming Language Design and Analysis 13 1 Background 13 2 The Vision of an Ideal Language Framework 14 3 The K Language Framework 16 4 Conclusion 18 References 18 Refining the Safety-Liveness Classification of Temporal Properties According to Realizability 20 1 Introduction 20 1.1 Relating Realizability to Time-Sensitive Requirements Specifications 21 1.2 Content of the Paper 21 2 The System Model 21 2.1 Streams, Time, and Behaviors 21 2.2 Syntactic Interfaces and Interface Behavior 22 3 Temporal System Properties 23 3.1 Bounded and Unbounded System Properties 24 3.2 Safety 24 3.3 Liveness 25 3.4 Refining Safety and Liveness 26 4 Logical Operations on Safety and Liveness Properties 27 4.1 Negation 27 4.2 Conjunction 29 4.3 Disjunction 30 4.4 Approximating Liveness 32 5 Specification by Interface Assertions and Interface Predicates 32 6 Strong Causality and Realizability of Specifications 33 7 Effects of Safety and Liveness onto Realizability 33 8 Liveness Leading to Unrealizability 39 9 Related Work and Conclusion 40 References 41 Static Analysis 42 Domain Analysis and Description – Sorts, Types, Intents 43 1 Motivation 43 1.1 Rôle of Domains 43 1.2 What Are Domains? 43 1.3 Why This Paper? 44 1.4 Ontologies 44 2 Sorts 46 2.1 Physical Parts, Living Species and Structures 46 2.2 Natural Parts and Artefacts 47 2.3 Various Forms of Physical Parts 47 2.4 Analysis and Description Prompts 48 2.5 An Example: Road Transport 49 3 Types 49 3.1 Space and Time 49 3.2 Internal Qualities 51 3.3 Physics Attributes 53 3.4 Artefactual Attributes 57 3.5 Intents 60 4 Actions, Events, Behaviours 63 4.1 Actions 64 4.2 Events 64 4.3 Behaviours 64 4.4 Summary 64 5 Conclusion 64 5.1 Sort Versus Types 65 5.2 Domain Oriented Programming Languages 66 5.3 Attributes of Living Species 66 References 66 Dynamic interval analysis by abstract interpretation⋆ 69 1 Introduction 69 2 Syntax and Trace Semantics of the Programming Language 70 3 Float intervals 74 4 Abstraction of real traces by float interval traces 75 5 Sound over-approximation in the concrete 76 6 Sound over-approximation in the abstract 77 7 Calculational design of the float interval trace semantics 78 8 On floating point computations 84 9 Abstraction to a transition system 85 10 Conclusion 90 References 92 Runtime Verification 95 Runtime Verification: Passing on the Baton 96 1 Introduction 96 2 Runtime Verification: A Very Brief Introduction and History 98 2.1 On Runtime Verification and Monitoring 98 2.2 On the Concept of Monitorability 100 2.3 A Very Brief History of Runtime Verification 101 3 A Hands-On Runtime Verification Course 103 3.1 Introduction to Runtime Verification 103 3.2 Introduction to Monitoring Through Assertions 104 3.3 Instrumenting Monitors 105 3.4 Verification Algorithms 106 3.5 Real-Time Properties 107 3.6 Offline Monitoring 108 3.7 Advanced Topics 109 4 Lecturing Experience 109 5 Conclusions 111 References 111 Hardware-Assisted Online Data Race Detection 115 1 Introduction 115 2 Our Approach and Related Work 117 3 Data Race Detection with COEMS 120 3.1 COEMS Infrastructure 120 3.2 Instrumentation and Data Race Monitoring 121 3.3 Lockset-Based Algorithm in TeSSLa 123 4 Case Study 125 5 Conclusion 130 References 131 Comparing Two Methods for Checking Runtime Properties 134 1 Introduction 134 2 Event Intervals 135 3 Formalization in Interval Logic 135 4 Some Complicating Factors 136 5 A Cobra Script 136 6 Comparison 138 7 Conclusion 139 References 140 Dynamic Assurance 141 Confidence Monitoring and Composition for Dynamic Assurance of Learning-Enabled Autonomous Systems 142 1 Introduction and Motivation 142 2 Problem Statement and Challenges 144 3 Outline of the Approach 146 3.1 Logical Structure of the Assurance Monitor 146 3.2 Assumption Monitors 148 3.3 Composition of Assumption Monitors 149 4 Summary and Discussion 149 References 151 Collision-Free 3D Flocking Using the Distributed Simplex Architecture*-6pt 152 1 Introduction 152 2 Distributed Simplex Architecture 153 2.1 Baseline Controller 154 2.2 Decision Module 155 3 Collision-Free Flocking 155 3.1 Synthesis of Control Barrier Function 156 3.2 Advanced Controller 158 3.3 Experimental Results 159 4 Conclusion 160 References 161 Automata Learning 162 A Context-Free Symbiosis of Runtime Verification and Automata Learning 163 1 Introduction 163 2 Preliminaries and Related Work 166 2.1 Preliminaries 166 2.2 Related Work 170 3 Efficient Context-Free Runtime Monitoring 171 3.1 An SOS-Based SPA Monitor 172 3.2 Correctness and Complexity 173 4 Benchmarks and Performance Evaluation 175 4.1 Experimental Setup 175 4.2 Threats to the Validity of the Experimental Results 176 4.3 Experimental Results 177 5 Conclusion and Future Work 180 References 181 Reverse Engineering Through Automata Learning 186 1 Introduction 186 2 Angluin's L* Learning Algorithm 187 3 Black Box Checking 191 4 Reverse Engineering 192 5 Comparison with Algorithmic Automata Synthesis 194 References 196 Author Index 197