Mikhail Usamovich Mandrykin
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
Research Subjects
Mikhail Usamovich Mandrykin has a total of 19 co-authors. Here are the top co-authors by number of shared publications:
- Alexey Vladimirovich Khoroshilov
Ivannikov Institute for System Programming, Russian Academy of Sciences, Moscow, Russia
4 shared publications - Rafael Faritovich Sadykov
Moscow State University, Moscow, Russia
2 shared publications - Vadim Mutilin
Institute for System Programming of the Russian Academy of Sciences
2 shared publications Alexey Khoroshilov
Institute for System Programming of the Russian Academy of Sciences
1 shared publicationAnton Vasilyev
Ivannikov Institute for System Programming of the Russian Academy of Sciences
1 shared publication- Denis Efremov
Faculty of Computer Science National Research University Higher School of Economics Moscow Russia
1 shared publication
Latest Publications
- 21 December 2022
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 48 (8) , 770-780
Complete Decision Procedure for the Theory of Bounded Pointer Arithmetic
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.
- 21 December 2022
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 48 (8) , 770-780
Complete Decision Procedure for the Theory of Bounded Pointer Arithmetic
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
- 1 January 2021
- Published by Institute for System Programming of the Russian Academy of Sciences in Proceedings of the Institute for System Programming of the RAS
- Vol. 33 (4) , 177-194
Complete decision procedure for the theory of bounded pointer arithmetic based on quantifier instantiation and SMT
Процесс разработки кода на Си довольно часто сопровождается появлением ошибок, связанных с использованием указателей и адресов памяти. В связи с этим возникает потребность создания инструментов автоматизированной проверки программ. Одним из методов, применяемых такими инструментами проверки, является использование решающих процедур на основе SMT-решателей. Но в то же время разрешимые логики (комбинации логических теорий), требуемые для адекватного моделирования указателей в языке Си, непосредственно не присутствуют в стандарте SMT-LIB и не реализованы в большинстве существующих SMT-решателей. Одним из возможных способов поддержки таких логик является непосредственная их реализация в каком-либо SMT-решателе, однако такой подход часто оказывается трудоемким (требуется изменение исходного кода решателя), негибким (трудно модифицировать сигнатуру и семантику новых теорий) и ограниченным (требуется отдельная реализация поддержки теории в каждом используемом решателе). Другим способом является реализация пользовательских стратегий конечного инстанцирования кванторов для сведения формул в неподдерживаемых логиках к формулам в широко распространенных разрешимых логиках, таких как QF_UFLIA. В данной статье представлена процедура инстанцирования лемм для трансляции формул в теории типизированной адресной арифметики в логику QF_UFLIA. Для процедуры трансляции даны доказательства корректности и полноты, а также описана формализация этих доказательств в системе Isabelle/HOL. Сама теория адресной арифметики сформулирована на основе известных ошибок использования адресной арифметики в языке Си, а также спецификаций семантики этих операций из стандарта языка. Аналогичные доказательства и процедура также могут быть сформулированы для фрагмента теории бит-векторов (монотонные формулы над равенствами между выражениями с побитовыми операциями, такими как исключающее “или”, сдвиг, конкатенация, экстракция, отрицание). Представленная в статье процедура трансляции, в частности, позволяет легко реализовать полный метод доказательства утверждений в теории адресной арифметики в системе Isabelle/HOL на основе существующей в этой системе поддержки SMT-решателей (Z3 или VeriT).
- 1 January 2021
- Published by Institute for System Programming of the Russian Academy of Sciences in Proceedings of the Institute for System Programming of the RAS
- Vol. 33 (4) , 177-194
Open AccessComplete decision procedure for the theory of bounded pointer arithmetic based on quantifier instantiation and SMT
Процесс разработки кода на Си довольно часто сопровождается появлением ошибок, связанных с использованием указателей и адресов памяти. В связи с этим возникает потребность создания инструментов автоматизированной проверки программ. Одним из методов, применяемых такими инструментами проверки, является использование решающих процедур на основе SMT-решателей. Но в то же время разрешимые логики (комбинации логических теорий), требуемые для адекватного моделирования указателей в языке Си, непосредственно не присутствуют в стандарте SMT-LIB и не реализованы в большинстве существующих SMT-решателей. Одним из возможных способов поддержки таких логик является непосредственная их реализация в каком-либо SMT-решателе, однако такой подход часто оказывается трудоемким (требуется изменение исходного кода решателя), негибким (трудно модифицировать сигнатуру и семантику новых теорий) и ограниченным (требуется отдельная реализация поддержки теории в каждом используемом решателе). Другим способом является реализация пользовательских стратегий конечного инстанцирования кванторов для сведения формул в неподдерживаемых логиках к формулам в широко распространенных разрешимых логиках, таких как QF_UFLIA. В данной статье представлена процедура инстанцирования лемм для трансляции формул в теории типизированной адресной арифметики в логику QF_UFLIA. Для процедуры трансляции даны доказательства корректности и полноты, а также описана формализация этих доказательств в системе Isabelle/HOL. Сама теория адресной арифметики сформулирована на основе известных ошибок использования адресной арифметики в языке Си, а также спецификаций семантики этих операций из стандарта языка. Аналогичные доказательства и процедура также могут быть сформулированы для фрагмента теории бит-векторов (монотонные формулы над равенствами между выражениями с побитовыми операциями, такими как исключающее “или”, сдвиг, конкатенация, экстракция, отрицание). Представленная в статье процедура трансляции, в частности, позволяет легко реализовать полный метод доказательства утверждений в теории адресной арифметики в системе Isabelle/HOL на основе существующей в этой системе поддержки SMT-решателей (Z3 или VeriT).
- 13 August 2020
- Published by Springer Nature
- p. 392-403
Formal Specification of a Security Framework for Smart Contracts
- 13 August 2020
- Published by Springer Nature
- p. 392-403
Formal Specification of a Security Framework for Smart Contracts
- Open Access
Formal specification of a security framework for smart contracts
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 AccessFormal specification of a security framework for smart contracts
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
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 AccessLemma Functions for Frama-C: C Programs as Proofs
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
- 14 April 2018
- Published by Springer Nature
- p. 427-431
CPA-BAM-Slicing: Block-Abstraction Memoization and Slicing with Region-Based Dependency Analysis
- 14 April 2018
- Published by Springer Nature
- p. 427-431
Open AccessCPA-BAM-Slicing: Block-Abstraction Memoization and Slicing with Region-Based Dependency Analysis
- 18 January 2018
- Published by Springer Nature
- p. 256-275
A Memory Model for Deductively Verifying Linux Kernel Modules
- 18 January 2018
- Published by Springer Nature
- p. 256-275
A Memory Model for Deductively Verifying Linux Kernel Modules
- 16 September 2016
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 42 (5) , 257-278
Region analysis for deductive verification of C programs
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.
- 16 September 2016
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 42 (5) , 257-278
Region analysis for deductive verification of C programs
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.
- 16 September 2016
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 42 (5) , 324-332
Towards deductive verification of C programs with shared data
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.
- 16 September 2016
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 42 (5) , 324-332
Towards deductive verification of C programs with shared data
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.
- 25 July 2015
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 41 (4) , 197-207
High-level memory model with low-level pointer cast support for Jessie intermediate language
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...
- 25 July 2015
- Published by Pleiades Publishing Ltd in Programming and Computer Software
- Vol. 41 (4) , 197-207
High-level memory model with low-level pointer cast support for Jessie intermediate language
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...