Research

Abstract. A cyber-physical system often consists of distributed multi-rate periodic processes that communicate using message passing; each process owns a local clock not synchronized with others. We call such systems quasi-periodic distributed systems. Traditionally, one would model them using timed automata, thereby having to deal with high-complexity verification problems. Recently, several researchers proposed discrete-time abstractions based on the calendar model to make the verification more tractable. However, even the calendar model contains a notion of time in the form of a global clock. We propose a novel, timeless computation model for quasi-periodic distributed systems to facilitate their verification. The main idea behind our model is to judiciously replace synchronization using a global clock and calendar with synchronization over lengths of message buffers. We introduce a simple domain-specific language for programming of such systems and use it to formalize the semantics of both the calendar and timeless model. Then, we prove that our timeless model is an overapproximation of the calendar model. Finally, we evaluate our timeless model using several benchmarks. [doi] [Paper]

Abstract. Modern geo-replicated data stores provide high availability by relaxing the underlying consistency requirements. Programs layered over such data stores are called weakly consistent programs. Due to the reduced consistency requirements, they exhibit highly nondeterministic behaviors, some of which might violate program invariants. Therefore, implementing correct weakly consistent programs and reasoning about them is challenging. In this paper, we present a systematic scheduling approach that is aware of the underlying consistency model. Our approach dynamically explores all possible program behaviors allowed by the used data store consistency model, and it evaluates program invariants during the exploration. We implement the approach in a prototype model checker for Antidote, which is a causally consistent key-value data store with convergent conflict handling. We evaluate our tool on several benchmarks. The results show that our approach is effective in detecting buggy behaviors in weakly consistent programs. [TechReport] [GitHub] [Paper]

Abstract. Observational determinism is a property that ensures the confidentiality in concurrent programs. It conveys that public variables are independent of private variables during the execution of programs, and the scheduling policy of threads. Different definitions for observational determinism have been proposed. On the other hand, observational determinism is not a standard property and it should be checked over two or more executions of a program. The self-composition approach allows comparing two different copies of a program using a single formula. In this paper, we propose a new specification for the observational determinism security property in linear temporal logic. We also present a general method to create the appropriate program model using the self-composition approach. Both the program model and the observational determinism property are encoded in embedded C codes in PROMELA using the SPIN model checker. The paper also discusses a method for the instrumentation of PROMELA code in order to encode the program model for specifying the observational determinism security property. [doi]