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

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

== Аннотация ==
;Докладчик: {{Speaker|Алексей Пустыгин}}
<blockquote>
Предложено эквивалентное представление исходного текста в форме, пригодной для выполнения анализов потока данных в потоке управления.
Оно основано на трансформации универсального промежуточного представления по данным и операциям над ними.

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

== Видео ==

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

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

{{----}}

== Тезисы ==

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

Одним из подходов, упрощающих статический анализ и построение различных эквивалентных представлений исходных текстов на разных языках,
является  использование  универсального  промежуточного  представления  (УПП)  [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).


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

Схему данных формата 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, построенным для одной переменной, но с ответвлениями для
побочных носителей.

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

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

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

Возможные варианты использования UIRDCF:
* Фильтрация в исходном коде позиций использования заданного поля или глобальной переменной по типу операции (Read, Copy, Share, Modify).
* ЭП Butterﬂy — глобальные потоки данных к переменной и из неё с разграничением типов потоков (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]: dcﬂow.xsd      [Электронный      ресурс].      URL:      https://yadi.sk/d/E0DfDdwKdLvjF (дата обращения: 08.01.2016).
;[7]:  UIRDCF.txt     [Электронный     ресурс].     URL:     https://yadi.sk/d/yWhYELCkeoiYS (дата обращения: 08.01.2016).

{{----}}

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

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

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

<!-- topub -->
{{stats|disqus_comments=0|refresh_time=2021-08-31T17:55:39.953177|vimeo_comments=0|vimeo_plays=18|youtube_comments=0|youtube_plays=27}}