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.

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.

https://www.sqlite.org/famous.html

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.

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.

[1]: https://www.sqlite.org/famous.html

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.

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.

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.

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.