4 ms·

This sounds like a bad idea to me if taken too seriously. Makefiles come from a grammar not a 5th order markov process. The sampled strings from the markov cha

This sounds like a bad idea to me if taken too seriously. Makefiles come from a grammar not a 5th order markov process. The sampled strings from the markov chain are not likely to be representative of the makefiles encountered in practice. I suspect that the makefile language is probably too complex for formal verification so I understand the problem, but I would prefer their other approach where they take large numbers of real world makefiles and compare the output seems a better choice. Just spend the effort and get a larger and more diverse set of test makefiles.

spuz 17y ago
If you've spent 2 years amassing 2000 real world sample inputs, I think this is a very valid way of going that extra bit further to test your system. Of course it's not possible to capture every possible test case when generating random input but using Markov chains seems like a good way to get 'sensible' data out of a random process. It is likely they exposed bugs in their parser that they would never have found by loading in real world make files.
skwiddor 17y ago
Did you read to the bottom? They wanted to generate not only valid output from valid makefiles but wanted to catch the same errors in the same way as their reference. I like their approach and I would consider it an excellent bug hunting tool. Focussed fuzzing. Would you consider their markov chained output a derivative work though ?
brown9-2 17y ago
From the article: Verifying the implementation of an emulator for a complex system is hard, especially when the original system has no formal specification.
emelski 17y ago
The problem with relying solely on "real world makefiles" is that there is not a lot of variation amongst those that are publicly accessible. The vast majority of open source projects that use make are autoconf based, which means the makefiles are all more-or-less the same, except that the list of source files and the project name change. Once you can successfully build one of these, you can probably build all of them. There are a handful projects that don't follow this pattern, such as Mozilla, but once you've built those they cease to be useful for flushing out new bugs. So, what do you do once you've built all the open source projects you can find, and you are still finding incompatibilities in your parser when you go to customers? Markov chain-based makefiles are a reasonable way to extend the breadth of our testing. Obviously it's not the only thing we do, but it is another valuable tool to add to the toolbox.
- kurtosis 17y ago
  Okay I understand where you're coming from. I'm really curious though, what were some of the bugs that showed up? Were they easy to fix or did they require adding a lot of special cases and patchwork to the code?
  - emelski 17y ago
    There were about a dozen issues uncovered using this technique. I would say the majority of them were what I would call "real" bugs, as opposed to "sure, that doesn't work but nobody cares". One example is that gmake allows $$ in variable names, as in "FOO$$BAR=abc"; at the time our parser did not handle this correctly. I did not have to create special cases to fix these bugs, at least not any more so than any other parser feature.

spuz 17y ago

If you've spent 2 years amassing 2000 real world sample inputs, I think this is a very valid way of going that extra bit further to test your system. Of course it's not possible to capture every possible test case when generating random input but using Markov chains seems like a good way to get 'sensible' data out of a random process. It is likely they exposed bugs in their parser that they would never have found by loading in real world make files.

skwiddor 17y ago

Did you read to the bottom? They wanted to generate not only valid output from valid makefiles but wanted to catch the same errors in the same way as their reference. I like their approach and I would consider it an excellent bug hunting tool. Focussed fuzzing. Would you consider their markov chained output a derivative work though ?

brown9-2 17y ago

From the article: Verifying the implementation of an emulator for a complex system is hard, especially when the original system has no formal specification.

emelski 17y ago

The problem with relying solely on "real world makefiles" is that there is not a lot of variation amongst those that are publicly accessible. The vast majority of open source projects that use make are autoconf based, which means the makefiles are all more-or-less the same, except that the list of source files and the project name change. Once you can successfully build one of these, you can probably build all of them. There are a handful projects that don't follow this pattern, such as Mozilla, but once you've built those they cease to be useful for flushing out new bugs. So, what do you do once you've built all the open source projects you can find, and you are still finding incompatibilities in your parser when you go to customers? Markov chain-based makefiles are a reasonable way to extend the breadth of our testing. Obviously it's not the only thing we do, but it is another valuable tool to add to the toolbox.

kurtosis 17y ago
Okay I understand where you're coming from. I'm really curious though, what were some of the bugs that showed up? Were they easy to fix or did they require adding a lot of special cases and patchwork to the code?
- emelski 17y ago
  There were about a dozen issues uncovered using this technique. I would say the majority of them were what I would call "real" bugs, as opposed to "sure, that doesn't work but nobody cares". One example is that gmake allows $$ in variable names, as in "FOO$$BAR=abc"; at the time our parser did not handle this correctly. I did not have to create special cases to fix these bugs, at least not any more so than any other parser feature.