SQLite is the most thoroughly tested codebase I'm aware of [1]. It has seven times more test code than non-test code. 100% branch coverage. If even SQLite can have a RCE vulnerability, I'm convinced that it is not feasible for anybody to write safe C code.
Right. The actual standard is called "modified condition/decison coverage" or MC/DC. In languages like C, MC/DC and branch coverage, though not exactly the same, are very close.
Achieving 100% MC/DC does not prove that you always get the right answer. All it means is that your tests are so extensive that you managed to get every machine-code branch to go in both directions at least once. It is a high standard and is difficult to achieve. It does not mean that the software is perfect.
But it does help. A lot. When I was young, I used to think I could right flawless code. Then I wrote SQLite, and it got picked up and used by lots of applications. It will amaze you how many problems will crop up when your code runs on in millions of application on billions of devices.
I was getting a steady stream of bug reports against SQLite. Then I took 10 months (2008-09-25 through 2009-07-25) to write the 100% MC/DC tests for SQLite. And after that, the number of bug reports slowed to a trickle. There still are bugs. But the number of bugs is greatly reduced. (Note that 100% MC/DC was first obtained on 2009-07-25, but the work did not end there. I spend most of my development time adding and enhancing test cases to keep up with changes in the deliverable SQLite code.)
100% MC/DC is just an arbitrary threshold - a high threshold and one that is easy to measure and difficult to cheat - but it is just a threshold at which we say "enough". You could just as easily choose a different threshold, such as 100% line coverage. The higher the threshold, the fewer bugs will slip through. But there will always be bugs.
My experience is that the weird tests you end up having to write just to cause some obscure branch to go one way or another end up finding problems in totally unrelated parts of the system. One of the chief benefits of 100% MC/DC is not so much that every branch is tested, but rather that you have to write so many tests, and such strange, weird, convoluted, and stressful tests, that you randomly stumble across (and fix) lots of problems you would have never thought about otherwise.
Another big advantage of 100% MC/DC is that once they are in place, you can change anything, anywhere in the code, and if the tests all still pass, you have high confidence that you didn't break anything. This enables us to evolve the SQLite code much faster than we could otherwise, using relatively few eyeballs.
Yet another advantage of 100% MC/DC is that you are really testing compiled machine code, not source code. So you worry less about compiler bugs. "Undefined behavior" is a big bugbear with C. We worry less than others about UB because we have tested the output of the compiler and we know that the compiler did what we wanted, even if the official C-language spec didn't require it to. We still avoid UB, and SQLite does not currently contain any UB as far as we know. But is is nice to know that even if we missed some UB in the code someplace, it probably doesn't matter.
Nicely written, and thank you for providing such a great peice of engineering!
A thought: would it help to have a modified C compiler that would crash the app whenever UB was encountered? It might help find some bugs where non-default C compiler was used (which I assume happens, given the large amount of platforms sqlite supports). Or am I missing something?
There is ASAN, the address sanitizer.
You can enable it by passing some flags to gcc.
It will make your program crash as soon as there is an out of bounds read / undefined behaviour.
If debug symbols are enabled, it will also tell you which line of code was responsible.
It can save you countless hours of debugging
I believe there's some things your have to do such aren't C compatible, e.g. store fat pointers of base+length+offset instead of raw pointers, to catch OOB accesses.
I would not help because modern compiler treat UB as an optimization opportunity, including a license to do whatever they want (even elimination of code).
That 100% branch coverage does not include indirect calls via functional pointers or jumps to signal handlers caused by devision by zero or invalid memory access, right?
That's not a branch; otherwise you would have an infinite (or impossibly large) number of branches for just that one line of code. A branch is when you execute one set of code upon a given condition, and another if that condition is not met.
I didn't say every number is a different branch. But on many processors, divide by zero triggers an interrupt. That's semantically the same as a branch.
It depends on the language. In C it is not a branch because division by zero is undefined and not a path you consider. In Java you can argue that there are two branches. One branch that throws an exception and one that does not.
No coverage reporting library will attempt to tell you that kind of coverage. You are essentially in violent agreement with the op but turning it into an argument by using different words for the same concept.
Testing all possible branches (each considered individually) won't get you very far in terms of testing all possible logic flows.
Consider a function which checks 5 simple if-statements in a row, always in the same order. Getting each branch means you tested 10 things.
But there are 32 ways for 5 if-statements to jointly evaluate. If there is a logical dependency between the state checked by one if-statement and the state checked by another one, your perfect coverage may not pick up on that.
If the if-statements might be checked in an arbitrary order... there are 120 ways to order 5 things. But you'll still get perfect branch coverage by checking 10 of them.
Will fail. However, branch coverage won't tell you that there's a hole in your test coverage.
Generally however, writing full branch coverage will find a lot of issues, and also cause you to really think through how your code works; but still, it doesn't guarantee correctness. If you want that you need to start bringing tools that either exhaust your input space (a function which takes 5 booleans can be exhaustively tested for correctness in trivial amounts of time), or you start modeling your chosen language well enough that you can use a mathematical prover to demonstrate that your program or function is safe on all inputs.
This of course requires you to come up with a definition of 'correct' or 'safe'. For the above program, it's clear how to define correctness. For things like "Don't let an unauthorized individual access this data or data that is derived from it in a way contrary to the desires of the owner of said data" it gets 'tricky' ;).
You can do this with machine verified programs. It's like proving a maths theorem; you don't check it for all values but you create a robust argument that it must be true for all values.
That is why I like using random data generators for tests. You can input some static data and then the rest is random. Every once in a while a bug pops out when you see a test fail that was previously passing.
None of the above methods are used for testing. You use boundary testing, branch testing, equivalence partitioning etc. Random data is not a good method of testing.
Except for the fact that it is exactly the method that has been used to discover a large number of critical bugs in the most popular OSS projects (including SQLite):
http://lcamtuf.coredump.cx/afl/
Fuzzing isn't really practical if all you do is just generate a totally random bit stream for input. There are many much more clever and robust strategies to hit as many edge cases as possible. Check AFL[1] for some details on generating smart random input files. You can also combine that with pretty advanced dynamic execution analysis to fuzz against unknown processor instruction sets, like in sandsifter[2].
On the contrary, for years, the most prolific fuzzers basically did just generate random bitstreams, and that technique will still find vulnerabilities in all the memory-unsafe software that hasn't been fished out by those same dumb fuzzers.
Sorry, I strongly disagree. Random data with a few static arguments is an incredibly great way to test. Adding in some chaos finds bugs. "why did that test fail after 100 times...ohhhh"
I try to only use random data when possible, less and smaller tests to write with a proper setup. End result: more bugs found.
Not sure why this is being downvoted, but you're correct. Now, a networked application that exposes some level of access to sqlite? That's another story. The question I think we all are asking is just how much "leg" does sqlite have to show to be vulnerable?
I think the reverse definition is just as silly... Calling a JPEG parser vulnerability an RCE just because some online service is using it in a way that can be exploited remotely. By that definition, any bug is an RCE, since I can just set up a web server to run that program.
I think a better way of looking at it is that it's an ACE Vulnerability in the e.g. JPEG parser that causes an RCE in the Online Service.
Or, in this case, an ACE vulnerability in SQLite that causes an RCE in Chromium.
Sure, though what I'd say is silly is epistemological conceit of trying to pin down vulnerabilities as "remote" or "local". A lot of vulnerability research terms are silly (sillier than RCE). Either way: it's a "term of art", and it means what it means, and this is a clear and obvious instance of an RCE.
I assume people making this distinction are thinking about "network services that the public can compromise by interacting with them over the Internet" vs. "software that someone can compromise by getting it to accept a malicious input". But I agree that "RCE" is commonly used for both; otherwise we would have to maintain that browsers don't suffer RCE vulnerabilities because a malicious document is no longer "remote" once the browser has downloaded it.
I don't know. I'd say PDF or JPEG parsers (and SQLite) can have arbitrary code execution vulnerabilities, which can in turn be responsible for remote code execution vulnerabilities when used in network-connected software.
e.g. SQLite has an ACE. Chrome has a RCE (which is SQLite's fault).
If what you're observing is that industry lingo is suboptimal, you'll get no argument from me. Consider for instance "XSS" and "CSRF", which are just manifestly silly names. But the names mean what they mean; try as I might, I can't get people to accept "Javascript injection".
The actual industry term is just "code execution", or maybe "arbitrary code execution" if you want to get more specific than is typically worthwhile, not "RCE".
I don't know what to tell you. Try this: Google [browser rce], and then [browser ace] (or [browser ace vulnerability] or whatever). It'll be immediately apparent what the term of art for drive-by code execution vulnerabilities in browsers is.
I sort of intellectually in the back of my head know that "arbitrary code execution" is a term that has been coined and used in the past, but I don't offhand know of anyone that uses it (among other things, it's kind of redundant). "Local only" code execution vulnerabilities aren't "LCE", but rather (usually) "privilege escalation".
In both my comments I explicitly said that vulnerabilities in browsers can and should be called RCEs. I was only arguing about what to call vulnerabilities in the underlying libraries (like SQLite) which aren't inherently exposed to "remote" data/manipulation.
Say for some reason someone used an exploitable version of SQLite in a program that had the setuid bit set. You wouldn't say SQLite had a privilege escalation vulnerability, would you?
They're only vulnerable to RCE if image data can be supplied remotely. What's the analog here? Accessing the JavaScript API? Specifying a query string? Maliciously encoded data? Some of these are scarier than others.
I would never argue they aren't, but by this logic ("it's like saying PDF or JPEG parsers can't be vulnerable to RCE") virtually every code execution vuln in a library can be called RCE. I haven't noticed this to be the case with e.g. libtiff vulnerabilities (of which many make it into my inbox regularly), although image libraries are one of the cases were CE = RCE is still fairly reasonable.
Let's assume this SQLite bug is only exploitable if you can input arbitrary SQL. Almost no applications use it this way (except Chrome). I think it's clearly unreasonable to call it a RCE in SQLite then.
I think you're assuming the target is a browser, but my question was how this might affects servers. Does the attack use malicious SQL statements, API calls, or encoded data?
Technically, this attack is actually is two separate attacks in a chain. The first node in the chain is delivering malicious SQL. The second node is executing code remotely via SQLite. The proof is that SQLite or the application linking it could have mitigated this attack independently by either filtering the query string or better protecting the memory which is being written to.
In practice, however, the community gets more bang for their buck if they label the SQLite code execution vulnerability as an RCE since the vast majority of use is in a networked setting. You have to remember the audience used for these terms. They aren’t scientists in the traditional sense where taxonomy is highly aligned the ontology — instead, the labeling serves the operators with metaphors that depart from reality insofaras they increase security engineers ability to do their job effectively.
It is, actually. When something binds to localhost, there's still potential for privilege escalation vulnerability, since any process can connect to the port - so if there's an exploit, a low-privileged process could hijack a higher-privileged one. Localhost sockets are still a security boundary.
Since SQLite in and of itself is just a library, it doesn't have that problem. You have to expose it to untrusted inputs manually somehow (e.g. by setting up a socket).
You had me up until that last little bit at the end. No where did you make any reference to C until the end. You're kind of putting the cart before the horse aren't you?
To be a bit glib, unit tests don’t catch security vulnerabilities. Maybe I’d agree this can happen to any project, but my example might be something more like OpenBSD
In this specific case, a unit test that checked this integer overflow seeems to prevent the vulnerability.
To be clear: This is not to admonish sqlite. They have taken testing further than any other project i've heard of, except maybe the NASA software that might cost lives if it fails.
[1] https://www.sqlite.org/testing.html