4 ms·

Automated Test-Case Reduction

102 points by ingve 2y ago

reruwe 2y ago
I find it odd that test-case reduction is billed as a “research skill”. To me, this is a basic debugging skill for anyone who works with code. Maybe it’s more critical when you’re dealing with “research-quality” code. This post seems to ignore the underlying problem: it’s rare to see research code with any tests.
- derdi 2y ago
  As the article says, right at the top: "The plan is to demonstrate techniques that “everyone knows” because everyone, in fact, does not already know them."
  - mistercow 2y ago
    This is actually something I find hard to resist in myself as an aging software engineer on HN. When I was young, articles would describe “obvious” things in excruciating detail, and I’d be grateful, because they were often things I didn’t know. Now when I see articles about things I find obvious on the front page — particularly if they’re topics I’ve seen hit the front page before (which, mind you, means “any time in the last 15 years or so”) — I have to resist an annoyed gut reaction. The fact that knowledge and skills seem obvious and boring once internalized is a kind of terrible quirk of the human condition.
    - tialaramex 2y ago
      For whatever it's worth, I enjoy explaining things to others so each time a topic recurs I can do that where it seems appropriate. And hey I can pass on things I didn't know about and then learned here, for example that's why I tell people about WUFFS, can you do all the bounds checking at compile time? Sure, for a price. And that price (generality) might be easily affordable in which case using Rust, never mind C++ is very silly because WUFFS was offering you better performance and total safety if you can do without generality.
    - HideousKojima 2y ago
      My issue isn't with articles describing "obvious" things, it's with articles acting like this obvious thing is an amazing new discovery. This is especially funny when you see it in articles about relational database stuff, since most of the fundamentals have been discovered since the 70's.
      - j16sdiz 2y ago
        Yes, but they were lost. We stored those discoveries in mongodb. Apparently it had failed in a web scale way and nobody has figured out how to restore from backup.
- Certhas 2y ago
  I don't understand your point. Debugging is research almost by definition, no?
  - DonaldPShimoda 2y ago
    No; I think in this context, "research skills" specifically means "skills in the service of conducting publishable research", not "skills that involve some quantity of exploration" or something like that. (To be clear, I don't agree with the sentiment of the comment to which you were replying, but I also don't think debugging "is research by definition".)
    - Certhas 2y ago
      It's not scientific research with the aim of publishing, but it is research as defined in the dictionary [1], and uses some of the same skills. Honestly, I am a scientist first. I am not aware of any activity outside of academia that is more research than debugging. You start with an observed phenomenon (the bug). Then you search for the cause of it. Along the way you formulate and test hypothesis, conduct experiments, gather evidence, check the literature. What's more: these activities are the bulk of what you do, especially in difficult cases. They are not incidental to debugging, they are the essence of the work. Much of what is published is the outcome of processes that look a lot less like research. [1] (E.g. I do research to win online argguments, or for a school essay, or a reporter does research for a story, or an engineer does research on how to implement some idea. None of these cases of research are academic/scientific research)
- tom306 2y ago
  Maybe. But test case reduction for compiler bugs is absolutely not a basic debugging skill for just "anyone".
wyldfire 2y ago
In addition to c-reduce and shrinkray there's also cvise [1] for reducing tests. It's great. Also, if you happen to be reducing an LLVM case you can use llvm-reduce [2]. [1] https://github.com/marxin/cvise https://github.com/marxin/cvise [2] https://llvm.org/docs/CommandGuide/llvm-reduce.html https://llvm.org/docs/CommandGuide/llvm-reduce.html
crvdgc 2y ago
Very interesting. Previously I've seen two similar ideas: 1. Reduce the test data by property-based tests' auto shrinking a là QuickCheck [1] 2. Reduce the change set to a codebase, a là delta debugging [2] The reducer is able to do both at the same time in a pretty generic way, with some restrictions on the expressivity. Seems to be a good fit for end-to-end tests. [1]: https://www.cse.chalmers.se/~rjmh/QuickCheck/ https://www.cse.chalmers.se/~rjmh/QuickCheck/ [2]: https://dl.acm.org/doi/10.1145/318774.318946 https://dl.acm.org/doi/10.1145/318774.318946
- eru 2y ago
  Btw, Python's Hypothesis is a lot better at shrinking than QuickCheck. Not only do you get shrinking 'for free', Hypothesis's shrinker is also smarter at finding opportunities to shrink.
  - one-punch 2y ago
    Do you have examples where Python’s Hypothesis (and its shrinking) works better than Haskell’s QuickCheck? This would let us improve Haskell’s QuickCheck. My understanding is that Haskell’s QuickCheck can shrink functions, and with parametric polymorphism, can work with vector types and more [1], which would be difficult if not impossible in Python. And in general, the base types covered by the shrinking in Python’s Hypothesis should have analogues by the shrinking in Haskell’s QuickCheck. And with deriving, Haskell’s QuickCheck should get shrinking ‘for free’ as in Python’s Hypothesis. Also, Haskell’s QuickCheck extends to stateful and parallel checking, which is not supported in Python [2]. [1]: https://library.mlabs.city/mastering-quickcheck https://library.mlabs.city/mastering-quickcheck "Mastering QuickCheck: Advanced yet Practical Techniques for Property-Based Testing" [2]: https://stevana.github.io/the_sad_state_of_property-based_testing_libraries.html#a-survey-of-property-based-testing-libraries https://stevana.github.io/the_sad_state_of_property-based_te... "The sad state of property-based testing libraries: A survey of property-based testing libraries"
    - eru 2y ago
      I have to admit the last time I seriously worked with QuickCheck was quite a while ago. > My understanding is that Haskell’s QuickCheck can shrink functions [...] Are you talking about shrinking a value of type (a -> b) (for some concrete a and b)? In Hypothesis, if you write a generator that spits out functions, you get a shrinker for free. So that shrinker will shrink functions. As far as I can tell, QuickCheck's shrinking is based on values. I just checked, the type is still `shrink :: a -> [a]`, so that can't have changed. In Hypothesis shrinking is based on the generation process. In Hypothesis generators act a bit like 'Functors' in Haskell, ie you can map over them. (You can also filter and `<>` and do monadic binds etc.) So in Hypothesis you can take a generator that produces integers, and create one that produces only even numbers by (in Haskell terms) mapping (2) over it. Now, the shrinker you get for free will also only produce even numbers. That's not possible (or at least not easily possible) in Haskell. You would have to define at least a newtype wrapper. Have a look at https://hypothesis.works/articles/compositional-shrinking/ https://hypothesis.works/articles/compositional-shrinking/ and https://hypothesis.works/articles/integrated-shrinking/ https://hypothesis.works/articles/integrated-shrinking/ for some more write-up, especially about how Hypothesis can preserve information even when shrinking past a monadic bind. If you follow some links in the two articles above, you land at https://github.com/icicle-lang/disorder.hs-ambiata/tree/master/disorder-jack https://github.com/icicle-lang/disorder.hs-ambiata/tree/mast... which is a Haskell library that shares a few design decisions with Hypothesis. Apart from shrinking, Haskell's QuickCheck can also learn a lot from Hypothesis in terms of floating point number generation. The last time I used QuickCheck seriously, they basically generated floats by converting from a sort-of uniformly sampled fractional number. I see that this commit https://github.com/nick8325/quickcheck/commit/07942642d7987b073a107863b68ac2f75013076b https://github.com/nick8325/quickcheck/commit/07942642d7987b... seems to have made float generation a lot smarter! Hypothesis is especially 'nasty' when it generates floats. It has a good chunk of probability allocated to things like various NaNs, infinities, sub-normal numbers, zero, one float past zero, etc, plus of course some probability mass on uniformly chosen floats. See https://hypothesis.readthedocs.io/en/latest/data.html#hypothesis.strategies.floats https://hypothesis.readthedocs.io/en/latest/data.html#hypoth... for the docs, but you should check out the code, too.
clord 2y ago
I used to do something like this all the time with C/C++ compiler tests. I tried lots of fancy tools and stuff, but I kept going back to: expand all macros and retokenize to one token per line (I made a custom build of the preprocessor that had this built in). Then, have a shell script randomly remove lines, and use another script to check that the resulting test case behaves consistently with the failure. It would run for a few hours (or days, for boost problems), then usually you'd get a really minimal testcase that shows the problem. Often I would use this to find regressions. Just have the shell script check one is good, the other has the problem. The resulting output would then usually point exactly at the regressed feature, and make an amazing unit test. Before leaving compiler team, I wanted to find a way to do this one the AST level (so parens always go in pairs, etc), but that could also complect with the bug. I wonder if LLMs could accelerate this by more intelligently removing stuff first, iteratively?
- derdi 2y ago
  Sophisticated reducers like C-Reduce do know things like that parens go in pairs. C-Reduce has many transformation operations, and while some are syntax agnostic (delete a few characters or tokens), others use Clang to try to parse the input as C++ and transform the AST. Perses is a reducer that works on an AST and claims to only try syntactically valid candidate inputs. It also claims to be language agnostic, and I don't know how these two things go together. But it does work nicely for Java for me. https://github.com/uw-pluverse/perses https://github.com/uw-pluverse/perses / https://faculty.cc.gatech.edu/~qzhang414/papers/icse18_chengnian.pdf https://faculty.cc.gatech.edu/~qzhang414/papers/icse18_cheng...
  - DRMacIver 2y ago
    Perses isn't language agnostic, it just knows the syntax of a lot of languages because there are antlr grammars for most commonly used languages. Really there's no such thing as a language-agnostic test-case reducer. shrink ray is much closer than most, but all this means is that it's got some heuristics that work well for a wide variety of common languages (e.g. the bracket balancing thing). It's also got a bunch of language-specific passes. This is sortof inherent to the problem, because in order to get good results and good performance, a test-case reducer has to have a strong idea of what sort of transformations are likely to work, which in turn means it has to have a strong idea of what sort of languages it's likely to be run on.
imp0cat 2y ago
Interesting. The techniques are quite similar to what one can do with Hypothesis in Python ( https://hypothesis.readthedocs.io/en/latest/quickstart.html https://hypothesis.readthedocs.io/en/latest/quickstart.html ). Basically, it generates a bunch of test data and then tries to shrink it to the smallest example that fails the test automatically.
- spockz 2y ago
  This is more generally called property based testing. My first encounters with it were quickcheck for erlang and Haskell. It has been around for ages.
- DRMacIver 2y ago
  This isn't a coincidence. I wrote both.
  - imp0cat 2y ago
    Thank you! I have no experience with Shrinkray, but Hypothesis is great.
mspdx22 2y ago
There was a talk about some novel ways to approach test suite generation and reduction at a PLDI workshop a few weeks ago. That work came from the compilers and programming languages tool domain: https://pldi24.sigplan.org/home/egraphs-2024#program https://pldi24.sigplan.org/home/egraphs-2024#program Specifically, the EGSTRA paper.
jedisct1 2y ago
Zig has a built-in test-case reduction command ("zig reduce").

102 points by ingve 2y ago

I find it odd that test-case reduction is billed as a “research skill”. To me, this is a basic debugging skill for anyone who works with code. Maybe it’s more critical when you’re dealing with “research-quality” code. This post seems to ignore the underlying problem: it’s rare to see research code with any tests.

derdi 2y ago
As the article says, right at the top: "The plan is to demonstrate techniques that “everyone knows” because everyone, in fact, does not already know them."
- mistercow 2y ago
  This is actually something I find hard to resist in myself as an aging software engineer on HN. When I was young, articles would describe “obvious” things in excruciating detail, and I’d be grateful, because they were often things I didn’t know. Now when I see articles about things I find obvious on the front page — particularly if they’re topics I’ve seen hit the front page before (which, mind you, means “any time in the last 15 years or so”) — I have to resist an annoyed gut reaction. The fact that knowledge and skills seem obvious and boring once internalized is a kind of terrible quirk of the human condition.
  - tialaramex 2y ago
    For whatever it's worth, I enjoy explaining things to others so each time a topic recurs I can do that where it seems appropriate. And hey I can pass on things I didn't know about and then learned here, for example that's why I tell people about WUFFS, can you do all the bounds checking at compile time? Sure, for a price. And that price (generality) might be easily affordable in which case using Rust, never mind C++ is very silly because WUFFS was offering you better performance and total safety if you can do without generality.
  - HideousKojima 2y ago
    My issue isn't with articles describing "obvious" things, it's with articles acting like this obvious thing is an amazing new discovery. This is especially funny when you see it in articles about relational database stuff, since most of the fundamentals have been discovered since the 70's.
    - j16sdiz 2y ago
      Yes, but they were lost. We stored those discoveries in mongodb. Apparently it had failed in a web scale way and nobody has figured out how to restore from backup.
Certhas 2y ago
I don't understand your point. Debugging is research almost by definition, no?
- DonaldPShimoda 2y ago
  No; I think in this context, "research skills" specifically means "skills in the service of conducting publishable research", not "skills that involve some quantity of exploration" or something like that. (To be clear, I don't agree with the sentiment of the comment to which you were replying, but I also don't think debugging "is research by definition".)
  - Certhas 2y ago
    It's not scientific research with the aim of publishing, but it is research as defined in the dictionary [1], and uses some of the same skills. Honestly, I am a scientist first. I am not aware of any activity outside of academia that is more research than debugging. You start with an observed phenomenon (the bug). Then you search for the cause of it. Along the way you formulate and test hypothesis, conduct experiments, gather evidence, check the literature. What's more: these activities are the bulk of what you do, especially in difficult cases. They are not incidental to debugging, they are the essence of the work. Much of what is published is the outcome of processes that look a lot less like research. [1] (E.g. I do research to win online argguments, or for a school essay, or a reporter does research for a story, or an engineer does research on how to implement some idea. None of these cases of research are academic/scientific research)
tom306 2y ago
Maybe. But test case reduction for compiler bugs is absolutely not a basic debugging skill for just "anyone".

wyldfire 2y ago

In addition to c-reduce and shrinkray there's also cvise [1] for reducing tests. It's great. Also, if you happen to be reducing an LLVM case you can use llvm-reduce [2]. [1] https://github.com/marxin/cvise https://github.com/marxin/cvise [2] https://llvm.org/docs/CommandGuide/llvm-reduce.html https://llvm.org/docs/CommandGuide/llvm-reduce.html

crvdgc 2y ago

Very interesting. Previously I've seen two similar ideas: 1. Reduce the test data by property-based tests' auto shrinking a là QuickCheck [1] 2. Reduce the change set to a codebase, a là delta debugging [2] The reducer is able to do both at the same time in a pretty generic way, with some restrictions on the expressivity. Seems to be a good fit for end-to-end tests. [1]: https://www.cse.chalmers.se/~rjmh/QuickCheck/ https://www.cse.chalmers.se/~rjmh/QuickCheck/ [2]: https://dl.acm.org/doi/10.1145/318774.318946 https://dl.acm.org/doi/10.1145/318774.318946

eru 2y ago
Btw, Python's Hypothesis is a lot better at shrinking than QuickCheck. Not only do you get shrinking 'for free', Hypothesis's shrinker is also smarter at finding opportunities to shrink.
- one-punch 2y ago
  Do you have examples where Python’s Hypothesis (and its shrinking) works better than Haskell’s QuickCheck? This would let us improve Haskell’s QuickCheck. My understanding is that Haskell’s QuickCheck can shrink functions, and with parametric polymorphism, can work with vector types and more [1], which would be difficult if not impossible in Python. And in general, the base types covered by the shrinking in Python’s Hypothesis should have analogues by the shrinking in Haskell’s QuickCheck. And with deriving, Haskell’s QuickCheck should get shrinking ‘for free’ as in Python’s Hypothesis. Also, Haskell’s QuickCheck extends to stateful and parallel checking, which is not supported in Python [2]. [1]: https://library.mlabs.city/mastering-quickcheck https://library.mlabs.city/mastering-quickcheck "Mastering QuickCheck: Advanced yet Practical Techniques for Property-Based Testing" [2]: https://stevana.github.io/the_sad_state_of_property-based_testing_libraries.html#a-survey-of-property-based-testing-libraries https://stevana.github.io/the_sad_state_of_property-based_te... "The sad state of property-based testing libraries: A survey of property-based testing libraries"
  - eru 2y ago
    I have to admit the last time I seriously worked with QuickCheck was quite a while ago. > My understanding is that Haskell’s QuickCheck can shrink functions [...] Are you talking about shrinking a value of type (a -> b) (for some concrete a and b)? In Hypothesis, if you write a generator that spits out functions, you get a shrinker for free. So that shrinker will shrink functions. As far as I can tell, QuickCheck's shrinking is based on values. I just checked, the type is still `shrink :: a -> [a]`, so that can't have changed. In Hypothesis shrinking is based on the generation process. In Hypothesis generators act a bit like 'Functors' in Haskell, ie you can map over them. (You can also filter and `<>` and do monadic binds etc.) So in Hypothesis you can take a generator that produces integers, and create one that produces only even numbers by (in Haskell terms) mapping (2) over it. Now, the shrinker you get for free will also only produce even numbers. That's not possible (or at least not easily possible) in Haskell. You would have to define at least a newtype wrapper. Have a look at https://hypothesis.works/articles/compositional-shrinking/ https://hypothesis.works/articles/compositional-shrinking/ and https://hypothesis.works/articles/integrated-shrinking/ https://hypothesis.works/articles/integrated-shrinking/ for some more write-up, especially about how Hypothesis can preserve information even when shrinking past a monadic bind. If you follow some links in the two articles above, you land at https://github.com/icicle-lang/disorder.hs-ambiata/tree/master/disorder-jack https://github.com/icicle-lang/disorder.hs-ambiata/tree/mast... which is a Haskell library that shares a few design decisions with Hypothesis. Apart from shrinking, Haskell's QuickCheck can also learn a lot from Hypothesis in terms of floating point number generation. The last time I used QuickCheck seriously, they basically generated floats by converting from a sort-of uniformly sampled fractional number. I see that this commit https://github.com/nick8325/quickcheck/commit/07942642d7987b073a107863b68ac2f75013076b https://github.com/nick8325/quickcheck/commit/07942642d7987b... seems to have made float generation a lot smarter! Hypothesis is especially 'nasty' when it generates floats. It has a good chunk of probability allocated to things like various NaNs, infinities, sub-normal numbers, zero, one float past zero, etc, plus of course some probability mass on uniformly chosen floats. See https://hypothesis.readthedocs.io/en/latest/data.html#hypothesis.strategies.floats https://hypothesis.readthedocs.io/en/latest/data.html#hypoth... for the docs, but you should check out the code, too.

clord 2y ago

I used to do something like this all the time with C/C++ compiler tests. I tried lots of fancy tools and stuff, but I kept going back to: expand all macros and retokenize to one token per line (I made a custom build of the preprocessor that had this built in). Then, have a shell script randomly remove lines, and use another script to check that the resulting test case behaves consistently with the failure. It would run for a few hours (or days, for boost problems), then usually you'd get a really minimal testcase that shows the problem. Often I would use this to find regressions. Just have the shell script check one is good, the other has the problem. The resulting output would then usually point exactly at the regressed feature, and make an amazing unit test. Before leaving compiler team, I wanted to find a way to do this one the AST level (so parens always go in pairs, etc), but that could also complect with the bug. I wonder if LLMs could accelerate this by more intelligently removing stuff first, iteratively?

derdi 2y ago
Sophisticated reducers like C-Reduce do know things like that parens go in pairs. C-Reduce has many transformation operations, and while some are syntax agnostic (delete a few characters or tokens), others use Clang to try to parse the input as C++ and transform the AST. Perses is a reducer that works on an AST and claims to only try syntactically valid candidate inputs. It also claims to be language agnostic, and I don't know how these two things go together. But it does work nicely for Java for me. https://github.com/uw-pluverse/perses https://github.com/uw-pluverse/perses / https://faculty.cc.gatech.edu/~qzhang414/papers/icse18_chengnian.pdf https://faculty.cc.gatech.edu/~qzhang414/papers/icse18_cheng...
- DRMacIver 2y ago
  Perses isn't language agnostic, it just knows the syntax of a lot of languages because there are antlr grammars for most commonly used languages. Really there's no such thing as a language-agnostic test-case reducer. shrink ray is much closer than most, but all this means is that it's got some heuristics that work well for a wide variety of common languages (e.g. the bracket balancing thing). It's also got a bunch of language-specific passes. This is sortof inherent to the problem, because in order to get good results and good performance, a test-case reducer has to have a strong idea of what sort of transformations are likely to work, which in turn means it has to have a strong idea of what sort of languages it's likely to be run on.

imp0cat 2y ago

Interesting. The techniques are quite similar to what one can do with Hypothesis in Python ( https://hypothesis.readthedocs.io/en/latest/quickstart.html https://hypothesis.readthedocs.io/en/latest/quickstart.html ). Basically, it generates a bunch of test data and then tries to shrink it to the smallest example that fails the test automatically.

spockz 2y ago
This is more generally called property based testing. My first encounters with it were quickcheck for erlang and Haskell. It has been around for ages.
DRMacIver 2y ago
This isn't a coincidence. I wrote both.
- imp0cat 2y ago
  Thank you! I have no experience with Shrinkray, but Hypothesis is great.

mspdx22 2y ago

There was a talk about some novel ways to approach test suite generation and reduction at a PLDI workshop a few weeks ago. That work came from the compilers and programming languages tool domain: https://pldi24.sigplan.org/home/egraphs-2024#program https://pldi24.sigplan.org/home/egraphs-2024#program Specifically, the EGSTRA paper.

jedisct1 2y ago

Zig has a built-in test-case reduction command ("zig reduce").