Incremental SAT-Based Reverse Engineering of Camouflaged Logic Circuits.

Layout-level gate or routing camouflaging techniques have attracted interest as countermeasures against reverse engineering of combinational logic. In order to minimize area overhead, typically only a subset of gate or routing components are camouflaged, and each camouflaged component layout can implement one of a few different functions or connections. The security of camouflaging relies on the difficulty of learning the overall combinational logic function without knowing the functions implemented by the individual camouflaged components of the circuit. In this paper, we expand our previous work on using incremental SAT solving to reconstruct the logical function of a circuit with camouflaged components. Our algorithm uses the standard attacker model in which an adversary knows only the noncamouflaged component functions, and has the ability to query the circuit to learn the correct output vector for any input vector. Our results demonstrate a $10.5\times$ speedup in average runtime over the best known existing deobfuscation algorithm prior to this technique. The results presented go beyond our previous work by showing that this technique, previously applied only to a particular style of gate camouflaging, is general and can be used to deobfuscate three different proposed styles of camouflaging. We give results to quantify the effectiveness of camouflaging techniques on a variety of ISCAS-85 benchmark circuits. [ABSTRACT FROM PUBLISHER]