Author(s): Mohamed El Massad, Siddarth Garg, Mahesh V. Tripunitara

Download: Paper (PDF)

Date: 7 Feb 2015

Document Type: Briefing Papers

Additional Documents: Slides

Associated Event: NDSS Symposium 2015


Circuit camouflaging is a recently proposed defense mechanism to protect digital integrated circuits (ICs) from reverse engineering attacks by using camouflaged gates, i.e., logic gates whose functionality cannot be precisely determined by the attacker. Recent work in CCS’13 appears to establish that an attacker requires time that is exponential in the number of camouflaged gates to reverse engineer a circuit, if the gates that are camouflaged are chosen using a procedure proposed in that work. Consequently, it appears to be the case that even by camouflaging a relatively small number of gates in the circuit, the attacker is forced to undertake several thousands of years of work. In this paper, we refute such claims. With an underlying complexity-theoretic mindset, we show that the same benchmark circuits with the camouflaged gates chosen the same way as prior work, we can decamouflage the circuit in minutes, and not years. As part of constructing our attack, we provide a precise characterization of two problems that the attacker seeks to solve to carry out his attack, and their computational complexity. A composition of solvers for the two problems is our attack procedure. We show that the two problems are co-NP-complete and NP-complete respectively, and our reduction to boolean satisfiability (SAT) and the use of off-the-shelf SAT solvers results in a highly effective attack. We also propose a new notion that we call a discriminating set of input patterns, that soundly captures the attacker’s difficulty. Our extensive empirical studies reveal that the discriminating sets of inputs for realistic circuits are surprising small, thereby providing an explanation for the effectiveness of our attack. We provide additional insights by comparing the procedure of choosing gates to be camouflaged proposed in prior work to simply choosing them randomly. After presenting the results from our attack, we provide insights into the fundamental effectiveness of IC camouflaging. Our work serves as a strong caution to designers of ICs that seek security through IC camouflaging.