Дмитрий Александрович Мордвинов
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Дмитрий Александрович Мордвинов has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
- Yurii Olegovich Kostyukov
St. Petersburg State University, St. Petersburg, Russia
6 shared publications - Aleksandr Vladimirovich Misonizhnik
Huawei
4 shared publications - Dmitry Ivanov
HUAWEI, Shenzhen, China
3 shared publications - Dmitry Vladimirovich Koznov
St. Petersburg State University
3 shared publications - Sergey Antonovich Morozov
Национальный исследовательский университет “Высшая школа экономики
3 shared publications - A. I. Vasenina
St. Petersburg State University, St. Petersburg, Russia
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
- 14 April 2024
- Published by Association for Computing Machinery (ACM)
- p. 41-42
UTBot Python at the SBFT Tool Competition 2024
UTBot is a tool for automated unit test generation, that generates ready-to-use Python test cases. It uses two approaches for finding input values: fuzzing and dynamic symbolic execution, which run in parallel. In this paper, we report the UTBot results at the SBFT 2024 Python tool competition.
- 14 April 2024
- Published by Association for Computing Machinery (ACM)
- p. 41-42
Open AccessUTBot Python at the SBFT Tool Competition 2024
UTBot is a tool for automated unit test generation, that generates ready-to-use Python test cases. It uses two approaches for finding input values: fuzzing and dynamic symbolic execution, which run in parallel. In this paper, we report the UTBot results at the SBFT 2024 Python tool competition.
- 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 January 2023
- Published by Institute for System Programming of the Russian Academy of Sciences in Proceedings of the Institute for System Programming of the RAS
- Vol. 35 (3) , 91-108
“Symcrete” memory Model with Lazy Initialization and Objects of Symbolic Sizes in KLEE
Dynamic symbolic execution is a well-known technique for testing applications. It introduces symbolic variables – program data with no concrete value at the moment of instantiation – and uses them to systematically explore the execution paths in a program under analysis. However, not every value can be easily modelled as symbolic: for instance, some values may take values from restricted domains or have complex invariants, hard enough to model using existing logic theories, despite it is not a problem for concrete computations. In this paper, we propose an implementation of infrastructure for dealing with such “hard-to-be-modelled” values. We take the approach known as symcrete execution and implement its robust and scalable version in the well-known KLEE symbolic execution engine. We use this infrastructure to support the symbolic execution of LLVM programs with complex input data structures and input buffers with indeterminate sizes.
- 1 January 2023
- Published by Institute for System Programming of the Russian Academy of Sciences in Proceedings of the Institute for System Programming of the RAS
- Vol. 35 (3) , 91-108
Open Access“Symcrete” memory Model with Lazy Initialization and Objects of Symbolic Sizes in KLEE
Dynamic symbolic execution is a well-known technique for testing applications. It introduces symbolic variables – program data with no concrete value at the moment of instantiation – and uses them to systematically explore the execution paths in a program under analysis. However, not every value can be easily modelled as symbolic: for instance, some values may take values from restricted domains or have complex invariants, hard enough to model using existing logic theories, despite it is not a problem for concrete computations. In this paper, we propose an implementation of infrastructure for dealing with such “hard-to-be-modelled” values. We take the approach known as symcrete execution and implement its robust and scalable version in the well-known KLEE symbolic execution engine. We use this infrastructure to support the symbolic execution of LLVM programs with complex input data structures and input buffers with indeterminate sizes.
- 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.
- Open Access
- 27 December 2019
- Published by P.G. Demidov Yaroslavl State University in Modeling and Analysis of Information Systems
- Vol. 26 (4) , 550-571
Property-Directed Inference of Relational Invariants
Property Directed Reachability (PDR) is an efficient and scalable approach to solving systems of symbolic constraints also known as Constrained Horn Clauses (CHC). In the case of non-linear CHCs, which may arise, e.g., from relational verification tasks, PDR aims to infer an inductive invariant for each uninterpreted predicate. However, in many practical cases this reasoning is not successful, as invariants should be derived for groups of predicates instead of individual predicates. The article describes a novel algorithm that identifies these groups automatically and complements the existing PDR technique. The key feature of the algorithm is that it does not require a possibly expensive synchronization transformation over the system of CHCs. We have implemented the algorithm on top of a up-to-date CHC solver Spacer. Our experimental evaluation shows that for some CHC systems, on which existing solvers diverge, our tool is able to discover relational invariants.
- 27 December 2019
- Published by P.G. Demidov Yaroslavl State University in Modeling and Analysis of Information Systems
- Vol. 26 (4) , 550-571
Open AccessProperty-Directed Inference of Relational Invariants
Property Directed Reachability (PDR) is an efficient and scalable approach to solving systems of symbolic constraints also known as Constrained Horn Clauses (CHC). In the case of non-linear CHCs, which may arise, e.g., from relational verification tasks, PDR aims to infer an inductive invariant for each uninterpreted predicate. However, in many practical cases this reasoning is not successful, as invariants should be derived for groups of predicates instead of individual predicates. The article describes a novel algorithm that identifies these groups automatically and complements the existing PDR technique. The key feature of the algorithm is that it does not require a possibly expensive synchronization transformation over the system of CHCs. We have implemented the algorithm on top of a up-to-date CHC solver Spacer. Our experimental evaluation shows that for some CHC systems, on which existing solvers diverge, our tool is able to discover relational invariants.
- 23 January 2018
- Published by EasyChair in EPiC Series in Computing
- Vol. 46, 338-319
Synchronizing Constrained Horn Clauses
Simultaneous occurrences of multiple recurrence relations in a system of non-linear constrained Horn clauses are crucial for proving its satis ability. A solution of such system is often inexpressible in the constraint language. We propose to synchronize recurrent computations, thus increasing the chances for a solution to be found. We introduce a notion of CHC product allowing to formulate a lightweight iterative algorithm of merging recurrent computations into groups and prove its soundness. The evaluation over a set of systems handling lists and linear integer arithmetic confirms that the transformed systems are drastically more simple to solve than the original ones.
- 23 January 2018
- Published by EasyChair in EPiC Series in Computing
- Vol. 46, 338-319
Synchronizing Constrained Horn Clauses
Simultaneous occurrences of multiple recurrence relations in a system of non-linear constrained Horn clauses are crucial for proving its satis ability. A solution of such system is often inexpressible in the constraint language. We propose to synchronize recurrent computations, thus increasing the chances for a solution to be found. We introduce a notion of CHC product allowing to formulate a lightweight iterative algorithm of merging recurrent computations into groups and prove its soundness. The evaluation over a set of systems handling lists and linear integer arithmetic confirms that the transformed systems are drastically more simple to solve than the original ones.