Построение эквивалентного представления исходных текстов в форме пригодной для выполнения анализов потока данных в потоке управления — различия между версиями

== Видео ==

{{vimeoembed|156812644|800|450}}
{{youtubelink|gVTNnHyBIIk}}{{letscomment}}
{{oseduconf-2016-draft}}

== Слайды ==

=== Трансформация универсального промежуточного представления по данным и операциям над ними ===

В  дальнейшем  для  обозначения  трансформации  УПП  по  данным  и  операциям  над  ними  будем  использовать  термин  Universal
Intermediate Representation of Data/Control Flow (UIRDCF).

Известны аналогичные представления: Program Dependence Graph (PDG) [3] и System Dependence Graph (SDG) [3,4], в которых фигурируют как зависимости данных, так и зависимости потока управления.

Связи в этих представлениях, которые относятся к зависимостям данных (data dependence), строятся по факту наличия операций над носителями данных (переменными), которые упоминаются в каждом из узлов, между которыми эта связь устанавливается, а сами узлы являются единичным оператором выполнения (single execution statement).

Направление связи определяется потоком управления и AST.

При этом сами связи не атрибутируются информацией о типе производимой операции, вместо этого в них содержится узел AST этой операции.

Алгоритм получения представления UIRDCF [5] однопроходный и выражается в трансформации имеющейся информации в УПП в абстрагированный набор операций над идентификаторами (носителями данных) в обертке операторов потока управления (Таблица 1).


[[File:Построение эквивалентного представления кода в форме пригодной для выполнения анализов потока данных в потоке управления-tab1.png|center|page=-|640px]]

Схему данных формата UIRDCF можно найти в [6], а текстовое описание элементов схемы в [7].

=== Граф распространения данных в потоке управления ===

== Примечания и отзывы ==
<!-- <blockquote>[©]</blockquote> -->

{{fblink|1693782940874720}}                                          
{{vklink|157}}                                          
<references/>

[[Category:OSEDUCONF-2016]]
[[Category:Наука]]
[[Category:Open-source projects]]





<!-- topub -->
{{stats|disqus_comments=0|refresh_time=2020-01-04T16:09:422021-08-31T17:55:39.006530953177|vimeo_comments=0|vimeo_plays=138|youtube_comments=0|youtube_plays=26}}7}}

[[Категория:OSEDUCONF-2016]]
[[Категория:Статический анализ кода]]

Текущая версия на 07:56, 20 октября 2025

«Построение эквивалентного представления исходных текстов программ в форме пригодной для выполнения анализов потока данных в потоке управления (Алексей Пустыгин, OSEDUCONF-2016)»

Аннотация[править | править вики-текст]

Докладчик

Алексей Пустыгин

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

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

Видео[править | править вики-текст]

on youtube

Слайды[править | править вики-текст]

Тезисы[править | править вики-текст]

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

Одним из подходов, упрощающих статический анализ и построение различных эквивалентных представлений исходных текстов на разных языках, является использование универсального промежуточного представления (УПП) [1,2].

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

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

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

Трансформация универсального промежуточного представления по данным и операциям над ними[править | править вики-текст]

В дальнейшем для обозначения трансформации УПП по данным и операциям над ними будем использовать термин Universal Intermediate Representation of Data/Control Flow (UIRDCF).

Известны аналогичные представления: Program Dependence Graph (PDG) [3] и System Dependence Graph (SDG) [3,4], в которых фигурируют как зависимости данных, так и зависимости потока управления.

Связи в этих представлениях, которые относятся к зависимостям данных (data dependence), строятся по факту наличия операций над носителями данных (переменными), которые упоминаются в каждом из узлов, между которыми эта связь устанавливается, а сами узлы являются единичным оператором выполнения (single execution statement).

Направление связи определяется потоком управления и AST.

При этом сами связи не атрибутируются информацией о типе производимой операции, вместо этого в них содержится узел AST этой операции.

Алгоритм получения представления UIRDCF [5] однопроходный и выражается в трансформации имеющейся информации в УПП в абстрагированный набор операций над идентификаторами (носителями данных) в обертке операторов потока управления (Таблица 1).

Схему данных формата UIRDCF можно найти в [6], а текстовое описание элементов схемы в [7].

Граф распространения данных в потоке управления[править | править вики-текст]

На основе полученного эквивалентного представления был разработан анализ в форме графа распространения данных в потоке управления. Данное представление является демонстрацией возможности выполнения анализов по разработанному эквивалентному представлению UIRDCF и позволяет отследить распространение данных из заданного носителя в потоке управления метода, а также вызовы, которые могут модифицировать аргументы, с учетом передачи переменной по ссылке или через указатель.

Возможны и другие анализы по данному представлению.

В дальнейшем граф распространения данных в потоке управления будем называть Data Redistribution in Control Flow (DRCF). Данное представление является трансформацией UIRDCF по заданным параметрам:

• Отслеживаемый идентификатор (носитель данных);
• Точка начала отслеживания (позиция в исходном тексте);
• Глубина отслеживания (не ограничена по умолчанию);
• Список имен методов с номерами и уровнями аргументов для отслеживания.

Алгоритм построения однопроходный. Построение начинается с обнаружения, начиная с заданной, начальной точки (позиции в исходном тексте) отслеживаемого идентификатора, который добавляется в список отслеживаемых идентификаторов. Далее стартует процесс отслеживания (трассировки) операций над идентификаторами из данного списка: чтения (Read), копирования (Copy), распространения (Share) и модификации (Modify).

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

Для детального анализа, дополнительно указывается список методов с набором интересуемых аргументов в качестве отслеживаемых носителей (Таблица 2).

Данное представление также записывается как текст на языке разметки XML.

Сравнение предложенных эквивалентных представлений и анализа с аналогами UIRDCF позволяет получить расширенную, но несколько абстрагированную от AST, версию PDG и SDG.

Различные операторы из AST в UIRDCF представлены классом производимой операции над данными. DRCF при этом можно сравнить с графом зависимостей данных из PDG, построенным для одной переменной, но с ответвлениями для побочных носителей.

Побочным носителем в данном примере выступает переменная «y» (помечена жирным), которая принимает данные из отслеживаемой переменной «x» посредством операции класса копирования (в данном случае оператор присваивания).

Возможные варианты использования предложенных эквивалентных представлений[править | править вики-текст]

Возможные варианты использования UIRDCF:

• Фильтрация в исходном коде позиций использования заданного поля или глобальной переменной по типу операции (Read, Copy, Share, Modify).
• ЭП Butterfly — глобальные потоки данных к переменной и из неё с разграничением типов потоков (copy/share).

Возможные варианты использования DRCF:

• Точки потенциальной неявной модификации данных — передача аргументов в вызовы методов по ссылке или указателю, модификация вторичных носителей данных (акцепторов), полученных через операцию Share (через указатель или по ссылке).

Выводы[править | править вики-текст]

Полученное эквивалентное представление UIRDCF удовлетворяет поставленным критериям для эквивалентного представления, на основании которого можно выполнять анализы потоков данных и управления совместно. Использование в качестве его основы УПП позволяет получить ряд универсальных инструментов для построения анализов.

Представление DRCF демонстрирует возможность анализов по предложенному эквивалентному представлению UIRDCF.

Описанный анализ DRCF демонстрирует преимущество уровневого подхода к построению полезных анализов исходных текстов, путем разбиения этой задачи на универсальные и независимые фрагменты и уровни: генератор DRCF не включает в себя ни модуля анализа исходного текста, ни модуля разбора УПП, только модуль разбора представления UIRDCF; при том какие-либо изменения в формате УПП, которые соответствующим образом учтены в генераторе UIRDCF, не повлияют на генератор анализа DRCF.\

Литература[править | править вики-текст]

[1]

Ошнуров Н. А. Построение универсального промежуточного представления исходных текстов на языках C++ и C# / Н. А. Ошнуров,

А. Н. Пустыгин, А. А. Ковалевский // Доклады Томского государственного университета систем управления и радиоэлектроники. — 2014. – Т. 33, № 3. — С. 135–139.

[2]

UIR.pdf [Электронный ресурс]. URL: https://yadi.sk/i/u3v0H-QTeohLV (дата обращения: 08.01.2016).

[3]

Background. Program Dependence Graph. [Электронный ресурс]. URL: http://www4.comp.polyu.edu.hk/~cscllo/teaching/SDGAPI/background.htm (дата обращения: 08.01.2016).

[4]

University of Leicester CO7206 [Электронный ресурс]. URL: http://www.cs.le.ac.uk/people/mer14/quiz2answer.html (дата обращения:08.01.2016).

[5]

Ковалевский А. А. Построение эквивалентного представления исходных текстов программ в форме, пригодной для выполнения анализов потока данных в потоке управления / Ковалевский А. А., Пустыгин А. Н., Ошнуров Н. А.// Известия Юго-Западного государственного университета Серия управление, вычислительная техника, информатика. медицинское приборостроение. — 2015, №1 (14). — C. 28–34.

[6]

dcflow.xsd [Электронный ресурс]. URL: https://yadi.sk/d/E0DfDdwKdLvjF (дата обращения: 08.01.2016).

[7]

UIRDCF.txt [Электронный ресурс]. URL: https://yadi.sk/d/yWhYELCkeoiYS (дата обращения: 08.01.2016).

Примечания и отзывы[править | править вики-текст]

• Discuss on Facebook
• Discuss on VK

Plays:45   Comments:0