fuzzing: add invariant tests in fuzz pipeline

[dpaiton]

These issues
delvtech/hyperdrive#253
delvtech/hyperdrive#534

outline a list of "invariants" (assumed truths) that should hold in hyperdrive at any time.

We've sorted them into two categories:

1. Alongside fuzz testing -- After each block is mined these invariants will be checked using the stored database state values inside a parallel cron job
2. Using interactive hyperdrive -- These are not using the fuzz framework, but instead are targeted tests using a controlled set of trades

---

1. Invariants to check alongside fuzz trades:

• total shares == share reserves + shorts outstanding/c + _governanceFeesAccrued + _withdrawalPool.proceeds + epsilon
• the system should always be solvent (solvency = share_reserves - global_exposure - minimum_share_reserves > 0)
• PV always >= idle
• ∆ lp share price should never be more than 0.1%
• share reserves * c - long exposure >= minimum share reserves
• creating a checkpoint should never fail

2. Conditions to check in an interactive setting (aka static tests; not included in fuzz testing)

• opening and immediately closing a trade shouldn't result in profit
• longs and shorts should always be closed at maturity for the correct amounts
• given a set of open positions, the final state of the reserves will be the same no matter what order the positions are closed in (path independence).
• if all of the funds are removed from Hyperdrive, there is no base left in the contract

Present value interactive test
do all trades (add & remove liquidity, open & close longs & shorts)

• For any trade, LP share price (which = present value / number of shares) shouldn't change by more than 0.1% when distributing excess idle (which is called when any action is done)
• open or close trades shouldn't affect PV (within tolerance, maybe 0.1%?)
• removing liquidity shouldn't result in the PV increasing (it should decrease)
• adding liquidity shouldn't result in the PV decreasing (it should increase)
• PV always >= idle

[dpaiton]

Input from @jalextowle

What I'm looking for is for us to fuzz invariants by making random actions and checking a set of invariants between every action. You can find a list of the invariants that we want to fuzz here: delvtech/hyperdrive#534 and delvtech/hyperdrive#253. If we get that finished, maybe working on automating crash reporting and deployment is useful, but we should start manual and only consider automation once we are getting real bug reports. Aside from that, I don't think that we should spend any time making the fuzzing smarter until we get to a point where we can't find bugs without it (i.e. we've spent a day or two fuzzing and we haven't found anything). Everything should be driven by breaking invariants and how long it takes the system to do so.

[dpaiton]

we will have two testing pipelines, lets call them "fuzz bots" and "interactive fuzz tests"; these pipelines are both "fuzzing" but they're using two different workflows. (numbers correspond to the categories in #1123)

The fuzz bot workflow deploys a handful of random trading agents in a docker container from infra onto an AWS workstation. There is a forever-loop of random trades happening on hyperdrive, as well as some "control bots" that ensure e.g. there is sufficient liquidity (lp bots), the market is rational (arb bots), etc. In parallel to this forever-loop process is a secondary "invariant checking" process that uses the database values to check all of the invariants every time a block is mined. This system of paired processes would be deployed by us, e.g. every time hyperdrive has a new release, and will run as long as we want to.

The "intaractive fuzz test" workflow is a python file per check that uses the Interactive Hyperdrive workflow to spin up a specific state and test that check. This will include random elements. These can be included in our agent0 CI.

These are the checks in the second category:

opening and immediately closing a trade shouldn't result in profit
 
given a set of open positions, the final state of the reserves will be the same no matter what order the positions are closed in (path independence).
 
if all of the funds are removed from Hyperdrive, there is no base left in the contract
 
LP share price shouldn't change by more x% when distributing excess idle
 
trades are never executed with negative interest rates

This category isn't to say that there is no fuzzing element, just to say that it is not part of the fuzz bot workflow. Each of them has its own explanation, but broadly I think the idea is these things are explicit situations that wouldn't necessarily come up by running a random trading bot. In other words, each of them assumes we're setting up some contrived state and checking a condition, instead of checking the condition after any random state.

opening and immediately closing a trade shouldn't result in profit -- the likelihood of a random bot opening & closing a trade immediately is low; we should have a notebook that fuzzes the amount, but explicitly does this open-then-close workflow and checks the profit amounts

given a set of open positions, the final state of the reserves will be the same no matter what order the positions are closed in (path independence) -- we randomly open some positions, save state, then in a loop close them at random, then check reserve levels

if all of the funds are removed from Hyperdrive, there is no base left in the contract -- we randomly open positions, then close them all, then check base balance

LP share price shouldn't change by more x% when distributing excess idle -- we set up scenarios with random LP shares & idle, and then check share price changes during distribution

trades are never executed with negative interest rates -- we execute all possible trades (with random values) with a negative rate and confirm that it never is executed

Those last three might end up in category 1
given a set of open positions, the final state of the reserves will be the same no matter what order the positions are closed in (path independence).

if all of the funds are removed from Hyperdrive, there is no base left in the contract

LP share price shouldn't change by more x% when distributing excess idle

could be checked at each block as well

[dpaiton]

fuzz tests implemented in #1138 #1161 #1162 #1177

[dpaiton]

Opened issues can be found here: https://github.com/delvtech/hyperdrive/issues?q=is%3Aissue+label%3Apython+

[dpaiton]

TODOs after convo with @jrhea and @jalextowle:

Files to update

fuzz_bots.py

• update base budget to 100% of liquidity, so that max trades could cause large swings
  • we might need to add some sort of weighting to the random draw so that super large trades are unlikely, or we could have a checker that monitors the pool state and adjusts it (e.g. launch the lp_and_arb bot alongside random bots & give it a large tolerance).
• larger slippage tolerance (maybe 10%? or better yet randomly on/off for each bot) to allow big trades

fuzz_bot_invariant_checks.py

• line 147: new formula:

expected_vault_shares = (
    pool_state.pool_info.share_reserves
    + pool_state.pool_info.shorts_outstanding / pool_state.pool_info.share_price
    + pool_state.gov_fees_accrued
    + pool_state.pool_info.withdrawal_shares_proceeds
    + pool_state.pool_info.zombie_share_reserves
)

• line 182: adjust to only check that current_share_reserves >= minimum_share_reserves. e.g.:

current_share_reserves = pool_state.pool_info.share_reserves
minimum_share_reserves = pool_state.pool_config.minimum_share_reserves
if not current_share_reserves >= minimum_share_reserves:
  ...

also move this to be above the solvency check.

• line 200: add a note:

# NOTE: This would be prone to false positives.
#       If the transaction would have failed anyway,
#       then we don't know that it failed bc of checkpoint failure or bc e.g. open long was for too much

fuzz_hyperdrive_balance.py

• line 65: advance_time should be False & no trades should mature
  • the total time advanced after open_random_trades() should be less than first trade's position duration

fuzz_path_independence.py

• line 93: Guarantee that the closing trades are all within the same checkpoint.
  • We would ideally like it to be the same block, but this is going to require a fairly large (1-2 day) refactor of the interactive hyperdrive pipeline. So we will just do same checkpoint for now and assess importance of same block later.
• line 101: present value should also match within tolerance (maybe 1e15 to 1e18, bc of weighted average & rounding)
• line 240: base balance is already being checked in fuzz_bot_invariant_checks.py and doesn't need to be checked here
• line 252: verify that the effective share reserves check is valid now that we have zombie shares
• line 269: Minimum share reserves -- don't need to check this because it is in pool_config and shouldn't change

fuzz_long_short_maturity_values.py

• verify that it is ok to skip over checkpoints when advancing time without trades.

Crash Report

• in the interactive fuzz tests add a ticker to see all trades

[slundqui]

After #1231, we have the following left:

update base budget to 100% of liquidity, so that max trades could cause large swings
we might need to add some sort of weighting to the random draw so that super large trades are unlikely, or we could have a checker that monitors the pool state and adjusts it (e.g. launch the lp_and_arb bot alongside random bots & give it a large tolerance).

Holding off for now to test if previous crashes is fixed in version v0.4.0

larger slippage tolerance (maybe 10%? or better yet randomly on/off for each bot) to allow big trades

Still need to randomly set on/off for each bot.

line 93: Guarantee that the closing trades are all within the same checkpoint. Could we force these to the same block? Alex suggested that we should be able to stop the "mine per transaction" anvil process, close the trades, mine a block, and then start it back up again. Either way, it should be implemented in helpers/close_random_trades.py with a flag on_single_block: bool =False

Implementing feature in follow up PR

line 101: present value should also match within tolerance (maybe 1e15 to 1e18, bc of weighted average & rounding)

Waiting for present value checks to be written

line 252: verify that the effective share reserves check is valid now that we have zombie shares

Took a quick look, calculating effective share reserves doesn't have zombie shares in the rust sdk. Need to dig deeper.

[slundqui]

line 65: advance_time should be False & no trades should mature
the total time advanced after open_random_trades() should be less than first trade's position duration

Revisiting, such that advance time is now True for this, and open_random_trades doesn't pass a position duration for the first trade
#1232

[dpaiton]

Added descriptions to make the tests easier to grok here #1233

[dpaiton]

Additional todos:

• modify max amount in generate_trade_list to use max_long and max_short instead of hard-coding 100k
• random bot policy should use min_trade_amount instead of 1WEI for getting trade_amount
• refactor long_short_maturity test:
  • assert open bonds == close bonds, then just use one of them (instead of testing both)
  • verify close vs open base amounts, are we using the correct ones? Remove intermediate variables and instead add comments noting why we're using open vs close.
  • verify that the TODO on line 117 (ensure maturity chkpt is maturity of all positions) is done, delete it
• add a flag to make variable interest zero (this is just in config right?)

[slundqui]

refactor long_short_maturity test:
assert open bonds == close bonds, then just use one of them (instead of testing both)
verify close vs open base amounts, are we using the correct ones? Remove intermediate variables and instead add comments noting why we're using open vs close.
verify that the TODO on line 117 (ensure maturity chkpt is maturity of all positions) is done, delete it

#1234

[dpaiton]

line 101: present value should also match within tolerance (maybe 1e15 to 1e18, bc of weighted average & rounding)

#1236

[dpaiton]

random policy uses min transaction amount for trade lower bound

#1238

[dpaiton]

modify max amount in generate_trade_list to use max_long and max_short instead of hard-coding 100k

#1241

Original implementation caused an error, fixed in #1245

[slundqui]

add a flag to make variable interest zero (this is just in config right?)

#1242

[slundqui]

line 93: Guarantee that the closing trades are all within the same checkpoint. Could we force these to the same block? Alex suggested that we should be able to stop the "mine per transaction" anvil process, close the trades, mine a block, and then start it back up again. Either way, it should be implemented in helpers/close_random_trades.py with a flag on_single_block: bool =False

We added assertions for the path independence test to ensure transactions are closed within the same checkpoint (#1242). However, it's a bit of a heavy lift to add the feature for multiple transactions on the same block for interactive hyperdrive, mostly due to keeping everything synchronous in interactive hyperdrive. This feature is detailed in #1244, but we're working around this for now by turning off variable interest for the path independence test.

[dpaiton]

TODOs after latest convo

• in our fuzz tests lets prevent allowing two max longs/shorts in row

  • lets put a check in the interface before calling rust funcs; if bond & share are at certain levels (e.g. close to equal for max long) then we directly return FixedPoint(0) without bothering with the rust func. Similar for max short

• catch neg interest in crash reporting and see if it's because max long was too big (calc_max has noise, this results from two max trades in a row)

Moved the above 2 tasks to their own issue delvtech/hyperdrive-rs#126 because we do not believe they are presently causing failures.

• set it to use 75% of the max long

• add new time stretch calc to rust & hyperdrivepy (update agent0 & hyperdrivepy to use new time stretch formula #1230)

• path_independence_check effective share reserves has tolerance of 1e-4

• instead of making trades close on same block lets just set variable rate to 0 right before you start closing (we can do this in close_random_trades.py)

• delete hyperdrive balance test (this test only works if closures happen on same block, which we can't do)

[slundqui]

set it to use 75% of the max long

path_independence_check effective share reserves has tolerance of 1e-4

instead of making trades close on same block lets just set variable rate to 0 right before you start closing (we can do this in close_random_trades.py)

delete hyperdrive balance test (this test only works if closures happen on same block, which we can't do)

#1249

[dpaiton]

new TODOs (@slundqui is on this):

• increase the number of times we run the test
• if a closure path fails (neg interest, over/under flow); skip that closure path
  • if none of the paths succeed, skip the test
  • make sure you log those errors, but don't count it as a failed test
• only count the fuzz test as "failed" if we had >1 successful close path AND the invariance checks failed.
• check that we have a test that closes random trades at maturity in random orders, and we expect them to never fail (e.g. neg interest)

[slundqui]

increase the number of times we run the test
if a closure path fails (neg interest, over/under flow); skip that closure path
if none of the paths succeed, skip the test
make sure you log those errors, but don't count it as a failed test
only count the fuzz test as "failed" if we had >1 successful close path AND the invariance checks failed.

#1252

[slundqui]

check that we have a test that closes random trades at maturity in random orders, and we expect them to never fail (e.g. neg interest)

#1253

[dpaiton]

update base budget to 100% of liquidity, so that max trades could cause large swings
we might need to add some sort of weighting to the random draw so that super large trades are unlikely, or we could have a checker that monitors the pool state and adjusts it (e.g. launch the lp_and_arb bot alongside random bots & give it a large tolerance).
larger slippage tolerance (maybe 10%? or better yet randomly on/off for each bot) to allow big trades

achieved in #1265

[dpaiton]

Closing this issue as all tasks have been completed.