Abstract:Concurrent bugs are difficult to trigger, debug, and detect. Dynamic program analysis techniques have been proven useful in addressing such challenges. Due to non-deterministic nature of concurrent programs in which the major source of non-determinism is the shared memory, obtaining the order of shared memory accesses, i.e., shared memory dependences, is the basis of such dynamic analyses. This work proposes a survey framework to demonstrate the key issues in obtaining the shared memory dependences. The framework includes four performance metrics (immediacy, accuracy, efficiency and simplicity), two categories of approaches (online tracing and offline synthesis), and two categories of applications (trace analysis and concurrency control). Existing techniques as well as potential future work are studied in the paper.