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

<!-- <blockquote>[©]</blockquote> -->

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

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

<!-- topub -->
{{stats|disqus_comments=0|refresh_time=2021-08-25T03:19:5031T17:55:39.248751953177|vimeo_comments=0|vimeo_plays=18|youtube_comments=0|youtube_plays=27}}

Версия 14:55, 31 августа 2021

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

Аннотация

Докладчик

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

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

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

Видео

Слайды

Тезисы

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

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