6 ms·

I think one approach would be to use RNGs in a slightly different way. Instead of a 'random walk' of various API calls, define a possible outcome category, and

by bcbrown 14y ago

I think one approach would be to use RNGs in a slightly different way. Instead of a 'random walk' of various API calls, define a possible outcome category, and choose a random number to be the quantity of that outcome. So for the bounded queue problem, set the outcome category to be "elements in queue". Say you get 3, 12, and 7 as your first three random numbers. Then the first three test cases would be "get the load to 3 elements", "get the capacity to 12 elements", "get the capacity to 7 elements".

regehr 14y ago
This does indeed work. The problem is that there is a very large number of possible goals that a random tester might aim for, and we do not know ahead of time which ones are most important. Also, for complex testers like Csmith, it is not clear how to reach some goals. This kind of thing complicates the code a lot too.
- bcbrown 14y ago
  I'll state up front that I have no familiarity with Csmith or compilers. You can characterize a random test as a random walk through a many-dimensional space, right? And the problem is that a random walk will naturally spend more time close to the starting point? What if, when choosing the next step to take, you bias the options towards moving away from the initial state? Is it even possible to talk about 'away' and 'towards' in the state space? Going back to the queue example, this would mean that if the starting load of the queue is 5, whenever the load is above 5, bias the distribution of enqueues/dequeues towards enqueueing.
  - regehr 14y ago
    Csmith is much less like a random walk; most program generation steps result in forward progress. The problem is that at the end of many forward steps, we may have a test case that is, in some sense, very similar to all of the other programs generated by Csmith. So when we compile this test case, nothing very interesting happens. If we decided up front that, for example, the next program to generate would have 95% stores through pointers and only 5% scalar operations, then this would probably be pretty useful. But nothing in Csmith currently supports this kind of high-level goal-seeking behavior. So overall there are engineering issues, but also there are some hard open questions about what it is that a random tester is trying to accomplish. By necessity these programs start with only very weak hypothesis about what the bugs that they are trying to find look like.

by bcbrown 14y ago

regehr 14y ago

This does indeed work. The problem is that there is a very large number of possible goals that a random tester might aim for, and we do not know ahead of time which ones are most important. Also, for complex testers like Csmith, it is not clear how to reach some goals. This kind of thing complicates the code a lot too.

bcbrown 14y ago
I'll state up front that I have no familiarity with Csmith or compilers. You can characterize a random test as a random walk through a many-dimensional space, right? And the problem is that a random walk will naturally spend more time close to the starting point? What if, when choosing the next step to take, you bias the options towards moving away from the initial state? Is it even possible to talk about 'away' and 'towards' in the state space? Going back to the queue example, this would mean that if the starting load of the queue is 5, whenever the load is above 5, bias the distribution of enqueues/dequeues towards enqueueing.
- regehr 14y ago
  Csmith is much less like a random walk; most program generation steps result in forward progress. The problem is that at the end of many forward steps, we may have a test case that is, in some sense, very similar to all of the other programs generated by Csmith. So when we compile this test case, nothing very interesting happens. If we decided up front that, for example, the next program to generate would have 95% stores through pointers and only 5% scalar operations, then this would probably be pretty useful. But nothing in Csmith currently supports this kind of high-level goal-seeking behavior. So overall there are engineering issues, but also there are some hard open questions about what it is that a random tester is trying to accomplish. By necessity these programs start with only very weak hypothesis about what the bugs that they are trying to find look like.