Optimization Methods for Nop-Shadows Typestate Analysis

Chengsong WANG  Xiaoguang MAO  Yan LEI  Peng ZHANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.6   pp.1213-1227
Publication Date: 2015/06/01
Publicized: 2015/02/23
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7329
Type of Manuscript: PAPER
Category: Dependable Computing
Keyword: 
typestate analysis,  runtime monitoring,  static analysis,  Nop-shadows Analysis,  data-flow analysis,  

Full Text: PDF(1.2MB)>>
Buy this Article




Summary: 
In recent years, hybrid typestate analysis has been proposed to eliminate unnecessary monitoring instrumentations for runtime monitors at compile-time. Nop-shadows Analysis (NSA) is one of these hybrid typestate analyses. Before generating residual monitors, NSA performs the data-flow analysis which is intra-procedural flow-sensitive and partially context-sensitive to improve runtime performance. Although NSA is precise, there are some cases on which it has little effects. In this paper, we propose three optimizations to further improve the precision of NSA. The first two optimizations try to filter interferential states of objects when determining whether a monitoring instrumentation is necessary. The third optimization refines the inter-procedural data-flow analysis induced by method invocations. We have integrated our optimizations into Clara and conducted extensive experiments on the DaCapo benchmark. The experimental results demonstrate that our first two optimizations can further remove unnecessary instrumentations after the original NSA in more than half of the cases, without a significant overhead. In addition, all the instrumentations can be removed for two cases, which implies the program satisfy the typestate property and is free of runtime monitoring. It comes as a surprise to us that the third optimization can only be effective on 8.7% cases. Finally, we analyze the experimental results and discuss the reasons why our optimizations fail to further eliminate unnecessary instrumentations in some special situations.