If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision?

This is a question relevant to information security as metamorphic malware will perform transformations on its own code which will make it look different to static malware detectors while preserving its semantics. If it is possible to write a machine that can detect whether two programs carry the same semantics, then it is impossible to write "undetectable" malware.


Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are limits to what we can do, if we allow the language in which these properties are defined to be rich enough, so the answer to your question, in the general case, would have to be negative.

More specifically though, behind every specific metamorphic process that can be automated there is also a specific strategy, so there are also limits to the efficacy of those malware pieces. Because of that, it may be possible, given some knowledge of this strategy, to target its syntactical features in a controlled way, and automatically crack the code behind it, preventing it from attacking.

Malware creators have the initiative though, which gives them an advantage. This advantage can be amplified with technical skill and mathematical sophistication, so it's not advisable to base your security strategy on the ability to detect and deactivate a piece of software that already entered your system.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.