ДМДмитрий Александрович Мордвинов

Дмитрий Александрович Мордвинов

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Automatic Inference of Synchronous Regular Invariants

    by A. I. Vasenina, Yu. O. Kostyukov, D. A. Mordvinov

    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.

  • AUTOMATIC INFERENCE OF SYNCHRONOUS REGULAR INVARIANTS

    by A.I. Vasenina, Y.O. Kostyukov, D.A. Mordvinov

    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

    UTBot Python at the SBFT Tool Competition 2024

    by Ekaterina Tochilina, Vyacheslav Tamarin, Dmitry Mordvinov, Valentyn Sobol, Sergey Pospelov, Alexey Menshutin, Yury Kamenev, Dmitry Ivanov

    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

    KLEEF: Symbolic Execution Engine (Competition Contribution)

    by Aleksandr Misonizhnik, Sergey Morozov, Yurii Kostyukov, Vladislav Kalugin, Aleksei Babushkin, Dmitry Mordvinov, Dmitry Ivanov

    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

    “Symcrete” memory Model with Lazy Initialization and Objects of Symbolic Sizes in KLEE

    by Sergey Antonovich Morozov, Aleksandr Vladimirovich Misonizhnik, Dmitry Aleksandrovich Mordvinov, Dmitry Vladimirovich Koznov, Дмитрий Аркадьевич Иванов

    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

    Generation of the weakest preconditions of programs with dynamic memory in symbolic execution

    by Aleksandr V. Misonizhnik, Yurii O. Kostyukov, Michael P. Kostitsyn, Dmitry A. Mordvinov, Dmitry V. Koznov

    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

    Automated testing of LLVM programs with complex input data structures

    by Alexander Vladimirovich Misonizhnik, Alexey Alexandrovich Babushkin, Sergey Antonovich Morozov, Yurii Olegovich Kostyukov, Дмитрий Александрович Мордвинов, Dmitry Vladimirovich Koznov

    Символьное исполнение является известным подходом для автоматической генерации регрессионных тестов и поиска ошибок/уязвимостей в программах. Данная работа посвящена созданию практичного метода к символьному исполнению LLVM-программ, пригодного для работы со сложными входными структурами данных. Метод основан на известной идее ленивой инициализации, позволяющей избавить пользователя от необходимости вручную создавать ограничения на входные структуры данных и полностью автоматизировать процесс символьного исполнения программы. Предлагается два улучшения ленивой инициализации для сегментированной символьной моделей памяти – использование временных меток и информации о типах. Предложенный метод реализован в символьной виртуальной машине KLEE для платформы LLVM и протестирован на реальных C-структурах данных — списках, биномиальных кучах, AVL-деревьях, красно-чёрных деревьях, двоичных деревьях и борах (префиксных деревьях).


  • Open Access

    Beyond the elementary representations of program invariants over algebraic data types

    by Yurii Kostyukov, Dmitry Mordvinov, Grigory Fedyukovich

    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

    Property-Directed Inference of Relational Invariants

    by Дмитрий Александрович Мордвинов

    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.

  • Synchronizing Constrained Horn Clauses

    by Dmitry Mordvinov, Grigory Fedyukovich

    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.