Information Technology Reference
In-Depth Information
Optimizing Nop-shadows Typestate Analysis
by Filtering Interferential Configurations
Chengsong Wang
1
, Zhenbang Chen
1
,
2
,
, and Xiaoguang Mao
1
1
College of Computer, National University of Defense Technology, Changsha, China
2
National Laboratory for Parallel and Distributed Processing, Changsha, China
jameschen186@gmail.com,
{
zbchen,xgmao
}
@nudt.edu.cn
Abstract.
Nop-shadows Analysis (NSA) is an ecient static typestate
analysis, which can be used to eliminate unnecessary monitoring instru-
mentations for runtime monitors. In this paper, we propose two opti-
mizations to improve the precision of NSA. Both of the optimizations
filter interferential configurations when determining whether a monitor-
ing instrumentation is necessary. We have implemented our optimization
methods in Clara and conducted extensive experiments on the DaCapo
benchmark. The experimental results indicate that the optimized NSA
can further remove unnecessary instrumentations after the original NSA
in more than half of the cases, without a significant overhead. In addi-
tion, for two cases, all the instrumentations are removed, which implies
the program is proved to satisfy the typestate property.
Keywords:
Typestate Analysis, Runtime Monitoring, Static Analysis,
Nop-shadows Analysis.
1 Introduction
A typestate property [23] describes the acceptable operations on a single ob-
ject or a group of inter-related objects, according to the current state (i.e., the
typestate) of the object or the group [7,10]. For example, usually, programmers
cannot call the method
write
until the method
open
is called on a same File
object. Lots of large-scale software system errors are caused by the violations of
typestate properties. What is worse, it is very dicult and time-consuming to
find out and fix these errors [6,22]. The static analysis of a program with respect
to a typestate property is generally undecidable. The existing static typestate
checking tools [3,19] suffer from the scalability and the false-alarm problems.
Dynamic typestate checking methods complement the static methods with run-
time monitoring to improve the scalability and the accuracy of the analysis, but
sacrifice the completeness.
Usually, dynamic typestate analysis approaches, such as runtime verification
[5,11,15,16], automatically convert typestate properties into runtime monitors
that can detect the property violations at runtime. Implementing runtime mon-
itors needs to instrument the monitored programs. The instrumentation can
Corresponding author.
