How SQLite Is Tested
sqlite.org
sqlite.org
Static analysis has not proven to be especially helpful in finding bugs in SQLite. Static analysis has found a few bugs in SQLite, but those are the exceptions. More bugs have been introduced into SQLite while trying to get it to compile without warnings than have been found by static analysis.
Also, having these tools, but no coding rules by code contributors, enforced with real code-reviews and reviewer(s), will also deliver 'not worth it' results. Its a process, not a chisel.
Sure, it's better to catch them up front. But catching them later is still extremely valuable.
This speaks more to the maturity and robustness of the SQLite codebase than it does of static analysis as a type of tool.
Static Analysis is very useful in the development phase of a project where you can treat them effectively as compiler warnings if your build system is setup that way.
...and that isn't to say that its not worth still using SA on mature codebases, just because a codebase is mature does not indicate its quality.
SA will capture issues related to the implementation but in itself it has no knowledge of application-specific behaviour.
Tests on the other hand do have application-specific knowledge and this is where their value lies.
Note also:
> We want verification to be about proving absence of bugs, not about finding bugs
A more interesting comparison would be between the most powerful/restrictive static analyses vs. the most powerful dynamic analyses.
Every release of FreeRADIUS (http://freeradius.org) gets run through three different static analysis tools. They each find slightly different things.
At this point, the bulk of issues they find are false positives. Addressing those doesn't create bugs, and I'm not sure why it would.
We found Coverity to be prohibitively expensive; but unfortunately there isn't any real alternative!
Anything that changes behaviour could create bugs. Here is an example
signed bar = something_possibly_negative();
if(some_case) {
bar = calc_returning_unsigned_where_MSB_is_an_error_flag();
if(bar < 0)
return ERROR;
}
// now bar is valid, whether negative or positive.
long long bar = something_possibly_negative();
For more in this vein see: http://ithare.com/best-practices-vs-witch-hunts/
Fuzzing found real actionable bugs in SQLite. As I consider fuzzing a variant of static checking (it executes a subset of symbolic evaluation space), I consider the result above as a resounding success of static methods.
Also please look at the date when the phrase was added: https://web.archive.org/web/20090205181900/http://sqlite.org... - it's 2009, the very first version of the page! And they didn't change it a bit since.
Basically you base your damnation on an outdated information.
You cannot "examine the code" without executing it, partially or in full, with some input or intermediate values or (symbolically) with all of them.
I am sure I sound contrary to "common definitions" - so be it. I also think that dynamic typing is a subset of static typing, more or less for the same reason.
It is entirely possible to break a stream of text down into symbols and examine the relationship of those symbols without evaluating (i.e. executing) them. It is not really necessary or possible to know their meaning/definition at all, only their "shape" or the "part of speech" that they represent.
In the simplest form, static analyzers are a set of heuristic pattern matchers that a stream of text is sent through. It might get fancy and build an AST first, but that still does not constitute execution or evaluation in the technical sense.
You can prove that sqlite_exec("create table a ...insert into a ...select * from a where ...") is equal to, say list ["gaga", "gugu"], given supercompiler that is powerful enough. The paper above proves properties up to termination of programs, so it will prove (Haskell) sum [1..] == sum (map (+1) [0..]) as equal (up to computation of the lists).
Would you consider this an example of static analysis?
If answer is "yes", bear in mind that supercompilation includes evaluation of the programs - basically, supercompiler executes them, looking for states it already seen.
I also would like to hear reasons why if answer is "no".
It's pretty simple: if you execute the program code, whether directly on a processor or in an virtual processor/emulator, it's dynamic analysis. Otherwise it's a variant of static analysis.
https://bugzilla.mozilla.org/show_bug.cgi?id=581946
The SQLite guy were ridiculously responsive and added all sorts of tests around the fix.
It's not every day you can say you found and helped troubleshoot a bug that literally could be affected 100s of millions of users!
In fact those test suites being so large is possibly part of the problem. Sounds like they are being overly prescriptive in their testing, which is why it's so damn fussy about the order commands are executed without causing it to leak memory left right and center.
You're going to have to justify that a bit more, that would not be the overwhelming experience around these parts.
Not to say its perfect but its the weight of evidence is in SQLites favour here.
On a fairly regular basis. Google gives:About 57,400 results
So I'm definitely not the only one.
Transactions are particularly bad. One bug I ran into earlier in the year would gobble up 12gb of system ram trying to search and insert a few 10s of mb of text, just because it was leaving prepared statements laying around without telling me.
... thanks for reporting it.
(https://www.sqlite.org/malloc.html)
"No memory leaks. The application is responsible for destroying any objects it allocates."
"Robust against allocation failures. If a memory allocation ever fails (that is to say, if malloc() or realloc() ever return NULL) then SQLite will recover gracefully."
And I see plenty of reported examples and work arounds. Even yum has been suffering from it for years.
http://forums.fedoraforum.org/showthread.php?t=260195
http://www.pvangsgaard.com/2016/03/16/yum-error-database-dis...
All I said is the databases are temperamental. If you do anything "unexpected" it breaks. Numerous ways and often. Most of the bugs I've seen would be easily picked up with non deterministic testing. (Leaking result sets and prepared statements for example) - which is how I found them.
The testing codebase can only be that huge if they are all deterministic tests.
Trouble with deterministic tests is they miss all the edge cases and bugs persist for a long long time.
The transaction stuff is particularly bad. Gobbles memory without a care in the world till it either runs out and performance drops to near zero or fails and corrupts the database.
So everyone is forced to break transactions they would prefer to be atomic into multiple smaller ones.
These aren't things that should need a specific test case making in c, and many of the problems are horrific optimisation problems rather than show stoppers.
My point is. For all those kloc of testing, the sqlite code is definitely not what I would call robust.
How long has sqlite been reporting "out of memory" just because a database failed to open for some reason?
The biggest problem seems to be right here:
OOM testing is accomplished by simulating OOM errors.
I.e. not simulated in a real way. Which is silly when it is so easy to generate them.
"The application is responsible for destroying any objects it allocates"
...smells like user error to me.
e.g. "the application must use sqlite3_finalize() on every prepared statement and sqlite3_close() on every database connection "
I suggest that if you want to continue to assert that SQLite is not robust, you have to show us your code.
Because the number of cases where finalize doesn't destroy them or calling finalize on a closed prepared statement (supposed to be a harmless noop) crashing it completely seems fairly common. Yum is open source. A big chunk of the sqlite tests are not. With plenty of examples of yum sqlite databases becoming corrupt and needing to be rebuilt from scratch why would you need my code. Yum is infinately more important to those millions of users than anything I write.
So yeah, great when it works, but testing nothing to be proud of is definitely my experience.
Pay for this: TH3 is free to SQLite Consortium members and is available by license to others.
No chance.
That default encryption is locked behind walls doesn't inspire cooperation either.
rather than: for 1 to 1000 testCommand(random 1 to 6)
6 lines instead of 2, and less robust testing.
With today's mindset of letting users do most of the testing, it is actually quite common to find bugs like that.
However, really nice job of the SQLite devs to follow through so fast.
Your definition of "common" is quite different than mine. There are only a handful of packages which are used by "100s of millions of users."
If finding and helping to troubleshoot a bug is "common" then that's, what, 1 million user-reported bugs? Mozilla's bug tracker has only 1.3M entries.
Now, I've submitted a bug to Mozilla. But I've submitted far more bugs to smaller packages, which don't have 100s of millions of users.
So I think it's not that "common to find bugs like that."
Your definition of "only" is quite different than mine. :)
Dozens of these bugs have been reported by me (same for Chromium) and I'm not even that much of a bug hunter. So yeah, I'd say it's common.
Given that some of those are developers, or people like you, who report dozens of bugs, the odds of a user reporting a bug is well less than 1:100. I submit that it's far less.
The odds of someone finding and helping to troubleshoot the bug are even lower.
By comparison, most of the bug report I've sent in are to packages with fewer than 10,000 users.
If I hadn't traced out the SQL statement that was causing the segfaults I think it might not have been found!
I wasn't sure how to interpret it, but then they mention that it's 40100 distinct test cases, parameterized. I would have rephrased it as "40K of parameterized test cases".
> 4. The "speedtest1.c" program estimates the performance of SQLite under a typical workload.
> 5. The "mptester.c" program is a stress test for multiple processes concurrently reading and writing a single database.
> 6. The "threadtest3.c" program is a stress test for multiple threads using SQLite simultaneously.
I think it's ridiculous that people make proprietary test suites. In my opinion, test suites shouldn't even be copyrightable let alone made proprietary. A test suite is used to define what the precise interface of an API is, it's just a piece of code rather than a standards document.
EDIT: To be clear, the actual test framework might be copyrightable. But the actual test cases should not be IMO. It's also a shame that a free software project requires using proprietary software in order to practically test it.
Additionally, there are three major test suites for SQLite, and two of them (with a test coverage that still leaves most other open source projects in the dust) are open source and free.
I can live with paying members getting additional testing possibilities.
A test case is structured around an assertion of facts. To that extent, it is not copywriteable.
But other parts of a test case, which have creative thought, are copywriteable. This can include the test name and any comments.
If you manage to get ahold of the test suite, strip out all of the assertions, and create a new test system which does the same tests, then you might get a lawyer to agree that it's not copyright infringement.
Even then, a test case might use something which is under copyright. For example, it may contain a poem, and check if the length of the poem is as expected.
That said, if there were no copyright (let's say it's the 1960s, before copyright was extended to software), it could still be covered as a trade secret, and protected under confidentiality agreements. That is, copyright affects what you can do once you get the software, but you might not be able to get it in the first place.
Therefore, while I understand and even empathize with your argument, I don't think you should based the argument in copywriteability.
Instead, I think you should look to Stallman's argument for why documentation for a free software project should itself be free. If you modify the code, you should be able to modify the documentation instead of starting from scratch. https://www.gnu.org/software/gsl/manual/html_node/Free-Softw...
By analogy, if you modify the code, you should be modify the test suite instead of starting from scratch.
One obvious solution is to start your own GNU-licensed SQLite test suite, to, ahem, fight against the software hoarders. ;)