compute the ground-truth dependence set of any given query against the
distributed programs and their executions used in our evaluation; neither is
it possible to produce all such ground truth manually. Thus, we extended the
manual inspection adopted for the preliminary version of this work [30],
following a prior methodology aiming at a similar purpose [11] as summarized
as follows. For each of our studied subjects and executions, we randomly chose
ten queries for which none of the D2Abs instantiations produced a dependence
set that includes more than 50 methods---we had to limit the scale of this
manual study because of its tedious and heavyweight nature. Then, for each
chosen query, we manually produced the ground-truth dynamic dependence set by
in-depth code review and step-through tracking of the executions (like step-
over debugging) while leveraging available documentation of respective subject
systems. Using these ground-truth dependencies, we computed the precision and
recall for each of the chosen queries.

With these cases, the average (over all the subject executions and the ten
queries per execution) precision of Basic, Msg+, Csd+, and Scov+ was 55.1%,
64.8%, 93.4%, and 98.6%, respectively. Importantly, for all these cases, the
recall of any instantiation was 100%---indeed, the dependence set of each of
these sample queries did not include any dependencies induced by reflective or
JNI calls. This confirmed that the pruning carried out by the three advanced
versions only removed false-positive dependencies.

###  8.2 Instantiation Selection

As shown, our framework offers flexible options of cost-effectiveness
tradeoffs through the four instantiations each providing a distinct level of
such tradeoffs. For a user with a particular task that relies on the dynamic
dependencies computed by D2Abs, a practical problem is to how to choose the
right instantiation (tool) out of the varied alternatives. Thus, we make
recommendations in this regard as guidelines as follows.

Figure 7 suggests that the most cost-effective option varied both with
different subject systems (of varying code size and complexity) and with
different executions (of varying execution complexity) of the same systems.
Yet for systems and executions of a small to medium size and complexity, the
user might want to choose Scov+ given that it tended to offer the highest
cost-effectiveness in most cases in our evaluation study. For large-scale and
highly-complex distributed systems and executions, though, the user would be
most likely recommended to opt for Msg+ given the highest level of cost-
effectiveness it offered.

However, there are also situations in which the user’s best option may not be
the most cost-effective one. For instance, the user would choose the
instantiation that offers higher precision for the system and execution on
hand as long as the added costs are still affordable, even though the extra
costs are not best paid off. For another example, the fastest instantiation
might be the best choice to the user when the small efficiency advantages
(over the second fastest) matter, although this fastest tool is not as cost-
effective as other options. In these situations, the user should choose the
instantiation that satisfies the cost or effectiveness priority with respect
to the particular task. Note that the presence of these situations justifies
not only offering the most cost-effective analysis techniques but also
providing those of other levels of cost-effectiveness, just as D2Abs did.

##  9 Related Work

Four main categories of previous work are most related to ours: impact
analysis, dependence analysis of distributed programs, logging for distributed
systems, and dynamic partial order reduction.

###  9.1 Impact Analysis

The EAS approach [18] which partially inspired D2Abs is a performance
optimization of its predecessor PathImpact [17]. Many other dynamic impact
analysis techniques also exist [64, 65], aiming at improving precision [21,
66, 67], recall [68], efficiency [69], and cost-effectiveness [24, 12] over
PathImpact and EAS. However, these techniques did not address distributed or
multiprocess programs that we focus on in this work. Two recent advances in
dynamic impact analysis, Diver [21] and the unified framework in [24, 12],
utilize hybrid program analysis to achieve higher precision and more flexible
cost-effectiveness options over EAS-based approaches, but still target single-
process programs only. On the other hand, the Csd+ version of D2Abs was
initially motivated by these prior works to incorporate the static intra-
component dependencies for effectiveness improvement. In preliminary work [25,
30], we developed an early prototype of D2Abs that includes the the Basic and
Msg+ versions. This paper extends that prior work both technically by adding
Csd+ and Scov+, and empirically through a larger-scale and more extensive
evaluation.

An impact analysis for distributed systems, Helios [6] can predict impacts of
potential changes to support evolution tasks for DEBS. However, it relies on
particular message-type filtering and manual annotations in addition to a few
other constraints. Although these limitations are largely lifted by its
successor Eos [9], both approaches are _static_ and limited to DEBS only, as
is another technique [7] which identifies impacts based on change-type
classification yet ignores intra-component dependencies hence provides
incomplete results. While sharing similar goals, D2Abs targets a broader range
of distributed systems than DEBS using _dynamic_ analysis and without relying
on special source-code information (e.g., interface patterns) as those
techniques do. Unlike our dependence-based approach, a traceability-based
solution [70] is presented in [71] which relies on a well-curated repository
of various software models. The dynamic impact analysis for component-based
software in [72] works at architecture level, different from ours working for
distributed programs at code level.

###  9.2 Dependence Analysis of Distributed Programs

Historically, dependence analysis has underlain a wide range of code-based
software engineering tasks and associated techniques [3, 4]. In particular, a
large body and variety of dependence-based approaches have been proposed over
the past few decades to support development and maintenance in general [73,
74, 64, 75, 76, 77], and fault diagnosis [78, 79, 80, 81] and security defense
in particular [82, 83, 84, 85, 86, 87]. For instance, for maintaining and
evolving a software system, it is essential to assess the influence of given
program entries of interest on the rest of the program [70, 64] for change
planning (deciding whether to realize changes at candidate change locations)
and fulfillment (deciding where to realize the changes) [70, 35, 19].

Using fine-grained dependency analysis, a large body of work attempted to
extend traditional slicing algorithms to concurrent programs [88, 89, 42, 41,
90] yet mostly focused on centralized, and primarily multithreaded, ones. For
those programs, traditional dependence analysis was extended to handle
additional dependencies due to shared variable accesses, synchronization, and
communication between threads and/or processes (e.g., [88, 42]). While D2Abs
also handles multithreaded programs, it targets multiprocess ones running on
distributed machines, and aims at method-level dependence abstraction instead
of fine-grained slicing. For systems running in multiple processes where
interprocess communication is realized via socket-based message passing, an
approximation for static slicing was discussed in [88]. Various dynamic
slicing algorithms have been proposed too, earlier for procedural programs
only [91, 92, 31, 93, 94] and recently for object-oriented software also [13,
14, 15, 95]. And a more complete and detailed summary of slicing techniques
for distributed programs can be found in [90] and [14].

A few other static analysis algorithms for distributed systems exist as well
but focus on other (special) types of systems, such as RMI-based Java programs
[96], different from the common type of distributed systems [1] D2Abs
addresses. At coarser levels, researchers resolve dependencies in distributed
systems too but for different purposes such as enhancing parallelization [97],
system configuration [98], and high-level system modeling [99, 10], or limited
to static analysis [5, 6, 9]. In contrast, D2Abs performs code-based analysis
while providing more focused dependencies (impacts) relative to concrete
program executions than static-analysis approaches.

###  9.3 Logging for Distributed Systems

Targeting high-level understanding of distributed systems, techniques like
logging and mining run-time logs [10, 34] infer inter-component interactions
using textual analysis of system logs, relying on the availability of
particular data such as informative logs and/or patterns in them. D2Abs
utilizes similar information (i.e., the Lamport timestamps) but infers the
happens-before relation between method-execution events mainly for code-level
dependence analysis. Also, D2Abs automatically generates such information it
requires rather than relying on existing information in the original programs.

The Lamport timestamp used is related to vector clocks [100, 101] used by
other tools, such as ShiVector [99] for ordering distributed logs and Poet
[102] for visualizing distributed systems executions. While we could utilize
vector clocks also, we chose the Lamport timestamp as it is lighter-weight yet
suffices for D2Abs. In addition, unlike ShiVector, which requires accesses to
source code and recompilation using the AspectJ compiler, D2Abs does not have
such constraints as it works on bytecode.

Tracing message-passing systems was explored before but for different
purposes, such as overcoming non-determinacy/race detection [103] and
reproducing buggy executions [104]. Tools like RoadRunner [105] and
ThreadSanitizer [106] targeted multithreaded, centralized programs. None of
these solutions work for large, diverse distributed systems without
perturbations as D2Abs did.

###  9.4 Dynamic Partial Order Reduction (DPOR)

DPOR has been used to improve the performance of model checking concurrent
software by avoiding the examination of independent transitions [107]. Sharing
the spirit of DPOR, especially distributed DPOR [108], D2Abs synchronizes
method-execution events for efficient computation of partial ordering of
methods within processes, and exploits message-passing semantics to avoid
partial-ordering independent methods across processes. However, unlike
existing DPOR techniques which target multi-threaded programs, D2Abs focuses
on multi-process, distributed programs. On the other hand, DPOR may be adopted
for dynamic dependence analysis of distributed programs with
extensions/adaptations. First, the execution conditions of methods can be
modeled as method-level states (versus statement-level states in the original
DPOR). Also, to represent state transitions across processes, the identifiers
of parent processes need to be incorporated in thread identifiers. Finally,
partial ordering algorithms like LTS may be employed to determine transition
dependence at process level.

##  10 Conclusion

Modeling and reasoning about program dependencies has long been a fundamental
approach to many advanced techniques and tools for various software
engineering tasks, ranging from testing and debugging to refactoring and
optimizations. However, traditional dependence models and analysis algorithms,
which assume explicit references among code entities, cannot be readily
applied to distributed systems with full potential, because the architectural
design of these systems encourages implicit references among decoupled
components via networking facilities such as socket.

To unleash the power of dependence analysis for distributed software, we
presented D2Abs, a framework for dynamic dependence abstraction that safely
approximates run-time code dependencies at method level both within and across
process boundaries. D2Abs offers cost-effective dependence abstraction by
partially ordering method-execution events, exploiting message-passing
semantics, incorporating static intra-component dependencies, and leveraging
whole-system statement coverage data. Blending multiple forms of program
information, D2Abs offers flexible cost-effectiveness balances via four
instantiations, to accommodate varying time and other resource budgets in
diverse task scenarios in distributed software development and maintenance.

We motivated and described the design of this framework in its application for
dynamic impact analysis, and evaluated its effectiveness and efficiency also
in the context of impact prediction. Our empirical results with large real-
world distributed programs have shown the superior effectiveness of advanced
D2Abs versions over its basic, purely control-flow based version as a baseline
by safely reducing false positives of the baseline by 15% to 54% at the cost
of varied but reasonable analysis overheads. There are many applications of
D2Abs beyond impact analysis. As immediately next steps, we plan to apply the
framework for performance diagnosis and security defense of distributed
systems.

## References

  * [1] G. Coulouris, J. Dollimore, T. Kindberg, and G. Blair, _Distributed Systems: Concepts and Design_ , 5th ed. Addison-Wesley Publishing Company, 2011.
  * [2] J. Dean, ‘‘Designs, lessons and advice from building large distributed systems,’’ _Keynote from LADIS_ , pp. 1--73, 2009.
  * [3] A. Podgurski and L. Clarke, ‘‘A formal model of program dependences and its implications for software testing, debugging, and maintenance,’’ _IEEE Transactions on Software Engineering_ , vol. 16, no. 9, pp. 965--979, 1990.
  * [4] S. Horwitz and T. Reps, ‘‘The use of program dependence graphs in software engineering,’’ in _Proceedings of IEEE/ACM International Conference on Software Engineering_ , 1992, pp. 392--411.
  * [5] G. C. Murphy and D. Notkin, ‘‘Lightweight lexical source model extraction,’’ _ACM Transactions on Software Engineering and Methodology_ , vol. 5, no. 3, pp. 262--292, 1996.
  * [6] D. Popescu, J. Garcia, K. Bierhoff, and N. Medvidovic, ‘‘Impact analysis for distributed event-based systems,’’ in _Proceedings of International Conference on Distributed Event-Based Systems_ , 2012, pp. 241--251.
  * [7] S. Tragatschnig, H. Tran, and U. Zdun, ‘‘Impact analysis for event-based systems using change patterns,’’ in _Proceedings of ACM Symposium on Applied Computing_ , 2014, pp. 763--768.
  * [8] K. Jayaram and P. Eugster, ‘‘Program analysis for event-based distributed systems,’’ in _Proceedings of International Conference on Distributed Event-Based System_ , 2011, pp. 113--124.
  * [9] J. Garcia, D. Popescu, G. Safi, W. G. Halfond, and N. Medvidovic, ‘‘Identifying message flow in distributed event-based systems,’’ in _Proceedings of ACM International Symposium on the Foundations of Software Engineering_ , 2013, pp. 367--377.
  * [10] I. Beschastnikh, Y. Brun, M. D. Ernst, and A. Krishnamurthy, ‘‘Inferring models of concurrent systems from logs of their behavior with CSight,’’ in _Proceedings of IEEE/ACM International Conference on Software Engineering_ , 2014, pp. 468--479.
  * [11] H. Cai, ‘‘Hybrid program dependence approximation for effective dynamic impact prediction,’’ _IEEE Transactions on Software Engineering_ , vol. 44, no. 4, pp. 334--364, 2018.
  * [12] H. Cai, R. Santelices, and D. Thain, ‘‘Diapro: Unifying dynamic impact analyses for improved and variable cost-effectiveness,’’ _ACM Transactions on Software Engineering and Methodology_ , vol. 25, no. 2, p. 18, 2016.
  * [13] D. P. Mohapatra, R. Kumar, R. Mall, D. Kumar, and M. Bhasin, ‘‘Distributed dynamic slicing of Java programs,’’ _Journal of Systems and Software_ , vol. 79, no. 12, pp. 1661--1678, 2006.
  * [14] S. S. Barpanda and D. P. Mohapatra, ‘‘Dynamic slicing of distributed object-oriented programs,’’ _IET software_ , vol. 5, no. 5, pp. 425--433, 2011\.
  * [15] S. Pani, S. M. Satapathy, and G. Mund, ‘‘Slicing of programs dynamically under distributed environment,’’ in _Proceedings of International Conference on Advances in Computing_. Springer, 2012, pp. 601--609.
  * [16] H. Cai and R. Santelices, ‘‘Method-level program dependence abstraction and its application to impact analysis,’’ _Journal of Systems and Software_ , vol. 122, pp. 311--326, 2016.
  * [17] J. Law and G. Rothermel, ‘‘Whole program path-based dynamic impact analysis,’’ in _Proceedings of IEEE/ACM International Conference on Software Engineering_ , 2003, pp. 308--318.
  * [18] T. Apiwattanapong, A. Orso, and M. J. Harrold, ‘‘Efficient and precise dynamic impact analysis using execute-after sequences,’’ in _Proceedings of IEEE/ACM International Conference on Software Engineering_ , 2005, pp. 432--441.
  * [19] Y. Tao, Y. Dang, T. Xie, D. Zhang, and S. Kim, ‘‘How do software engineers understand code changes?: an exploratory study in industry,’’ in _Proceedings of ACM International Symposium on the Foundations of Software Engineering_ , 2012, pp. 51:1--51:11.
  * [20] H. Cai and R. Santelices, ‘‘A comprehensive study of the predictive accuracy of dynamic change-impact analysis,’’ _Journal of Systems and Software_ , vol. 103, pp. 248--265, 2015.
  * [21] \------, ‘‘Diver: Precise dynamic impact analysis using dependence-based trace pruning,’’ in _Proceedings of International Conference on Automated Software Engineering_ , 2014, pp. 343--348.
  * [22] M. Acharya and B. Robinson, ‘‘Practical Change Impact Analysis Based on Static Program Slicing for Industrial Software Systems,’’ in _Proceedings of IEEE/ACM International Conference on Software Engineering, Software Engineering in Practice Track_ , May 2011, pp. 746--765.
  * [23] X. Zhang, R. Gupta, and Y. Zhang, ‘‘Precise dynamic slicing algorithms,’’ in _Proc. of Int’l Conf. on Softw. Eng._ , May 2003, pp. 319--329.
  * [24] H. Cai and R. Santelices, ‘‘A framework for cost-effective dependence-based dynamic impact analysis,’’ in _International Conference on Software Analysis, Evolution, and Reengineering_ , 2015, pp. 231--240.
  * [25] H. Cai and D. Thain, ‘‘DistIA: A cost-effective dynamic impact analysis for distributed programs,’’ in _Proceedings of the 31st IEEE/ACM International Conference on Automated Software Engineering_ , 2016, pp. 344--355.
  * [26] L. Lamport, ‘‘Time, clocks, and the ordering of events in a distributed system,’’ _Communications of the ACM_ , vol. 21, no. 7, pp. 558--565, 1978\.
  * [27] D. Jackson and M. Rinard, ‘‘Software analysis: A roadmap,’’ in _Proceedings of the Conference on the Future of Software Engineering_ , 2000, pp. 133--145.
  * [28] H. Cai and R. Santelices, ‘‘Abstracting program dependencies using the method dependence graph,’’ in _International Conference on Software Quality, Reliability and Security (QRS)_ , 2015, pp. 49--58.
  * [29] C. Artho, M. Hagiya, R. Potter, Y. Tanabe, F. Weitl, and M. Yamamoto, ‘‘Software model checking for distributed systems with selector-based, non-blocking communication,’’ in _Proceedings of IEEE/ACM International Conference on Automated Software Engineering_ , 2013, pp. 169--179.
  * [30] H. Cai and D. Thain, ‘‘Distea: Efficient dynamic impact analysis for distributed systems,’’ _arXiv preprint arXiv:1604.04638_ , 2016.
  * [31] D. Goswami and R. Mall, ‘‘Dynamic slicing of concurrent programs,’’ in _IEEE International Conference on High Performance Computing_ , 2000, pp. 15--26.
  * [32] G. Mühl, L. Fiege, and P. Pietzuch, _Distributed event-based systems_. Springer, 2006, vol. 1.
  * [33] P. Eugster and K. Jayaram, ‘‘EventJava: An extension of Java for event correlation,’’ in _Proceedings of European Conference on Object-Oriented Programming_. Springer, 2009, pp. 570--594.
  * [34] J.-G. Lou, Q. Fu, Y. Wang, and J. Li, ‘‘Mining dependency in distributed systems through unstructured logs analysis,’’ _ACM SIGOPS Operating Systems Review_ , vol. 44, no. 1, pp. 91--96, 2010.
  * [35] P. Rovegard, L. Angelis, and C. Wohlin, ‘‘An empirical study on views of importance of change impact analysis issues,’’ _IEEE Transactions on Software Engineering_ , vol. 34, no. 4, pp. 516--530, 2008.
  * [36] C. R. de Souza and D. F. Redmiles, ‘‘An empirical study of software developers’ management of dependencies and changes,’’ in _Proceedings of the 30th international conference on Software engineering_. ACM, 2008, pp. 241--250.
  * [37] E. Pitt and K. McNiff, _Java. RMI: The Remote Method Invocation Guide_. Addison-Wesley Longman Publishing Co., Inc., 2001.
  * [38] J. Siegel and D. Frantz, _CORBA 3 fundamentals and programming_. John Wiley & Sons New York, NY, USA:, 2000, vol. 2.
  * [39] S. Horwitz, T. Reps, and D. Binkley, ‘‘Interprocedural slicing using dependence graphs,’’ _ACM Trans. on Prog. Lang. and Systems_ , vol. 12, no. 1, pp. 26--60, 1990.
  * [40] J. Ferrante, K. Ottenstein, and J. Warren, ‘‘The program dependence graph and its use in optimization,’’ _ACM Trans. on Prog. Lang. and Systems , 9(3):319-349_, Jul. 1987.
  * [41] D. Giffhorn and C. Hammer, ‘‘Precise slicing of concurrent programs,’’ _Automated Software Engineering_ , vol. 16, no. 2, pp. 197--234, 2009.
  * [42] M. G. Nanda and S. Ramesh, ‘‘Interprocedural slicing of multithreaded programs with applications to Java,’’ _ACM Transactions on Programming Languages and Systems_ , vol. 28, no. 6, pp. 1088--1144, 2006.
  * [43] X. Fu and H. Cai, ‘‘Measuring interprocess communications in distributed systems,’’ in _IEEE/ACM International Conference on Program Comprehension (ICPC)_ , 2019, pp. 323--334.
  * [44] Apache, ‘‘ZooKeeper,’’ https://zookeeper.apache.org/, 2015.
  * [45] A. Beszedes, C. Farago, Z. Mihaly Szabo, J. Csirik, and T. Gyimothy, ‘‘Union slices for program maintenance,’’ in _Proceedings of IEEE International Conference on Software Maintenance_ , Oct. 2002, pp. 12--21.
  * [46] B. Livshits, M. Sridharan, Y. Smaragdakis, O. Lhoták, J. N. Amaral, B.-Y. E. Chang, S. Z. Guyer, U. P. Khedker, A. Møller, and D. Vardoulakis, ‘‘In defense of soundiness: a manifesto.’’ _Communications of the ACM_ , vol. 58, no. 2, pp. 44--46, 2015.
  * [47] P. Lam, E. Bodden, O. Lhoták, and L. Hendren, ‘‘Soot - a Java bytecode optimization framework,’’ in _Cetus Users and Compiler Infrastructure Workshop_ , 2011.
  * [48] Oracle, ‘‘Java Socket I/O,’’ http://docs.oracle.com/javase/7/docs/api/java/net/Socket.html, 2015.
  * [49] \------, ‘‘Java NIO,’’ http://docs.oracle.com/javase/7/docs/api/java/nio/package-summary.html, 2015\.
  * [50] GoogleCode, ‘‘MultiChat,’’ https://code.google.com/p/multithread-chat-server/, 2015.
  * [51] SourceForge, ‘‘NioEcho,’’ http://rox-xmlrpc.sourceforge.net/niotut/index.html#Thecode, 2015.
  * [52] Vice, ‘‘xSocket,’’ http://xsocket.org/, 2018.
  * [53] Apache, ‘‘Thrift,’’ https://thrift.apache.org/, 2018.
  * [54] Bamberg University, ‘‘Open Chord,’’ http://sourceforge.net/projects/open-chord/, 2015.
  * [55] P. Hunt, M. Konar, F. P. Junqueira, and B. Reed, ‘‘Zookeeper: Wait-free coordination for internet-scale systems.’’ in _Proceedings of USENIX Annual Technical Conference_ , vol. 8, 2010, p. 9.
  * [56] Apache, ‘‘Voldemort,’’ https://github.com/voldemort, 2015.
  * [57] The Freenet team, ‘‘The Free Network,’’ https://freenetproject.org/, 2015\.
  * [58] R. E. Walpole, R. H. Myers, S. L. Myers, and K. E. Ye, _Probability and Statistics for Engineers and Scientists_. Prentice Hall, Jan. 2011.
  * [59] N. Cliff, _Ordinal methods for behavioral data analysis_. Psychology Press, 1996.
  * [60] J. Romano, J. D. Kromrey, J. Coraggio, J. Skowronek, and L. Devine, ‘‘Exploring methods for evaluating group differences on the nsse and other surveys: Are the t-test and cohen’sd indices the most appropriate choices,’’ in _Annual meeting of the Florida Association of Institutional Research_. Citeseer, 2006.
  * [61] T. D. LaToza, G. Venolia, and R. DeLine, ‘‘Maintaining mental models: a study of developer work habits,’’ in _Proceedings of the 28th international conference on Software engineering_. ACM, 2006, pp. 492--501.
  * [62] M. Lindvall and K. Sandahl, ‘‘How well do experienced software developers predict software change?’’ _Journal of Systems and Software_ , vol. 43, no. 1, pp. 19--27, 1998.
  * [63] L. N. Q. Do, K. Ali, B. Livshits, E. Bodden, J. Smith, and E. Murphy-Hill, ‘‘Just-in-time static analysis,’’ in _Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis_. ACM, 2017, pp. 307--317.
  * [64] B. Li, X. Sun, H. Leung, and S. Zhang, ‘‘A survey of code-based change impact analysis techniques,’’ _Software Testing, Verification and Reliability_ , vol. 23, pp. 613--646, 2013.
  * [65] H. Cai, ‘‘A reflection on the predictive accuracy of dynamic impact analysis,’’ in _2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER)_. IEEE, 2020, pp. 562--566.
  * [66] H. Cai, S. Jiang, R. Santelices, Y. jie Zhang, and Y. Zhang, ‘‘SensA: Sensitivity analysis for quantitative change-impact prediction,’’ in _Proceedings of IEEE Working Conference on Source Code Analysis and Manipulation_ , 2014, pp. 165--174.
  * [67] H. Cai, R. Santelices, and S. Jiang, ‘‘Prioritizing change-impact analysis via semantic program-dependence quantification,’’ _IEEE Transactions on Reliability_ , vol. 65, no. 3, 2015.
  * [68] M. C. O. Maia, R. A. Bittencourt, J. C. A. de Figueiredo, and D. D. S. Guerrero, ‘‘The hybrid technique for object-oriented software change impact analysis,’’ in _Proceedings of European Conference on Software Maintainance and Reengineering_ , 2010, pp. 252--255.
  * [69] B. Breech, M. Tegtmeyer, and L. Pollock, ‘‘A comparison of online and dynamic impact analysis algorithms,’’ in _Proceedings of European Conference on Software Maintainance and Reengineering_ , 2005, pp. 143--152.
  * [70] S. A. Bohner and R. S. Arnold, _An introduction to software change impact analysis_. Software Change Impact Analysis, IEEE Comp. Soc. Press, pp. 1--26, Jun. 1996.
  * [71] H. M. Sneed, ‘‘Impact analysis of maintenance tasks for a distributed object-oriented system,’’ in _Proceedings of the IEEE International Conference on Software Maintenance_ , 2001, p. 180.
  * [72] T. Feng and J. I. Maletic, ‘‘Applying dynamic change impact analysis in component-based architecture design,’’ in _ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing_ , 2006, pp. 43--48.
  * [73] K. B. Gallagher and J. R. Lyle, ‘‘Using program slicing in software maintenance,’’ _Software Engineering, IEEE Transactions on_ , vol. 17, no. 8, pp. 751--761, 1991.
  * [74] J. P. Loyall and S. A. Mathisen, ‘‘Using dependence analysis to support the software maintenance process,’’ in _Software Maintenance, 1993. CSM-93, Proceedings., Conference on_. IEEE, 1993, pp. 282--291.
  * [75] A. Orso, S. Sinha, and M. J. Harrold, ‘‘Classifying data dependences in the presence of pointers for program comprehension, testing, and debugging,’’ _ACM Trans. on Softw. Eng. and Methodology_ , vol. 13, no. 2, pp. 199--239, April 2004.
  * [76] M. Petrenko and V. Rajlich, ‘‘Variable granularity for improving precision of impact analysis,’’ in _Program Comprehension, 2009. ICPC’09. IEEE 17th International Conference on_. IEEE, 2009, pp. 10--19.
  * [77] H. Cai and R. Santelices, ‘‘TracerJD: Generic trace-based dynamic dependence analysis with fine-grained logging,’’ in _International Conference on Software Analysis, Evolution, and Reengineering_ , 2015, 489--493.
  * [78] G. K. Baah, A. Podgurski, and M. J. Harrold, ‘‘The Probabilistic Program Dependence Graph and Its Application to Fault Diagnosis,’’ _IEEE Transactions on Software Engineering_ , vol. 36, no. 4, pp. 528--545, 2010.
  * [79] S. Bates and S. Horwitz, ‘‘Incremental program testing using program dependence graphs,’’ in _Proc. of Symp. on Principles of Prog. Lang._ , Jan. 1993, pp. 384--396.
  * [80] W. E. Wong, R. Gao, Y. Li, R. Abreu, and F. Wotawa, ‘‘A survey on software fault localization,’’ _IEEE Transactions on Software Engineering_ , vol. 42, no. 8, pp. 707--740, Aug 2016.
  * [81] X. Fu, H. Cai, and L. LI, ‘‘Dads: Dynamic slicing continuously-running distributed programs with budget constraints,’’ in _ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_ , 2020, pp. 1566--1570.
  * [82] M. Dalton, H. Kannan, and C. Kozyrakis, ‘‘Raksha: a flexible information flow architecture for software security,’’ in _ACM SIGARCH Computer Architecture News_ , vol. 35, no. 2. ACM, 2007, pp. 482--493.
  * [83] M. Attariyan and J. Flinn, ‘‘Automating configuration troubleshooting with dynamic information flow analysis.’’ in _OSDI_ , vol. 10, 2010, pp. 1--14.
  * [84] V. P. Kemerlis, G. Portokalidis, K. Jee, and A. D. Keromytis, ‘‘libdft: Practical dynamic data flow tracking for commodity systems,’’ in _Acm Sigplan Notices_ , vol. 47, no. 7. ACM, 2012, pp. 121--132.
  * [85] X. Fu and H. Cai, ‘‘A dynamic taint analyzer for distributed systems,’’ in _ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE)_ , 2019, pp. 1115--1119.
  * [86] \------, ‘‘Scaling application-level dynamic taint analysis to enterprise-scale distributed systems,’’ in _Proceedings of the ACM/IEEE 42nd International Conference on Software Engineering: Companion Proceedings_ , 2020, pp. 270--271.
  * [87] \------, ‘‘Flowdist: Multi-staged refinement-based dynamic information flow analysis for distributed software systems,’’ in _30th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 21)_, 2021, pp. 2093--2110.
  * [88] J. Krinke, ‘‘Context-sensitive slicing of concurrent programs,’’ in _Proceedings of ACM International Symposium on the Foundations of Software Engineering_ , vol. 28, no. 5, 2003, pp. 178--187.
  * [89] J. Xiao, D. Zhang, H. Chen, and H. Dong, ‘‘Improved program dependence graph and algorithm for static slicing concurrent programs,’’ in _Advanced Parallel Processing Technologies_. Springer, 2005, pp. 121--130.
  * [90] B. Xu, J. Qian, X. Zhang, Z. Wu, and L. Chen, ‘‘A brief survey of program slicing,’’ _ACM SIGSOFT Software Engineering Notes_ , vol. 30, no. 2, pp. 1--36, 2005.
  * [91] B. Korel and R. Ferguson, ‘‘Dynamic slicing of distributed programs,’’ _Applied Mathematics and Computer Science_ , vol. 2, no. 2, pp. 199--215, 1992\.
  * [92] J. Cheng, ‘‘Dependence analysis of parallel and distributed programs and its applications,’’ in _Proceedings of Advances in Parallel and Distributed Computing_ , 1997, pp. 370--377.
  * [93] E. Duesterwald, R. Gupta, and M. Soffa, ‘‘Distributed slicing and partial re-execution for distributed programs,’’ in _Languages and Compilers for Parallel Computing_. Springer, 1993, pp. 497--511.
  * [94] M. Kamkar and P. Krajina, ‘‘Dynamic slicing of distributed programs,’’ in _Proceedings of IEEE International Conference on Software Maintenance_ , 1995, pp. 222--229.
  * [95] X. Fu, H. Cai, W. Li, and L. LI, ‘‘Seads: Scalable and cost-effective dynamic dependence analysis of distributed systems via reinforcement learning,’’ _ACM Transactions on Software Engineering and Methodology (TOSEM)_ , vol. 30, no. 1, 2020.
  * [96] M. Sharp and A. Rountev, ‘‘Static analysis of object references in RMI-based Java software,’’ _IEEE Transactions on Software Engineering_ , vol. 32, no. 9, pp. 664--681, 2006.
  * [97] K. Psarris and K. Kyriakopoulos, ‘‘An experimental evaluation of data dependence analysis techniques,’’ _IEEE Transactions on Parallel and Distributed Systems_ , vol. 15, no. 3, pp. 196--213, 2004.
  * [98] F. Kon and R. H. Campbell, ‘‘Dependence management in component-based distributed systems,’’ _IEEE concurrency_ , vol. 8, no. 1, pp. 26--36, 2000\.
  * [99] J. Abrahamson, I. Beschastnikh, Y. Brun, and M. D. Ernst, ‘‘Shedding light on distributed system executions,’’ in _Companion Proceedings of the 36th International Conference on Software Engineering_ , 2014, pp. 598--599.
  * [100] C. J. Fidge, ‘‘Timestamps in message-passing systems that preserve the partial ordering,’’ in _Proceedings of the 11th Australian Computer Science Conference_ , vol. 10, no. 1, 1988, pp. 56--66.
  * [101] F. Mattern, ‘‘Virtual time and global states of distributed systems,’’ _Parallel and Distributed Algorithms_ , vol. 1, no. 23, pp. 215--226, 1989\.
  * [102] T. Kunz, J. P. Black, D. J. Taylor, and T. Basten, ‘‘Poet: Target-system independent visualizations of complex distributed-application executions,’’ _The Computer Journal_ , vol. 40, no. 8, pp. 499--512, 1997.
  * [103] R. H. Netzer and B. P. Miller, ‘‘Optimal tracing and replay for debugging message-passing parallel programs,’’ _The Journal of Supercomputing_ , vol. 8, no. 4, pp. 371--388, 1995.
  * [104] R. Konuru, H. Srinivasan, and J.-D. Choi, ‘‘Deterministic replay of distributed java applications,’’ in _International Parallel and Distributed Processing Symposium_ , 2000, pp. 219--227.
  * [105] C. Flanagan and S. N. Freund, ‘‘The roadrunner dynamic analysis framework for concurrent programs,’’ in _Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering_ , 2010, pp. 1--8.
  * [106] K. Serebryany and T. Iskhodzhanov, ‘‘Threadsanitizer: data race detection in practice,’’ in _Proceedings of the Workshop on Binary Instrumentation and Applications_ , 2009, pp. 62--71.
  * [107] C. Flanagan and P. Godefroid, ‘‘Dynamic partial-order reduction for model checking software,’’ in _Proceedings of the 32Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages_ , 2005, pp. 110--121.
  * [108] Y. Yang, X. Chen, G. Gopalakrishnan, and R. M. Kirby, ‘‘Distributed dynamic partial order reduction based verification of threaded software,’’ in _Model Checking Software_. Springer, 2007, pp. 58--75.