Stranger Strings: An exploitable flaw in SQLite

Re:Stranger Strings: An exploitable flaw in SQLite by perlgeek on Tuesday October 25, 2022 @12:52PM (#33333127)

> 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.

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by insanitybit on Tuesday October 25, 2022 @01:37PM (#33333720)

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.

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by taeric on Tuesday October 25, 2022 @04:42PM (#33335878)

I 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.

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by insanitybit on Tuesday October 25, 2022 @04:45PM (#33335926)

By "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.

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by taeric on Tuesday October 25, 2022 @04:48PM (#33335961)

Right, 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.

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by insanitybit on Tuesday October 25, 2022 @04:49PM (#33335977)

Yep, we're on the same page.

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by taeric on Tuesday October 25, 2022 @05:15PM (#33336269)

Coming back to this, I understand your previous post about "this" now. :D Apologies on misunderstanding that the first time around!

[ Parent | on HN ]

Re:Stranger Strings: An exploitable flaw in SQLite by kyralis on Tuesday October 25, 2022 @09:20PM (#33338506)

> 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.

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.

[ Parent | on HN ]