research-article

Canary: practical static detection of inter-thread value-flow bugs

Authors:

Charles ZhangAuthors Info & Claims

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

Pages 1126 - 1140

https://doi.org/10.1145/3453483.3454099

Published: 18 June 2021 Publication History

Abstract

Concurrent programs are still prone to bugs arising from the subtle interleavings of threads. Traditional static analysis for concurrent programs, such as data-flow analysis and symbolic execution, has to explicitly explore redundant control states, leading to prohibitive computational complexity.

This paper presents a value flow analysis framework for concurrent programs called Canary that is practical to statically find diversified inter-thread value-flow bugs. Our work is the first to convert the concurrency bug detection to a source-sink reachability problem, effectively reducing redundant thread interleavings. Specifically, we propose a scalable thread-modular algorithm to capture data and interference dependence in a value-flow graph. The relevant edges of value flows are annotated with execution constraints as guards to describe the conditions of value flows. Canary then traverses the graph to detect concurrency defects via tracking the source-sink properties and solving the aggregated guards of value flows with an SMT solver to decide the realizability of interleaving executions. Experiments show that Canary is precise, scalable and practical, detecting over eighteen previously unknown concurrency bugs in large, widely-used software systems with low false positives.

References

[1]

Domagoj Babic and Alan J. Hu. 2008. Calysto: Scalable and Precise Extended Static Checking. In Proceedings of the 30th International Conference on Software Engineering (ICSE ’08). Association for Computing Machinery, New York, NY, USA. 211–220. isbn:9781605580791 https://doi.org/10.1145/1368088.1368118

Digital Library

[2]

Jia-Ju Bai, Julia Lawall, Qiu-Liang Chen, and Shi-Min Hu. 2019. Effective Static Analysis of Concurrency Use-After-Free Bugs in Linux Device Drivers. In 2019 USENIX Annual Technical Conference, USENIX ATC 2019, Renton, WA, USA, July 10-12, 2019, Dahlia Malkhi and Dan Tsafrir (Eds.). USENIX Association, 255–268. https://www.usenix.org/conference/atc19/presentation/bai

[3]

Josh Berdine, Cristiano Calcagno, Byron Cook, Dino Distefano, Peter W. O’Hearn, Thomas Wies, and Hongseok Yang. 2007. Shape Analysis for Composite Data Structures. In Computer Aided Verification, 19th International Conference, CAV 2007, Berlin, Germany, July 3-7, 2007, Proceedings, Werner Damm and Holger Hermanns (Eds.) (Lecture Notes in Computer Science, Vol. 4590). Springer, 178–192. https://doi.org/10.1007/978-3-540-73368-3_22

[4]

Tom Bergan, Dan Grossman, and Luis Ceze. 2014. Symbolic execution of multithreaded programs from arbitrary program contexts. In Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications, OOPSLA 2014, part of SPLASH 2014, Portland, OR, USA, October 20-24, 2014, Andrew P. Black and Todd D. Millstein (Eds.). ACM, 491–506. https://doi.org/10.1145/2660193.2660200

Digital Library

[5]

Al Bessey, Ken Block, Ben Chelf, Andy Chou, Bryan Fulton, Seth Hallem, Charles Henri-Gros, Asya Kamsky, Scott McPeak, and Dawson Engler. 2010. A Few Billion Lines of Code Later: Using Static Analysis to Find Bugs in the Real World. Commun. ACM, 53, 2 (2010), Feb., 66–75. issn:0001-0782 https://doi.org/10.1145/1646353.1646374

Digital Library

[6]

Sam Blackshear, Nikos Gorogiannis, Peter W. O’Hearn, and Ilya Sergey. 2018. RacerD: Compositional Static Race Detection. Proc. ACM Program. Lang., 2, OOPSLA (2018), Article 144, Oct., 28 pages. https://doi.org/10.1145/3276514

Digital Library

[7]

Yan Cai, Biyun Zhu, Ruijie Meng, Hao Yun, Liang He, Purui Su, and Bin Liang. 2019. Detecting Concurrency Memory Corruption Vulnerabilities. In Proceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2019). Association for Computing Machinery, New York, NY, USA. 706–717. isbn:9781450355728 https://doi.org/10.1145/3338906.3338927

Digital Library

[8]

Satish Chandra, Stephen J. Fink, and Manu Sridharan. 2009. Snugglebug: A Powerful Approach to Weakest Preconditions. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’09). Association for Computing Machinery, New York, NY, USA. 363–374. isbn:9781605583921 https://doi.org/10.1145/1542476.1542517

Digital Library

[9]

Hongxu Chen, Shengjian Guo, Yinxing Xue, Yulei Sui, Cen Zhang, Yuekang Li, Haijun Wang, and Yang Liu. 2020. MUZZ: Thread-aware Grey-box Fuzzing for Effective Bug Hunting in Multithreaded Programs. In 29th USENIX Security Symposium, USENIX Security 2020, August 12-14, 2020, Srdjan Capkun and Franziska Roesner (Eds.). USENIX Association, 2325–2342. https://www.usenix.org/conference/usenixsecurity20/presentation/chen-hongxu

[10]

Sigmund Cherem, Lonnie Princehouse, and Radu Rugina. 2007. Practical Memory Leak Detection Using Guarded Value-Flow Analysis. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’07). Association for Computing Machinery, New York, NY, USA. 480–491. isbn:9781595936332 https://doi.org/10.1145/1250734.1250789

Digital Library

[11]

Jong-Deok Choi, Manish Gupta, Mauricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. 1999. Escape Analysis for Java. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’99). Association for Computing Machinery, New York, NY, USA. 1–19. isbn:1581132387 https://doi.org/10.1145/320384.320386

Digital Library

[12]

Ravi Chugh, Jan W. Voung, Ranjit Jhala, and Sorin Lerner. 2008. Dataflow Analysis for Concurrent Programs Using Datarace Detection. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’08). Association for Computing Machinery, New York, NY, USA. 316–326. isbn:9781595938602 https://doi.org/10.1145/1375581.1375620

Digital Library

[13]

Edmund M. Clarke, Orna Grumberg, Marius Minea, and Doron A. Peled. 1999. State Space Reduction Using Partial Order Techniques. Int. J. Softw. Tools Technol. Transf., 2, 3 (1999), 279–287. https://doi.org/10.1007/s100090050035

[14]

Patrick Cousot and Radhia Cousot. 1979. Systematic Design of Program Analysis Frameworks. In Proceedings of the 6th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL ’79). Association for Computing Machinery, New York, NY, USA. 269–282. isbn:9781450373579 https://doi.org/10.1145/567752.567778

Digital Library

[15]

Leonardo Mendonça de Moura and Nikolaj Bjørner. 2008. Z3: An Efficient SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems, 14th International Conference, TACAS 2008, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2008, Budapest, Hungary, March 29-April 6, 2008. Proceedings, C. R. Ramakrishnan and Jakob Rehof (Eds.) (Lecture Notes in Computer Science, Vol. 4963). Springer, 337–340. https://doi.org/10.1007/978-3-540-78800-3_24

[16]

Isil Dillig, Thomas Dillig, Alex Aiken, and Mooly Sagiv. 2011. Precise and compact modular procedure summaries for heap manipulating programs. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2011, San Jose, CA, USA, June 4-8, 2011, Mary W. Hall and David A. Padua (Eds.). ACM, 567–577. https://doi.org/10.1145/1993498.1993565

Digital Library

[17]

Azadeh Farzan, Zachary Kincaid, and Andreas Podelski. 2013. Inductive data flow graphs. In The 40th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’13, Rome, Italy - January 23 - 25, 2013, Roberto Giacobazzi and Radhia Cousot (Eds.). ACM, 129–142. https://doi.org/10.1145/2429069.2429086

Digital Library

[18]

Azadeh Farzan and P. Madhusudan. 2007. Causal Dataflow Analysis for Concurrent Programs. In Tools and Algorithms for the Construction and Analysis of Systems, 13th International Conference, TACAS 2007, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2007 Braga, Portugal, March 24 - April 1, 2007, Proceedings, Orna Grumberg and Michael Huth (Eds.) (Lecture Notes in Computer Science, Vol. 4424). Springer, 102–116. https://doi.org/10.1007/978-3-540-71209-1_10

[19]

Azadeh Farzan, P. Madhusudan, Niloofar Razavi, and Francesco Sorrentino. 2012. Predicting Null-Pointer Dereferences in Concurrent Programs. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE ’12). Association for Computing Machinery, New York, NY, USA. Article 47, 11 pages. isbn:9781450316149 https://doi.org/10.1145/2393596.2393651

Digital Library

[20]

Cormac Flanagan and Patrice Godefroid. 2005. Dynamic partial-order reduction for model checking software. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, USA, January 12-14, 2005, Jens Palsberg and Martín Abadi (Eds.). ACM, 110–121. https://doi.org/10.1145/1040305.1040315

Digital Library

[21]

Malay Ganai, Dongyoon Lee, and Aarti Gupta. 2012. DTAM: Dynamic Taint Analysis of Multi-Threaded Programs for Relevancy. In Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering (FSE ’12). Association for Computing Machinery, New York, NY, USA. Article 46, 11 pages. isbn:9781450316149 https://doi.org/10.1145/2393596.2393650

Digital Library

[22]

Patrice Godefroid. 1997. VeriSoft: A Tool for the Automatic Analysis of Concurrent Reactive Software. In Computer Aided Verification, 9th International Conference, CAV ’97, Haifa, Israel, June 22-25, 1997, Proceedings, Orna Grumberg (Ed.) (Lecture Notes in Computer Science, Vol. 1254). Springer, 476–479. https://doi.org/10.1007/3-540-63166-6_52

[23]

Shengjian Guo, Markus Kusano, Chao Wang, Zijiang Yang, and Aarti Gupta. 2015. Assertion guided symbolic execution of multithreaded programs. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering, ESEC/FSE 2015, Bergamo, Italy, August 30 - September 4, 2015, Elisabetta Di Nitto, Mark Harman, and Patrick Heymans (Eds.). ACM, 854–865. https://doi.org/10.1145/2786805.2786841

Digital Library

[24]

Ben Hardekopf and Calvin Lin. 2009. Semi-Sparse Flow-Sensitive Pointer Analysis. In Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’09). Association for Computing Machinery, New York, NY, USA. 226–238. isbn:9781605583792 https://doi.org/10.1145/1480881.1480911

Digital Library

[25]

Ben Hardekopf and Calvin Lin. 2011. Flow-sensitive pointer analysis for millions of lines of code. In Proceedings of the CGO 2011, The 9th International Symposium on Code Generation and Optimization, Chamonix, France, April 2-6, 2011. IEEE Computer Society, 289–298. https://doi.org/10.1109/CGO.2011.5764696

[26]

Marijn JH Heule, Oliver Kullmann, and Armin Biere. 2018. Cube-and-conquer for satisfiability. In Handbook of Parallel Constraint Reasoning. Springer, 31–59.

[27]

Jeff Huang. 2015. Stateless model checking concurrent programs with maximal causality reduction. In Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, June 15-17, 2015, David Grove and Steve Blackburn (Eds.). ACM, 165–174. https://doi.org/10.1145/2737924.2737975

Digital Library

[28]

Jeff Huang. 2018. UFO: Predictive Concurrency Use-after-Free Detection. In Proceedings of the 40th International Conference on Software Engineering (ICSE ’18). Association for Computing Machinery, New York, NY, USA. 609–619. isbn:9781450356381 https://doi.org/10.1145/3180155.3180225

Digital Library

[29]

Jeff Huang, Patrick O’Neil Meredith, and Grigore Rosu. 2014. Maximal Sound Predictive Race Detection with Control Flow Abstraction. In Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’14). Association for Computing Machinery, New York, NY, USA. 337–348. isbn:9781450327848 https://doi.org/10.1145/2594291.2594315

Digital Library

[30]

Jeff Huang and Charles Zhang. 2012. LEAN: Simplifying Concurrency Bug Reproduction via Replay-Supported Execution Reduction. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA ’12). Association for Computing Machinery, New York, NY, USA. 451–466. isbn:9781450315616 https://doi.org/10.1145/2384616.2384649

Digital Library

[31]

Jeff Huang, Charles Zhang, and Julian Dolby. 2013. CLAP: recording local executions to reproduce concurrency failures. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’13, Seattle, WA, USA, June 16-19, 2013, Hans-Juergen Boehm and Cormac Flanagan (Eds.). ACM, 141–152. https://doi.org/10.1145/2491956.2462167

Digital Library

[32]

D. R. Jeong, K. Kim, B. Shivakumar, B. Lee, and I. Shin. 2019. Razzer: Finding Kernel Race Bugs through Fuzzing. In 2019 IEEE Symposium on Security and Privacy (SP). 754–768. https://doi.org/10.1109/SP.2019.00017

[33]

Vineet Kahlon, Nishant Sinha, Erik Kruus, and Yun Zhang. 2009. Static Data Race Detection for Concurrent Programs with Asynchronous Calls. In Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering (ESEC/FSE ’09). Association for Computing Machinery, New York, NY, USA. 13–22. isbn:9781605580012 https://doi.org/10.1145/1595696.1595701

Digital Library

[34]

Dileep Kini, Umang Mathur, and Mahesh Viswanathan. 2017. Dynamic race prediction in linear time. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, Barcelona, Spain, June 18-23, 2017, Albert Cohen and Martin T. Vechev (Eds.). ACM, 157–170. https://doi.org/10.1145/3062341.3062374

Digital Library

[35]

Jens Krinke. 2003. Context-Sensitive Slicing of Concurrent Programs. In Proceedings of the 9th European Software Engineering Conference Held Jointly with 11th ACM SIGSOFT International Symposium on Foundations of Software Engineering (ESEC/FSE-11). Association for Computing Machinery, New York, NY, USA. 178–187. isbn:1581137435 https://doi.org/10.1145/940071.940096

Digital Library

[36]

Markus Kusano and Chao Wang. 2016. Flow-Sensitive Composition of Thread-Modular Abstract Interpretation. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE 2016). Association for Computing Machinery, New York, NY, USA. 799–809. isbn:9781450342186 https://doi.org/10.1145/2950290.2950291

Digital Library

[37]

Leslie Lamport. 1979. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers C-28, 9 (1979), September, 690–691. https://www.microsoft.com/en-us/research/publication/make-multiprocessor-computer-correctly-executes-multiprocess-programs/

Digital Library

[38]

Ondrej Lhoták and Kwok-Chiang Andrew Chung. 2011. Points-to Analysis with Efficient Strong Updates. In Proceedings of the 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’11). Association for Computing Machinery, New York, NY, USA. 3–16. isbn:9781450304900 https://doi.org/10.1145/1926385.1926389

Digital Library

[39]

Lian Li, Cristina Cifuentes, and Nathan Keynes. 2011. Boosting the Performance of Flow-Sensitive Points-to Analysis Using Value Flow. In Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering (ESEC/FSE ’11). Association for Computing Machinery, New York, NY, USA. 343–353. isbn:9781450304436 https://doi.org/10.1145/2025113.2025160

Digital Library

[40]

Lian Li, Cristina Cifuentes, and Nathan Keynes. 2013. Precise and Scalable Context-Sensitive Pointer Analysis via Value Flow Graph. In Proceedings of the 2013 International Symposium on Memory Management (ISMM ’13). Association for Computing Machinery, New York, NY, USA. 85–96. isbn:9781450321006 https://doi.org/10.1145/2464157.2466483

Digital Library

[41]

Bozhen Liu and Jeff Huang. 2018. D4: fast concurrency debugging with parallel differential analysis. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018, Jeffrey S. Foster and Dan Grossman (Eds.). ACM, 359–373. https://doi.org/10.1145/3192366.3192390

Digital Library

[42]

Benjamin Livshits, Dimitrios Vardoulakis, Manu Sridharan, Yannis Smaragdakis, Ondřej Lhoták, José Amaral, Bor-Yuh Chang, Samuel Guyer, Uday Khedker, and Anders Møller. 2015. In Defense of Soundiness: A Manifesto. Commun. ACM, 58 (2015), 01, 44–46. https://doi.org/10.1145/2644805

Digital Library

[43]

Shan Lu, Soyeon Park, Eunsoo Seo, and Yuanyuan Zhou. 2008. Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics. In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS XIII). Association for Computing Machinery, New York, NY, USA. 329–339. isbn:9781595939586 https://doi.org/10.1145/1346281.1346323

Digital Library

[44]

Umang Mathur, Dileep Kini, and Mahesh Viswanathan. 2018. What happens-after the first race? enhancing the predictive power of happens-before based dynamic race detection. Proc. ACM Program. Lang., 2, OOPSLA (2018), 145:1–145:29. https://doi.org/10.1145/3276515

Digital Library

[45]

Ana Milanova, Atanas Rountev, and Barbara G. Ryder. 2004. Precise Call Graphs for C Programs with Function Pointers. Autom. Softw. Eng., 11, 1 (2004), 7–26. https://doi.org/10.1023/B:AUSE.0000008666.56394.a1

Digital Library

[46]

Mayur Naik, Alex Aiken, and John Whaley. 2006. Effective static race detection for Java. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, Ottawa, Ontario, Canada, June 11-14, 2006, Michael I. Schwartzbach and Thomas Ball (Eds.). ACM, 308–319. https://doi.org/10.1145/1133981.1134018

Digital Library

[47]

Mangala Gowri Nanda and S. Ramesh. 2000. Slicing Concurrent Programs. In Proceedings of the 2000 ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA ’00). Association for Computing Machinery, New York, NY, USA. 180–190. isbn:1581132662 https://doi.org/10.1145/347324.349121

Digital Library

[48]

Mangala Gowri Nanda and S. Ramesh. 2006. Interprocedural Slicing of Multithreaded Programs with Applications to Java. ACM Trans. Program. Lang. Syst., 28, 6 (2006), Nov., 1088–1144. issn:0164-0925 https://doi.org/10.1145/1186632.1186636

Digital Library

[49]

Satish Narayanasamy, Zhenghao Wang, Jordan Tigani, Andrew Edwards, and Brad Calder. 2007. Automatically Classifying Benign and Harmful Data Races Using Replay Analysis. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’07). Association for Computing Machinery, New York, NY, USA. 22–31. isbn:9781595936332 https://doi.org/10.1145/1250734.1250738

Digital Library

[50]

Andreas Pavlogiannis. 2020. Fast, sound, and effectively complete dynamic race prediction. Proc. ACM Program. Lang., 4, POPL (2020), 17:1–17:29. https://doi.org/10.1145/3371085

Digital Library

[51]

G. Ramalingam. 2000. Context-Sensitive Synchronization-Sensitive Analysis is Undecidable. ACM Trans. Program. Lang. Syst., 22, 2 (2000), March, 416–430. issn:0164-0925 https://doi.org/10.1145/349214.349241

Digital Library

[52]

Venkatesh Prasad Ranganath and John Hatcliff. 2004. Pruning Interference and Ready Dependence for Slicing Concurrent Java Programs. In Compiler Construction, Evelyn Duesterwald (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 39–56. isbn:978-3-540-24723-4

[53]

Martin C. Rinard. 2001. Analysis of Multithreaded Programs. In Proceedings of the 8th International Symposium on Static Analysis (SAS ’01). Springer-Verlag, Berlin, Heidelberg. 1–19. isbn:3540423141

Digital Library

[54]

Jake Roemer, Kaan Genç, and Michael D. Bond. 2020. SmartTrack: efficient predictive race detection. In Proceedings of the 41st ACM SIGPLAN International Conference on Programming Language Design and Implementation, PLDI 2020, London, UK, June 15-20, 2020, Alastair F. Donaldson and Emina Torlak (Eds.). ACM, 747–762. https://doi.org/10.1145/3385412.3385993

Digital Library

[55]

Radu Rugina and Martin Rinard. 1999. Pointer Analysis for Multithreaded Programs. In Proceedings of the ACM SIGPLAN 1999 Conference on Programming Language Design and Implementation (PLDI ’99). Association for Computing Machinery, New York, NY, USA. 77–90. isbn:1581130945 https://doi.org/10.1145/301618.301645

Digital Library

[56]

Alexandru Salcianu and Martin Rinard. 2001. Pointer and Escape Analysis for Multithreaded Programs. In Proceedings of the Eighth ACM SIGPLAN Symposium on Principles and Practices of Parallel Programming (PPoPP ’01). Association for Computing Machinery, New York, NY, USA. 12–23. isbn:1581133464 https://doi.org/10.1145/379539.379553

Digital Library

[57]

Qingkai Shi, Xiao Xiao, Rongxin Wu, Jinguo Zhou, Gang Fan, and Charles Zhang. 2018. Pinpoint: Fast and Precise Sparse Value Flow Analysis for Million Lines of Code. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). Association for Computing Machinery, New York, NY, USA. 693–706. isbn:9781450356985 https://doi.org/10.1145/3192366.3192418

Digital Library

[58]

Yao Shi, Soyeon Park, Zuoning Yin, Shan Lu, Yuanyuan Zhou, Wenguang Chen, and Weimin Zheng. 2010. Do I Use the Wrong Definition? DeFuse: Definition-Use Invariants for Detecting Concurrency and Sequential Bugs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (OOPSLA ’10). Association for Computing Machinery, New York, NY, USA. 160–174. isbn:9781450302036 https://doi.org/10.1145/1869459.1869474

Digital Library

[59]

Nishant Sinha and Chao Wang. 2010. Staged Concurrent Program Analysis. In Proceedings of the Eighteenth ACM SIGSOFT International Symposium on Foundations of Software Engineering (FSE ’10). Association for Computing Machinery, New York, NY, USA. 47–56. isbn:9781605587912 https://doi.org/10.1145/1882291.1882301

Digital Library

[60]

Yannis Smaragdakis, Jacob Evans, Caitlin Sadowski, Jaeheon Yi, and Cormac Flanagan. 2012. Sound predictive race detection in polynomial time. In Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, John Field and Michael Hicks (Eds.). ACM, 387–400. https://doi.org/10.1145/2103656.2103702

Digital Library

[61]

Bjarne Steensgaard. 1996. Points-to Analysis in Almost Linear Time. In Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’96). Association for Computing Machinery, New York, NY, USA. 32–41. isbn:0897917693 https://doi.org/10.1145/237721.237727

Digital Library

[62]

Yulei Sui, Peng Di, and Jingling Xue. 2016. Sparse flow-sensitive pointer analysis for multithreaded programs. In Proceedings of the 2016 International Symposium on Code Generation and Optimization, CGO 2016, Barcelona, Spain, March 12-18, 2016, Björn Franke, Youfeng Wu, and Fabrice Rastello (Eds.). ACM, 160–170. https://doi.org/10.1145/2854038.2854043

Digital Library

[63]

Yulei Sui, Ding Ye, and Jingling Xue. 2012. Static Memory Leak Detection Using Full-Sparse Value-Flow Analysis. In Proceedings of the 2012 International Symposium on Software Testing and Analysis (ISSTA 2012). Association for Computing Machinery, New York, NY, USA. 254–264. isbn:9781450314541 https://doi.org/10.1145/2338965.2336784

Digital Library

[64]

Jan Wen Voung, Ranjit Jhala, and Sorin Lerner. 2007. RELAY: Static Race Detection on Millions of Lines of Code. In Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering (ESEC-FSE ’07). Association for Computing Machinery, New York, NY, USA. 205–214. isbn:9781595938114 https://doi.org/10.1145/1287624.1287654

Digital Library

[65]

John Whaley and Martin Rinard. 1999. Compositional Pointer and Escape Analysis for Java Programs. In Proceedings of the 14th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA ’99). Association for Computing Machinery, New York, NY, USA. 187–206. isbn:1581132387 https://doi.org/10.1145/320384.320400

Digital Library

[66]

Jingyue Wu, Yang Tang, Gang Hu, Heming Cui, and Junfeng Yang. 2012. Sound and precise analysis of parallel programs through schedule specialization. In ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’12, Beijing, China - June 11 - 16, 2012, Jan Vitek, Haibo Lin, and Frank Tip (Eds.). ACM, 205–216. https://doi.org/10.1145/2254064.2254090

Digital Library

[67]

Yichen Xie and Alex Aiken. 2007. Saturn: A scalable framework for error detection using boolean satisfiability. ACM Transactions on Programming Languages and Systems (TOPLAS), 29, 3 (2007), 16–es.

Digital Library

[68]

M. Xu, S. Kashyap, H. Zhao, and T. Kim. 2020. Krace: Data Race Fuzzing for Kernel File Systems. In 2020 IEEE Symposium on Security and Privacy (SP). 1643–1660. https://doi.org/10.1109/SP40000.2020.00078

[69]

Junfeng Yang, Ang Cui, Sal Stolfo, and Simha Sethumadhavan. 2012. Concurrency Attacks. In Proceedings of the 4th USENIX Conference on Hot Topics in Parallelism (HotPar’12). USENIX Association, USA. 15.

Digital Library

[70]

Hongtao Yu, Jingling Xue, Wei Huo, Xiaobing Feng, and Zhaoqing Zhang. 2010. Level by Level: Making Flow- and Context-Sensitive Pointer Analysis Scalable for Millions of Lines of Code. In Proceedings of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’10). Association for Computing Machinery, New York, NY, USA. 218–229. isbn:9781605586359 https://doi.org/10.1145/1772954.1772985

Digital Library

[71]

S. Zhao, R. Gu, H. Qiu, T. O. Li, Y. Wang, H. Cui, and J. Yang. 2018. OWL: Understanding and Detecting Concurrency Attacks. In 2018 48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 219–230.

Cited By

Zhao JFu YWu YDong JHong R(2025)Thread-sensitive fuzzing for concurrency bug detectionComputers & Security10.1016/j.cose.2024.104171148(104171)Online publication date: Jan-2025
https://doi.org/10.1016/j.cose.2024.104171
Zhan QHu XXia XLi SFilkov VRay BZhou M(2024)REACT: IR-Level Patch Presence Test for BinaryProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695012(381-392)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695012
Xu RPeng HYang KMao X(2024)Exploring Scalability of Value-Flow Graph ConstructionProceedings of the 2024 4th International Conference on Artificial Intelligence, Automation and High Performance Computing10.1145/3690931.3690951(112-117)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3690931.3690951
Show More Cited By

Index Terms

Canary: practical static detection of inter-thread value-flow bugs
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation

Recommendations

Effective Static Analysis to Find Concurrency Bugs in Java
SCAM '10: Proceedings of the 2010 10th IEEE Working Conference on Source Code Analysis and Manipulation

Multithreading and concurrency are core features of the Java language. However, writing a correct concurrent program is notoriously difficult and error prone. Therefore, developing effective techniques to find concurrency bugs is very important. ...
Static lock capabilities for deadlock freedom
TLDI '12: Proceedings of the 8th ACM SIGPLAN workshop on Types in language design and implementation

We present a technique --- lock capabilities --- for statically verifying that multithreaded programs with locks will not deadlock. Most previous work on deadlock prevention requires a strict total order on all locks held simultaneously by a thread, but ...
Compositional deadlock detection for rendezvous communication
EMSOFT '09: Proceedings of the seventh ACM international conference on Embedded software

Concurrent programming languages are growing in importance with the advent of multi-core systems. However, concurrent programs suffer from problems, such as data races and deadlock, absent from sequential programs. Unfortunately, traditional race and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2021: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 2021

1341 pages

ISBN:9781450383912

DOI:10.1145/3453483

General Chair:
Stephen N. Freund
Williams College, USA
,
Program Chair:
Eran Yahav
Technion, Israel

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

RGC16206517, ITS/440/18FP

Conference

PLDI '21

Sponsor:

SIGPLAN

PLDI '21: 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation

June 20 - 25, 2021

Virtual, Canada

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
521
Total Downloads

Downloads (Last 12 months)115
Downloads (Last 6 weeks)12

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao JFu YWu YDong JHong R(2025)Thread-sensitive fuzzing for concurrency bug detectionComputers & Security10.1016/j.cose.2024.104171148(104171)Online publication date: Jan-2025
https://doi.org/10.1016/j.cose.2024.104171
Zhan QHu XXia XLi SFilkov VRay BZhou M(2024)REACT: IR-Level Patch Presence Test for BinaryProceedings of the 39th IEEE/ACM International Conference on Automated Software Engineering10.1145/3691620.3695012(381-392)Online publication date: 27-Oct-2024
https://dl.acm.org/doi/10.1145/3691620.3695012
Xu RPeng HYang KMao X(2024)Exploring Scalability of Value-Flow Graph ConstructionProceedings of the 2024 4th International Conference on Artificial Intelligence, Automation and High Performance Computing10.1145/3690931.3690951(112-117)Online publication date: 19-Jul-2024
https://dl.acm.org/doi/10.1145/3690931.3690951
Zou CHe DSui YXue J(2024)TIPS: Tracking Integer-Pointer Value Flows for C++ Member Function PointersProceedings of the ACM on Software Engineering10.1145/36607791:FSE(1609-1631)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660779
Wen CCai YZhang BSu JXu ZLiu DQin SMing ZCong T(2024)Automatically Inspecting Thousands of Static Bug Warnings with Large Language Model: How Far Are We?ACM Transactions on Knowledge Discovery from Data10.1145/365371818:7(1-34)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3653718
Cai YYao PYe CZhang CCalandrino JTroncoso C(2023)Place your locks wellProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620446(3727-3744)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620446
Cai YZhang C(2023)A Cocktail Approach to Practical Call Graph ConstructionProceedings of the ACM on Programming Languages10.1145/36228337:OOPSLA2(1001-1033)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622833
Ma WYang STan TMa XXu CLi Y(2023)Context Sensitivity without Contexts: A Cut-Shortcut Approach to Fast and Precise Pointer AnalysisProceedings of the ACM on Programming Languages10.1145/35912427:PLDI(539-564)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591242
Düsing JHermann BBissyandé TKlein JBird CSarro F(2023)Persisting and Reusing Results of Static Program Analyses on a Large ScaleProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00080(888-900)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00080
Llorente-Vazquez OSantos-Grueiro IBringas P(2023)When Memory Corruption Met Concurrency: Vulnerabilities in Concurrent ProgramsIEEE Access10.1109/ACCESS.2023.327283311(44725-44740)Online publication date: 2023
https://doi.org/10.1109/ACCESS.2023.3272833
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents