Yurii Olegovich Kostyukov
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Yurii Olegovich Kostyukov has a total of 10 co-authors. Here are the top co-authors by number of shared publications:
- Дмитрий Александрович Мордвинов
St. Petersburg State University, St. Petersburg, Russia
6 shared publications - Aleksandr Vladimirovich Misonizhnik
Huawei
3 shared publications - A. I. Vasenina
St. Petersburg State University, St. Petersburg, Russia
2 shared publications - Alexey Alexandrovich Babushkin
Huawei
2 shared publications - Dmitry Vladimirovich Koznov
St. Petersburg State University
2 shared publications - Sergey Antonovich Morozov
Национальный исследовательский университет “Высшая школа экономики
2 shared publications
Latest Publications
- 15 July 2025
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 51 (4) , 242-256
Automatic Inference of Synchronous Regular Invariants
Algebraic data types make it possible to represent complex data structures; therefore, the classical verification methods relying on inductive invariant inference are not applicable to programs with such types. The main difficulty in the classical methods is the weakness of the first-order logic language used to represent inductive invariants. In this paper, synchronous tree automata are considered as an alternative to the classical representations of invariants using first-order logic. A method for automatic inductive invariant inference represented by synchronous tree automata is proposed. This method uses finite-model findings. The implementation of the proposed method finds 65% more invariants than a first-order logic based tool, and it is a multiple winner of international verifier competition using inductive invariant inference.
- 15 July 2025
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 51 (4) , 242-256
Automatic Inference of Synchronous Regular Invariants
Algebraic data types make it possible to represent complex data structures; therefore, the classical verification methods relying on inductive invariant inference are not applicable to programs with such types. The main difficulty in the classical methods is the weakness of the first-order logic language used to represent inductive invariants. In this paper, synchronous tree automata are considered as an alternative to the classical representations of invariants using first-order logic. A method for automatic inductive invariant inference represented by synchronous tree automata is proposed. This method uses finite-model findings. The implementation of the proposed method finds 65% more invariants than a first-order logic based tool, and it is a multiple winner of international verifier competition using inductive invariant inference.
- 1 January 2025
- Published by Akademizdatcenter Nauka in Программирование / Programming and Computer Software
- No. 4,p. 33
AUTOMATIC INFERENCE OF SYNCHRONOUS REGULAR INVARIANTS
Algebraic data types allow representing complex data structures, thus classical verification methods relying on inductive invariant inference are not applicable to programs with such types. The main problem with classical methods is the weakness of the first-order logic language used to represent inductive invariants. In this paper, synchronous automata over trees are considered as an alternative to classical representations of invariants using first-order logic. A method for automatic inductive invariant inference represented by synchronous automata over trees is proposed. The method uses finite-model finding. The implementation of the proposed method finds 65% more invariants than a first-order logic based tool, which is an annual winner of an international verifier competition, on an existing benchmark.
- 1 January 2025
- Published by Akademizdatcenter Nauka in Программирование / Programming and Computer Software
- No. 4,p. 33
AUTOMATIC INFERENCE OF SYNCHRONOUS REGULAR INVARIANTS
Algebraic data types allow representing complex data structures, thus classical verification methods relying on inductive invariant inference are not applicable to programs with such types. The main problem with classical methods is the weakness of the first-order logic language used to represent inductive invariants. In this paper, synchronous automata over trees are considered as an alternative to classical representations of invariants using first-order logic. A method for automatic inductive invariant inference represented by synchronous automata over trees is proposed. The method uses finite-model finding. The implementation of the proposed method finds 65% more invariants than a first-order logic based tool, which is an annual winner of an international verifier competition, on an existing benchmark.
- Open Access
- 6 April 2024
- Published by Springer Nature
- p. 314-319
KLEEF: Symbolic Execution Engine (Competition Contribution)
KLEEF is a complete overhaul of the KLEE symbolic execution engine for LLVM, fine-tuned for a robust analysis of industrial C/C++ code. KLEEF natively handles complex data structures, such as trees, linked lists, and dynamically allocated arrays, via lazy initialization and symcrete values. KLEEF has fine-tuned modes for both maximal test coverage generation and reproducing error traces, in particular reaching a specific point in the program. In the paper, we describe the above features and a competition configuration of KLEEF.
- 6 April 2024
- Published by Springer Nature
- p. 314-319
Open AccessKLEEF: Symbolic Execution Engine (Competition Contribution)
KLEEF is a complete overhaul of the KLEE symbolic execution engine for LLVM, fine-tuned for a robust analysis of industrial C/C++ code. KLEEF natively handles complex data structures, such as trees, linked lists, and dynamically allocated arrays, via lazy initialization and symcrete values. KLEEF has fine-tuned modes for both maximal test coverage generation and reproducing error traces, in particular reaching a specific point in the program. In the paper, we describe the above features and a competition configuration of KLEEF.
- Open Access
- 1 October 2022
- Published by ITMO University in Scientific and Technical Journal of Information Technologies, Mechanics and Optics
- Vol. 22 (5) , 982
Generation of the weakest preconditions of programs with dynamic memory in symbolic execution
Symbolic execution is a widely used method for the systematic study of program execution paths; it allows solving a number of important problems related to verification of correctness: searching for errors and vulnerabilities, automatic test generation, etc. The main idea of symbolic execution is generation and use of symbolic expressions in the program analysis in direct order, i.e., from the entry point to the points of interest. At the same time, since the time of E.W. Dijkstra, the method of backward symbolic execution has been popular when the conditions for hitting the point of interest are extended to the entry point of the program due to the iterative calculation of the weakest preconditions. This method is usually much more difficult to implement than direct symbolic execution, so even the artifacts of the latter cannot be used in the implementation. In this paper, the relationship between direct and backward symbolic execution based on the calculation of the weakest preconditions is investigated. In particular, it is shown that the latter can be implemented using the former. A formal presentation of symbolic execution with lazy initialization for programs with dynamic memory is given. An algorithm for calculating the weakest preconditions for arbitrary symbolic executed program branches is proposed. The lazy initialization mechanism and the algorithm for calculating the weakest preconditions are implemented in KLEE, a symbolic virtual machine for the well-known LLVM platform. The proposed method allows performing backward symbolic analysis using direct symbolic execution. This is important for the implementation of bidirectional program execution which can be used both for program verification and for automatic test generation.
- 1 October 2022
- Published by ITMO University in Scientific and Technical Journal of Information Technologies, Mechanics and Optics
- Vol. 22 (5) , 982
Open AccessGeneration of the weakest preconditions of programs with dynamic memory in symbolic execution
Symbolic execution is a widely used method for the systematic study of program execution paths; it allows solving a number of important problems related to verification of correctness: searching for errors and vulnerabilities, automatic test generation, etc. The main idea of symbolic execution is generation and use of symbolic expressions in the program analysis in direct order, i.e., from the entry point to the points of interest. At the same time, since the time of E.W. Dijkstra, the method of backward symbolic execution has been popular when the conditions for hitting the point of interest are extended to the entry point of the program due to the iterative calculation of the weakest preconditions. This method is usually much more difficult to implement than direct symbolic execution, so even the artifacts of the latter cannot be used in the implementation. In this paper, the relationship between direct and backward symbolic execution based on the calculation of the weakest preconditions is investigated. In particular, it is shown that the latter can be implemented using the former. A formal presentation of symbolic execution with lazy initialization for programs with dynamic memory is given. An algorithm for calculating the weakest preconditions for arbitrary symbolic executed program branches is proposed. The lazy initialization mechanism and the algorithm for calculating the weakest preconditions are implemented in KLEE, a symbolic virtual machine for the well-known LLVM platform. The proposed method allows performing backward symbolic analysis using direct symbolic execution. This is important for the implementation of bidirectional program execution which can be used both for program verification and for automatic test generation.
- Open Access
- 1 January 2022
- Published by Institute for System Programming of the Russian Academy of Sciences in Proceedings of the Institute for System Programming of the RAS
- Vol. 34 (4) , 49-62
Automated testing of LLVM programs with complex input data structures
Символьное исполнение является известным подходом для автоматической генерации регрессионных тестов и поиска ошибок/уязвимостей в программах. Данная работа посвящена созданию практичного метода к символьному исполнению LLVM-программ, пригодного для работы со сложными входными структурами данных. Метод основан на известной идее ленивой инициализации, позволяющей избавить пользователя от необходимости вручную создавать ограничения на входные структуры данных и полностью автоматизировать процесс символьного исполнения программы. Предлагается два улучшения ленивой инициализации для сегментированной символьной моделей памяти – использование временных меток и информации о типах. Предложенный метод реализован в символьной виртуальной машине KLEE для платформы LLVM и протестирован на реальных C-структурах данных — списках, биномиальных кучах, AVL-деревьях, красно-чёрных деревьях, двоичных деревьях и борах (префиксных деревьях).
- 1 January 2022
- Published by Institute for System Programming of the Russian Academy of Sciences in Proceedings of the Institute for System Programming of the RAS
- Vol. 34 (4) , 49-62
Open AccessAutomated testing of LLVM programs with complex input data structures
Символьное исполнение является известным подходом для автоматической генерации регрессионных тестов и поиска ошибок/уязвимостей в программах. Данная работа посвящена созданию практичного метода к символьному исполнению LLVM-программ, пригодного для работы со сложными входными структурами данных. Метод основан на известной идее ленивой инициализации, позволяющей избавить пользователя от необходимости вручную создавать ограничения на входные структуры данных и полностью автоматизировать процесс символьного исполнения программы. Предлагается два улучшения ленивой инициализации для сегментированной символьной моделей памяти – использование временных меток и информации о типах. Предложенный метод реализован в символьной виртуальной машине KLEE для платформы LLVM и протестирован на реальных C-структурах данных — списках, биномиальных кучах, AVL-деревьях, красно-чёрных деревьях, двоичных деревьях и борах (префиксных деревьях).
- Open Access
- 18 June 2021
- Published by Association for Computing Machinery (ACM)
- p. 451-465
Beyond the elementary representations of program invariants over algebraic data types
First-order logic is a natural way of expressing properties of computation. It is traditionally used in various program logics for expressing the correctness properties and certificates. Although such representations are expressive for some theories, they fail to express many interesting properties of algebraic data types (ADTs). In this paper, we explore three different approaches to represent program invariants of ADT-manipulating programs: tree automata, and first-order formulas with or without size constraints. We compare the expressive power of these representations and prove the negative definability of both first-order representations using the pumping lemmas. We present an approach to automatically infer program invariants of ADT-manipulating programs by a reduction to a finite model finder. The implementation called RInGen has been evaluated against state-of-the-art invariant synthesizers and has been experimentally shown to be competitive. In particular, program invariants represented by automata are capable of expressing more complex properties of computation and their automatic construction is often less expensive.
- 18 June 2021
- Published by Association for Computing Machinery (ACM)
- p. 451-465
Open AccessBeyond the elementary representations of program invariants over algebraic data types
First-order logic is a natural way of expressing properties of computation. It is traditionally used in various program logics for expressing the correctness properties and certificates. Although such representations are expressive for some theories, they fail to express many interesting properties of algebraic data types (ADTs). In this paper, we explore three different approaches to represent program invariants of ADT-manipulating programs: tree automata, and first-order formulas with or without size constraints. We compare the expressive power of these representations and prove the negative definability of both first-order representations using the pumping lemmas. We present an approach to automatically infer program invariants of ADT-manipulating programs by a reduction to a finite model finder. The implementation called RInGen has been evaluated against state-of-the-art invariant synthesizers and has been experimentally shown to be competitive. In particular, program invariants represented by automata are capable of expressing more complex properties of computation and their automatic construction is often less expensive.