2,616 karma · joined October 16, 2012
(1) The 100% branch test coverage requirement forces us to remove unreachable code, or else convert that code into assert() statements, thereby helping to remove cruft.
(2) High test coverage gives us freedom to refactor the code aggressively without fear of breaking things.
So, if your developers are passionate about long term maintainability, then having 100% MC/DC testing is a big big win. But if your developers are not interested in maintainability, then forcing a 100% MC/DC requirement on them does not help and could make things worse.
(1) One test uses compiler and preprocessor options set up to measure coverage. This is not so much a test of SQLite itself as it is a test of the test logic, to verify that the testing provides 100% MC/DC.
(2) The second test runs with assert(), ALWAYS(), and NEVER() enabled. This is like a unit test. It verifies internal assumptions and state, at the expense of running 3x slower.
(3) Finally, we build as for delivery and test once again. This is the string test, where we "test what we fly".
All three test runs must give the same answer (modulo performance) before a release.
During day-to-day development work, we usually run (2), but occasionally toss in a (1) or (3) just to confirm that we haven't introduced any gaps in test coverage, or bugs that are masked by the debugging logic.
So you are correct that you should not do all your testing using one configuration and then deliver a different build. But that does not mean you can't have extra logic in your code that helps do unit testing and debugging during development and which is excluded from release builds. You just need to make sure that you rerun all tests in the release configuration.
An example is the "About branch begin-concurrent-pnu-wal2" at the top of the page https://www.sqlite.org/src/timeline?r=begin-concurrent-pnu-w... - the page shows all check-ins for the branch, and the Wiki at the top gives a summary of what that branch is about.
Another example is the detailed discussion in the "About" section for check-in https://www.sqlite.org/src/info/718ead555b09892f - important information that records the thinking about this commit but which seems too prolix for a check-in comment.
Let me know your thoughts on this idea.
When the design of a system makes something difficult, people tend to avoid doing that thing. The Git data design makes extracting some kinds of historical information difficult, with the result that many common tools (ex: GitHub) don't bother. This reduces the information available to users, resulting in reduced situational awareness.
I make no claim that Fossil is perfect in this regard. My only claim is that Fossil is better.
Whether you use Fossil or not, I don't much care. But I really would like you to understand some of the features of Fossil that (I think) make it better than Git, and perhaps start adding some of those features to your favorite VCS, be it Git or something else. Understand the general concepts, then port those concepts to other systems.
The fossil-scm.org server gets between 1500 and 2000 distinct human visitors per day on weekdays. (Lower traffic on weekends. Robots are excluded from the count. "distinct" means visitors having different IP addresses.) This is perhaps orders of magnitude less than git-scm.org (I'm guessing - anybody have stats?) but it is also non-trivial. With ~1750 visitors per day somebody must be using it. And I would guess that most actual users do not visit the site daily. (When was the last time you visited git-scm.org?)
FWIW, today has already seen in excess of 10,000 distinct human IPs, likely due to this HN post.
(1) The coverage testing used by SQLite is very good at finding problems that occur when the system is used as it was intended. Fuzz testing is better for finding vulnerabilities that can be exploited by a hacker. The 100% MC/DC testing in SQLite is very useful in ensuring that the code does what is intended for sane inputs. And 100% MC/DC helps prevent us from breaking things as we evolve and enhance the code. But the MC/DC testing is less useful at fending off attackers.
(2) The magellan vulnerability exploits a bug in an SQLite extension, FTS3, which while very well tested, is not testing to 100% MC/DC. (See the second sentence at https://www.sqlite.org/testing.html#test_coverage)
Hence my takeaways from this episode include that I need to extend 100% MC/DC testing to all commonly used extensions in SQLite, including FTS3, FTS5, and RTREE, and I need to improve fuzz testing throughout SQLite but especially in extensions.
Advocates of "safe" language correctly observe that this particular problem would not have happened if SQLite were written in (say) Rust. Rewriting SQLite in Rust in not (yet) a viable solution. (See https://www.sqlite.org/whyc.html) But I can start moving SQLite in that direction, and perhaps make use of techniques taken from safe languages to improve its resistance to attack.
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.
The new SQLITE_DBCONFIG_DEFENSIVE features is more of a defense-in-depth, designed to head off future vulnerabilities by making shadow-tables read-only to ordinary SQL, along with some other restrictions. If you have an application that allows potential attackers to run arbitrary SQL, then the use of SQLITE_DBCONFIG_DEFENSIVE is recommended. It is not required. We still consider it a serious bug if somebody is able to find an exploit even with SQLITE_DBCONFIG_DEFENSIVE turned off. But that setting reduces the attack surface, making future bugs less likely.
The vulnerability only exists in applications that allow a potential attacker to run arbitrary SQL. If an application allows that, it is usually called an "SQL Injection" vulnerability and is the fault of the application, not the database engine. The one notable exception to this rule is WebSQL in Chrome.
I put up https://www.sqlite.org/security.html recently to serve as guidance for people who want to live on the edge and give unrestricted SQL access (or unrestricted database file access) to potentially hostile attackers. That page is a work in progress. More could be said. For example, it is probably also a good idea to use various obscure APIs to limit the length of SQL statements or the amount of memory that can be used, to avoid DOS attacks. I'll keep improving the document as I have time.
Our intent is that SQLite should be secure against these kinds of attacks. We have spent years fuzzing it to try to find these problems. But the thing is, we never configured a fuzzer in such a way that it might start modifying the shadow tables of FTS3, and so we missed this one. Moral: never underestimate the ingenuity of a motivated gray-hat.
The Chrome people have recently starting fuzzing SQLite database files on Google's infrastructure. We had previously only fuzzed database files on our own workstations. It's amazing the number of new problems you can find when you run a fuzzer at scale. :-) A few more problems have been fixed. We are not aware of any exploits. And in particular, if you follow the advice of the article above and "PRAGMA quick_check" untrusted database files or set "PRAGMA cell_size_check=ON" then none of the recently found and fixed issues are reachable.
Why not? Isn't the whole point of a code-of-conduct to describe the ethical values of a community? And isn't all ethics a kind of religion, even if it does not always make explicit mention of deity? From that point of view, every code-of-conduct is a credo, by definition.
Suppose I were to go in and edit St. Benedict's rules to omit all reference to "God" and "Christ", leaving behind such things as "do not steal", "do not nurse a grudge", "do not return evil for evil", and so forth. Would the document be acceptable to you then? If not, then what exactly are the ground rules for codes of conduct? And who makes those rules? Is there a code-of-conduct for codes of conduct?
If you answer "Yes" to the previous, then are you suggesting that you and/or I are somehow wiser than Benedict of Nursia, such that we are able to edit and improve upon his work?
While all that was happening 10+ years ago, I learned about DO-178B. I have a copy of the DO-178B spec within arms reach. And I found that, unlike most other "quality" standards I have encountered, DO-178B is actually useful for improving quality.
I originally developed the TH3 test suite for SQLite with the idea that I could sell it to companies interested in using SQLite in safety-critical applications, and thereby help pay for the open-source side of SQLite. That plan didn't work out as nobody ever bought it. But TH3 and the discipline of 100% MC/DC testing was and continues to be enormously helpful in keeping bugs out of SQLite, and so TH3 and all the other DO-178B-inspired testing and refactoring of SQLite has turned out to be well worth the thousands of hours of effort invested.
The SQLite project is not 100% DO-178B compliant. We have gotten slack on some of the more mundane paperwork aspects. Also, we aggressively optimize the SQLite code base for performance, whereas in a real safety-critical application the focus would be on extreme simplicity at the cost of reduced performance.
However, if some company does call us tomorrow and says that they want to purchase a complete set of DO-178B/C Level-A certification artifacts from us, I think we could deliver that with a few months of focused effort.
SQLite tries to only uses indexes in situations where they help the query run faster. SQLite is not limited in its use of indexes. It is just that the use of multiple indexes for a single FROM-clause term is rarely helpful.
SELECT * FROM tab WHERE key1=1 AND key2 IN (2,3,4,5);
The insight here is that a multi-column key value can be resolved using a single binary search. It is not a sequence thing where we first look for the key1=1 and then do a separate lookup in a subtree for key2. Both key1 and key2 are resolved in the same binary search.
I don't know for sure what this means, but it sounds like it is incorrect.