10 ms·
Great work!!! "SQLite is extensively tested with 100% branch test coverage. We discovered this vulnerability despite the tests, which raises the question: how
by gregors 4y ago
Great work!!!
"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?
- RHSeeger 4y agoIndeed. Tests do not tell you code is correct. They only tell you a list of ways it is not incorrect.
- aa-jv 4y ago.. and combined with coverage they also tell you what you are yet to test properly.
- fulafel 4y agos/properly//
- kevincox 4y agoActually: It tells you some things that are not tested properly. 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.
- Macha 4y agoYeah, coverage (or rather 100% - coverage) is basically a lower bound on what's not tested.
- masklinn 4y agoEven "coverage" is not enough, what 100% coverage? Lines? Branches? Paths?
- Macha 4y agoThat's my point, coverage (whatever your chosen metric) can only prove the absence of tests, not their presence 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%
- PathOfEclipse 4y agoI think this thinking is short-sighted. Tests increase your confidence that code is correct, and they are much cheaper to do that formal verification, which itself still requires a leap of faith that there is no bug in the formal verification system, its implementation in the compiler toolchain, or the assumptions made about the underlying hardware. 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.
- pclmulqdq 4y agoFormal verification also becomes practically impossible at a certain level of complexity. 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.
- hulitu 4y ago> Formal verification also becomes practically impossible at a certain level of complexity. Then reduce complexity.
- capableweb 4y agoUnsure if Property Testing would actually have found this issue, 2 billion bytes is a very large string and usually you wouldn't put the limit so high, the tests would run for too long. 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.
- ajross 4y agoYeah, exactly. People tend to misunderstand fuzzing, and think of it as "feeding random garbage at an API". Fuzzing, done with proper tooling, is automated coverage testing. You have a bounds overflow that depends on input data but only if condition A and B and C are true in the runtime state? Fuzzing will find it, almost always, by detecting the branching behavior of your code. 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.
- shagie 4y ago> Fuzzing would be a more appropriate measure to have found this issue SQLite has some fairly extensive fuzzing. https://www.sqlite.org/testing.html#fuzz_testing 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.
- chasil 4y ago
- XCSme 4y agoProving that a code always works means that there doesn't exist any case in which it breaks. You can't really prove something doesn't exist, unless the input domain is of fixed size and you can test all of it. In self-hosted technology, it is even trickier to prove something won't break, as there is so much potential variation in the hardware/software that your program runs on. There might even be stupid edge-cases, like the program failing only when the device it runs on is upside-down, or placed at high altitude, etc.
- rowanG077 4y agoYou can prove things even if then input domain has infinite size. For example n < n + 1 is always true. It's trivial to prove this. Yet the n can have infinite different values.
- naikrovek 4y agoIs this what "formal verification" is? That seems very hard for software that accepts arbitrary input. I understand formal verification, a bit, in terms of FPGA design, but not software.
- mrcus 4y ago“Program testing can be used to show the presence of bugs, but never to show their absence!”
- perlgeek 4y ago> how did the tests miss it? 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.
- insanitybit 4y agohttps://www.sqlite.org/testing.html#mcdc https://www.sqlite.org/testing.html#mcdc 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.
- taeric 4y agoI don't think that tracks. Consider: if (a) { doA(); } if (b) { doB(); } With (a,b) as (true, false) and (false, true), you satisfy every outcome of each decision test, but you never tested "doA()" and "doB()" at the same time. 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) that you test changing the values of a and b independently to show that either one of them can cause the check to pass.
- insanitybit 4y agoBy "this" I meant what I linked, not "what you just said". I realize in retrospect that I was unclear. I'm not sure if their approach would imply satisfying the (true, true)/ (false, false) case given that they are separate branches.
- taeric 4y agoRight, but I think that is what the original poster meant. There is a "path" through my example that hits both "doA()" and "doB()." And having 100% branch coverage doesn't necessarily get you there. Even under the stricter rule that they are using.
- paulmd 4y ago> Tests only validate known behavior. They didn't have a test that exercised a large string. 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.
- rowanG077 4y agoA function in a programming langauge is nothing more then a spec. Programming is writing or translating the specification.
- hulitu 4y agoWelcome to SW testing. Testing for limits is a no go. Testing for random input is a no go.