You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
It would be great to implement test case reduction strategies in SQLancer itself. The advantage of doing this in SQLancer, rather than an external tool like C-Reduce, is that we have all the information on whether a specific bug is still triggered (e.g., that two queries should yield the same result) and that the reduction can likely go further than when having an external interestingness test (e.g., since a predicate in the WHERE condition of two queries can be reduced simultaneously).
Hi @mrigger, I read about your research which I found really interesting (kudos!), as well as others from your research group at the ETH.
I would like to help here, can you provide some guidance on this task?
I see also that in the README.md you are speaking about a SQL specific reducer that you were developing already
Thanks for your interest and your kind words, @nicdard!
A way would be to start with reducing statements only. I previously prototyped a very hacky implementation, which I just uploaded at 66f57c6, for SQLite and the NoREC oracle. The core idea is to have a class FoundBugException that is thrown once a bug is found and that contains a Reproducer which is the interestingness test (i.e., for NoREC comparing whether the optimized and unoptimized queries compute the same result) that can be replayed on the current, possibly reduced, database. The current implementation of the reducer tries to drop statements and some hard-coded keywords. The implementation is hacky because I did not write the main logic of the reducer and logger in a clean way. I hope it is still useful to get started (and feel to copy&paste any code that seems useful). In the pom.xml file, I specified an old version of SQLite, so you can conveniently test the reducer.
A good way to go forward would be to first implement such a reducer that removes statements only for a single DBMS, then try to generalize it to multiple DBMSs (e.g., by implementing a common interface), and then progress to reduce also expressions, keywords, etc. A good candidate might be DuckDB, since I believe that the developers might appreciate this (CC @hannesmuehleisen @Mytherin).
For a quick feedback cycle, it might be helpful to create small pull requests (e.g., one for adding the reproducer class and implementing it for an oracle or oracles of a database).
Sorry for the delay, I was under pressure at work, since I am finishing my internship.
Thank you very much for the guidance and the code. I have two questions more:
how do you apply C-Reduce to reduce the tests? Can you provide an example?
I have tried to run the branch you provided, but the FoundBugException is never thrown, since the execution is always failing before an actual bug is discovered due to a SQLite exception: org.sqlite.SQLiteException: [SQLITE_ERROR] SQL error or missing database (near "NULLS": syntax error). Is there a way that you know to avoid this, for example using a different version of SQLite? I have noticed that with version 3.36 this error is not thrown.
Also I find that implement this via small pull request is a great way to go :)
I have tried to run the branch you provided, but the FoundBugException is never thrown, since the execution is always failing before an actual bug is discovered due to a SQLite exception: org.sqlite.SQLiteException: [SQLITE_ERROR] SQL error or missing database (near "NULLS": syntax error). Is there a way that you know to avoid this, for example using a different version of SQLite? I have noticed that with version 3.36 this error is not thrown.
how do you apply C-Reduce to reduce the tests? Can you provide an example?
For example, you can still check whether the output contains an unexpected error (including the string malformed) using an (ugly) bash script that you pass to C-Reduce like this:
The goal of the reducer would be to have a SQLancer-internal replacement of C-Reduce.
I have tried to run the branch you provided, but the FoundBugException is never thrown, since the execution is always failing before an actual bug is discovered due to a SQLite exception: org.sqlite.SQLiteException: [SQLITE_ERROR] SQL error or missing database (near "NULLS": syntax error). Is there a way that you know to avoid this, for example using a different version of SQLite? I have noticed that with version 3.36 this error is not thrown.
As @oraluben pointed out above, I forgot to mention that --test-nulls-first-last=false needs to be used for this old version of SQLite.
Moving a conversation from PR#597 to here. The FoundBugException idea is great for showing that we found an actual bug instead of hitting some other snag that needs to be ignored, but has one fatal problem: exceptions cannot be generic. As a result, the reproducer inside the exception can't be generic.
To me, the real problem is that we're using exceptions instead of return statements. We could resolve this by having TestOracle.check() return a Reproducer<G extends GlobalState> instance on finding a bug. The problem there is that there are many classes that implement TestOracle that would have to be refactored. I don't think any of us want to see a refactoring quite that big just for this case.
Another option is to add a method to TestOracle that yields the last Reproducer. That would require some refactoring, but only to supply type information. Then the ProviderAdapter could find the reproducer if it's available.
Then there are less clean options, like adding a generic method to TestOracle to return a Reproducer, but provide the GlobalState class it's expected to use. If the two match then return the Reproducer, and if not either return Null or throw an exception. I'm not sure that's a great option, and it's certainly not obvious, but it means not refactoring any other classes.
Otherwise, I'm open to ideas. Basically, we need some channel to return to ProviderAdapter the Reproducer with the generic type info intact. Let me know if you have any other ideas on how we can do that!
Thanks for the summary of the problem and potential ways of going forward! I think either letting TestOracle.check() return a Reproducer<G extends GlobalState> as a cleaner way, or the generic method as a faster way seem reasonable to me.
To me, the real problem is that we're using exceptions instead of return statements.
Besides TestOracles, also other components can report bugs. We found, for example, bugs that were triggered when reading the schema or connecting to a database. For now, I think it makes sense to consider only logic bugs found by the TestOracles, but it would be great to consider how we could create Reproducers also in such scenarios in the future.
Thanks for the summary of the problem and potential ways of going forward! I think either letting TestOracle.check() return a Reproducer<G extends GlobalState> as a cleaner way, or the generic method as a faster way seem reasonable to me.
Are you sure that suck a big refactor is ok? I can probably do something this week, but it might be a big PR!
To me, the real problem is that we're using exceptions instead of return statements.
Besides TestOracles, also other components can report bugs. We found, for example, bugs that were triggered when reading the schema or connecting to a database. For now, I think it makes sense to consider only logic bugs found by the TestOracles, but it would be great to consider how we could create Reproducers also in such scenarios in the future.
Yea, I don't really know much about those scenarios. If you feel the Reproducer can be used for that, then bonus :)
I'm trying to think of how to encode each of the four possible results of a call to check():
No error found. Return Null ?
Possible bug found, but no reproducer available. Throw an exception is the old way, which we could keep for backwards compatibility. Is that the right move going forward? Or maybe an Optional without the Reducer?
Possible bug found, with reproducer. As above, return the Reproducer itself, or Optional?
IgnoreMeException. Throw the way it is now? Or try to get rid of exceptions entirely?
For backward compatibility and quick prototyping, we could add a default method like checkWithReproducer in TestOracle that calls check() and returns empty. We could then also leave the Exception in the signature and not reduce bugs for implementations that do not override checkWithReproducer.
For the new logic, perhaps we can have checkWithReproducer return Optional<Reducer> that returns either the state to reproduce a bug, if one is found, and empty otherwise. New implementations will then implement checkWithReproducer rather than check, which we can subsequently deprecate and remove.
Do you think this makes sense? Not sure if I understood you correctly.
If you still have some time, the most useful thing would be to write the reduced test cases to a file, perhaps in a log-reduced directory adjacent to the current log directory.
Activity
nicdard commentedon Aug 27, 2021
Hi @mrigger, I read about your research which I found really interesting (kudos!), as well as others from your research group at the ETH.
I would like to help here, can you provide some guidance on this task?
I see also that in the README.md you are speaking about a SQL specific reducer that you were developing already
mrigger commentedon Aug 30, 2021
Thanks for your interest and your kind words, @nicdard!
A way would be to start with reducing statements only. I previously prototyped a very hacky implementation, which I just uploaded at 66f57c6, for SQLite and the NoREC oracle. The core idea is to have a class
FoundBugExceptionthat is thrown once a bug is found and that contains aReproducerwhich is the interestingness test (i.e., for NoREC comparing whether the optimized and unoptimized queries compute the same result) that can be replayed on the current, possibly reduced, database. The current implementation of the reducer tries to drop statements and some hard-coded keywords. The implementation is hacky because I did not write the main logic of the reducer and logger in a clean way. I hope it is still useful to get started (and feel to copy&paste any code that seems useful). In thepom.xmlfile, I specified an old version of SQLite, so you can conveniently test the reducer.A good way to go forward would be to first implement such a reducer that removes statements only for a single DBMS, then try to generalize it to multiple DBMSs (e.g., by implementing a common interface), and then progress to reduce also expressions, keywords, etc. A good candidate might be DuckDB, since I believe that the developers might appreciate this (CC @hannesmuehleisen @Mytherin).
For a quick feedback cycle, it might be helpful to create small pull requests (e.g., one for adding the reproducer class and implementing it for an oracle or oracles of a database).
nicdard commentedon Sep 4, 2021
Sorry for the delay, I was under pressure at work, since I am finishing my internship.
Thank you very much for the guidance and the code. I have two questions more:
FoundBugExceptionis never thrown, since the execution is always failing before an actual bug is discovered due to a SQLite exception:org.sqlite.SQLiteException: [SQLITE_ERROR] SQL error or missing database (near "NULLS": syntax error). Is there a way that you know to avoid this, for example using a different version of SQLite? I have noticed that with version 3.36 this error is not thrown.Also I find that implement this via small pull request is a great way to go :)
oraluben commentedon Sep 5, 2021
Maybe give
--test-nulls-first-last=falsea try?mrigger commentedon Sep 5, 2021
For example, you can still check whether the output contains an unexpected error (including the string
malformed) using an (ugly) bash script that you pass to C-Reduce like this:The goal of the reducer would be to have a SQLancer-internal replacement of C-Reduce.
As @oraluben pointed out above, I forgot to mention that
--test-nulls-first-last=falseneeds to be used for this old version of SQLite.kshehata commentedon Nov 27, 2022
Moving a conversation from PR#597 to here. The FoundBugException idea is great for showing that we found an actual bug instead of hitting some other snag that needs to be ignored, but has one fatal problem: exceptions cannot be generic. As a result, the reproducer inside the exception can't be generic.
To me, the real problem is that we're using exceptions instead of return statements. We could resolve this by having TestOracle.check() return a Reproducer<G extends GlobalState> instance on finding a bug. The problem there is that there are many classes that implement TestOracle that would have to be refactored. I don't think any of us want to see a refactoring quite that big just for this case.
Another option is to add a method to TestOracle that yields the last Reproducer. That would require some refactoring, but only to supply type information. Then the ProviderAdapter could find the reproducer if it's available.
Then there are less clean options, like adding a generic method to TestOracle to return a Reproducer, but provide the GlobalState class it's expected to use. If the two match then return the Reproducer, and if not either return Null or throw an exception. I'm not sure that's a great option, and it's certainly not obvious, but it means not refactoring any other classes.
Otherwise, I'm open to ideas. Basically, we need some channel to return to ProviderAdapter the Reproducer with the generic type info intact. Let me know if you have any other ideas on how we can do that!
mrigger commentedon Nov 27, 2022
Thanks for the summary of the problem and potential ways of going forward! I think either letting
TestOracle.check()return aReproducer<G extends GlobalState>as a cleaner way, or the generic method as a faster way seem reasonable to me.Besides
TestOracles, also other components can report bugs. We found, for example, bugs that were triggered when reading the schema or connecting to a database. For now, I think it makes sense to consider only logic bugs found by theTestOracles, but it would be great to consider how we could createReproducers also in such scenarios in the future.kshehata commentedon Nov 27, 2022
Are you sure that suck a big refactor is ok? I can probably do something this week, but it might be a big PR!
Yea, I don't really know much about those scenarios. If you feel the Reproducer can be used for that, then bonus :)
kshehata commentedon Nov 27, 2022
I'm trying to think of how to encode each of the four possible results of a call to
check():mrigger commentedon Nov 27, 2022
For backward compatibility and quick prototyping, we could add a default method like
checkWithReproducerinTestOraclethat callscheck()and returnsempty. We could then also leave theExceptionin the signature and not reduce bugs for implementations that do not overridecheckWithReproducer.For the new logic, perhaps we can have
checkWithReproducerreturnOptional<Reducer>that returns either the state to reproduce a bug, if one is found, andemptyotherwise. New implementations will then implementcheckWithReproducerrather thancheck, which we can subsequently deprecate and remove.Do you think this makes sense? Not sure if I understood you correctly.
kshehata commentedon Nov 28, 2022
Added a preview of the refactoring changes in #624
kshehata commentedon Dec 4, 2022
Now that we've merged in #624, should we get some feedback, or perhaps look at expanding to new test oracles?
mrigger commentedon Dec 5, 2022
If you still have some time, the most useful thing would be to write the reduced test cases to a file, perhaps in a log-reduced directory adjacent to the current log directory.
sachinnandan commentedon Mar 27, 2023
Is it solved ?? @mrigger
committed to the issue sqlancer#333