This is analogous to virtual attacks on information systems which are hardened against familiar routes of ingress and vulnerable to those which are wonderful and surprising.
Of course computers are eventually physical reality, too, and things like rowhammer show that you don’t even need traditional “bugs” to escape your mathematical utopia.
But all the bugs talked about here are entirely the fault of the software.
Are you going to fuzz the program "x = y+1; return x;", or are you convinced already that it will always return either y+1 (with y treated as a natural number, not a finite width integer), or 0 (if y was the maximum value in the unsigned data type of x), and that it will never access memory out of bounds?
Formal verification is exactly that, just usually in less obvious scenarios. Advanced type systems do the same implicitly by making expressions that would violate such properties (or where they cannot be proven) not type check.
Computers these days are sufficiently complex and with enough abstractions that there’s no such thing as a guarantee.
> Fuzzing is only relevant where formal verification cannot be exhaustively applied (which is reality in turing complete languages), or is too cost-prohibitive.
Funny you should use that specific example, because your analysis fails to account for the case where a) this is C or C++, b) y has a signed integer type, and c) its value is the maximum value of said type. In that case the behavior is, infamously, undefined, and anything can happen including accessing memory out of bounds. This is exactly the sort of corner case that fuzzing is designed to reveal. Formal analysis of the function would, of course, also flag the fact that the set of values of y for which the program is well-defined is not the entire domain of its type.
Undefined per the standard, yes. Undefined per a particular implementation? Well, that’s up to each particular implementation. A compiler is free to make stronger guarantees than the standard requires. And, a formal verification is allowed to presume a particular compiler, and rely on whatever stronger guarantees it makes. Which means of course that the verification is only valid as long as that compiler is used, and changing the compiler requires revisiting the verification (even if only just to confirm that the new compiler makes the same guarantees) - but, in many cases, especially the cases in which formal verification is in the most demand (safety critical systems), that’s an acceptable limitation.
> it will always return either y+1 (with y treated as a natural number, not a finite width integer), or 0 (if y was the maximum value in the unsigned data type of x)
And it does not matter, since the point of formal verification is to help taking those issues into account.
Of course, even perfect software is susceptible to physical attacks on the hardware it’s running on, but that’s different.
I don't think this is obvious, even for theoretical software, much less for practical software. Even formal methods have limitations.
A very public recent example was of the formally proven logic in Intel and other processors around speculative execution (Spectre, Meltdown etc.). That logic was formally proven not to leak information, but the formal model wasn't actually sophisticated enough. Note that these weren't hardware bugs (they weren't bugs in the electrical components of the processor or in the analog logic), they were logic bugs in the processor's code (whether that was microcode or burned into the processor is less relevant).
In general, you can prove that a piece of software adheres to some specification, but you can't prove that the specification itself is complete enough.
Of course, realistic software has many more layers of uncertainty, and realistic formal verification is far to costly to apply to anything but very short programs.
Still, there are a lot of properties that are easy to state, and a lot of properties that are feasible to prove, and the intersection of these two can be very valuable in eradicating common issues in critical software, be it out-of-bounds pointers or your garden variety type confusion. (Again, not always possible, thanks to the halting problem, but often.)
The cost may indeed be prohibitive, though.
Most of the time, a barrier to elevated privileges that was not correctly implemented, i.e. a bug, not anything the designer did not anticipate.
> Can't you "brute force" even the most theoretically rock solid privilege boundary by simply attaching your own computer to the memory in question?
So? Does that mean it's not worth looking at the paths where the attacker does not have physical access of the machine that sits in some data center's secured basement?
For physical locks, you cannot even rigorously define the "input".
[1] Not always, unfortunately, if your language is turing complete. You might be able to prove weaker, but still very useful statements, like "no input will cause a point to be dereferenced out of bounds".
Had SQLite been written in a language that would have made it easier to perform a proof of correctness then it wouldn’t be nearly as widely used and because of that language choice and then it likely wouldn’t have had the resources (financial nor community input) to complete a proof anyway. So would it have actually been any less buggy if it weren’t a C project?
Sometimes worse is better and moaning about “what if” is neither constructive nor even warranted when you consider just how well written SQLite already is and how abundant the tests are.
> Sometimes worse is better and moaning about “what if” is neither constructive[...]
... and yet here we are talking about extremely dangerous and possibly far-reaching vulnerabilities in SQLite.
Programming languages can artificially limit the attack surface. (Up to hardware exploits which can subvert the processor itself.)