Temporal Fuzzing I: Memory Models (2021)(reitzen.com)
reitzen.com
Temporal Fuzzing I: Memory Models (2021)
https://www.reitzen.com/post/temporal-fuzzing-01/
6 comments
I'd like to see a post on fuzzing distributed applications rather than memory models. I understand the underlying principle is the same, but having only seen memory models be tested I can't quite shift my perspective enough to figure out how fuzzing processing communicating over networks would work. The SQL transaction post would be a nice perspective too. Is this still in the works?
Progress is slow, but I've been maintaining the Rust version when I have time. The MVP of fuzzing network communications and disk access is fairly easy, but there is a long tail of very complicated behaviour I'd like to simulate.
Dan Luu's site [1] goes into a fair bit of detail on the disk side. I see no reason why you can't emulate a superset of the worst case behaviour, and have a great deal of confidence that you're using file access in a way that won't result in corruption.
Networks will have a similar long tail, e.g. asymmetric net splits.
The SQL version is a bit trickier, as the API is much wider. The abstraction I was working on was essentially that you get select, insert and update, and write anything more complicated yourself.
This works for replicating the skews and other phenomena described in DDIA [2], but it runs into the same core problem that you're simulating a model of your code, not your code itself. The best pathway for temporal fuzzing databases with production loads is probably at the network layer.
[1] https://danluu.com/file-consistency/ [2] https://www.amazon.com.au/Designing-Data-Intensive-Applicati...
Dan Luu's site [1] goes into a fair bit of detail on the disk side. I see no reason why you can't emulate a superset of the worst case behaviour, and have a great deal of confidence that you're using file access in a way that won't result in corruption.
Networks will have a similar long tail, e.g. asymmetric net splits.
The SQL version is a bit trickier, as the API is much wider. The abstraction I was working on was essentially that you get select, insert and update, and write anything more complicated yourself.
This works for replicating the skews and other phenomena described in DDIA [2], but it runs into the same core problem that you're simulating a model of your code, not your code itself. The best pathway for temporal fuzzing databases with production loads is probably at the network layer.
[1] https://danluu.com/file-consistency/ [2] https://www.amazon.com.au/Designing-Data-Intensive-Applicati...
Great, thank you for the reading!
It would be interesting to see this interact with the lower-level ISA memory model work in diy, litmus, etc. Could you validate your ISA memory models against the generated litmus tests in https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf, https://github.com/litmus-tests/litmus-tests-riscv?
It should be quite possible to validate this way, although I would need to implement more ISA specific fences and features.
As mentioned in a sibling comment, I've moved away from the idea of building a model in Clojure and implementing separately, to a system in Rust where the model is the program with a compile time switch.
There were too many ways to introduce careless errors when doing a port. Although the opposite approach would have been to ingest compiled programs directly, or move to something higher level like WASM (once it gets more than SeqCst atomics).
As mentioned in a sibling comment, I've moved away from the idea of building a model in Clojure and implementing separately, to a system in Rust where the model is the program with a compile time switch.
There were too many ways to introduce careless errors when doing a port. Although the opposite approach would have been to ingest compiled programs directly, or move to something higher level like WASM (once it gets more than SeqCst atomics).
I originally submitted the post in 2021, but it was (somehow) picked up for a second chance.
The work has evolved into a Rust project Temper[1], which features a fairly intricate simulation of the Rust/C++11-without-consume memory model, supporting a superset of what Loom's atomics can simulate, but it's much much slower.
It also contains the most comprehensive set of C++11 memory model tests that I'm aware of, with test cases sourced from books, blog posts, Stack Overflow and the C++ standard. I'd love to be pointed at something larger, if it exists. [2]
[1] https://github.com/reitzensteinm/temper [2] https://github.com/reitzensteinm/temper/tree/main/memlog/tes...