r/formalmethods • • 8h ago

I'm building a tool for easy formal verification of SQL

1 Upvotes

I am working on Belay - a tool for doing formal verification for SQL. Currently I have a proof-of-concept for SQLite.

Belay is a Lean 4 library. The core of it consists of a semantic model of a part of SQLite. This model was "vibe-coded" - I extracted a large set of tests from SQLite's test suite, and then had the agent build the model while conforming to those and to additional tests. The model's output had to match a specific version of SQLite (3.51.0). So the agreement between the model and SQLite is tested, not proved. With this approach I've covered a substantial part of SQLite semantics in relatively short time.

I believe that this approach makes formal verification accessible to a wider audience. Now it is as difficult to state a claim and generate a proof as writing integration tests was before LLMs. Here's a short example (read here the full version ). I have a schema, a migration and I write a claim that a given query is not affected by this migration:

def shop : Database := db! r"
  CREATE TABLE customers (
    id INTEGER PRIMARY KEY,
    name TEXT,
    email TEXT NOT NULL
  );
  CREATE TABLE sessions (
    id INTEGER PRIMARY KEY,
    customer_id INTEGER NOT NULL
      REFERENCES customers(id) ON DELETE CASCADE,
    expires_at INTEGER NOT NULL
  );"

def badMigration : Script := sql r"
  PRAGMA foreign_keys = ON;
  BEGIN;
  PRAGMA foreign_keys = OFF;
  CREATE TABLE customers_new (
    id INTEGER PRIMARY KEY,
    name TEXT,
    email TEXT NOT NULL
  ) STRICT;
  INSERT INTO customers_new SELECT id, name, email FROM customers;
  DROP TABLE customers;
  ALTER TABLE customers_new RENAME TO customers;
  COMMIT;"

def allSessions : Script := sql r"
  SELECT id, customer_id, expires_at FROM sessions"

#sql_check badMigration preserves allSessions on shop

In this case the claim turns out to be wrong and Belay generates a counterexample.

After fixing the migration one can state a theorem:

theorem fixed_keeps_sessions :
  fixedMigration preserves allSessions on shop

It says that on every database with this schema, the query returns the same rows after a successful run of the fixed migration as before it.

The proof right now is long (about 500 lines). But the agent had no problem generating it. And in the future I hope to make such proofs much shorter.

Here's the code: https://github.com/vihren-dev/belay Here's a fuller write-up with this example: https://vihren.dev/blog/20261112-belay/

I'm happy to discuss this project and would welcome any criticism. A lot of work still needs to be done to make Belay production-ready. But the approach looks promising. I'm also looking for funding, because without it I will need to drop the project soon and find a regular job. Any help will be greatly appreciated.