Stranger Strings: An exploitable flaw in SQLite
blog.trailofbits.com
blog.trailofbits.com
"SQLite is extensively tested with 100% branch test coverage. We discovered this vulnerability despite the tests, which raises the question: how did the tests miss it?"
Tests only validate known behavior. They didn't have a test that exercised a large string. I don't know how their test suite works but I'm curious if quickcheck might have possibly found this or if the 32-bit viewpoint of the programmer at the time would have also limited possible generated values?
Just because something has coverage doesn't mean that it is tested properly as evidenced by this bug even though sqlite has 100% branch coverage.
e.g. if your coverage is 80%, then you know (100-80)% = 20% is definitely not tested since it never even ran in your tests. It doesn't tell you much about the 80%
You can cast doubt on anything. Will you be alive 30 seconds from now? You don't know for sure! But you can be pretty confident. Similarly, testing can increase confidence in code correctness. SQLite has an excellent security history overall, and it's testing strategy is part of the reason for that success.
SQLite is better tested than many silicon chips, so it's hard to fault their testing strategy.
Perhaps a few static analyzers should be run on the codebase to find possible bugs like this.
Then reduce complexity.
SQLite is a complex program, inherently. It's designed to allow users to do complex things, and as such cannot be simpler than its purpose allows.
I'm no formal verification expert—so I don't know if SQLite is above or below that fuzzy threshold—but "reduce complexity" is not always an available tool.
Your confidence as SW engineer. The purpose of a test is to look for unexpected behaviour, not for expected behaviour.
Though clearly there's still unknowns, like when you're throwing random data at an api to see if you can find bugs. But even still, you know what _ways_ you're doing that. Tests generally won't turn up things nobody has thought to test.
Fuzzing would be a more appropriate measure to have found this issue, as usually you do fuzzing with no limit of length/size, as that's the entire point of fuzzing to expand the scope of what you're testing.
Regarding test coverage, I'd argue that even caring about test coverage is giving people a false sense of security. It's easy to achieve 100% test coverage, but that doesn't actually say that you're testing the right/wrong thing, just that at one point that line of code was executed, but again, that says nothing about correctness.
So all the replies here saying "the tests didn't find it because they didn't cover the case" are missing the point. There are test paradigms that don't rely on humans to enumerate cases.
SQLite has some fairly extensive fuzzing. https://www.sqlite.org/testing.html#fuzz_testing
One of the sections on Fuzz testing:
> 4.3 Boundary Value Tests
> SQLite defines certain limits on its operation, such as the maximum number of columns in a table, the maximum length of an SQL statement, or the maximum value of an integer. The TCL and TH3 test suites both contains numerous tests that push SQLite right to the edge of its defined limits and verify that it performs correctly for all allowed values. Additional tests go beyond the defined limits and verify that SQLite correctly returns errors. The source code contains testcase macros to verify that both sides of each boundary have been tested.
"...arbitrary code execution is confirmed when the library is compiled without stack canaries, but unconfirmed when stack canaries are present, and denial-of-service is confirmed in all cases."
Everything should be compiled with all available compiler defenses:
https://manpages.debian.org/testing/devscripts/hardening-che...
$ hardening-check /usr/lib64/libsqlite3.so.0.8.6
/usr/lib64/libsqlite3.so.0.8.6:
Position Independent Executable: no, regular shared library (ignored)
Stack protected: yes
Fortify Source functions: yes (some protected functions found)
Read-only relocations: yes
Immediate binding: no, not found!Yet, this is a textbook case of issues caught by static analysis.
It is though. Give me one project and I'll send you a test suite that "tests" 100% of executable lines. It won't have any actual assertions, but that's not what code coverage is about anyways, so hopefully you won't mind.
Number of assertions per line of code is about as good metric for how well tested something is as code coverage, which means just about nil.
I don’t think you can do that with every project. For example, a function f may do:
if (p == null) {
abort();
}
if (p == null) {
abort(“p is null”);
}
if (p == null) { // copy-paste bug
abort(“q is null”);
}
if (r == null) {
abort(“r is null”);
}
As a simple contrived counterexample, try getting 100% coverage on a function that does if(secure_hash(foo) == 0) bar();
Minor nitpick, process terminations are unit-testable in general; see e.g. https://github.com/google/googletest/blob/main/docs/advanced...
Even in the above examples, a linter should point out that the second `p == null` is inaccessible. I’m very pro test coverage, but static analysis shouldn’t be thrown out just because unit tests are available.
By adhering to the DO-178B standard, the testing is confirmed extensive and satisfies requirements for use in avionics.
"Rockwell Collins... introduced me to this concept of DO-178B. It’s a quality standard for safety-critical aviation products, and unlike so many quality standards, this one’s actually readable... one of the key things that they push is, they want 100% MCDC test coverage.
"Your tests have to cause each branch operation in the resulting binary code to be taken and to fall through at least once.
"At the machine code level... actually, MCDC’s a little stricter than that. Let’s not dwell on the details, but I had this idea, I’m going to write tests to bring SQLite up to the quality of 100% MCDC, and that took a year of 60 hour weeks. That was hard, hard work. I was putting in 12 hour days every single day. I was just getting so tired of this because with this sort of thing, it’s the old joke of, you get 95% of the functionality with the first 95% of your budget, and the last 5% on the second 95% of your budget. It’s kind of the same thing. It’s pretty easy to get up to 90 or 95% test coverage. Getting that last 5% is really, really hard and it took about a year for me to get there, but once we got to that point, we stopped getting bug reports from Android."
https://corecursive.com/066-sqlite-with-richard-hipp/
Indeed, SQLite is used for flight systems on the Airbus A350. No other major database vendor is certified to do so.
Perhaps mutation testing could have revealed the test suite was lacking in a test detecting that bug (for example, a mutation that changed a type from unsigned to signed or vice versa.)
Admittedly the some languages might make them very hard to do, but the payoff would be so, so sweet.
There are testing modes that are worth doing, and I think should be part of a development process, but shouldn't be run at every check-in. Long soaks of random input property-based testing is like this, for example.
Personally, there's a free software effort where my contribution is running tens of millions of randomized property-based tests each day and registering bugs when failures occur. This supplements and complements the fast tests that all must pass before changes are merged to master.
Even when I was on teams where the general cadence of getting changes out all the way to prod was on the order of a week, we still had changes getting to our beta environments in less than an hour. And that was on a team that wanted mutation testing, so we had it.
Edit: So my point was team mates that were worried about the 6 minutes added by mutation testing there, were the ones that would commit and then constantly refresh the page so that they could "approve" a change as it goes out. I pushed for all approvals to be automated, so there was nothing for them to watch.
Bugs rarely occur for typical input values but more often occur at the "boundaries" or limits of the input domain.
That being said I don't really fault SQlites testing here.
The key takeaway for me is that even with exhaustive testing you can still have security issues like this, so perhaps what is needed is a language or methodology change.
If SQLite, a quality codebase with exhaustive tests, can have memory vulnerabilities, maybe we need to leave C behind.
One severe CVE in about 20 years is no reason to rewrite in another language and remove support for some platforms.
The Library of Congress also recommends it for preservation of digital content, which would be harder if Rust compilers were lost. If all C89 compilers were lost, it would be much more simple to create a new one to compile SQLite than it would be to recreate a Rust compiler.
But people need to consider how much testing SQLite did and still hit memory vulnerabilities when they consider picking up C for a new project.
"I’m going to write tests to bring SQLite up to the quality of 100% MCDC, and that took a year of 60 hour weeks. That was hard, hard work."
Whatever comes out of Rust will be much worse until compliance is achieved. That's going to take substantial time.
If code hasn’t been written to be testable, 100% coverage is not _easy_, by any stretch. Any legacy code base written without unit tests that I’ve come across required significant refactoring to get any basic assertions I place, let alone any reasonable coverage.
I also think there is some value in high coverage, even without assertions. At a minimum it’s a guarantee that code has been run before production/distribution. That’s probably a lot more than can be said about a lot of code.
I understand formal verification, a bit, in terms of FPGA design, but not software.
Just one note, there are still edge cases, if n overflows the data type, you would have n > n + 1
I'll offer another explanation: branch coverage != path coverage
You generally cannot cover every possible code path through a program, because even for n branches, the possible paths scale as 2^n, and for loops it's even worse.
Once you have 100% branch/statement coverage in your tests, all bugs that are left are those that arise from the interaction of two or more statements, in a way that wasn't covered in the tests.
This is what sqlite means by "branch" coverage, it is in fact a bit stricter.
You can see in this document how significant the sqlite testing is, the 100% MC/DC is just one component.
if (a) {
doA();
}
if (b) {
doB();
}
I think there is some interpretation of that last bullet, "Each condition in a decision is shown to independently affect the outcome of the decision" that is inline with the idea. But that sounds more like on an statement like:
if (a && b)
A bit tangential, but this statement is not accurate. You can have complete branch/statement coverage and still have single-line bugs due to not fully testing the domain/range of all relevant variables; the simplest example is the potential for divide-by-zero bugs in otherwise fully tested code paths.
100% branch/statement coverage is necessary for real confidence, but it is sufficient for very little.
Which is the classic thing with no-code and with Copilot-style assistance: writing the function that meets the spec is easy. Writing a comprehensive and correct spec is the hard part.
It's like thinking someone is a better programmer because they type faster or have a better keyboard or whatever: the words aren't the hard part, typing is maybe 10% of the time you spend programming at most. It's logical correctness in composing those functions, and being able to "hold the entire sculpture in your mind" so to speak.
Source: https://www.sqlite.org/cves.html#status_of_recent_sqlite_cve...
I assume the SQLite CLI (sqlite3) uses these APIs. Could the bug be triggered indirectly by input to sqlite3? The article doesn't appear to address this question.
So in any case a string length check in the Backend should help here. Also if you get strings from a Browser Frontend, it seems unlikely you could create a payload of 2GB due to several reasons, one being string length limitations on the Browser side: https://stackoverflow.com/questions/34957890/javascript-stri...
≥ When this code was first written, most processors had 32-bit registers and 4GB of addressable memory, so allocating 1GB strings as input was impractical. Now that 64-bit processors are quite common, allocating such large strings is feasible and the vulnerable conditions are reachable.
One has to wonder how much code written in the past 30 years has safety checks assuming 32-bit processors which now have vulnerabilities like this one. I'd bet quite a lot.
July 14, 2022: Reported vulnerability to the Computer Emergency Response Team (CERT) Coordination Center.
July 15, 2022: CERT/CC reported vulnerability to SQLite maintainers.
July 18, 2022: SQLite maintainers confirmed the vulnerability and fixed it in source code.
July 21, 2022: SQLite maintainers released SQLite version 3.39.2 with fix.
Actually, 100% branch coverage says every line has been executed but also that every branch has been both taken and not taken. So e.g. every non-constant if statement is both taken and not taken.
Not all combinations are tested, all branches are both taken and not taken, but not all combinations of taken/not taken are tested.
Or even if you have a ternary operator (which has an implicit if-then-else take/don't take branch) that is usually only one line.
void foo(int arg) {
int *x = malloc(sizeof(int));
if (arg) {
free(x);
}
}
From here, we yield our only preconditions for the call being valid: `s` must point to either a `char` equal to 0 or an element of an array of `char`s that is eventually followed by a 0 (§7.6.1.2, §7.6.6), and there must be no thread or signal handler concurrently modifying it (which would cause a data race, §6.9.2.2). These are necessary for each `s[i]` access in the length computation to be valid.
Letting `n` be the computed length, we have our final precondition, that `[s, s + n)` is a valid range (§21.3.3.3). "Valid range" has a specific meaning in the standard (§23.3.1):
> A sentinel `s` is called reachable from an iterator `i` if and only if there is a finite sequence of applications of the expression `++i` that makes `i == s`. If `s` is reachable from `i`, `[i, s)` denotes a valid range.
Since `s` must point to an array of `char`s of length greater than `n`, `s + n` is clearly reachable from `s`. Therefore, `[s, s + n)` denotes a valid range, given our preconditions.
The only length restriction in the standard is that the source string must be no more than `SIZE_MAX` characters long (excluding the null terminator), since otherwise `std::char_traits<char>::length(s)` would have no correct return value.
[0] https://open-std.org/jtc1/sc22/wg21/docs/papers/2020/n4868.p...
There is another thing I found string able to do: throw std::length_error. But that's consistent with your statement that it either succeeds or throws.
So, going back to my question, it seems like the small leap from C to C++, if the author embraces the STL, does categorically prevent this class of overflow.
"Categorically" is a bit strong; if any index were ever truncated to a 32-bit integer before writing to s[i], that could also cause major issues.
Also, the C++ standard library does not have a monopoly on safe interfaces; all of the relevant APIs can be trivially reimplemented in C. It's just that C libraries have not historically made safe internal interfaces a priority.
I have the greatest respect for the quality of the SQLite codebase, which is one of the best-tested open source projects in existence, but at the end of the day, if formatting a string can lead to arbitrary code execution, it's time to question the foundations you're building on.
As long as C and C++ are considered acceptable languages for writing mission critical software, these vulnerabilities will never go away. We have incredible static analysis tools and hyper-advanced fuzzers driven by genetic algorithms, and yet this continues to happen despite every precaution imaginable being taken.
It's time to fix the problem at its root. Languages that are memory unsafe by default need to be phased out sooner rather than later.
Though to actually get binaries out of it LLVM is used, which itself is written in C++.
(the Rust compiler is written in Rust, but the LLVM backend it uses (and soon GCC, IIRC), is still written in C++)
Sqlite also has never had a severe CVE, from the parent's link:
> All historical vulnerabilities reported against SQLite require at least one of these preconditions:
> The attacker can submit and run arbitrary SQL statements.
> The attacker can submit a maliciously crafted database file to the application that the application will then open and query.
The OP's vulnerability requires passing an insanely long string to a C api, which isn't something you'd expect to be secure.
You may as well be correct about not helping here, but borrow checker provides proofs, not tests; a test can only prove the presence of a bug, while a proof can prove the lack of a certain kind of bug.
1. Accepting user input on a webpage (e.g. a first_name field on a singup form)
2. Storing that user input in a database
Would trigger a RCE if the string was escaped properly.
Here we are dealing with a memory safety problem of a type that cannot occur in Rust unless you use `unsafe` blocks. Rust doesn't allow unsafe memory access such as pointer arithmetic or out-of-bounds operations (those produce a runtime panic). C happily accepts those, and the effects may include buffer overflows leading to arbitrary code execution.
This should never, ever be possible when writing a normal program. I love that Rust has named the keyword that enables such things "unsafe", because that's precisely what it is. That C has this behavior as a default is nothing short of madness, though of course C is an artifact of a time when such issues weren't understood as well as they are today.
That being said, whether a runtime panic leads to DoS depends on the execution model. In web applications, threads are usually mapped to connections in some way, and a runtime panic only unwinds the thread it occurs in, so this wouldn't necessarily mean that other users experience service disruptions.
More to the point, I'd expect modern application and/or library code to include default safety checks that prevent scenarios like absurdly large queries from happening in the first place, and provide recoverable errors if such pathological inputs are encountered.
We have seen time and time again that humans aren't good enugh at that task, even in low-level code (and 2x is very buch an outlier).
https://www.sqlite.org/cves.html mentions this.
How do you do this in Firefox? Firefox never implemented WebSQL.
I don't think SQLite needs to be rewritten in any language, tho.
Yes it is!
Rust would help here - not the borrow checker, but the bounds checking.
Sure, write new stuff in Rust, but SQLite needs to stay in C at this point.
I would like them to try, though, because I suspect, barring a Bellard Event, no-one will be able to get close to SQLite's functionality[1], reliability, etc., in a new Rust implementation within 5 years (possibly even 10 years.)
[1] including being able to load extensions, integrate into basically everything as library, etc.
And again, SQLite is used in places that Rust has no compiler for. This is a hard constraint that precludes using Rust.
Just the other day I found a relatively recent C++ tutorial on YouTube using Turbo C++ for MS-DOS, imagine how idiomatic it looked like.
And most of those "teralines" of code are legacy garbage. The core OS, a basic userland, a database and a webserver are 90% of the world's critical IT infrastructure. That doesn't take a century to rewrite.
You will lose all of that in a rewrite, which is why people don't do it.
> You will lose all of that in a rewrite
I don't think you lose everything in a rewrite in general - you still have all of the edge cases and business logic in the old code that you translate to the new code. It's not like you are implementing whatever it is from scratch.
Sure, there are opportunities for the translation to introduce regressions, but that's a vastly different argument (and I think a much more minor downside).
At some point you have to come to terms with the fact that some bugs shouldn’t be fixed.
And you don't have to rewrite everything at once, you can do it at the function or file level bit by bit. Perhaps the parts that are changing the most are done first, or perhaps the parts with the most bugs.
I'm still not saying rewriting is always right or wrong, but I think it isn't as cut and dry as some make it sound.
Well I have this native app fetish. I mean why pay for 4 G ram for each electron app?
No, there is more legacy code than you list there.
Please keep those web apps.
(I'm actually curious, how does dynamic linking work with Rust? Can you build a .so/.dll/.h pair and ship it everywhere like with C?)
everywhere depends on what you mean; rustc does have support for fewer platforms than gcc. But it's still quite a few.
The people who think this is the solution are the ones who will need to take up the work.
It's not like the people who don't think this is the solution will do it.
Get ready to work hard for 5, 10, 20 years... rewriting sqlite will be a monumental effort and take the laser focus of a strong development team for years, if not decades. It's fraught with risk. Think about it... how many years would it be before a stable version of sqlite based on rust was available with comparable performance and fewer bugs than the c-based version?
(Seems likely to me that it would never happen.)
I think you'd be better off creating a sqlite competitor, that could start off much smaller with a much smaller feature and much less stringent performance requirements that, nevertheless, has enough for many common cases. Of course, you'd still have to convince people to use it over sqlite. If your main selling point is "significantly fewer bugs than sqlite" I don't think it's going to be very easy to make that true, rust or not.