面向输出混淆度最优化的逻辑加密线性规划方法

秦蔚蓉; 崔晓通; 程克非

doi:10.11999/JEIT250527

面向输出混淆度最优化的逻辑加密线性规划方法

doi: 10.11999/JEIT250527 cstr: 32379.14.JEIT250527

秦蔚蓉^{1, 2},
崔晓通^1, ,,
程克非¹

1.
重庆邮电大学网络空间安全与信息法学院重庆 400065
2.
中国人民解放军陆军特色医学中心重庆 400042

基金项目: 国家自然科学基金(62402080)，重庆市博士后科研项目特别资助项目(2022CQBSHTB3101)

详细信息

作者简介:
秦蔚蓉：女，硕士，研究方向为硬件安全、无线电测试

崔晓通：男，博士，副教授，研究方向为硬件安全、容错计算

程克非：男，博士，教授，研究方向为网络安全、嵌入式系统

通讯作者:
崔晓通　cuixt@cqupt.edu.cn

1¹⁾ 本文重点讨论XOR和XNOR类型的密钥门。其他类型的密钥门需进行针对性调整：对于可线性化密钥模块(即逻辑功能可通过线性方程组等价描述的模块，如由基础逻辑门组合形成的加密单元)，可依据式(1)–式(13)线性化后再代入线性规划模型求解最优插入位置；对于不可线性化密钥门模块（如LUT, MUX等逻辑功能无法直接用线性方程描述的模块），可先基于XOR/XNOR门的线性模型计算最优插入位置，再替换为目标密钥模块并插入对应位置。
中图分类号: TP309.1; TN402
计量
- 文章访问数: 2
- HTML全文浏览量: 2
- PDF下载量: 0
- 被引次数: 0
出版历程
- 收稿日期: 2025-06-09
- 修回日期: 2025-09-08
- 网络出版日期: 2025-09-12

Optimizing Output Obfuscation of Logic Locking with Linear Programming

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)

摘要

摘要: 逻辑加密通过向硬件设计中插入密钥驱动的门电路来混淆原始电路，其能够有效预防集成电路中的知识产权窃取和硬件木马等安全问题。逻辑加密方法的安全程度主要在于其结构的安全性和输出混淆度，前者决定了攻击者排除错误密钥或找到正确密钥的效率，而后者决定了攻击者寻找近似密钥方案的可行性。该文研究如何将线性规划应用于逻辑加密，并在此基础上提出一种自增长的密钥选择算法以最优化错误密钥情况下的电路输出混淆度。实验结果验证了线性规划在提升逻辑加密输出混淆度方面的有效性。
- 逻辑加密 /
- 线性规划 /
- 随机性 /
- 最优化 /
- 输出混淆度
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

HTML全文

图 1 集成电路供应链水平分工模式下的安全与可信问题

下载: 全尺寸图片幻灯片

图 2 逻辑加密使用的基本单元

下载: 全尺寸图片幻灯片

图 3 不同加密方法下的C17加密电路

下载: 全尺寸图片幻灯片

图 4 各电路在不同加密方法下海明距离达50%的输出占比

下载: 全尺寸图片幻灯片

图 5 各电路在不同加密方法下海明距离不为0%的输出占比

下载: 全尺寸图片幻灯片

表 1 FLL和LPLL在C17电路上不同密钥位数下的输出混淆度

加密方法	KeySize=1			KeySize=2			KeySize=3
加密方法	HD=0%	HD=50%	HD=100%	HD=0%	HD=50%	HD=100%	HD=0%	HD=50%	HD=100%
FLL	34	16	14	57	38	33	80	128	48
LPLL	32	32	0	54	64	10	88	128	40

下载: 导出CSV

1 基于线性规划的逻辑加密(LPLL)密钥自增长算法

输入：Circuit, KeySize
输出：Encrypted Circuit
// Circuit Preprocessing Phase
Circuit_temp ← Circuit;
foreach net_j ∈ Circuit_temp do
Insert XOR gate;
Update the Circuit_temp;
end
// Location Selection Phase
LP_Model ← ConvertToLPModel(Circuit_temp); //Convert Circuit_temp to Linear Programming model; SetObjective(LP_Model, Minimize, Objective_func); //Objective_func is expressed in equation 36;
HistoricalKeys ← $\varnothing $;
for i ← 1 to KeySize do
//update the “key_count” constraint which limits the number of keys at each iteration
RemoveOldConstraint(LP_Model, “key_count”); //remove “key_count” constraint of last iteration;
AddConstraint(LP_Model, Σ(key_j) = i, “key_count”); //add a new “key_count” constraint;
foreach key_j ∈ HistoricalKeys do
AddConstraint(LP_Model, key_j = 1); //set each key=1 that generated in previous iterations;
end
solution ← SolveLinearProgrammingModel();
selectedKeys ← {key_j \| key_j = 1 in solution}; //Extract keys with value 1 in solution
HistoricalKeys ← selectedKeys;
end
// Insert keygate Phase
foreach key_j ∈ selectedKeys do
Insert XOR or XNOR gate and update the Circuit;
end

下载: 导出CSV

参考文献(26)

[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.