Відділ теорії цифрових автоматів

Завідувач відділу:

Летичевський Олександр Олександрович

Доктор фізико-математичних наук, старший науковий співробiтник

Відділ засновано 1957 року академіком Віктором Михайловичем Глушковим, який очолював його до 1982 р. У 1982 р. відділ було розділено на два тісно взаємодіючих відділи: відділ теорії цифрових автоматів (завідувач − Капітонова Юлія Володимирівна, доктор фізико-математичних наук, професор, Заслужений діяч науки і техніки України) та відділ рекурсивних обчислювальних машин (завідувач − Летичевський Олександр Адольфович, член-кореспондент Національної академії наук України, доктор фізико-математичних наук, професор). У 2008 році обидва відділи знову було злито в один: відділ теорії цифрових автоматів.

У відділі працюють 19 співробітників, серед них —3 доктори та 10 кандидатів наук.

Відділ теорії цифрових автоматів

ОСНОВНІ НАПРЯМИ НАУКОВОЇ ДІЯЛЬНОСТІ

  • прикладна теорія алгоритмів: автоматно-алгебраїчні моделі обчислювальних систем, теорія проектування обчислювальних систем, алгоритмічні мови високого рівня, паралельні обчислення;
  • алгебраїчна теорія взаємодії агентів та середовищ, інсерційне моделювання та їх застосування;
  • алгебраїчне програмування та комп’ютерна алгебра;
  • теорія та розробка дедуктивних систем штучного інтелекту, інтелектуальні інформаційні технології;
  • технології розробки надійного та ефективного програмного забезпечення;
  • алгебраїчний підхід в методах кібербезпеки, верифікації, тестуванні;
  • моделювання та аналіз кібер-фізичних систем

НАЙВАЖЛИВІШІ РЕЗУЛЬТАТИ

Фундаментальні.

  • створено алгебраїчну теорію взаємодії агентів і середовищ (інсерційне моделювання);
  • розроблено основи теорії алгебри поведінок та її властивостей;
  • розроблено технологію верифікації вимог та специфікацій із застосуванням дедуктивних методів.
  • розроблено математичні основи модельного проектування обчислювальних систем;
  • розроблено основи теорії модельного тестування обчислювальних систем;
  • розроблено алгоритми перевірки несуперечності та повноти вимог до програмних систем;
  • розроблено версію алгоритму очевидності В.М. Глушкова для застосування у верифікаційних системах;
  • розвинуто технологію алгебраїчного програмування для застосування в різних прикладних областях.

Прикладні.

  • розроблено систему інсерційного програмування та моделювання для створення прикладних систем;
  • розроблено систему алгебраїчного програмування, на базі якої створено технологічні засоби верифікації систем;
  • розроблено програмне середовище, що моделює взаємодію людини та комп’ютера, для обчислення параметрів стану користувача та вироблення рекомендацій щодо вдосконалення його робочого місця;
  • розроблено систему верифікації вимог і специфікацій для фірми МОТОРОЛА;
  • створено технологію процесу розробки високонадійних систем та систем, що критичні до безпеки на основі використання символьних та дедуктивних методів.
  • розроблено технологію тестування на основі моделей з використанням символьних методів, а саме пряме та обернене модельне тестування, тестування «білої скриньки», інтеграційне тестування
  • розроблено технологію виявлення вразливих та зловмисних поведінок в програмних системах з використанням алгебраїчного підходу.

Дослідження та застосування

Кібербезпека

Створено технологію виявлення вразливостей в бінарному коді.

Визначено семантику інструкцій для бінарного коду процесора Intel x86 у вигляді специфікацій алгебри поведінок.

Створено алгоритми алгебраїчного співставлення поведінок та символьного моделювання з використанням шаблонів вразливостей.

Створено технологію формалізації шаблонів вразливостей та атак.

Запропоновано гібрідну технологію виявлення атак в мережевому середовищі з використанням алгебраїчного підходу та машинного навчання.

Верифікація та тестування систем апаратного забезпечення.

Технологію верифікації та модельного тестування  було адаптовано для апаратного забезпечення та інтегровано із мовою специфікацій VHDL.

Апробація методів верифікації та тестування проводилось в ході виконання промислових проектів НВП «Радій» м. Кропивницький. Були отримані вагомі результати отримані під час розв’язання наступних задач формальної верифікації. По-перше, виконано алгебраїчний опис обраного фрагмента специфікації вимог для електронних компонент проекту, які реалізовано мовою VHDL. Для фрагменту специфікації вимог виконано аналіз наявності порушень характеристик несуперечливості, повноти та інше, що є особливо важливим для процесів верифікації цифрових пристроїв. Одержано тестові набори для проведення функціональної (поведінкової) симуляції роботи обраного бібліотечного ком1понента. Цей результат дозволяє знизити суб’єктивні ризики виконання поведінкового тестування, тобто знизити ризики якості формулювання вимог розробником та їх розуміння тестувальником, а також якості та кількості тестових наборів, які розроблюються та виконуються з цифровим пристроєм. По-друге, виконано алгебраїчний опис набору сценаріїв логік користувача User Application Logic (UAL), які виконуються програмованим логічним контролером (ПЛК), у процесі чого визначено ймовірні критичні шляхи виконання цих логік.

Верифікація та формалізація кібер-фізичних систем

Розширено алгебру поведінок для формалізації та моделювання систем в яких присутня неперервна компонента. Досліджено деякі моделі та проведено експерименти з верифікації кібер-фізичних систем на прикладі апаратного забезпечення. Дані експерименту стали основою архітектури системи аналізу поведінок компонент апаратного забезпечення з метою виявлення температурних та електромагнітних аномалій, хибного спрацювання у вентильних матрицях та мікроконтролерах.

Координація наукової діяльності

Відділ виступає як провідний у розвитку досліджень з алгебричного програмування та інсерційного моделювання в Україні та у світі, співпрацює з вищими навчальними закладами країни та з установами, що займаються розробкою програмного забезпечення, поширюючи набуті знання, новітні методи та впроваджуючи результати досліджень.

У відділі постійно працює науковий семінар.

Міжнародні зв’язки

Відділ підтримує наукові зв’язки з США (фірма Google, Cadence, Amazon), Великобританією (Лондонський університетський коледж, Лідський університет Бекета, університет Глазго), Ірландією (Університетський Коледж Дублін), Болгарією(Інститут інформації та комунікаційних технологій), Австрією (Інститут символьних обчислень Лінц, Технічний університет Відень), Академією наук Молдови (Інститут математики і інформатики), Китай (компанія Huawei)

Скобелєв В.Г. є членом редколегій двох закордонних журналів:

“International Journal of Trendy Research in Engineering and Technology” (IJTRET), India.

“Computer Science Journal of Moldova” (CSJM), Republic of Moldova.