10.14489/vkit.2025.03.pp.057-063

DOI: 10.14489/vkit.2025.03.pp.057-063

Плаксин С. И.
МЕТОД ФОРМИРОВАНИЯ ГРАФА ВЫПОЛНЕНИЯ ПРОГРАММЫ ДЛЯ ПОИСКА ВЛОЖЕННЫХ ЦИКЛОВ НА ОСНОВЕ СТАТИЧЕСКОГО И ДИНАМИЧЕСКОГО АНАЛИЗОВ ИСПОЛНИМОГО КОДА
(с. 57-63)

Аннотация. Изложен метод построения графа выполнения программы на основе статического и динамического анализов исполнимого кода программы для последующего поиска вложенных циклов и их классификации. Приведена упрощенная структура графа выполнения для снижения повторных вычислений при обработке. Приведен алгоритм совмещения графов выполнения программы, получаемых от статического и динамического анализов. Информация о циклах открывает возможности для автоматического распараллеливания на системе пользователя с учетом ее конфигурации.

Ключевые слова: граф исполнения программы; статический анализ кода; динамический анализ кода; вложенные циклы; исполнимый код.

Plaksin S. I.
METHOD OF FORMING A PROGRAM EXECUTION GRAPH TO SEARCH FOR NESTED CYCLES BASED ON STATIC AND DYNAMIC ANALYSIS OF EXECUTABLE CODE
(pp. 57-63)

Abstract. A method is proposed for constructing a program execution graph based on static and dynamic analysis of executable program code for subsequent search for nested loops and their classification. A simplified structure of the execution graph is presented to reduce the number of repeated calculations during processing. Such structure consists of individual procedure subgraphs that being linked to each other. Code instructions grouped into code instruction blocks separated by jmp-type instructions. It is shown how nesting depth of loop can be calculated utilizing intraprocedure and interprocedure nesting depth of each subgraph. The process of obtaining execution graphs based on static and dynamic analysis of executable program is briefly described. A method for combining program execution graphs obtained from static and dynamic analysis is presented. The graph from static analysis used as a basis, due to its higher code coverage. First stage is an algorithm for initial matching of corresponding procedure subgraphs of both graphs, using the memory address of first vertex. Second stage is an algorithm for combination of both subgraphs into one, using the memory address to determine the equality of all vertices in both subgraphs. Third stage is an algorithm for adjusting the execution order records from the dynamic analysis to the obtained graph. The resulting information about cycles can be applied for automatic parallelization on the user's system side, taking into account its configuration.

Keywords: Program execution graph; Static code analysis; Dynamic code analysis; Nested loops; Executable code.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

С. И. Плаксин (Тульский государственный университет, Тула, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

S. I. Plaksin (Tula State University, Tula, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Штейнберг Б. Я. Распараллеливание программ для суперкомпьютеров с параллельной памятью и открытая распараллеливающая система: специальность 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей»: автореферат дис… д-ра техн. наук: / Штейнберг Борис Яковлевич; Южный федеральный университет. Ростов-на-Дону: Таганрогский государственный радиотехнический университет, 2004.
2. Efficient scheduling of nested parallel loops on multicore systems / A. Kejariwal, A. Nicolau, A. V. Veidenbaum et al. // 38th International Conference on Parallel Processing (ICPP 2009). 22–25 September 2009. Vienna, Austria. IEEE., 2009. С. 74–83.
3. Arato P., Suba G. A data flow graph generation method starting from c description by handling loop nest hierarchy // 9th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI 2014). 15–17 May 2014. Timisoara, Romania, IEEE, 2014.
4. Alfred V. A., Monica S. L., Jeffrey D. U. Compilers Principles, Techniques & Tools. London: Pearson Education Inc., 2007. С. 525–533.
5. Михайлов А. А. Анализ графа потоков управления в задаче декомпиляции подпрограмм объектных файлов dcuil // Вестник Новосибирского государственного университета Сер. Информационные технологии, Т. 12, № 2. 2014. С. 74–79.
6. Eagle C. The IDA Pro Book: The Unofficial Guide to the World's Most Popular Disassembler San Francisco, CA: No Starch Press, Inc., 2011.
7. Theiling H. Control flow graphs for real-time systems analysis //Universität des Saarlandes, Diss. 2002.
8. Babai L. Graph isomorphism in quasipolynomial time // Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. Cambridge. 19–21 June 2016. MA, USA. С. 684–697.

Eng

1. Shteynberg B. Ya. (2004). Parallelization of programs for supercomputers with parallel memory and an open parallelizing system. Doctor of Technical Sciences: Mathematical and software support for computing machines, complexes and computer networks. Southern Federal University. Rostov-on-Don: Taganrogskiy gosudarstvennyy radiotekhnicheskiy universitet. [in Russian language]
2. Kejariwal A., Nicolau A., Veidenbaum A. V. et al. (2009). Efficient scheduling of nested parallel loops on multicore systems. Vienna: 38th International Conference on Parallel Processing, (ICPP 2009). IEEE, 74 – 83.
3. Arato P., Suba G. (2014). A data flow graph generation method starting from c description by handling loop nest hierarchy. Timisoara: 9th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI 2014). IEEE.
4. Alfred V. A., Monica S. L., Jeffrey D. U. (2007). Compilers Principles, Techniques & Tools, 525 – 533. London: Pearson Education Inc.
5. Mihaylov A. A. (2014). Analysis of the control flow graph in the task of decompiling subroutines of dcuil object files. Vestnik Novosibirskogo gosudarstvennogo universiteta Seriya Informatsionnye tekhnologii, 12(2), 74 – 79. [in Russian language]
6. Eagle C. (2011). The IDA Pro Book: The Unofficial Guide to the World's Most Popular Disassembler. San Francisco: No Starch Press, Inc.
7. Theiling H. (2002). Control flow graphs for realtime systems analysis. Universität des Saarlandes, Diss.
8. Babai L. (2016). Graph isomorphism in quasipolynomial time, 684 – 697. Cambridge: Proceedings of the fortyeighth annual ACM symposium on Theory of Computing.

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 700 руб. (в том числе НДС 20%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2025.03.pp.057-063

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 700 rubles. (including VAT 20%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2025.03.pp.057-063

and fill out the form