research-article

Tunable FPGA Bitstream Obfuscation with Boolean Satisfiability Attack Countermeasure

Authors:

Robert KaramAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 25, Issue 2

Article No.: 19, Pages 1 - 22

https://doi.org/10.1145/3373638

Published: 03 February 2020 Publication History

Abstract

Field Programmable Gate Arrays (FPGAs) are seeing a surge in usage in many emerging application domains, where the in-field reconfigurability is an attractive characteristic for diverse applications with dynamic design requirements, such as cloud computing, automotive, IoT, and aerospace. The security of the FPGA configuration file, or bitstream, is critical, especially for devices with long in-field lifetimes, where attackers may attempt to extract valuable Intellectual Property (IP) from within. In this article, we propose a tunable obfuscation approach that protects IP from typical bitstream attacks while enabling designers to trade off security with acceptable overhead. We also consider two potential attacks on this protection mechanism: Boolean SAT Attacks on the obfuscation and removal attacks on the protection circuitry. The obfuscation and SAT countermeasure are integrated in a custom CAD framework within a commercial FPGA toolflow and together provide mathematically strong protection against common bitstream attacks. Further, we quantify the difficulty of a removal attack on the protection circuitry through pattern matching and direct bitstream manipulation. The average area, power, and delay overhead for obfuscation with 95% mismatch probability are 18%, 16%, and 8%, respectively, for small combinational circuits, and 1%, 2%, and 5% for larger arithmetic modules.

References

[1]

2012. Introduction to FPGA Technology: Top 5 Benefits. National Instruments. Retrieved from http://www.ni.com/en-us/innovations/white-papers/08/fpga-fundamentals.html.

[2]

M. Al-Asli, M. E. S. Elrabaa, and M. Abu-Amara. 2019. FPGA-based symmetric re-encryption scheme to secure data processing for cloud-integrated Internet of Things. IEEE Int. Things J. 6, 1 (Feb. 2019), 446--457.

[3]

F. Benz, A. Seffrin, and S. A. Huss. 2012. Bil: A tool-chain for bitstream reverse-engineering. In Proceedings of the 22nd International Conference on Field Programmable Logic and Applications (FPL’12). 735--738.

[4]

R. S. Chakraborty, I. Saha, A. Palchaudhuri, and G. K. Naik. 2013. Hardware trojan insertion by direct modification of FPGA configuration bitstream. IEEE Des. Test 30, 2 (Apr. 2013), 45--54.

[5]

Yung-Chih Chen. 2017. Tree-based logic encryption for resisting SAT attack. In Proceedings of the IEEE 26th Asian Test Symposium (ATS’17). 46--51.

[6]

Yung-Chih Chen. 2018. Enhancements to SAT attack: Speedup and breaking cyclic logic encryption. ACM Trans. Des. Autom. Electron. Syst. 23, 4, Article 52 (May 2018), 25 pages.

Digital Library

[7]

K. Dang Pham, E. Horta, and D. Koch. 2017. BITMAN: A tool and API for FPGA bitstream manipulations. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE’17). 894--897.

[8]

S. Dupuis, P. Ba, G. Di Natale, M. Flottes, and B. Rouzeyre. 2014. A novel hardware logic encryption technique for thwarting illegal overproduction and hardware trojans. In Proceedings of the IEEE 20th International On-Line Testing Symposium (IOLTS’14). 49--54.

[9]

N. B. Gaikwad, V. Tiwari, A. Keskar, and N. C. Shivaprakash. 2019. Efficient FPGA implementation of multilayer perceptron for real-time human activity classification. IEEE Access 7 (2019), 26696--26706.

[10]

Intel. 2015. Quartus II Handbook Version 15.0.0. Intel.

[11]

Vinayaka Jyothi and Jeyavijayan J. V. Rajendran. 2018. Hardware Trojan Attacks in FPGA and Protection Approaches. Springer, 345--368.

[12]

Robert K. Brayton and Alan Mishchenko. 2010. ABC: An academic industrial-strength verification tool. In Proceedings of the International Conference on Computer Aided Verification, Vol. 6174. 24--40.

[13]

R. Karam, T. Hoque, S. Ray, M. Tehranipoor, and S. Bhunia. 2016. Robust bitstream protection in FPGA-based systems through low-overhead obfuscation. In Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig’16). 1--8.

[14]

Richard L. Rudell and Alberto Sangiovanni-Vincentelli. 1987. Multiple-valued minimization for PLA optimization. IEEE Trans. Comput.-Aided Des. Integ. Circ. Syste. 6 (10 1987), 727--750.

[15]

Heiko Lohrke, Shahin Tajik, Thilo Krachenfels, Christian Boit, and Jean-Pierre Seifert. 2018. Key Extraction using Thermal Laser Stimulation: A Case Study on Xilinx Ultrascale FPGAs. Cryptology ePrint Archive, Report 2018/717. Retrieved from https://eprint.iacr.org/2018/717.

[16]

S. Mal-Sarkar, R. Karam, S. Narasimhan, A. Ghosh, A. Krishna, and S. Bhunia. 2016. Design and validation for FPGA trust under hardware trojan attacks. IEEE Trans. Multi-scale Comput. Syst. 2, 3 (July 2016), 186--198.

[17]

H. Mardani Kamali, K. Zamiri Azar, K. Gaj, H. Homayoun, and A. Sasan. 2018. LUT-lock: A novel LUT-based logic obfuscation for FPGA-bitstream and ASIC-hardware protection. In Proceedings of the IEEE Computer Society Symposium on VLSI (ISVLSI’18). 405--410.

[18]

Mentor Graphics Corporation. 2012. ModelSim User’s Manual (10.5c ed.). Mentor Graphics Corporation.

[19]

K. Mershad, H. Artail, M. A. R. Saghir, H. Hajj, and M. Awad. 2017. A study of the performance of a cloud datacenter server. IEEE Trans. Cloud Comput. 5, 4 (Oct. 2017), 590--603.

[20]

Alan Mishchenko, Roland Jiang, Satrajit Chatterjee, and Robert Brayton. 2004. FRAIGs: Functionally reduced AND-INV graphs. (01 2004). Retrieved from https://people.eecs.berkeley.edu/&sim;alanmi/research/fraigs/fraigs.pdf.

[21]

E. Monmasson, L. Idkhajine, M. N. Cirstea, I. Bahri, A. Tisan, and M. W. Naouar. 2011. FPGAs in industrial control applications. IEEE Trans. Industr. Inf. 7, 2 (May 2011), 224--243.

[22]

Amir Moradi, Alessandro Barenghi, Timo Kasper, and Christof Paar. 2011. On the vulnerability of FPGA bitstream encryption against power analysis attacks: Extracting keys from Xilinx Virtex-II FPGAs. IACR Cryptology ePrint Archive 2011 (10 2011), 111--124.

Digital Library

[23]

Amir Moradi, David Oswald, Christof Paar, and Pawel Swierczynski. 2013. Side-channel attacks on the bitstream encryption mechanism of Altera Stratix II: Facilitating black-box analysis using software reverse-engineering. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA’13). 91--100.

Digital Library

[24]

J.-B. Note and E. Rannaud. 2008. From the bitstream to the netlist. In Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays (FPGA’08). 8 (01 2008).

Digital Library

[25]

J. Rajendran, Y. Pino, O. Sinanoglu, and R. Karri. 2012. Security analysis of logic obfuscation. In Proceedings of the Design Automation Conference (DAC’12). 83--89.

[26]

J. Rajendran, H. Zhang, C. Zhang, G. S. Rose, Y. Pino, O. Sinanoglu, and R. Karri. 2015. Fault analysis-based logic encryption. IEEE Trans. Comput. 64, 2 (Feb. 2015), 410--424.

Digital Library

[27]

A. Rezaei, Y. Shen, S. Kong, J. Gu, and H. Zhou. 2018. Cyclic locking and memristor-based obfuscation against CycSAT and inside foundry attacks. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE’18). 85--90.

[28]

J. A. Roy, F. Koushanfar, and I. L. Markov. 2008. EPIC: Ending piracy of integrated circuits. In Proceedings of the Design, Automation and Test in Europe Conference. 1069--1074.

[29]

Raymond Shanahan. 2017. Field Programmable Gate Array (FPGA) Assurance. Technical Report. United States Department of Defense. Retrieved from https://www.acq.osd.mil/se/briefs/19864-NDIA17-Shanahan-FPGA.pdf.

[30]

Yuanqi Shen and Hai Zhou. 2017. Double DIP: Re-evaluating security of logic encryption algorithms. 179--184.

[31]

S. Shreejith and S. A. Fahmy. 2015. Extensible FlexRay communication controller for FPGA-based automotive systems. IEEE Trans. Vehic. Technol. 64, 2 (Feb. 2015), 453--465.

[32]

Pramod Subramanyan, Sayak Ray, and Sharad Malik. 2015. Evaluating the security of logic encryption algorithms. In Proceedings of the IEEE International Symposium on Hardware-Oriented Security and Trust. 137--143.

[33]

P. Swierczynski, M. Fyrbiak, P. Koppe, and C. Paar. 2015. FPGA trojans through detecting and weakening of cryptographic primitives. IEEE Trans. Comput.-aided Des. Integ. Circ. Syst. 34, 8 (Aug. 2015), 1236--1249.

[34]

Y. Xie and A. Srivastava. 2019. Anti-SAT: Mitigating SAT attack on logic locking. IEEE Trans. Comput.-Aided Des. Integ. Circ. Syst. 38, 2 (Feb. 2019), 199--207.

Digital Library

[35]

Saeyang Yang. 1991. Logic Synthesis and Optimization Benchmarks User Guide Version 3.0. Microelectronics Center of North Carolina (04 1991).

[36]

M. Yasin, B. Mazumdar, J. J. V. Rajendran, and O. Sinanoglu. 2016. SARLock: SAT attack resistant logic locking. In Proceedings of the IEEE International Symposium on Hardware Oriented Security and Trust (HOST’16). 236--241.

[37]

H. Zhou, R. Jiang, and S. Kong. 2017. CycSAT: SAT-based attack on cyclic logic encryptions. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’17). 49--56.

Cited By

Surabhi VSadhukhan RRaz MPearce HKrishnamurthy PTrujillo JKarri RKhorrami F(2024)FEINT: Automated Framework for Efficient INsertion of Templates/Trojans into FPGAsInformation10.3390/info1507039515:7(395)Online publication date: 8-Jul-2024
https://doi.org/10.3390/info15070395
Zhao HRatazzi P(2024)A Lightweight Hardware-Assisted Security Method for eFPGA Edge DevicesIEEE Internet of Things Journal10.1109/JIOT.2024.339166111:13(23673-23682)Online publication date: 1-Jul-2024
https://doi.org/10.1109/JIOT.2024.3391661
Alsuwaiyan AHabib AImoukhuede AOmar MMaruf MAlqarni MEl-Maleh ATabbakh AFelemban MAzim A(2024)A Systematic Literature Review on Vulnerabilities, Mitigation Techniques, and Attacks in Field-Programmable Gate ArraysArabian Journal for Science and Engineering10.1007/s13369-024-09562-wOnline publication date: 23-Sep-2024
https://doi.org/10.1007/s13369-024-09562-w
Show More Cited By

Index Terms

Tunable FPGA Bitstream Obfuscation with Boolean Satisfiability Attack Countermeasure
1. Hardware
  1. Electronic design automation
    1. Hardware description languages and compilation
2. Security and privacy
  1. Security in hardware
    1. Hardware attacks and countermeasures
      1. Malicious design modifications
    2. Hardware reverse engineering

Recommendations

On the vulnerability of FPGA bitstream encryption against power analysis attacks: extracting keys from xilinx Virtex-II FPGAs
CCS '11: Proceedings of the 18th ACM conference on Computer and communications security

Over the last two decades FPGAs have become central components for many advanced digital systems, e.g., video signal processing, network routers, data acquisition and military systems. In order to protect the intellectual property and to prevent fraud, ...
Semi-invasive EM attack on FPGA RO PUFs and countermeasures
WESS '11: Proceedings of the Workshop on Embedded Systems Security

It is often argued that Physical Unclonable Functions (PUFs) are resistant against invasive and semi-invasive attacks since these attacks would damage the underlying PUF structure resulting in a different PUF response. In this paper, we demonstrate ...
A synthesizable datapath-oriented embedded FPGA fabric
FPGA '07: Proceedings of the 2007 ACM/SIGDA 15th international symposium on Field programmable gate arrays

We present an architecture for a synthesizable datapath-oriented Field Programmable Gate Array (FPGA) core which can be used to provide post-fabrication flexibility to a System-on-Chip (SoC). Our architecture is optimized for bus-based operations that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 25, Issue 2

March 2020

256 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3375457

Editor:
Naehyuck Chang
Korea Advanced Institute of Science and Technology, Korea

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 03 February 2020

Accepted: 01 November 2019

Revised: 01 October 2019

Received: 01 June 2019

Published in TODAES Volume 25, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
355
Total Downloads

Downloads (Last 12 months)36
Downloads (Last 6 weeks)6

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Surabhi VSadhukhan RRaz MPearce HKrishnamurthy PTrujillo JKarri RKhorrami F(2024)FEINT: Automated Framework for Efficient INsertion of Templates/Trojans into FPGAsInformation10.3390/info1507039515:7(395)Online publication date: 8-Jul-2024
https://doi.org/10.3390/info15070395
Zhao HRatazzi P(2024)A Lightweight Hardware-Assisted Security Method for eFPGA Edge DevicesIEEE Internet of Things Journal10.1109/JIOT.2024.339166111:13(23673-23682)Online publication date: 1-Jul-2024
https://doi.org/10.1109/JIOT.2024.3391661
Alsuwaiyan AHabib AImoukhuede AOmar MMaruf MAlqarni MEl-Maleh ATabbakh AFelemban MAzim A(2024)A Systematic Literature Review on Vulnerabilities, Mitigation Techniques, and Attacks in Field-Programmable Gate ArraysArabian Journal for Science and Engineering10.1007/s13369-024-09562-wOnline publication date: 23-Sep-2024
https://doi.org/10.1007/s13369-024-09562-w
Zhang TRahman FTehranipoor MFarahmandi F(2023)FPGA-Chain: Enabling Holistic Protection of FPGA Supply Chain With Blockchain TechnologyIEEE Design & Test10.1109/MDAT.2022.321399840:2(127-136)Online publication date: Apr-2023
https://doi.org/10.1109/MDAT.2022.3213998
Moraitis MDubrova E(2023)FPGA Design Deobfuscation by Iterative LUT Modification at Bitstream LevelJournal of Hardware and Systems Security10.1007/s41635-022-00130-y7:1(11-24)Online publication date: 16-Feb-2023
https://doi.org/10.1007/s41635-022-00130-y
Olney BKaram R(2022)Diverse, Neural Trojan Resilient Ecosystem of Neural Network IPACM Journal on Emerging Technologies in Computing Systems10.1145/347118918:3(1-23)Online publication date: 2-Feb-2022
https://dl.acm.org/doi/10.1145/3471189
Sunkavilli SZhang ZYu Q(2021)New Security Threats on FPGAs: From FPGA Design Tools Perspective2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI51109.2021.00058(278-283)Online publication date: Jul-2021
https://doi.org/10.1109/ISVLSI51109.2021.00058
Mahmud SOlney BKaram R(2021)An Extensible Evaluation Platform for FPGA Bitstream Obfuscation Security2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)10.1109/ISVLSI51109.2021.00032(120-125)Online publication date: Jul-2021
https://doi.org/10.1109/ISVLSI51109.2021.00032
Danesh WBanago JRahman M(2021)Turning the Table: Using Bitstream Reverse Engineering to Detect FPGA TrojansJournal of Hardware and Systems Security10.1007/s41635-021-00122-4Online publication date: 1-Nov-2021
https://doi.org/10.1007/s41635-021-00122-4

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents