Understanding & Managing the Dynamic Behavior of
Parallel Programs

Description

The advent of multicore processors has introduced new opportunities for achieving increased reliability. However, powerful dynamic execution monitoring techniques that impose low runtime overhead are required to realize these opportunities. This project is aimed at developing efficient monitoring techniques and utilizing them in building powerful software tools for interactive debugging as well as runtime fault detection and recovery.

• Efficient Monitoring - runtime monitoring of parallel and multithreaded programs poses significant challenges. For a wide variety of tasks such as dynamic slicing and information flow tracking, monitoring is carried by associating meta-data with program data. It is essential to maintain a consistent view of the data and meta-data by updating program data and the meta-data atomically. Our goal is to maintain this consistent view at a low overhead cost for which we are developing a combination of dynamic binary translation techniques [SP&E'11b,SIGOPS'09], programmable architectural mechanisms [ISCA'09,VEE'09], and additional software techniques [ISSTA'07,FSE'06]. These monitoring capability is being built upon a sequentially consistent multicore system [SC'14,ICS'13,ASPLOS'12,PACT'10]. Our recent work is employing efficient monitoring technqiues to capture execution profiles of parallel and distributed applications to enable performance debugging [HPDC'16,RV'17,PACMPL'19,FMSD'19] and dynamic analysis for autotuning [CGO'19].

• Interactive Debugging and Deterministic Replay - we are developing an interactive debugging interface that combines several capabilities that together reduce debugging effort and increase debugging speed. The capabilities that yield these benefits include: sophisticated state alteration commands for dynamically switching the directions of conditional branches and suppressing the execution of statements; sophisticated state inspection commands including those for computing, browsing, and pruning dynamic slices; state rollback and checkpointing commands to allow reexecuting the program from any earlier checkpoints. Our prototype is built on top of GDB; thus all commands that are supported by GDB are also available to the programmer [SCAM'13]. We have also developed an enhanced delta debugging technique based upon relevant inputs dynamic analysis [ISSRE'13]. To support debugging of parallel programs we have integrated some of the above techniques with deterministic replay in DrDebug [CGO'14] and LightPlay [LCPC'14] systems. We have developed techniques for debugging when faults lead to violation of data structure constraints [ISSRE'16,CC'16,SANER'15]. Our recent work has developed a dynamic slicing and other analysis tools to help in debugging of Android applications [ICSE'19,INFOCOM'19,ASIACCS'18].

• Fault Detection, Avoidance, and Recovery - runtime monitoring is being employed for developing a powerful techniques for runtime detection of faults (e.g., memory bugs, data races, and atomicity violations [ISMM'13,CGO'13,SPE'11a,ISSTA'08,ICSM'08]) and security holes through dynamic information flow tracking [INTERACT'08]. We are also considering errors involving violations of integrity of data structures [CC'16] and instability involving floating-point data [OOPSLA'15]. In scenarios where both sequential and parallel versions of a program are available, we detect faults by comparing the executions of the two program versions. We have also developed online fault detection, avoidance and recovery techniques for clusters [SC'17,IPDPS'18,HIPS'18,CC'19], multicores [COMPSAC'08,ISMM'09], and mobile systems [PAM'17,EASE'15,ISSRE'15]. Our recent work is aimed at developing concolic testing techniques for parallel programs that utilize dynamic concurrent data structures [ICS'21].

Publications

1. DSGEN: Concolic Testing GPU Implementations of Concurrent Dynamic Data Structures
   X. Sun and R. Gupta. ACM International Conference on Supercomputing (ICS), pages 75-87, June 2021.
   

2. Annotation Guided Collection of Context-Sensitive Parallel Execution Profiles
   Z. Benavides, K. Vora, R. Gupta, and X. Zhang. Formal Methods in System Design, An International Journal (FMSD), Springer, Volume 54, Issue 3, pages 388-415, November 2019.
   Among best papers from RV 2017 with extended versions invited for publication in FMSD.
   download: https://www.cs.ucr.edu/~gupta/fmsd-artifacts.zip

3. DProf: Distributed Profiler with Strong Guarantees
   Z. Benavides, K. Vora, and R. Gupta. Proceedings of the ACM on Programming Languages (PACMPL), Volume 3, Issue OOPSLA, Article 156, 24 pages, Athens, Greece, October 2019.

4. When The Attacker Knows A Lot: The GAGA Graph Anonymizer
   A. Alavi, R. Gupta, and Z. Qian. 22nd Information Security Conference (ISC), LNCS 11723, Springer, pages 211-230, New York, NY, September 2019.

5. Dynamic Slicing for Android
   T. Azim, A. Alavi, I. Neamtiu, and R. Gupta. 41st ACM/IEEE International Conference on Software Engineering (ICSE), pages 1154-1164, Montreal, Canada, May 2019. download: https://github.com/archer29m/AndroidSlicer

6. Figment: Fine-grained Permission management for Mobile Apps
   I. Gasparis, Z. Qian, C. Song, S.V. Krishnamurthy, R. Gupta, and P. Yu. IEEE International Conference on Computer Communications (INFOCOM), pages 1405-1413, Paris, France, April-May, 2019.

7. White-Box Program Tuning
   W-C. Lee, Y. Liu, P. Liu, S. Ma, H.J. Choi, X. Zhang, and R. Gupta. IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 122-135, Washington DC, February 2019.

8. Efficient Concolic Testing for MPI Applications
   H. Li, Z. Chen, and R. Gupta. International Conference on Compiler Construction (CC), pages 193-204, Washington DC, February 2019.

9. Droid M+: Developer Support for Imbibing Android’s New Permission Model
   I. Gasparis, A. Aqil, Z. Qian, C. Song, S.V. Krishnamurthy, R. Gupta, and E. Colbert. ACM Asia Conference on Computer and Communications Security (ASIACCS), pages 765-776, Songdo, Incheon, Korea, June 2018.

10. COMPI: Concolic Testing for MPI Applications
    H. Li, S. Li, Z. Benavides, Z. Chen, and R. Gupta. 32nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 865-874, Vancouver, British Columbia, May 2018.

11. Non-Intrusively Avoiding Scaling Problems in and out of MPI Collectives
    H. Li, Z. Chen, R. Gupta, and M. Xie. International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS), pages 415-424, in IEEE IPDPSW Proceedings, Vancouver, British Columbia, May 2018.

12. ParaStack: Efficient Hang Detection for MPI Programs at Large Scale
    H. Li, Z. Chen, and R. Gupta. ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC), Article No. 63, 12 pages, Denver, Colorado, November 2017.

13. Annotation Guided Collection of Context-Sensitive Parallel Execution Profiles
    Z. Benavides, R. Gupta, and X. Zhang. The 17th International Conference on Runtime Verification (RV), LNCS 10548, Springer, pages 103-120, Seattle, Washington, September 2017.

14. Where is the Weakest Link? A Study on Security Discrepancies between Android Apps and Their Website Counterparts
    A. Alavi, A. Quach, H. Zhang, B. Marsh, F. Ul Haq, Z. Qian, L. Lu, and R. Gupta. The Passive and Active Measurement Conference (PAM), LNCS 10176, pages 100-112, Springer, Sydney, Australia, March 2017.

15. Parallel Execution Profiles
    Z. Benavides, R. Gupta, and X. Zhang. 25th ACM International Symposium on High-Performance Parallel and Distributed Computing (HPDC), pages 215-218, Kyoto, Japan, May-June 2016.

16. Proving Concurrent Data Structures Linearizable
    V. Singh, I. Neamtiu, and R. Gupta. The 27th IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 230-240, Ottawa, Canada, October 2016.

17. Automatic Fault Location for Data Structures
    V. Singh, R. Gupta, and I. Neamtiu. 25th International Conference on Compiler Construction (CC), pages 99-109, Barcelona, Spain, March 2016.

18. Experience Report: How Do Bug Characteristics Differ Across Severity Classes: A Multi-platform Study
    B. Zhou, I. Neamtiu, and R. Gupta. The 26th IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 507-517, Gaithersburg, Maryland, November 2015.

19. RAIVE: Runtime Assessment of Floating-Point Instability by Vectorization
    W-C. Lee, T. Bao, Y. Zheng, X. Zhang, K. Vora, and R. Gupta. ACM SIGPLAN International Conference on Object Oriented Programming Systems, Languages and Applications (OOPSLA), pages 623-638, Pittsburgh, PA, October 2015.

20. A Cross-platform Analysis of Bugs and Bug-fixing in Open Source Projects: Desktop vs. Android vs. iOS
    B. Zhou, I. Neamtiu, and R. Gupta. 19th International Conference on Evaluation and Assessment in Software Engineering (EASE), Article 7, 10 pages, Nanjing, China, April 2015.

21. Predicting Concurrency Bugs: How Many, What Kind and Where Are They?
    B. Zhou, I. Neamtiu, and R. Gupta. 19th International Conference on Evaluation and Assessment in Software Engineering (EASE), Article 6, 10 pages, Nanjing, China, April 2015.

22. MG++: Memory Graphs for Analyzing Dynamic Data Structures
    V. Singh, R. Gupta, and I. Neamtiu. 22nd IEEE International Conference on Software Analysis, Evolution, and Reengineering (SANER), pages 291-300, Montreal, Canada, March 2015.

23. Fence Scoping
    C. Lin, V. Nagarajan, and R. Gupta. ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 105-116, New Orleans, Louisiana, November 2014.

24. LightPlay: Efficient Replay with GPUs
    M. Feng, F. Khorasani, R. Gupta, and L.N. Bhuyan. 27th International Workshop on Languages and Compilers for Parallel Computing (LCPC), LNCS 8967, Chapter 22, pages 332-347, Hillsboro, Oregon, September 2014.

25. DrDebug: Deterministic Replay based Cyclic Debugging with Dynamic Slicing
    Y. Wang, H. Patil, C. Pereira, G. Lueck, R. Gupta, and I. Neamtiu. IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 98-108, Orlando, Florida, March 2014. DrDebug download: Replay & Slicing

26. Relevant Inputs Analysis and its Applications
    Y. Wang, R. Gupta, and I. Neamtiu. The 24th IEEE International Symposium on Software Reliability Engineering (ISSRE), pages 268-277, Pasadena, CA, November 2013.

27. A State-Alteration and Inspection-based Interactive Debugger
    Y. Wang, M. Feng, R. Gupta, and I. Neamtiu. 13th International Working Conference on Source Code Analysis and Manipulation (SCAM), pages 84-93, Eindhoven, Netherlands, September 2013.

28. Generating Sound and Effective Memory Debuggers
    Y. Wang, I. Neamtiu, and R. Gupta. International Symposium on Memory Management (ISMM), pages 51-62, Seattle, Washington, June 2013.

29. Address-aware Fences
    C. Lin, V. Nagarajan, and R. Gupta. 27th International Conference on Supercomputing (ICS), pages 313-324, Eugene, Oregon, June 2013.

30. Lightweight Fault Detection in Parallelized Programs
    L. Tan, M. Feng, and R. Gupta. IEEE/ACM International Symposium on Code Generation and Optimization (CGO), pages 1-11, Shenzhen, China, February 2013.

31. A System for Debugging via Online Tracing and Dynamic Slicing
    V. Nagarajan, D. Jeffrey, and R. Gupta. Software - Practice & Experience (SP&E), Vol. 42, No. 8, pages 995-1014, August 2012.

32. Efficient Sequential Consistency via Conflict Ordering
    C. Lin, V. Nagarajan, R. Gupta, and B. Rajaram. ACM 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), London, UK, March 2012.

33. Efficient Sequential Consistency Using Conditional Fences
    C. Lin, V. Nagarajan, and R. Gupta. International Journal of Parallel Programming (IJPP), Vol. 40, No. 1, pages 84-117, Feb. 2012. Special issue of best papers from PACT 2010.

34. Isolating Bugs in Multithreaded Programs Using Execution Suppression
    D. Jeffrey, Y. Wang, C. Tian, and R. Gupta. Software - Practice & Experience (SP&E), Vol. 41, No. 11, pages 1259-1288, October 2011.

35. Efficient Sequential Consistency Using Conditional Fences
    C. Lin, V. Nagarajan, and R. Gupta. 19th International Conference on Parallel Architectures and Compilation Techniques (PACT), pages 295-306, Vienna, Austria, September 2010.

36. Automated Dynamic Detection of Busy-wait Synchronizations
    C. Tian, V. Nagarajan, R. Gupta, and S. Tallam. Software - Practice & Experience (SP&E), Vol. 39, No. 11, pages 947-972, 2009.

37. Self-Recovery in Server Programs
    V. Nagarajan, D. Jeffrey, and R. Gupta. International Symposium on Memory Management (ISMM), pages 49-58, Dublin, Ireland, June 2009.

38. ECMon: Exposing Cache Events for Monitoring
    V. Nagarajan and R. Gupta. ACM/IEEE 36th International Symposium on Computer Architecture (ISCA), pages 349-360, Austin, Texas, June 2009.

39. Runtime Monitoring on Multicores via OASES
    V. Nagarajan and R. Gupta. ACM SIGOPS Operating Systems Review, (SIGOPS), special issue on the interaction among the OS, Compilers, and Multicore Processors, pages 15-24, Vol. 43, No. 2, April 2009 (Invited Paper).

40. Architectural Support for Shadow Memory in Multiprocessors
    V. Nagarajan and R. Gupta. ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments (VEE), pages 1-10, Washington DC, March 2009.

41. Dynamic Slicing of Multithreaded Programs for Race Detection
    S. Tallam, C. Tian, and R. Gupta. International Conference on Software Maintenance (ICSM), pages 97-106, Beijing, China, September 2008.

42. Avoiding Program Failures Through Safe Execution Perturbations
    S. Tallam, C. Tian, R. Gupta, and X. Zhang. IEEE Computer Software and Applications Conference (COMPSAC), pages 152-159, Turku, Finland, August 2008.

43. Dynamic Recognition of Synchronization Operations for Improved Data Race Detection
    C. Tian, V. Nagarajan, R. Gupta, and S. Tallam. International Symposium on Software Testing and Analysis (ISSTA), pages 143-154, Seattle, July 2008.

44. Support for Symmetric Shadow Memory in Multiprocessors
    V. Nagarajan and R. Gupta. Workshop on Parallel and Distributed Systems: Testing, Analysis, and Debugging (PADTAD), 9 pages, Seattle, July 2008.

45. Scalable Dynamic Information Flow Tracking and its Applications
    R. Gupta, N. Gupta, X. Zhang, D. Jeffrey, V. Nagarajan, S. Tallam, and C. Tian. NSF Next Generation Software Workshop (NSFNGS), colocated with IPDPS, pages 1-5, Florida, April 2008.

46. Dynamic Information Flow Tracking on Multicores
    V. Nagarajan, H-S. Kim, Y. Wu, and R. Gupta. Workshop on Interaction between Compilers and Computer Architectures (INTERACT), Co-located with HPCA, Salt Lake City, Feb. 2008.

47. Synchronization Aware Conflict Resolution for Runtime Monitoring Using Transactional Memory
    C. Tian, V. Nagarajan, and R. Gupta. Workshop on Software Tools for Multicore Systems (STMCS), colocated with CGO, pages 1-6, Boston, April 2008.

48. Enabling Tracing of Long-Running Multithreaded Programs via Dynamic Execution Reduction
    S. Tallam, C. Tian, X. Zhang, and R. Gupta. International Symposium on Software Testing and Analysis (ISSTA), pages 207-218, London, July 2007.

49. Dynamic Slicing Long Running Programs through Execution Fast Forwarding
    X. Zhang, S. Tallam, and R. Gupta. 14th ACM SIGSOFT Symposium on Foundations of Software Engineering (FSE), pages 81-91, Portland, Oregon, November 2006.

50. Distributed Slicing and Partial Re-execution for Distributed Programs
    E. Duesterwald, R. Gupta, and M.L. Soffa. 5th Workshop on Languages and Compilers for Parallel Computing (LCPC), LNCS 757 Springer Verlag, pages 497-511, Yale University, New Haven, Connecticut, August 1992.

• SHF: Small: CT-DDS - Scalable Concolic Testing of Parallel Applications With Shared Dynamic Data Structures,
  National Science Foundation, CCF-2226448, 10/2022-9/2025.
  

• TWC: Small: Collaborative: Improving Android Security with Dynamic Slicing,
  National Science Foundation, CCF-1617424, 9/2016-8/2020.
  

• Dynamic Slicing for Interactive Debugging of Multithreaded Programs,
  Intel Corporation, 6/2012-9/2015.

• SHF: Small: Memory Consistency - Hardware, Compiler, and Programming Support,
  National Science Foundation, CCF-1318103, 9/2013-8/2017.
  

• SHF: Medium: Programmable Monitoring Framework for Multicore Systems,
  National Science Foundation, CCF-0963996, 9/2010-8/2014.
  

• CSR-AES-RCS: Scalable and Efficient Dynamic Information Flow Tracking in Multithreaded Programs,
  National Science Foundation, CNS-0751961/0719791, 9/2007-8/2010.