The Experts below are selected from a list of 18219 Experts worldwide ranked by ideXlab platform
Philippe Moret - One of the best experts on this subject based on the ideXlab platform.
-
jp2 call site aware Calling Context profiling for the java virtual machine
Science of Computer Programming, 2014Co-Authors: Aibek Sarimbekov, Walter Binder, Philippe Moret, Andreas Sewe, Mira MeziniAbstract:Calling Context profiling fulfills programmers' information needs to obtain a complete picture of a program's inter- and intra-procedural control flow, which are important for workload characterization, debugging, profiling, program comprehension, and reverse engineering. Many existing Calling Context profilers for Java, however, resort to sampling or other incomplete instrumentation techniques; thus, they collect incomplete profiles only. In this article we present JP2, a new Calling Context profiler for the Java Virtual Machine, which collects profiles that are not only complete but also call-site aware; that is, JP2 is able to distinguish between multiple call sites within a single method. JP2 supports selective profiling of the dynamic extent of chosen methods and supports profiling of native method invocations. Moreover, produced profiles contain execution statistics at the level of individual basic blocks of code, thereby preserving the intra-procedural control flow of the profiled applications. We rigorously evaluate the overhead incurred by JP2. This overhead is acceptable in tasks such as workload characterization. JP2 is freely available under an Open Source license.
-
complete and platform independent Calling Context profiling for the java virtual machine
Electronic Notes in Theoretical Computer Science, 2011Co-Authors: Aibek Sarimbekov, Walter Binder, Philippe Moret, Andreas Sewe, Mira MeziniAbstract:Calling Context profiling collects statistics separately for each Calling Context. Complete Calling Context profiles that faithfully represent overall program execution are important for a sound analysis of program behavior, which in turn is important for program understanding, reverse engineering, and workload characterization. Many existing Calling Context profilers for Java rely on sampling or on incomplete instrumentation techniques, yielding incomplete profiles; others rely on Java Virtual Machine (JVM) modifications or work only with one specific JVM, thus compromising portability. In this paper we present a new Calling Context profiler for Java that reconciles completeness of the collected profiles and full compatibility with any standard JVM. In order to reduce measurement perturbation, our profiler collects platform-independent dynamic metrics, such as the number of method invocations and the number of executed bytecodes. In contrast to prevailing Calling Context profilers, our tool is able to distinguish between multiple call sites in a method and supports selective profiling of (the dynamic extent of) certain methods. We have evaluate the overhead introduced by our profiler with standard Java and Scala benchmarks on a range of different JVMs.
-
portable and accurate collection of Calling Context sensitive bytecode metrics for the java virtual machine
Principles and Practice of Programming in Java, 2011Co-Authors: Aibek Sarimbekov, Walter Binder, Philippe Moret, Andreas Sewe, Martin Schoeberl, Mira MeziniAbstract:Calling-Context profiles and dynamic metrics at the bytecode level are important for profiling, workload characterization, program comprehension, and reverse engineering. Prevailing tools for collecting Calling-Context profiles or dynamic bytecode metrics often provide only incomplete information or suffer from limited compatibility with standard JVMs. However, completeness and accuracy of the profiles is essential for tasks such as workload characterization, and compatibility with standard JVMs is important to ensure that complex workloads can be executed. In this paper, we present the design and implementation of JP2, a new tool that profiles both the inter- and intra-procedural control flow of workloads on standard JVMs. JP2 produces Calling-Context profiles preserving callsite information, as well as execution statistics at the level of individual basic blocks of code. JP2 is complemented with scripts that compute various dynamic bytecode metrics from the profiles. As a case-study and tutorial on the use of JP2, we use it for cross-profiling for an embedded Java processor.
-
visualizing and exploring profiles with Calling Context ring charts
Software - Practice and Experience, 2010Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex Villazon, Abbas HeydarnooriAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. The Calling Context Tree (CCT) is a common data structure that stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is a need for a condensed visualization that eases the localization of performance bottlenecks. In this article, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe two case studies where CCRCs help us to detect and fix performance problems in applications. A performance evaluation also confirms that our implementation can efficiently handle large CCTs. Copyright © 2010 John Wiley & Sons, Ltd.
-
exploring large profiles with Calling Context ring charts
Workshop on Software and Performance, 2010Co-Authors: Philippe Moret, Walter Binder, Alex Villazon, Danilo AnsaloniAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. A common data structure is the Calling Context Tree (CCT), which stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is need for a condensed visualization that eases the location of performance bottlenecks. In this paper, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe a case study where CCRCs help detect and fix performance problems in an application. An evaluation confirms that our implementation efficiently handles large CCTs with millions of nodes.
Alex Villazon - One of the best experts on this subject based on the ideXlab platform.
-
visualizing and exploring profiles with Calling Context ring charts
Software - Practice and Experience, 2010Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex Villazon, Abbas HeydarnooriAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. The Calling Context Tree (CCT) is a common data structure that stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is a need for a condensed visualization that eases the localization of performance bottlenecks. In this article, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe two case studies where CCRCs help us to detect and fix performance problems in applications. A performance evaluation also confirms that our implementation can efficiently handle large CCTs. Copyright © 2010 John Wiley & Sons, Ltd.
-
exploring large profiles with Calling Context ring charts
Workshop on Software and Performance, 2010Co-Authors: Philippe Moret, Walter Binder, Alex Villazon, Danilo AnsaloniAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. A common data structure is the Calling Context Tree (CCT), which stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is need for a condensed visualization that eases the location of performance bottlenecks. In this paper, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe a case study where CCRCs help detect and fix performance problems in an application. An evaluation confirms that our implementation efficiently handles large CCTs with millions of nodes.
-
visualizing Calling Context profiles with ring charts
Visualizing Software for Understanding and Analysis, 2009Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex VillazonAbstract:Calling Context profiling is an important technique for analysing the performance of object-oriented software with complex inter-procedural control flow. A common data structure is the Calling Context Tree (CCT), which stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is need for a condensed visualization that eases the location of performance bottlenecks. In this paper, we introduce Calling Context Ring Charts, a new compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric.
-
locating performance bottlenecks in embedded java software with Calling Context cross profiling
Quantitative Evaluation of Systems, 2009Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex Villazon, Martin SchoeberlAbstract:Prevailing approaches to analyze embedded software performance either require the deployment of the software on the embedded target, which can be tedious and may be impossible in an early development phase, or rely on simulation, which can be extremely slow. We promote cross-profiling as an alternative approach, which is particularly well suited for embedded Java processors. The embedded software is profiled in any standard Java Virtual Machine in a host environment, but the generated cross-profile estimates the execution time on the target. We implemented our approach in the customizable cross-profiler CProf, which generates Calling-Context cross-profiles. Each Calling-Context stores dynamic metrics, such as the estimated CPU cycle consumption on the target. We visualize the generated Calling-Context cross-profiles as ring charts, where callee methods are represented in segments surrounding the caller's segment. As the size of each segment corresponds to the relative CPU consumption of the corresponding Calling-Context, the visualization eases the location of performance bottlenecks in embedded Java software, revealing hot methods, as well as their callers and callees, at one glance.
-
parallelizing Calling Context profiling in virtual machines on multicores
Principles and Practice of Programming in Java, 2009Co-Authors: Walter Binder, Danilo Ansaloni, Alex Villazon, Philippe MoretAbstract:The Calling Context Tree (CCT) is a prevailing datastructure for Calling Context profiling. As generating a complete CCT reflecting every method call is expensive, recent research has focused on efficiently approximating the CCT with sampling techniques. However, for tasks such as debugging, testing, and reverse engineering, complete and accurate CCTs are often needed. In this paper, we introduce the ParCCT, a novel approach to parallelizing application code and CCT generation on multicores. Each thread maintains a shadow stack and generates "packets" of method calls and returns that correspond to partial CCTs. Each packet includes a copy of the shadow stack, indicating the Calling Context of the first method call in the packet. Hence, packets are independent of each other and can be processed out-of-order and in parallel in order to update the CCT. Our portable and extensible implementation targets standard Java Virtual Machines, thanks to instrumentation techniques that ensure complete bytecode coverage and efficiently support custom Calling Context representations. The ParCCT is more than 110% faster than a primitive, non-parallel approach to CCT construction, when more than two cores are available. This speedup stems both from reduced contention and from parallelization.
Walter Binder - One of the best experts on this subject based on the ideXlab platform.
-
comprehensive multi platform dynamic program analysis for the java and dalvik virtual machines
Principles and Practice of Programming in Java, 2014Co-Authors: Yudi Zheng, Haiyang Sun, Lubomir Bulej, Petr Tůma, Walter BinderAbstract:Despite its importance for many software engineering tasks, dynamic program analysis is only insufficiently supported on the Java platform [2]. Existing Java Virtual Machines (JVMs) as well as Android's Dalvik Virtual Machine (DVM) lack dedicated mechanisms for expressing arbitrary dynamic program analysis tasks at a high abstraction level, for ensuring complete code coverage of the analysis, and for isolating analysis tasks from the observed program to prevent interference. For example, the JVM Tool Interface requires analysis tasks to be written in low-level native code, and some virtual machines (e.g., DVM) do not support it. As a consequence, dynamic program analysis tools are often implemented using low-level mechanisms, resulting in error-prone code that is difficult to maintain, and support only a particular virtual machine. Moreover, many analysis tools produce unsound profiles (due to interference of the analysis with the observed program) or incomplete profiles (due to limited code coverage). We present a novel dynamic program analysis framework that offers high-level abstractions for comprehensive, multi-platform analysis for the JVM and DVM. Our framework ensures complete bytecode coverage and isolates the execution of the analysis code from the observed program. It is based on the concepts developed for DiSL [4], ShadowVM [3], and FRANC [1]. The domain-specific aspect language DiSL is used to specify the events of interest for an analysis. The events captured during program execution are transmitted to the ShadowVM, where the user-defined analysis code processes the events. Different event-ordering semantics are supported, avoiding synchronization for analyses that do not require global event ordering across all threads. In addition to events specified by DiSL code, our framework also generates lifecycle events and inter-process communication events. The latter is particularly important for the analysis of Android applications, as they typically involve multiple processes. Several state-of-the-art analysis tools have already been ported to our framework, including code coverage testing tools, Calling-Context profilers, and object liftetime profilers.
-
jp2 call site aware Calling Context profiling for the java virtual machine
Science of Computer Programming, 2014Co-Authors: Aibek Sarimbekov, Walter Binder, Philippe Moret, Andreas Sewe, Mira MeziniAbstract:Calling Context profiling fulfills programmers' information needs to obtain a complete picture of a program's inter- and intra-procedural control flow, which are important for workload characterization, debugging, profiling, program comprehension, and reverse engineering. Many existing Calling Context profilers for Java, however, resort to sampling or other incomplete instrumentation techniques; thus, they collect incomplete profiles only. In this article we present JP2, a new Calling Context profiler for the Java Virtual Machine, which collects profiles that are not only complete but also call-site aware; that is, JP2 is able to distinguish between multiple call sites within a single method. JP2 supports selective profiling of the dynamic extent of chosen methods and supports profiling of native method invocations. Moreover, produced profiles contain execution statistics at the level of individual basic blocks of code, thereby preserving the intra-procedural control flow of the profiled applications. We rigorously evaluate the overhead incurred by JP2. This overhead is acceptable in tasks such as workload characterization. JP2 is freely available under an Open Source license.
-
complete and platform independent Calling Context profiling for the java virtual machine
Electronic Notes in Theoretical Computer Science, 2011Co-Authors: Aibek Sarimbekov, Walter Binder, Philippe Moret, Andreas Sewe, Mira MeziniAbstract:Calling Context profiling collects statistics separately for each Calling Context. Complete Calling Context profiles that faithfully represent overall program execution are important for a sound analysis of program behavior, which in turn is important for program understanding, reverse engineering, and workload characterization. Many existing Calling Context profilers for Java rely on sampling or on incomplete instrumentation techniques, yielding incomplete profiles; others rely on Java Virtual Machine (JVM) modifications or work only with one specific JVM, thus compromising portability. In this paper we present a new Calling Context profiler for Java that reconciles completeness of the collected profiles and full compatibility with any standard JVM. In order to reduce measurement perturbation, our profiler collects platform-independent dynamic metrics, such as the number of method invocations and the number of executed bytecodes. In contrast to prevailing Calling Context profilers, our tool is able to distinguish between multiple call sites in a method and supports selective profiling of (the dynamic extent of) certain methods. We have evaluate the overhead introduced by our profiler with standard Java and Scala benchmarks on a range of different JVMs.
-
portable and accurate collection of Calling Context sensitive bytecode metrics for the java virtual machine
Principles and Practice of Programming in Java, 2011Co-Authors: Aibek Sarimbekov, Walter Binder, Philippe Moret, Andreas Sewe, Martin Schoeberl, Mira MeziniAbstract:Calling-Context profiles and dynamic metrics at the bytecode level are important for profiling, workload characterization, program comprehension, and reverse engineering. Prevailing tools for collecting Calling-Context profiles or dynamic bytecode metrics often provide only incomplete information or suffer from limited compatibility with standard JVMs. However, completeness and accuracy of the profiles is essential for tasks such as workload characterization, and compatibility with standard JVMs is important to ensure that complex workloads can be executed. In this paper, we present the design and implementation of JP2, a new tool that profiles both the inter- and intra-procedural control flow of workloads on standard JVMs. JP2 produces Calling-Context profiles preserving callsite information, as well as execution statistics at the level of individual basic blocks of code. JP2 is complemented with scripts that compute various dynamic bytecode metrics from the profiles. As a case-study and tutorial on the use of JP2, we use it for cross-profiling for an embedded Java processor.
-
visualizing and exploring profiles with Calling Context ring charts
Software - Practice and Experience, 2010Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex Villazon, Abbas HeydarnooriAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. The Calling Context Tree (CCT) is a common data structure that stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is a need for a condensed visualization that eases the localization of performance bottlenecks. In this article, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe two case studies where CCRCs help us to detect and fix performance problems in applications. A performance evaluation also confirms that our implementation can efficiently handle large CCTs. Copyright © 2010 John Wiley & Sons, Ltd.
Danilo Ansaloni - One of the best experts on this subject based on the ideXlab platform.
-
visualizing and exploring profiles with Calling Context ring charts
Software - Practice and Experience, 2010Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex Villazon, Abbas HeydarnooriAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. The Calling Context Tree (CCT) is a common data structure that stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is a need for a condensed visualization that eases the localization of performance bottlenecks. In this article, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe two case studies where CCRCs help us to detect and fix performance problems in applications. A performance evaluation also confirms that our implementation can efficiently handle large CCTs. Copyright © 2010 John Wiley & Sons, Ltd.
-
exploring large profiles with Calling Context ring charts
Workshop on Software and Performance, 2010Co-Authors: Philippe Moret, Walter Binder, Alex Villazon, Danilo AnsaloniAbstract:Calling Context profiling is an important technique for analyzing the performance of object-oriented software with complex inter-procedural control flow. A common data structure is the Calling Context Tree (CCT), which stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is need for a condensed visualization that eases the location of performance bottlenecks. In this paper, we discuss Calling Context Ring Charts (CCRCs), a compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric. We describe a case study where CCRCs help detect and fix performance problems in an application. An evaluation confirms that our implementation efficiently handles large CCTs with millions of nodes.
-
visualizing Calling Context profiles with ring charts
Visualizing Software for Understanding and Analysis, 2009Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex VillazonAbstract:Calling Context profiling is an important technique for analysing the performance of object-oriented software with complex inter-procedural control flow. A common data structure is the Calling Context Tree (CCT), which stores dynamic metrics, such as CPU time, separately for each Calling Context. As CCTs may comprise millions of nodes, there is need for a condensed visualization that eases the location of performance bottlenecks. In this paper, we introduce Calling Context Ring Charts, a new compact visualization for CCTs, where callee methods are represented in ring segments surrounding the caller's ring segment. In order to reveal hot methods, their callers, and callees, the ring segments can be sized according to a chosen dynamic metric.
-
locating performance bottlenecks in embedded java software with Calling Context cross profiling
Quantitative Evaluation of Systems, 2009Co-Authors: Philippe Moret, Walter Binder, Danilo Ansaloni, Alex Villazon, Martin SchoeberlAbstract:Prevailing approaches to analyze embedded software performance either require the deployment of the software on the embedded target, which can be tedious and may be impossible in an early development phase, or rely on simulation, which can be extremely slow. We promote cross-profiling as an alternative approach, which is particularly well suited for embedded Java processors. The embedded software is profiled in any standard Java Virtual Machine in a host environment, but the generated cross-profile estimates the execution time on the target. We implemented our approach in the customizable cross-profiler CProf, which generates Calling-Context cross-profiles. Each Calling-Context stores dynamic metrics, such as the estimated CPU cycle consumption on the target. We visualize the generated Calling-Context cross-profiles as ring charts, where callee methods are represented in segments surrounding the caller's segment. As the size of each segment corresponds to the relative CPU consumption of the corresponding Calling-Context, the visualization eases the location of performance bottlenecks in embedded Java software, revealing hot methods, as well as their callers and callees, at one glance.
-
parallelizing Calling Context profiling in virtual machines on multicores
Principles and Practice of Programming in Java, 2009Co-Authors: Walter Binder, Danilo Ansaloni, Alex Villazon, Philippe MoretAbstract:The Calling Context Tree (CCT) is a prevailing datastructure for Calling Context profiling. As generating a complete CCT reflecting every method call is expensive, recent research has focused on efficiently approximating the CCT with sampling techniques. However, for tasks such as debugging, testing, and reverse engineering, complete and accurate CCTs are often needed. In this paper, we introduce the ParCCT, a novel approach to parallelizing application code and CCT generation on multicores. Each thread maintains a shadow stack and generates "packets" of method calls and returns that correspond to partial CCTs. Each packet includes a copy of the shadow stack, indicating the Calling Context of the first method call in the packet. Hence, packets are independent of each other and can be processed out-of-order and in parallel in order to update the CCT. Our portable and extensible implementation targets standard Java Virtual Machines, thanks to instrumentation techniques that ensure complete bytecode coverage and efficiently support custom Calling Context representations. The ParCCT is more than 110% faster than a primitive, non-parallel approach to CCT construction, when more than two cores are available. This speedup stems both from reduced contention and from parallelization.
Michael D Bond - One of the best experts on this subject based on the ideXlab platform.
-
efficient Context sensitivity for dynamic analyses via Calling Context uptrees and customized memory management
Conference on Object-Oriented Programming Systems Languages and Applications, 2013Co-Authors: Jipeng Huang, Michael D BondAbstract:State-of-the-art dynamic bug detectors such as data race and memory leak detectors report program locations that are likely causes of bugs. However, programmers need more than static program locations to understand the behavior of increasingly complex and concurrent software. Dynamic Calling Context provides additional information, but it is expensive to record Calling Context frequently, e.g., at every read and write. Context-sensitive dynamic analyses can build and maintain a Calling Context tree (CCT) to track Calling Context--but in order to reuse existing nodes, CCT-based approaches require an expensive lookup.This paper introduces a new approach for Context sensitivity that avoids this expensive lookup. The approach uses a new data structure called the Calling Context uptree (CCU) that adds low overhead by avoiding the lookup and instead allocating a new node for each Context. A key contribution is that the approach can mitigate the costs of allocating many nodes by extending tracing garbage collection (GC): GC collects unused CCU nodes naturally and efficiently, and we extend GC to merge duplicate nodes lazily.We implement our CCU-based approach in a high-performance Java virtual machine and integrate it with a staleness-based memory leak detector and happens-before data race detector, so they can report Context-sensitive program locations that cause bugs. We show that the CCU-based approach, in concert with an extended GC, provides a compelling alternative to CCT-based approaches for adding Context sensitivity to dynamic analyses.
-
Breadcrumbs: Efficient Context Sensitivity for Dynamic Bug Detection Analyses ∗
2010Co-Authors: Michael D Bond, Graham Z. Baker, Samuel Z. GuyerAbstract:To appear in PLDI 2010. This is the submitted version. We welcome any feedback. Calling Context—the set of active methods on the stack—is critical for understanding the dynamic behavior of large programs. Dynamic program analysis tools, however, are almost exclusively Context insensitive because of the prohibitive cost of representing Calling Contexts at run time. Deployable dynamic analyses, in particular, are limited to reporting only static program locations. This paper presents Breadcrumbs, an efficient technique for recording and reporting dynamic Calling Contexts. It builds on an existing technique for computing a compact (one word) encoding of each Calling Context that client analyses can use in place of a program location. The key feature of our system is a search algorithm that can reconstruct a Calling Context from its encoding using only a static call graph and a small amount of dynamic information collected in cold methods. Breadcrumbs requires no offline training or program modifications, and handles all language features, including dynamic class loading. On average, it adds 10% to 20 % overhead to existing dynamic analyses, depending on how much additional information it collects: more information slows down execution, but improves the decoding algorithm. We use Breadcrumbs to add Context sensitivity to two dynamic analyses: a race detector and an analysis that identifies the origins of null pointer exceptions. Our system can reconstruct nearly all of the Contexts for the reported bugs in a few seconds. These Calling Contexts are non-trivial, and they significantly improve both the precision of the analyses and the quality of the bug reports. 1
-
Breadcrumbs: Efficient Context Sensitivity for Dynamic Bug Detection Analyses ∗
2010Co-Authors: Michael D Bond, Graham Z. Baker, Samuel Z. GuyerAbstract:Calling Context—the set of active methods on the stack—is critical for understanding the dynamic behavior of large programs. Dynamic program analysis tools, however, are almost exclusively Context insensitive because of the prohibitive cost of representing Calling Contexts at run time. Deployable dynamic analyses, in particular, are limited to reporting only static program locations. This paper presents Breadcrumbs, an efficient technique for recording and reporting dynamic Calling Contexts. It builds on an existing technique for computing a compact (one word) encoding of each Calling Context that client analyses can use in place of a program location. The key feature of our system is a search algorithm that can reconstruct a Calling Context from its encoding using only a static call graph and a small amount of dynamic information collected in cold methods. Breadcrumbs requires no offline training or program modifications, and handles all language features, including dynamic class loading. On average, it adds 10% to 20 % overhead to existing dynamic analyses, depending on how much additional information it collects: more information slows down execution, but improves the decoding algorithm. We use Breadcrumbs to add Context sensitivity to two dynamic analyses: a race detector and an analysis that identifies the origins of null pointer exceptions. Our system can reconstruct nearly all of the Contexts for the reported bugs in a few seconds. These Calling Contexts are non-trivial, and they significantly improve both the precision of the analyses and the quality of the bug reports. 1
-
probabilistic Calling Context
Conference on Object-Oriented Programming Systems Languages and Applications, 2007Co-Authors: Michael D Bond, Kathryn S MckinleyAbstract:Calling Context enhances program understanding and dynamic analyses by providing a rich representation of program location. Compared to imperative programs, object-oriented programs use more interprocedural and less intraprocedural control flow, increasing the importance of Context sensitivity for analysis. However, prior online methods for computing Calling Context, such as stack-walking or maintaining the current location in a Calling Context tree, are expensive in time and space. This paper introduces a new online approach called probabilistic Calling Context (PCC) that continuously maintains a probabilistically unique value representing the current Calling Context. For millions of unique Contexts, a 32-bit PCC value has few conflicts. Computing the PCC value adds 3% average overhead to a Java virtual machine. PCC is well-suited to clients that detect new or anomalous behavior since PCC values from training and production runs can be compared easily to detect new Context-sensitive behavior; clients that query the PCC value at every system call, Java utility call, and Java API call add 0-9% overhead on average. PCC adds space overhead proportional to the distinct Contexts stored by the client (one word per Context). Our results indicate PCC is efficient and accurate enough to use in deployed software for residual testing, bug detection, and intrusion detection.
