?
Современное состояние исследований в области обфускации программ: определение стойкости обфускации
Программирование. 2015. № 6.
Zakharov V., Кузюрин Н. Н., Варновский Н. П., Шокуров А. В.
In press
Program obfuscation is a semantic-preserving transformation aimed at bringing a program into such a form, which impedes the understanding of its algorithm and data structures or prevents extracting of some valuable information from the text of a program. Since obfuscation could find wide use in computer security, information hiding and cryptography, security requirements to program obfuscators became a major focus of interests for pioneers of theory of software obfuscation. In this paper we give a survey of various definitions of obfuscation security and main results that establish possibility or impossibility of secure program obfuscation under certain cryptographic assumptions. We begin with a short retrospective survey on the origin and development of program obfuscation concept in software engineering and mathematical cryptography. In the introduction we also point out on the main difficulties in the development of practical and secure obfuscation techniques. In the next section we discuss the main line of research in the application of program obfuscation to the solution of various problems in system programming and software security. Finally, in section 3 we present and discuss a compendium of formal definitions of the program obfuscation concept developed so far in mathematical cryptography - black-box obfuscation, gray-box obfuscation, the best possible obfuscation, obfuscation with auxiliary inputs, etc.. We also make a comparative analysis of these definitions and present the main results on the (im)possibility of secure program obfuscation w.r.t. every such definition.
Zakharov V.A., Kuzurin N. N., Varnovsky N. P. et al., Programming and Computer Software 2015 Vol. 41 No. 6 P. 361-372
Program obfuscation is a semantic-preserving transformation aimed at bringing a program into a form that impedes understanding of its algorithm and data structures or prevents extracting certain valuable information from the text of the program. Since obfuscation may find wide use in computer security, information hiding and cryptography, security requirements to program obfuscators have become ...
Added: October 13, 2015
Zakharov V., Абрамова И. В., Варновский Н. П. et al., Труды Института системного программирования РАН 2019 Т. 31 № 6 С. 145-162
In this paper, we study the possibility of using a certain cloud computing model supplied with cryptoservers to obfuscate software programs. Earlier, we proposed this cloud computing model in our study of some information security problems for multi-client distributed computing over encrypted data. Based on this model, we proposed a new approach involving the use ...
Added: February 19, 2020
Avdoshin S. M., Набебин А. А., М. : ДМК Пресс, 2019
The book contains the necessary information from the algorithm theory, graph theory, combinatorics. It is considered partially recursive functions, Turing machines, some versions of the algorithms (associative calculus, the system of substitutions, grammars, Post's productions, Marcov's normal algorithms, operator algorithms). The main types of graphs are described (multigraphs, pseudographs, Eulerian graphs, Hamiltonian graphs, trees, bipartite ...
Added: August 24, 2018
Zakharov V., Abbas M. M., Automatic Control and Computer Sciences, USA 2019 Vol. 53 No. 7 P. 589-606
Mathematical models of distributed computations, based on the calculus of mobile processes (pi-calculus) are widely used for checking the information security properties of cryptographic protocols. Since pi-calculus is Turing-complete, this problem is undecidable in general case. Therefore, the study is carried out only for some special classes of pi-calculus processes with restricted computational capabilities, for ...
Added: October 17, 2019
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245-268
It is generally accepted that to unify a pair of substitutions θ_1 and θ_2 means to find out a pair of substitutions η' and η'' such that the compositions θ_1 η' and θ_2 η'' are the same. Actually, unification is the problem of solving linear equations of the form θ_1 X=θ_2 Y in the semigroup ...
Added: September 30, 2015
Vikentyeva O., Полякова О. А., Пермь : Издательство Пермского национального исследовательского политехнического университета, 2019
The tutorial deals with the application of the basic principles of structured programming in complex software systems in the high-level C ++ language, which are demonstrated with meaningful examples. ...
Added: September 16, 2020
Gribanov D., Malyshev D., Mokeev D. B., Дискретный анализ и исследование операций 2020 Т. 27 № 3 С. 71-87
Рассматривается задача минимизации количества цветов в раскрасках вершин задаваемого графа так, что каждой вершине назначаются цвета, число которых равно задаваемому весу вершины, причём смежным вершинам назначаются различные цвета. Для всех наследственных классов, определяемых парой связных 5-вершинных порождённых запретов, кроме четырёх случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. В настоящей ...
Added: September 15, 2020
Zakharov V., Аббас М. М., Моделирование и анализ информационных систем 2018 Т. 25 № 6 С. 589-606
Mathematical models of distributed computing based on the calculus of mobile processes ($\pi$-calculus) are widely used for checking the information security properties of cryptographic protocols. Since $\pi$calculus is Turing-complete, this problem is undecidable in general case. Therefore, the research is carried out only for some special classes of $\pi$-calculus processes with restricted computational capabilities, for ...
Added: October 26, 2018
Switzerland : Springer, 2020
This book presents state-of-the-art intelligent methods and techniques for solving real-world problems and offers a vision of future research. Featuring 143 papers from the 4th Future Technologies Conference, held in San Francisco, USA, in 2019, it covers a wide range of important topics, including, but not limited to, computing, electronics, artificial intelligence, robotics, security and communications ...
Added: October 20, 2019
Switzerland : Springer, 2019
The book, presenting the proceedings of the 2018 Future Technologies Conference (FTC 2018), is a remarkable collection of chapters covering a wide range of topics, including, but not limited to computing, electronics, artificial intelligence, robotics, security and communications and their real-world applications. The conference attracted a total of 503 submissions from pioneering researchers, scientists, industrial ...
Added: October 29, 2018
Goldengorin B. I., Malyshev D., Pardalos P. M., Doklady Mathematics 2013 Vol. 87 No. 3 P. 368-371
The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and ...
Added: June 23, 2013
Zakharov V., Варновский Н. П., Кузюрин Н. Н. et al., Труды Института системного программирования РАН 2014 Т. 26 № 3 С. 167-198
Program obfuscation is a semantic-preserving transformation aimed at bringing a program into such a form, which impedes the understanding of its algorithm and data structures or prevents extracting of some valuable information from the text of a program. Since obfuscation could find wide use in computer security, information hiding and cryptography, security requirements to program ...
Added: September 30, 2015
Malyshev D., Дискретный анализ и исследование операций 2017 Т. 24 № 1 С. 81-96
Понятия граничного и минимального сложного классов графов, объединённые общим термином «критический класс», являются полезными инструментами для анализа вычислительной сложности задач на графах в семействе наследственных классов графов. В данном семействе для нескольких задач на графах известны граничные классы. В этой работе критические классы графов рассматриваются применительно к семействам сильно наследственных и минорно замкнутых классов. До ...
Added: February 27, 2017
Malyshev D., Дискретная математика 2013 Т. 25 № 2 С. 63-67
В статье изучается влияние предельного роста упаковочного числа графов (как функции от числа вершин) на сложностной статус задачи о независимом множестве. Доказывается, что при некоторых естественных предположениях эта задача полиномиально разрешима тогда и только тогда, когда упаковочное число растет по порядку не быстрее логарифма числа вершин. ...
Added: January 15, 2014
Cham : Springer, 2019
The book, presenting the proceedings of the 2018 Future Technologies Conference (FTC 2018), is a remarkable collection of chapters covering a wide range of topics, including, but not limited to computing, electronics, artificial intelligence, robotics, security and communications and their real-world applications. The conference attracted a total of 503 submissions from pioneering researchers, scientists, industrial ...
Added: October 30, 2018
Malyshev D., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2013 Vol. 7 No. 2 P. 221-228
The notion of a boundary class of graphs is a helpful tool for the computational complexity analysis of graph theory problems in the family of hereditary classes. Some general and specific features for families of boundary classes of graphs for the vertex k-colorability problem and its “limit” variant, the chromatic index problem, were studied by ...
Added: June 23, 2013
Vnukov A., М. : Издательство РУДН, 2008
В пособии рассматриваются теория и практика обеспечения информационной безопасности в кредитно–финансовой сфере России, нормативная база по использованию в кредитно-финансовой сфере России российских сертифицированных средств защиты информации, концепция безопасности коммерческого банка, объекты защиты коммерческого банка, единый подход к защите информации в финансовой сфере. Получению детальных сведений о состоянии информационной системы, проверки имеющихся элементов защиты информации, разработки ...
Added: July 21, 2014
Vnukov A., М. : Издательство РУДН, 2008
В пособии рассматриваются теория и практика обеспечения информационной безопасности в кредитно–финансовой сфере России, нормативная база по использованию в кредитно-финансовой сфере России российских сертифицированных средств защиты информации, концепция безопасности коммерческого банка, объекты защиты коммерческого банка, единый подход к защите информации в финансовой сфере. Получению детальных сведений о состоянии информационной системы, проверки имеющихся элементов защиты информации, разработки ...
Added: July 24, 2014
Shvydun S., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/07.
Two-stage superposition choice procedures, which sequentially apply two choice procedures so that the result of the first choice procedure is the input for the second choice procedure, are studied. We define which of them satisfy given normative conditions, showing how a final choice is changed due to the changes of preferences or a set of ...
Added: October 20, 2015
Zakharov V., Новикова Т. А., Труды Института системного программирования РАН 2011 Т. 21 С. 141-166
Many problems in software engineering such as program refactoring, deobfuscation, vulnerability detection, require an efficient toolset for detecting pieces of code that have similar behavior. Current state of art in software clone detection makes it possible to find out only those pieces of code which have the same syntactic structure since. A more profound analysis ...
Added: September 30, 2015
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 3 С. 58-64
An algorithm is implemented in the article for finding the independence number of a n-vertex graph from the class Free({P5,C5, Kp}) in time O(np+O(1)). ...
Added: June 6, 2012
Malyshev D., Дискретный анализ и исследование операций 2013 Т. 20 № 3 С. 26-44
Доказывается полиномиальная разрешимость задачи о независимом множестве для некоторого семейства классов планарных субкубических графов. ...
Added: June 23, 2013
Malyshev D., Дискретный анализ и исследование операций 2012 Т. 19 № 4 С. 66-72
Рассматривается конструктивный подход к формированию новых случаев эффективной разрешимости задачи о независимом множестве в семействе наследственных частей множества графов Free({P5,C5}). Именно, доказывается, что если эта задача полиномиально разрешима в классе Free({P5,C5,G}), то для любого графа H, который может быть индуктивно получен из G применением к текущему графу сложения с K1 или умножения на K1, эта ...
Added: August 31, 2012
Sirotkin D., Malyshev D., Дискретная математика 2017 Т. 29 № 3 С. 114-125
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. Предлагается новый способ редукции графов. С его помощью получено новое доказательство NP-полноты задачи о независимом множестве в классе планарных графов и доказана NP-полнота данной задачи в классе плоских графов, имеющих только треугольные внутренние грани, с максимальной степенью ...
Added: September 7, 2017