Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Combinatorial Constructions for Effective Testing
Speaker:Filip Nikšić
coming from:Max Planck Institute for Software Systems
Speakers Bio:
Event Type:SWS Student Defense Talks - Thesis Proposal
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Monday, 14 August 2017
Duration:60 Minutes
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

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.
Video Broadcast
Video Broadcast:YesTo Location:Saarbrücken
To Building:E1 5To Room:029
Tags, Category, Keywords and additional notes
Attachments, File(s):
Maria-Louise Albrecht/MPI-KLSB, 08/09/2017 05:03 PM
Last modified:
Maria-Louise Albrecht/MPI-KLSB, 08/09/2017 05:06 PM
  • Maria-Louise Albrecht, 08/09/2017 05:06 PM -- Created document.