Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Automated Test-Case Reduction

cs.cornell.edu

Post reply on HN
Print view View original

11–20 of 30 posts

Re: Automated Test-Case Reduction

#11

Post by derdi »

clord wrote: post #9

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 r…

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://faculty.cc.gatech.edu/~qzhang414/papers/icse18_cheng...

Re: Automated Test-Case Reduction

#13

Post by DRMacIver »

derdi wrote: post #11
clord wrote: post #9

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 r…

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…

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.

Re: Automated Test-Case Reduction

#14

Post by spockz »

imp0cat wrote: post #12

Interesting. The techniques are quite similar to what one can do with Hypothesis in Python ( 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.

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.

Re: Automated Test-Case Reduction

#16

Post by DRMacIver »

imp0cat wrote: post #12

Interesting. The techniques are quite similar to what one can do with Hypothesis in Python ( 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.

This isn't a coincidence. I wrote both.

Re: Automated Test-Case Reduction

#17

Post by tom306 »

reruwe wrote: post #2

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.

Maybe. But test case reduction for compiler bugs is absolutely not a basic debugging skill for just "anyone".

Re: Automated Test-Case Reduction

#18

Post by pdimitar »

DRMacIver wrote: post #13
derdi wrote: post #11

Earlier quoted context omitted.

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…

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…

I am just shooting in the dark here so excuse me if my comment is too ignorant: have you considered rolling your own reducer and use TreeSitter grammars for it?

Re: Automated Test-Case Reduction

#19

Post by j16sdiz »

HideousKojima wrote: post #7
mistercow wrote: post #4

Earlier quoted context omitted.

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 i…

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.

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.

Re: Automated Test-Case Reduction

#20

Post by DonaldPShimoda »

Certhas wrote: post #10
reruwe wrote: post #2

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.

I don't understand your point. Debugging is research almost by definition, no?

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

Post reply on HN