验证无无符号整数回绕

Question

Frama-c 似乎允许无符号整数数学回绕，同时它假定有符号整数数学不会溢出，这需要稍后用 -wp-rte 标志来证明。（我个人使用的是 Frama-C 20.0 Calcium。）我想以某种方式创建一个 assurance/requirement，一些 calculation/property 不会溢出。我要处理的问题的简化版本是：

#include <stdint.h>

struct example_struct {
  unsigned int a;
  unsigned int b;
};

/*@
  predicate valid_example_struct_one{L}(struct example_struct ex_struct) =
    ex_struct.a * ex_struct.b <= UINT_MAX;
*/

显然，由于无符号整数数学上的回绕，上述谓词始终为真。我希望能够将 a 和 b 转换为不会溢出的整数类型，或者以某种方式指定它不能使用另一种方法溢出。以下似乎有点工作：

/*@
  predicate valid_example_struct_two{L}(struct example_struct ex_struct) =
    1 <= UINT_MAX / ex_struct.a / ex_struct.b;
*/

但是，我不确定上面是否真的等价，因为它很难证明（注意交换的 a 和 b）：

  1 <= UINT_MAX / ex_struct.b / ex_struct.a;

如果我要求它与被告知的输入一起支持谓词 valid_example_struct_two。有没有人建议说 a * b 小于 UINT_MAX（不做回绕）？

Answer 1

你的谓词

/*@
  predicate valid_example_struct_one{L}(struct example_struct ex_struct) =
    ex_struct.a * ex_struct.b <= UINT_MAX;
*/

不是 "always true due to wrap-around on unsigned integer math"。正如 ACSL 手册中提到的，ACSL 中的所有算术运算都是在 integer（或 real）类型中完成的，即没有环绕。因此，它是表示不存在算术溢出的规范方式，也是 RTE 和 Eva 在发出相关警报时使用的方式。

就是说，RTE 完全能够为无符号溢出发出断言，但这必须使用内核选项 -warn-unsigned-overflow 显式激活（参见 Frama-C user manual，第 6.3 节。此选项的原因默认情况下未激活的是，与例如有符号溢出相反，无符号溢出在 C 中具有完美定义的语义

验证无无符号整数回绕

Verifying no unsigned integer wrap-around

frama-c