日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

How many mutex bugs can a simple analysis
ﬁnd in Go programs?
Fumi Takeuchi

Hidehiko Masuhara

Youyou Cong

Keisuke Ishibashi

Raﬃ Khatchadourian

In open source software, it is known that there are many concurrency bugs. A previous study in Go
revealed that a considerable number of such bugs are simple (for example, 9% of the bugs are the ones
that forget to unlock a mutex,) through a manual program investigation. This paper tries to detect suchbugs by applying a simple analysis in order to see how far such a tool can match the manual analysis.
We built a simple intraprocedural control ﬂow analysis in Go, and evaluated its performance with respect
to the open source programs with concurrency bugs reported in the previous study. Consequently, as for
quality, the recall is good at 88% and the precision is poor at 60%, and as for analysis time, it can beﬁnished within practical amount of time (for example, 1 second per 5000 LoC).

the error handling case.

1 Introduction

Among many languages, the Go programming

Forgetting to unlock mutual exclusion (here-language (hereinafter referred to as Go) programs

inafter referred to as mutex) is one of the ma-seems to have many mutex bugs. Like the casejor root cause of bugs dealing with mutex. Thisof [27], mutex bugs can be found around error

bugs will lead to deadlock errors by waiting for re-handling, since programmers need to unlock mu-

sources forgotten to be released which will nevertex at both of the main functionality and er-

be available. We call this bugs as mutex bugs, andror handling.

forgotten unlock as missing unlock.

try-catch-finally exception handling, program-If a language has the feature of

Mutex bugs sometimes lead to serious and fatal

mers can put unlocks together in finally clause.

errors in software. For example, [27] is a mutex

Nevertheless, Go intentionally omit this style ex-

bug found in MariaDB recently which will cause

ception handling system [9].

denial of service fatal error. The cause of [27] wasPrevious study [48] shows that considerable

that acquired mutex was not released correctly inamout (about 9%) of bugs which will lead to deadlock error are mutex bugs. This study was con-

制御フロー解析を用いた排他制御誤り検出器の作成と Go
言語製オープンソースソフトウェアに対する有効性検証
竹内 史 増原 英彦 叢 悠悠, 東京工業大学 数理・計算科学系, Tokyo Institute of Technology.

Raﬃ Khatchadourian, ニューヨーク市立大学 (CUNY)
ハンター校, City University of New York (CUNY)
Hunter College.
石橋 圭介, 国際基督教大学, International Christian
University.

ducted by the manual investigation on real-worldopen source software (hereinafter referred to as
OSS) written in Go.
We aim to propose a mutex bugs checker to see
how frequent those bugs appear in real world Go
programs. In this paper, mutex bugs checker madewith control ﬂow analysis is shown in Section 3

and its evaluation regarding the quality and thewhich increment V. Here, increment operation is

performance is illustrated in Section 5.

done by loading from the memory, adding 1 to thePrevious studies enable the detection and auto-

value, and then writing the result to the mem-mated ﬁx, by using session graphs [43], behavioral

ory. The expected result value of V is 2 since ittypes [38] [39], novel constraints solver [41], mod-is incremented two times. However, A and B areeling Go’s communication between processes [45],done concurrently, it is possible that loading in A

none of the above studies did investigate the pos-is done between loading in B and writing in B.

sibility of a simple analysis, whose analysis could

In this case, both A and B write 1 to the V, andbe ﬁnished faster.

this is called a race condition. Troublesomely, race

2 Backgroundcondition does not happen every time. In the pre-2. 1 Go and Concurrency

vious example, it is also the case that A is done af-

To deal with concurrency, it is essential to con-ter the writing operation of B, which results in nosider how to synchronize each process at somerace conditions. Thereby, to eliminate the possi-

point. Concurrent programs consist of two parts,

bility of race conditions, mutex is used. According

one is the point that is needed to run syn-to [42], mutex has two states, locked and unlocked,

chronously, and the other is the point that canand two operations, lock and unlock. Each opera-

be run simultaneously since each process does nottion is done atomically, thus a process has to wait

depend on the other [42]. The latter one is called

to possess the lock of mutex from locked mutex

embarrassingly parallel, and for concurrent pro-by the other process to be unlocked. Therefore,grams, the method to deal with the former is sig-

for the above example, by wrapping lock and un-

niﬁcant. In fact, many techniques are proposed tolock to the same mutex object each increment inturn the former part into the embarrassingly par-A an B, the race condition is resolved and always

allel, and it is better to do so if it can be, but inthe result V becomes 2. Besides, the part which

Go, the former case can be seen a lot, so this paper

must be protected due to race condition is calledfocuses on that.

a critical section.

In Go, there are two commonly used methods

However, since processes cannot go through theto deal with concurrency. One is mutual exclusion

critical section until the lock is released, if one(hereinafter referred to as mutex), and the otherprocess forgets to release the lock, every process

is channel. Mutex is a well-known method often

cannot proceed. This is called a deadlock error.

used in other languages while channel is not.

Actually Go has two types of deadlocks: one is a
global deadlock, and the other is a partial dead-

2. 2 Mutex

lock. Global deadlock means all the processes are

Mutex is a well-known and low-level mechanism

halted, on the other hand, partial deadlock indi-

for concurrency to exclude race conditions. Racecates some of the processes are halted.

condition happens when concurrent processes operate the same memory without synchronizationand if one of them is the write operation [42]. For

2. 3 Channel
Channel is like a stream with buﬀers to com-example, suppose there are one global variable V

municate between processes.

and two processes executed concurrently A and B

Communication Sequential Processes [34] (here-

Based on Hoare’sinafter called CSP), channel is brought to Go.

1// F returns the position of 0

As Hoare described in [34], input and output be-2// in the given lisrt.

tween processes are the primitives of communica-3// If no 0 in list, then return4// the length of the list.

5

func F(list []int) int {and receive values between processes. Originally

6

fmt.Println("start")in [34], transceiving is done directly from and to7

counter := 0

processes, however, he also considered communi-

8for _, l := range list {9

fmt.Println("check", l)

10

if l == 0 {tions, and he illustrates communication as send

cating through a port, a sort of variable for input
and output like a stream.

fmt.Println("0 found", counter)

11

break

12

2. 4 Go and Static Analysis
In Go, static code analysis tools are often used.
One example is a lint tool called go fmt (or gofmt)}

13

counter++

14
15

}

16

fmt.Println("end")[8]. Go oﬃcially provides go fmt command for the17

sake of formatting codes. Thanks to this static

18

return counter}

analysis tool, the number of conﬂicts over coding
styles might be fewer than other languages since
Go programmers can delegate it to the standard[46]. The other example is go vet [18]. As thedescription in [18] says, go vet command reports
common mistakes in a heuristical way by analyzing code statically.

The code in Listing 1 contains some conditional
branches. On line 6, if iteration over list has
not done, the body of for loop (hereinafter called
range.body) will be executed.

Otherwise afterline 14 (hereinafter called range.done) will be executed. And on line 8, there is a if statement
dependent on the condition of the current list

2. 5 Control Flow Analysis
To analyze programs statically, it is needed toknow in what order the program will be executed.
To have this information, Control Flow Graph(hereinafter called CFG) represents the order ofthe program execution.
CFG is a directed graph that consists of basic

item l in the iteration. If the condition holds,
break will be executed subsequently, so the successor of this if body (hereinafter called if.then isrange.done.
And Figure 1 represents the CFG of Listing 1.
Each node consists of the fragment of linearly sequential processes †1 .

blocks which are composed of a linear sequence ofa fragment of a program [28]. In short, a part ofa program whose order of execution depends on
condition is expressed as a path, while a part ofa program that has immutable order is expressed
as a vertex. The example code in Go and its CFG
are shown in Listing 1 and Figure 1.
Listing 1

Example Code for CFG

2. 6 Strongly Connected Components
In a directed graph, if the subgraph of it consists of vertices that are reachable from any othervertices, the region is estimated as strongly con†1 Depending on the implementation of CFG builder,
the computation for conditions (such as l == 0 in the
Listing 1) are sometimes included in successive nodes(here means 4 if.then instead of 2 range.body), but inthis paper, regarding it as included in its predecessor.

0 entry
fmt.Println("start")
counter := 0
, l := range list
3 range.done
1 range.loop
fmt.Println("end")
return counter2 range.body

4 if.thenfmt.Println("check", l)l == 0

fmt.Println("0 found", counter)

5 if.done
counter++
図1

CFG of Listing 1

nected [28]. This is important for analysis since4

this represents a loop in CFG. In the above ex-5}ample Figure 1, the components which can be es-

6mu.Unlock()timated as strongly connected are 1, 2, and 5, as

return7

for _, l := range list {8

shown in Figure 2 with enclosed by the red dashed

9mu.Lock()

frame.

10

if l == 0 {By seeing strongly connected components (hereinafter referred to as SCC) as a block, this graphcontinue

11
12

}

13

if l == 1 {can be assessed as a directed acyclic graph (here-

14

inafter called DAG).

15

break
}
mu.Unlock()16

3 Methodology

}

17
18

}

1

func _(mu *sync.Mutex, cond bool, list []To check mutex bugs, our checker attempts toﬁnd missing unlocks, in other words, the position
Listing 3

that locks may be called without unlocked. Listing 2 shows the Go code contaning mutex bugs,
while Listing 3 is the ﬁxed version of Listing 2.

int) {
mu.Lock()

2

The Listing 3 illustrates three patterns of the miss-3

ing unlock positions.

4

if cond {+mu.Unlock()return5

Listing 2
1int) {
2
3

Go Code with Mutex Bugs

func _(mu *sync.Mutex, cond bool, list []mu.Lock()
if cond {Fixed code of Listing 2

6

}

7

mu.Unlock()89

for _, l := range list {10

mu.Lock()

11

if l == 0 {0 entry
fmt.Println("start")
counter := 0
, l := range list
3 range.done
1 range.loop
fmt.Println("end")
return counter2 range.body

4 if.thenfmt.Println("check", l)l == 0

fmt.Println("0 found", counter)

5 if.done
counter++
図2

12

+

Pseudo code of checker’s common
algorithm by DFS

}

14

1

if l == 1 {

15

+

17

2

block: CFG’s block,3

lockstate: hashmap of boolean,

break

4

report: procedure which require block and}

19

mu.Unlock()lockstate,
5

}

20

Require:mu.Unlock()18

21

Listing 4

mu.Unlock()continue

13

16

CFG of Listing 1 with a Red Dashed Frame of Strongly Connected Components}

6

procedure DFS(block, lockstate, report)

7

for each node in block’s AST nodes

8

if node is an operation to a mutex

each function declaration including methods and9mu = the operated mutex object

anonymous functions.

10

if operation is lockTo check mutex bugs, ﬁrstly CFG built on

Since the analysis strat-

object11

egy is intraprocedural, CFG builder does not trace

12

lockstate[mu] = trueelse if operation is unlock

function calls inside function declaration. In brief,13

the checker interprets a project as a cluster of

14

many CFGs.

15

end if16

end forAfter CFGs are constructed, thechecker traverses each CFG by DFS. At each DFS

17

step, lock and unlock operations for each mutex

18

object are recorded (corresponding to lockstate

19

in Listing 4). Then current CFG block is deter-

20

mined as containing mutex bugs or not (corre-

21
22

sponding to report procedure call in Listing 4).

lockstate[mu] = false
end if23

report(block, lockstate)for each succ of block
DFS(succ, copy of lockstate, report)
end forend procedure

The whole speciﬁcation of the procedure is shownin Listing 4.

The report function tries to ﬁnd three types ofpatterns, one is missing unlock reporter before re-0 entry

turn, another is the checker for lock-unlock consistency in a loop, and the other is the missing unlock reporter before exiting from a loop by break.
1 if.done

These reporters are run sequentially and some2

times report the same missing unlock. If the reports are the same suggestion, it must be reported

2 if.then

図3

only one of them.

CFG of Listing 5 with a Blue Doubled
Frame For the Block to be Reported

If any mutex objects’ lockstate are true and the(corresponding AST Nodes are abbreviated)block does not have any successors, it should bereported at the block since it means releasing ofcontinue is executed, acquirement for the lock of

the mutex object’s lock is not done before exiting

mu on line 3 will be executed, although it causes

from the function. For example, in Listing 5, on

deadlock since it is not unlocked.

line 4, the mutex object mu has been locked but
not released before exiting from the function.

Listing 6
1

Listing 5
1

Missing Unlock Before Returnfunc _(mu *sync.Mutex, cond bool) {2

mu.Lock()

3

if cond {7

if l == 0 {continue}mu.Unlock()
}

8
9

}

And in Figure 3, the CFG of Listing 5 is shown.
As it indicates exiting block (block 1 and 2) fromthe function does not have any successors, so it
can be reported. In those two, block 2 does nothave unlock call for mu, therefore it must be reported. Additionally for the automated ﬁx, unlock
call for mu must be inserted at the last position before return of AST nodes in block 2.
If any mutex objects’ lockstate is true, the current block’s successor is a loop entrance (likerange.loop or for.loop), and the lock is acquiredin the SCC which includes the loop entrance, it
must be reported.

mu.Lock()

4

7

mu.Unlock()

6

3

6

}

5

for _, l := range list {2

5

return4

For instance, Listing 6 andMissing Unlock in the Last of Loopfunc _(mu *sync.Mutex, list []int) {}If any mutex objects’ lockstate is true, the current block is the bridge from an SCC, and all thepredecessors of the successors of the current block
except the current block are in the same SCC, it
must be a break from a loop without unlocking.
As an example, Listing 7 and its CFG in Figure 5
represents the error captured by this algorithm.
On line 5 break from a loop is executed without
unlocking the mu mutex, therefore if mu lock is tried
to be acquired in other functions or somewhere in
the same function, it will be a deadlock error.
Listing 7
1

Missing Unlock in the Last of Loopfunc _(mu *sync.Mutex, list []int) {corresponding CFG given in Figure 4 contains a2

missing unlock in if.then block, since on line 5

3

mu.Lock()

continue is executed without unlock for mu. If

4

if {

for _, l := range list {0 entry

1 range.loop

2 range.body

4 if.then

5 if.done

3 range.done
図4

CFG of Listing 6 with a Red Dashed Frame of Strongly Connected Components and a Blue

Doubled Frame For the Block to be Reported (corresponding AST Nodes are abbreviated)
break

5

However, [5] does not have the position informa-

6}tion corresponding to blocks. AST nodes in blocks

7

mu.Unlock()know their position in source code, but if a block

}

8
9

}

does not have any AST nodes, there is no way toidentify the block’s position, though the position
data are required to report or insert release calls

4 Implementation

to developers.

To implement simple analysis checker and auto-

For this reason, we decided to fork the ctrlflow

mated ﬁx tool in Go, commonly analysis package

package [5] to supplement position information to[1] is used as mentioned in Section 2. Additionally,

blocks. By virtue of this fork, for example, reportprevious studies use external languages or toolsof break like in Listing 7 was realized, since with-like C++ [41] or Haskella and mCRL2 [39] [44],out position data the if then block have no AST

but this paper only uses Go and Go libraries tonodes which are required to report.

make the installation process as easy as possible.

In terms of the limitation of using this package,

The implementation will be available at https:

all the code must be buildable before static anal-//github.com/prg-titech/mutexunlock.

ysis. This is required to build the type and value
information for variables and functions.

4. 1 Control Flow Graph Builder
Under [1], some helpful checkers are provided by

4. 2 Fix Suggestion

the Go team semi-oﬃcially. For the CFG Builder.

[1] also has ﬁx suggestion system. By putting

Among those, ctrlflow package [5] helps to build

the start position, the end position, and the alter-

CFG from the source code. This package con-native text to TextEdit [2] struct, ﬁx suggestion

structs CFG based on intraproceduraal analysis,

could be implemented. To use, the only require-

which means panic outside of a function will bement is to add -fix option when executing theomitted from CFG.

analyzer binary.

0 entry

1 range.loop

2 range.body

4 if.then

5 if.done

3 range.done
図5

CFG of Listing 7 with a Red Dashed Frame of Strongly Connected Components and a Blue

Doubled Frame For the Block to be Reported (corresponding AST Nodes are abbreviated)

4. 3 Strongly Connected Components

the paper [48].

To know whether the nodes are strongly con-

Finally, by running the detector on those codes,

nected or not, this implementation used Tarjan’s

the results are obtained. The quality is calculated

algorithm [47] to construct SCC data because of

based on recall and precision of the results, andits eﬃciency.

the performance is obtained by calculating mean
response time and its SD of 10 times running by

5 Results
We evaluate our checker’s feasibility with re-time command in GNU Bash [10] for each commit.
All the experiments are done on an arm64

spect to real-world code by applying the checker

Ubuntu 20.04 docker (runsc [11]) instance run-to selected open source software projects that arening on a VM.Standard.A1.Flex Oracle Cloud in-already reported to have mutex bugs in the pre-stance, whose shared CPU is 4 core Ampere(R)vious study.

The selected projects are namely
BoltDB [3], CockroachDB [4], Docker [16]†2 , etcd

Altra (Neoverse-N1) and memory is 24GiB.

[7], gRPC-Go [12], and Kubernetes [15] on GitHub.

quence for the quality and the performance of theFirst, from the bugs reported in the previous

checker with the all or target module source code

As a result, Table 5 shows the overall conse-

study [48], we selected the ones that are related

statistics.

to mutex bugs. The bug-ﬁxing commits are re-containing commit and the applied results with thetrieved from the previous study [48]. They col-lines of code (hereinafter called LoC), the number

lected many ﬁx commits related to concurrencyof functions, the number of blocks, and the num-

bugs from popular OSS. The number of such bug-ber of edges included in the module, each column

containing commits is 8.

shows the following statistics:

Next, for each bug, we apply the buggy commit
to the detector, where a buggy commit is one version prior to the ﬁx commit of the bug reported in†2 Docker repository is renamed to Moby

While each row represents the bug-• “Runnable” represents whether the checker
can be run.
• “Detected” shows how many missing unlock
was reported.

• “False Positives” illustrates the number offalse-positive reports• “True Positives” indicates the number of reasonable reports.
• “Manually Fixed in [48]” column implies how
many missing unlock was ﬁxed manually by
the programmer originally, in other words, thenumber of bugs expected to be reported.
If the checker is run on a module, the lines of code
(hereinafter called LoC), the number of functions,the number of blocks, and the number of edges
are the code included in the module, not a wholeproject. Due to the limitation of the implementation, the number of functions, the number ofblocks, and the number of edges cannot be obtained if the target source code is not buildable sothat those ﬁelds of the commit 8eba018 in Docker[20] are empty.

a889f82 [21]1f70b73 [23]d7bb465 [25]64579f5 [19]8eba018 [20]7c6103d [24]2e7993e [22]07424af [26]

CockroachDB

CockroachDB

CockroachDB

DockerDockergRPC-Go

Kubernetes

Kubernetes

25,3075,279

storagecloudprovider

24,200303,110512

24,415

118,783

513

LoC(Project)(Failed)

proxy

util

(Project)gossipModule*

817

134

1,121

-

20

799

4,527

89

NumberofFunctions

7,437

1,037

5,888

-

106

5,779

49,482

552

Numberof
Blocks

6,673

956

4,734

-

85

5,048

47,174489

Number
of
Edges
5
5
1
1
4
2
2

△1
✓
△2
△2
×
✓
△3
△3

20

Detected

Runnable

12

1

1

3

-

0

1

4

2

False
Positives

7(8)**

1

1

1

-

1

0

1

2(3)**

True
Positives

7(8)***111(1)***

1

0

1

2**

Manually
Fixed
in [48]

6.95

4.35

2.78

-

1.13

2.57

20.06

2.14

Mean
Response
Time (s)

0.26

0.22

0.33

-

0.18

0.25

0.27

0.15

SD (s)*** Since the detector cannot be run on Docker 8eba018, it is excluded from the sum.

** The detector found a unknown missing unlock not ﬁxed in [48]sub-sub directory (module) names which the analyzer could be run.

* (Project) means the analyzer could be run on the whole project (the root path), (Failed) means the analyzer could not be run, and the others are the sub or

3 Runnable only on sub-sub directory due to build error and memory usage on subdirectory

2 Runnable only on subdirectory due to build error

1 Runnable only on subdirectory due to memory usage

Total

CommitPositives and True Positives, and the Number of Manually Fixed Bugs in [48] for Each Commit.

Results of the Evaluation with Characteristics of Each Project, Including the Number of Detected Missing Unlock, the Number of False

Project

表1

According to Table 5, for the quality, the recall

depend on the code size and the domain of mod-is 88% (7 out of 8) while the precision is 60% (12ules, as the results of CockroachDB’s 1f70b73 [23],out of 20). For the performance, it took 1 sec-

and gRPC-Go’s 7c6103d [24] in Table 5 imply that

ond to analyze 5000 LoC in this experiment with

reports on the whole project might have high ratearound 1-second start-up time. The plot is shown

false positives at 75% to 80%. the report by ”Miss-in Figure 6.

ing Unlock Before Exiting from a Function” forAs Figure 6 indicates, the relationship between

Intentionally-separated lock and unlock functions,

LoC and the time taken by applying to the target

and regarding a block as break block mistakenly

source code indicates that the time is also linearlyby ”Consistency After Breaking from Loop” com-increased as the LoC rises.

mit the high rate of false positives.

6 Discussion and Future WorkThe rate of false positives has a tendency to

6. 1 Discussion

be high on the whole project running. The re-First of all, the rate of missing unlock is 8 out ofsults of CockroachDB’s 1f70b73 [23], and gRPC-

83 blocking bugs, which denotes around 9%. This

Go’s 7c6103d [24] show 4 out of 5 and 3 out of 4

rate accords with the previous study results, as

respectively, which means 75% to 80% of the re-[41] shows that the missing unlock bug is approxi-

ports. Mainly, those false positives reports consist

mately 13% of all the bugs they used in their ex-of separate function design for lock and unlock like

periment. Although it is not such a high rate, con-transaction’s begin and commit function, in othersidering that these are caused by careless mistakes

words intentionally not to unlock at the exit pointthat language design could eliminate, the fact thatof a function. The other reports are caused by

missing unlock is ﬁxable using the detector can-the analysis algorithm. Listing 8 shows the false-

not be ignored. Moreover, blocking bugs halt thepositive report due to the detection algorithm.

whole of the program suspiciously despite the difﬁculty of reducing the state complexity, so if 9% of

Listing 8

A False Positive Fix Suggestion in
gRPC-Gothe blocking bugs can be reduced, it is meaningful.
1diff --git a/balancer.go b/balancer.go2index 419e2146..36bdd220 100644

3--- a/balancer.go

missing unlocks at a high rate, 100% for the detec-4+++ b/balancer.gotion and the automated ﬁx with the exception of5

6@@ -357,6 +357,7 @@ func (rr *roundRobin)Get(ctx context.Context,
opts BalancerGetOptions) (addr Ad...

Among them, Section 5 shows the simple analysis algorithm can detect and ﬁx automatically suchthe unbuildable case (if not included, 88% for thedetection and the automated ﬁx). Although the

7

for {

number of bugs is not so much compared to previ-

8...

ous work [41], the fact that such a simple detector

9demonstrates detection and ﬁx at a high rate is10

signiﬁcant.

ch = make(chan struct{})
rr.waitCh = ch11
12

However, the number of false positives is con-if rr.waitCh == nil {} else {ch = rr.waitCh

13sidered to be a problem. Although according to

14

Section 5, false positives are 12 out of 20 which

15}

mean 60% of the whole reports, obviously it will16

rr.mu.Unlock()+ rr.mu.Unlock()25.00Mean Response Time (s)20.00

y = 0.0002x + 1.36

15.00

10.00

5.00

0.00
0

図6

20000

40000

60000
80000
Lines of Code

100000120000140000

The Relationship between Response Time of the Analyzer by Applying to Each OSS andLines of Code with SD Error Bar

17

...

a project because of its ease of measurement.

In Listing 8, unlock is done after the else clause

6. 2 Future Work

therefore it is not needed to insert rr.mu.Unlock()

6. 2. 1 Algorithm

in the else clause. This ﬁx is suggested by the

The current algorithm used in ”Consistency Af-”Consistency After Breaking from Loop” reporterter Breaking from Loop” has a problem to deter-

since the algorithm misunderstands the else clausemine whether a block represents a break from aas the block which contains a break because of theloop or not. The cause of this problem is using

CFG shape. False-positive reports can be divided

SCC to know whether it is a loop or not. Newer

into these two types.

methods to identify the loop are proposed like [50],For benchmark, Figure ?? indicates that the detector running time is linearly increased along withthus using these instead of SCC will solve thisproblem.

the amount of the sum of the number of blocks andAdditionally, ”Missing Unlock Before Exiting

number of edges. This result meets the originalfrom a Function” is the one that commits to false

estimation described in Section 1 and Section 3.

positives. One simple solution to the issue is that

Interestingly, Figure 6 indicates that the detec-

ﬁrstly the just lock functions are marked as candi-

tor benchmark shows the linear increase with LoC,

dates to be reported, and then if those are not con-which is a more suitable indicator for the scale ofsistent in the callee function, it can be reported.

of shared memory synchronization bugs, which is

6. 2. 2 Channel Support

treated in this paper, is decreased. In contrast, theCurrently, the tool does not support channels,

number of bugs related to channel is increased.

so it must be supported in the future. Actually,

Likewise, in other languages, concurrency-

previous work [41] can detect and automaticallyrelated bugs in OSS are also researched as theﬁx it. Details will be described in Section 7.

study on real-world bugs investigation. [49] is one

6. 2. 3 Requirement for Full Builds andof the examples in Node.js. They collected andanalyzed 57 bugs among popular OSS in Node.js,

Memory Usage
ctrlflow package [5] requires the target source

and as a result, they found two-thirds of themcode to be buildable, which is not needed for theare atomicity violations due to the lack of lan-construction of CFG. However, type information

guage and runtime support of locks and transac-

for variables is necessary for detecting mutex ob-tion mechanisms.

ject. Currently, we could not ﬁnd a great way
to deal with this requirement.

On the side of

7. 2 Concurrency-Related Bugs Detection

memory usage, 3 cases were failed due to the highmemory usage during the analysis. This is caused

For bug detection, there are dynamic and stat-by ctrlflow package [5], not our implementation

ical ways. Go provides a dynamic race condition

part. In [35] it looks runnable on relatively large

bug detection tool oﬃcially [6]. Additionally, Go

projects which is failed in this study due to mem-can detect global deadlock errors at runtime since

ory usage error, therefore maybe using other pack-it can be investigated by observing processes andage to build CFG would solve this problem.

timers. If none of them has progress, it means
the program faces a deadlock error. However, dy-

7 Related Worknamic detection cannot know the bug until they

Bugs related to concurrency were examined ameet, therefore sometimes edge case bugs remain

lot. They can be roughly divided into three types:

in a released software emerged as investigated bugs

one is the study about bugs itself, another is thein [48].

bug detection, and the last one is the automatedbug ﬁx.

Therefore statical analyses are essential, though
it is not provided oﬃcially.

[31] illustrates thecurrent overview of statical concurrency bug de7. 1 Study on Concurrency-Related Bugs

tection studies in Go. The ﬁrst one which pro-[48] is the study which collects bug ﬁxes re-posed the statical concurrency bug detector in Go

lated to concurrency bugs from popular OSS in[43] used session graph. From the same research

Go. As Go introduces the diﬀerent approach fromgroup, two research based on their single static

other languages to communicate between pro-assignment intermediate representation and its be-

cesses, which is channel, they studied how channel

havioural types checking [38] [39] are published.

impacted the number of concurrency bugs. The

Moreover, they used bounded model checking inresult is that more than half of 171 bugs in to-[32] to aim for supporting more large scale source

tal are caused due to Go’s characteristics. They

code. The veriﬁcation of communicating session

also mentioned that by using channel, the number

automata for concurrency is discussed in [40]. One

more study with Go and behavioral types is [33].

not ﬁx but refactoring, because refactoring implies

This paper extends the usage to not only dead-the aspect of alleviation.

locks but also race condition detections. Anotherapproach is proposing Mini-Go, a subset language

8 Conclusionof Go only for concurrent features with its formal-

Bugs in software lead to critical problems oc-

ization [45]. They used it to detect global deadlock

casionally. Especially, concurrency-related issues

errors. In addition to those studies, [30] made aare relatively more complicated to ﬁx among thosetranspiler from Go to Coq and applied the codebugs due to the complex states rather than thoseto model checker Iris [14] which provides concur-

sequential programs’. Notably, the combination ofrency proofs. Likewise, concurrency proofs are en-mutex for data race avoidance and error handlingcouraged in other languages than Go. For exam-

without exception handling makes it harsh to man-ple, [38] uses Haskell implementation termination

age mutual exclusion unnecessarily; nevertheless,checker and mCRL2 [13].

the worst-case scenario halts the whole program.
Besides, Go is a language advertised for con-

7. 3 Automated Fix for ConcurrencyRelated Bugs

currency support without exception handling. In
fact, such mistakes can be found in the list of real-

Concurrency-related bugs detection and ﬁxes

world bugs [48] in Go. Seemingly, these bugs inare on dependence relation; it must be detected

Go can be detected by using the analysis on theat least to ﬁx bugs.

CFG, therefore this paper discussed such a detec-[41] is a direct previous work published in 2021,

which uses a similar implementation to this paper.

tor really works by applying to the real-world ﬁxes
collected in [48].

Firstly they modeled channel and its communica-

For the detector, we focus on three missing mu-tion between processes. Mutex can be expressedtex releases, one is before exiting a function, an-

as channel with a size 1 buﬀer they said, therefore

other is before going back to a loop’s head, and themodeling is enough to support the ﬁx for full Go’s

other is breaking from a loop. At each step of DFS

concurrency. Secondly, all the possible path com-to traverse CFG, the lock state for each mutex ob-

binations are calculated. Then, they used a novel

ject is stacked, and if the latest state holds one ofconstraint solving method (using Z3 [29]) to ex-

the three conditions at least, it will be reported

amine buﬀer size overﬂow for each possible path.

at the block in the CFG. At the same time, ﬁx

Contrary to this paper, the path combination cancandidates are also suggested by inserting unlock

beyond the unit of function.

call for the mutex object at the position reports

In other languages, for example in C, while [35]emerged.

provides automated ﬁx using XXX, [37] ﬁxes au-

Meanwhile, the detector is evaluated by apply-

tomatically by a constraint solving especially foring those ﬁxes in OSS in [48]. Firstly, those ﬁxes

mutex lock and unlock in C.

which are suspected to be missing mutex unlock

As the other example in Java, [36] uses types-

picked up manually from blocking bugs list in [48].

tate analysis to examine Stream API which was

Secondly, the detector is applied to one before

introduces in Java 8 [17]. This study is diﬀerent

commit of the target ﬁx. Finally, the evaluation isfrom others a little, in terms of its responsibility isdone by comparing the detection and ﬁx reports

with the original programmers’ ﬁxes.
As a result, there are 8 out of 83 (approximately
9%) satisfying bugs. This result is reasonable considering other previous work like [41]. The detector can appropriately report and ﬁx all of them except for 1 build error project. On the other hand,
the rate of false positives is 75% to 80%, which isrelatively high especially for large LoC targets.
In conclusion, although the number of missing
unlock ﬁxes are not so large, it can be stated that
if 9% of bugs ascribed to trivial mistakes can beeliminated, it is worth applying. However, the rateof false positives is rather problematic. To decrease the rate, the analysis algorithm must be
extended, like marking at call and checking at
callee. Moreover, the determination algorithm forthe loop must be replaced by other techniques like[50]. Overall, through this study at least it can beshown that the simple detector made with CFG
analysis can detect simple missing unlock.

9 Acknowledgment
I would like to express my gratitude to all thelab members, my family and friends for their support.
参 考 文 献[ 1 ] : analysis package, https://golang.org/x/too
ls/go/analysis. Accessed: 2021-12-21.
[ 2 ] : analysis package - golang.org/x/tools/go/analysis- pkg.go.dev, https://pkg.go.dev/golang.org/
x/tools/go/analysis#SuggestedFix. Accessed:
2022-01-31.
[3] :boltdb/bolt:
An embedded key/value
database for Go., https://github.com/boltdb/
bolt. Accessed: 2022-01-28.
[ 4 ] : cockroachdb/cockroach: CockroachDB the open source, cloud-native distributed SQL
database., https://github.com/cockroachdb/c
ockroach. Accessed: 2022-01-28.
[ 5 ] : ctrlﬂow package, https://golang.org/x/t
ools/go/analysis/passes/ctrlflow. Accessed:
2021-12-21.
[ 6 ] : Data Race Detector - The Go Programming

Language, https://go.dev/doc/articles/race detector. Accessed: 2022-01-31.
[ 7 ] : etcd-io/etcd: Distributed reliable key-value
store for the most critical data of a distributed
system, https://github.com/etcd-io/etcd. Accessed: 2022-01-28.
[ 8 ] : fmt command - cmd/fmt - pkg.go.dev, https://pkg.go.dev/cmd/gofmt@go1.17.6. Accessed:
2022-01-14.
[ 9 ] : Frequently Asked Questions (FAQ), https://go.dev/doc/faq. Accessed: 2022-08-01.
[10] : GNU Time - GNU Project - Free Software
Foundation, https://www.gnu.org/software/tim
e/. Accessed: 2022-01-30.
[11] : google/gvisor: Application Kernel for Containers, https://github.com/google/gvisor. Accessed: 2022-01-30.
[12] : grpc/grpc-go: The Go language implementation of gRPC. HTTP/2 based RPC, https://github.com/grpc/grpc- go. Accessed: 202201-28.
[13] : Home ― mCRL2 202106.0 documentation,
https://www.mcrl2.org/web/user manual/index.
html. Accessed: 2022-01-31.
[14] : Iris Project, https://iris- project.org/.
Accessed: 2022-01-31.
[15] : kubernetes/kubernetes: Production-GradeContainer Scheduling and Management, https://github.com/kubernetes/kubernetes. Accessed:
2022-01-28.
[16] : moby/moby: Moby Project - a collaborative
project for the container ecosystem to assemble
container-based systems, https://github.com/moby/moby. Accessed: 2022-01-28.
[17] : Stream (Java Platform SE 8 ), https://docs.oracle.com/javase/jp/8/docs/api/java/util/stream/Stream.html. Accessed: 2022-02-01.
[18] : vet command - cmd/vet - pkg.go.dev, https://pkg.go.dev/cmd/vet@go1.17.6. Accessed: 202201-14.
[19] : Merge pull request #7301 from vieux/ﬁx goroutines leak exit code · moby/moby@64579f5,
https://github.com/moby/moby/commit/64579f
51fcb439c36377c0068ccc9a007b368b5a, 8 2014.
Accessed: 2022-01-30.
[20] : Merge pull request #17155 from janten/meitner · moby/moby@8eba018, https://github.com/moby/moby/commit/8eba018b610e425960ffb462
0dd7a0bfde5238d9, 10 2015. Accessed: 2022-01-30.
[21] : Merge pull request #583 from kkaneda/
kkaneda/use has space · cockroachdb/cockroach@a889f82, https://github.com/cockroachdb/c
ockroach/commit/a889f828214fcfd76f7f2689b7
4cb4bec2bd23a1, 4 2015. Accessed: 2022-01-30.
[22] :
Merge pull request #20674 from caesarxuchao/decode-status · kubernetes/kubernetes@2e7993e, https://github.com/kubernetes/kube

rnetes/commit/2e7993e05708c484a69291c6ddee
gram., Vol. 195, No. 102476(2020), pp. 102476.
f6f3bcc9ee23, 2 2016. Accessed: 2022-01-30.
[37] Khoshnood, S., Kusano, M., and Wang, C.:[23] : Merge pull request #3652 from BramConcBugAssist: constraint solving for diagnosis
Gruneir/3270 · cockroachdb/cockroach@1f70b73,
and repair of concurrency bugs, Proceedings of thehttps://github.com/cockroachdb/cockroach2015 International Symposium on Software Test/commit/1f70b73ae293d9cb18a0927e79ddc28d9e
ing and Analysis, ISSTA 2015, New York, NY,
5cf696, 1 2016. Accessed: 2022-01-30.
USA, Association for Computing Machinery, July[24] : Merge pull request #794 from smallﬁsh/mas2015, pp. 165–176.
ter · grpc/grpc-go@7c6103d, https://github.com[38] Lange, J., Ng, N., Toninho, B., and Yoshida,/grpc/grpc-go/commit/7c6103d142da5fd11a369
N.: Fencing oﬀ Go: Liveness and safety for
64c3a42cf698056b00b, 7 2016. Accessed: 2022-01channel-based programming, Conference Record of30.
the Annual ACM Symposium on Principles of Pro[25] : Merge pull request #9924 from petermattis/
gramming Languages, Association for Computing
pmattis/rm-resource-doc · cockroachdb/cockroach
Machinery, January 2017, pp. 748–761.
[39] Lange, J., Ng, N., Toninho, B., and Yoshida,@d7bb465, https://github.com/cockroachdb/c
ockroach/commit/d7bb465e695c8d6e53d3e2d566
N.: A Static Veriﬁcation Framework for Message
4e764fe4f60f0d, 10 2016. Accessed: 2022-01-30.
Passing in Go Using Behavioural Types, Proceed[26] : Merge pull request #45179 from yguo0905/
ings - International Conference on Software Engiubuntu-node-e2e-test · kubernetes/kubernetes @07424af, neering, 2018.
https://github.com/kubernetes/kubernetes/c[40] Lange, J. and Yoshida, N.: Verifying Asynommit/07424af12b79fe214549e990e014d302b37d
chronous Interactions via Communicating Session
f5c8, 5 2017. Accessed: 2022-01-30.
Automata, Computer Aided Veriﬁcation, Dillig,[27] : CVE-2022-31623, https://cve.mitre.org/
I. and Tasiran, S.(eds.), Cham, Springer Internacgi- bin/cvename.cgi?name=CVE- 2022- 31623,
tional Publishing, 2019, pp. 97–117.
May 2022. Accessed: 2022-08-03.
[41] Liu, Z., Zhu, S., Qin, B., Chen, H., and Song,[28] Allen, F. E.: Control ﬂow analysis, ACM SigL.: Automatically detecting and ﬁxing concurrency
plan Notices, Vol. 5, No. 7(1970), pp. 1–19.
bugs in go software systems, Proceedings of the[29] Bjørner, N. and de Moura, L.: Z3: An eﬃcient
26th ACM International Conference on ArchitecSMT solver, Tools and Algorithms for the Contural Support for Programming Languages and Opstruction and Analysis of Systems,(TACAS 08),
erating Systems, 2021, pp. 616–629.
(2008).
[42] McCool, M. D., Robison, A. D., Reinders, J.,[30] Chajed, T., Tassarotti, J., Kaashoek, M. F.,
清文菅原, and エクセルソフト株式会社: 構造化並列and Zeldovich, N.: Verifying concurrent Go code
プログラミング : 効率良い計算を行うためのパターン
in Coq with Goose, The Sixth International Work, カットシステム, 2013.
shop on Coq for Programming Languages, CoqPL,[43] Ng, N. and Yoshida, N.: Static deadlock deVol. 2020, 2020.
tection for concurrent go by global session graph[31] Dilley, N. and Lange, J.: An Empirical Study
synthesis, Proceedings of CC 2016: The 25th Inof Messaging Passing Concurrency in Go Projects.
ternational Conference on Compiler Construction,[32] Dilley, N. and Lange, J.: Automated VeriﬁcaAssociation for Computing Machinery, Inc, Marchtion of Go Programs via Bounded Model Checking,2016, pp. 174–184.
International Conference on Automated Software[44] Ng, N. and Yoshida, N.: Static deadlock deEngineering (ASE). IEEE/ACM, 2021.
tection for concurrent go by global session graphsynthesis, Proceedings of CC 2016: The 25th In[33] Gabet, J. and Yoshida, N.: Static race detection and mutex safety and liveness for go
ternational Conference on Compiler Construction,
Association for Computing Machinery, Inc, March
programs, 34th European Conference on Object2016, pp. 174–184.
Oriented Programming (ECOOP 2020), Schloss
Dagstuhl-Leibniz-Zentrum für Informatik, 2020.
[45] Stadtmüller, K., Sulzmann, M., and Thiemann, P.: Static trace-based deadlock analysis[34] Hoare, C. A. R.: Communicating sequential
for synchronous mini-go, Programming Languages
processes, Communications of the ACM, Vol. 21,
and Systems, Lecture notes in computer science,
No. 8(1978), pp. 666–677.
Springer International Publishing, Cham, 2016,[35] Jin, G., Zhang, W., and Deng, D.: Automatedpp. 116–136.
concurrency-bug ﬁxing, 10th {USENIX} Symposium on Operating Systems Design and Implemen[46] Suzuki, D.: Go を使いこなせる組織作りの取り組
tation ({OSDI} 12), 2012, pp. 221–236.
み / DeNA.go # 1, https://speakerdeck.com/daisuzu/dena-dot-go-number-1?slide=10, 5 2019.
[36] Khatchadourian, R., Tang, Y., and Bagherzadeh,M.: Safe automated refactoring for intelligent parAccessed: 2022-01-03.
allelization of Java 8 streams, Sci. Comput. Pro[47] Tarjan, R.: Depth-ﬁrst search and linear graphalgorithms, SIAM journal on computing, Vol. 1,
No. 2(1972), pp. 146–160.
[48] Tu, T., Liu, X., Song, L., and Zhang, Y.: Understanding real-world concurrency bugs in Go,
Proceedings of the Twenty-Fourth International
Conference on Architectural Support for Programming Languages and Operating Systems, 2019,
pp. 865–878.
[49] Wang, J., Dou, W., Gao, Y., Gao, C., Qin, F.,

Yin, K., and Wei, J.: A comprehensive study onreal world concurrency bugs in Node.js, 2017 32nd
IEEE/ACM International Conference on Automated Software Engineering (ASE), October 2017,
pp. 520–531.
[50] Wei, T., Mao, J., Zou, W., and Chen, Y.: A
new algorithm for identifying loops in decompilation, International Static Analysis Symposium,
Springer, 2007, pp. 170–183.