Original title: Minimalizace testů pro modely na základě podgrafů
Translated title: Subgraph-based test minimization for models
Authors: Mucha, Samuel Ján ; Hudák, David (referee) ; Fiedor, Jan (advisor)
Document type: Bachelor's theses
Year: 2025
Language: eng
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [eng] [cze]
Redundancia testov v modeloch Simulink predstavuje významnú výzvu pre efektívnosť overovania softvéru. Táto práca skúma detekciu izomorfizmu podgrafov pomocou algoritmu VF3, adaptovaného a implementovaného v rámci vlastného reťazca nástrojov BLADE-BALROG-BALIN. BLADE zjednodušuje modelovanie modelov Simulink, BALROG spracováva konverziu grafov pre internú reprezentáciu v NetworkX a BALIN vykonáva VF3. Benchmarking na grafoch podobných Simulinku demonštruje takmer kubickú škálovateľnosť priemernej doby behu a efektívne odmietnutie neizomorfizmu. Počiatočné testy modelu BLADE potvrdili správnosť. Tento výskum zavádza reťazec nástrojov a poskytuje sľubné dôkazy o tom, že VF3 dokáže efektívne znížiť redundanciu v testovaní založenom na modeloch Simulink, čím sa zvyšuje efektívnosť overovania softvéru. Test redundancy in Simulink models poses a significant challenge to software verification efficiency. This thesis investigates subgraph isomorphism detection using the VF3 algorithm, adapted and implemented within a custom BLADE-BALROG-BALIN toolchain. BLADE simplifies Simulink models modeling, BALROG handles graph conversion for internal representation in NetworkX, and BALIN executes VF3. Benchmarking on Simulink-like graphs demonstrates near-cubic average-case runtime scaling and efficient non-isomorphism rejection. Initial BLADE model tests validated correctness. This research establishes a toolchain and provides promising evidence that VF3 can effectively reduce redundancy in Simulink model-based testing, improving efficiency in software verification.
Keywords: Algoritmus VF3; Analýza Modelov; Atribuované orientované grafy; BLADE; NetworkX; Podgrafový Izomorfizmus; Simulink; BLADE; Directed Attributed Graphs; Model Analysis; NetworkX; Simulink; Subgraph Isomorphism; VF3 algorithm

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/253227

Permalink: http://www.nusl.cz/ntk/nusl-683431


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Bachelor's theses