Optimizing Output Obfuscation of Logic Locking with Linear Programming

QIN Weirong; CUI Xiaotong; CHENG Kefei

doi:10.11999/JEIT250527

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

QIN Weirong, CUI Xiaotong, CHENG Kefei. Optimizing Output Obfuscation of Logic Locking with Linear Programming[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250527

Citation:

QIN Weirong, CUI Xiaotong, CHENG Kefei. Optimizing Output Obfuscation of Logic Locking with Linear Programming[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250527

QIN Weirong, CUI Xiaotong, CHENG Kefei. Optimizing Output Obfuscation of Logic Locking with Linear Programming[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250527

Citation:

QIN Weirong, CUI Xiaotong, CHENG Kefei. Optimizing Output Obfuscation of Logic Locking with Linear Programming[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250527

PDF( 2240 KB)

Optimizing Output Obfuscation of Logic Locking with Linear Programming

doi: 10.11999/JEIT250527 cstr: 32379.14.JEIT250527

QIN Weirong^{1, 2},
CUI Xiaotong^{1
,
,},
CHENG Kefei¹

1.
School of Cyber Security and Information Law, Chongqing University of Posts and Telecommunications, Chongqing 400065, China
2.
Army Medical Center, Chongqing 400042, China

Funds: the National Natural Science Foundation of China (NSFC 62402080), Chongqing Special Funding for Postdoctoral Research Projects (2022CQBSHTB3101)

Received Date: 2025-06-09
Rev Recd Date: 2025-09-08

Available Online: 2025-09-12

Abstract

Abstract

Objective The globalization of the Integrated Circuit (IC) supply chain has created a crisis of hardware trust, exposing systems to hardware security threats. Logic locking, a key Design-For-Trust (DFT) technique, protects hardware designs by inserting key-driven gates that obfuscate the original circuit, thereby mitigating threats such as intellectual property theft and hardware Trojans. The effectiveness of logic locking is determined by its output obfuscation level, which directly influences resilience against existing attacks. This level is quantified by two sub-metrics: randomness and inconsistency. Weakness in either sub-metric enables targeted attacks, and current methods achieve limited performance on both, restricting their practical security guarantees. To address these limitations, this study proposes a logic locking approach that improves the output obfuscation level of locked circuits using linear programming. Methods A Linear Programming-based Logic Locking (LPLL) method is proposed to optimize output obfuscation under incorrect keys. The core idea is to model each circuit gate as a set of linear constraints, thereby transforming the objective of maximizing the output obfuscation level into a solvable linear objective function. This formulation determines the optimal placement of key gates that are specifically activated by incorrect keys. Because adversaries in real-world attack scenarios rely on random key guessing, key gates may remain inactive, leading to weakened obfuscation. To address this vulnerability, an auto-incrementing key selection algorithm is introduced. This algorithm iteratively builds upon and inherits prior optimization results, thereby strengthening robustness. The iterative mechanism ensures persistent output corruption: even if key gates selected at later stages remain inactive, obfuscation is still enforced by those optimized in earlier iterations. Results and Discussions Experimental results demonstrate that the proposed LPLL method substantially enhances output obfuscation. For equivalent key sizes, LPLL markedly increases the randomness of output obfuscation, consistently sustaining a high degree of unpredictability. Quantitatively, it improves the probability of randomness by up to 24.1% compared with Fault analysis-based Logic Locking (FLL) and by 49.9% compared with Random Logic Locking (RLL) (Fig. 4). In addition to randomness, LPLL exhibits a clear advantage in output obfuscation inconsistency. While both LPLL and FLL achieve improved inconsistency with increasing key sizes, LPLL consistently reaches higher inconsistency values across most scenarios. Specifically, it raises the probability of inconsistency by up to 26.2% relative to FLL and by 62.5% relative to RLL (Fig. 5). This advantage is particularly pronounced at smaller key sizes, where LPLL achieves greater inconsistency spread and more efficient key utilization, making it especially suitable for resource-constrained applications. Conclusions This work presents LPLL, an approach that redefines logic locking by mapping complex circuit structures onto a linear programming model. The method systematically formulates optimal key-gate selection as a solvable linear optimization problem. To further strengthen security, LPLL incorporates an auto-incrementing key selection algorithm that establishes an iterative mechanism, ensuring persistent high-level output obfuscation even under dynamic attack conditions. LPLL not only exceeds existing methods such as RLL and FLL)in output obfuscation metrics but, more importantly, provides a systematic and quantifiable paradigm for determining key-gate layouts. This research offers a forward-looking perspective for the design of trustworthy hardware.
- Logic locking,
- Linear programming,
- Randomness,
- Optimization,
- Output obfuscation

FullText(HTML)

References(26)

References

[1]	TEHRANIPOOR M and KOUSHANFAR F. A survey of hardware Trojan taxonomy and detection[J]. IEEE Design & Test of Computers, 2010, 27(1): 10–25. doi: 10.1109/MDT.2010.7.
[2]	GUBBI K I, SABER LATIBARI B, SRIKANTH A, et al. Hardware Trojan detection using machine learning: A tutorial[J]. ACM Transactions on Embedded Computing Systems, 2023, 22(3): 1–26. doi: 10.1145/3579823.
[3]	YASAEI R, CHEN Luke, YU S Y, et al. Hardware Trojan detection using graph neural networks[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2025, 44(1): 25–38. doi: 10.1109/TCAD.2022.3178355.
[4]	YASAEI R, YU S Y, NAEINI E K, et al. GNN4IP: Graph neural network for hardware intellectual property piracy detection[C]. Proceedings of the 58th Annual ACM/IEEE Design Automation Conference, San Francisco, USA, 2021: 217–222. doi: 10.1109/DAC18074.2021.9586150.
[5]	DÍAZ-RIZO A R, ABOUSHADY H, and STRATIGOPOULOS H G. Anti-piracy design of RF transceivers[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2023, 70(1): 492–505. doi: 10.1109/TCSI.2022.3214111.
[6]	CUI Aobo, ZHANG Dongrong, REN Qiang, et al. A novel dual logic locking method to prevent counterfeit IP/IC[C]. 2022 IEEE International Test Conference in Asia (ITC-Asia), Taipei, China, 2022: 79–84. doi: 10.1109/ITCAsia55616.2022.00024.
[7]	TEHRANIPOOR M, PUNDIR N, VASHISTHA N, et al. Hardware Security Primitives[M]. Cham: Springer, 2023. doi: 10.1007/978-3-031-19185-5.
[8]	ZHANG Ruisi, RAJARATHNAM R S, PAN D Z, et al. ICMarks: A robust watermarking framework for integrated circuit physical design IP protection[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2025. doi: 10.1109/TCAD.2025.3552503. (查阅网上资料,未找到本条文献卷期页码信息,请确认).
[9]	DAS U, RAHMAN M S, ANANDAKUMAR N N, et al. PSC-watermark: Power side channel based IP watermarking using clock gates[C]. 2023 IEEE European Test Symposium (ETS), Venezia, Italy, 2023: 1–6. doi: 10.1109/ETS56758.2023.10174052.
[10]	KOUSHANFAR F and QU Gang. Hardware metering[C]. Proceedings of the 38th annual Design Automation Conference, Las Vegas, USA, 2001: 490–493. doi: 10.1145/378239.378568.
[11]	ALKABANI Y M and KOUSHANFAR F. Active hardware metering for intellectual property protection and security[C]. Proceedings of 16th USENIX Security Symposium on USENIX Security Symposium, Boston, USA, 2007: 20.
[12]	KOUSHANFAR F. Provably secure sequential obfuscation for IC metering and piracy avoidance[J]. IEEE Design & Test, 2021, 38(3): 51–57. doi: 10.1109/MDAT.2021.3065324.
[13]	ALAQL A, CHATTOPADHYAY S, CHAKRABORTY P, et al. LeGO: A learning-guided obfuscation framework for hardware IP protection[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(4): 854–867. doi: 10.1109/TCAD.2021.3075939.
[14]	SHAKYA B, TEHRANIPOOR M M, BHUNIA S, et al. Introduction to hardware obfuscation: Motivation, methods and evaluation[J]. Hardware Protection Through Obfuscation, 2017: 3–32. doi: 10.1007/978-3-319-49019-9_1.
[15]	HOQUE T, CHAKRABORTY R S, and BHUNIA S. Hardware obfuscation and logic locking: A tutorial introduction[J]. IEEE Design & Test, 2020, 37(3): 59–77. doi: 10.1109/MDAT.2020.2984224.
[16]	ROY J A, KOUSHANFAR F, and MARKOV I L. EPIC: Ending piracy of integrated circuits[C]. 2008 Design, Automation and Test in Europe, Munich, Germany, 2008: 1069–1074. doi: 10.1109/DATE.2008.4484823.
[17]	YASIN M, RAJENDRAN J J, SINANOGLU O, et al. On improving the security of logic locking[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2016, 35(9): 1411–1424. doi: 10.1109/TCAD.2015.2511144.
[18]	RAJENDRAN J, ZHANG Huan, ZHANG Chi, et al. Fault analysis-based logic encryption[J]. IEEE Transactions on Computers, 2015, 64(2): 410–424. doi: 10.1109/TC.2013.193.
[19]	SUBRAMANYAN P, RAY S, and MALIK S. Evaluating the security of logic encryption algorithms[C]. 2015 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), Washington, USA, 2015: 137–143. doi: 10.1109/HST.2015.7140252.
[20]	YASIN M, MAZUMDAR B, RAJENDRAN J J V, et al. SARLock: SAT attack resistant logic locking[C]. 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), McLean, USA, 2016: 236–241. doi: 10.1109/HST.2016.7495588.
[21]	XIE Yang and SRIVASTAVA A. Mitigating SAT attack on logic locking[C]. Proceedings of the 18th International Conference International Conference on Cryptographic Hardware and Embedded Systems – CHES 2016, Santa Barbara, USA, 2016: 127–146. doi: 10.1007/978-3-662-53140-2_7.
[22]	YASIN M, MAZUMDAR B, SINANOGLU O, et al. Removal attacks on logic locking and camouflaging techniques[J]. IEEE Transactions on Emerging Topics in Computing, 2020, 8(2): 517–532. doi: 10.1109/TETC.2017.2740364.
[23]	SHAMSI K, LI Meng, MEADE T, et al. AppSAT: Approximately deobfuscating integrated circuits[C]. 2017 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), Mclean, USA, 2017: 95–100. doi: 10.1109/HST.2017.7951805.
[24]	LIMAYE N, KALLIGEROS E, KAROUSOS N, et al. Thwarting all logic locking attacks: Dishonest oracle with truly random logic locking[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021, 40(9): 1740–1753. doi: 10.1109/TCAD.2020.3029133.
[25]	KAMALI H M, AZAR K Z, FARAHMANDI F, et al. Advances in logic locking: Past, present, and prospects[EB/OL]. Cryptology ePrint Archive, https://eprint.iacr.org/2022/260, 2022.
[26]	AZAR K Z, KAMALI H M, FARAHMANDI F, et al. Understanding Logic Locking[M]. Cham: Springer, 2024.