Machine learning and structural characteristics for reverse engineering

In the past years, much of the research into hardware reverse engineering has focused on the abstraction of gate level netlists to a human readable form. However, none of the proposed methods consider a realistic reverse engineering scenario, where the netlist is physically extracted from a chip. This paper analyzes the impact of errors caused by this extraction and the later partitioning of the netlist on the ability to identify the functionality. Current formal verification based methods which compare against golden models are incapable of dealing with such erroneous netlists. Two methods focusing on the idea that structural similarity implies functional similarity solve this problem: The first new approach uses fuzzy structural similarity matching to compare the structural characteristics of an unknown design against designs in a golden model library. The second new approach proposes a method for inexact graph matching using fuzzy graph isomorphisms, based on the functionalities of gates used within the design. In addition, past attacks on obfuscation methods such as logic locking have required access to an activated chip to compare the obfuscated netlist to a functionally equivalent model. The proposed methods can also find a golden model without the need of an activated chip, so that attacks can occur even before production and activation of the chip. Experiments show that for simple logic locking the approaches identify a suitable golden model in more than 80% of all cases. For realistic error percentages, both approaches can match more than 90% of designs correctly. This is an important first step for hardware reverse engineering methods beyond formal verification based equivalence matching.