The TAU Programming Languages and Systems Seminar - Combinatorial Constructions for Effective Testing

Abstract:

Empirically, many bugs in complex systems have a simple cause: they are triggered by the interaction of a small number of specific events.Guided by this observation, in certain cases it may be possible to test all k-wise interactions for a constant k by executing a family of tests whose size is logarithmic or even doubly logarithmic in the number of all tests. Thus, in such cases we can effectively find all bugs that depend on the interaction of up to k events. In this talk we present two occurrences of this phenomenon. First, many partition faults in distributed systems are caused by the inability of two or three key nodes to communicate. By using the probabilistic method from combinatorics, we show that in a system with n nodes, all such faults can be uncovered by simulating O(log n) network partitions.Moreover, all such faults can be uncovered with high probability by simulating O(log n) randomly generated partitions. Second, in the context of concurrent programs, many bugs have "small depth" -- they depend on a relative ordering of a small number of events. One can expose all bugs of depth d by executing schedules from a d-hitting family of schedules. We show that if the partial order of events for a concurrent program is known in advance and it is structured as a tree or a series-parallel graph of height h, we can explicitly construct a d-hitting family of size O(h^(d-1)). If the partial order is revealed on-the-fly and it is structured arbitrarily, we can construct a d-hitting family of size w^2 n^(d-1), where w is the maximal width of the partial order. 

Bio:

Filip Niksic is a doctoral student at the Max Planck Institute for Software Systems (MPI-SWS) in Kaiserslautern, Germany. His research interests broadly lie in the analysis, verification, and testing of concurrent systems.