Complexity of a Special Deobfuscation Problem

摘要

This paper considers process of obfuscation as adding additional (redundant) entities to the program at intermediate representation that would complicate the understanding of entangled code. The presented mathematical apparatus discusses introductory terms, definitions, and operations and formulates a theorem about NP-completeness of such deobfuscation problem. We show that the problem of determining the significance of the operational logic in the obfuscated routine is reduced to the Boolean satisfiability problem. The limits of applicability of the theorem are mentioned and an approach is offered that can significantly reduce the probability of creating a deobfuscator running in polynomial time.