| Summary: | <p>Asynchronous programming is a ubiquitous idiom for concurrent programming, where sequential units of code, called events, are scheduled and run atomically by a scheduler. While running, an event can post additional events for future execution by the scheduler. Asynchronous programs can have subtle bugs due to the non-deterministic scheduling of events, and a lot of recent research has focused on systematic testing of these programs.</p> <br/> <p>Empirically, many bugs in asynchronous programs have small bug depth: that is, the number of events d that must be scheduled in a specific order for a bug to be exposed is small. A natural question then is to find a d-hitting family of schedules: a set of schedules is 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. A d-hitting family is guaranteed to expose all bugs with d events. By analyzing the structure of the tree of events in an asynchronous execution, we provide explicit constructions for small d-hitting families of schedules. When the tree is balanced, our construction is polylogarithmic in the number of events.</p> <br/> <p>We have implemented our algorithm for computing d-hitting families on top of a race condition checker for web pages. We empirically confirm previous findings that many bugs occur with small bug depth. We demonstrate that even with d = 2 we are able to detect bugs in real web applications and that we get a small 3-hitting family for d = 3.</p>
|
|---|