MobilityReadingGroup

Static Deadlock Detection for Concurrent Go by Global Session Graph Synthesis

Nicholas NG, Nobuko YOSHIDA

Go is a programming language developed at Google, with channel-based concurrent features based on CSP. Go can detect global communication deadlocks at runtime when all threads of execution are blocked, but deadlocks in other paths of execution could be undetected. We present a new static analyser for concurrent Go code to find potential communication errors such as communication mismatch and deadlocks at compile time. Our tool extracts the communication operations as session types, which are then converted into Communicating Finite State Machines (CFSMs). Finally, we apply a recent theoretical result on choreography synthesis to generate a global graph representing the overall communication pattern of a concurrent program. If the synthesis is successful, then the program is free from communication errors. We have implemented the technique in a tool, and applied it to analyse common Go concurrency patterns and an open source application with over 700 lines of code.

@inproceedings{NY2016,
  author = {Nicholas Ng and Nobuko Yoshida},
  title = {{Static Deadlock Detection for Concurrent Go by Global Session Graph Synthesis}},
  booktitle = {25th International Conference on Compiler Construction},
  pages = {174--184},
  publisher = {ACM},
  year = 2016
}

@inproceedings{NY2016,
  author = {Nicholas Ng and Nobuko Yoshida},
  title = {{Static Deadlock Detection for Concurrent Go by Global Session Graph Synthesis}},
  booktitle = {25th International Conference on Compiler Construction},
  pages = {174--184},
  publisher = {ACM},
  doi = "10.1145/2892208.2892232",
  year = 2016
}