SWS   Info

Public Audience

English

60 Minutes

Kaiserslautern

Testing is the predominant approach to finding bugs and gaining
assurance in correctness of concurrent and distributed systems with
complex state spaces. In this thesis we use combinatorial methods to
develop new techniques for systematic and randomized testing. We answer
several theoretical questions about the size of test sets that achieve
full coverage, and propose a practical tool for testing actor-based
programs.

We start with a general construction, obtained using the probabilistic
method from combinatorics, that shows that whenever a random test covers
a fixed testing goal with sufficiently high probability, there is a
small set of random tests that achieves full coverage with high
probability. We use this construction in the context of testing
distributed systems under network partition faults: our construction
explains why random testing tools in this context achieve good
coverage--and hence, find bugs--quickly.

In the context of testing concurrent programs, we introduce a notion of
hitting families of schedules. It suffices to test schedules from a
hitting family if the goal is to expose bugs of "small depth"--bugs that
only depend on the relative ordering of a small number of specific
events in the program. We study the size of optimal hitting families,
and give explicit constructions of small hitting families when the
events in the program are partially ordered as a tree. In particular,
for balanced trees, our constructions are polylogarithmic in the number
of events.

Finally, we propose a testing tool for finding bugs of small depth in
actor-based programs. The tool is based on an existing randomized
scheduler for shared-memory multithreaded programs. Adapting the
scheduler to actor-based programs poses an interesting underlying
theoretical problem.

--email hidden

Yes

Saarbrücken

E1 5

029

passcode not visible

logged in users only