Using Hegel for OCaml for Antithesis workloads
This is a simple test workload we call the bank test, which checks atomicity and isolation in a SQLite database and a functional correctness property on a model of a bank. Note that some code is omitted for brevity. See Further reading for the full code.
Bank state
Section titled “Bank state”open Hegel
let busy_timeout_ms = 5_000
type config = { accounts : int ; initial_balance : int ; max_amount : int }
type transfer_outcome = | Committed | Insufficient_funds | Unknown
let string_of_outcome = function | Committed -> "Committed" | Insufficient_funds -> "Insufficient_funds" | Unknown -> "Unknown";;
type t = { dir : string ; path : string ; mutex : Mutex.t ; mutable idle : Sqlite3.db list ; config : config ; attempted : int Atomic.t ; committed : int Atomic.t ; total : int }busy_timeout_ms is how long a connection waits on a locked database before it fails with SQLITE_BUSY.
The database has one accounts table with an account_id, a balance and an opCount for each account.
The database runs in WAL mode, which allows non-blocking reads while transfers are executing, and each read sees a consistent snapshot. Since writers are serialized, transfers must take the write lock first with BEGIN IMMEDIATE.
config sets the number of accounts, the starting balance of each account, and the largest transfer amount.
Transfers can have one of the following outcomes (transfer_outcome):
Committed:COMMITreturned successfully.Insufficient_funds: the transaction was rolled back because the source balance was too low.Unknown: SQLite returned an error, such asSQLITE_BUSY. The client does not know if the transaction committed.
The test state t consists of the database path, a pool of idle connections, counts of attempted and committed transfers, and the total balance. Mutable fields of t are
atomic or guarded by a mutex since they may be modified
concurrently.
Database helpers
Section titled “Database helpers”let step db sql ?(params = []) () = ...
let int n = Sqlite3.Data.INT (Int64.of_int n)let select_int db sql ?params () = Option.get (step db sql ?params ())let execute db sql ?params () = ignore (step db sql ?params ())
let open_db path = ...
let with_db path f = let db = open_db path in Fun.protect ~finally:(fun () -> ignore (Sqlite3.db_close db)) (fun () -> f db);;step prepares a SQL statement, binds its parameters, runs it, and returns the first column of the first row or None if there is no row. select_int returns the integer from a query. execute executes a statement and throws away the resulting value. open_db opens a connection with the busy timeout set, and with_db opens a connection, runs a function on it, and closes the connection.
let init config = let dir = Filename.temp_dir "sqlite_bank" "" in let path = Filename.concat dir "bank.sqlite3" in with_db path (fun db -> execute db "PRAGMA journal_mode = WAL" (); execute db "PRAGMA synchronous = FULL" (); execute db "CREATE TABLE accounts (account_id INTEGER PRIMARY KEY, balance INTEGER NOT NULL, \ opCount INTEGER NOT NULL)" (); execute db "BEGIN" (); for id = 0 to config.accounts - 1 do execute db "INSERT INTO accounts (account_id, balance, opCount) VALUES (?, ?, 0)" ~params:[ int id; int config.initial_balance ] () done; execute db "COMMIT" ()); { dir ; path ; mutex = Mutex.create () ; idle = [] ; config ; attempted = Atomic.make 0 ; committed = Atomic.make 0 ; total = config.accounts * config.initial_balance };;
let close t = List.iter (fun db -> ignore (Sqlite3.db_close db)) t.idle; t.idle <- []; Array.iter (fun file -> Sys.remove (Filename.concat t.dir file)) (Sys.readdir t.dir); Sys.rmdir t.dir;;
let with_bank config f = let bank = init config in Fun.protect ~finally:(fun () -> close bank) (fun () -> f bank);;
let with_conn t f = ...;;init creates the database in a temporary directory, switches it to WAL mode, and creates the accounts table with one row per account. Each account starts with the initial balance and an opCount of 0. init also records the expected total accounts * initial_balance. close closes the connections in the connection pool and deletes the database files.
with_bank wraps a function in init and close. with_conn takes an idle connection from the pool or opens a new one if the pool is empty, and returns it to the pool when the function returns.
Transfers
Section titled “Transfers”let transfer t ~source ~dest ~amount = Atomic.incr t.attempted; let transaction db = execute db "BEGIN IMMEDIATE" (); try let balance = select_int db "SELECT balance FROM accounts WHERE account_id = ?" ~params:[ int source ] () in if balance < amount then ( execute db "ROLLBACK" (); Insufficient_funds) else ( execute db "UPDATE accounts SET balance = balance - ?, opCount = opCount + 1 WHERE \ account_id = ?" ~params:[ int amount; int source ] (); execute db "UPDATE accounts SET balance = balance + ?, opCount = opCount + 1 WHERE \ account_id = ?" ~params:[ int amount; int dest ] (); execute db "COMMIT" (); Committed) with | exn -> let backtrace = Printexc.get_raw_backtrace () in ignore (Sqlite3.exec db "ROLLBACK"); Printexc.raise_with_backtrace exn backtrace in match with_conn t transaction with | outcome -> if outcome = Committed then Atomic.incr t.committed; outcome | exception (Sqlite3.Error _ | Sqlite3.SqliteError _) -> Unknown;;transfer increments attempted, then runs one transaction. If the source balance is less than the transfer amount, the transaction is rolled back. Otherwise, transfer subtracts the amount from the source, adds the amount to the destination, and increments opCount on both accounts. If a statement raises an exception, the transaction is rolled back and the exception is propagated.
If the transaction commits, transfer increments committed. Any SQLite error becomes Unknown.
Properties
Section titled “Properties”let verify_total_balance t = let sum = with_conn t (fun db -> select_int db "SELECT SUM(balance) FROM accounts" ()) in if sum <> t.total then Printf.ksprintf failwith "money was created or destroyed: SUM(balance) = %d, expected %d" sum t.total;;
let verify_ops_not_lost t = let committed = Atomic.get t.committed in let sum = with_conn t (fun db -> select_int db "SELECT SUM(opCount) FROM accounts" ()) in let attempted = Atomic.get t.attempted in if sum mod 2 <> 0 then Printf.ksprintf failwith "SUM(opCount) = %d is odd: a transfer was half-applied" sum; if sum < 2 * committed then Printf.ksprintf failwith "committed transfers were lost: SUM(opCount) = %d < 2 * %d committed" sum committed; if sum > 2 * attempted then Printf.ksprintf failwith "phantom transfers: SUM(opCount) = %d > 2 * %d attempted" sum attempted;;
let verify_no_negative t = let negative = with_conn t (fun db -> select_int db "SELECT COUNT(*) FROM accounts WHERE balance < 0" ()) in if negative <> 0 then Printf.ksprintf failwith "%d account(s) have a negative balance" negative;;verify_total_balance checks that SUM(balance) equals the starting total (i.e. no money was created or destroyed).
verify_ops_not_lost checks SUM(opCount). Each transfer increments two counts, so the sum must be even. The sum must be at least 2 * committed, or a committed transfer was lost. It can be higher because some transfers can commit without the client knowing, but it cannot exceed 2 * attempted.
verify_no_negative checks that no account has a balance below zero. If two transfers
both read the old balance before either withdraws, the account can be overdrawn.
Rules and invariants
Section titled “Rules and invariants”module%hegel_concurrent_state_machine Machine = struct let total_balance_preserved _tc bank = verify_total_balance bank [@@invariant]
let no_committed_transfer_lost _tc bank = verify_ops_not_lost bank [@@invariant { always_check = true }] ;;
let no_negative_balance _tc bank = verify_no_negative bank [@@invariant]
let transfer tc () bank = let n = bank.config.accounts in let source = draw tc (integers ~min_value:0 ~max_value:(n - 1) ()) in let dest = draw tc (integers ~min_value:0 ~max_value:(n - 1) ()) in let amount = draw tc (integers ~min_value:0 ~max_value:bank.config.max_amount ()) in let outcome = string_of_outcome (transfer bank ~source ~dest ~amount) in note tc (Printf.sprintf "transfer %d from %d to %d: %s" amount source dest outcome) [@@rule { groups = [ "bank" ]; weight = 6 }] ;;
let verify_total_balance _tc () bank = verify_total_balance bank [@@rule { groups = [ "bank" ] }] ;;
let verify_ops_not_lost _tc () bank = verify_ops_not_lost bank [@@rule { groups = [ "bank" ] }] ;;
let verify_no_negative _tc () bank = verify_no_negative bank [@@rule { groups = [ "bank" ] }] ;;endWe can now define our workload.
We are required to define actions on the state, which are called rules in Hegel. Rules can belong to
one or more groups. Only rules in the same group may execute concurrently. If no group is provided,
the rule belongs to a default group. In this case, all the rules belong to the bank group for
demonstration, but the group could have been omitted. Rules also have a weight, which gives Hegel
a hint of how frequently a rule should run relative to other rules in its group(s). The default
weight is 1.
We can optionally define statements about the system that should always be true, which are called
invariants. By default, invariants are sampled for performance. For example, if we had 1 million
accounts instead of 16, we might not want check no_negative_balance after every single round
because it requires checking all accounts. Setting always_check = true forces the invariant
to always be checked between rounds.
Notice that we define the verification functions both as invariants and rules. Invariants check the state of the system at some settled state when no actions are running. When we define the verification function as a rule, they can run while other actions are mutating the state.
For example, the invariant total_balance_preserved checks that after all transfers are done,
the total amount of money has not changed. The rule verify_total_balance checks that while
transfers are executing, we never see a state in which the total amount of money has changed.
Running the workload
Section titled “Running the workload”let%hegel_main workload tc = with_bank { accounts = 16; initial_balance = 1_000; max_amount = 10_000 } (fun bank -> Machine.run tc ~init:bank ~step_count:Int.max_int ~min_concurrency:2 ~max_concurrency:8);;
let () = workload ()let%hegel_main to turns the workload into a standalone program, which allows us to pass test settings as command line options,
such as dune exec workload.exe -- --seed 1 --verbosity verbose.
init represents the initial state of the workload. Since the account balances are stored in the database, we only pass the bank handle,
which holds the database path, the connection pool, the transfer counters, and the configuration. step_count sets how many rounds execute within a test. Inside of Antithesis, this number should be very high to allow
the fuzzer ample time to explore a branch. Finally, min_concurrency and max_concurrency set the bounds for the number of concurrent workers,
which can be threads, domains, or any other unit of concurrency. Hegel spawns some number of workers within those bounds.
The diagram above shows how the workload is executed. In each round, Hegel chooses a group, then gives each worker a set of rules to run. Each worker executes its rules concurrently with other workers. Once all workers have finished executing their rules in a round, Hegel runs the invariants.
Further reading
Section titled “Further reading”For the full runnable workload, see the GitHub repository.
For more information on concurrent stateful testing, see the documentation.