Tracking and Reducing Uncertainty in Dataflow Analysis-Based Dynamic Parallel Monitoring
International Conference on Parallel Architectures and Compilation Techniques (PACT 2015), Oct 18, 2015 - Oct 21, 2015, San Francisco, CA.
Michelle Goodstein, Phillip Gibbons, Michael Kozuch*, Todd Mowry
Carnegie Mellon University
* Intel Labs Pittsburgh
Dataflow analysis-based dynamic parallel monitoring (DADPM) is a recent approach for identifying bugsin parallel software as it executes, based on the key insight of explicitly modeling a sliding window of uncertainty across parallel threads. While this makes the approach practical and scalable, it also introduces the possibility of false positives inthe analysis. In this paper, we improve upon the DADPM framework through two observations. First, by explicitly tracking new "uncertain" states in the metadata lattice, we can distinguish potential false positives from true positives. Second, as the analysis tool runs dynamically, it can use the existence (or absence) of observed uncertain states to adjust the tradeoff between precision and performance on-the-fly. For example, we demonstrate how the epoch size parameter canbe adjusted dynamically in response to uncertainty in order to achieve better performance and precision than when the tool is statically configured. This paper shows how to adapt a canonical data flow analysis problem (reaching definitions) and a popular security monitoring tool (TAINTCHECK) to our new uncertainty-tracking framework, and provides new provable guarantees that reported true errors are now precise.
FULL REPORT: pdf