Source file rte.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
open Cil_types
type 'a alarm_gen =
remove_trivial:bool ->
on_alarm:(invalid:bool -> Alarms.alarm -> unit) ->
'a -> unit
type bound_kind = Alarms.bound_kind = Lower_bound | Upper_bound
let get_expr_val expr = Cil.constFoldToInt expr
let valid_index ~remove_trivial ~on_alarm e size =
let alarm bk =
let b = match bk with
| Lower_bound -> None
| Upper_bound -> Some size
in
if not (bk == Upper_bound && Cil.isZero size) then begin
on_alarm ~invalid:false (Alarms.Index_out_of_bound(e, b))
end
in
if remove_trivial then begin
let v_e = get_expr_val e in
let v_size = get_expr_val size in
let neg_ok =
Option.fold ~none:false ~some:(Z.leq Z.zero) v_e
|| Cil.isUnsignedInteger (Cil.typeOf e)
in
if not neg_ok then alarm Lower_bound;
let pos_ok = match v_e, v_size with
| Some v_e, Some v_size -> Z.lt v_e v_size
| None, _ | _, None -> false
in
if not pos_ok then alarm Upper_bound
end else begin
alarm Lower_bound;
alarm Upper_bound;
end
let lval_assertion ~read_only ~remove_trivial ~on_alarm lv =
let rec check_array_access default off typ in_struct =
match off with
| NoOffset ->
if default then
on_alarm ~invalid:false (Alarms.Memory_access(lv, read_only))
| Field (fi, off) ->
check_array_access default off fi.ftype true
| Index (e, off) ->
match Ast_types.unroll_node typ with
| TArray (bt, Some size) ->
if Kernel.SafeArrays.get () || not in_struct then begin
valid_index ~remove_trivial ~on_alarm e size;
check_array_access default off bt in_struct
end else
check_array_access true off bt in_struct
| TArray (bt, None) -> check_array_access true off bt in_struct
| _ -> assert false
in
match lv with
| Var vi , off -> check_array_access false off vi.vtype false
| (Mem _ as lh), off ->
if not (Ast_types.is_fun (Cil.typeOfLval lv)) then
check_array_access true off (Cil.typeOfLhost lh) false
let lval_initialized_assertion ~remove_trivial:_ ~on_alarm lv =
let typ = Cil.typeOfLval lv in
match lv with
| Var vi, NoOffset ->
if not (vi.vglob || vi.vformal || vi.vtemp)
&& not (Ast_types.is_struct_or_union typ)
then
on_alarm ~invalid:false (Alarms.Uninitialized lv)
| _ ->
if not Ast_types.(is_fun typ || is_struct_or_union typ) then
on_alarm ~invalid:false (Alarms.Uninitialized lv)
let uminus_assertion ~remove_trivial ~on_alarm exp =
let t = Ast_types.unroll (Cil.typeOf exp) in
let size = Cil.bitsSizeOf t in
let min_ty = Cil.min_signed_number size in
let bound = Z.succ min_ty in
let alarm ?(invalid=false) () =
let a = Alarms.Overflow(Alarms.Signed, exp, bound, Lower_bound) in
on_alarm ~invalid a
in
if remove_trivial then begin
match get_expr_val exp with
| None -> alarm ()
| Some a64 ->
if Z.equal a64 min_ty then
alarm ~invalid:true ()
end
else alarm ()
let mult_sub_add_assertion ~signed ~remove_trivial ~on_alarm (exp,op,lexp,rexp) =
let t = Ast_types.unroll (Cil.typeOf exp) in
let size = Cil.bitsSizeOf t in
let min_ty, max_ty =
if signed then Cil.min_signed_number size, Cil.max_signed_number size
else Z.zero, Cil.max_unsigned_number size
in
let alarm ?(invalid=false) bk =
let bound = match bk with
| Upper_bound -> max_ty
| Lower_bound -> min_ty
in
let signed = if signed then Alarms.Signed else Alarms.Unsigned in
on_alarm ~invalid (Alarms.Overflow (signed, exp, bound, bk));
in
let alarms () =
alarm Lower_bound;
alarm Upper_bound;
in
if remove_trivial then begin
match get_expr_val lexp, get_expr_val rexp, op with
| Some l, Some r, _ ->
let warn r =
let warn bk = alarm ~invalid:true bk in
if Z.gt r max_ty then warn Upper_bound
else if Z.lt r min_ty then warn Lower_bound
in
(match op with
| MinusA -> warn (Z.sub l r)
| PlusA -> warn (Z.add l r)
| Mult -> warn (Z.mul l r)
| _ -> assert false)
| _, Some v , PlusA | Some v, _, PlusA ->
if Z.(gt v zero) then alarm Upper_bound
else if Z.(lt v zero) then alarm Lower_bound
| _, Some r , MinusA ->
if Z.(gt r zero) then alarm Lower_bound
else if Z.(lt r zero) then alarm Upper_bound
| Some l, None , MinusA ->
if signed then begin
if Z.(gt l minus_one) then alarm Upper_bound
else if Z.(lt l minus_one) then alarm Lower_bound
end
else begin
alarm Lower_bound
end
| Some v, None, Mult | None, Some v, Mult
when Z.is_zero v || Z.is_one v -> ()
| None, None, _ | Some _, None, _ | None, Some _, _ -> alarms ()
end
else alarms ()
let divmod_assertion ~remove_trivial ~on_alarm divisor =
let alarm ?(invalid=false) () =
on_alarm ~invalid (Alarms.Division_by_zero divisor);
in
if remove_trivial then begin
match get_expr_val divisor with
| None ->
alarm ();
| Some v64 ->
if Z.is_zero v64 then
alarm ~invalid:true ()
end
else alarm ()
let signed_div_assertion ~remove_trivial ~on_alarm (exp, lexp, rexp) =
let t = Ast_types.unroll (Cil.typeOf rexp) in
let size = Cil.bitsSizeOf t in
let max_ty = Cil.max_signed_number size in
let alarm ?(invalid=false) () =
let a = Alarms.Overflow(Alarms.Signed, exp, max_ty, Alarms.Upper_bound) in
on_alarm ~invalid a;
in
if remove_trivial then begin
let min = Cil.min_signed_number size in
match get_expr_val lexp, get_expr_val rexp with
| Some e1, _ when not (Z.equal e1 min) ->
()
| _, Some e2 when not (Z.equal e2 Z.minus_one) ->
()
| Some _, Some _ ->
alarm ~invalid:true ()
| None, Some _ | Some _, None | None, None ->
alarm ()
end
else alarm ()
let shift_assertion ~remove_trivial ~on_alarm (exp, upper_bound) =
let alarm ?(invalid=false) () =
let a = Alarms.Invalid_shift(exp, upper_bound) in
on_alarm ~invalid a ;
in
if remove_trivial then begin
match get_expr_val exp with
| None -> alarm ()
| Some c64 ->
let upper_bound_ok = match upper_bound with
| None -> true
| Some u -> Z.lt c64 (Z.of_int u)
in
if not (Z.geq c64 Z.zero && upper_bound_ok) then
alarm ~invalid:true ()
end
else alarm ()
let shift_width_assertion ~remove_trivial ~on_alarm (exp, typ) =
let size = Cil.bitsSizeOf typ in
shift_assertion ~remove_trivial ~on_alarm (exp, Some size)
let shift_negative_assertion ~remove_trivial ~on_alarm exp =
shift_assertion ~remove_trivial ~on_alarm (exp, None)
let shift_overflow_assertion ~signed ~remove_trivial ~on_alarm (exp, op, lexp, rexp) =
let t = Ast_types.unroll (Cil.typeOf exp) in
let size = Cil.bitsSizeOf t in
if size <> Cil.bitsSizeOf (Cil.typeOf lexp) then
Options.warning ~current:true ~once:true
"problem with bitsSize of %a: not treated" Printer.pp_exp exp;
if op = Shiftlt then
let maxValResult =
if signed
then Cil.max_signed_number size
else Cil.max_unsigned_number size
in
let overflow_alarm ?(invalid=false) () =
let signed = if signed then Alarms.Signed else Alarms.Unsigned in
let a = Alarms.Overflow (signed, exp, maxValResult, Alarms.Upper_bound) in
on_alarm ~invalid a;
in
if remove_trivial then begin
match get_expr_val lexp, get_expr_val rexp with
| None,_ | _, None ->
overflow_alarm ()
| Some lval64, Some rval64 ->
if Z.(rval64 >= zero && (shift_left_z lval64 rval64) >= maxValResult)
then
overflow_alarm ~invalid:true ()
end
else overflow_alarm ()
let downcast_assertion ~remove_trivial ~on_alarm (dst_type, exp) =
let src_type = Cil.typeOf exp in
let src_signed = Cil.isSignedInteger src_type in
let dst_signed = Cil.isSignedInteger dst_type in
let src_size = Cil.bitsSizeOf src_type in
let dst_size = Cil.bitsSizeOfBitfield dst_type in
if (dst_size < src_size || dst_size == src_size && dst_signed <> src_signed)
&& not Ast_types.(is_ptr src_type && (is_intptr_t dst_type || is_uintptr_t dst_type))
then
let dst_min, dst_max =
if dst_signed
then Cil.min_signed_number dst_size, Cil.max_signed_number dst_size
else Z.zero, Cil.max_unsigned_number dst_size
in
let overflow_kind =
if Ast_types.is_ptr src_type
then Alarms.Pointer_downcast
else if dst_signed
then Alarms.Signed_downcast
else Alarms.Unsigned_downcast
in
let alarm ?(invalid=false) bound bound_kind =
let a = Alarms.Overflow (overflow_kind, exp, bound, bound_kind) in
on_alarm ~invalid a;
in
let alarms () =
alarm dst_max Upper_bound;
if src_signed then alarm dst_min Lower_bound;
in
match remove_trivial, get_expr_val exp with
| true, Some a64 ->
let invalid = true in
if Z.lt a64 dst_min then alarm ~invalid dst_min Lower_bound
else if Z.gt a64 dst_max then alarm ~invalid dst_max Upper_bound
| _ -> alarms ()
let float_to_int_assertion ~remove_trivial ~on_alarm (ty, exp) =
let e_typ = Ast_types.unroll (Cil.typeOf exp) in
match e_typ.tnode, ty.tnode with
| TFloat _, TInt ikind ->
let signed = Cil.isSigned ikind in
let size = Cil.bitsSizeOfBitfield ty in
let largest = Cil.max_unsigned_number size in
let max_ty = if signed then Cil.max_signed_number size else largest in
let min_ty = if signed then Cil.min_signed_number size else Z.zero in
let bound = function Lower_bound -> min_ty | Upper_bound -> max_ty in
let build_alarm b = Alarms.Float_to_int (exp, bound b, b) in
let alarm ?(invalid = false) b = on_alarm ~invalid (build_alarm b) in
let number =
match exp.enode with
| Const (CReal (f, fk, _)) -> Some (f, fk)
| UnOp (Neg, { enode = Const (CReal (f, fk, _)) }, _) -> Some (-. f, fk)
| _ -> None
in
begin match remove_trivial, number with
| false, _ | true, None -> alarm Upper_bound ; alarm Lower_bound
| true, Some (f, _) ->
match Floating_point.truncate_to_integer f with
| Underflow -> alarm Lower_bound
| Overflow -> alarm Upper_bound
| Integer i when Z.lt i min_ty -> alarm ~invalid:true Lower_bound
| Integer i when Z.gt i max_ty -> alarm ~invalid:true Upper_bound
| Integer _ -> ()
end
| _ -> ()
let finite_float_assertion ~remove_trivial:_ ~on_alarm (fkind, exp) =
let invalid = false in
match Kernel.SpecialFloat.get () with
| "none" -> ()
| "nan" -> on_alarm ~invalid (Alarms.Is_nan (exp, fkind))
| "non-finite" -> on_alarm ~invalid (Alarms.Is_nan_or_infinite (exp, fkind))
| _ -> assert false
let pointer_call ~remove_trivial:_ ~on_alarm (e, args) =
on_alarm ~invalid:false (Alarms.Function_pointer (e, Some args))
let rec is_safe_offset = function
| NoOffset -> true
| Field(fi,o) -> fi.fcomp.cstruct && not fi.faddrof && is_safe_offset o
| Index(_,o) -> is_safe_offset o
let is_safe_pointer_value = function
| Lval (Var vi, offset) ->
not vi.vaddrof && is_safe_offset offset
| AddrOf (_, NoOffset) | StartOf (_, NoOffset) -> true
| CastE (_typ, e) ->
let v = get_expr_val e in
Option.fold ~none:false ~some:Z.(equal zero) v
| _ -> false
let pointer_value ~remove_trivial ~on_alarm expr =
if not (remove_trivial && is_safe_pointer_value expr.enode)
then on_alarm ~invalid:false (Alarms.Invalid_pointer expr)
type verdict = Yes | No | Maybe
let trivially_aligned (expr: Cil_types.exp) target =
if Ast_types.is_void target
|| Ast_types.is_fun target
then
Yes
else
let t_align = Cil.bytesAlignOf target in
let expr = Cil.stripCasts expr in
let orig_t = Cil.typeOf expr in
if Ast_types.is_void_ptr orig_t || Ast_types.is_fun_ptr orig_t
then Maybe
else
if Ast_types.is_integral orig_t
then match Cil.constFoldToInt expr with
| None -> Maybe
| Some value when Z.(zero = (value mod of_int t_align)) -> Yes
| _ -> No
else
match expr.enode with
| Lval (Var vi, NoOffset) when not vi.vglob && not vi.vaddrof ->
if t_align <= Cil.bytesAlignOf @@ Ast_types.direct_pointed_type orig_t
then Yes
else Maybe
| AddrOf (Var vi, NoOffset) | StartOf (Var vi, NoOffset) ->
if 0 = Cil.bytesAlignOfVarinfo vi mod t_align
then Yes
else Maybe
| _ ->
Maybe
let pointer_alignment ~remove_trivial ~on_alarm (expr, t) =
assert (Ast_types.is_ptr t) ;
let pointed_to = Ast_types.direct_pointed_type t in
let expr = Cil.stripCasts expr in
match trivially_aligned expr pointed_to with
| Yes ->
if not remove_trivial
then on_alarm ~invalid:false (Alarms.Unaligned_pointer (expr, pointed_to))
| No ->
on_alarm ~invalid:true (Alarms.Unaligned_pointer (expr, pointed_to))
| Maybe ->
on_alarm ~invalid:false (Alarms.Unaligned_pointer (expr, pointed_to))
let bool_value ~remove_trivial ~on_alarm lv =
match remove_trivial, lv with
| true, (Var vi, NoOffset)
when
(not vi.vglob) &&
(not vi.vaddrof)
-> ()
| _ -> on_alarm ~invalid:false (Alarms.Invalid_bool lv)