hello everyone here I am going to
introduce my recent work Kronos a
testing framework for detecting timeout
bugs in distributed systems by Deep
priority fuzzing with transient
delay distributed systems are prone to
various faults that may occur at runtime
one of the most common faults is delays
which can be caused by uncontrollable
factors such as Network traffic resource
monopolization software bugs and so on
in comp Le Lex distributed systems to
mitigate these unexpected failures
various timeout mechanisms have been
proposed ensuring the stability and
reliability of distributed
systems when object 01 sends a request
to another object O2 01 sets a timeout
value and waits for the response from O2
until the time expires in case O2 fails
or a message loss occurs 01 can break
out of the waiting State triggered by
the timeout of
execute timeout handling code and take
proper actions retrying or skipping
accordingly in general the timeout
mechanism in a distributed system mainly
distributes on two parts components
interact locally through local IO and
nodes communicate remotely via Network
IO distributed systems are inherently
complex involving numerous resources and
nodes that communicate with with each
other to handle unexpected delays and
maintain uninterrupted service provision
these systems require a significant
number of timeout mechanisms however due
to this complexity it can be challenging
to avoid incorrect handling or
implementation bugs in these timeout
Logics which we call them timeout
bugs to effectively test these timeout
mechanisms it is necessary to trigger
more abnormal delays than those
occurring naturally during regular use
by injecting plenty of
delays here I show an example of timeout
bug in hdfs where incorrect handling of
the timeout mechanism led to critical
issues the data streamer throws an IO
exception and incorrectly sets its state
to interrupted as shown in line 18
however when the thread then performs
other actions such as an RPC remote
procedure call to name node by the
function abandon block it first checks
the current state and fails immediately
since its state is interrupted
triggering this bug this bug obstructs
the RPC to other nodes causing service
Hang-Ups and affecting the availability
of the
hdfs however there are three main
challenges first code implementation of
distributed systems is huge and various
it is hard to precisely identify all the
code location ations where to inject
delays the Second Challenge lies in
effectively triggering instrumented
delays in deep paths where timeout bugs
tend to remain hidden in distributed
systems the business logic is usually
divided into multiple phases each with
its corresponding timeout mechanism
frequently executing delays at the
shallow execution paths prevents
exploring timeout mechanisms in deep
paths resulting in ineffective
testing the third challenge is that
executing delays will introduce
significant overhead to the testing
process since actual timeouts are
usually timeconsuming directly inserting
delays reduces testing speed and
consequently testing
performance to overcome these three
challenges we propose Kronos as shown in
this picture which consists of two main
process the first process is the delay
instrument process in this process given
a DSU the delay injector first decides
where to inject delays then precisely
injects the fine grain delay logic and
finally outputs the instrumented DSU
with a set of delay
blocks the second process is the testing
process which involves the following
steps Kronos first loads workloads to
send requests to the distributed system
then delay selector dynamically selects
a subset of the delay blocks according
to the runtime context such as call
Trace execution depth and so
on after that Kronos combines the
selected delay blocks and generates a
delay
sequence and then delay selector
activates all delay blocks in the
sequence dut executes the workload with
the activated delay blocks to speed up
the testing process C the delay
executive proposes the transient delay
mechanism to quickly trigger the timeout
mechanisms finally the timeout bug
analyzer monitors the runtime states of
distributed systems in real time and
identifies if there are node crashes or
service
hangs the timeout bugs are reported once
they are detected Kronos proceeds to the
next iteration from step one to step
seven of the testing process until
termination
first the delay injector determines
where to inject delay which code
locations in delay blocks are eligible
to inject delays there are three
alternative delay injection methods as
shown in
figure first we can directly modify the
source code of the distributed system
under test however it is hard to
identify all timeout mechanisms since
their code implementation are complex
and
various or we can inject delays in local
IO and network iio by the Linux kernel
however it is hard for the OS kernel to
distinguish which collar which delay
blocks D1 D2 or D3 calls through the
EO since timeout mechanisms in local
interactions and remote Communications
are executed through local IO and
network EO usually distributed systems
do not directly operate these IO but
rather utilize existing common runtime
libraries so we can inject delays in the
runtime Library
layer the Second Challenge is to decide
when to activate delays each delay block
has two states activated or
deactivated because there are so many
delay blocks in a distributed system the
input space is
huge and one our assumption is that
delay mechanisms in the Deep path are
hardly triggered in normal usage or
testing and therefore may have more
timeout bugs
then we use a deep priority guided
algorithm for selecting delay sequences
that can trigger new found deep delays
in this way Kronos constantly generates
highquality delay sequences as test
inputs and explores as many deep delay
blocks as
possible the third challenge is how to
execute delays in real world distributed
systems timeouts are typically set
between 1 second to 10
minutes however injecting such long
delays directly can significantly slow
down the testing
process to address it we propose a
transient delay mechanism that directly
sets the timeout value to zero this
enables quick triggering of delay Logics
in the system and speed up the testing
process we have implemented Kronos on
four widely used distributed systems
including zookeeper MySQL cluster hdfs
and go ethereum in total we have
detected 28 new bugs in these systems we
compared Kronos with other state-of-art
methods for fault injection Tech on
alies including random method brute
force method and coverage guided fuzzing
the results show Kronos always
outperforms others on all four targets
distributed
systems to evaluate the effectiveness of
the transient delay we also run Kronos
minus the version of Kronos which
disables the the transient delay and
executes the actual delays in conclusion
Kronos can detect all 28 bugs within 24
hours while Kronos minus only detects 14
of them and Kronos covers 18% more delay
blocks our future work mainly focuses on
the following points first we would
explore more oracles such as privacy
leaking problem or performance issues to
further improve kronos's bug
analyzer in addition we will try to
enhance Kronos with finer feedback
guidance in finding more timeout bugs at
last we will try to adapt Kronos to more
distributed
systems thank you for listening please
contact me if you have any questions