Video summary
The core challenge addressed in this lecture segment is the problem of scheduling non-determinism in concurrent programs, where a single execution with identical inputs can result in vastly different behaviors due to varying thread interleavings. This issue is often compared to Heisenbugs, which are notorious for disappearing when actively investigated because they only manifest under specific, rare timing conditions. To systematically explore these possibilities rather than relying on random chance, the video introduces CHESS, a user-mode scheduler that takes control of all scheduling decisions. CHESS guarantees two critical properties: it ensures that every program run triggers a new, distinct interleaving to maximize bug exposure, and it can reproduce any specific interleaving observed during a test, allowing developers to reliably debug issues that might otherwise vanish upon re-execution.
To manage the vast search space of possible executions, the concept of an interleaving tree is employed, where each path from the root to a leaf node represents a unique schedule determined by scheduling decisions at various points in the code. While theoretically one could map every possible execution path for a program with $n$ threads and $k$ instructions per thread, the resulting complexity grows exponentially ($n^{n \times k}$), making exhaustive exploration impossible for realistic systems. To address this practical limitation, CHESS utilizes a technique called preemption bounding, which restricts the number of times the scheduler switches between threads to a small constant $c$. This heuristic is effective because empirical evidence suggests that most concurrency bugs can be triggered with very few context switches, thereby reducing the complexity from exponential in both thread count and instruction count to one that is manageable for testing purposes.
Beyond preemption bounding, the video highlights several other strategies for influencing scheduling decisions to uncover hidden bugs. These include random delays on concurrent operations, such as artificially delaying lock acquisitions, and leveraging known bug patterns to bias the scheduler toward likely failure scenarios. Additionally, program annotations allow developers to explicitly instruct the scheduler to wait at specific points to verify correctness under different timing conditions. A sophisticated approach known as active testing combines static analysis with dynamic execution; in this two-phase method, potential bugs identified by static tools are used to bias the scheduler during runtime specifically to confirm and expose those issues. Ultimately, these techniques transform concurrency testing from a game of chance into a systematic process that not only finds bugs faster but also ensures they can be consistently reproduced for deep analysis.
Read the full video transcript
hi hello and welcome back to program
analysis
in this fourth and last video of this
lecture on analyzing concurrent programs
we will look
into exploring different interleavings
that
the execution of a program may actually
trigger and this is a problem that is
kind of orthogonal to the
problems that we've looked at in the
previous uh videos of this lecture
because
in the previous videos we were always
assuming that we somehow triggered the
right
interleaving when executing the program
and now we will
look at one approach for um hopefully
triggering the right interleaving a
little faster
again this is based on the paper so if
you're interested in more details
please have a look at this paper down
here
so the underlying challenge that we are
addressing here is the problem of
scheduling non-determinism
that's a fact that you've already seen
with one of the examples that i've shown
earlier it's the fact that a single
program
executed with a single input may have
many different interleavings and
therefore also many different
behaviors now in practice there's some
scheduler
that decides these interleavings
non-deterministically which means if you
execute a program multiple times you
will get different
interleavings and many of the
concurrency bugs have the
nasty property that only some
interleavings actually expose
the bug and others just execute
correctly which has given these
bugs the nickname heisenbach's because
they kind of disappear when you try to
look for them
so the challenge is how to actually
explore different interleavings
in a hopefully systematic way and how to
then also detect
buggy interleavings
so one way to explore interleavings in a
systematic way is an approach called
chess which we will
have a look at now so chess is a user
mode scheduler that controls
all scheduling non-determinism of a
program so you essentially give
chess a program that has multiple
threads and then it's controlling
in which order the different statements
and operations
of the concurrent threads are executing
chess makes two uh very interesting
guarantees the first one is that
every program run um takes a new threat
into leaving that means if you execute
the program three times you will have
triggered three different
um behaviors or at least three different
interleavings that potentially lead
to different visible behavior the second
property that
chess guarantees is that it can
reproduce the interleaving of every run
so this is very important because
otherwise you have these heisenbach's
that you maybe
observe once but then you cannot observe
again because you can't reproduce the
interleaving
but with chess if you have seen an
interesting run for example a run that
exposes a bug
you can reproduce this run and debug it
in more detail
so the way this works is through
systematic but non-exhaustive
exploration which basically means that
chess is looking at the set of possible
interleavings
and then systematically tries one after
the other um without really attempting
to try all of them because for
realistic programs they are more than
you can reasonably try
in the time that's typically available
for testing
so to reason about the different
interleavings that the execution of a
program
may have we need some kind of
representation of this
space of interleavings and the way this
search space can be represented very
nicely is as a tree
of interleavings where basically every
path through this tree so from the root
to the
uh to some leaf node represents one
possible schedule
that a program is taking so notes in
this
three um represent scheduling decisions
so basically every point
in the program where this thread or that
thread may execute next
is represented as a node in this tree
and then the edges
correspond to decisions that are taking
so from every node there are at least
two
outgoing edges that represent that you
either do this
or do that and then if you have the tree
built up this way
then every path from the root down to
relief represents one possible schedule
and one possible
interleaving that the program may take
so as an example to illustrate this tree
of interleavings let's just have a look
again at this example that we've
seen earlier on in this lecture where we
have this piece of code
that starts with some initialization
of variables and then has two
concurrently running threads that each
are executing two statements
a slightly more abstract way to look at
this example is by just saying that we
have
one thread t one which is executing a
statement one followed by a statement
two
doesn't really matter what these
statements are doing
and then we have statement t two which
also has
um two statements one and two which
maybe aren't usually are different
from what thread t1 is executing
now using this abstracted notation we
can try to write down the scheduling
tree
of this little program
and we're starting here with the root
where we
just call the root 0 0
and the notation here is the following
so for every node i'm having
two values
such that the first value is the last
instruction that has been executed by
thread t1
and the second value is the last
instruction that has been executed by a
thread
t2 so 0 0 essentially means we have not
yet executed
any of the instructions of any of these
threads but are literally
at the beginning of the concurrent part
of the execution of this program
so when the program is in this state 0 0
there are
two options what could happen next and
each of these options is represented as
one outgoing
edge out of our node
so one option is that we start by
executing
the first instruction of thread 1 which
is represented as
1 0 because then the first execution of
the first
statement in t1 has been executed but
nothing yet in t2
and the other option is that we start
with thread 2 which is
represented as 0 1. now after
having executed the first instruction in
thread 1
what we could do next is to also execute
the second instruction and then once
we've done this there's only one option
left
namely to execute the first instruction
of
t2 that we haven't yet executed and then
the one outstanding instruction
which is the second instruction of t2
what we could have done here instead of
continuing in
thread 1 is of course to also
switch to thread 2.
if we do this we end up in this state
one one because now we've executed the
first
instruction of each of the two threads
and in that state
we again have two options one is to go
back to
thread one and execute its second
instruction
after which we then will go back to
thread two
or we stay in thread two and
execute its second instruction and then
go back to thread one to again end up in
state 2 2.
and on the right side of the tree you
can do essentially the same just just
the inverse
where at each node you basically have to
decide among all the possible
instructions that are executed next and
at the end you always end up in stage 2
2 because at the end we always must have
executed all statements
of all threads
so as you've seen for this tiny program
that has just two threads that each
just have two instructions it's possible
to write down the entire
tree of interleavings but let's now have
a look at the space of these
interleavings for
more realistic programs so in general we
have
not just two threads but we have n
threads so thread one to
thread n and let's just to simplify
things a little bit assume that each of
these
threads has k instructions so in every
thread
we have k different instructions or
statements
that need to be scheduled now the number
of interleavings that you get in this
general setup
is in the order of n to the power of n
times k
which means it's exponential in both n
and k
which does not really sound good and in
practice also is not good because
typically
you have a lot of instructions per
thread so typically more than hundreds
and a relatively small small number of
threads
so typically less than 10 but still both
together
um leads to the situation that it's
practically impossible
to explore all interleavings because
in particular because of k which is
getting pretty
large pretty quickly um giving us so
many interleavings that you just can't
explore
all of them
so now in order to still be practical
chess
implements a pretty clever idea and this
is called preemption bounding so the
basic idea is to limit the number of
times that the scheduler switches from
one thread
to another so each of these switches is
called a preemption
and the basic idea is to limit this
number of preemptions to a small number
c
and if you do this and think again about
how many schedules
the scheduler then has to explore you'll
find out that this is in the order of
what you can see here and if you look at
this term
you see that it's still exponential in c
and
in n but not anymore in k and as we've
seen
on the previous slide k this number of
instructions per thread
is what is really going high
in real programs now this idea of
preemption bounding is based on the
empirical observation that most
concurrent
c related bugs can actually be triggered
with few
typically um less than two preemptions
so you do not have to go back and forth
between threats that often you just have
to go back and forth
at the right points in time and are
still able to trigger
most concurrency bugs now of course this
is a
empirical observation and this whole
idea of preemption bounding
is just a heuristic so it's of course
possible that
you're missing some concurrency bugs if
you limit
the number of preemptions to a c that is
too small
so this idea of chess has been
implemented through binary
instrumentation so basically taking an
existing binary
program that has concurrent behavior and
then it's instrumented in order to
control the scheduling decision that
happen when the program is executing
and then this implementation has been
applied to a couple of
mid size and larger systems up to 175
000 lines of code in which the tool was
able to find a total of 27 bucks
that's a pretty nice result and beyond
the ability to find bugs that
you may not find if you just randomly um
repeat the execution of this program um
so
stress testing is that once you have a
failure
um detected it's easy to reproduce and
debug it because you know which
interleaving has triggered
this failure simply because the
scheduler has controlled the
interleavings and
then also knows how to trigger the same
interleaving again
finally let me say that there are also
other ways of controlling the
scheduling decisions of course um one
and that is
surprisingly effective in practice is to
just
randomly delay some of the concurrency
related operations so for example if
a threat is trying to acquire a lock you
can just randomly delay it a little bit
hoping to trigger a different
interleaving by doing this and
yeah more often than not this actually
turns out to trigger
behavior that is able to detect some
bugs
then there are different pieces of work
that use various heuristics in order to
influence the scheduler for example
based on known bug patterns where you
know that if you influence the schedule
in this way or that way
it's more likely to trigger a bug and in
a sense chess can be seen as one
instance of this heuristics based idea
another one is to use
a program by annotation so if a
programmer explicitly says that
maybe here we should wait a little to
see if the program still behaves
correctly then you can use this
as a way to control the schedule
and finally there's a pretty nice way
called active testing
which works in two phases phase one is
to find
potential bugs using some other kind of
analysis for example a static analysis
of the code
and phase two is then biasing the
scheduler
knowing about these potential bugs
towards confirming these bugs
in an actual execution so for example if
we know that two memory accesses
may be in a data race then maybe we
should wait before one of the excesses
until the other one is ready
and then see if by doing this we can
trigger some interesting behavior that
hopefully exposes some bugs
all right and this is the end of part
four of this lecture on analyzing
concurrent programs
i hope you now have a better idea of how
we can actually control the
interleavings that happen
while the program is executing so that
we can
trigger interesting bugs faster and
maybe even reproduce
the interleavings that are triggering
these bugs
thank you very much for listening and
see you around