Rice's theorem is nice and all, but in the real world we can model executables as things other than turing machines and answer questions about them. If I was t

Rice's theorem is nice and all, but in the real world we can model executables as things other than turing machines and answer questions about them. If I was trying to detect a "trusting trust" type backdoor, one thing I might do is model the control flow of the executable as a graph, and use something like approximate graph isomorphism to detect additional large blocks of code.