4 billion was a lot when I first got into programming, but it just isn't that much any more. Always start out by making your sequence numbers 64 bits: 2^64 nanoseconds = ~585 years. (I have in the past stolen a few bits for other uses, but I'm less certain of the wisdom of that these days.)
32 bits is suitable for things that can only happen once a frame - (2^32/60) seconds = 2.26 years - but not much more than that.
But there's a flip side to computers being able to wrap a uint32_t so quickly: if you've got 32 bits'-worth of combinations, then you can might actually be able to do an exhaustive test. 2^32 microseconds = 71 minutes. Work in C++, run on all threads, and you probably won't even need to wait that long.
I did something similar a few years ago, prototyping a 16x16 multiply routine for an 8-bit CPU. It took about 5 minutes running on both threads on my 2.5GHz dual core laptop, and found some interesting cases I'd got completely wrong.
65536 was a lot when I first got into programming, there was also floating point, and then the realization that we don't need to be constrained to 4 bits, 8 bits, 16 bits, 24 bits, 32 bits, 64 bits, 128 bits, two digit years, 640K of RAM, small stack frames, broken memory models and all the other ridiculous limits. Give it a decade and I bet the ~585 year time frame is reduced to a small enough interval where bugs appear. Bet on lots of 64-bit bugs appearing, and a programmer in the future commenting that 128-bits should have been used, and 128-bits will break in the future of that future, and so on.
For me, the biggest bug in the modern x86 chip is ME: a full system that can be turned on, take over everything and eats up valuable core space.
> Give it a decade and I bet the ~585 year time frame is reduced to a small enough interval where bugs appear.
I'm skeptical that much changes in the next decade regarding where 64-bit integers are useful. It's been a long time since there are been meaningful clock frequency increases in commodity CPUs. Even if we had a 100Ghz CPU and we had it increment a register once per clock cycle, we're still talking ~6 years for it to overflow. And, thats assuming a 20+ times increase in clock frequency when clock frequencies have been mostly flat for the last 10 years.
> a programmer in the future commenting that 128-bits should have been used, and 128-bits will break in the future of that future, and so on.
I disagree with this statement. With 128-bits, it becomes difficult (though not impossible) to even come up with things that are numerous enough to be unable to count with that number of bits. That was never the case for 64-bit or smaller integers.
ME is implemented with a tiny Quark processor on the PCH. It doesn't consume any valuable space in the CPU. Every modern non-trivial support ASIC has an embedded processor for housekeeping duty. The problem is how much ME can extend its tendrils into every aspect of a modern PC.
Exhaustive search is untenable for the 64-bit case. Any strategy here? Testing 2^40 bits might be tenable; any way to select which ones would have the best ROI?
I'm not so sure that's true. You can rent a Skylake chip on Google Cloud that'll perform 1.6 trillion 64 bit operations per second for $0.96/hr preemptively. That's enough to run one instruction over a 64 bit address space exhaustively over 120 days, or for ~$2800.
Obviously that needs to be multiplied by the number of instructions a test needs to execute (and it has to be well written with AVX 512), but we're not talking nation state levels of resources here for simple cases, and that figure is only going to drop further with time.
Not to mention the potential for FPGA or ASIC implementations if the tests are important enough.
It's hard to give a general strategy without knowing the problem structure, but I guess you could say one general strategy is to exploit the problem structure in a way that lets you test multiple values in one shot.
For real though, the difference between 60 and 144 is night and day. I can't go back to 60 after playing with 144. I wonder if going beyond 144 would have the same effect.
A frame is 1/60 of a second (generally), so if you are indexing your frames with a 32-bit integer, you have enough for 2.26 years of video (or video game, or whatever).
High refresh rate monitors are getting more and more popular; at 240 FPS, a signed 32-bit counter will just last a bit over 3 months. Competitive players may want to play at even higher frame rates to decrease input lag even further. It's _probably_ still fine, because people _generally_ don't leave the game running for months, but those 31 usable bits get used up rsurprisingly quickly.
Note this is by Jann Horn, the same Google security researcher who discovered Spectre/Meltdown. Serious props to this guy, and hopefully he stays in a whitehat role where he can find and deal with these issues through responsible disclosure.
I mean with 20 (while still in colleague), cure53 got already curious about Horn, which is quite crazy. (cure53 is one of german's best penetration/security company, they even analayze your software as a service, they actually pentested curl: https://cure53.de/pentest-report_curl.pdf, prometheus: https://cure53.de/pentest-report_prometheus.pdf and probably other high valuable software)
Perhaps people new to the codebase (or the industry, or to life in general) are less likely to view existing constructs as obviously correct, and therefore more likely to point out flaws.
I think you are right. It definitely takes more than that, but you can be the smartest guy in the world and you won't discover many vulnerabilities if you assume certain components are "hallowed ground".
Apparently he thought of the spectre-style vulnerabilities while through the Intel processor manuals[1]. How many established engineers would a) read through these reference manuals at all, and b) question the implementations described therein?
I think software is a young mans game. I think bugs like this take a lot of intense time and focus. As you get older you got other things to distract you like kids, wife, house etc.
I am a lot more careful now, as compared to the start of my career. I have a lot more experience with testing and by all metrics I can measure the code that I ship goes out with a much lower defect rate. I think it is just the reverse - I think software is an excellent profession to stick to for the long haul, because with even a moderate amount of effort you can improve tremendously over time.
"This fits in with the kernel's policy of attempting to keep the system running as much as possible by default; if an accidental use-after-free bug occurs here for some reason, the kernel can probably heuristically mitigate its effects and keep the process working."
That's a pretty bad design decision. I'd much rather have a kernel panic than a kernel that continues to run with known bad datastructures. Like that the bugs will never really shake out, silent failures like that are super dangerous because essentially the system is running in an undefined state past that point.
IIUC the heuristic here is how much of the system to take down (i.e., back out of fast path [this case] < kill thread < kill process < kernel panic) and this seems correct (but could still be a symptom of more corruption).
Anyway, there has been discussion about this issue in general previously on the Linux kernel mailing list, and Linus said [1] that the correct procedure is to first introduce by-default reporting and an opt-in kill switch, then make the kill switch the default, then remove the non-kill option. This is supposed to weed out bugs eventually without disrupting users too much, but I can imagine that it enables some expolits. There was an HN discussion about it too. [2]
It's terrible from a correctness perspective, sure. But from a business perspective, that could mean $50 million of revenue not-lost to a flaw you (as an owner/operator) can't do much about. Sure, it could lead to an exploit like this, but I'd wager a cost-benefit analysis for almost any organization (except maybe CIA/NSA types) would support this design choice.
That's not to say it's a good design choice, but it's certainly a defensible one IMO. You can have the most secure OS in the world, but if no one wants to use it, all you've got is a very secure waste of hard drive space.
If a kernel panic can cost you $50 million you have other problems. Really, in an organization where downtime due to a server rebooting would be that expensive you'd hope they would be able to deal with that gracefully and that they would be deploying the rough equivalent of chaosmonkey to ensure that their stuff is protected against such errors.
After all, a harddrive or a CPU could die just the same.
This is a principle borne of experience. There have been a number of cases where a new fatal-error check killed a bunch of systems that apparently were working for a long time before. Usually it is preferred to WARN_ONCE() but not BUG_ON(). Otherwise, big corporate users, or a wide random assortment of desktop users, end up going back to an older kernel to make their systems work. The linux kernel tries above all to never have regressions, even if these regressions are just catching probably very bad bugs that were just not caught before. This happens, often enough!
Think of this from the lense of natural selection. There are many many subtle tricky low-level bugs that can result in memory corruption - many drivers, many features, many optimizations, many "cleanups", a surprisingly high rate of code changes. Many of them are caught when they cause problematic corruption. Others, just due to luck, very rarely cause any visible problem, - for months or years. We do want to know about them. We do not want to suicide the whole system, it may be one of those rare bugs that made it this far because it's usually (surprisingly) not fatal on its own.
Your implicit assumption is that the server will only reboot once. I think if the Linux kernel is upfront about its security posture and your threat-model is incompatible, it is OK to go with OpenBSD.
The problem is that downtime sucks, but if you don't take the time to make the system more correct then these buglets pile up and then you have a huge technical debt problem. It's all about economics, really, and if you have the resources early on in a project, then aiming for correctness is better than sweeping things under the rug.
It's extremely useful for developing drivers. I've developed drivers on kernels that are hardwired to panic at the slightest problem and it's a real nuisance.
Whether you should leave it on in production is debatable, but I like at least having the option of making exceptions raised in drivers nonfatal.
And the reason for that is that these drivers are linked into the monolith. If they were standalone processes you'd love the ability to do post-mortem debugging on them, or maybe even the luxury of being able to run them directly under the debugger.
Whenever I had to write device drivers I wrote them under QnX first and only then ported them to other OS's, that saved so much time, at least I knew the hardware interface would be up and running, and the data structures would all work as intended. After that all I then had to do was glue it to whatever calling convention the various *NIX flavors had.
That trick served me well, for motion capture devices as well as for high speed serial cards and some more exotic devices.
IMO - it's actually a really hard call. Error isolation is hard but we all want it. One of the somewhat less controversial versions is failing a single user request (in node or your web framework) with a 5xx on an exception. You're essentially betting that the exception is a logic bug and not somewhere that will affect other users. That's probably true, unless, you know, your database driver is responsible. We bet that's usually not the case - and we're mostly right.
Honestly I'm ok with trying to keep the system limping with a huge but - you must, at the point you first detect an error, dump...everything you know. You can try to limp along because you're trying to be a good host, but debugging after that state is, as you said, not trivial.
If you separate the two concerns (post-mortem debugging & uptime) there's a nice medium to be found. Ideally kernel panics aren't the only source of observability. You can have a daemon running that files a bug report to your favorite error tracker (sentry, etc) and (attempts to) gracefully reboot the system. That would be pretty sweet.
I agree. Efforts to continue past unexpected states frequently just make the situation worse and end up causing more user pain than a deterministic restart. This kind of recovery also masks real bugs and leads to their persistence in the codebase. (Heuristic error recovery also makes debugging more difficult.) A fail-fast approach both preserves user invariants and provides an impetus to fix bugs fast.
I've been taking a pretty close look at Linux's mm code recently, and I've been wondering why it needs to be as complex as it is. There's a brain-exploding amount of complexity, most of it open-coded, that seems to my eye to be unnecessary, or at least amenable to abstraction.
For example:
1) Why do we have entirely different management structures for anonymous memory (anon_vma and friends) and shared memory (inodes) when they really end up doing the same job? (Anonymous memory can be shared, so both paths end up needing to do the same kind of thing.) ISTM we can just use shared objects in all cases, tweaking the semantics as needed for shared memory. Anonymous memory is just swap-backed shared memory, after all. It should use the same logic.
(Yes, you need to work without a swapfile. No, that doesn't change the conceptual model.)
2) Do we really need open-coded page table walking? Why duplicate essentially the same logic four times? Sure, you occasionally want to do slightly different things at each page table level, but you can still unify most of the logic. (If you really want, you can encode the per-level differences in code generated via C++ template.)
3) Do micro-optimizations of the sort mentioned in the article really help? If these sequence numbers had been 64 bits long, they wouldn't have overflowed. If the VMA tree had been implemented as a splay tree (like on NT) instead of an RB tree with a per-thread cache, the per-thread cache might not have been needed. (Splay trees automatically cache recently-accessed nodes.) How much do these little tricks actually help? Is their cumulative effect positive?
4) Why is so much of the vm internal logic spread throughout the kernel? Both NT and the BSDs have a well-defined API that separates the MM subsystem from the rest of ring 0, but on Linux, ISTM that lots of code needs to care directly about low-level mm structures and locks. Why should code very far from the mm core (like the i915 driver) take mmap_sem directly? It feels like more abstraction would be possible here.
I get arguments based around ruthless pursuit of performance, but with function calls taking nanoseconds and page faults taking orders of magnitude more time, is anyone saving anything significant?
If you strip out all performance optimizations from modern computers they will be a lot more secure but they will run slow as molasses. Starting with the hardware caches and ending with optimizations like these we are not talking 'minor gains' but likely orders of magnitude difference between optimized and non-optimized. And all of those have security trade-offs.
It's a tough call, the mantra used to be 'get it right, then make it fast', but in practice whoever ships the fastest stuff will win the race, even if it is incorrect. As long as it is correct long enough to run the benchmarks I guess.
This is yet another reason why I love microkernels (real ones), they are a lot easier to reason about and to get right to the point that you can really rely on them not to suddenly exhibit some weird behavior due to the complexity of their execution context.
Agreed, but much of the time, these improvements can be had without complicating the code itself. That's one reason I much prefer C++ over C: it's much more amenable "cost free abstraction" techniques that provide both performance and clarity.
> If you strip out all performance optimizations from modern computers they will be a lot more secure but they will run slow as molasses
Each optimization needs to be evaluated on its own. Not every optimization actually helps, and due to the effects of path length, icache pressure, and code complexity, the cumulative effect of many micro-optimizations may end up being negative. (It's why -funroll-all-loops is not in fact very fun.)
There's no forced tradeoff between complexity and speed! The fastest code is the code that doesn't run at all. Often, the best way to optimize a program is to strip it down to the rafters and then re-add only the optimizations that actually help. Simpler is often faster.
That is mostly true, but the fact is that until 'spectre' and 'meltdown' everybody believed that the security implications of hardware caches were theoretical. It took decades since we started using them for the first practical manifestations of issues that were warned about long ago.
For pure software optimizations I would be more than happy to end up with a machine that is half as fast but bulletproof. But I am not sure that I am in the majority there.
And even though you are right that there is no forced tradeoff between complexity and speed in practice this is often the case, so often that we have institutionalized it, we generally accept that in order to make things faster we will have to make them more complex. If not then the most naive version of code would in general be the fastest and this just isn't the case.
So in the end it all boils down to where you draw an arbitrary line and say 'to the right there is too much complexity, to the left we are too slow'. Everybody will want to draw that line somewhere else, so we try to have our cake and eat it too: we optimize as much as we can, make stuff more and more complex and then we try to shoot holes in it. Sometimes successfully!
> The fastest code is the code that doesn't run at all.
I'm taken with Daniel Bernstein's observation that speed is totally unimportant for ~95% of the code generated. The reason being it the percentage of the time it runs is a small percentage of the total, or it runs hardly or not at all.
And I'll add that for most programs written, speed isn't important. Because the cost to run them is a small fraction of the cost to write and maintain them.
Regarding 3), I suspect that the optimization is rather important for page fault scalability when the process has many threads. You would traditionally synchronize access to the VMA tree using some sort of reader-writer lock, but scalable read locks impose a higher cost to writers. It's easy to believe that splay trees wouldn't help and might hurt in this case, as lookups may modify the tree structure and thus can require more synchronization than a read lock.
Calling this a micro-optimization is thus misleading; rather, it probably helps quite a lot in some particular workloads and has a negligible impact on others.
Plus when there were only two levels of page tables it didn’t matter that much. Now that we’re starting to see for and even five it’s becoming an issue.
Serious question - where would you start if you wanted to learn about how to do find/diagnose this types of issues and maybe one day work for project zero. Everytime I see these posts it blows my mind, maybe because I have never done any kernel development, but I tend to get the feeling these guys/girls must be the best of the best.
FreeBSD doesn't have a per-thread cache, but does similarly use a generation number to allow operations to detect stale state upon reacquiring the vm map lock. I don't see why it isn't prone to the same kinds of bugs.
You could argue that a system written in a language that permits such errors is not well-thought out. The terms you're using are not well-defined, so it's easy to disagree endlessly without arriving at a useful insight.
This is such fabulous work! Sometimes I look at such work with a tinge of jealousy. How does one get good so good at programming. I try but I cannot get to be this good. I especially find it hard to understand someone else's code.
The bug was fixed by changing the sequence numbers to 64 bits, thereby making an overflow infeasible, and removing the overflow handling logic.
So the bug is still there then? It will just take longer to hit.
Until someone else decides to change the encoding of that field, for some reason, and not initialize it at 0. It instead starts with a random value (for safety reasons). Good luck figuring out that random crash that happens once in a blue moon.
Like I said in my original comment, not if a future kernel change randomized that value to make it unpredictable to attacks. Then the bug will be back.
The bug doesn't trigger when the counter resets to zero, the bug triggers when the counter reuses a previous value.
So:
A) There is no reason whatsoever to randomize the counter
B) Even if they did, it wouldn't be a problem because it would still take an absurdly long time to loop around to the starting positions.
32 bits is suitable for things that can only happen once a frame - (2^32/60) seconds = 2.26 years - but not much more than that.
But there's a flip side to computers being able to wrap a uint32_t so quickly: if you've got 32 bits'-worth of combinations, then you can might actually be able to do an exhaustive test. 2^32 microseconds = 71 minutes. Work in C++, run on all threads, and you probably won't even need to wait that long.
Good example: https://randomascii.wordpress.com/2014/01/27/theres-only-fou... - runs in 90 seconds.
I did something similar a few years ago, prototyping a 16x16 multiply routine for an 8-bit CPU. It took about 5 minutes running on both threads on my 2.5GHz dual core laptop, and found some interesting cases I'd got completely wrong.