Removing Redundant Logic Pathways in Polymorphic Circuits

摘要

Evaluating the quality of software and circuit obfuscators is a research goal of great interest. However, there exists little research about evaluation of obfuscation effectiveness through analyzing and investigating redundancies found in the obfuscated variants. In this research, we consider programs represented as structural combinational circuits and then analyze obfuscated variants of those circuits through a tool that produces functionally equivalent variants based on subcircuit selection and replacement. We then consider how Boolean logic and reduction affects the size and levelization of circuit variants, giving us a concrete metric by which to consider obfuscation effectiveness. To accomplish these goals, we create an experimental environment based on a set of predefined circuits, a set of predefined algorithms which produce variants of those circuits, and a collection of logic reduction techniques and tools. We build logic reduction techniques using predefined patterns and predefined functions expressed as truth tables. As a contribution, we characterize and evaluate the effectiveness of obfuscating algorithms based on these reduction techniques. We show, for the circuits we observe, optimization on size is affected by ordering of the specific reduction patterns and functions. We also show, for the circuits we observe, reduction is affected by the specific obfuscating algorithm used to produce the variant. Based on these results, we provide a promising measurement of interest to compare both circuit variants and obfuscating algorithms.