_vvhw

Exactly, although, at present, Pure will also do dynamic analysis on the compressed stream once the metadata checks out, to verify that the compressed stream checks out with the metadata, i.e. that there's no semantic gap between the designated size and the actual stream size. This guards against one category of ZIP bomb.

I wanted to do this for those formats in particular, as well as Office files. Fastmail were going to sponsor some of this work to extend Pure, and I was chatting with the folks at Hey, but I couldn't get enough other sponsors to fund the work.

The idea is to use Pure to have a "Zero-Day Defense Mode" button for your email provider that you can push, if you want static analysis on 90% of the file formats coming and going, so that you can have stronger assurance on email attachments that you open. For example, I believe that Pure would have prevented last year's zero-click traversal against Apple Mail.

There are also so many ways to use file format anomalies to take out AV engines, so Pure can act as a first line of defense, before hostile data gets to them. For example, protecting them from the David Fifield zip bomb.

What I find most interesting with these checks, is that they're looking for explicit bleeds or explicit overflow bounds. So the signal to noise ratio is high.

Mostly, if people are interested, I would really love to move this all to Zig, to benefit from the checked arithmetic and spatial safety, since otherwise everything is all single-threaded run-to-completion.

> I’m a little confused by this statement. I assume by “address” you mean indexing, and the size of an index is related to the number of entries, not the amount of data being indexed.

Thanks for the question!

What's in view here is an LSM-tree database storage engine. In general, these typically store keys between 8 and 32 bytes and values up to a few MiB.

In our case, the question is how much memory is required for the LSM-tree to be able to index 100 TiB worth of key/value storage, where:

  * keys are between 8 and 32 bytes,
  * values are between 8 and 128 bytes,
  * keys and values are stored in tables up to 64 MiB,
  * each table requires between 128 and 256 bytes of metadata to be kept in memory,
  * auxiliary data structures such as a mutable/immutable table must be kept in memory, and where
  * all memory required by the engine must be statically allocated.

That's alot of small keys and values!

Typically, a storage system might require at least an order of magnitude more than 1 GiB of memory to keep track of that many keys using an LSM-tree as index, even using dynamic allocation, which only needs to allocate as needed.

Another way to think of this is as a filesystem, since it's a very similar problem. Imagine you stored 100 TiB worth of 4096 byte files in ZFS. How much RAM would that require for ZFS to be able to keep track of everything?

Thanks for the question.

"I would consider that type of logic error more or less impossible to defend at the language level, but I can see how analysis tools can be helpful."

This is how I see it too, as a logic error that exposes sensitive memory in a way that can be as unsafe as a UAF. It's a great leveler of languages, and why I get excited about enabling checked arithmetic by default in safe builds, explicit control flow, and minimizing complexity, abstractions and dependencies—this all helps to reduce the probability of semantic gaps and leaks.

Thanks for these!

Thanks! Yes, I did mention WUFFS before the edit, but then figured I could make it a bit more detailed. WUFFS is great.

The SafeDocs program and approach looks incredible. Installing tools like this at border gateways for SMTP servers, or as a front line defense before vulnerable AV engine parsers (as Pure is intended to be used), could make such a massive dent against malware and zero days.

Yes, exactly. That's what I was driving at. It's just a logic error, that leaks sensitive information, by virtue of leaking the wrong information. File formats in particular can make this difficult to get right. For example, the ZIP file format (that I have at least some experience with bleeds in) has at least 9 different places where a bleed might happen, and this can depend on things like: whether files are added incrementally to the archive, the type of string encoding used for file names in the archive etc.

Hackers exploit any avenue (and usually come in through the basement!), regardless of how skeptical we might be that they won't. They don't need the details, they'll figure it out. You give them a scrap and they'll get the rest. It's a different way of thinking that we're not used to, and don't understand unless we're exposed to it first-hand, e.g. through red-teaming.

For example, another way to think of this is that you have a buffer of initialized memory, containing a view onto some piece of data, from which you serve a subset to the user, but you get the format of the subset wrong, so that parts of the view leak through. That's a bleed.

Depending on the context, the bleed may be enough or it might be less severe, but the slightest semantic gap can be chained and built up into something major. Even if it takes 6 chained hoops to jump through, that's a low bar for a determined attacker.

Wow, that's saying something!

The tool is called Pure [1]. It was originally written in JavaScript and open-sourced, then rewritten for Microsoft in C at their request for performance (running sandboxed) after it also detected David Fifield's “A Better Zip Bomb” as a zero day.

I'd love to rewrite it in Zig to benefit from the checked arithmetic, explicit control flow and spatial safety—there are no temporal issues for this domain since it's all run-to-completion single-threaded.

Got to admit I'm a little embarrassed it's still in C!

[1] https://github.com/ronomon/pure

I worked on a static analysis tool to detect bleeds in outgoing email attachments, looking for non-zero padding in the ZIP file format.

It caught different banking/investment systems written in memory safe languages leaking server RAM. You could sometimes see the whole intranet web page, that the teller or broker used to generate and send the statement, leaking through.

Bleeds terrify me, no matter the language. The thing with bleeds is that they're as simple as a buffer underflow, or forgetting to zero padding. Not even the borrow checker can provide safety against that.

I see your UAF and raise you a bleed!

As you know, buffer bleeds like Heartbleed and Cloudbleed can happen even in a memory safe language, they're hard to defend against (padding is everywhere in most formats!), easier to pull off than a UAF, often remotely accessible, difficult to detect, remain latent for a long time, and the impact is devastating. All your RAM are belong to us.

For me, this can of worms is the one that sits on top of the dusty shelf, it gets the least attention, and memory safe languages can be all the more vulnerable as they lull one into a false sense of safety.

This is almost what we do for TigerBeetle, a new distributed database being written in Zig. All memory is statically allocated at startup [1]. Thereafter, there are zero calls to malloc() or free(). We run a single-threaded control plane for a simple concurrency model, and because we use io_uring—multithreaded I/O is less of a necessary evil than it used to be.

I find that the design is more memory efficient because of these constraints, for example, our new storage engine can address 100 TiB of storage using only 1 GiB of RAM. Latency is predictable and gloriously smooth, and the system overall is much simpler and fun to program.

[1] “Let's Remix Distributed Database Design” https://www.youtube.com/channel/UC3TlyQ3h6lC_jSWust2leGg

And coined the term “killer heuristic” for chess algorithms.

The founders of Convex are some of the most talented developers I know.

The CTO worked with Turing-award winner Barbara Liskov on Viewstamped Replication Revisited [1], the revision of the pioneering consensus protocol, and later the founding team pulled off the migration of Dropbox from S3 to their own custom storage stack called Magic Pocket [2].

The deterministic simulation testing techniques [3] they used to develop Dropbox's revised sync algorithm are still state of the art today (few systems are designed to be tested like this), and the online verification techniques [4] they used to verify their production systems are vital to building large-scale systems safely.

I can't think of a stronger technical team to do something like Convex, and couldn't imagine a better devops team to be running the backend.

[1] https://pmg.csail.mit.edu/papers/vr-revisited.pdf

[2] https://www.wired.com/2016/03/epic-story-dropboxs-exodus-ama...

[3] https://dropbox.tech/infrastructure/rewriting-the-heart-of-o...

[4] https://www.oreilly.com/library/view/velocity-conference-new...

Wow, this is high praise coming from Derek Sivers.

This should immediately be on Mercury's landing page. :)

No, I don't believe that the phrase “based solely” would be a fair assessment.

That there's a $1,024 bounty being awarded should be reason enough to suggest more than “10 minutes” went into this. While the issue was first reported in a tweet, you should know that it came to us from an experienced database engineer who worked on both Google Spanner and FoundationDB.

The initial triage was to compare O_DSYNC with F_FULLFSYNC on the same device, because the results should be within the same order of magnitude, relative to the same device—we already knew that APFS doesn't make the same distinction between O_SYNC vs O_DSYNC that Linux does.

"Intel has already proposed MRAM -- aka persistent memory. If I am understanding correctly, your tests would claim that MRAM backed disks would fail your tests, they would perform way too fast."

Again, I think you're missing that O_DSYNC was compared relative to the same device, with Darwin's custom F_FULLFSYNC as baseline.

Finally, to assume good faith, you can also imagine that once we had the triage in hand, the issue would have been confirmed independently as “correct” by a third party in the best position to make that assessment.

Details and verification are in the quoted thread (you need to click through).

TLDR: https://twitter.com/jorandirkgreef/status/153231416960472678...

You can see that, for those block sizes, the throughput of O_DSYNC is the same as F_NOCACHE, e.g. 3121 MiB/s vs 52.05 MiB/s for libuv's durable fdatasync() which is really actually using fcntl(F_FULLFSYNC) under the hood here.

In other words, O_DSYNC is only going as far as the disk's own internal cache. It's giving nearly the same performance as a buffered write.

So the reason it is “completely broken” and not simply “broken” then, is that setting the O_DSYNC bit provides no durability at all. It's a no-op.

Also, to be fair, if you're familiar with the space, it's been known for some time that Apple's fsync() is not durable—it's not like this is coming out of left field. What's new here, is that O_SYNC/O_DSYNC have the same issue. That's why we're awarding the bounty.

We discovered this through our use of O_DSYNC, and O_SYNC also has the same problem.

I think that for macOS so far, the focus has been on ordering guarantees, i.e. write barriers to reset the disk back to some atomic point in time after a crash.

However, for distributed databases like TigerBeetle, we also need durability guarantees, i.e. be able to know that the disk has the data down cold, that the disk won't “forget” data that the node has underwritten and ACK'ed externally.

Yes, we were counting on O_DSYNC to set the FUA bit on the write syscall so that we could avoid an extra F_FULLFSYNC fcntl syscall.

Technical debt has the second order effect of crippling morale.

We've been designing TigerBeetle [1], a distributed financial accounting database, from the beginning with the ultimate goal that the whole architecture of:

  * global consensus layer (Viewstamped Replication) [2], and the
  * local storage engine (a high-performance storage fault-tolerant LSM-tree over io_uring) [3],
  * which can all be deterministically simulated and fuzzed,

can eventually be used as a distributed library that gives you not only consensus but storage, all in one, kind of like “a DistSys Iron Man suit”—you put in your own state machine and business logic [4] inside it, and get all the replication and fault-tolerance around that, out of the box.

TigerBeetle is based on some of the latest research around storage faults, how to recover safely and maximize high availability, and we've been heavily inspired by the deterministic simulation testing of FoundationDB [5].

[1] https://github.com/coilhq/tigerbeetle

[2] https://github.com/coilhq/tigerbeetle/blob/main/src/vsr/repl...

[3] https://www.hytradboi.com/2022/tigerbeetles-lsm-forest

[4] https://github.com/coilhq/tigerbeetle/blob/main/src/state_ma...

[5] https://www.youtube.com/watch?v=OJb8A6h9jQQ — “How I Learned to Stop Worrying and Trust the Database”

Sneakers and War Games (and also Tron) are great.

We're running a consensus protocol bounty challenge for TigerBeetleDB inspired by them [1], with our distributed database simulator also being called The VOPR.

[1] https://www.youtube.com/watch?v=_Jlikdtm4OA

This is a great list—to add two categories:

If you need bloom filters, then use split block bloom filters [1] which use SIMD to increase speed from 30%-450%.

If you need erasure coding, then use Cauchy Reed-Solomon instead of Reed-Solomon. Cauchy Reed-Solomon uses pure XOR so you can do erasure coding at the speed of per-core memory bandwidth.

[1] https://arxiv.org/abs/2101.01719

> First of all, that's security, not safety. Lots of software exists in an environment where it isn't going to be attacked.

I use the terms interchangeably on purpose, because safety and security are really two sides of the same coin. In the past, I've worked in security and I now work in a domain where safety is critical. It's my experience that the two fields have considerable overlap.

We can always get better at interdisciplinary sharing of knowledge.

> I'm confused

Thanks, I've tried to clarify that Zig provides spatial memory safety but not temporal memory safety, so hopefully it's less confusing.

> "Simplicity" does not mean safety.

Ceteris parabus, complexity breeds bugs and simplicity improves the probability of safety. For example, if I were auditing a piece of code for security, I would prefer the simplest correct program to the most complex correct program. Reduced surface area means reduced area for attack.

When I say that Zig pursues simplicity, I also mean this as high praise, that Zig is highly "orthogonal". In other words, able to solve difficult problems with a minimum of overlapping features. For example, Zig's comptime gives you generics, but also gives you so much more, plus there is also type safety throughout Zig's comptime, yet it eliminates the need for macros, and is more versatile, powerful and flexible at the same time. It's incredibly elegant. Nothing left to add, nothing left to take away.

> Zig does exactly what Rust does in this case.

Things like checked arithmetic matter and should be enabled by default in safe builds, yet Rust does not actually do this in safe release builds. Zig does and I hope that Rust one day will.

> What are you trying to argue here? Buffer bleeds can't happen in safe rust.

By definition, buffer bleeds can in fact happen in safe Rust. The borrow checker can protect against UAF and overflow, but the borrow checker can't protect against all kinds of underflow, which is what a buffer bleed is. You can even pull them off in JavaScript.

No language is actually 100% memory safe, not with respect to buffer bleeds.

Between C++ and Rust, my bet would be that you decide Rust.

But—also learn Zig in addition to Rust.

Having seen first-hand how so many threat vectors these days are now supply chain attacks, having reported CVEs and earned P1 bounties in memory safe languages, and having worked on static analysis systems to detect zero day exploits—I'm also impressed by Zig's overall approach towards safety, as being more than only memory safety.

For example, this comes through in Zig's extreme simplicity and explicitness, and also how Zig enables checked arithmetic by default for safe builds. For people who haven't worked in security, integer overflow and wraparound may seem like small things, but they increase the probability of exploits such as buffer bleeds, i.e. attacks like OpenSSL's Heartbleed, which are often remotely accessible and easier to pull off than a UAF.

In fact, no language is 100% memory safe, i.e. able to prevent a memory buffer bleed, because these are logic errors with respect to the protocol. However, explicit control flow and checked arithmetic do help to close semantic gaps and minimize ambiguity, which is what good security comes down to.

Of course, Zig only offers spatial memory safety, and not temporal memory safety like Rust. So Zig is more memory safe than C, and less memory safe than Rust or JavaScript. Nevertheless, Zig is safer than Rust when it comes to being able to handle memory allocation failure.

Again, Rust's borrow checker is also valuable for concurrency safety, i.e. for multithreaded systems, but if you're using io_uring for fast I/O, then multithreading is less of the necessary evil that it used to be a few years ago.

Zig is something you can pick up in a week, with state of the art tooling, and fantastic C-ABI interop for libraries.

So... learn both!

Surprisingly, some of the most powerful distributed systems algorithms or tools are actually deterministic.

They're powerful because they can "load the dice" and so make the distributed system more intuitive for humans to reason about, more resilient to real world faults, and do all this with more performance.

For example, Barbara Liskov and James Cowling's deterministic view change from VSR [1][2], which isn't plagued by the latency issues of RAFT's randomized dueling leader problem. VSR's deterministic view change can react to a failed primary much quicker than RAFT since heartbeat timeouts don't require the randomized "padding" that they do in RAFT, commence the leader election, and also ensure that the leader election succeeds without a split vote.

Determinism makes all this possible.

Deterministic testing [3][4] is also your best friend when it comes to testing distributed systems.

[1] An introductory talk on VSR and it's deterministic view change — https://www.youtube.com/watch?v=Wii1LX_ltIs

[2] James Cowling on determinism, working with Barbara Liskov — https://www.youtube.com/watch?v=ps106zjmjhw

[3] FoundationDB are pioneers of deterministic testing — https://www.youtube.com/watch?v=OJb8A6h9jQQ

[4] TigerBeetle's deterministic simulation tests — https://github.com/coilhq/tigerbeetle#simulation-tests

> Allowing developers to think about a stream of operations that moves the databases from one legal state to another is super powerful.

You're right—it's super powerful.

We used this "RSM intuition" to test TigerBeetle's strict serializability, by verifying state transitions the instant they happen, taking advantage of the test simulator's knowledge of inflight client requests, instead of trying to piece everything together and verify strict serializability after the fact.

Here's TB's state checker in 49 lines of Zig:

https://github.com/coilhq/tigerbeetle/blob/477d6df366e2c10fa...

Loved this!

And here are a few more positive phrases: "total order", "committed/uncommitted log", "replicated state machine", "logical timestamp", "the network is not homogeneous", "bandwidth is not infinite", "tail latency tolerance", "fault model", "message passing", "recovery", "cascading failure", "metastable", "strict serializability", and "stable storage"!

Surprisingly, at least to me, it's jarring to hear the phrase "CAP" because the field is far more nuanced. That "C" alone has so many different flavors! Far more interesting to talk about the FLP result.

Watch out also for "RPC" because that's not isomorphic with optimal consensus protocols, where messages follow multi-path routing (A->C->B->A). Granted, RAFT uses the term "RPC" (A->B->A) but that's more a concession to accessibility and not the broadest way to think of distributed systems, or necessarily the best way to implement them. Message passing is simpler and more realistic as it helps you to see and think about the network/process fault model more clearly.

Distributed testing techniques are also moving towards autonomous deterministic testing, as pioneered by FoundationDB, where the database itself is the test simulator—these tend to get into more interesting state spaces that can also be replayed instantly from a seed, compared to external test harnesses that run for hours in real time and that can't reproduce distributed bugs deterministically in exactly the same way every time.

I had the recent privilege of interviewing Brian Oki [1] of Viewstamped Replication in September last year, since VSR is the consensus protocol that we use in TigerBeetle [2] to process a million financial transactions per second.

One of the first things that Brian Oki mentioned was Tandem NonStop, and I understand that Brian's VSR was then the first consensus protocol to deal with network partitions, where the network is not reliable, for high availability.

What was also special was that James Cowling joined me afterwards—we covered Viewstamped Replication Revisited, the 2012 revision, with a focus in both interviews on Barbara Liskov's influence on both James and Brian.

[1] https://www.youtube.com/watch?v=ps106zjmjhw

[2] https://www.tigerbeetle.com