A Program Logic for Concurrent Randomized Programs in the Oblivious Adversary Model

Abstract:

Concurrent randomized programs in the oblivious adversary model are extremely difficult for modular verification because the interaction between threads is very sensitive to the program structure and the execution steps. We propose a new program logic supporting thread-local verification. With a novel "split" mechanism, one can split the state distribution into smaller partitions, and the reasoning can be done based on each partition independently, which allows us to avoid considering different execution paths of branch statements simultaneously. The logic rules are compositional and are natural extensions of their sequential counterparts. Using our program logic, we verify four typical algorithms in the oblivious adversary model.

Authors:

Weijie Fan
Hongjin Liang
Xinyu Feng
Hanru Jiang

Published:

In Proc. 34th European Symposium on Programming (ESOP'25), LNCS 15694, pages 322–348, Hamilton, Canada, May 2025.