Security and Complexity Analysis of LUT-based Obfuscation: A Comprehensive Study

Abstract

Logic locking and Integrated Circuit (IC) camouflaging are the most prevalent protection schemes that significantly thwart security threats, such as Intellectual Property (IP) piracy, hardware Trojans, reverse engineering, counterfeiting, and overproduction. However, the state-of-the-art attacks, including Boolean Satisfiability (SAT), Signal Probability Skew (SPS), and approximate-based attacks demonstrate the lack of having a comprehensive powerful defense scheme. Recent obfuscation schemes have employed reconfigurable logics, such as Look-up-Tables (LUTs) to prevent reverse engineering. However, existing LUT-based approaches focus on only a specific design factor such as replacement strategy or optimization metric such as SAT-hardness. In this work, we study all proposed state-of-the art hardware obfuscation and attacks and forms a rationale for studying the LUT based obfuscation technique. We then propose a comprehensive analysis on LUT-based obfuscation based on all substantial metrics that have considerable impact on design criteria, i.e. Power/Performance/Area (PPA) and Security (PPA/S). We performed a large design-for-security space exploration using four crucial factors for LUT-based obfuscation which has remarkable effect on PPA and security, namely (1) LUT technology, (2) LUT size, (3) number of LUTs, and (4) replacement strategy. Among these design parameters, the size of LUT is identified to have the most impact on making the obfuscation SAT resilient even for a weak random replacement strategy. A smarter replacement strategy helps to reduce the reliance on using large LUT to achieve SAT resiliency. Moreover, we found that while a clear trade-off exists between SAT resiliency, area and power overhead of LUT-based obfuscation, the delay trade-off can be substantially eliminated by using our proposed iterative security-driven design method which is non-disruptive to current standard ASIC design flow. Our experimental results indicate that for the studied designs, less than two iterations are sufficient to enhance the PPA/S along with eliminating the delay overhead with the proposed iterative security-driven PPA optimization. Our empirical results further demonstrate that increasing the size of LUTs from 2 to 8 provides SAT-resiliency with only less than 1% of gates replaced with LUTs.