Optimizing Nop-shadows Typestate Analysis by Filtering Interferential Configurations - Runtime Verification - page 280

Tabl e 2. Results of the optimized NSA
Property + Program BN AN Opt1 Opt2 Both
FailSafeEnum + fop 5 5 5 0 0
FailSafeEnum + jython 47 44 44 36 36
FailSafeEnumHT + jython 76 76 76 72 72
FailSafeIter + bloat 1010 916 911 905 899
FailSafeIter + chart 158 150 150 120 120
FailSafeIter + jython 119 115 115 105 105
FailSafeIter + luindex 30 15 15 0 0
FailSafeIter + pmd 305 290 290 262 262
FailSafeIterMap + bloat 481 479 476 479 476
FailSafeIterMap + jython 153 133 133 119 119
FailSafeIterMap + pmd 372 262 262 260 260
Writer + antlr 44 35 34 35 34
Writer + bloat 19 11 9 11 9
BN : The number of shadows that remain before the original NSA. AN :The
number of shadows that remain after the original NSA. Opt1 :Thenumberof
shadows that remain after the first optimization. Opt2 : The number of shadows
that remain after the second optimization. Both : The number of shadows that
remain after the combination of two optimizations.
individually, the combination can identify one more “nop shadow” in this case.
The reason is: after the original NSA, the second optimization firstly removes
some shadows from the instrumented program, so the first optimization gener-
ates less configurations and can identify one more “nop shadow” under the same
configuration limit. In addition, there are three cases where local object opti-
mization cannot remove any “nop shadow” but the other one can, which also
justifies that the two optimizations complement each other.
5.2 Analysis Time
The analysis time of NSA is mainly dominated by the prior supporting analyses,
such as constructing call graphs and computing points-to information. Because
we evaluate each optimization by using NSA first and then the optimized NSA,
the analysis time for evaluating each optimization is definitely longer than that
of the original NSA. Table 3 displays the results of the analysis time of the cases
on which our optimizations have effects.
From the experimental results, it can be justified that the time for NSA is
just a small part of the total compilation time. In all cases but two, the total
compilation time including our optimizations is under 10 minutes. The average
analysis time of the original NSA is under 1 minute, though in some cases it
needs a few more minutes, such as FailSafeIter + bloat . In some cases, the
analysis time for the optimized analysis is less than that of the original NSA.
One of the key reasons is that the optimized NSA analyzes less shadows. For