Path-Aware Static Program Analyses for Specification Mining* - Mining Software Specifications: Methodologies and Applications - page 311

to the sequence of statements in a program (e.g., s1,s2,s4 is a path in the
program shown below). In realistic programs, there are potentially many paths
(e.g., there are four paths in the program shown below). Any program analysis
technique that takes paths into account is considered to be path-aware.
voidmain(intargc,char*argv[]) f
/*assume argv[0]="prog" */
intx;
char*str=NULL;
if(argc>2) f
str=(char*)malloc(strlen(argv[2])+1);
strcpy(str,argv[2]);/*s1*/
g
x=atoi(argv[1]);
if(x>0)
write(1,"positive",9);/*s2*/
else
write(1,"notpositive",13);/*s3*/
write(1,str,strlen(str));/*s4*/
g
To see why path-awareness is important for deriving useful specifica-
tions and localizing specification violations, consider the code fragment shown
above, which takes two arguments and characterizes the first argument as pos-
itive( s2 ) or not positive( s3 ) and simply prints( s4 ) the second argument after
storing( s1 ) it in a local variable str . The above fragment is obviously er-
roneous (at statement s4 ) if there is exactly one argument provided. Any
analysis technique that considers statement s4 in the context of statement s1
not being executed can only conclude the error associated with statement s4 .
If we define a simple analysis to detect whether str is assigned some value
before statement s4 after the NULL assignment, a path-unaware analysis will
collect all the statements preceding statement s4 and detect the assignment at
statement s1 . Conversely, a path-aware analysis will consider each program
path separately and determine that str is not assigned a value always. It
is this precision associated with path-aware analysis that dictates improved
accuracy with respect to software reliability.
9.1.2 Dynamic versus Static Path Generation
Even when a program analysis is path-aware, the paths analyzed can be
generated dynamically or statically. Dynamic path-aware analyses work by
running a program on a set of test inputs, deriving traces of the execution,
subsequently analyzing these traces to determine salient properties. In a static
analysis, the program source is analyzed to determine the properties of the
program. While dynamic analysis is precise with respect to the data analyzed,
the quality of the analysis is critically dependent on the completeness of the
test inputs. On the other hand, static analysis is totally independent of the test
inputs. However, due to program abstractions, static analysis cannot always
provide the same precision as dynamic analysis.