Video summary
Thread safety is a fundamental concept in concurrent programming designed to encapsulate the complexities of synchronization within specific classes, allowing other parts of a program to treat these objects as if they were accessed exclusively by a single thread. Ideally, a thread-safe class ensures that its methods behave correctly even when invoked simultaneously from multiple threads without any additional locking or synchronization logic required by the client code. The standard definition implies that concurrent operations should appear to execute in some serial order consistent with the actual method calls made by individual threads. This abstraction allows developers to rely on these classes as reliable "black boxes," but it also places a heavy burden of correctness on the implementation of these specific classes, making rigorous testing essential to prevent subtle bugs that could compromise the entire application.
To verify whether a class adheres to this definition, the lecture introduces a tool called Contig, which stands for Concurrent Test Generator. This tool automatically creates multi-threaded unit tests by combining a sequential prefix that initializes the object with multiple parallel suffixes that invoke methods on the shared instance. The generation process uses feedback-directed random testing to construct these tests; it randomly selects constructors and method calls while validating arguments to avoid immediate exceptions like index out of bounds errors in a single-threaded context. By executing these generated tests, Contig aims to trigger specific interleavings of thread operations that might expose concurrency bugs, such as the infamous bug found in the Java standard library's StringBuffers class where concurrent insertions and deletions led to unexpected runtime exceptions.
The core mechanism for identifying bugs lies in a thread-safety oracle that analyzes the results of these concurrent executions. When an exception or deadlock occurs during a test run, the oracle does not immediately classify it as a bug; instead, it compares the concurrent execution against all possible linearizations of the test. A linearization represents a hypothetical scenario where all concurrent calls are serialized into a single thread while preserving the internal order of operations within each original thread. If the same failure (exception or deadlock) can be reproduced in any of these linearized versions, the issue is deemed non-concurrent and is ignored as a standard sequential bug. However, if the failure only manifests under specific concurrent interleavings and cannot be replicated in any serial execution, it is confirmed as a genuine thread-safety violation.
This approach offers significant advantages over previous methods because it is sound yet incomplete; it guarantees that every reported bug is real with no false positives, although it may miss subtle issues that do not result in exceptions or deadlocks. Unlike tools limited to detecting data races, this oracle can identify a broader spectrum of concurrency problems, including atomicity violations and deadlocks, provided they manifest as observable failures. The effectiveness of Contig has been demonstrated through its application to popular Java classes from the JDK and Apache libraries, where it successfully uncovered fifteen previously unknown concurrency bugs. While the initial implementation was computationally intensive, taking up to nineteen hours in worst-case scenarios, subsequent improvements focused on test case coverage have significantly reduced execution times, making automated thread-safety verification a practical and powerful technique for ensuring robust concurrent software.
Read the full video transcript
hi hello and welcome back to program
analysis
this is part three of the lecture on
analyzing concurrent programs
and what we want to do in this third
part
is to look at a technique for testing
thread safe classes
again as for the other parts of this
lecture
this part is also based on a paper and
if you're interested in more details
about this technique then please have a
look at it
there so let's get started by defining
what threat safety
actually is it's a term that is
sometimes used in a very informal way
but usually what it means
is that it's a way to encapsulate the
challenges of concurrent programming
into a specific class
in a language that has classes and these
classes then are called
thread safe classes so the basic idea is
that instead of
using concurrency everywhere and
bothering about having the right locks
and synchronizing memory accesses
correctly everywhere in your program you
delegate this task to a few classes that
hopefully do that correctly
and then in the rest of the program you
can basically
assume that this class is ensuring the
correct synchronization
of all shared memory accesses so that
the clients of this class can basically
use
instances of this class as if they were
alone and no other threads
would access these instances so in a
sense the rest of the program
can treat a threadsafe class as a box
and just call its methods without really
thinking about
the other threads that may also use
objects of this class at the same time
a popular book on concurrency in java
gives this definition of what a thread
save class is so it basically says that
the methods of this class behave
correctly when accessed
from multiple threads with no additional
synchronization
in the calling code so the important bit
here is that
there's no need for clients of this
class to
acquire any logs but this is already
done in the class
what is not quite clear in this
definition is what it really means to
behave correctly
but fortunately there's a different
definition that
says that the operations of this threat
safe class
behave as if they occur in some serial
order that is consistent with the order
of the method calls
made by each of the individual threats
so essentially the correct behavior is
implicitly given by
what could happen if you would execute
the calls that happen concurrently
in some serial order and we will use
this
definition of thread safety as a way to
find bugs
in threadsafe classes
let's first illustrate this idea of
thread safety with one particular class
from the
java standard library that is supposed
to be thread safe namely the string
buffer class
and what we do here in this example is
to just initialize the string buffer and
then there are two threads that are
concurrently using
the same instance of the string buffer
and one of these threads is
appending a and b while the other one is
appending c and now the question
for you is well what would be um
possible contents of the string buffer b
assuming that string buffer is indeed a
thread safe class
so i invite you to stop the video here
for a few seconds and think about it
and then i'll tell you um what content
of b
could actually happen
so let's have a look at the solution so
there are three possible contents
that b may have that are legal if this
class is thread safe
one of them is abc which you basically
get if thread one is executing
its first two calls to append first and
then thread
two follows we could also have c a b
which is what you get if thread two
starts executing it's call and then
thread
one is executing the other two calls or
you could also legally get
acb if the call of thread two is
basically interleaved
in between the two calls of thread one
but any other state of the string buffer
for example
ac where maybe the c sorry the b is
overwritten
by the c are not legal or b a c
is also not okay because this would mean
we have reordered
the two calls in thread one which is not
okay with the definition of threat
safety
now because programs that use thread
safe classes put so much
confidence into these thread safe
classes the correctness of these
programs
heavily relies on the correctness of the
thread safe classes
so now what actually happens if these
classes are not thread safe well then
you have a problem so you better
test for these classes to be actually
thread safe
and one way to do this is the tool that
we are talking about now here
it's called contig which basically means
concurrent test
generator and in a nutshell what it does
is to automatically generate
multi-threaded unit tests which
basically look like normal unit tests
just that they have multiple threads
and by doing this it detects threat
safety violations so threat safety
related bugs
by comparing the concurrent behavior of
these
multi-threaded unit tests two
linearizations
of this concurrent behavior so basically
two
alternative tests where you would put
all the methods that happen concurrently
into a single thread
before looking into how exactly this
works let's just have a look at one
example bug that this approach has found
and this was a bug in jdk which is
in the string buffer class that we have
already seen earlier
so if string buffer is used as shown
here in this example
then something unexpected happens so in
this example
the string buffer is initialized and
then some strings say abc
is appended to it and then the same
string buffer object b
is used in two different concurrently
executing threads
where the first thread is trying to
insert the content of the string buffer
into itself at index one so it basically
tries to put abc
right after um the a that is already
there so that at the end you would have
a
abc bc and concurrently
thread two is trying to delete a
particular character that is already in
the string buffer namely the character
at index one and now if you write code
like this and you execute it
concurrently
you may actually get an index out of
bounds exception
which is of course not what you would
accept expect
because um if you would just execute one
of these calls after another
this kind of exception could never occur
and this
has actually been a bug in the jdk
which has also been confirmed by the
java developers
to detect this kind of work quantity is
automatically generating test cases that
test the thread safety
of a given class so the input to the
approach
is this class under test and then the
output is
either nothing or a reported body bug
that it has found
so to do this um there are three main
steps the first one is to
generate a concurrent test and we've
already seen examples of these tests and
we'll see in a second how they are
generated then the next step is to
execute this test
and finally there's a threat safety
oracle which we'll also see in a second
that looks at the execution of this test
case
and determines whether there was a
threat safety violation or not if there
was one
it's going to be reported as a bug and
if not
then the approach goes back to one of
the two earlier stages
so either it goes back to execution
which basically means it's just
executing the same test again hoping
that in a different execution
it's going to hit different behavior
that maybe exposes a bug
or it takes this arrow back here and
goes back to generating another test
hoping that maybe another test
is going to expose a threat safety bug
so let's start by looking at how the
generation of these concurrent tests
works so the example that you've seen
before is actually a generated test
that has been generated by this
algorithm and each of these tests
consists of three parts one is what is
called the sequential prefix so it's
essentially
a sequence of statements that creates
and then sets up
an instance of the class under test for
example by just calling the constructor
and then calling
one or more methods on it and then we
have
two parallel parallely executing threads
that each execute a so-called concurrent
suffix
so the key idea here is that these
concurrent suffixes are using
the shared instance of the class under
test and each are calling
methods on this shared instance
to generate such a test um the test
generation algorithm takes
three steps the first one is to generate
this prefix so essentially here it
instantiates the class on a test and
calls some methods on it
and once it has done this it moves on to
step number two
where it's creating multiple suffixes
for this prefix
which basically adds calls on this
shared instance
of the class under test and then once
the algorithm has
produced a prefix and at least two
suffixes
suffixes it puts them together into a
test which basically looks like what
you've seen before so where you have to
prefix first
followed by the two concurrently
executing uh
tests and all of this generation of the
method calls and as a result also of the
prefixes and suffixes
happens through so-called feedback
directed
random test generation which um we'll
see in more detail
in a second let's look into this
algorithm in some more detail and let's
start with the first step which is to
create
this prefix um for our test so in the
prefix we start by instantiating
the class under test so we want to call
one of its constructors and this happens
by basically randomly
selecting one of the available
constructors so let's say our class
under test is stringbuffer
and let's say we are randomly selecting
this constructor that just
calls the default constructor without
passing any arguments then we would
basically have this
this call here now whenever the test
generation algorithm is adding
a call or or a constructor call to the
test
it's executing this entire test that it
has at this point in order to check
whether
this call or constructor call um yields
an exception and only if it does not
yield an exception it's continuing
so this is an an idea that is similar to
what you've seen earlier in the lecture
when we talked about randoop and its
feedback directed random test generation
now here for this simple example if we
just execute this test that we have so
far
we will see that it runs fine without
any exception so we can continue
extending this prefix now to
extend this prefix the algorithm wants
to call some methods on this
newly created instance of the class
under test so it will
randomly select some method let's say it
randomly selects
to call the append method which requires
a string argument
and now in order to get an argument um
it goes through a couple of different
options
so one option is to take one of the
already available
objects that we have so if we had a
string
object in this test we could just use
that the second
option is to call another method which
is returning
an object or a value of the required
type
and the third option is to just pick a
random value
so for the sake of the example let's
assume the algorithm is picking a random
value let's say abc
and then it has extended this test with
a new call so it will again execute
this extended test to check whether this
leads to an exception
because if it does then we should not
use this prefix
but here everything is fine so we are
basically done
creating a prefix of course we could
also add more methods but for the
example
let's just assume that one is enough and
this is the
prefix that we get
so let's now look into the second step
which is creating suffixes for the
already created prefix
and what we essentially want to do here
is after the object
has been set up in the prefix we want to
call some more methods
on this shared instance of the class
under test
so we start with the prefix that we have
already created
and then in order to call more methods
on it we again randomly select
one of the methods that this object is
providing so let's
say we are selecting insert and insert
has multiple variants so let's say we
take the one that takes an
integer argument as the first argument
and then
a character sequence which tells us what
to insert at a given
index so that means again the algorithm
needs to decide what arguments to use
here for the integer and for the
character sequence
and again it has these three options of
taking any available object that has a
compatible type
or calling a method that returns a value
of the required type
or just picking a random value so let's
say it takes
a mix here of option a and c
by taking a random value minus 5 for the
int
and the existing variable b which is
compatible
with the character sequence type that we
need because string buffer
is also a character sequence
so now this is the call we have added
now
and now the algorithm is trying out
again if this leads to an exception or
not
so it will execute both the prefix and
this so far created suffix and if it
does that
it'll actually get an exception and the
reason simply is that we cannot insert
anything at the
index minus five so we get an index out
of bounds exception here
so now this is just a sequential problem
it doesn't have anything to do with
concurrency or threat safety so
the algorithm does not want to have this
kind of suffix but instead goes back
to the previous step where it's trying
to find better arguments for this call
that do not lead to an exception
and now let's say it now randomly
chooses one
and b as the arguments so we again
execute this entire
um prefix plus partial suffix and now in
this case
we do not get an exception which means
we have created
um a suffix that is fine so now
we could of course add more method calls
to this suffix but for the sake of the
example
let's assume we are done and then move
on to the second
suffix that we also want to have and
that we also create
in a similar way to before so let's now
assume we add this call in the second
suffix
um that calls delete character at with
index 1.
if we execute just the prefix and the
second suffix
one after the other we will see that
there is no exception
so everything is fine which means we
basically have created
another suffix that the algorithm can
continue to work with
so now at this point the algorithm has a
prefix and two suffixes so it will put
these
together into a complete test
which basically just works by spawning
a new thread for each of the suffixes
after the prefix
has been executed and this gives us
exactly the test that we've seen earlier
which if you execute it
and are lucky to trigger the right
interleaving will expose
a thread safety bug
all right so zooming out a little bit um
here's the overview of the approach
again
you now have seen how to generate
concurrent tests now these tests are
executed we will not look into detail
of how this um works um in practice
quantity is just repeatedly executing
the test
on the standard java virtual machine but
you could use more sophisticated
techniques such as the one that we'll
see
in the fourth lecture of this on the
fourth video of this lecture
so now instead of looking more into the
execution let's now have a look
into the threat safety oracle which is
trying to find out whether a given
execution of this
generated concurrent test is exposing a
threat safety bug
or not okay so let's have a look at this
flat safety oracle and let's see how it
figures out whether a given test
execution
is actually exposing a threat safety
violation or not so there are two key
ideas here one is that
the oracle is focusing on very clear
signs of misbehavior
namely exceptions and deadlocks when any
of these two happens
and the programmer does not expect it
it's it's obviously bad
and the second idea is related to the
definition of threat safety itself
and this idea is to compare the
concurrent execution
of the given test case to linearizations
of this test case
to basically check if the misbehavior
the exception or the deadlock that we
are seeing in a concurrent execution
could also happen in a linearization of
this test
so what does linearization mean
linearization essentially means we are
putting all calls that happen in the
concurrent test
into just a single thread while
preserving the order of the calls within
that thread so let's say we have a test
case
that looks like this where we have some
prefix
up here followed by two concurrently
executing
suffixes one executes some statements
one and two and the other one executes
the statement three
then we would have three possible
linearizations
of this test case namely the ones that
you see here so they always have the
suffix at the beginning
followed by all the calls in the prefix
but
preserving the order of calls within the
individual threads which basically means
we're never swapping the order of
one and two but we may put three in
between or before
or after these two calls one and two
so now given this idea of linearizations
let's have a look at how the oracle
figures out whether an execution of a
concurrent threat
exposes a threat safety problem so it
starts by executing
the test concurrently and in this one
concurrent execution of the test
it checks whether there is an exception
or a deadlock
if there is no such misbehavior then
we're basically done with this one
execution it has not exposed any threat
safety problem
and there will be no further analysis of
this execution
in contrast if the oracle sees an
exception or deadlock the question is
whether this could also happen in one of
the linearizations of the test
so in this case it's trying out um a
linearization of this test case and
checks if the same failure
also happens if the same failure also
happens
it basically means that well okay it's
an exception or that look but it could
also happen if you just call this
these two or more concurrent methods
in a single thread which means it's not
a threat safety problem it's not even a
concurrency related problem
so there's no need to report anything to
the user
but if the same failure does not happen
in this linearization
and if it also does not happen in any
other linearizations
so basically the algorithm has checked
all possible linearizations
of the concurrent test and hasn't seen
the same
exception or deadlock then and only then
a threat safety violation is reported
because then we know for sure that there
actually is a threat safety bug
in our class under test
so let's illustrate this um idea of the
oracle again with our running example so
here's the
generated test that tests the string
buffer class of the jdk
and as i've said earlier if you execute
this test concurrently and you're lucky
enough to hit the right
interleaving you will actually get an
exception so now the oracle is checking
whether this exception can also happen
in one of the linearizations
in this case there are only two
linearizations one where we take
the call from thread one first followed
by the call
from thread two and if you do this you
will not get an exception
and the other one where we just swap the
order of the two calls
from the two threads so after the prefix
execute thread
thread two's call and then threats one
thread one's call
and in this case we also do not get an
exception and this means that the
exception
is actually a threat safety violation
and this is
um gonna be reported by the oracle
good so now that you've seen um how this
oracle works
let's take a step back and think about
what properties this oracle is actually
giving us
so it turns out this oracle is sound but
incomplete
which here means that all reported
threat safety violations are real so
there are no false positives but
whenever the approach
says that there is a threat safety
problem then indeed there is one
but on the downside the oracle cannot
guarantee to
um yeah that the class that is tested is
indeed thread safe because it may not
um see some more subtle misbehavior that
for example does not result
in an exception or a deadlock what is
nice about this oracle is that it's
independent of the bug type so in
contrast to for example the eraser
approach that we've seen
in the previous part of this lecture it
is not just looking at data races
but it can also detect other kinds of
concurrency bugs including
data races but also atomicity violations
or deadlocks for example
and as long as any of these bugs
manifests through an exception
or a deadlock um the oracle will be able
to find it
finally let me just quickly tell you
about some results
that this test generator has obtained so
it is implemented for java classes and
then
was applied to popular thread safe
classes from the
jdk itself but also from various apache
libraries
and in total it could find 15
concurrency bugs that were not
previously known in these classes
including some previously unknown
problems
in the jdk itself which is a nice
finding because
that's a piece of software that is used
by many many people
in the version of the tool that i've
talked about here it has
taken between several seconds and
several hours in the worst case 19 hours
to find debug so it was actually pretty
compute intensive and one of the reasons
is that this random generation of tests
doesn't really look at what kind of
concurrent behavior has already been
seen and in a follow-up
piece of work that um yeah a master
student and my group has actually worked
on
we could reduce this worst case time to
several minutes so the
the overall approach has become much
more efficient
and the key idea here was to look at the
coverage of
the that the test cases achieve and to
try to cover new
behavior more often so that we do not
repeatedly test
the same kind of behavior
all right and this is the end of video
number three in this
lecture on analyzing concurrent programs
you hopefully now have a better idea of
what
thread safety means and also have seen
how to automatically test whether a
class
is indeed thread safe by generating
tests at random and then comparing their
concurrent behavior
to linearizations of the concurrent test
thank you very much for listening and
see you next time