Dynamic analysis for concurrency bugs in multithreaded programs

多線程程序中並發缺陷的動態分析

Student thesis: Doctoral Thesis

View graph of relations

Author(s)

  • Yan CAI

Related Research Unit(s)

Detail(s)

Awarding Institution
Supervisors/Advisors
Award date3 Oct 2014

Abstract

Concurrency bugs are severe problems in multithreaded programs. They include data races, atomicity violations, and deadlocks. To detect them, existing static techniques report many false positives, and yet dynamic techniques fail to scale up to handle large-scale programs and effectively isolate real concurrency bugs from all reported warnings. In this thesis, we propose novel dynamic techniques to analyze and manipulate lock usage sequences for scalable detection and effective isolation of real concurrency bugs. The first contribution is to address the scalability challenge in dynamic deadlock prediction. We propose Magiclock, a novel technique that efficiently analyzes execution traces to locate deadlock warnings. Magiclock eliminates irrelevant lock operations, merges such operations that are equivalent among one another into the same operation, and explores one possible sequence among all for each set of these operations, which suffices to detect all deadlocks warnings. Our experiments show that Magiclock can be thousand times more efficient than existing techniques to locate deadlock warnings. The second contribution is to address the challenges in isolating real deadlocks from a set of deadlock warnings. A reported deadlock warning can be a real deadlock or a false positive. We propose a family of novel techniques, MagicScheduler, ASN, and ConLock, to handle different aspects of them. MagicScheduler aims to check an execution against multiple deadlock warnings. ASN divides an execution trace into segments, and steers the executions of threads involved in a deadlock warning in another execution segments by segments toward triggering real deadlocks. ConLock further handles false positives. It analyzes an execution trace to identify a set of locking sequence constraints necessary to turn the warning into a real deadlock if any, and schedules another execution not to violate these constraints. Any constraint violation indicates the latter execution cannot trigger the intended deadlock, which should be the case for false positive warnings. Experiments show both ASN and ConLock are significantly more effective than existing techniques in triggering real deadlocks, whereas MagicScheduler can be as effective as existing techniques even in single warning scenarios. Moreover, ConLock effectively shortens the whole confirmation period by terminating the executions via the detection of constraint violations. The third contribution is an online lock trace reduction technique. Precise happened-before based dynamic techniques fully track lock operations to infer the causal relationships among threads through vector clocks. Each vector clock operation incurs O(n) in time complexity and storage complexity, where n is the total number of threads. We exploit the observation that a thread may frequently acquire and release the same lock before this lock is acquired by any other threads. We propose a technique entitled LOFT to eliminate a class of vector clock operations not affecting the orders among threads, reduce the tracking overhead, and shorten the resultant lock trace thus generated. Experimental results show that LOFT can reduce, on average, 64% of O(n) vector clock operations needed to track locking operations. In conclusion, this thesis contributes a set of novel techniques to efficiently and effectively detect and confirm deadlocks bugs and an online lock trace reduction technique for large-scale multithreaded programs.

    Research areas

  • Threads (Computer programs), Reliability, Computer software, Parallel programming (Computer science)