Update to SQLite 3.45.0 introduces an issue where a required column is not passed into a table due to optimizations for the IN keyword

[Samuel-Roach]

Bug report

What operating system and version are you using?

version = 10.0.22631
build = 22631
platform = windows

What version of osquery are you using?

version = 5.12.0

What steps did you take to reproduce the issue?

Running the following query:

WITH a (
    path
) AS (
    SELECT
        path
    FROM services
    UNION
    SELECT
        path
    FROM startup_items
),
b (
    path
) AS (
    SELECT DISTINCT
        path
    FROM a
),
c (
    path,
    subject_name
) AS (
    SELECT
        b.path,
        ac.subject_name
    FROM b
    LEFT JOIN authenticode AS ac ON
        ac.path = b.path
)
SELECT DISTINCT
    a.path
FROM a
LEFT JOIN c ON
    a.path = c.path
WHERE c.subject_name NOT IN ('Microsoft Windows', 'Microsoft Windows Publisher');

What did you expect to see?

Results from the query. This is the seen behaviour in Osquery version 5.11.0.

What did you see instead?

W0305 11:44:30.440654  7540 virtual_table.cpp:975] Table authenticode was queried without a required column in the WHERE clause
W0305 11:44:30.442656  7540 virtual_table.cpp:986] Please see the table documentation: https://osquery.io/schema/#authenticode
Error: constraint failed

What is the issue?

I have investigated and found the root cause of the issue. It was introduced in SQLite version 3.43.0, Osquery version 5.12.0 will update to SQLite version 3.45.0. I have built Osquery with SQLite version 3.43.0 and seen the issue, and also with SQLite version 3.42.0 and not seen the issue.

An optimisation was introduced as part of the following check-in: https://www.sqlite.org/src/info/f544a8e47cdd5ad7. More specifically, previously TK_IN was simply returning WRC_Prune, however now it will call sqlite3WalkExpr(pWalker, pExpr->pLeft); beforehand. From my understanding, this is where we see the issue as the IN statement is now walked (and inadvertently now calling the authenticode table without the required column).

I have built Osquery with SQLite version 3.43.0, and with TK_IN back to just calling return WRC_Prune;, and I have seen that the issue is not present, which verifies this. For the moment it can be remediated by changing the last line to the following:

WHERE c.subject_name != 'Microsoft Windows' AND c.subject_name != 'Microsoft Windows Publisher';

However, as this is implying the same as NOT IN, they should be interchangeable without error.

[Smjert]

@Samuel-Roach Thanks for the writing and for catching this.
I have only given a cursory look; is it your understanding that sqlite is at fault and/or should we do something osquery side?

In the sqlite commit it seems this is an optimization done for a LEFT JOIN; is this also broken in other situations?

[Samuel-Roach]

@Smjert My understanding is that SQLite is not at fault, as the optimisation they have made is probably fair, albeit could be further scrutinised for validation of this.

In my opinion, something should be done on the osquery side. I'm not 100% on the interraction between SQLite and Osquery code; however, the concept of required columns for a table is part of osquery, and is not a core part of SQL. Therefore, osquery should make a change in order to accommodate for this optimization made in SQLite.

I'm under the impression from the release notes (https://www.sqlite.org/releaselog/3_43_0.html) that this could affect all types of JOIN, as the optimization this is in relation to is generalised to RIGHT and FULL joins. To verify this I have run the following changes to c table in the query above:

c (
    path,
    subject_name
) AS (
    SELECT
        b.path,
        ac.subject_name
    FROM b
    FULL JOIN authenticode AS ac ON
        ac.path = b.path
)

and

c (
    path,
    subject_name
) AS (
    SELECT
        b.path,
        ac.subject_name
    FROM b
    RIGHT JOIN authenticode AS ac ON
        ac.path = b.path
)

In both cases, the end result is as follows, although it takes a little longer to get there:

W0305 17:13:34.864069 12656 virtual_table.cpp:975] Table authenticode was queried without a required column in the WHERE clause
W0305 17:13:34.866068 12656 virtual_table.cpp:986] Please see the table documentation: https://osquery.io/schema/#authenticode
Error: constraint failed

The query in the initial bug was the minimal reproducible example I could create, and it seems very temperamental when changing any aspect of the query. E.g. Removing the DISTINCT in the main query will stop this from happening.

[directionless]

However, as this is implying the same as NOT IN, they should be interchangeable without error.

I wonder how #8263 intersects this.

[Samuel-Roach]

I think this issue might be present in earlier versions, but in a different form. I was experimenting further with using !=, and have found a use case where a call can be made to the authenticode table leading to the same error message in Osquery 5.11.0.

WITH a (
    path
) AS (
    SELECT
        path
    FROM services
),

b (
    path,
    subject_name
) AS (
    SELECT
        a.path,
        authenticode.subject_name
    FROM a
    INNER JOIN authenticode ON
        authenticode.path = a.path
)

SELECT DISTINCT
    a.path,
    b.subject_name
FROM a
LEFT JOIN b ON
    a.path = b.path
WHERE
    b.subject_name != 'Microsoft Windows';

Running this against Osquery 5.11.0 I see the following output:

W0311 11:27:26.173632 22456 services.cpp:124] 000000000340DF40: failed to query service description
W0311 11:27:26.231290 22456 services.cpp:124] 000000000340C58E: failed to query service description
W0311 11:27:26.254547 22456 services.cpp:124] 000000000340BC64: failed to query service description
W0311 11:27:26.270889 22456 services.cpp:124] 000000000340B4B8: failed to query service description
W0311 11:27:26.290596 22456 services.cpp:124] 000000000340A89C: failed to query service description
W0311 11:27:26.314883 22456 services.cpp:124] 0000000003409DFE: failed to query service description
W0311 11:27:26.381752 22456 virtual_table.cpp:975] Table authenticode was queried without a required column in the WHERE clause
W0311 11:27:26.385138 22456 virtual_table.cpp:986] Please see the table documentation: https://osquery.io/schema/#authenticode
Error: constraint failed

It would be worth noting that changing this to be

WHERE
    b.subject_name NOT IN ('Microsoft Windows');

also fails, however making the JOIN to authenticode in table b a LEFT JOIN results in the query working...

[Smjert]

During the office hours we said that we wanted to resolve this, or at least avoid the regression, by first trying to patch the sqlite source code, removing that optimization.
The problem though is that the code that the commit touches has been changed since then (since it's also from almost 1 year ago), and I'm not sure if it's ideal to revert.

Furthermore there's something that doesn't checks with me.
Interestingly enough the very first query in the issue doesn't cause any error in my tests, while the FULL JOIN and RIGHT JOIN do. But in those cases is to be expected.
EDIT: The first query does fail, made an error in the test, the reasoning on the other kind of joins stands though.

A RIGHT JOIN or a FULL JOIN requires for all the right table rows to be present in the result of the join. The only way one can obtain all results from authenticode is querying it without constraints; but this is not possible because path is required.
So the FULL and RIGHT JOIN example queries do not seem incorrect to me.

I can reproduce with your very last example though, which is interesting. But I wonder if there isn't something else we are missing.

[Smjert]

Something I just discovered is that it's possible to return SQLITE_CONSTRAINT from xBestIndex to say that the constraint is unusable.
This is documented in https://www.sqlite.org/vtab.html, in the "Return value" section. And even more clearly in "Enforcing Required Parameters On Table-Valued Functions", where it shows as an example a plan that's not acceptable for the function.

I tried it and it works; I think though the problem with this is when we are actually doing a query with no required constraint.
The problem is that the query returns with "Error: no query solution", which is not too helpful; but we have access to zErrMsg, that is a variable that can be set to bring an error back to the caller.

I haven't investigated further but we should also be able to distinguish the case of a plan not be valid due to a required constraint missing among valid plans, to avoid outputting the content of zErrMsg, and the case where the query actually failed due to that.

EDIT: Also for additional notes on this, since we talked about this specific thing during the office hours, when the xBestIndex plan does not contain a required column we set the cost to a high value we call kMaxIndexCost. The problem though is that this is not really the maximum cost possible, and this is why it still gets selected.
The documentation mentions about returning SQLITE_CONSTRAINT or setting the cost to infinity; the double infinity value, since estimatedCost is a double.

[zwass]

@Smjert great find! Looks like there is some attempt made to use this functionality but at a glance I can't tell if it's correct:

osquery/osquery/sql/virtual_table.cpp

Line 992 in 8ded5d5

return SQLITE_CONSTRAINT;

[Smjert]

@Smjert great find! Looks like there is some attempt made to use this functionality but at a glance I can't tell if it's correct:

osquery/osquery/sql/virtual_table.cpp

Line 992 in 8ded5d5

return SQLITE_CONSTRAINT;

Yeah the difference it's that it's in the xFilter, which simply makes the whole query fail, and it's after all the plan evaluation.
We need to filter plans in xBestIndex

[zwass]

Ah yes I had just noticed that. It makes sense and seems like a path forward!