Information Technology Reference
In-Depth Information
be done manually or automatically based on existing techniques, such as AOP
[14]. However, the programs instrumented with runtime monitors usually con-
tain many redundant instrumentations, which result in a significant monitoring
overhead. Therefore, some approaches [6,12] exploit static analysis information
to remove provable unnecessary instrumentations for reducing the overhead of
runtime monitoring. These methods are often called hybrid typestate analysis.
Theoretically, hybrid typestate analysis is equivalent to the static analysis of
typestate properties. If all the instrumentations of a runtime monitor can be
removed, the program is proved to satisfy the typestate property. Nop-shadows
analysis (NSA) [6,7] is one of the existing hybrid analysis methods. NSA is
implemented in Clara [1] to optimize the runtime monitoring of large-scale
Java programs. NSA uses intra-procedural flow-sensitive and partially context-
sensitive data-flow analysis to identify the redundant instrumentations generated
for monitors.
Although NSA is effective [6,7], there are some cases in which unnecessary
instrumentations still remain after NSA. One of the main reasons is that NSA
is only an intra-procedural flow-sensitive static analysis. The overly conservative
approximations of inter-procedural cases in NSA reduce the accuracy of the
analysis. In this paper, we propose two optimizations to improve the precision
of NSA. Both of the optimizations can filter interferential configurations when
determining whether a monitoring instrumentation is necessary. An interferential
configuration refers to the configuration that lowers the precision of identifying
“nop shadows” in NSA. One optimization identifies changeless configurations
produced by the backward data-flow analysis of NSA; the other one utilizes
local object information to refine the iterations of data-flow analysis. Using the
two optimizations, more unnecessary instrumentations can be removed.
To evaluate our optimizations, we have integrated our optimizations into
Clara, and applied them to the DaCapo benchmark suite [4]. In more than
half of the cases, the optimized NSA can further remove unnecessary instru-
mentations after the original NSA. In two cases, we get a perfect result,
i.e.
,
all the monitoring instrumentations are removed, entirely obviating the need for
monitoring at runtime.
To summarize, our paper has the following contributions:
- Propose two optimizations for NSA to improve the precision of the analysis.
Both of the optimizations filter interferential configurations by identifying
changeless configurations and exploiting local object information.
- Propose and implement an approximate, but sound, intra-procedural flow-
sensitive algorithm to determine whether a variable points to a local object.
- Implement the two optimizations and integrate them into Clara.
- Conduct extensive experiments on the DaCapo benchmark suite to show the
effectiveness of our optimizations.
The remainder of this paper is organized as follows. We begin with an overview
of NSA in Section 2. In Section 3, we give two motivating examples to illustrate
the two different optimization methods, respectively. Section 4 formulates the
details of our proposed optimizations. Our experiments, described in Section 5,
