You are addressing a completely different issue than the paper did. Yes, the general case is nearly impossibly hard.
But that is not the point. The point is that against a determined adversary, you can not trust an arbitrary program, even if that program is compiled from source, unless you can also trust every other component on your system.
The point then, is to encourage that "bit of paranoia" and make people understand that thinking you're safe just because you can read through the source or have another mechanism for producing or obtaining what you might think is a pristine, safe copy of a piece of software is a false sense of security.
While this particular attack to my knowledge was only a thought experiment and I've never heard of it occurring in the wild, note that at least a few viruses for example propagate by modifying binaries to act as carriers, and often modify the system to obscure their presence (e.g. report incorrect file sizes, and not read back the modified data). This is largely the same threat, and in many ways far more practical because it doesn't require people to take the step of trying to recompile applications.
Having the source (or a "known good" source of your application) does not help you, as your binary is infected when it is handled by the compromised system. Taking checksums etc. on the compromised systems may not help you.
But that is not the point. The point is that against a determined adversary, you can not trust an arbitrary program, even if that program is compiled from source, unless you can also trust every other component on your system.
The point then, is to encourage that "bit of paranoia" and make people understand that thinking you're safe just because you can read through the source or have another mechanism for producing or obtaining what you might think is a pristine, safe copy of a piece of software is a false sense of security.
While this particular attack to my knowledge was only a thought experiment and I've never heard of it occurring in the wild, note that at least a few viruses for example propagate by modifying binaries to act as carriers, and often modify the system to obscure their presence (e.g. report incorrect file sizes, and not read back the modified data). This is largely the same threat, and in many ways far more practical because it doesn't require people to take the step of trying to recompile applications.
Having the source (or a "known good" source of your application) does not help you, as your binary is infected when it is handled by the compromised system. Taking checksums etc. on the compromised systems may not help you.