Debian Codegraph @

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

raw
1 ; File name: loop_unrolling.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
34
35 (declare-const x Int)
36 (declare-const A (Array Int Int))
37 (declare-const i_0 Int)
38 (declare-const found_0 Int)
39
40 (declare-const found_1 Int)
41 (declare-const found_2 Int)
42 (declare-const i_1 Int)
43 (declare-const i_2 Int)
44
45 ; Pre-condition: variables initialization
46 (assert
47 (and
48 (= i_0 0)
49 (= found_0 0)
50 )
51 )
52
53 ; Transition function
54 (define-fun body ((f_0 Int) (f Int) (i_0 Int) (i_1 Int)(_A (Array Int Int)) (_x Int)) Bool
55 (and
56 (= f (ite (= _x (select _A i_0)) 1 f_0))
57 (= i_1 (+ i_0 1))
58 )
59 )
60
61 ; Post-condition function
62 (define-fun post ((_f Int) (_i Int) (_x Int) (_A (Array Int Int))) Bool
63 (=
64 (= _f 1)
65 (= _x (select _A _i))
66 )
67 )
68
69 ; Transition function is called DIM times:
70 ; for practical reasons, we are considering here DIM = 2
71 (assert (body found_0 found_1 i_0 i_1 A x))
72 (assert (body found_1 found_2 i_1 i_2 A x))
73
74 (push)
75
76 (echo "Bounded model checking with loop unrolling")
77
78 (echo "------------------------------------------")
79
80 ; Post-condition (negated) is called DIM times
81 (assert
82 (not
83 (or
84 (post found_2 i_0 x A)
85 (post found_2 i_1 x A)
86 )
87 )
88 )
89
90 (echo "Testing the validity of the post-condition: `unsat expected`")
91
92 ; `unsat` expected
93 (check-sat)
94
95 (pop)
96
97 ; Post-condition (called DIM times)
98 (assert
99 (or
100 (post found_2 i_0 x A)
101 (post found_2 i_1 x A)
102 )
103 )
104
105 (echo "Getting a model; `sat` expected: ")
106
107 ; `sat` expected
108 (check-sat)
109
110 (echo "------------------------------------------")
111
112 (echo "Model: ")
113 (get-value (x A found_2))
114 (exit)