Proposal for improvements to `generateInternal`

[Zon8Research]

Proposal for improvements to generateInternal.

So currently code generation works like this (from what I can see):

1. Pick any random codegen
2. If we meet the required context and inputs, generate code.
3. Otherwise, do nothing and return.

I propose we take the following approach:

1. Find all codegens that meet our context/inputs.
2. Pick a random codegen from this newly generated list.

The reasons for doing this are as follows:

• It can be common for the random choice to pick something that is out of context or don't have inputs for, therefore returning without generating code. The new approach will mean we always generate a valid codegen.
• It would also improve the chances of hitting lower probability code generators if other out of scope codegens are removed.
• This helps reduce a larger issue, and that is that the test cases generated by fuzzilli have an over proportionate amount of empty functions, loops and if statements. eg

for (const v375 in v374) {
}
function v376(v377) {
}
function v378(v379,v380) {
    for (let v384 = 0; v384 < 100; v384 = v384 || -1024) {
    }
    const v385 = (v386,v387,v388,v389,v390) => {
    };
}

Example code for this change would be to replace https://github.com/googleprojectzero/fuzzilli/blob/10d5db4700b2d02481b916302269025cee9a1f69/Sources/Fuzzilli/Core/ProgramBuilder.swift#L832 with as follows:

// We can't run code generators if we don't have any visible variables.
var inScopeCodeGens: [CodeGenerator] = []
guard self.scopeAnalyzer.visibleVariables.count > 0 else { return }
for codegen in self.fuzzer.codeGenerators {
    if codegen.requiredContext.isSubset(of: self.context) {
        inScopeCodeGens.append(codegen)
    }
}
let generator = inScopeCodeGens.randomElement()
if generator == nil {
    return
}

self.run(generator!)

One argument against this might be potential performance impact of finding all codegens that are suitable.

I've timed the generateInternal function with the new changes and this is the speed in debug mode:

0.00012600421905517578 seconds elapsed

Compared to the original speed which was:

1.0013580322265625e-05 seconds elapsed

However, you could also argue that this performance impact is inconsequential compared to how long is spent executing the payload. Also, this isn't even factoring in the time wasted currently by attempting to generate a codegen, but then returning with nothing. So you may actually end up saving time by having less wasted cycles.

Looking forward to hearing your thoughts.

[saelo]

Thanks, yes, that sounds good to me! Maybe open a PR with that code for any further discussions?

This helps reduce a larger issue, and that is that the test cases generated by fuzzilli have an over proportionate amount of empty functions, loops and if statements

Maybe it would make sense to open a separate issue for this, unless it's covered in https://github.com/googleprojectzero/fuzzilli/issues/236

[saelo]

Closing since this is implemented in https://github.com/googleprojectzero/fuzzilli/pull/255 and https://github.com/googleprojectzero/fuzzilli/issues/264 now covers the empty blocks issue