Research: explicit SMT assertions for non-linear arithmetic

[0xkarmacoma]

Problem

Non-linear arithmetic on bitvectors is very expensive for SMT solvers. Simple queries take a very long time to complete, for instance:

from z3 import *

x = BitVec('x', 256)
y = BitVec('y', 256)

# takes 7s to return [y = 0, x = 1]
solve(Not(ULT(UDiv(x, y), x)))

# takes 1m30s to return unsat (no solution)
solve(ULT(x, y), UDiv(x, y) > 0)

As a result, the equivalent tests in halmos also take a long time:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.15;

contract DivisionIsHard {
    /// @notice we expect a counterexample [y = 0, x = 1]
    function check_divRoundsDown(uint256 x, uint256 y) external {
        assert(x / y < x);
    }

    /// @notice we expect unsat (no counterexample)
    function check_divRoundsToZero(uint256 x, uint256 y) external {
        require(x < y);
        assert(x / y == 0);
    }
}

(run with halmos --solver-timeout-assertion 0 --statistics)

Let's break down how halmos processes check_divRoundsDown:

• halmos starts with an uninterpreted function (evm_bvudiv) to avoid the cost of bitvector division
• halmos finds a path that could trigger the assertion violation, asks the solver for a model
• the solver returns an invalid model since it contains evm_bvudiv (i.e. it doesn't know that we're asking about the actual division operation)
• halmos refines the query (aka replaces the UF evm_bvudiv with the real bvudiv operator) and asks the solver again
• the solver returns a valid counterexample (x = 0, y = 1), but takes a while to do so

Proposed solution

This test is simple enough that it can be solved without refinement, i.e. no need to do any actual bitvector division.

We could explicitly tell the solver some properties of evm_bvudiv that are sufficient to return a counterexample:

    def mk_div(self, ex: Exec, x: Any, y: Any) -> Any:
        term = f_div(x, y)
        ex.path.append(ULE(term, x))  # (x / y) <= x

        # y == 0 implies (x / y) == 0
        ex.path.append(Implies(y == con(0), term == con(0)))

        # y == 1 implies (x / y) == x
        ex.path.append(Implies(y == con(1), term == x))

        # y > 1 implies (x / y) < x
        ex.path.append(Implies(ULT(con(1), y), ULT(term, x)))

        # y > x implies (x / y) == 0
        ex.path.append(Implies(ULT(x, y), term == con(0)))

        return term

In this case, the key assertion is y == 1 implies (x / y) == x. With this, the test returns a valid result immediately and does not require refining the query.

Work to do

• find interesting axioms to add (for div, mul, mod, sdiv, ...)
• study the power of the added axioms (are we able to solve more tests?)
• study the performance trade-off (are we solving real problems faster? is adding many assertions making the query too big?)
• study the performance trade-off for a couple of solvers: the effect could be different on z3 vs boolector, cvc5, etc.
• is it possible to do better than eagerly adding assertions for all operations?

Related

Hozzová, Petra, et al. "Overapproximation of Non-Linear Integer Arithmetic for Smart Contract Verification." Proceedings of 24th International Conference on Logic. Vol. 94. 2023.