research-article

Public Access

D4: fast concurrency debugging with parallel differential analysis

Authors:

Jeff HuangAuthors Info & Claims

PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 359 - 373

https://doi.org/10.1145/3192366.3192390

Published: 11 June 2018 Publication History

Abstract

We present D4, a fast concurrency analysis framework that detects concurrency bugs (e.g., data races and deadlocks) interactively in the programming phase. As developers add, modify, and remove statements, the code changes are sent to D4 to detect concurrency bugs in real time, which in turn provides immediate feedback to the developer of the new bugs. The cornerstone of D4 includes a novel system design and two novel parallel differential algorithms that embrace both change and parallelization for fundamental static analyses of concurrent programs. Both algorithms react to program changes by memoizing the analysis results and only recomputing the impact of a change in parallel. Our evaluation on an extensive collection of large real-world applications shows that D4 efficiently pinpoints concurrency bugs within 100ms on average after a code change, several orders of magnitude faster than both the exhaustive analysis and the state-of-the-art incremental techniques.

Supplementary Material

WEBM File (p359-liu.webm)

Download
82.22 MB

References

[1]

Akka Cluster Usage. http://http://doc.akka.io/docs/akka/current/java/ cluster-usage.html .

[2]

Titan Graph Partitioning. http://s3.thinkaurelius.com/docs/titan/0.5. 0/graph-partitioning.html .

[3]

T. J. Watson Libraries for Analysis (WALA). http://wala.sourceforge. net/ .

[4]

RacerD. http://fbinfer.com/docs/racerd.html .

[5]

D4 website. https://github.com/parasol-aser/D4 .

[6]

The Language Server protocol. https://langserver.org/ .

[7]

Zhan, Sheng and Huang, Jeff ECHO: Instantaneous In Situ Race Detection in the IDE. In Proceedings of the International Symposium on the Foundations of Software Engineering (2016), pp. 775–786.

Digital Library

[8]

Blackburn, S. M. and Garner, R. and Hoffman, C. and Khan, A. M. and McKinley, K. S. and Bentzur, R. and Diwan, A. and Feinberg, D. and Frampton, D. and Guyer, S. Z. and Hirzel, M. and Hosking, A. and Jump, M. and Lee, H. and Moss, J. E. B. and Phansalkar, A. and Stefanović, D. and VanDrunen, T. and von Dincklage, D. and Wiedermann, B. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In Proceedings of the 21st annual ACM SIG-PLAN conference on Object-Oriented Programing, Systems, Languages, and Applications (2006), pp. 169–190.

Digital Library

[9]

Acar, U. A. Self-adjusting Computation. PhD thesis, 2005.

Digital Library

[10]

Acar, U. A., Blelloch, G. E., Blume, M., and Tangwongsan, K. An experimental analysis of self-adjusting computation. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation (2006), pp. 96–107.

Digital Library

[11]

Arzt, S., and Bodden, E. Reviser: Efficiently updating ide-/ifds-based data-flow analyses in response to incremental program changes. In Proceedings of the 36th International Conference on Software Engineering, ICSE 2014, ACM, pp. 288–298.

Digital Library

[12]

Bhatotia, P., Fonseca, P., Acar, U. A., Brandenburg, B. B., and Rodrigues, R. ithreads: A threading library for parallel incremental computation. In Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (2015), pp. 645–659.

Digital Library

[13]

Burckhardt, S., Kothari, P., Musuvathi, M., and Nagarakatte, S. A randomized scheduler with probabilistic guarantees of finding bugs. In Proceedings of the Fifteenth Edition of ASPLOS on Architectural Support for Programming Languages and Operating Systems, ASPLOS XV, ACM, pp. 167–178.

Digital Library

[14]

Chen, Y., Dunfield, J., and Acar, U. A. Type-directed automatic incrementalization. In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation (2012), pp. 299–310.

Digital Library

[15]

Edvinsson, M., Lundberg, J., and Löwe, W. Parallel points-to analysis for multi-core machines. In Proceedings of the 6th International Conference on High Performance and Embedded Architectures and Compilers, HiPEAC ’11, ACM, pp. 45–54.

Digital Library

[16]

Engler, D., and Ashcraft, K. Racerx: Effective, static detection of race conditions and deadlocks. In Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, SOSP ’03, ACM, pp. 237–252.

Digital Library

[17]

Flanagan, C., and Freund, S. N. Fasttrack: Efficient and precise dynamic race detection. In Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’09, ACM, pp. 121–133.

Digital Library

[18]

Fonseca, P., Li, C., and Rodrigues, R. Finding complex concurrency bugs in large multi-threaded applications. In Proceedings of the Sixth Conference on Computer Systems, EuroSys ’11, ACM, pp. 215–228.

Digital Library

[19]

Grove, D., and Chambers, C. A framework for call graph construction algorithms. ACM Trans. Program. Lang. Syst. 23, 6 (2001), 685–746.

Digital Library

[20]

Sridharan, M., Chandra, S., Dolby, J., and Fink, S. J., and Yahav, E. Alias Analysis for Object-oriented Programs. Aliasing in ObjectOriented Programming (2013), pp. 196–232.

Digital Library

[21]

Hardekopf, B., and Lin, C. The ant and the grasshopper: Fast and accurate pointer analysis for millions of lines of code. In Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation (2007), pp. 290–299.

Digital Library

[22]

Jin, G., Zhang, W., Deng, D., Liblit, B., and Lu, S. Automated concurrency-bug fixing. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI’12, USENIX Association, pp. 221–236.

Digital Library

[23]

Kastrinis, G., and Smaragdakis, Y. Efficient and effective handling of exceptions in java points-to analysis. In Proceedings of the 22Nd International Conference on Compiler Construction, CC’13, SpringerVerlag, pp. 41–60.

Digital Library

[24]

Mendez-Lojo, M., Burtscher, M., and Pingali, K. A gpu implementation of inclusion-based points-to analysis. In Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’12, ACM, pp. 107–116.

Digital Library

[25]

Méndez-Lojo, M., Mathew, A., and Pingali, K. Parallel inclusionbased points-to analysis. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’10, ACM, pp. 428–443.

Digital Library

[26]

Musuvathi, M., Qadeer, S., Ball, T., Basler, G., Nainar, P. A., and Neamtiu, I. Finding and reproducing heisenbugs in concurrent programs. In Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, OSDI’08, USENIX Association, pp. 267–280.

Digital Library

[27]

Nagaraj, V., and Govindarajan, R. Parallel flow-sensitive pointer analysis by graph-rewriting. In Proceedings of the 22Nd International Conference on Parallel Architectures and Compilation Techniques, PACT ’13, IEEE Press, pp. 19–28.

Digital Library

[28]

Naik, M., Aiken, A., and Whaley, J. Effective static race detection for java. In Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’06, ACM, pp. 308–319.

Digital Library

[29]

Putta, S., and Nasre, R. Parallel replication-based points-to analysis. In Proceedings of the 21st International Conference on Compiler Construction, CC’12, Springer-Verlag, pp. 61–80.

Digital Library

[30]

Saha, D., and Ramakrishnan, C. R. Incremental and demand-driven points-to analysis using logic programming. In Proceedings of the 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, PPDP ’05, ACM, pp. 117–128.

Digital Library

[31]

Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., and Anderson, T. Eraser: A dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15, 4 (Nov. 1997), 391–411.

Digital Library

[32]

Sen, K. Race directed random testing of concurrent programs. In Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’08, ACM, pp. 11–21.

Digital Library

[33]

Serebryany, K., and Iskhodzhanov, T. Threadsanitizer: Data race detection in practice. In Proceedings of the Workshop on Binary Instrumentation and Applications, WBIA ’09, ACM, pp. 62–71.

Digital Library

[34]

Shang, L., Lu, Y., and Xue, J. Fast and precise points-to analysis with incremental cfl-reachability summarisation: Preliminary experience. In Proceedings of the 27th IEEE/ACM International Conference on Automated Software Engineering, ASE 2012, ACM, pp. 270–273.

Digital Library

[35]

Sridharan, M., Gopan, D., Shan, L., and Bodík, R. Demand-driven points-to analysis for java. In Proceedings of the 20th Annual ACM SIG-PLAN Conference on Object-oriented Programming, Systems, Languages, and Applications, OOPSLA ’05, ACM, pp. 59–76.

Digital Library

[36]

Su, Y., Ye, D., and Xue, J. Parallel pointer analysis with cfl-reachability. In Proceedings of the 2014 Brazilian Conference on Intelligent Systems, BRACIS ’14, IEEE Computer Society, pp. 451–460.

Digital Library

[37]

Szabó, T., Erdweg, S., and Voelter, M. Inca: A dsl for the definition of incremental program analyses. In Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering, ASE 2016, ACM, pp. 320–331.

Digital Library

[38]

Terragni, V., Cheung, S.-C., and Zhang, C. Recontest: Effective regression testing of concurrent programs. In Proceedings of the 37th International Conference on Software Engineering - Volume 1 (2015), pp. 246–256.

Digital Library

[39]

Voung, J. W., Jhala, R., and Lerner, S. 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, ACM, pp. 205–214.

Digital Library

[40]

Yu, J., Narayanasamy, S., Pereira, C., and Pokam, G. Maple: A coverage-driven testing tool for multithreaded programs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, OOPSLA ’12, ACM, pp. 485–502.

Digital Library

[41]

Zhang, W., Lim, J., Olichandran, R., Scherpelz, J., Jin, G., Lu, S., and Reps, T. Conseq: Detecting concurrency bugs through sequential errors. In Proceedings of the Sixteenth International Conference on Architectural Support for Programming Languages and Operating Systems, ASPLOS XVI, ACM, pp. 251–264.

Digital Library

[42]

Zhou, P., Teodorescu, R., and Zhou, Y. Hard: Hardware-assisted lockset-based race detection. In Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, HPCA ’07, IEEE Computer Society, pp. 121–132.

Digital Library

[43]

Do, Lisa Nguyen Quang and Ali, Karim and Livshits, Benjamin and Bodden, Eric and Smith, Justin and Murphy-Hill, Emerson Just-in-time Static Analysis. In Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, ISSTA ’17, ACM, pp. 307–317.

Digital Library

[44]

Camil Demetrescu Fully Dynamic Algorithms for Path Problems on Directed Graphs. PhD thesis, 2001.

[45]

Bender, Michael A. and Fineman, Jeremy T. and Gilbert, Seth and Tarjan, Robert E. A New Approach to Incremental Cycle Detection and Related Problems. In ACM Trans. Algorithms (2016), pp. 14:1–14:22.

Digital Library

[46]

Italiano, Giuseppe F. and Nussbaum, Yahav and Sankowski, Piotr and Wulff-Nilsen, Christian Improved Algorithms for Min Cut and Max Flow in Undirected Planar Graphs. In Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing (2011), pp. 313–322.

Digital Library

[47]

Yu, T., Srisa-an, W., and Rothermel, G. SimRT: An automated framework to support regression testing for data races. In Proceedings of the 36th International Conference on Software Engineering (2014), pp. 48–59.

Digital Library

Cited By

Wimmer CStancu CKozak DWürthinger T(2024)Scaling Type-Based Points-to Analysis with SaturationProceedings of the ACM on Programming Languages10.1145/36564178:PLDI(990-1013)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656417
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
Brahmakshatriya AAmarasinghe SDubach CBruening DHardekopf B(2023)D2X: An eXtensible conteXtual Debugger for Modern DSLsProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580014(162-172)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580014
Show More Cited By

Index Terms

D4: fast concurrency debugging with parallel differential analysis
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. Development frameworks and environments
      1. Integrated and visual development environments

Recommendations

D4: fast concurrency debugging with parallel differential analysis
PLDI '18

We present D4, a fast concurrency analysis framework that detects concurrency bugs (e.g., data races and deadlocks) interactively in the programming phase. As developers add, modify, and remove statements, the code changes are sent to D4 to detect ...
Sound and efficient concurrency bug prediction
ESEC/FSE 2021: Proceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering

Concurrency bugs are extremely difficult to detect. Recently, several dynamic techniques achieve sound analysis. M2 is even complete for two threads. It is designed to decide whether two events can occur consecutively. However, real-world concurrency ...
Scalable concurrency debugging with distributed graph processing
CGO '18: Proceedings of the 2018 International Symposium on Code Generation and Optimization

Existing constraint-solving-based technique enables an efficient and high-coverage concurrency debugging. Yet, there remains a significant gap between the state of the art and the state of the programming practices for scaling to handle long-running ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI 2018: Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2018

825 pages

ISBN:9781450356985

DOI:10.1145/3192366

General Chair:
Jeffrey S. Foster
University of Maryland at College Park, USA
,
Program Chair:
Dan Grossman
University of Washington, USA

ACM SIGPLAN Notices Volume 53, Issue 4
PLDI '18
April 2018
834 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/3296979
Editor:
Matthew Fluet
Rodchester Institude of Technology
Issue’s Table of Contents

Copyright © 2018 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: 11 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

NSF

Conference

PLDI '18

Sponsor:

SIGPLAN

PLDI '18: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 18 - 22, 2018

PA, Philadelphia, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
1,048
Total Downloads

Downloads (Last 12 months)218
Downloads (Last 6 weeks)27

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wimmer CStancu CKozak DWürthinger T(2024)Scaling Type-Based Points-to Analysis with SaturationProceedings of the ACM on Programming Languages10.1145/36564178:PLDI(990-1013)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656417
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
Brahmakshatriya AAmarasinghe SDubach CBruening DHardekopf B(2023)D2X: An eXtensible conteXtual Debugger for Modern DSLsProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580014(162-172)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580014
Cai YYe CShi QZhang CRoychoudhury ACadar CKim M(2022)Peahen: fast and precise static deadlock detection via context reductionProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3549110(784-796)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3549110
Liu BHuang J(2022)SHARP: fast incremental context-sensitive pointer analysis for JavaProceedings of the ACM on Programming Languages10.1145/35273326:OOPSLA1(1-28)Online publication date: 29-Apr-2022
https://dl.acm.org/doi/10.1145/3527332
Liu PLi YSwain BHuang JDwyer MDamian DZeller A(2022)PUSProceedings of the 44th International Conference on Software Engineering10.1145/3510003.3510075(1781-1792)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510003.3510075
Beillahi SBouajjani AEnea CLahiri S(2022)Automated Synthesis of AsynchronizationsStatic Analysis10.1007/978-3-031-22308-2_7(135-159)Online publication date: 5-Dec-2022
https://dl.acm.org/doi/10.1007/978-3-031-22308-2_7
Cai YYao PZhang CFreund SYahav E(2021)Canary: practical static detection of inter-thread value-flow bugsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454099(1126-1140)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454099
Liu BLiu PLi YTsai CDa Silva DHuang JFreund SYahav E(2021)When threads meet events: efficient and precise static race detection with originsProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454073(725-739)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454073
Wang ZWang HLiu SSun JWang HChen J(2020)IFIX: Fixing Concurrency Bugs While They Are Introduced2020 25th International Conference on Engineering of Complex Computer Systems (ICECCS)10.1109/ICECCS51672.2020.00025(155-164)Online publication date: Oct-2020
https://doi.org/10.1109/ICECCS51672.2020.00025
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents