Sub-Circuit Selection and Replacement Algorithms Modeled as Term Rewriting Systems
Abstract
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. These rewrite rules are examined for critical overlaps which cannot be resolved by a widely used completion algorithm known as Knuth-Bendix. The research group performs an analysis of the critical overlaps found within the rewrite rules and successfully relates these results to the instruction-substitution obfuscations of a software obfuscator.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 16, 2008
- Accession Number
- ADA493071
Entities
People
- Eric D. Simonaire
Organizations
- Air Force Institute of Technology