Reorder Pointer Flow in Sound Concurrency Bug Prediction
Open Access
- 6 February 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-13
Abstract
Due to the non-determinism of thread interleaving, predicting concurrency bugs has long been an extremely difficult task. Recently, several sound bug-detecting approaches were proposed. These approaches are based on local search, i.e., mutating the sequential order of the observed trace and predicting whether the mutated sequential order can trigger a bug. Surprisingly, during this process, they never consider reordering the data flow of the pointers, which can be the key point to detecting many complex bugs. To alleviate this weakness, we propose a new flow-sensitive point-to analysis technique ConPTA to help actively reorder the pointer flow during the sequential order mutation process. Based on ConPTA, we further propose a new sound predictive bug-detecting approach Eagle to predict four types of concurrency bugs. They are null pointer dereference (NPD), uninitialized pointer use (UPU), use after free (UAF), and double free (DF). By actively reordering the pointer flow, Eagle can explore a larger search space of the thread interleaving during the mutation and thus detect more concurrency bugs. Our evaluation of Eagle on 10 real-world multi-threaded programs shows that Eagle significantly outperforms four state-of-the-art bug-detecting approaches UFO, ConVul, ConVulPOE and Period in both effectiveness and efficiency.Keywords
Funding Information
- National Natural Science Foundation of China (61932012, 62132020, 62232016, 62372437)
- National Key Research and Development Program of China (2022YFB3104004)
- Key Research Program of Frontier Science, Chinese Academy of Sciences (ZDBS-LY-7006)
- Youth Innovation Promotion Association of the Chinese Academy of Sciences (Y2021041, 2019111)
This publication has 56 references indexed in Scilit:
- Predicting null-pointer dereferences in concurrent programs2012
- IFRit2012
- Sound predictive race detection in polynomial time2012
- SAGE: Whitebox Fuzzing for Security TestingQueue, 2012
- Detecting and surviving data races using complementary schedules2011
- Race directed random testing of concurrent programs2008
- RaceTrack2005
- EraserACM Transactions on Computer Systems, 1997
- Testing Shared MemoriesSIAM Journal on Computing, 1997
- Time, clocks, and the ordering of events in a distributed systemCommunications of the ACM, 1978