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