informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2022-19-3-25-39inform-1205Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNКанонизация графов при декомпиляции транзисторных схемCanonization of graphs during transistor circuits decompilationЧеремисиновД. И.CheremisinovD. I.

Черемисинов Дмитрий Иванович, кандидат технических наук, доцент, ведущий научный сотрудник 

ул. Сурганова, 6, Минск, 220012

Dmitry I. Cheremisinov, Ph. D. (Eng.), Associate Professor, Leading Researcher 

st. Surganova, 6, Minsk, 220012

cher@newman.bas-net.byЧеремисиноваЛ. Д.CheremisinovaL. D.

Черемисинова Людмила Дмитриевна, доктор технических наук, профессор, главный научный сотрудник 

ул. Сурганова, 6, Минск, 220012

Ljudmila D. Cheremisinova, D. Sc. (Eng.), Professor, Chief Researcher 

st. Surganova, 6, Minsk, 220012

cld@newman.bas-net.byОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus2022280620221932539Copyright © Черемисинов Д.И., Черемисинова Л.Д., 20222022Черемисинов Д.И., Черемисинова Л.Д.Cheremisinov D.I., Cheremisinova L.D.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/1205

Цели. Разрабатываются средства распознавания (экстракции) высокоуровневой структуры в транзисторной схеме, которые позволяют получить представление на уровне логических элементов, эквивалентное исходному плоскому описанию на транзисторном уровне. Получение такого представления существенно снижает время выполнения проверки топологии и служит основой для перепроектирования интегральных схем и обратного инжиниринга для обнаружения несанкционированных вложений.Методы. Предлагаются графовые методы и программные средства распознавания топологически эквивалентных транзисторных схем, позволяющие разбить множество подсхем на классы. Задача сводится к проверке изоморфизма помеченных графов, задающих схемы на транзисторном уровне, путем их канонизации и сравнения канонических маркировок. Исходная плоская и полученная двухуровневая транзисторные схемы представляются в формате SPICE.Результаты. Предложенные методы реализованы на языке C++ как часть программы декомпиляции транзисторных схем для случая, когда искомая библиотека логических элементов заранее неизвестна. Предложенный метод канонизации помеченных графов используется при распознавании топологически эквивалентных подсхем среди функционально эквивалентных подсхем, реализующих логические элементы; разбиении множества подсхем, не распознанных как логические элементы, на классы топологически эквивалентных; верификации результатов экстракции иерархической схемы на транзисторнологическом уровне относительно плоской схемы на транзисторном уровне.Заключение. Программа декомпиляции была протестирована на практических схемах транзисторного уровня. Показано, что она имеет достаточное быстродействие, чтобы обрабатывать схемы более чем со 100 тыс. транзисторов за несколько минут на ПЭВМ.

Objectives. The objective of the work is to develop the means for recognition (extraction) of high-level structures in circuits on transistor level. This allows to obtain a representation on logical level, equivalent to original flat description on transistor level. Obtaining such a representation significantly reduces the time to perform VLSI topology check, but also provides the basis for reengineering of integrated circuits and reverse engineering for detecting unauthorized attachments.Methods. Graph based methods and software tools are proposed for recognizing topologically equivalent transistor circuits, which makes it possible to divide the set of subcircuits into topologically equivalent classes. The problem is reduced to checking the isomorphism of labeled graphs defining circuits on transistor level by canonizing them and comparing canonical labeling. The original flat and resulting two-level transistor circuits are presented in SPICE format.Results. The proposed methods are implemented in C++ as a part of a transistor circuit decompilation program for the case without predetermined cell library. The proposed method of canonization of labeled graphs is used: to recognize topologically equivalent subcircuits among functionally equivalent subcircuits that implement logical elements; to split the set of subcircuits not recognized as logical elements into classes of topologically equivalent ones; to verify the results of extraction of the hierarchical circuit at the transistor-logic level relative to the flat circuit at the transistor level.Conclusion. The decompilation program has been tested on practical transistor-level circuits. Experiments indicate that this tool is fast enough to process the circuits with more than one hundred thousand transistors in a few minutes on a personal computer.

экстракция транзисторных подсхемКМОП-схемыверификацияраспознавание логических вентилейизоморфизм графовформат SPICEtransistor subcircuit extractionCMOS circuitsVLSI layout verificationlogical gates recognitiongraph isomorphismSPICE formatReferencesBaker, R. J. CMOS Circuit Design, Layout, and Simulation / R. J. Baker. – Third ed. – Wiley-IEEE Press, 2010. – 1214 p.Baker R. J. CMOS Circuit Design, Layout, and Simulation. Third ed. Wiley-IEEE Press, 2010, 1214 p.Zhang, N. The subcircuit extraction problem / N. Zhang, D. C. Wunsch, F. Harary // Proc. IEEE Intern. Behavioral Modeling and Simulation Workshop. – 2005. – Vol. 33(3). – P. 22–25.Zhang N., Wunsch D. C., Harary F. The subcircuit extraction problem. Proceedings IEEE International Behavioral Modeling and Simulation Workshop, 2005, vol. 33(3), рр. 22–25.Yang, L. FROSTY: A program for fast extraction of high-level structural representation from circuit description for industrial CMOS circuits / L. Yang, C.-J. R. Shi // Integration the VLSI J. – 2006. – Vol. 39, no 4. – P. 311–339.Yang L., Shi C.-J. R. FROSTY: A program for fast extraction of high-level structural representation from circuit description for industrial CMOS circuits. Integration the VLSI Journal, 2006, vol. 39, no 4, рр. 311–339.Черемисинов, Д. И. Извлечение сети логических элементов из КМОП-схемы транзисторного уровня / Д. И. Черемисинов, Л. Д. Черемисинова // Микроэлектроника. – 2019. – Т. 48, № 3. – С. 224–234. https://doi.org/10.1134/S0544126919030037Cheremisinov D. I., Cheremisinova L. D. Extracting a logic gate network from a transistor-level CMOS circuit. Mikrojelektronika [Russian Microelectronics], 2019, vol. 48, no. 3, рр. 224–234. https://doi.org/10.1134/S0544126919030037 (In Russ.).Abadir, M. S. An improved layout verification algorithm (LAVA) / M. S. Abadir, J. Ferguson // Proc. of the European Design Automation Conf., Glasgow, UK, 12–15 Mar. 1990. – Glasgow, 1990. – P. 391–395.Abadir M. S., Ferguson J. An improved layout verification algorithm (LAVA). Proceedings of the European Design Automation Conference, Glasgow, UK, 12–15 March 1990. Glasgow, 1990, рр. 391–395.Framework for simulation of the Verilog/SPICE mixed model: Interoperation of Verilog and SPICE simulators using HLA/RTI for model reusability / M. G. Seok [et al.] // 22nd Intern. Conf. on Very Large Scale Integration (VLSI-SoC), Playa del Garmen, Mexico, 6–8 Oct. 2014. – Playa del Garmen, 2014. – P. 1–6.Seok M. G., Park D. J., Cho G. R., Kim T. G. Framework for simulation of the Verilog/SPICE mixed model: Interoperation of Verilog and SPICE simulators using HLA/RTI for model reusability. 22nd International Conference on Very Large Scale Integration (VLSI-SoC), Playa del Garmen, Mexico, 6–8 October 2014. Playa del Garmen, 2014, рр. 1–6.Kundu, S. GateMaker: A transistor to gate level model extractor for simulation, automatic test pattern generation and verification / S. Kundu // Proc. of the Intern. Test Conf., Washington, DC, USA, 18–23 Oct. 1998. – Washington, 1998. – P. 372–381.Kundu S. GateMaker: A transistor to gate level model extractor for simulation, automatic test pattern generation and verification. Proceedings of the International Test Conference, Washington, DC, USA, 18–23 October 1998. Washington, 1998, рр. 372–381.Hunt, V. D. Reengineering: Leveraging the Power of Integrated Product Development / V. D. Hunt. – Wiley, 1993. – 283 p.Hunt V. D. Reengineering: Leveraging the Power of Integrated Product Development. Wiley, 1993, 283 p.Rostami, M. A primer on hardware security: Models, methods, and metrics / M. Rostami, F. Koushanfar, R. Karri // Proceedings of the IEEE. – 2014. – Vol. 102, no. 8. – P. 1283–1295.Rostami M., Koushanfar F., Karri R. A primer on hardware security: Models, methods, and metrics. Proceedings of the IEEE, 2014, vol. 102, no. 8, pp. 1283–1295.Tehranipoor, M. A survey of hardware trojan taxonomy and detection / M. Tehranipoor, F. Koushanfar // IEEE Design & Test of Computers. – 2010. – Vol. 27, no. 1. – P. 10–25.Tehranipoor M., Koushanfar F. A survey of hardware trojan taxonomy and detection. IEEE Design & Test of Computers, 2010, vol. 27, no. 1, pp. 10–25.Белоус, А. И. Основы кибербезопасности. Стандарты, концепции, методы и средства обеспечения / А. И. Белоус, В. А. Солодуха. – М. : Техносфера, 2021. – 482 с.Belous A. I., Solodukha V. A. Osnovy kiberbezopasnosti. Standarty, kontseptsii, metody i sredstva obespecheniya. Fundamentals of Cybersecurity. Standards, Concepts, Methods and Means of Support. Moscow, Tekhnosfera, 2021, 482 p. (In Russ.).Черемисинов, Д. И. Распознавание логических вентилей в плоской транзисторной схеме / Д. И. Черемисинов, Л. Д. Черемисинова // Информатика. – 2021. – Т. 18, № 4. – С. 96–107. https://doi.org/10.37661/1816-0301-2021-18-4-96-107Cheremisinov D. I., Cheremisinova L. D. Logical gates recognition in a flat transistor circuit. Informatika [Informatics], 2021, vol. 18, no. 4, pp. 96−107. https://doi.org/10.37661/1816-0301-2021-18-4-96-107 (In Russ.).Hartke, S. G. McKay's Canonical Graph Labeling Algorithm / S. G. Hartke, A. J. Radcliffe // Communicating Mathematics. – 2009. – Vol. 479. – P. 99–111.Hartke S. G., Radcliffe A. J. McKay's Canonical Graph Labeling Algorithm. Communicating Mathematics, 2009, vol. 479, pp. 99–111.Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 589 c.Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskiye osnovy proyektirovaniya diskretnykh ustroystv. Logical Basis for Designing Discrete Devices. Moscow, Fizmatlit, 2007, 589 p. (In Russ.).Garey, M. R. Computers and Intractability: A Guide to the Theory of NP-Completeness / M. R. Garey, D. S. Johnson. – N. Y. : W. H. Freeman and Company, 1979. – 340 р.Garey M. R., Johnson D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, W. H. Freeman and Company, 1979, 340 р.McKay, B. D. Practical graph isomorphism / B. D. McKay // Congressus Numerantium. – 1981. – Vol. 30. – P. 45–87.McKay B. D. Practical graph isomorphism. Congressus Numerantium, 1981, vol. 30, pp. 45–87.Junttila, T. Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs / T. Junttila, P. Kaski // Proc. Meeting on Algorithm Engineering & Expermiments SIAM, New Orleans, LA, 6 Jan. 2007. – New Orleans, 2007. – P. 135–149.Junttila T., Kaski P. Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs. Proceedings Meeting on Algorithm Engineering & Expermiments SIAM, New Orleans, LA, 6 January 2007. New Orleans, 2007, pp. 135–149.Черемисинов, Д. И. Верификация логических схем из КМОП-транзисторов / Д. И. Черемисинов, Л. Д. Черемисинова // Новые информационные технологии в исследовании сложных структур : материалы 13-й Междунар. конф., 7–9 сент. 2020 г. – Томск : Изд. дом Томского гос. ун-та, 2020. – С. 150–151.Cheremisinov D. I., Cheremisinova L. D. Verification of logic circuits from CMOS transistors. Novyye informatsionnyye tekhnologii v issledovanii slozhnykh struktur : materialy 13-j Mezhdunarodnoj konferencii, 7–9 sentyabrya 2020 g. [New Information Technologies in the Study of Complex Structures: Proceedings of the 13th International Conference, 7–9 September 2020]. Tomsk, Izdatel'skij dom Tomskogo gosudarstvennogo universiteta, 2020, pp. 150–151 (In Russ.).

The authors declare that there are no conflicts of interest present.