Ian Romanick - Randomized Testing
Testing all of the corner cases of a complex piece of software is hard. It's really, really hard. The problem can be thought of from a search perspective: somewhere in the space of possible inputs, the software under test may produce incorrect results. As a tester, the goal is to find those inputs. For many pieces of software the space of possible inputs is uncountably infinite. Traditional search techniques fail in these scenarios.
All is not lost, however. There are many examples in algorithm research where judicious application of randomization to exceptionally difficult problems can either solve the problem correctly in probabilistic finite time or solve the problem in finite time with probabilistic correctness.
Numerous aspects of an OpenGL shading language compiler have uncountably infinite possible inputs. Specifically, the possible set of uniform blocks is uncountably infinite. Each possible uniform block has a single, valid memory layout. Many GLSL compiler implementations produce incorrect layouts for some uniform blocks. These factors make this an ideal "search" problem for a randomized technique.
I would like to present:
- Background of randomized techniques.
- The problem of uniform blocks, and why it's so hard to get right.
- The randomized test generator that has been implemented.
- Sampling of the bugs that it has already found.
- Ways to extend the current test generator.
- Additional areas that would be good candidates for a similar testing method.