Hitting Families of Schedules for Asynchronous Programs

Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 9780)

Abstract

We consider the following basic task in the testing of concurrent systems. The input to the task is a partial order of events, which models actions performed on or by the system and specifies ordering constraints between them. The task is to determine if some scheduling of these events can result in a bug. The number of schedules to be explored can, in general, be exponential.

Empirically, many bugs in concurrent programs have been observed to have small bug depth; that is, these bugs are exposed by every schedule that orders d specific events in a particular way, irrespective of how the other events are ordered, and d is small compared to the total number of events. To find all bugs of depth d, one needs to only test a d-hitting family of schedules: we call a set of schedules a d-hitting family if for each set of d events, and for each allowed ordering of these events, there is some schedule in the family that executes these events in this ordering. The size of a d-hitting family may be much smaller than the number of all possible schedules, and a natural question is whether one can find d-hitting families of schedules that have small size.

In general, finding the size of optimal d-hitting families is hard, even for d = 2. We show, however, that when the partial order is a tree, one can explicitly construct d-hitting families of schedules of small size. When the tree is balanced, our constructions are polylogarithmic in the number of events.

1 Introduction

Consider the following basic task in systematic testing of programs. We are given n events \(a_1\), \(a_2\), \(\ldots \), \(a_n\), and we ask if the execution of some ordering of these events can cause the program to exhibit a bug. In the worst case, one needs to run n! tests, one corresponding to each ordering of events. Empirically, though, many bugs in programs depend on the precise ordering of a small number of events [3, 13, 16]. That is, for many bugs, there is some constant d (called the bug depth, small in comparison to n) and a subset \(a_{i_1}\), \(\ldots \), \(a_{i_d}\) of events such that some ordering of these d events already exposes the bug no matter how all other events are ordered. This empirical observation is the basis for many different systematic testing approaches such as context-bounded testing [14], delay-bounded testing [6], and PCT [3]. Can we do better than n! tests if we only want to uncover all bugs of depth up to d, for fixed d? An obvious upper bound on the number of tests is given by
$$\begin{aligned} { n \atopwithdelims ()d } \cdot d! \le n^d, \end{aligned}$$
which picks a test for each choice of d events and each ordering of these events. In this paper, we show that one can do significantly better—in this as well as in more general settings.

Hitting Families of Schedules. We consider a more general instance of the problem, where there is a partial ordering between the n events. A schedule is a linearization (a linear extension) of the partial order of events. A dependency between two events a and b in the partial order means that in any test, the event a must execute before b. For example, a may be an action to open a file and b an action that reads from the file, or a may be a callback that enables the callback b.

The depth of a bug is the minimum number of events that must be ordered in a specific way for the bug to be exposed by a schedule. For example, consider some two events a and b in the partial order of an execution. If a bug manifests itself only when a occurs before b, the bug depth is 2. If there are three events that must occur in a certain order for a bug to appear, the depth is 3, and so on. For example, an order violation involving two operations is precisely a bug of depth 2: say, event a writes, event b reads, or vice versa (race condition). Basic atomicity violation bugs are of depth 3: event a establishes an invariant, b breaks it, c assumes the invariant established by a; bugs of larger depth correspond to more involved scenarios and capture more complex race conditions. A schedule is said to hit a bug if the events that expose the bug occur in the schedule in the required order. The question we study in this paper is whether it is possible to find a family of schedules that hits all potential bugs of depth d, for a fixed \(d\ge 2\) —we call such a family a d-hitting family of schedules.

For a general partial order, finding an optimal d-hitting family is NP-hard, even when \(d=2\) [24]; in fact, even approximating the optimal size is hard [4, 9]. Thus, we focus on a special case: when the Hasse diagram of the partial order is a tree. Our choice is motivated by several concurrent programming models, such as asynchronous programs [8, 11, 20] and JavaScript events [17], whose execution dependencies can be approximated as trees.

Constructing Hitting Families for Trees. For trees and \(d=2\), it turns out that two schedules are enough, independent of the number of events in the tree. These two schedules correspond to leftmost and rightmost DFS (depth-first) traversals of the tree, respectively.

For \(d > 2\) and an execution tree of n events, we have already mentioned the upper bound of \(n^d\) for the size of an optimal d-hitting family (cf. delay-bounded scheduling [6]). Our main technical results show that this family can be exponentially sub-optimal. For \(d=3\) and a balanced tree on n nodes, we show an explicit construction of a 3-hitting family of size \(O(\log n)\), which is optimal up to a constant factor. (Our construction works on a more general partial order, which we call a double tree.) For each \(d > 3\), we show an explicit construction of a d-hitting family of size \(f(d) \cdot (\log n)^{d-1}\), which is optimal up to a polynomial. Here f(d) is an exponential function depending only on d. As a corollary, the two constructions give explicit d-hitting families of size \(O(\log n)\) (for \(d=3\)) and \(O((\log n)^{d-1})\) (for \(d > 3\)) for antichains, i.e., for the partial order that has no dependencies between the n events. We also show a lower bound on the size of d-hitting families in terms of the height of the tree; in a dual way, for an antichain of n events, the size of any d-hitting family is at least \(g(d) \cdot \log n\) for each \(d > 2\).

For a testing scenario where the height of the tree (the size of the maximum chain of dependencies) is exponentially smaller than its size (the number of events), our constructions give explicit test suites that are exponentially smaller than the size—in contrast to previous techniques for systematic testing.

Related Work. Our notion of bug depth is similar to bug depth for shared-memory multi-threaded programs introduced in [3]. The quantity in [3] is defined as the minimal number of additional constraints that guarantee an occurrence of the bug. Depending on the bug, this can be between half our d and one less than our d. Burckhardt et al. [3] show an \(O(m n^{d'-1})\) family for m threads with n instructions in total (\(d'\) denotes bug depth according to their definition). Since multi-threaded programs can generate arbitrary partial orders, it is difficult to prove optimality of hitting families in this case.

Our notion of d-hitting families is closely related to the notion of order dimension for a partial order, defined as the smallest number of linearizations, the intersection of which gives rise to the partial order [5, 19, 23]. Specifically, the size of an optimal 2-hitting family is the order dimension of a partial order, and the size of an optimal d-hitting family is a natural generalization. To the best of our knowledge, general d-hitting families have not been studied before for general partial orders. A version of the dimension (\(d = 2\)) called fractional dimension is known to be of use for approximation of some problems in scheduling theory [2]. Other generalizations of the dimension are also known (see, e.g., [22]), but, to the best of our knowledge, none of them is equivalent to ours.

Summary. The contribution of this paper is as follows:
  • We introduce d-hitting families as a common framework for systematic testing (Sect. 2). The size of optimal d-hitting families generalizes the order dimension for partial orders, and the families themselves are natural combinatorial objects of independent interest.

  • We provide explicit constructions of d-hitting families for trees that are close to optimal: up to a small constant factor for \(d = 3\) and up to a polynomial for \(d > 3\) (Sects. 35). Our families of schedules can be exponentially smaller than the size of the partial order.

We outline some challenges in going from our theoretical constructions to building practical and automated test generation tools in Sect. 6.

2 Hitting Families of Schedules

In this section, we first recall the standard terminology of partial orders, and then proceed to define schedules (linearizations of these partial orders) and hitting families of schedules.

Preliminaries: Partial Orders. A partial order (also known as a partially ordered set, or a poset) is a pair \((\mathcal {P}, \le )\) where \(\mathcal {P}\) is a set and \(\le \) is a binary relation on \(\mathcal {P}\) that is:
  1. (1)

    reflexive: \(x \le x\) for all \(x \in \mathcal {P} \),

     
  2. (2)

    antisymmetric: \(x \le y\) and \(y \le x\) imply \(x = y\) for all \(x, y \in \mathcal {P} \),

     
  3. (3)

    transitive: \(x \le y\) and \(y \le z\) imply \(x \le z\) for all \(x, y, z \in \mathcal {P} \).

     

One typically uses \(\mathcal {P}\) to refer to \((\mathcal {P}, \le )\). We will refer to elements of partial orders as events; the size of \(\mathcal {P}\) is the number of events in it, \(|\mathcal {P} |\).

The relation \(x \le y\) is also written as \(x \le _\mathcal {P} y\) and as \(y \ge x\); the event x is a predecessor of y, and y is a successor of x. One writes \(x < y\) iff \(x \le y\) and \(x \ne y\). Furthermore, x is an immediate predecessor of y (and y is an immediate successor of x) if \(x < y\) but there is no \(z \in \mathcal {P} \) such that \(x< z < y\). The Hasse diagram of a partial order \(\mathcal {P}\) is a directed graph where the set of vertices is \(\mathcal {P}\) and an edge (xy) exists if and only if x is an immediate predecessor of y. Partial orders are sometimes identified with their Hasse diagrams.

Events x and y are comparable iff \(x \le y\) or \(y \le x\). Otherwise they are incomparable, which is written as \(x \parallel y\). Partial orders \((\mathcal {P} _1, \le _1)\) and \((\mathcal {P} _2, \le _2)\) are disjoint if \(\mathcal {P} _1 \cap \mathcal {P} _2 = \emptyset \); the parallel composition (or disjoint union) of such partial orders is the partial order \((\mathcal {P}, \le )\) where \(\mathcal {P} = \mathcal {P} _1 \cup \mathcal {P} _2\) and \(x \le y\) iff \(x, y \in \mathcal {P} _k\) for some \(k \in \{1, 2\}\) and \(x \le _k y\). In this partial order, which we will denote by \(\mathcal {P} _1 \parallel \mathcal {P} _2\), any two events not coming from a single \(\mathcal {P} _k\) are incomparable: \(x_1 \in \mathcal {P} _1\) and \(x_2 \in \mathcal {P} _2\) imply \(x_1 \parallel x_2\).

For a partial order \((\mathcal {P}, \le )\) and a subset \(\mathcal {Q} \subseteq \mathcal {P} \), the restriction of \((\mathcal {P}, \le )\) to \(\mathcal {Q}\) is the partial order \((\mathcal {Q}, \le _\mathcal {Q})\) in which, for all \(x, y \in \mathcal {Q} \), \(x \le _\mathcal {Q} y\) if and only if \(x \le y\). Instead of \(\le _\mathcal {Q} \) one usually writes \(\le \), thus denoting the restriction by \((\mathcal {Q}, \le )\). We will also say that the partial order \(\mathcal {P}\)contains the partial order \(\mathcal {Q}\). In general, partial orders \((\mathcal {P} _1, \le _1)\) and \((\mathcal {P} _2, \le _2)\) are isomorphic iff there exists an isomorphism \(f :\mathcal {P} _1 \rightarrow \mathcal {P} _2\): a bijective mapping that respects the ordering, i.e., with \(x \le _1 y\) iff \(f(x) \le _2 f(y)\) for all \(x, y \in \mathcal {P} _1\). Containment of partial orders is usually understood up to isomorphism.

Schedules and Their Families. A partial order is linear (or total) if all its events are pairwise comparable. A linearization (linear extension) of the partial order \((\mathcal {P}, \le )\) is a partial order of the form \((\mathcal {P}, \le ')\) that is linear and has \(\le '\) which is a superset of \(\le \). We call linearizations (linear extensions) of \(\mathcal {P} \)schedules. In other words, a schedule \(\alpha \) is a permutation of the elements of \(\mathcal {P}\) that respects\(\mathcal {P}\), i.e., respects all constraints of the form \(x \le y\) from \(\mathcal {P}\): for all pairs \(x, y \in \mathcal {P} \), whenever \(x \le _\mathcal {P} y\), it also holds that \(x \le _\alpha y\). We denote the set of all possible schedules by \(S(\mathcal {P})\); a family of schedules for \(\mathcal {P}\) is simply a subset of \(S(\mathcal {P})\).

In what follows, we often treat schedules as words and families of schedules as languages. Indeed, let \(\mathcal {P}\) have n elements \(\{v_1, \ldots , v_n\}\), then any schedule \(\alpha \) can be viewed as a word of length n over the alphabet \(\{v_1, \ldots , v_n\}\) where each letter occurs exactly once. We say that \(\alpha \)schedules events in the order of occurrences of letters in the word that represents it.

Suppose \(\alpha _1\) and \(\alpha _2\) are schedules for disjoint partial orders \(\mathcal {P} _1\) and \(\mathcal {P} _2\); then \(\alpha _1 \cdot \alpha _2\) is a schedule for the partial order \(\mathcal {P} _1 \parallel \mathcal {P} _2\) that first schedules all events from \(\mathcal {P} _1\) according to \(\alpha _1\) and then all events from \(\mathcal {P} _2\) according to \(\alpha _2\). Note that we will use the \(\cdot \) to concatenate schedules (as well as individual events); since some of our partially ordered sets will contain strings, concatenation “inside” an event will be denoted simply by juxtaposition.

Admissible Tuples and d-Hitting Families. Fix a partial order \(\mathcal {P}\) and let \(\varvec{a} = (a_1, \ldots , a_d)\) be a tuple of \(d \ge 2\) distinct elements of \(\mathcal {P}\); we call such tuples d-tuples. Suppose \(\alpha \) is a schedule for \(\mathcal {P}\); then the schedule \(\alpha \)hits the tuple \(\varvec{a}\) if the restriction of \(\alpha \) to the set \(\{ a_1, \ldots , a_d \}\) is the sequence \(a_1 \cdot \ldots \cdot a_d\).

Note that for a tuple \(\varvec{a}\) to have a schedule that hits \(\varvec{a}\) it is necessary and sufficient that \(\varvec{a}\) respect \(\mathcal {P}\); this condition is equivalent to the condition that \(a_i \le a_j\) or \(a_i \parallel a_j\) whenever \(1 \le i \le j \le d\). We call d-tuples satisfying this condition admissible.

Definition 1

(d-hitting family). A family of schedules \(F\) for \(\mathcal {P}\) is d-hitting if for every admissible d-tuple \(\varvec{a}\) there is a schedule \(\alpha \in F \) that hits \(\varvec{a}\).

It is straightforward that every \(\mathcal {P}\) with \(|\mathcal {P} | = n\) has a d-hitting family of size at most \(\left( {\begin{array}{c}n\\ d\end{array}}\right) \cdot d! \le n^d\): just take any hitting schedule for each admissible d-tuple, of which there are at most \(\left( {\begin{array}{c}n\\ d\end{array}}\right) \cdot d!\). For \(d = 2\), the size of the smallest 2-hitting family is known as the dimension of the partial order [5, 23]. Computing and even approximating the dimension for general partial orders is known to be a hard problem [4, 9, 24]. In the remainder of the paper, we focus on d-hitting families for specific partial orders, most importantly trees (which can, for instance, approximate happens-before relations of asynchronous programs). We first consider two simple examples.

Example 2

(chain). Consider a chain of n events (a linear order): \(\mathcal {C} _n = \{1, \ldots , n\}\) with \(1< 2< \ldots < n\). This partial order has a unique schedule: \(\alpha = 1 \cdot 2 \cdot \ldots \cdot n\); a d-tuple \(\varvec{a} = (a_1, \ldots , a_d)\) is admissible iff \(a_1< \ldots < a_d\), and \(\alpha \) hits all such d-tuples. Thus, for any d, the family \(F = \{\alpha \}\) is a d-hitting family for \(\mathcal {C} _n\).

Example 3

(chain with independent event). Consider \(\mathcal {C} _n \parallel \{\dag \}\), the disjoint union of \(\mathcal {C} _n\) from Example 2 and a singleton \(\{\dag \}\). There are \(n + 1\) possible schedules, depending on how \(\dag \) is positioned with respect to the chain: \(\alpha _0 = \dag \cdot 1 \cdot 2 \cdot \ldots \cdot n\), \(\alpha _1 = 1 \cdot \dag \cdot 2 \cdot \ldots \cdot n\), ..., \(\alpha _n = 1 \cdot 2 \cdot \ldots \cdot n \cdot \dag \). For \(d = 2\), admissible pairs are of the form (ij) with \(i < j\), \((\dag , i)\), and \((i, \dag )\) for all \(1 \le i \le n\); the family \(F _2 = \{ \alpha _0, \alpha _n \}\) is the smallest 2-hitting family. Now consider \(d = 3\). Note that all triples \((i, \dag , i + 1)\) with \(1 \le i \le n - 1\), as well as \((\dag , 1, 2)\) and \((n - 1, n, \dag )\), are admissible, and each of them is hit by a unique schedule. Therefore, the smallest 3-hitting family of schedules consists of all \(n + 1\) schedules: \(F _3 = \{ \alpha _0, \ldots , \alpha _n \}\). For \(d \ge 4\), it remains to observe that every d-hitting family is necessarily \(d'\)-hitting for \(2 \le d' \le d\), hence \(F _3\) is optimal for all \(d \ge 3\).

An important corollary of this example is that, for any \(d \ge 3\) and any partial order \(\mathcal {P}\), every d-hitting family must contain at least \(m + 1\) schedules, where m denotes the maximum number n such that \(\mathcal {P}\) contains \(\mathcal {C} _n \parallel \{\dag \}\). This m is upper-bounded (and this upper bound is tight) by the height of the partial order \(\mathcal {P}\), sometimes called length: the maximal cardinality of a chain (a set of pairwise comparable events) in \(\mathcal {P}\).

3 Hitting Families of Schedules for Trees

3.1 Definitions and Overview

Consider a complete binary tree of height h with edges directed from the root. This tree is the Hasse diagram of a partial order \(\mathcal {T} ^h\), unique up to isomorphism; we will apply tree terminology to \(\mathcal {T} ^h\) itself. The root of \(\mathcal {T} ^h\) forms the 0th layer, its children the 1st layer and so on. The maximum k such that \(\mathcal {T} ^h\) has an element in the kth layer is the height of the tree \(\mathcal {T} ^h\). We will assume that elements of \(\mathcal {T} ^h\) are strings: \(\mathcal {T} ^h = \{0, 1\}^{\le h}\) with \(x \le y\) for \(x, y \in \mathcal {T} ^h\) iff x is a prefix of y. The kth layer of \(\mathcal {T} ^h\) is \(\{0, 1\}^k\), and nodes of the hth layer are leaves. Unless \(x \in \mathcal {T} ^h\) is a leaf, nodes \(x \,0\) and \(x \,1\) are left- and right-children of x, respectively. (Recall that the juxtaposition here denotes concatenation of strings, with the purpose of distinguishing individual strings and their sequences.) The tree \(\mathcal {T} ^h\) has \(n = 2^{h + 1} - 1\) nodes.

The central question that we study in this paper is as follows: How big are optimal d-hitting families of schedules for \(\mathcal {T} ^h\) with n nodes?

As it turns out, for \(\mathcal {T} ^h\) very efficient constructions of d-hitting families exist. It is, in fact, possible, to find such families that have size exponentially smaller than n, the number of events. More specifically, we prove the following results (h is the height of the partial order—the size of the longest chain):
  1. 1.

    For arbitrary \(d \ge 3\), there is a simple d-hitting family of size \(O(n^{d - 2})\) (Claim 5 in the following Subsect. 3.2).

     
  2. 2.

    For \(d = 3\), there is a 3-hitting family of size O(h) (Theorem 7 in Sect. 4).

     
  3. 3.

    For arbitrary \(d \ge 3\), there is a d-hitting family of size \(O(h^{d - 1})\) (Theorem 10 in Sect. 5).

     

Our main technical results are Theorems 7 and 10, shown in the next sections— where they are stated for complete binary trees, with \(h = \log (n + 1) - 1\). (Arbitrary trees are, of course, contained in these complete trees, and our constructions extend in a natural way.) The remainder of this section is structured as follows. In Subsect. 3.2, we prove, as a warm-up, Claim 5. After this, in Subsect. 3.3, we show that the problem of finding families of schedules with size smaller than n turns out to be tricky even when there are no dependencies between events at all. This problem arises as a sub-problem when considering trees (as, indeed, there are no dependencies between the leaves in a tree), and thus our main constructions in Sects. 4 and 5 must be at least as agile.

3.2 Warm-Up: d-Hitting Families of Size \(O(n^{d - 2})\)

Claim 4

The smallest 2-hitting family of schedules for \(\mathcal {T} ^h\) has size 2.

The construction is as follows. Take \(F _{\mathsf {dfs}} = \{ \lambda , \rho \}\) where \(\lambda \) and \(\rho \) are left-to-right and right-to-left DFS (depth-first) traversals of \(\mathcal {T} ^h\), respectively. More formally, these schedules are defined as follows: for \(x, y \in \mathcal {T} ^h\), \(x \le _\lambda y\) if either \(x \le y\) (i.e., x is a prefix of y) or \(x = u \,0 \,x'\) and \(y = u \,1 \,y'\) for some strings \(u, x', y' \in \{0, 1\}^*\); \(x \le _\rho y\) if either \(x \le y\) or \(x = u \,1 \,x'\) and \(y = u \,0 \,y'\). For instance, \(\mathcal {T} ^2\) has \(\lambda = \varepsilon \cdot 0 \cdot 00 \cdot 01 \cdot 1 \cdot 10 \cdot 11\) and \(\rho = \varepsilon \cdot 1 \cdot 11 \cdot 10 \cdot 0 \cdot 01 \cdot 00\). The family \(F _{\mathsf {dfs}} \) is 2-hitting: all admissible pairs (xy) satisfy either \(x \le y\), in which case they are hit by any possible schedule, or \(x \parallel y\), in which case neither is a prefix of the other, \(x = u \,a \,x'\) and \(y = u \,\bar{a} \,y'\) with \(\{ a, \bar{a} \} = \{0, 1\}\), so \(\lambda \) and \(\rho \) schedule them in reverse orders. Since it is clear that a family of size 1 cannot be 2-hitting for \(\mathcal {T} ^h\) with \(h \ge 1\) (as \(\mathcal {T} ^h\) contains at least one pair of incomparable elements), the family \(F _{\mathsf {dfs}}\) is optimal.

Based on this construction for \(d = 2\), it is possible to find d-hitting families for \(d \ge 3\) that have size \(o(n^d)\) where \(n = 2^{h + 1} - 1\) is the number of events in \(\mathcal {T} ^h\):

Claim 5

For any \(d \ge 3\), \(\mathcal {T} ^h\) has a d-hitting family of schedules of size \(O(n^{d - 2})\).

Indeed, group all admissible d-tuples \(\varvec{a} = (a_1, \ldots , a_d)\) into bags agreeing on \(a_1, \ldots , a_{d - 2}\). For each bag, construct a pair of schedules \( \lambda ' = \lambda ' (a_1, \ldots , a_{d - 2})\) and \(\rho ' = \rho ' (a_1, \ldots , a_{d - 2})\) as follows. In both \(\lambda '\) and \(\rho '\), first schedule\(a_1, \ldots , a_{d - 2}\): that is, start with an empty sequence of events, iterate over \(k = 1, \ldots , d - 2\), and, for each k, append to the sequence all events \(x \in \mathcal {T} ^h\) such that \(x \le a_k\). The order in which these xes are appended is chosen in the unique way that respects the partial order \(\mathcal {T} ^h\). Events that are predecessors of several \(a_k\) are only scheduled once, for the least k. Note that no \(a_k\), \(1 \le k \le d\), is a predecessor of any \(a_j\) for \(j < k\), because otherwise the d-tuple \(\varvec{a} = (a_1, \ldots , a_d)\) is not admissible. After this, the events of \(\mathcal {T} ^h\) that have not been scheduled yet form a disjoint union of several binary trees. The schedule \(\lambda '\) then schedules all events according to how the left-to-right DFS traversal \(\lambda \) would work on \(\mathcal {T} ^h\), omitting all events that have already been scheduled, and the schedule \(\rho '\) does the same based on \(\rho \). As a result, these two schedules hit all admissible d-tuples that agree on \(a_1, \ldots , a_{d - 2}\); collecting all such schedules for all possible \(a_1, \ldots , a_{d - 2}\) makes a d-hitting family for \(\mathcal {T} ^h\) of size at most \(2 n^{d - 2}\).

3.3 Antichains: d-Hitting Families of Size \(f(d) \log n\)

An antichain is a partial order where every two elements are incomparable: \(\mathcal {A} _n = \{ v_1 \} \parallel \{ v_2 \} \parallel \ldots \parallel \{ v_n \}\). The set of all schedules for \(\mathcal {A} _n\) is \(S _n\), the set of all permutations, and the set of all admissible d-tuples is the set of all d-arrangements of these n events.

For our problem of finding hitting families of schedules for trees, considering antichains is, in fact, an important subproblem. For example, a complete binary tree with m nodes contains an antichain of size \(\lceil m / 2 \rceil \): the set of its leaves. Thus, any d-hitting family of sublinear size for the tree must necessarily extend a d-hitting family of sublinear size for the antichain—a problem of independent interest that we study in this section.

Theorem 6

For any \(d \ge 3\), the smallest d-hitting family for \(\mathcal {A} _n\) has size between \(g(d) \log n - O(1)\) and \(f(d) \log n\), where \(g(d) \ge d / 2 \log (d + 1)\) and \(f(d) \le d! \, d\).

We sketch the proof of Theorem 6 in the remainder of this section. We will show how to obtain the upper bound by two different means: with the probabilistic method and with a greedy approach. From the results of the following Sect. 4 one can extract a derandomization for \(d = 3\), also with size \(O(\log n)\); and Sect. 5 achieves size \(f(d) \cdot (\log n)^{d - 1}\) for \(d \ge 3\). In the current section we also show a lower bound based on a counting argument; the reasoning above demonstrates that this lower bound for antichains extends to a lower bound for trees (see Corollary 8).

Upper Bound: Probabilistic Method. Consider a family of schedules \(F = \{ \alpha _1, \ldots , \alpha _k \}\) where each \(\alpha _i\) is chosen independently and uniformly at random from \(S _n\); the parameter k will be chosen later. Fix any admissible \(\varvec{a} = (a_1, \ldots , a_d)\). What is the probability that a specific \(\alpha _i\) does not hit \(\varvec{a}\)? A random permutation arranges \(a_1, \ldots , a_d\) in one of d! possible orders without preference to any of them, so this probability is \(1 - 1 / d!\). Since all \(\alpha _i\) are chosen independently, the probability that none of them hits \(\varvec{a}\) is \((1 - 1 / d!)^k\). By the union bound, the probability that at least oned-tuple \(\varvec{a}\) is not hit by any of \(\alpha _i\) does not exceed \(p = n^d \cdot (1 - 1 / d!)^k\).

Now observe that this value of p is exactly the probability that \(F\) is not a d-hitting family. If we now choose k in such a way that \(p < 1\), then the probability of \(F\) being a d-hitting family is non-zero, i.e., a d-hitting family of size k exists. Calculation shows that \(k > (d! \, d) \log n / \log e\) suffices.

The probabilistic method, a classic tool in combinatorics, is due to Erdős [1].

Upper Bound: Greedy Approach. We exploit the following connection between d-hitting families and set covers. Recall that in a set cover problem one is given a number of sets, \(R_1, \ldots , R_s\), and the goal is to find a small number of these sets whose union is equal to \(R = R_1 \cup \ldots \cup R_s\). A set \(R_i\) covers an element \(e \in R\) iff \(e \in R_i\), and this covering is essentially the same as hitting in d-hitting families: elements \(e \in R\) are admissible d-tuples \(\varvec{a} = (a_1, \ldots , a_d)\), and each schedule \(\alpha \) corresponds to a set \(R_\alpha \) that contains all d-tuples \(\varvec{a}\) that it hits. A d-hitting family of schedules is then the same as a set cover.

A well-known approach to the set cover problem is the greedy algorithm, which in our setting works as follows. Initialize a list of all admissible \(\varvec{a} = (a_1, \ldots , a_d)\); on each step, pick some schedule \(\alpha \) that hits the largest number of tuples in the list, and cross out all these tuples. Terminate when the list is empty; the set of all picked schedules is a d-hitting family.

While this algorithm can be used for any partial order \(\mathcal {P}\), in our case we can estimate the quality of its output. The so-called greedy covering lemma by Sapozhenko [18] or a more widely known Lovász-Stein theorem [12, 21] gives an explicit upper bound on the size of the obtained greedy cover in terms of |R| and the density of the instance (the smallest \(\gamma \) such that every \(e \in R\) belongs to at least \(\gamma s\) out of s sets). In our case, \(|R| \le n^d\), and the density is 1 / d!; the obtained upper bound on the size of the smallest d-hitting family is \(d! \, d \cdot \log n / \log e - \mathrm {\varTheta }(d! \, d \log d)\).

Lower Bound. Consider the case \(d = 3\). Take any 3-hitting family \(F = \{ \alpha _1, \ldots , \alpha _k \}\) and consider the binary matrix \(B = (b_{i j})\) of size \(k \times (n - 1)\) where \(b_{i j} = 1\) iff the schedule \(\alpha _i\) places event \(v_j\) before \(v_n\). We claim that all columns of B are pairwise distinct. Indeed, if for some \(j' \ne j''\) and all i it holds that \(b_{i j'} = b_{i j''}\), then no schedule from \(F\) can place \(v_{j'}\) before \(v_n\) without also placing \(v_{j''}\) before \(v_n\), and vice versa. This means that no schedule from \(F\) hits the 3-tuples \(\varvec{a} ' = (v_{j' }, v_n, v_{j''})\) and \(\varvec{a} '' = (v_{j''}, v_n, v_{j' })\), so \(F\) cannot be 3-hitting.

Since all columns of B are pairwise distinct and B is a 0 / 1-matrix, it follows that the number of columns, \(n - 1\), cannot be greater than the number of all subsets of its rows, \(2^k\). From \(n - 1 \le 2^k\) we deduce that \(k \ge \log (n - 1)\). The construction in the general case \(d \ge 3\) is analogous.

As we briefly explained above, the lower bound for an antichain of size n remains valid for any partial order that contains an antichain of size n (as defined in Sect. 2). We invoke this argument in Theorem 7 and Corollary 8 in the following section.

4 3-Hitting Families of Size \(O(\log n)\)

The goal of this section is to construct 3-hitting families of schedules for trees. In fact, the construction that we develop is naturally stated for slightly more involved partial orders, which we call double trees. These double trees are extensions of trees (see Fig. 1). We construct explicit 3-hitting families of schedules of logarithmic size for double trees, so that restriction of these 3-hitting families to appropriate subsets of events gives explicit 3-hitting families for trees and for antichains, also of logarithmic size.

The (binary) double tree of half-height \(h \ge 1\) is the partial order \(\mathcal {D}\) defined as follows. Intuitively, each \(\mathcal {D} ^h\) is a parallel composition (disjoint union) of two copies of \(\mathcal {D} ^{h-1}\), with additional top and bottom (largest and smallest) events; and the induction basis is that \(\mathcal {D} ^0\) consists of a single event. Figure 1 depicts \(\mathcal {D} ^2\), the double tree of half-height 2.
Fig. 1.

(a) A double tree (\(h=2\)); (b) A tree embedded into a double tree

More precisely, (the Hasse diagram of) \(\mathcal {D}\) consists of two complete binary trees of height h that share their set of \(2^h\) leaves; in the first tree, the edges are directed from the root to the leaves, and in the second tree, from the leaves to the root. Formally, \(\mathcal {D} ^h = \{ -1, +1 \} \times \{0, 1\}^{\le h - 1} \cup \{ 0 \} \times \{0, 1\}^{h}\); note that the cardinality of this set is \(3 \cdot 2^h - 2\). Each event \(x = (s_x, x') \in \mathcal {D} ^h\) either belongs to one of the trees (\(s_x \in \{ -1, +1 \}\)) or is a shared leaf (\(s_x = 0\)). We define the ordering by taking the transitive closure of the following relation: let \(x = (s_x, x')\) and \(y = (s_y, y')\) be events of \(\mathcal {D} ^h\); if \(\{s_x, s_y\} \subseteq \{ -1, 0 \}\), then \(x \le y\) whenever \(x'\) is a prefix of \(y'\); and if \(\{s_x, s_y\} \subseteq \{ 0, +1 \}\), then \(x \le y\) whenever \(y'\) is a prefix of \(x'\). (Note that all events xy with \(s_x = s_y = 0\) are pairwise incomparable.)

Theorem 7

The smallest 3-hitting family for the double tree \(\mathcal {D} ^h\) with \(n = 3 \cdot 2^h - 2\) events has size between \(2 h = 2 \log n - O(1)\) and \(4 h = 4 \log n - O(1)\).

Recall that a double tree with \(3 \cdot 2^h - 2\) events contains a complete binary tree with \(2 \cdot 2^h - 1\) nodes, which in turn contains an antichain of size \(2^h\). As a corollary, \(\mathcal {T} ^h\), a tree with \(n = 2 \cdot 2^h - 1\) nodes, has a 3-hitting family of size \(4 h = 4 \log (n + 1) - 4\). Similarly, \(\mathcal {A} _n\), an antichain of size \(n = 2^h\), has a 3-hitting family of size \(4 \log n\). Unlike the constructions from Subsect. 3.3, the construction of Theorem 7 is explicit.

Corollary 8

For an arbitrary (not necessarily balanced) tree of height h, outdegree at most \(\mathrm {\varDelta }\), and with at least 2 children of the root, the smallest 3-hitting family has size between h and \(4 h \log \mathrm {\varDelta }\).

Note that lower bounds proportional to h follow from Example 3. We describe the construction of Theorem 7 below.

Matrix Notation. We use the following notation for families of schedules. Let \(\mathcal {P}\) be a partial order, \(|\mathcal {P} | = n\). Let \(F\) be a family of schedules for \(\mathcal {P}\), \(|F | = m\). We then write
$$\begin{aligned} F = \begin{pmatrix} a_{1 1} &{} a_{1 2} &{} \ldots &{} a_{1 n} \\ a_{2 1} &{} a_{2 2} &{} \ldots &{} a_{2 n} \\ \vdots &{} \vdots &{} \ddots &{} \vdots \\ a_{m 1} &{} a_{m 2} &{} \ldots &{} a_{m n} \\ \end{pmatrix} \end{aligned}$$
where \(F = \{ \alpha _1, \ldots , \alpha _m \}\) and \(\alpha _i = a_{i 1} \cdot a_{i 2} \cdot \ldots \cdot a_{i n}\) for \(1 \le i \le m\). In other words, a family of m schedules for an n-sized partial order is written as an \(m \times n\)-matrix whose entries are elements of \(\mathcal {P}\), with no element appearing more than once in any row. In particular, if \(\alpha \) is a schedule for \(\mathcal {P}\), then we represent it with a row vector. The union of families naturally corresponds to stacking of matrices: \( F _1 \cup F _2 = \begin{pmatrix} F _1 \\ F _2 \end{pmatrix} \), and putting two matrices of the same height m next to each other corresponds to concatenating two families of size m, in order to obtain a family of size m for the union of two partial orders: \(\begin{pmatrix} F _1&F _2 \end{pmatrix}\).
Construction of 3-Hitting Families for Double Trees. We define the families of schedules using induction on h; in matrix notation, the families will be denoted and structured as follows:
$$\begin{aligned} M_h = \begin{bmatrix} A _h&B _h \\ C _h&D _h \\ \end{bmatrix} \end{aligned}$$
where all four blocks are of size \((3 \cdot 2^{h - 1} - 1) \times 2 h\); in total, \(M^h\) will contain 4h schedules, each with \(3 \cdot 2^h - 2\) events.
Base case, \(h = 1\):
$$\begin{aligned} \left[ \begin{array}{c|c} A _1 &{} B _1 \\ \end{array} \right] = \left[ \begin{array}{c|c} C _1 &{} D _1 \\ \end{array} \right] = \left[ \begin{array}{cc|cc} (-1, \varepsilon ) &{} (0, 0) &{} (0, 1) &{} (+1, \varepsilon ) \\ (-1, \varepsilon ) &{} (0, 1) &{} (0, 0) &{} (+1, \varepsilon ) \\ \end{array} \right] . \end{aligned}$$
Note that \(M_1\) specifies both possible schedules two times. However, this redundancy disappears in the inductive step.

Inductive step from \(h \ge 1\) to \(h + 1\): Note that, for \(\ell \in \{0, 1\}\), restricting \(\mathcal {D} ^{h + 1}\) to events of the form \((s, x')\) where \(x' = \ell \,x''\) leads to a partial order isomorphic to \(\mathcal {D} ^h\); these two partial orders are disjoint, and we denote them by \(\mathcal {D} ^h(\ell )\), \(\ell \in \{0, 1\}\); in fact, \(\mathcal {D} ^h(0) \cup \mathcal {D} ^h(1) \cup \{ (-1, \varepsilon ), (+1, \varepsilon ) \}\) forms a partition of \(\mathcal {D} ^{h + 1}\). We assume that the matrix \(M_h\) is known (the inductive hypothesis); for \(\ell \in \{0, 1\}\), we denote its image under the (entry-wise) mapping \((s, x') \mapsto (s, \ell \,x')\) by \(M_h(\ell )\). In other words, \(M_h(\ell )\) is the matrix that defines our (soon proved to be 3-hitting) family of schedules for \(\mathcal {D} ^h(\ell )\); we will also apply the same notation to \(A\), \(B\), \(C\), and \(D\).

Finally, we will need two auxiliary schedules for double trees, which we call left and right traversals. The left traversal \(\lambda \) of \(\mathcal {D} ^{h + 1}\) is defined inductively as follows: it first schedules \((-1, \varepsilon )\), then takes the left traversal of \(\mathcal {D} ^h(0)\), then the left traversal of \(\mathcal {D} ^h(1)\), and then schedules \((+1, \varepsilon )\). The right traversal \(\rho \) is defined symmetrically. Denote by \(\lambda (\ell )\) and \(\rho (\ell )\) left and right traversals of \(\mathcal {D} ^h(\ell )\), respectively (we omit reference to h since this does not create confusion). ThenOur result is that, for each h, \(M_h\) is a 3-hitting family of schedules for \(\mathcal {D} ^h\). The key part of the proof relies on the following auxiliary property, which is a stronger form of the 2-hitting condition.

Lemma 9

For any pair of distinct events \(\varvec{a} = (a_1, a_2)\) from \(\mathcal {D} ^h\), if there is a schedule for \(\mathcal {D} ^h\) that hits \(\varvec{a}\), then each of the matrices \( \left[ \begin{array}{c|c} A _h &{} B _h \\ \end{array} \right] \) and \( \left[ \begin{array}{c|c} C _h &{} D _h \\ \end{array} \right] \) contains a schedule for \(\mathcal {D} ^h\) where \(a_1\) is placed in the first half and \(a_2\) is placed in the second half.

5 d-Hitting Families for \(d \ge 3\) of Size \(f(d) (\log n)^{d - 1}\)

Fix some d and let \(\mathcal {T} ^h\) be a complete binary tree of height h, as defined in Subsect. 3.1. In this section we prove the following theorem.

Theorem 10

For any \(d \ge 2\) the complete binary tree of height h has a d-hitting family of schedules of size \(\exp (d) \cdot h^{d - 1}\).

Note that in terms of the number of nodes of \(\mathcal {T} ^h\), which is \(n = 2^{h + 1} - 1\), Theorem 10 gives a d-hitting family of size polylogarithmic in n. The proof of the theorem is constructive, and we divide it into three steps. The precise meaning to the steps relies on auxiliary notions of a pattern and of d-tuples conforming to a pattern; we give all necessary definitions below.

Lemma 11

For each admissible d-tuple \(\varvec{a} = (a_1, \ldots , a_d)\) there exists a pattern p such that \(\varvec{a}\) conforms to p.

Lemma 12

For each pattern p there exists a schedule \(\alpha _p\) that hits all d-tuples \(\varvec{a}\) that conform to p.

Lemma 13

The total number of patterns, up to isomorphism, does not exceed \(\exp (d) \cdot h^{d - 1}\).

The statement of Theorem 10 follows easily from these lemmas. The key insight is the definition of the pattern and the construction of Lemma 12.

In the sequel, for partial orders that are trees directed from the root we will use the standard terminology for graphs and trees (relying on Hasse diagrams): node, outdegree, siblings, 0- and 1-principal subtree of a node, isomorphism. We denote the parent of a node u by \({{\mathrm{par}}}u\) and the least common ancestor of nodes u and v by \({{\mathrm{lca}}} (u, v)\).

If T is a tree and \(X \subseteq T\) is a subset of its nodes, then by \([X]\) we denote the \({{\mathrm{lca}}}\)-closure of X: the smallest set \(Y \subseteq T\) such that, first, \(X \subseteq Y\) and, second, for any \(y_1, y_2 \in Y\) it holds that \({{\mathrm{lca}}} (y_1, y_2) \in Y\). The following claim is a variation of a folklore Lemma 1 in [7].

Claim 14

\(|[X]| \le 2 \, |X| - 1\).

Definition 15

(pattern). A pattern is a quintuple \(p = (D, \preccurlyeq , s, \ell , \pi )\) where:
  • \(d \le |D| \le 2 d - 1\),

  • \((D, \preccurlyeq )\) is a partial order which is, moreover, a tree directed from the root,

  • the number of non-leaf nodes in \((D, \preccurlyeq )\) does not exceed \(d - 1\),

  • each node of \((D, \preccurlyeq )\) has outdegree at most 2,

  • the partial function \(s :D \rightharpoonup \{0, 1\}\) specifies, for each pair of siblings \(v_1, v_2\) in \((D, \preccurlyeq )\), which is the left and which is the right child of its parent: \(s (v_t) = 0\) and \(s (v_{3 - t}) = 1\) for some \(t \in \{1, 2\}\); the value of \(s \) is undefined on all other nodes of D,

  • the partial function \(\ell :D \rightharpoonup \{0, 1, \ldots , h - 1\}\) associates a layer with each non-leaf node of \((D, \preccurlyeq )\), so that \(u \prec v\) implies \(\ell (u) < \ell (v)\); the value of \(\ell \) is undefined on all leaves of D, and

  • \(\pi \) is a schedule for \((D, \preccurlyeq )\).

We remind the reader that the symbol \(\le \) refers to the same partial order as \(\mathcal {T} ^h\).

Definition 16

(conformance). Take any pattern \(p = (D, \preccurlyeq , s, \ell , \pi )\) and any tuple \(\varvec{a} = (a_1, \ldots , a_d)\) of d distinct elements of the partial order \(\mathcal {T} ^h\). Consider the set \(\{ a_1, \ldots , a_d \}\): the restriction of \(\le \) to its \({{\mathrm{lca}}}\)-closure \(A = [\{ a_1, \ldots , a_d \}]\) is a binary tree, \((A, \le )\). Suppose that the following conditions are satisfied:
  1. (a)

    the trees \((D, \preccurlyeq )\) and \((A, \le )\) are isomorphic: there exists a bijective mapping \(i :D \rightarrow A\) such that \(v_1 \preccurlyeq v_2\) in D iff \(i (v_1) \le i (v_2)\) in \(\mathcal {T} ^h\);

     
  2. (b)

    the partial function \(s\) correctly indicates left- and right-subtree relations: for any \(v \in D\), \(s (v) = b \in \{0, 1\}\) if and only if \(i (v)\) lies in the b-principal subtree of \(i ({{\mathrm{par}}}(v))\);

     
  3. (c)

    the partial function \(\ell \) correctly specifies the layer inside \(\mathcal {T} ^h\): for any non-leaf \(v \in D\), \(\ell (v) = |i (v)|\); recall that elements of \(\mathcal {T} ^h\) are binary strings from \(\{0, 1\}^{\le h}\);

     
  4. (d)

    the schedule \(\pi \) for \((D, \preccurlyeq )\) hits the tuple \(i ^{-1}(\varvec{a}) = (i ^{-1}(a_1), \ldots , i ^{-1}(a_d))\).

     

Then we shall say that the tuple \(\varvec{a}\)conforms to the pattern p.

We now sketch the proof of Lemma 12. Fix any pattern \(p = (D, \preccurlyeq , s, \ell , \pi )\). Recall that we need to find a schedule \(\alpha _p\) that hits all d-tuples \(\varvec{a} = (a_1, \ldots , a_d)\) conforming to p. We will pursue the following strategy. We will cut the tree \(\mathcal {T} ^h\) into multiple pieces; this cutting will be entirely determined by the pattern p, independent of any individual \(\varvec{a}\). Each piece in the cutting will be associated with some element \(c \in D\), so that each element of D can have several pieces associated with it. In fact, every piece will form a subtree of \(\mathcal {T} ^h\) (although this will be of little importance). The key property is that, for every d-tuple \(\varvec{a} = (a_1, \ldots , a_d)\) conforming to p, if \(i\) is the isomorphism from Definition 16, then each event \(a_k\), \(1 \le k \le d\), will belong to a piece associated with \(i ^{-1}(a_k)\). As a result, the desired schedule \(\alpha _p\) can be obtained in the following way: arrange the pieces according to how \(\pi \) schedules elements of D and pick any possible schedule inside each piece. This schedule will be guaranteed to meet the requirements of the lemma.

6 From Hitting Families to Systematic Testing

Hitting families of schedules serve as a theoretical framework for systematically exposing all bugs of small depth. However, bridging the gap from theory to practice poses several open challenges, which we describe in this section.

To make the discussion concrete, we focus on a specific scenario: testing the rendering of web pages in the browser. Web pages exhibit event-driven concurrency: as the browser parses the page, it concurrently executes JavaScript code registered to handle various automatic or user-triggered events. Many bugs occur as a consequence of JavaScript’s ability to manipulate the structure of the page while the page is being parsed. Previous work shows such bugs are often of small depth [10, 17].
Fig. 2.

Example of bugs of depth \(d=2\) and \(d=3\) in a web page

As an example, consider the web page in Fig. 2. In the example, the image (represented by the Open image in new window tag) has an on-load event handler that calls the function loaded() once the image is loaded. The function, defined in a separate script block, changes the text of the paragraph p to Loaded. There are two potential bugs in this example. The first one is of depth \(d=2\), and it occurs if the image is loaded quickly (for example, from the cache), before the browser parses the Open image in new window tag. In this case, the on-load handler tries to call an undefined function. The second bug is of depth \(d=3\), and it occurs if the handler is executed after the Open image in new window tag is parsed, but before the Open image in new window tag is parsed. In this case, the function loaded() tries to access a non-existent HTML element.

Next, we identify and discuss three challenges.
Fig. 3.

Using a timer to fix the bug from Fig. 2 involving a non-existent element

Events and Partial Orders Need Not Be Static. Our theoretical model assumes a static partially-ordered set of events, and allows arbitrary reordering of independent (incomparable) events. For the web page in Fig. 2, there are three parsing events (corresponding to the three HTML tags) and an on-load event. The parsing events are chained in the order their tags appear in the code. The on-load event happens after the Open image in new window tag is parsed, but independently of the other parsing events, giving a tree-shaped partial order.

In more complex web pages, the situation is not so simple. Events may be executions of scripts with complex internal control-flow and data dependencies, as well as with effect on the global state. Once a schedule is reordered, new events might appear, and some events might never trigger. An example showing a more realistic situation is given in Fig. 3. In order to fix the bug involving a non-existent HTML element p, the programmer now explicitly checks the result of getElementById(). If p does not exist (p == null), the programmer sets a timer to invoke the function loaded() again after 10 milliseconds. As a consequence, depending on what happens first—the on-load event or the parsing of Open image in new window—we may or may not observe one or more timeout events. Note that the chain of timeout events also depends on parsing the Open image in new window tag. If the tag is not parsed, the loaded() function does not exist, so no timer is ever set. Moreover, the number of timeout events depends on when exactly the Open image in new window tag is parsed.

The example shows that there is a mismatch between the assumption of static partially ordered events and the dynamic nature of events occuring in complex web pages. Ideally, the mismatch should be settled in future work by explicitly modeling this dynamic nature. However, even the current theory of hitting families can be applied as a testing heuristic. While we lose completeness (in the sense of hitting all depth-d bugs), we retain the variety of different event orderings. In the context of web pages, an initial execution of a page gives us an initial partially ordered set of events. We use it to construct a hitting family of schedules, which we optimistically try to execute. The approach is based on the notion of approximate replay, which is employed by \(R^4\), a stateless model checker for web pages [10]. We come back to this approach later in the section.

Another approach is to construct hitting families on the fly: Such a construction would unravel events and the partial order dynamically during execution, and non-deterministically construct a schedule from a corresponding hitting family. In this way, the issue of reordering events in an infeasible way does not arise, simply because nothing is reordered. This is in line with how PCT [3] and delay-bounded scheduling [6] work. On-the-fly constructions of small hitting families are a topic for future work.

Beyond Trees. Our results on trees are motivated by the existing theoretical models of asynchronous programs [6, 8, 11], where the partial order induced by event handlers indeed form trees. However, in the context of web pages, events need not necessarily be ordered as nodes of a tree. An example of a feature that introduces additional ordering constraints is deferred scripts. Scripts marked as deferred are executed after the page has been loaded, and they need to be executed in the order in which their corresponding Open image in new window tags were parsed [15]. The tree approximation corresponds to testing the behavior of pages when the deferred scripts are treated as normal scripts and loaded right away. An open question is to generalize our construction to other special cases of partial orders that capture common programming idioms.

Unbalanced Trees. For a tree of height h, constructions from Sects. 4 and 5 give 3-hitting families of size O(h) and \(O(h^2)\), respectively. If the tree is balanced, the cardinality of these families are exponentially smaller than the number of events in the tree. However, in the web page setting, trees are not balanced.
Table 1.

For each website, the table show the number of events in the initial execution, the height of the partial order (happens-before graph), the number of schedules generated for \(d=3\), and the number of schedules for \(d=3\) with pruning based on races.

Website

# Events

Height

\(d=3\)

\(d=3\) (pruned)

abc.xyz

337

288

561

0

newscorp.com

1362

875

2689

100

thehartford.com

2018

1547

3913

138

www.allstate.com

4534

3822

9023

106

www.americanexpress.com

2971

2586

5897

340

www.bankofamerica.com

2305

2095

4561

150

www.bestbuy.com

301

248

576

10

www.comcast.com

188

118

337

16

www.conocophillips.com

4184

3478

8286

248

www.costco.com

7331

6390

14614

364

www.deere.com

2286

1902

4516

236

www.generaldynamics.com

2820

2010

5611

272

www.gm.com

2337

1473

4600

94

www.gofurther.com

1117

638

2154

568

www.homedepot.com

3780

2100

7515

1526

www.humana.com

5611

4325

11174

2058

www.johnsoncontrols.com

2953

2395

5881

450

www.jpmorganchase.com

4134

3519

8247

1316

www.libertymutual.com

3885

3560

7735

324

www.lowes.com

6938

4383

13778

3438

www.massmutual.com

3882

3313

7682

1852

www.morganstanley.com

2752

2301

5402

128

www.utc.com

4081

3266

8100

206

www.valero.com

2116

1849

4178

38

In order to inspect the shape of partial orders occurring in web pages, we randomly selected 24 websites of companies listed among the top 100 of Fortune 500 companies. For each website, we used \(R^4\) [10] to record an execution and construct the happens-before relation (the partial order). Table 1 shows the number of events and the height of the happens-before graph for the websites. The results indicate that a typical website has most of the events concentrated in a backbone of very large height, proportional to the total number of events.

The theory shows that going below \(\mathrm {\varTheta }(h)\) is impossible in this case unless \(d < 3\); and this can indeed lead to large hitting families: for example, our construction for \(h= 1000\) and \(d=4\) corresponds to several million tests. However, not all schedules of the partial ordering induced by the event handlers may be relevant: if two events are independent (commute), one need not consider schedules which only differ in their ordering. Therefore, since hitting families are defined on an arbitrary partial order, not only on the happens-before order, we can use additional information, such as (non-)interference of handlers, to reduce the partial ordering first.

For web pages, we apply a simple partial order reduction to reduce the size of the input trees in the following way. We say a pair of events race if they both access some memory location or some DOM element, with at least one of them writing to this location or the DOM element. Events that do not participate in races commute with all other events, so they need not be reordered if our goal is to expose bugs.

\(R^4\) internally uses a race detection tool (EventRacer [17]) to over-approximate the set of racing events. In order to compute hitting families, we construct a pruned partial order from the original tree of events. As an example, for \(d = 3\) and the simple \(O(n^{d-2})\) construction, instead of selecting \(a_1\) arbitrarily, we select it from the events that participate in races. We then perform the left-to-right and right-to-left traversals as usual. In total, the number of generated schedules is 2r, where r is the number of events participating in races. This number can be significantly smaller than 2n, as can be seen in the fourth (\(d=3\)) and fifth (\(d=3\) pruned) columns of Table 1.

7 Conclusions

We have introduced hitting families as the basis for systematic testing of concurrent systems and studied the size of optimal d-hitting families for trees and related partial orders.

We have shown that a range of combinatorial techniques can be used to construct d-hitting families: we use a greedy approach, a randomized approach, and a construction based on DFS traversals; we also develop a direct inductive construction and a construction based on what we call patterns. The number of schedules in the pattern-based construction is polynomial in the height—for balanced trees, this is exponentially smaller than the total number of nodes.

Our development of hitting families was motivated by the testing of asynchronous programs, and we studied the partial ordering induced by the happens-before relationship on event handlers. While this ordering gives a useful testing heuristic in scenarios such as rendering of web pages, the notion of hitting families applies to any partial ordering, and we leave its further uses to future work.

Acknowledgements

We thank Madan Musuvathi for insightful discussions and comments.

Copyright information

© Springer International Publishing Switzerland 2016

Authors and Affiliations

  • Dmitry Chistikov
    • 1
    • 2
  • Rupak Majumdar
    • 1
  • Filip Niksic
    • 1
  1. 1.Max Planck Institute for Software Systems (MPI-SWS)Kaiserslautern and SaarbrückenGermany
  2. 2.Department of Computer ScienceUniversity of OxfordOxfordUK

Personalised recommendations