← 输入框|github.com|刷新
Skip to content

Automatic test case reduction #333

Open

Description

@mrigger

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

See:

Activity

  1. nicdard commented on Aug 27, 2021

    @nicdard

    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

  2. mrigger commented on Aug 30, 2021

    @mrigger
    ContributorAuthor

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

  3. nicdard commented on Sep 4, 2021

    @nicdard

    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 :)

  4. oraluben commented on Sep 5, 2021

    @oraluben
    Collaborator
    • 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.

    Maybe give --test-nulls-first-last=false a try?

  5. mrigger commented on Sep 5, 2021

    @mrigger
    ContributorAuthor
    • 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:

    #!/bin/bash
    
    [ -f test.db ] && rm test.db
    
    sql=$(cat test.sql);
    
    output1=$(echo "${sql}" | /home/manuel/sqlite/sqlite3 test.db 2>&1)
    echo "$output1" | grep -w "malformed" >/dev/null 2>&1
    

    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.

  6. kshehata commented on Nov 27, 2022

    @kshehata
    Contributor

    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!

  7. mrigger commented on Nov 27, 2022

    @mrigger
    ContributorAuthor

    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.

  8. kshehata commented on Nov 27, 2022

    @kshehata
    Contributor

    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 :)

  9. kshehata commented on Nov 27, 2022

    @kshehata
    Contributor

    I'm trying to think of how to encode each of the four possible results of a call to check():

    1. No error found. Return Null ?
    2. 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?
    3. Possible bug found, with reproducer. As above, return the Reproducer itself, or Optional?
    4. IgnoreMeException. Throw the way it is now? Or try to get rid of exceptions entirely?
  10. mrigger commented on Nov 27, 2022

    @mrigger
    ContributorAuthor

    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.

  11. kshehata commented on Nov 28, 2022

    @kshehata
    Contributor

    Added a preview of the refactoring changes in #624

  12. kshehata commented on Dec 4, 2022

    @kshehata
    Contributor

    Now that we've merged in #624, should we get some feedback, or perhaps look at expanding to new test oracles?

  13. mrigger commented on Dec 5, 2022

    @mrigger
    ContributorAuthor

    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.

  14. sachinnandan commented on Mar 27, 2023

    @sachinnandan

    Is it solved ?? @mrigger

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions