Sub-Circuit Selection and Replacement Algorithms Modeled as Term Rewriting Systems

Intent protection is a model of software obfuscation which, among other criteria, prevents an adversary from understanding the program's function for use with contextual information. Relating this framework for obfuscation to malware detection, if a malware detector can perfectly normalize a program P and any obfuscation (variant) of the program O(P), the program is not intent protected. The problem of intent protection on programs can also be modeled as intent protection on combinational logic circuits. If a malware detector can perfectly normalize a circuit C and any obfuscation (variant) O(C) of the circuit, the circuit is not intent protected. In this effort, the research group set the primary goal as determining if a malware detector based upon the mechanisms of term rewriting theory can perfectly normalize circuits transformed by a sub-circuit selection and replacement algorithm, even when the transformation algorithm is known. The research group set the secondary goal as relating this result on circuit transformations to the realm of software obfuscation. The transformation rules of the sub-circuit selection and replacement algorithm are identified and modeled as rewrite rules in a term rewriting system.