TOCTOU bugs in ActionHandler

The action-handler system in Penumbra works by running the checks of actions in parallel such that side effects of the execution of an action do not affect the checks of another action in the same transaction.

A more concise example of this would be the below call trace:

Action 1 -> check_stateless
Action 2 -> check_stateless
...
Action N -> check_stateless


Action 1 -> check_stateful
Action 2 -> check_stateful
...
Action N -> check_stateful


Action 1 -> execute
Action 2 -> execute
...
Action N -> execute

This causes issues where developers could expect these checks to act like the transaction handling in Cosmos, which is instead dispatched like this:

Action 1 -> check_stateless
Action 1 -> check_stateful
Action 1 -> execute


Action 2 -> check_stateless
Action 2 -> check_stateful
Action 2 -> execute


Action N -> check_stateless
Action N -> check_stateful
Action N -> execute

This mismatch between the intuitive mental model of sequential execution of each action's methods with the actual interleaved order leads to time-of-check time-of-use (TOCTOU) bugs, where action 1's execute modifies state that was already checked by action 2's check_stateful, and then action 2's execute proceeds as if its check_stateful's checks still held. Mitigating these bugs efficiently can often be done by ensuring that there is a corresponding check in Transaction::check_stateless that ensures that multiple actions within the same transaction do not modify the same state.

As a concrete example, Spend::check_stateful checks that the nullifier for the note is not present in the nullifier set, and Spend::execute adds the nullifier to the set. This would be fine under a sequential order, but under the interleaved order, this would result in a note being able to be spent multiple times within one transaction — if not for Transaction::check_stateless's no_duplicate_spends check, which ensures that each nullifier occurs at most once within a transaction, which ensures that Spend::execute (and SwapClaim::execute) check and modify disjoint parts of the state.

We recommend that:

• If it does not sacrifice too much performance (or possibly only under a debug_assertions-style feature flag), Transaction::execute should rerun each Action's check_stateful method immediately before the corresponding execute, eliminating this class of bugs.

• If the sequential execution of check_stateful is only done under a feature flag, differential fuzzing or property testing of transaction validation (with a mutator or strategy that provides valid proofs and signatures) with and without the flag may be able to detect instances of this bug class.

• Any implementation of ActionHandler with a nontrival check_stateful method should have a documentation comment on execute explaining why possible interleavings of other Action's execute methods still meet the preconditions established as if check_stateful had been run sequentially, referencing the corresponding check in Transaction::check_stateless if applicable.

Remediation

This issue has been acknowledged by Penumbra Labs, and fixes were implemented in the following commits:

• 1f084185↗
• 2949f8f0↗

In PR 3962↗, check_stateful and execute were renamed to check_historical and check_and_execute, with check_historical's documentation explaining this risk.

Many former check_stateful checks were moved to check_and_execute pending profiling, and SAFETY: comments describing invariants were added to the remaining check_historical checks.