Random adversary.

[afck]

While it's impossible to cover every conceivable sophisticated attack strategy, we should send at least one fake message of each variant in some test, i.e. for each algorithm have a random adversary that creates all kinds of nonsense messages.

Where possible, we could make it a bit smarter (or have a separate, less random adversary) and e.g. generate fake messages with the correct epoch (or ±1), since that is more likely to expose bugs.

Another way to generate more "realistic" fake messages is to simulate a complete instance of the algorithm in parallel and use it as inspiration, i.e. modify its messages a bit and send them to the honest nodes.

[mbr]

A first draft is in PR #112, for your consideration ;)

Some comments beyond:

While it's impossible to cover every conceivable sophisticated attack strategy, we should send at least one fake message of each variant in some test, i.e. for each algorithm have a random adversary that creates all kinds of nonsense messages.

• Nonsense
• Replay attacks

Where possible, we could make it a bit smarter (or have a separate, less random adversary) and e.g. generate fake messages with the correct epoch (or ±1), since that is more likely to expose bugs.

Right now the epoch is random, mainly because this was a way longer hanging fruit. It is not impossible to add though, see the PR #112 for details.

Another way to generate more "realistic" fake messages is to simulate a complete instance of the algorithm in parallel and use it as inspiration, i.e. modify its messages a bit and send them to the honest nodes.

As mentioned in PR #112, the Adversary API could use some changes. One addition not proposed in the PR would be to restructure the whole construct and have faulty as well as correct nodes take part in the network the same way. Instead of forcing the Adversary to handle messages for their nodes through the push_message() function, the adversary should be a message filter in front of each node instead.

This would allow an adversary implementation to easily play along and only occasionally change a message.

Further ideas

I would like to suggest two other things: It seems that a few bits of random input could be tested more efficiently, e.g. property-based testing could be used to generate these inputs. E.g., when testing the broadcast algorithm, a crate like proptest or quickcheck would generate multiple inputs to be tested. Proptest has the nice feature that it will save the random seed used in a file that can be checked into version control, causing all tests that failed in the past to be run against first; this efficiently keeps track of regressions.

Another approach worth exploring would be model-based testing. For this, the algorithm would be implemented in a stripped-down form in the test crate to form a model. An enum of operations is then created, representing all "operations" that could occur, including malicious ones from an adversary. Both, implementation and model, are executed in lockstep and if any invariants are violated, the resulting test would fail.

Here is a sketch of an example:

1. A global message queue of messages that are sent across the network exists.
2. A new algorithm instance is created, in both model and implementation.
3. The following operations are available (non-exhaustive, but a good starting point):
   • Step: Take the message at the head of the message queue and deliver it.
   • Shuffle: Have the adversary re-arrange the message queue contents.
   • Replay: Take a random, previously sent message and re-add it to the message queue.
   • Inject: Create a new random message and append it to the queue.
   • Verify: Verify that all invariants hold. Alternatively, this can be done on every step instead.

In model-based testing, proptest can now be used to generate a random vector of operations and apply them to both algorithm instances. If this causes any failure, proptest will automatically reduce this to a minimal example by trying to drop arbitrary operations from the sequence until it no longer causes a failure. The result is then displayed.

This solves the reproducability issue that is currently present - any failing test in the RandomAdversary will just output a ton (up to 13,000 in the case of the current 10% honey badger test) of random messages with no means to reproduce them.

The model crate is an example implementation of this scheme, the boilerplate code is not entirely trivial. The core is proptest though and model could be omitted.

While I am not 100% that this would solve all problems or even work well, it seems a worthwhile pursuit if randomness-based testing is to be a thing from now on.

A lot of these ideas are also explained in Tyler Neely's RustFest 2018 Talk, which I recommend everyone watch who has not seen it. A bit dated, but available nonetheless is Martin Hellspong's RustFest 2016 Talk.