Thorium: A Language for Bounded Verification of Dynamic Reactive Objects

Date
2023-10-19
Authors
Baldor, Kevin
Wang, Xiaoyin
Niu, Jianwei
Journal Title
Journal ISSN
Volume Title
Publisher
Association for Computing Machinery
Abstract

Developing reliable reactive software is notoriously difficult – particularly when that software reacts by changing its behavior. Some of this difficulty is inherent; software that must respond to external events as they arrive tends to end up in states that are dependent on the value of that input and its order of arrival. This results in complicated corner cases that can be challenging to recognize. However, we find that some of the complexity is an accident of the features of the programming languages widely used in industry. The loops and subroutines of structured programming are well-suited to data transformation, but poorly capture – and sometimes obscure – the flow of data through reactive programs developed using the inversion-of-control paradigm; an event handler that modifies the data flow tends to be declared closer to the definition of the event that activates it than to the initial definition of the data flow that it modifies. This paper approaches both challenges with a language inspired by the declarative modules of languages SIGNAL and Lustre and the semantics of the SodiumFRP Functional Reactive Programming library with a declarative mechanism for self modification through module substitution. These language features lead to software with a code structure that closely matches the flow of data through the running program and thus makes software easier to understand. Further, we demonstrate how those language features enable a bounded model checking approach that can verify that a reactor meets its requirements or present a counterexample trace, a series of states and inputs that lead to a violation. We analyze the runtime performance of the verifier as a function of model size and trace length.

Description
Keywords
bounded model checking, functional reactive programming
Citation
Baldor, K., Wang, X., & Niu, J. (2023). Thorium: A Language for Bounded Verification of Dynamic Reactive Objects. Paper presented at the 10th ACM SIGPLAN International Workshop on Reactive and Event-Based Languages and Systems, Cascais, Portugal. https://doi.org/10.1145/3623506.3623574
Department
Computer Science