Detail projektu

Efektivní konečné automaty pro automatické usuzování

Období řešení: 1. 1. 2020 - 31. 12. 2024

Typ projektu: grant

Kód: LL1908

Agentura: Ministerstvo školství, mládeže a tělovýchovy České republiky

Program: ERC CZ

Název anglicky
Efficient Finite Automata for Automated Reasoning
Typ
grant
Klíčová slova

konečné automaty, logika, automatizované uvažování, formální verifikace, analýza programu, analýza tvaru, analýza řetězcových programů, bezpečnost

Abstrakt

Cílem projektu je zlepšit efektivitu základních technik konečných automatů. Konečný automat je základní koncepcí informatiky s četnými aplikacemi. Výzkum automatů přináší neustále nové výsledky týkající se široké škály aplikací v automatizovaném rozhodování, formálním ověřování, zpracování jazyka, databázích a webových technologiích. Bohužel jejich praktický dopad, i když je pozoruhodný, je do značné míry omezen nedostatečnou škálovatelností automatických technik zakořeněné ve velmi základních pojmech a algoritmech. Efektivnost automatické technologie však není dostatečně vyřešena. Výzkum se většinou zaměřuje na různá rozšíření automatů a vzrušující "teoretické" aplikace. Důvodem této nedostatečné pozornosti je skutečnost, že se základní automatizační techniky zdají být z obvyklé automatické teoretické perspektivy již dobře pochopené, a proto neposkytují dostatek prostoru pro výzkum. Je zapotřebí vyvinout soustředěné úsilí a přijít s novými myšlenkami v mnohem pragmatickějším směru, abych mohlo dojít k posunutí vývoje. Příležitost v dosažení průlomu v efektivnosti rozhodování vidím ve využití automatů, které vychází z pokroku v automatizovaném rozhodování a ověřování. Koncepty, jako je líné hodnocení, symbolické reprezentace, abstrakce nebo heuristika z řešení SAT / SMT, lze kombinovat s tradičními automatovými technikami a zpracovat novým způsobem. Plánuji detailně prozkoumat základní automatové nástroje společně s těmito koncepty s důrazem na jejich výkonnost v praxi. Jsem přesvědčen, že když výkonnost v praxi získává zaslouženou pozornost, můžeme očekávat podobně rychlý pokrok, jaký byl např. u řešení problému SAT / SMT nebo u ověřování softwaru, což může vést k velmi užitečným a prakticky škálovatelným metodám a nástrojům, stejně jako k novým příležitostem pro hluboké teoretické studium nových technik.

Řešitelé
Holík Lukáš, doc. Mgr., Ph.D. (UITS FIT VUT) , hlavní řešitel
Blahoudek František, RNDr., Ph.D. (UITS FIT VUT)
Češka Milan, doc. RNDr., Ph.D. (UITS FIT VUT)
Fiedor Tomáš, Ing., Ph.D. (UITS FIT VUT)
Havlena Vojtěch, Ing., Ph.D. (UITS FIT VUT)
Homoliak Ivan, Ing., Ph.D. (UITS FIT VUT)
Horký Michal, Ing. (FIT VUT)
Hošták Viliam Samuel, Ing. (FIT VUT)
Hruška Martin, Ing. (UITS FIT VUT)
Jawed Soyiba, Ph.D. (UPSY FIT VUT)
Kesiraju Michaela, Bc. (FIT VUT)
Křivka Zbyněk, Ing., Ph.D. (UIFS FIT VUT)
Lengál Ondřej, Ing., Ph.D. (UITS FIT VUT)
Martiček Štefan, Ing. (UITS FIT VUT)
Meduna Alexander, prof. RNDr., CSc. (UIFS FIT VUT)
Rogalewicz Adam, doc. Mgr., Ph.D. (UITS FIT VUT)
Síč Juraj, Mgr. (UITS FIT VUT)
Slezáková Alexandra, Bc. (FIT VUT)
Šedý Michal, Bc. (FIT VUT)
Šoková Veronika, Ing. (UITS FIT VUT)
Toth Vaňo Pavol, Bc. (FIT VUT)
Turoňová Lenka, Ing. (UITS FIT VUT)
Vojnar Tomáš, prof. Ing., Ph.D. (UITS FIT VUT)
Publikace

2023

  • CHEN Yu-Fang, CHUNG Kai-Min, LENGÁL Ondřej, LIN Jyun-ao, TSAI Wei-lun a YEN Di-de. An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits. Proceedings of the ACM on Programming Languages, 2023. ISSN 2475-1421. Detail
  • CHEN Yu-Fang, CHUNG Kai-Min, LENGÁL Ondřej, LIN Jyun-ao a TSAI Wei-lun. AutoQ: An Automata-based Quantum Circuit Verifier. In: Proceedings of 35th International Conference on Computer Aided Verification. Springer Verlag, 2023. ISSN 0302-9743. Detail
  • HOLÍK Lukáš, SÍČ Juraj, TUROŇOVÁ Lenka a VOJNAR Tomáš. Fast Matching of Regular Patterns with Synchronizing Counting (Technical Report). Ithaca, 2023. Detail
  • HAVLENA Vojtěch, LENGÁL Ondřej, LI Yong, ŠMAHLÍKOVÁ Barbora a TURRINI Andrea. Modular Mix-and-Match Complementation of Büchi Automata. In: Proceedings of TACAS'23. Paris: Springer Verlag, 2023, s. 249-270. ISSN 0302-9743. Detail
  • HAVLENA Vojtěch, LENGÁL Ondřej, LI Yong, ŠMAHLÍKOVÁ Barbora a TURRINI Andrea. Modular Mix-and-Match Complementation of Büchi Automata (Technical Report). Ithaca: Cornell University Library, 2023. Detail
  • BLAHOUDEK František, HAVLENA Vojtěch, HOLÍK Lukáš, CHEN Yu-Fang, CHOCHOLATÝ David, LENGÁL Ondřej a SÍČ Juraj. Word Equations in Synergy with Regular Constraints. In: Proceedings of FM'23. Lübeck: Springer Verlag, 2023, s. 403-423. ISSN 0302-9743. Detail

2022

  • HAVLENA Vojtěch, LENGÁL Ondřej a ŠMAHLÍKOVÁ Barbora. Complementing Büchi Automata with Ranker. In: Proceedings of the 34th International Conference on Computer Aided Verification. Haifa: Springer Verlag, 2022, s. 188-201. ISBN 978-3-031-13187-5. ISSN 0302-9743. Detail
  • HAVLENA Vojtěch, LENGÁL Ondřej a ŠMAHLÍKOVÁ Barbora. Complementing Büchi Automata with Ranker (Technical Report). Ithaca: Cornell University Library, 2022. Detail
  • KLOBUČNÍKOVÁ Dominika, KŘIVKA Zbyněk a MEDUNA Alexander. Conclusive Tree-Controlled Grammars. In: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications . Debrecen: School of Computer Science and Engineering, University of New South Wales, 2022, s. 112-125. ISSN 2075-2180. Detail
  • TUROŇOVÁ Lenka, HOLÍK Lukáš, HOMOLIAK Ivan, LENGÁL Ondřej, VEANES Margus a VOJNAR Tomáš. Counting in Regexes Considered Harmful: Exposing ReDoS Vulnerability of Nonbacktracking Matchers. In: Proceedings of the 31st USENIX Security Symposium. Boston, MA: USENIX, 2022, s. 4165-4182. ISBN 978-1-939133-31-1. Detail
  • HOLÍK Lukáš, PERINGER Petr, ROGALEWICZ Adam, ŠOKOVÁ Veronika, VOJNAR Tomáš a ZULEGER Florian. Low-Level Bi-Abduction. In: 36th European Conference on Object-Oriented Programming (ECOOP 2022). Leibniz International Proceedings in Informatics, roč. 2022. Wadern: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2022, s. 1-30. ISBN 978-3-95977-225-9. ISSN 1868-8969. Detail
  • HOLÍK Lukáš, PERINGER Petr, ROGALEWICZ Adam, ŠOKOVÁ Veronika, VOJNAR Tomáš a ZULEGER Florian. Low-Level Bi-Abduction (Artifact). Dagstuhl, 2022. Detail
  • HOLÍK Lukáš, PERINGER Petr, ROGALEWICZ Adam, ŠOKOVÁ Veronika, VOJNAR Tomáš a ZULEGER Florian. Low-Level Bi-Abduction (technical report). Ithaca, 2022. Detail
  • HAMMER Jan a KŘIVKA Zbyněk. Practical Aspects of Membership Problem of Watson-Crick Context-free Grammars. In: Proceedings 12th International Workshop on Non-Classical Models of Automata and Applications . Debrecen: School of Computer Science and Engineering, University of New South Wales, 2022, s. 88-111. ISSN 2075-2180. Detail
  • GE-ERNST Aile, SCHOLL Christoph, SÍČ Juraj a WIMMER Ralf. Solving dependency quantified Boolean formulas using quantifier localization. Theoretical Computer Science, roč. 2022, č. 925, s. 1-24. ISSN 0304-3975. Detail

2021

  • SÍČ Juraj a STREJČEK Jan. DQBDD: An Efficient BDD-Based DQBF Solver. In: Proc. of the 24th International Conference on Theory and Applications of Satisfiability Testing. Heidelberg: Springer Verlag, 2021, s. 535-544. ISSN 0302-9743. Detail
  • MATOUŠEK Petr, HAVLENA Vojtěch a HOLÍK Lukáš. Efficient Modelling of ICS Communication For Anomaly Detection Using Probabilistic Automata. In: Proceedings of IFIP/IEEE International Symposium on Integrated Network Management. Bordeaux: International Federation for Information Processing, 2021, s. 81-89. ISBN 978-3-903176-32-4. Detail
  • KŘIVKA Zbyněk a MEDUNA Alexander. Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete. Fundamenta Informaticae, roč. 179, č. 4, 2021, s. 361-384. ISSN 0169-2968. Detail
  • ABDULLA Parosh A., ATIG Mohamed F., BUI Phi Diep, HOLÍK Lukáš, CHEN Yu-Fang a WU Zhilin. Solving Not-Substring Constraint with Flat Abstraction. In: Programming Languages and Systems - 19th Asian Symposium, APLAS 2021, Chicago, IL, USA, October 17-18, 2021, Proceedings. 13008. Berlín: Springer International Publishing, 2021, s. 305-320. ISBN 978-3-030-89051-3. Detail

2020

  • HAVLENA Vojtěch, CHEN Yu-Fang, LENGÁL Ondřej a TURRINI Andrea. A Symbolic Algorithm for the Case-Split Rule in String Constraint Solving. In: Proceedings of APLAS'20. Heidelberg: Springer Verlag, 2020, s. 343-363. ISSN 0302-9743. Detail
  • HAVLENA Vojtěch, HOLÍK Lukáš, LENGÁL Ondřej, VALEŠ Ondřej a VOJNAR Tomáš. Antiprenexing for WSkS: A Little Goes a Long Way. In: EPiC Series in Computing. Proceedings of LPAR-23. Manchester: EasyChair, 2020, s. 298-316. ISSN 2398-7340. Detail
  • ABDULLA Parosh A., ATIG Mohamed F., BUI Phi Diep, HOLÍK Lukáš, CHEN Yu-Fang, JANKŮ Petr, LIN Hsin-Hung a WU Wei-Cheng. Efficient handling of string-number conversion. In: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). New York: Association for Computing Machinery, 2020, s. 943-957. ISBN 978-1-4503-7613-6. Detail
  • TUROŇOVÁ Lenka, HOLÍK Lukáš, LENGÁL Ondřej, SAARIKIVI Olli, VEANES Margus a VOJNAR Tomáš. Regex Matching with Counting-Set Automata. Proceedings of the ACM on Programming Languages, roč. 4, č. 11, 2020, s. 1-30. ISSN 2475-1421. Detail
Produkty

2022

  • Broom: Nástroj pro statickou analýzu C programů založen na separační logice a bi-abdukčním přístupu, software, 2022
    Autoři: Holík Lukáš, Peringer Petr, Rogalewicz Adam, Šoková Veronika, Vojnar Tomáš, Zuleger Florian Detail
  • GadgetCA - Nástroj pro generování ReDoS útoků, software, 2022
    Autoři: Holík Lukáš, Homoliak Ivan, Lengál Ondřej, Turoňová Lenka, Veanes Margus, Vojnar Tomáš Detail
  • Ranker: Nástroj pro komplementaci Büchiho automatů, software, 2022
    Autoři: Havlena Vojtěch, Lengál Ondřej, Šmahlíková Barbora Detail
Nahoru