[mbrock]

This is not a true implication.

If all the executables in the archive were, say, loop-free trivial programs, then of course you could instantly confirm an absence of malware.

If there are some loops and complications in there, you would do some more logical work, and then depending on the power of your logical system, either conclude safety or unsafety, or time out.

Rice's theorem does not mean that static analysis is impossible, even of machine code!

[jmite]

Right, but Rice's theorem means that you either have false positives, false negatives, or "Unknown" answers in any static analysis. Which means that the CIA could never guarantee the absence of malware, for example, if any of the programs timed out in the static analysis.

[mbrock]

It seems likely that they wouldn't be able to guarantee that, but we need to be more clear.

The fundamental limitations of computer science, as expressed by Rice's theorem, says that the CIA cannot make a program that given any archive says in finite time whether there is malware there.

It doesn't say that for some specific archive the CIA cannot guarantee the absence of malware.

There are infinitely many EXE files that you can prove malware-free, and this set expands with the progress of static analysis.

But of course, if one EXE file says "if (unsolved_math_problem()) { malware(); } else { harmless(); }" then the CIA would have to spend a lot of effort proving its status.