mrigger

More information at https://modus-continens.com/.

From the report at https://abertschi.ch/default_public/ethz/graalphp/download.p...: "Experimental results indicate that our runtime reaches competitive results with performance gains of up to 859% compared to PHP 7. These preliminary results suggest that a Truffle-hosted PHP implementation might be significantly faster than existing language implementations."

For DBMS, the authors of the APOLLO system found the following [1]:

"Code coverage is a frequently used feedback mechanism in fuzzing engines [22, 27]. We found that this metric is not particularly useful for fuzzing DBMSs, since the core components of DBMS (e.g., query optimizer) already have high coverage (e.g., >95%) after running tens of queries."

[1] APOLLO: Automatic Detection and Diagnosis of Performance Regressions in Database Systems http://www.vldb.org/pvldb/vol13/p57-jung.pdf

Yes, you are right, the results are not comparable between DBMS that we tested. For MySQL, the large number of existing bugs prevented us from going further, and also testing more advanced functionality (like FTS). For SQLite (and DuckDB), bugs were typically fixed within hours, which is why we could comprehensively test them. For SQLite, we also tested three extensions (besides FTS, also R*Tree and DBSTAT).

I believe that the approaches that we designed could be implemented/extended to document-oriented DBMS. Since I don't have any experience with those DBMS, I have no intuition on whether the approaches would uncover any bugs.

Implementation-wise, supporting CouchDB and MongoDB in SQLancer would be feasible. SQLancer shares little infrastructure between the testing implementations for the individual DBMS, and thus imposes only few restrictions on them. We would definitely welcome implementations for any NoSQL DBMS in SQLancer!

Thanks for your interest! I'd love to test H2, but we are currently lacking the resources to do so. We've received a number of similar requests in the last couple of days and weeks. For each DBMS that we test, we need to add some logic to randomly generate databases and queries, since the SQL dialects typically differ. I've opened an issue in SQLancer's issue tracker for now: https://github.com/sqlancer/sqlancer/issues/23

Thanks! Here is one interesting example of a bug that was reported on the SQLite mailing list: https://www.mail-archive.com/sqlite-users@mailinglists.sqlit.... The SQL query that triggers the bug is rather complex. Interestingly, it was generated automatically: "I might not spell it like that myself, but a code generator would do it (and much worse!). This example was simplified from a query generated by a Django ORM queryset using `.exclude(nullable_joined_table__column=1)`, for instance."

When the user reported the bug, it had actually already been fixed on the latest SQLite3 trunk based on one of our bug reports. The query in our test case used a “NOT NULL NOT NULL” predicate, which is unnecessary complex as well: https://www.sqlite.org/src/tktview?name=c31034044b. We believe that this is interesting evidence that even “obscure” bugs matter in practice, for example, when the queries are automatically generated, as demonstrated above.

We automatically generate databases and queries. The main challenge is to verify that the query yields the expected result. To this end, we have designed and implemented three different approaches:

* Pivoted Query Synthesis (PQS): The main idea is to generate a query that is guaranteed to fetch a randomly-selected row, to which we refer as the pivot row. If the pivot row is not contained in the result set, we have detected a bug.

* Non-Optimizing Reference Engine Construction (NoREC): The idea is to transform a query so that it cannot be optimized effectively by the DBMS. By comparing the result set of the "optimized" query with the result set of the "unoptimized" query, we can detect bugs that affect the DBMS' query optimizer.

* Ternary Logic Partitioning (TLP): The main idea of this approach is that we can partition a given query into multiple "partitioning" queries, each of which computes a partition of the result, and to then combine these partitions to derive the same result as the original query. If the two results differ, we have detected a bug in the DBMS.

Thanks a lot! So far, we have considered only systems that are (partially) available in the open. Two of these are mainly developed commercially, namely CockroachDB and TiDB. We are glad that Cockroach Labs and PingCAP were indeed quite thankful for our testing efforts (e.g., see https://twitter.com/JordanALewis/status/1249689838686818304 for CockroachDB and https://twitter.com/PingCAP/status/1260678075714600968 for TiDB).

We will also consider testing DBMS with a DeWitt Clause in the future. For now, we have indirect evidence that our approaches could find bugs in Oracle. Specifically, we found a case in MySQL, which we consider a bug, but which was closed by the bug verifiers, partly because Oracle computes the same - we believe incorrect - result. Our bug report can be found here: https://bugs.mysql.com/bug.php?id=99182.

We believe that it is a bug, because:

* the invariants that we are testing using TLP, which is the approach that we used to find the bug, should hold for all DBMS;

* dropping the UNIQUE constraint would yield the result we would expect, and we believe that an index should never affect a query's result;

* an earlier version of MySQL computed the result we would expect;

* and DBMS that strive to support the MySQL SQL dialect, computed the result we would expect (e.g., TiDB).

Thank you! SQLite was indeed a challenging target. We could find and report many bugs in it only because all of our bugs were addressed very quickly (typically within a day). For some of the other DBMS that we tested, bugs were fixed slowly, and for some we also saw many unresolved bugs in their bug tracker, which is why we did/could not comprehensively test these DBMS.

Before we proposed our testing approaches, the state of the art of finding logic bugs was writing unit tests, which does not scale well, since it requires much manual effort. We believe that we provide the first practical approaches to automatically finding logic bugs. Companies have already started adopting them. For example, PingCAP implemented all three approaches that we proposed in https://github.com/chaos-mesh/go-sqlancer to test their DBMS TiDB.

A number of tools are available to test other aspects, like performance or for crash bugs. SQLsmith, for example, is one effective tool that allows finding crash bugs (see https://github.com/anse1/sqlsmith).

Many DBMS development teams use SQLsmith and other random query generators, which can effectively find crash bugs. In contrast, we designed and developed SQLancer to automatically find logic bugs, which are bugs that cause the DBMS to compute an incorrect result set (e.g., by omitting a record from the result set).