proposal: cmd/asm: support for mutation testing

[FiloSottile]

Test coverage for cryptographic assembly is worthless, because branches are intentionally avoided for constant timedness, and control flow and edge cases are hidden with CMOV and ADC instructions. A few years ago I tried dynamic instrumentation to observe flag states, but it quickly turned unwidely, and it's not portable.

Mutation testing provides effectively a coverage replacement: if we mutate a CMOV first to a MOV, and then to a NOP, and tests fail in both cases, it means we are covering both "branches".

Applying mutations to the assembler input is difficult due to macro expansion, so it'd be best to have assembler support.

I propose adding a -mutlist flag which prints an instruction listing to stderr in format asm: mutlist: FILEPATH:LINE: PC INSTR with virtual PCs (the potential targets) and a mutually exclusive -mut flag which accepts a mutation in the format FILEPATH:PC=INSTR[;INSTR].

$ go test crypto/ed25519 -asmflags=crypto/internal/fips140/edwards25519/field=-mutlist -c
# crypto/internal/fips140/edwards25519/field
asm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:8: 00001 TEXT   crypto/internal/fips140/edwards25519/field.feMul(SB), NOSPLIT, $0-24
[...]
asm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:23: 00012 ADDQ  AX, DI
asm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:24: 00013 ADCQ  DX, SI
asm: mutlist: $GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:27: 00014 MOVQ  16(CX), DX
[...]

$ go test crypto/ed25519 -asmflags=crypto/internal/fips140/edwards25519/field='"-mut=$GOROOT/src/crypto/internal/fips140/edwards25519/field/fe_amd64.s:13=STC;ADCQ DX, SI"'
--- FAIL: TestGenerateKey (0.00s)
panic: runtime error: invalid memory address or nil pointer dereference [recovered, repanicked]
[signal SIGSEGV: segmentation violation code=0x1 addr=0x0 pc=0x5a900de]

The PCs need to be virtual to avoid having to recompute them after inserting/mutating instructions.

There is an implementation in CL 665375, and a mutation test framework that uses it in CL 666395. I wrote more about the use case here.

/cc @golang/compiler

[gabyhelp]

Related Code Changes

• cmd/asm: add -mut and -mutlist flags for mutation testing

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[cherrymui]

Thanks for the proposal! Excited to see this!

It looks to me that the -mutlist flag just dumps instructions, similar to the -S flag. What's the difference? Could we just use the -S flag? Or should it take some sort of filter, such as -mutlist=ADCQ so it just prints the ADCQ instructions?

The -mut flag takes FILEPATH:PC, which is a bit strange. Usually we print FILE:LINE, as does with the -S flag and the proposed -mutlist flag. PC has an advantage over line number in that it is relative to the function, so it won't change as code moves. Perhaps it could take function_name+PC instead?

I'm also wondering, instead of the two-step approach, if it is possible to have a more "high level" interface, where you specify a list of mutations, or a pattern like ADCQ->ADDQ, and it tries to mutate every match and expect it to fail.

[FiloSottile]

It looks to me that the -mutlist flag just dumps instructions, similar to the -S flag. What's the difference? Could we just use the -S flag?

-S uses real program counters, while -mutlist prints the virtual PC. Using real program counters makes -mut more invasive, because it needs to compute program counters, find the instruction, mutate it, and then recompute program counters (hoping it did not discard information it needed to do so). Doing mutation at the virtual PC stage is a lot more natural.

The -mut flag takes FILEPATH:PC, which is a bit strange. Usually we print FILE:LINE, as does with the -S flag and the proposed -mutlist flag. PC has an advantage over line number in that it is relative to the function, so it won't change as code moves. Perhaps it could take function_name+PC instead?

Line number won't work because it's not unique, with a macro or INSTR; INSTR we can have multiple instructions on a line.

Not changing as the code moves is not really a concern, the idea is that -mutlist and -mut are called in a tight loop. All we need is a way to uniquely identify an instruction such that it can be mutated.

Is function_name+PC unique?

Or should it take some sort of filter, such as -mutlist=ADCQ so it just prints the ADCQ instructions?

I'm also wondering, instead of the two-step approach, if it is possible to have a more "high level" interface, where you specify a list of mutations, or a pattern like ADCQ->ADDQ, and it tries to mutate every match and expect it to fail.

I like leaving as much complexity as possible outside of cmd/asm. It lets us do more complex things in the future in the caller, without having to reach back into cmd/asm. Note that the "expecting to fail" also needs to be implemented outside of cmd/asm.

Another way to look at it is that we are implementing a higher-level framework, in CL 666395, and this proposal is just for the cmd/asm integration.