Overview of the GLFuzz transformations
If you’ve read the examples from my posts on finding bugs in AMD and Apple drivers, then hopefully you’ll be getting a feeling for how GLFuzz works: we have devised a number of program transformations that should be semantics-preserving, or almost semantics-preserving, and we flag up cases where these transformations do have a significant impact.
In future posts I will go into details of issues such as:
- cases where our transformations do have an impact and lead to false alarms
- how we try to avoid wasting time examining false alarms by distinguishing automatically between small and large image differences
- how we obtain minimised variants from the bloated variants that GLFuzz initially produces
Here, I’ll give an overview of four of the transformations that GLFuzz employs: dead code injection, dead control flow injection, expression mutation, and control flow wrapping.
The injectionSwitch vector
GLFuzz equips a variant shader with a new uniform:
uniform vec2 injectionSwitch;
At runtime, injectionSwitch is set to (0.0, 1.0), so that injectionSwitch.x is 0.0 and injectionSwitch.y is 1.0. This new uniform is used by the transformations we now describe.
Dead code injection
GLFuzz randomly grabs a piece of code from another shader (we have a library of suitable shaders, mined from GLSLsandbox), and inserts it at a random point into the target shader. However, the injected code is wrapped inside a “dead-by-construction” conditional statement, such as:
if(injectionSwitch.x > injectionSwitch.y) {
// Injected code transplanted from another shader
}
so that it should have no effect at runtime.
The piece of code being injected might contain free variables. For example, if we choose the body of a for loop, but do not include the for loop header, then the counter of the for loop will not be declared in the injected code — it is a free variable. For a free variable v, we choose randomly between (a) declaring v at the start of the injection, initialising it to a randomly generated expression, and (b) finding a variable in the target shader, x say, that is in scope at the point of injection and that has the same type as v, and replacing all occurrences of v in the injected block with x.
The second approach — substituting free variables with the names of in-scope variables — may turn out to be important because it prevents the compiler from optimising away the injected code. If the injected code would declare all the data that it ever accesses, and never let that data leak outside the block, then an aggressive compiler might simply delete the injection, realising that it can have no effect on shader computation. If the injected block contains code that assigns to variables declared outside the block then the compiler cannot perform such an optimisation.
Dead control flow injection
GLFuzz uses a special case of dead code injection, called dead control flow injection. This involves injecting a conditional with a false guard, but containing just a single branching statement:
if(injectionSwitch.x > injectionSwitch.y) {
branching_stmt;
}
where branching_stmt is one of break, continue, return or discard. We only generate break and continue if the injection is inside a loop, and when generating return we are sure to return a randomly generated expression of the correct type, if the function being injected into does not have return type void.
Expression mutation
If e is an expression of type int, we can transform e into, e.g., (e*1), (e+0), (e/1), (true ? e : …), (false ? … : e), where “…” stands for any expression. These transformations should have no effect on computation, clearly.
Furthermore, instead of explicitly using the literals, 1, 0, true and false, we can obtain opaque versions of these values from injectionSwitch: 0 is provided by injectionSwitch.x, 1 by injectionSwitch.y, true by injectionSwitch.x < injectionSwitch.y, and false by injectionSwitch.x > injectionSwitch.y.
We can pull similar tricks with float variables and vectors.
We can also apply these transformations recursively to get very complicated expressions that may be good at exposing compiler bugs. For example, here is an original program statement expression from a shader from our database:
cPos = vec3(0.0, 2.0, — 4.0);
and here is a rewritten version of the statement after some expression mutation has been applied:
cPos = vec3(0.0, (injectionSwitch.y * (false ? vec4(-60.21, -0.9, 6.0, 636.467)[2] : 1.0 * 2.0)), — 4.0);
If you look carefully you’ll see that in all cases the mutations have no ultimate effect given that injectionSwitch has the value (0.0, 1.0).
An issue that I’ll return to in a future post is that, as Dan Liew already pointed out, sometimes adding zero or multiplying by one can actually have an effect on floating-point computation. Our hypothesis is that this effect will often be small and so by investigating large differences we can find interesting compiler bugs, and this has played out in practice so far.
Control flow wrapping
The final transformation I’ll discuss here is control flow wrapping. This is where we take a block of code, B say, and replace B with one of the following:
if(true) { B; }
or
if(false) { } else { B; }
or
for(int temp = 0; temp < 1; temp++) { B; }
In each case, however, GLFuzz randomly chooses whether to obfuscate true, false, 1 and 0 by means of injectionSwitch, to prevent the extent to which the compiler can undo the wrapping.
Back to the slug
Remember the slug example from this post about Apple’s drivers? Some GLFuzz transformations caused the slug to disappear:
The slug example neatly showcases control flow wrapping (the “c” loop), expression mutation (multiplying 0.8 by injectionSwitch.y), and a rather trivial form of dead code injection (the empty if statement). The Apple garbage example, and the AMD issues we discovered, show that dead control flow injection can be really effective too.
GLFuzz has two more kinds of transformation: live code injection, and vectorization. I haven’t yet shown you cases where these lead to the discovery of interesting compiler bugs, so I’ll save them for future posts where they do.