Search papers, labs, and topics across Lattice.
This paper introduces a Flow extension to Coroutine Types, enabling the modeling of coroutines with multiple receiving and yielding operations, which addresses a limitation of prior Coroutine Type systems. The authors develop a type system that maps Go expressions to these extended Coroutine Types to detect potential deadlocks arising from incorrect concurrency usage in Go programs. By reducing the Coroutine Types and checking for a zero result, the system identifies properly paired channel operations, and the approach, integrated with the Z3 SMT solver, recognizes 17 channel/goroutine interaction patterns, outperforming existing deadlock detectors in certain scenarios.
A new type system flags Go concurrency deadlocks that other static and dynamic analyzers miss, by extending Coroutine Types to handle multiple send/receive operations.
Coroutines, as an abstract programming construct, are a generalization of functions that can suspend execution part- way for later resumption. Coroutine Types are behavioral types to model interactions of coroutines with a single receiving operation followed by a single yielding operation. Coroutine Types have been applied to model-driven engineering, smart contracts, and test case generation. We contribute a Flow extension to Coroutine Types, so that coroutines with more than one receiving and yielding operation can be modeled. We accordingly revise the reduction rules of Coroutine Types. To show the usefulness of the Flow extension, we contribute a type system that maps expressions of the Go programming language to Coroutine Types. If the reduction result is 0, the two channel operations are paired properly and the program has no deadlocks. We choose Go because it is a popular programming language for distributed systems, but a frequent kind of bugs in Go is deadlocks due to the wrong use of concurrency features. We concentrate on the most commonly used semantics in Go: unbuffered channels with the keywords go and defer. Our Flow extension and the type system recognize 17 patterns of channels and goroutine interactions, including mismatched receivers and senders, nested goroutines, etc. We also integrate the Z3 SMT solver to take account of conditional execution and type inheritance. Other static or dynamic deadlock detectors crashed or gave wrong predictions in some patterns. Therefore, our type-based deadlock analyzer not only fills the gap in the landscape of value-based detection, but also complements existing detectors.
