Download Paper - STS

Transcript
3 Data Flow Analyses for Bidirectional Predicate Propagation
1
2
3
4
void main ( int x , int y )
{
int h ;
a[] = 0, 1, 2, 3, 4 1
const int a [ ] = { 0 , 1 , 2 ,
3 , 4};
5
/∗@ a s s e r t r t e :
{0 ≤ x,
h = a[x] 2
index bound : 0 ≤ x ;
x < 5}
∗/
6
/∗@ a s s e r t r t e :
i n d e x b o u n d : x < 5 ; ∗/
{y 6= 0}
h = 1/y 3
7
h = a[x];
8
/∗@ a s s e r t r t e :
d i v i s i o n b y z e r o : y 6=
{a[x] 6= 0,
0 ; ∗/
0 ≤ x,
h = 1/a[x] 4
9
h = 1 / y;
x < 5}
10
/∗@ a s s e r t r t e :
division by zero : a[ x ]
6= 0 ; ∗/
x=y5
11
/∗@ a s s e r t r t e :
index bound : 0 ≤ x ;
∗/
{y 6= 0}
h = 1/y 6
12
/∗@ a s s e r t r t e :
i n d e x b o u n d : x < 5 ; ∗/
13
h = 1/ a [ x ] ;
14
x = y;
Figure 3.1: CFG of the Example with Dif15
/∗@ a s s e r t r t e :
ferent Kinds of Warnings
d i v i s i o n b y z e r o : y 6=
0 ; ∗/
16
h = 1 / y;
17
return ;
18
}
Listing 3.1: Example with Different Kinds
of Warnings
Figure 3.1 shows the CFG of the code in Listing 3.1. In addition to the CFG, we also
have the predicates that are asserted in the warnings corresponding to the statements in
Figure 3.1. In this example, we have multiple warnings attached to one statement for the
first time. The fourth statement, for example, has three warnings attached to it, two of
them are array-index-out-of-bounds warnings. One states that x has to be greater than
or equal to zero. The other warning states that x has to be smaller than five. Otherwise,
an array-index-out-of-bounds error occurs. In addition to these warnings, we also have
a division-by-zero warning stating that a[x] 6= 0 has to hold.
28