MMMikhail Usamovich Mandrykin

Mikhail Usamovich Mandrykin

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

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Mikhail Usamovich Mandrykin has a total of 19 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Complete Decision Procedure for the Theory of Bounded Pointer Arithmetic

    by R. F. Sadykov, M. U. Mandrykin

    The process of developing C programs is quite often prone to errors associated with the use of pointer arithmetic and operations on memory addresses. Hence, the need for various automated program verification tools arises. One of the techniques frequently employed by these tools is invocation of suitable decision procedures implemented within existing SMT solvers. However, both the SMT standard and the majority of existing SMT solvers lack relevant logics (combinations of logical theories) for the direct and precise modeling of the semantics of pointer operations in C. A possible way to support these logics is to implement them in an SMT solver. However, this approach can be time-consuming (as it requires modifying the source code of the solver), inflexible (because introducing any changes to the signature or semantics of the theory can be unreasonably hard), and limited (every solver has to be supported individually). Another way is to design and implement custom quantifier instantiation strategies. These strategies can then be used to translate formulas in selected theory combinations into formulas in well-supported decidable logics, e.g., QF_UFLIA. In this paper, we present an instantiation procedure for translating formulas in the theory of bounded pointer arithmetic into the QF_UFLIA logic. We formally prove the soundness and completeness of our instantiation procedure in Isabelle/HOL. The paper also presents an informal description of this proof for the proposed procedure. The theory of bounded pointer arithmetic itself is formulated based on known errors associated with the use of pointer arithmetic operations in C, as well as based on the semantics of these operations specified in the C standard. Similar procedure can also be defined for a practically relevant fragment of the theory of bit vectors (monotone propositional combinations of equalities between bitwise expressions). Our approach is sufficient to derive efficient decision procedures, implemented as Isabelle/HOL proof methods, for several decidable logical theories used in C program verification by relying on the existing capabilities of well-known SMT solvers (e.g., Z3), as well as on the proof reconstruction capabilities of the Isabelle/HOL proof assistant.

  • Open Access

    Complete decision procedure for the theory of bounded pointer arithmetic based on quantifier instantiation and SMT

    by Rafael Faritovich Sadykov, Mikhail Usamovich Mandrykin

    Процесс разработки кода на Си довольно часто сопровождается появлением ошибок, связанных с использованием указателей и адресов памяти. В связи с этим возникает потребность создания инструментов автоматизированной проверки программ. Одним из методов, применяемых такими инструментами проверки, является использование решающих процедур на основе SMT-решателей. Но в то же время разрешимые логики (комбинации логических теорий), требуемые для адекватного моделирования указателей в языке Си, непосредственно не присутствуют в стандарте SMT-LIB и не реализованы в большинстве существующих SMT-решателей. Одним из возможных способов поддержки таких логик является непосредственная их реализация в каком-либо SMT-решателе, однако такой подход часто оказывается трудоемким (требуется изменение исходного кода решателя), негибким (трудно модифицировать сигнатуру и семантику новых теорий) и ограниченным (требуется отдельная реализация поддержки теории в каждом используемом решателе). Другим способом является реализация пользовательских стратегий конечного инстанцирования кванторов для сведения формул в неподдерживаемых логиках к формулам в широко распространенных разрешимых логиках, таких как QF_UFLIA. В данной статье представлена процедура инстанцирования лемм для трансляции формул в теории типизированной адресной арифметики в логику QF_UFLIA. Для процедуры трансляции даны доказательства корректности и полноты, а также описана формализация этих доказательств в системе Isabelle/HOL. Сама теория адресной арифметики сформулирована на основе известных ошибок использования адресной арифметики в языке Си, а также спецификаций семантики этих операций из стандарта языка. Аналогичные доказательства и процедура также могут быть сформулированы для фрагмента теории бит-векторов (монотонные формулы над равенствами между выражениями с побитовыми операциями, такими как исключающее “или”, сдвиг, конкатенация, экстракция, отрицание). Представленная в статье процедура трансляции, в частности, позволяет легко реализовать полный метод доказательства утверждений в теории адресной арифметики в системе Isabelle/HOL на основе существующей в этой системе поддержки SMT-решателей (Z3 или VeriT).


  • Formal Specification of a Security Framework for Smart Contracts

    by Mikhail Mandrykin, Jake O’sHannessy, Jacob Payne, Ilya Shchepetkov


  • Open Access

    Formal specification of a security framework for smart contracts

    by Mikhail Mandrykin, Jake O'Shannessy, Jacob Payne, Ilya Shchepetkov

    As smart contracts are growing in size and complexity, it becomes harder and harder to ensure their correctness and security. Due to the lack of isolation mechanisms a single mistake or vulnerability in the code can bring the whole system down, and due to this smart contract upgrades can be especially dangerous. Traditional ways to ensure the security of a smart contract, including DSLs, auditing and static analysis, are used before the code is deployed to the blockchain, and thus offer no protection after the deployment. After each upgrade the whole code need to be verified again, which is a difficult and time-consuming process that is prone to errors. To address these issues a security protocol and framework for smart contracts called Cap9 was developed. It provides developers the ability to perform upgrades in a secure and robust manner, and improves isolation and transparency through the use of a low level capability-based security model. We have used Isabelle/HOL to develop a formal specification of the Cap9 framework and prove its consistency. The paper presents a refinement-based approach that we used to create the specification, as well as discussion of some encountered difficulties during this process.

  • Open Access

    Lemma Functions for Frama-C: C Programs as Proofs

    by Grigoriy Volkov, Mikhail Mandrykin, Denis Efremov

    This paper describes the development of an auto-active verification technique in the Frama-C framework. We outline the lemma functions method and present the corresponding ACSL extension, its implementation in Frama-C, and evaluation on a set of string-manipulating functions from the Linux kernel. We illustrate the benefits our approach can bring concerning the effort required to prove lemmas, compared to the approach based on interactive provers such as Coq. Current limitations of the method and its implementation are discussed.

  • Open Access

    CPA-BAM-Slicing: Block-Abstraction Memoization and Slicing with Region-Based Dependency Analysis

    by Pavel Andrianov, Vadim Mutilin, Mikhail Mandrykin, Anton Vasilyev


  • Region analysis for deductive verification of C programs

    by M. U. Mandrykin, A. V. Khoroshilov

    This paper presents a memory model with nonoverlapping memory areas (regions) for the deductive verification of C programs. This memory model uses a core language that supports arbitrary nesting of structures, unions, and arrays into other structures and allows reducing the number of user-provided annotations as a result of region analysis. This paper also describes semantics of the core language and normalizing transformations for translating an input annotated C program into a program in the core language. In addition, an encoding is proposed for modeling the memory state of a core-language program with logical formulas as described by the model semantics of the core language. For the model semantics, the soundness and completeness theorems are proved. Additional constraints on the typing context of the core-language terms are described that determine the result of the region analysis enabling the complete modeling of a limited class of programs without using additional annotations. A proof sketch for the theorem stating completeness of the proposed region analysis for a limited class of programs is presented.


  • Towards deductive verification of C programs with shared data

    by M. U. Mandrykin, A. V. Khoroshilov

    This paper considers the problem of the deductive verification of the Linux kernel code that is concurrent and accesses shared data. The presence of shared data does not allow applying traditional deductive verification techniques, so we consider how to verify such a code by proving its compliance to a given specification of a certain synchronization discipline. The approach is illustrated by the examples of a spinlock specification and a simplified specification of the read-copy-update (RCU) API.


  • High-level memory model with low-level pointer cast support for Jessie intermediate language

    by M. U. Mandrykin, A. V. Khoroshilov

    The paper presents a target analyzable language used for verification of real-world production GNU C programs (Linux kernel modules). The language represents an extension of the existing intermediate...