Verifying Correctness of a Simple Arithmetic Function with Formal Methods in Rust

Formal verification aims to prove the correctness of software by using mathematical methods. This challenge focuses on applying formal verification techniques to a simple arithmetic function in Rust, ensuring it behaves as expected under various conditions. This is crucial for developing reliable software, especially in safety-critical systems where bugs can have severe consequences.

Problem Description

Your task is to implement a function in Rust that calculates (a * b + c) / d. You will then use formal verification techniques to prove that this function meets specific properties. The primary goal is to ensure the function handles potential integer overflow and division by zero gracefully, and that the mathematical result is correct within the constraints of integer arithmetic.

Key Requirements:

1. Implement the Function: Create a Rust function calculate_arithmetic(a: i64, b: i64, c: i64, d: i64) -> Result<i64, ArithmeticError> that computes (a * b + c) / d.
2. Handle Errors: The function should return an ArithmeticError for the following conditions:
   • Division by zero (d == 0).
   • Integer overflow during the multiplication a * b.
   • Integer overflow during the addition (a * b) + c.
   • Integer overflow during the division, if applicable (though less common with i64).
3. Formal Verification: Use a Rust formal verification tool (e.g., creusot, prusti) to write specifications and prove that your function satisfies them. The specifications should cover:
   • Non-division by zero: The function never returns a successful result if d is zero.
   • Correctness of calculation: For valid inputs (where no overflow occurs and d != 0), the returned value is mathematically equivalent to (a * b + c) / d using standard integer division.
   • Overflow detection: The function returns an error if overflow occurs during intermediate calculations.

Expected Behavior:

• If d is 0, the function should return Err(ArithmeticError::DivisionByZero).
• If a * b overflows i64, the function should return Err(ArithmeticError::Overflow).
• If (a * b) + c overflows i64, the function should return Err(ArithmeticError::Overflow).
• If no errors occur, the function should return Ok(result), where result is the computed value.

Examples

Example 1:

Input: a = 2, b = 3, c = 4, d = 2
Output: Ok(5)
Explanation: (2 * 3 + 4) / 2 = (6 + 4) / 2 = 10 / 2 = 5. No overflow or division by zero occurs.

Example 2:

Input: a = 1000000000000000000, b = 2, c = 1, d = 1
Output: Err(ArithmeticError::Overflow)
Explanation: The multiplication `a * b` will overflow the i64 type.

Example 3:

Input: a = 1, b = 1, c = 1, d = 0
Output: Err(ArithmeticError::DivisionByZero)
Explanation: The divisor `d` is zero.

Example 4:

Input: a = 9223372036854775807, b = 1, c = 1, d = 1
Output: Err(ArithmeticError::Overflow)
Explanation: The addition `a * b + c` (which is `9223372036854775807 + 1`) will overflow the i64 type.

Constraints

• The inputs a, b, c, and d are of type i64.
• The function should not panic. All error conditions must be handled via Result.
• The formal verification tool must be able to successfully prove the specified properties for your implementation.
• The implementation of the arithmetic calculation should be as straightforward as possible, relying on Rust's built-in checked arithmetic operations.

Notes

• You will need to choose and set up a formal verification tool for Rust. creusot and prusti are popular choices. Familiarize yourself with the syntax and capabilities of your chosen tool.
• Focus on how to express pre-conditions, post-conditions, and invariants using the formal verification tool's constructs.
• Consider using Rust's checked_mul, checked_add, and checked_div methods, which return Option and can help in detecting overflows. You will then need to map these Option results to your ArithmeticError enum.
• The goal is not just to make the code work, but to prove that it works under the defined conditions.
• The verification process might involve refining your implementation based on what the verifier can and cannot prove.