Debian Codegraph @

examples/SMT-LIB2/bounded model checking/loop_unrolling_bitvec.smt2

raw
1 ; File name: loop_unrolling_bitvec.smt2
2 ;
3 ; Copyright (c) March, 2021 - Matteo Nicoli
4 ;
5 ;
6 ; Let's start considering a simple C program involving an iteration:
7 ;
8 ; #define DIM 2
9 ;
10 ; /* uninterpreted functions */
11 ; long get_number();
12 ; void fill_array(long *A);
13 ;
14 ; int main()
15 ; {
16 ; long x = get_number();
17 ; long A[DIM];
18 ; long i = 0;
19 ; long found = 0;
20 ;
21 ; fill_array(A);
22 ;
23 ; while(i < DIM) {
24 ; if(x == A[i])
25 ; found = 1;
26 ; i++;
27 ; }
28 ; }
29 ;
30 ; Below, we can see its SSA representation in SMT-LIB2.
31 ; Our goal is to verify that, at the end of the program, the variable `found`
32 ; is equal to 1 if, and only if, `x` is an element of the array.
33 ; We define our custom sort `IntValue` that represents a 32-bit integer value.
34
35
36 (define-sort IntValue () (_ BitVec 32))
37 (declare-const x IntValue)
38 (declare-const A (Array IntValue IntValue))
39 (declare-const i_0 IntValue)
40 (declare-const found_0 IntValue)
41
42 (declare-const found_1 IntValue)
43 (declare-const found_2 IntValue)
44 (declare-const i_1 IntValue)
45 (declare-const i_2 IntValue)
46
47 ; Pre-condition: variables initialization
48 (assert
49 (and
50 (= i_0 #x00000000)
51 (= found_0 #x00000000)
52 )
53 )
54
55 ; Transition function
56 (define-fun body ((f_0 IntValue) (f IntValue) (i_0 IntValue) (i_1 IntValue)(_A (Array IntValue IntValue)) (_x IntValue)) Bool
57 (and
58 (= f (ite (= _x (select _A i_0)) #x00000001 f_0))
59 (= i_1 (bvadd i_0 #x00000001))
60 )
61 )
62
63 ; Post-condition function
64 (define-fun post ((_f IntValue) (_i IntValue) (_x IntValue) (_A (Array IntValue IntValue))) Bool
65 (=
66 (= _f #x00000001)
67 (= _x (select _A _i))
68 )
69 )
70
71 ; Transition function is called DIM times:
72 ; for practical reasons, we are considering here DIM = 2
73 (assert (body found_0 found_1 i_0 i_1 A x))
74 (assert (body found_1 found_2 i_1 i_2 A x))
75
76 (push)
77
78 (echo "Bounded model checking with loop unrolling")
79
80 (echo "------------------------------------------")
81
82 ; Post-condition (negated) is called DIM times
83 (assert
84 (not
85 (or
86 (post found_2 i_0 x A)
87 (post found_2 i_1 x A)
88 )
89 )
90 )
91
92 (echo "Testing the validity of the post-condition: `unsat expected`")
93
94 ; `unsat` expected
95 (check-sat)
96
97 (pop)
98
99 ; Post-condition (called DIM times)
100 (assert
101 (or
102 (post found_2 i_0 x A)
103 (post found_2 i_1 x A)
104 )
105 )
106
107 (echo "Getting a model; `sat` expected: ")
108
109 ; `sat` expected
110 (check-sat)
111
112 (echo "------------------------------------------")
113
114 (echo "Model: ")
115 (get-value (x A found_2))
116 (exit)