Graph Centrality Algorithms for Hardware Trojan Detection at Gate-Level Netlists

Document Type : Original Article


1 School of Electrical and Computer Engineering, College of Engineering, University of Tehran, Tehran, Iran

2 Department of Computer Engineering, Sharif University of Technology, Tehran, Iran


The rapid growth in the supply chain of electronic devices has led companies to purchase Intellectual Property or Integrated Circuits from unreliable sources. This dispersion in the design to fabrication stages of IP/IC has led to new attacks called hardware Trojans. Hardware Trojans can bargain information, reduce performance, or cause failure. Various methods have been introduced to detect or prevent hardware Trojans. Machine learning methods are one of these. Selecting the type and number of input variables in the learning algorithm has an important role in the performance of the learning model. Some previous hardware Trojan detection studies have used structural gate-level features to create data sets for machine learning models. In this paper, a method based on directed graphs for extracting features is proposed. The proposed method use Graph Centrality Algorithm and structural gate-level features. To examine the importance and the impact of the extracted features with the proposed method, three types of data sets are created as input to the learning model made with XGBoost. The trained learning models based on these three data sets show that extracting graph-based features has improved the F1-score by 10% and the ROC by 22%. The combination of these features with the structural gate-level features improved the F1-score by 17.5% and the ROC by 38.5%.


Main Subjects

  1. Bhunia, S., Hsiao, M.S., Banga, M. and Narasimhan, S., "Hardware trojan attacks: Threat analysis and countermeasures", Proceedings of the IEEE, Vol. 102, No. 8, (2014), 1229-1247, doi: 10.1109/JPROC.2014.2334493.
  2. Goldstein, L.H. and Thigpen, E.L., "Scoap: Sandia controllability/observability analysis program", in Proceedings of the 17th Design Automation Conference., (1980), 190-196, doi: 10.1145/800139.804528.
  3. Esfandian, N. and Hosseinpour, K., "A clustering-based approach for features extraction in spectro-temporal domain using artificial neural network", International Journal of Engineering,Transactions B: Applications, Vol. 34, No. 2, (2021), 452-457, doi: 10.5829/IJE.2021.34.02B.17.
  4. Chen, T. and Guestrin, C., "Xgboost: A scalable tree boosting system", in Proceedings of the 22nd acm sigkdd international conference on knowledge discovery anionsd data mining. Vol., No. Issue, (2016), 785-794, doi: 10.1145/2939672.2939785.
  5. Yang, Y., Ye, J., Cao, Y., Zhang, J., Li, X., Li, H. and Hu, Y., "Survey: Hardware trojan detection for netlist", in 2020 IEEE 29th Asian Test Symposium (ATS), IEEE. , (2020), 1-6, doi: 10.1109/ATS49688.2020.9301614.
  6. Hicks, M., Finnicum, M., King, S.T., Martin, M.M. and Smith, J.M., "Overcoming an untrusted computing base: Detecting and removing malicious hardware automatically", in 2010 IEEE symposium on security and privacy, IEEE., (2010), 159-172, doi: 10.1109/SP.2010.18.
  7. Zhang, J., Yuan, F., Wei, L., Liu, Y. and Xu, Q., "Veritrust: Verification for hardware trust", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 34, No. 7, (2015), 1148-1161, doi: 10.1109/TCAD.2015.2422836.
  8. Waksman, A., Suozzo, M. and Sethumadhavan, S., "FANCI: Identification of stealthy malicious logic using boolean functional analysis", in Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security., (2013), 697-708, doi: 10.1145/2508859.2516654.
  9. Fyrbiak, M., Wallat, S., Swierczynski, P., Hoffmann, M., Hoppach, S., Wilhelm, M., Weidlich, T., Tessier, R. and Paar, C., "Hal—the missing piece of the puzzle for hardware reverse engineering, trojan detection and insertion", IEEE Transactions on Dependable and Secure Computing, Vol. 16, No. 3, (2018), 498-510, doi: 10.1109/TDSC.2018.2812183.
  10. Sullivan, D., Biggers, J., Zhu, G., Zhang, S. and Jin, Y., "Fight-metric: Functional identification of gate-level hardware trustworthiness", in Proceedings of the 51st Annual Design Automation Conference., (2014), 1-4, doi: 10.1145/2593069.2596681.
  11. Hasegawa, K., Oya, M., Yanagisawa, M. and Togawa, N., "Hardware trojans classification for gate-level netlists based on machine learning", in 2016 IEEE 22nd International Symposium on On-Line Testing and Robust System Design (IOLTS), IEEE., (2016), 203-206, doi: 10.1109/IOLTS.2016.7604700.
  12. Hasegawa, K., Yanagisawa, M. and Togawa, N., "Trojan-feature extraction at gate-level netlists and its application to hardware-trojan detection using random forest classifier", in 2017 IEEE International Symposium on Circuits and Systems (ISCAS), IEEE., (2017), 1-4, doi: 10.1109/ISCAS.2017.8050827.
  13. Ye, J., Yang, Y., Gong, Y., Hu, Y. and Li, X., "Grey zone in pre-silicon hardware trojan detection", in 2018 IEEE International Test Conference in Asia (ITC-Asia), IEEE., (2018), 79-84, doi: 10.1109/ITC-Asia.2018.00024.
  14. Salmani, H., Tehranipoor, M. and Karri, R., "On design vulnerability analysis and trust benchmarks development", in 2013 IEEE 31st international conference on computer design (ICCD), IEEE., (2013), 471-474, doi: 10.1109/ICCD.2013.6657085.
  15. Shakya, B., He, T., Salmani, H., Forte, D., Bhunia, S. and Tehranipoor, M., "Benchmarking of hardware trojans and maliciously affected circuits", Journal of Hardware and Systems Security, Vol. 1, No. 1, (2017), 85-102, doi: 10.1007/s41635-017-0001-6.
  16. Hoque, T., Cruz, J., Chakraborty, P. and Bhunia, S., "Hardware ip trust validation: Learn (the untrustworthy), and verify", in 2018 IEEE International Test Conference (ITC), IEEE., (2018), 1-10, doi: 10.1109/TEST.2018.8624727.
  17. Salmani, H., "COTD: Reference-free hardware trojan detection and recovery based on controllability and observability in gate-level netlist", IEEE Transactions on Information Forensics and Security, Vol. 12, No. 2, (2016), 338-350, doi: 10.1109/TIFS.2016.2613842.
  18. Xie, X., Sun, Y., Chen, H. and Ding, Y., "Hardware trojans classification based on controllability and observability in gate-level netlist", IEICE Electronics Express, Vol. 14, No. 18, (2017), 20170682-20170682, doi: 10.1587/elex.14.20170682.
  19. Wang, Y., Han, T., Han, X. and Liu, P., "Ensemble-learning-based hardware trojans detection method by detecting the trigger nets", in 2019 IEEE International Symposium on Circuits and Systems (ISCAS), IEEE., (2019), 1-5, doi: 10.1109/ISCAS.2019.8702539.
  20. Kurihara, T. and Togawa, N., "Hardware-trojan classification based on the structure of trigger circuits utilizing random forests", in 2021 IEEE 27th International Symposium on On-Line Testing and Robust System Design (IOLTS), IEEE., (2021), 1-4, doi: 10.1109/IOLTS52814.2021.9486700.
  21. Hagberg, A., Swart, P. and S Chult, D., Exploring network structure, dynamics, and function using networkx. 2008, Los Alamos National Lab.(LANL), Los Alamos, NM (United States).
  22. Brandes, U., "A faster algorithm for betweenness centrality", Journal of Mathematical Sociology, Vol. 25, No. 2, (2001), 163-177, doi: 10.1080/0022250X.2001.9990249.
  23. Chen, D., Lü, L., Shang, M.-S., Zhang, Y.-C. and Zhou, T., "Identifying influential nodes in complex networks", Physica a: Statistical mechanics and its applications, Vol. 391, No. 4, (2012), 1777-1787, doi: 10.1016/j.physa.2011.09.017.
  24. Rodrigues, F.A., "Network centrality: An introduction", in A mathematical modeling approach from nonlinear dynamics to complex systems. 2019, Springer. 177-196, doi: 10.48550/arXiv.1901.07901.
  25. Upstill, T., Craswell, N. and Hawking, D., "Predicting fame and fortune: Pagerank or indegree?", (2003).
  26. Jaderyan, M. and Khotanlou, H., "Automatic hashtag recommendation in social networking and microblogging platforms using a knowledge-intensive content-based approach", International Journal of Engineering, Transactions B: Applications, Vol. 32, No. 8, (2019), 1101-1116, doi: 10.5829/IJE.2019.32.08B.06.
  27. Liu, Q., Zhao, P. and Chen, F., "A hardware trojan detection method based on structural features of trojan and host circuits", IEEE Access, Vol. 7, (2019), 44632-44644, doi: 10.1109/ACCESS.2019.2908088.
  28. Kurihara, T., Hasegawa, K. and Togawa, N., "Evaluation on hardware-trojan detection at gate-level ip cores utilizing machine learning methods", in 2020 IEEE 26th International Symposium on On-Line Testing and Robust System Design (IOLTS), IEEE., (2020), 1-4, doi: 10.1109/IOLTS50870.2020.9159740.
  29. Bastian, M., Heymann, S. and Jacomy, M., "Gephi: An open source software for exploring and manipulating networks", in Third international AAAI conference on weblogs and social media., (2009) , doi: 10.13140/2.1.1341.1520.
  30. Tarjan, R., "Depth-first search and linear graph algorithms", SIAM Journal on Computing,  Vol. 1, No. 2, (1972), 146-160, doi: 10.1137/0201010.
  31. Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R. and Dubourg, V., "Scikit-learn: Machine learning in python", the Journal of Machine Learning Research, Vol. 12, (2011), 2825-2830, doi: 10.5555/1953048.2078195.
  32. Lundberg, S.M. and Lee, S.-I., "A unified approach to interpreting model predictions", in Proceedings of the 31st international conference on neural information processing systems., (2017), 4768-4777, doi: 10.48550/arXiv.1705.07874.