Formal Verification of a Simple Arithmetic Expression in Rust

Formal verification aims to mathematically prove the correctness of a program. This challenge introduces you to the basics of formal verification in Rust using the prover crate, focusing on verifying a simple arithmetic expression. You'll define a function that calculates the result of an expression and then use prover to prove that the function always returns a non-negative result, regardless of the input.

Problem Description

You are tasked with implementing a function safe_add that takes two integer arguments, a and b, and returns their sum. The goal is to formally verify that safe_add always returns a non-negative result. This means proving that safe_add(a, b) >= 0 for all possible integer values of a and b within a defined range. You will use the prover crate to achieve this. The verification process involves annotating your code with preconditions and postconditions, and then running the prover to check if the annotations hold true.

Key Requirements:

• Implement the safe_add function.
• Annotate the function with preconditions and postconditions using prover attributes.
• Ensure the verification process completes successfully without errors.
• The verification should prove that the function always returns a non-negative result.

Expected Behavior:

The safe_add function should correctly calculate the sum of two integers. The formal verification process should confirm that the sum is always non-negative, given the constraints.

Edge Cases to Consider:

• Integer overflow: While the prover handles overflow, it's good to be aware of it. The constraints will limit the input range to avoid overflow issues.
• Negative inputs: The verification should hold true even when both inputs are negative, as long as their sum remains non-negative within the specified range.
• Zero inputs: The verification should also hold true when one or both inputs are zero.

Examples

Example 1:

Input: a = 5, b = 3
Output: 8
Explanation: 5 + 3 = 8, which is non-negative.

Example 2:

Input: a = -2, b = 5
Output: 3
Explanation: -2 + 5 = 3, which is non-negative.

Example 3:

Input: a = -5, b = -3
Output: -8
Explanation: -5 + -3 = -8, which violates the non-negative constraint.  The prover should catch this if the range is not properly constrained.

Constraints

• The input integers a and b will be within the range of i16. This range is chosen to keep the verification process manageable.
• The prover crate must be used for formal verification.
• The verification process must complete successfully without errors.
• The function must be named safe_add.
• The function signature must be fn safe_add(a: i16, b: i16) -> i16.

Notes

• You'll need to add the prover crate to your Cargo.toml file.
• The prover crate uses attributes to specify preconditions and postconditions. Refer to the prover documentation for details on how to use these attributes.
• Start with a simple implementation of safe_add and then gradually add the annotations.
• The key to success is carefully defining the preconditions and postconditions to accurately reflect the desired behavior of the function. Consider the range of inputs and the expected output.
• The prover might require you to specify the type of the result in the postcondition.
• The prover crate might require you to enable specific features in your Cargo.toml file. Consult the crate's documentation for details.