Data provenance tracking for concurrent programs

Abstract

We propose Last Writer Slicing (LWS), a mechanism for tracking data provenance information in multithreaded code in a production setting. Last writer slices dynamically track provenance of values by recording the thread and operation that last wrote each variable. We show that this information complements core dumps and greatly improves debugability. We also propose communication traps (CTraps), an extensible framework that uses LWS to interpose on operations that lead to inter-thread communication. We show how to use CTraps to implement multiple dynamic analysis tools for mulithreaded programs. Our evaluation on server programs and PARSEC benchmarks shows that LWS has low run time overheads (0-15%) for many applications, including mem-cached, LevelDB, MySQL, and Apache. Our debugging case studies of real, buggy programs shows that LWS are indeed useful for debugging.