Strong Anti-SAT: Secure and Effective Logic Locking

Yuntao Liu1, Michael Zuzak1, Yang Xie1, Abhishek Chakraborty2, Ankur Srivastava1
1University of Maryland, College Park, 2University of Maryland College Park


Logic locking has been proposed as strong protection of intellectual property (IP) against security threats in the IC supply chain especially when the fabrication facility is untrusted. Such techniques use additional locking circuitry to inject incorrect behavior into the digital functionality when the key is incorrect. An attack method called the "SAT attack" provides a strong mathematical formulation to find the correct key to the locked circuits. Many conventional SAT-resilient logic locking schemes fail to inject sufficient error into the circuit when the key is incorrect: there are usually very few (or only one) input minterms that cause any error at the circuit output. The state-of-the-art stripped functionality logic locking (SFLL) technique provides a wide spectrum of configurations which introduced a trade-off between security (i.e. SAT attack complexity) and effectiveness (i.e. the amount of error injected by a wrong key). In this work, we prove that such a trade-off is universal among all logic locking techniques. In order to attain high effectiveness of locking without compromising SAT resiliency, we propose a novel secure and effective logic locking scheme, called Strong Anti-SAT (SAS). SAS has the following significant improvements over existing techniques. (1) We prove that SAS’s security against SAT attack is not compromised with higher effectiveness. (2) In contrast to prior work which focused solely on the circuit-level locking impact, we integrate SAS-locked modules into processors and show that SAS has high application-level impact. (3) SAS’s hardware overhead is smaller than those of existing techniques.