Aktualności Instytutu Podstaw Informatyki PAN

31 stycznia b.r. w czasopiśmie IEEE Transactions on Reliability został opublikowany artykuł pracowników IPI PAN: prof. Wojciecha Penczka, dr Łukasza Maśko i mgr Teofila Sidoruka, napisany we współpracy z prof. Laure Petrucci, dr Carlosem Olarte i dr Jaime Ariasem z Université Sorbonne Paris Nord. Praca "Optimal Scheduling of Agents in ADTrees: Specialized Algorithm and Declarative Models" stanowi kontynuację wcześniejszej linii badań [1], w której zaproponowano reprezentowanie drzew ataku/obrony (ADTrees) jako systemów wieloagentowych. ADTrees są popularnym formalizmem, pozwalającym na analizowanie scenariuszy bezpieczeństwa, w których dwie grupy agentów próbują albo wykonać podzadania (poszczególne węzły drzewa) składające się na główny cel (korzeń drzewa), albo dążą do uniemożliwienia tego przeciwnej grupie. Dzięki translacji do formalizmu wieloagentowego, możliwe staje się rozważanie tych dwóch grup jako koalicji, charakteryzujących się nie tylko pewną liczbą agentów, ale również konkretnym ich przydziałem do poszczególnych podzadań. To z kolei determinuje zarówno możliwość skutecznego ataku lub obrony przeciwko drugiej koalicji, ale także wpływa na rozważane cechy kwantytatywne, np. czas ataku/obrony lub związany z nimi koszt finansowy.

Istotne staje się wobec tego zminimalizowanie liczby potrzebnych agentów przy zachowaniu optymalnego planu ich działań. W pracy zostały przedstawione i przeanalizowane dwa odrębne podejścia do rozwiązania tego problemu. Po pierwsze, zaproponowano wyspecjalizowany algorytm, działający w czasie kwadratowym, minimalizujący dla danego ADTree liczbę potrzebnych agentów i optymalnie przydzielający je do poszczególnych podzadań. Po drugie, pokazano ogólne, deklaratywne podejście oparte na logice przepisywania (ang. rewriting logic) i zbiorze reguł dokładnie specyfikującym wymagania, jakie musi spełniać potencjalne rozwiązanie, aby było poprawne i optymalne. Ten sposób, chociaż mniej efektywny niż wyspecjalizowany algorytm, ma wiele zalet: przed wszystkim jest znacznie bardziej ogólny i dzięki temu łatwo może zostać dopasowany do potrzeb np. rozszerzeń ADTrees lub innych pokrewnych formalizmów.

Bezpieczeństwo systemów komputerowych stanowi kluczowe zagadnienie, a uzyskane wyniki z jednej strony otwierają nowe możliwości analizy scenariuszy ataku/obrony w tym kontekście, natomiast z drugiej wpisują się również w istotny aspekt z perspektywy systemów wieloagentowych, jakim jest ograniczenie problemu eksplozji przestrzeni stanów poprzez minimalizację liczby agentów w systemie. Ponadto, autorzy proponują kilka kierunków dalszych badań, w tym m.in. użycie czasowych wariantów logik temporalno-strategicznych TATL lub niedawno zaproponowanego STCTL [2], co pozwoliłoby na specyfikację znacznie bardziej złożonych celów w rozważanych scenariuszach bezpieczeństwa. Warto podkreślić, że doskonale łączy się to z najważniejszymi zadaniami trwającej współpracy naukowej z zespołem prof. Petrucci na Université Sorbonne Paris Nord (współfinansowanej przez PAN w ramach projektów IEA), w szczególności z połączeniem aspektów zdolności strategicznej i czasu w kontekście weryfikacji modelowej i testowania spełnialności w asynchronicznych systemach wieloagentowych.

Artykuł jest rozszerzoną wersją pracy przedstawionej na konferencji ICECCS 2022 [3], wzbogaconą o nowe, deklaratywne podejście do rozważanego problemu i jego eksperymentalne porównanie z dotychczasowym, wyspecjalizowanym algorytmem. Manuskrypt jest również dostępny w repozytorium arXiv [4]; wersja ta różni się od końcowej publikacji wyłącznie kilkoma drobnymi poprawkami natury edytorskiej.

1. J. Arias, C. E. Budde, L. Petrucci, W. Penczek, T. Sidoruk, M. Stoelinga: Hackers vs. Security: Attack-Defence Trees as Asynchronous Multi-agent Systems. Proceedings of the 22nd International Conference on Formal Engineering Methods (ICFEM 2020), Singapore, March 1–3, 2021, pp. 3-19
2. J. Arias, W. Jamroga, L. Petrucci, W. Penczek, T. Sidoruk: Strategic (Timed) Computation Tree Logic. Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023), London, United Kingdom, May 29-June 2, 2023, pp. 382-390
3. J. Arias, Ł. Maśko, L. Petrucci, W. Penczek, T. Sidoruk: Minimal Schedule with Minimal Number of Agents in Attack-Defence Trees. Proceedings of the 26th International Conference on Engineering of Complex Computer Systems (ICECCS 2022), Hiroshima, Japan, March 26-30, 2022, pages 1-10
4. https://arxiv.org/abs/2305.04616