Preview

Информатика

Расширенный поиск

Канонизация графов при декомпиляции транзисторных схем

https://doi.org/10.37661/1816-0301-2022-19-3-25-39

Аннотация

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

Об авторах

Д. И. Черемисинов
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь

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

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



Л. Д. Черемисинова
Объединенный институт проблем информатики Национальной академии наук Беларуси
Беларусь

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

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



Список литературы

1. Baker, R. J. CMOS Circuit Design, Layout, and Simulation / R. J. Baker. – Third ed. – Wiley-IEEE Press, 2010. – 1214 p.

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

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

4. Черемисинов, Д. И. Извлечение сети логических элементов из КМОП-схемы транзисторного уровня / Д. И. Черемисинов, Л. Д. Черемисинова // Микроэлектроника. – 2019. – Т. 48, № 3. – С. 224–234. https://doi.org/10.1134/S0544126919030037

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

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

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

8. Hunt, V. D. Reengineering: Leveraging the Power of Integrated Product Development / V. D. Hunt. – Wiley, 1993. – 283 p.

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

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

11. Белоус, А. И. Основы кибербезопасности. Стандарты, концепции, методы и средства обеспечения / А. И. Белоус, В. А. Солодуха. – М. : Техносфера, 2021. – 482 с.

12. Черемисинов, Д. И. Распознавание логических вентилей в плоской транзисторной схеме / Д. И. Черемисинов, Л. Д. Черемисинова // Информатика. – 2021. – Т. 18, № 4. – С. 96–107. https://doi.org/10.37661/1816-0301-2021-18-4-96-107

13. Hartke, S. G. McKay's Canonical Graph Labeling Algorithm / S. G. Hartke, A. J. Radcliffe // Communicating Mathematics. – 2009. – Vol. 479. – P. 99–111.

14. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. – М. : Физматлит, 2007. – 589 c.

15. 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 р.

16. McKay, B. D. Practical graph isomorphism / B. D. McKay // Congressus Numerantium. – 1981. – Vol. 30. – P. 45–87.

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

18. Черемисинов, Д. И. Верификация логических схем из КМОП-транзисторов / Д. И. Черемисинов, Л. Д. Черемисинова // Новые информационные технологии в исследовании сложных структур : материалы 13-й Междунар. конф., 7–9 сент. 2020 г. – Томск : Изд. дом Томского гос. ун-та, 2020. – С. 150–151.


Рецензия

Для цитирования:


Черемисинов Д.И., Черемисинова Л.Д. Канонизация графов при декомпиляции транзисторных схем. Информатика. 2022;19(3):25-39. https://doi.org/10.37661/1816-0301-2022-19-3-25-39

For citation:


Cheremisinov D.I., Cheremisinova L.D. Canonization of graphs during transistor circuits decompilation. Informatics. 2022;19(3):25-39. (In Russ.) https://doi.org/10.37661/1816-0301-2022-19-3-25-39

Просмотров: 264


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1816-0301 (Print)
ISSN 2617-6963 (Online)