Обробка деревоподібних структур і уніфіковане AST

Попередня стаття серії була присвячена теорії парсинга исходников з використанням ANTLR і Roslyn. В ній було зазначено, що процес сигнатурного аналізу коду в нашому проекті PT Application Inspector розбитий на наступні етапи:
  1. парсинг в залежне від мови подання (abstract syntax tree, AST);
  2. перетворення AST у незалежний від мови уніфікований формат (Unified AST, UAST);
  3. безпосереднє зіставлення з шаблонами, описаними на DSL.
Дана стаття присвячена другому етапу, а саме: обробці AST з допомогою стратегій Visitor і Listener, перетворення AST в уніфікований формат, спрощення AST, а також алгоритму зіставлення деревоподібних структур.


Зміст

Обхід AST
Як відомо, парсер перетворює вихідний код в дерево розбору (в дерево, в якому прибрані всі несуттєві токени), званому AST. Існують різні способи обробити таке дерево. Найпростіший полягає в обробці дерева з допомогою рекурсивного обходу нащадків в глибину. Однак даний спосіб застосовується тільки для зовсім простих випадків, у якому існує небагато типів вузлів і логіка обробки проста. В інших випадках, необхідно виносити логіку обробки кожного типу вузла в окремі методи. Це здійснюється з допомогою двох типових підходів (патернів проектування): Visitor і Listener.

Visitor і Listener
У Visitor для відвідування нащадків вузла необхідно вручну викликати методи обходу дочірніх вузлів. При цьому якщо батько має три нащадка, і викликати методи тільки для двох вузлів, то частина піддерева взагалі не буде оброблена. У Listener (Walker) методи відвідування всіх нащадків викликаються автоматично. У Listener існує метод, що викликається на початку відвідування сайту (enterNode) і метод, що викликається після відвідування сайту (exitNode). Методи Visitor, на відміну від Listener, можуть повертати об'єкти і навіть можуть бути типізованими, тобто при оголошенні CSharpSyntaxVisitor кожен метод Visit, буде повертати об'єкт AstNode, який в нашому випадку є загальним предком для всіх інших вузлів уніфікованого AST.

Таким чином, код перетворення дерева з допомогою Visitor виходить більш функціональним і лаконічним за рахунок того, що в ньому немає потреби зберігати інформацію про відвідані сайти. На малюнку нижче можна побачити, що, наприклад, при перетворенні мови PHP, непотрібні вузли HTML і CSS відсікаються. Порядок обходу позначений числами. Listener зазвичай використовується при аггрегации даних (наприклад з файлів типу CSV), перетворення одного коду в інший (JSON -> XML). Докладніше про це написано в "The Definitive ANTLR 4 Reference".

Visitor & Listener

Відмінності в Visitor в ANTLR і Roslyn.
Реалізація Visitor і Listener може відрізнятися в бібліотеках. Наприклад, у таблиці нижче описані класи і методи Visitor і Listener в Roslyn і ANTLR.







ANTLR Roslyn Visitor AbstractParseTreeVisitor< Result > CSharpSyntaxVisitor< Result > Listener IParseTreeListener CSharpSyntaxWalker Default DefaultResult DefaultVisit(SyntaxNode node) Visit Visit(IParseTree tree) Visit(SyntaxNode node)
І ANTLR і Roslyn мають методи для повернення результату за замовчуванням (якщо метод Visitor для якоїсь синтаксичної конструкції не перевизначений), а також узагальнений метод Visit, який сам визначає, який спеціальний метод Visitor повинен викликатися.

У ANTLR визиторе для кожного синтаксичного правила граматики генерується власний Visitor. Також існують спеціальні типи методів:
  • VisitChild(IRuleNode node)
    ; використовується для реалізації обходу сайту за замовчуванням.
  • VisitTerminal(IRuleNode node)
    ; використовується при обході термінальних вузлів, тобто токенів.
  • VisitErrorNode(IErrorNode node)
    ; використовується при обході токенів, отриманих в результаті парсинга коду з лексичними або синтаксичними помилками. Наприклад, якщо в утвердженні пропущена крапка з комою в кінці, то парсер вставить такий токен і вкаже, що він є помилковим. Детальніше про помилки парсинга написано у попередній статті.
  • AggregateResult(AstNode aggregate, AstNode nextResult)
    ; рідко використовуваний метод, призначений для аггрегации результатів обходу нащадків.
  • ShouldVisitNextChild(IRuleNode node, AstNode currentResult)
    ; рідко використовуваний метод, призначений для визначення того, чи потрібно обробляти наступного нащадка
    node
    в залежності від результату обходу вузла
    currentNode
    .
Roslyn відвідувач має спеціальні методи для кожної синтаксичної конструкції і узагальнений метод Visit для всіх вузлів. Однак методів для обходу "проміжних" конструкцій в ньому немає, на відміну від ANTLR. Наприклад, в Roslyn не існує методу для тверджень
VisitStatement
, а тільки існують спеціальні
VisitDoStatement
,
VisitExpressionStatement
,
VisitForStatement
і т. д. як
VisitStatement
можна використовувати узагальнений
Visit
. Ще однією відмінністю є те, що методи обходу тривіальних (SyntaxTrivia) сайтів, тобто сайтів, які можна видалити без втрати інформації про код (пропуски, коментарі), викликаються поряд з методами обходу основних вузлів і токенів.

Недоліком ANTLR визиторов є те, що назви згенерованих методів-Visitor безпосередньо залежать від стилю написання правил граматики, тому вони можуть не вписуватися в загальну стилістику коду. Наприклад, sql-граматиках прийнято використовувати так званий Snake case, в якому для розділення слів використовуються символи підкреслення. Roslyn методи написані в стилістиці C#-коду. Незважаючи на відмінності, методи обробки деревоподібних структур в Roslyn і ANTLR з новими версіями все більше і більше уніфікуються, що не може не радувати (в ANTLR версії 3 і нижче не було механізму Visitor і Listener).

Граматика і Visitor в ANTLR.
У ANTLR правила
ifStatement
: If parenthesis statement elseIfStatement* elseStatement?
| If parenthesis ':' innerStatementList elseIfColonStatement* elseColonStatement? EndIf ';'
;

буде сформовано метод
VisitIfStatement(PHPParser.IfStatementContext context)
в якому context буде мати наступні поля:
  • parenthesis
    – одиничний вузол;
  • elseIfStatement*
    – масив вузлів. Якщо синтаксис відсутня, то довжина масиву дорівнює нулю;
  • elseStatement?
    – опціональний вузол. Якщо синтаксис відсутня, то приймає значення null;
  • If
    ,
    EndIf
    — термінальні вузли, починаються з великої літери;
  • ':'
    ,
    ';'
    — термінальні вузли, які не містяться в context (доступні тільки через GetChild()).
Варто відзначити, що чим менше правил існує в граматиці, тим легше і швидше писати Visitor. Однак повторюваний синтаксис також потрібно виносити в окремі правила.

Альтернативні і елементні мітки в ANTLR
Часто виникають ситуації, в яких зазвичай має кілька алтернатив і було б логічніше обробляти ці альтернативи в окремих методах. На щастя, в ANTLR 4 для цього існують спеціальні альтернативні мітки, які починаються з символу
#
і додаються після кожної альтернативи правила. При генерації коду програми, для кожної мітки генерується окремий метод-Visitor, що дозволяє уникнути великої кількості коду в разі, якщо правило має багато альтернатив. Варто відзначити, що повинні позначатися або всі альтернативи, або жодної. Також для позначення терміналу, приймає безліч значень, можна використовувати елементні мітки (rule element label):
expression
: op=('+'|'-'|'++'|'--') expression #UnaryOperatorExpression
| expression op=('*'|'/'|'%') expression #MultiplyExpression
| expression op=('+'|'-') expression #AdditionExpression
| expression op='&&' expression #LogicalAndExpression
| expression op='?' expression op2=':' expression #TernaryOperatorExpression
;

Для цього правила ANTLR згенерує визиторы
VisitExpression
,
VisitUnaryOperatorExpression
,
VisitMultiplyExpression
та ін. У кожному визиторе буде існувати масив expression, що складається з 1 або 2 елементів, а також літерал op. Завдяки міткам, код визиторов буде більш чистим і лаконічним:
Код при використанні альтернативних та елементних міток
public override AstNode VisitUnaryOperatorExpression(TestParser.UnaryOperatorExpressionContext context)
{
var op = new MyUnaryOperator(context.op().GetText());
var expr = (Expression)VisitExpression(context.expression(0));
return new MyUnaryExpression(op, expr);
}

public override AstNode VisitMultiplyExpression(TestParser.MultiplyExpressionContext context)
{
var left = (Expression)VisitExpression(context.expression(0));
var op = new MyBinaryOpeartor(context.op().GetText());
var right = (Expression)VisitExpression(context.expression(1));
return new MyBinaryExpression(left, op, right);
}

public override AstNode VisitTernaryOperatorExpression(TestParser.TernaryOperatorExpressionContext context)
{
var first = (Expression)VisitExpression(context.expression(0));
var second = (Expression)VisitExpression(context.expression(1));
var third = (Expression)VisitExpression(context.expression(2));
return new MyTernaryExpression(first, second, third);
}

...

Без альтернативні міток, обробка Expression перебувала б в одному методі і код виглядав так:
Код без використання альтернативних та елементних міток
public override AstNode VisitExpression(TestParser.ExpressionContext context)
{
Expression expr, expr2, expr3;
if (context.ChildCount == 2) // Unary
{
var op = new MyUnaryOperator(context.GetChild<ITerminalNode>(0).GetText());
expr = (Expression)VisitExpression(context.expression(0));
return new MyUnaryExpression(op, expr);
}
else if (context.ChildCount == 3) // Binary
{
expr = (Expression)VisitExpression(context.expression(0));
var binaryOp = new MyBinaryOpeartor(context.GetChild<ITerminalNode>(0).GetText());
expr2 = (Expression)VisitExpression(context.expression(1));
return new MyBinaryExpression(expr, binaryOp, expr2);
...
}
else // Ternary
{
var first = (Expression)VisitExpression(context.expression(0));
var second = (Expression)VisitExpression(context.expression(1));
var third = (Expression)VisitExpression(context.expression(2));
return new MyTernaryExpression(first, second, third);
}
}

Варто зазначити, що альтернативні мітки існують не тільки в ANTLR, але і інших засобах для опису граматик. Наприклад, в Nitra мітка зі знаком привласнення ставиться зліва від альтернативи, на відміну від ANTLR:
syntax Expression
{
| IntegerLiteral
| BooleanLiteral
| NullLiteral = "null";
| Parenthesized = "(" Expression ")";
| Cast1 = "(" !Expression AnyType ")" Expression;
| ThisAccess = "this";
| BaseAccessMember = "base" "." QualifiedName;
| RegularStringLiteral;


Типи вузлів уніфікованого AST
При розробці структури уніфікованого AST і типів вузлів, ми керувалися структурою AST з проекту NRefactory на увазі того, що вона є нам досить простий, а отримання достовірного дерева (fidelity, оборотне у вихідний код з точністю до символу) не вимагалося. Будь-який вузол є спадкоємцем AstNode і має власний тип NodeType, який також використовується на етапі матчинга і при десеріалізації з JSON. Структура вузлів виглядала приблизно наступним чином:
UAST Types
Крім типу, кожен вузол має властивість, що зберігає розташування в коді (TextSpan), яке використовується для його відображення у вихідний код при зіставленні з шаблоном. Нетерминальный вузол зберігає список дочірніх вузлів, а термінальний — числове, рядковий або інше примітивне значення.

Для того, щоб зв'язати вузли AST різних мов, була складена таблиця, в якій рядками був синтаксис визначених вузлів, а стовпцями — їх реалізація в мовах C#, Java, PHP, що виглядало наступним чином:







Node Args C# Java PHP MCA MDA While cond:Expression; stmt:Statement while (cond) stmt while (cond) stmt while (cond) stmt While(cond, stmt) While(cond, stmt) BinaryOp l,r:Expression; op:Literal l op r l op r l op r BinaryOp(l, op, r) BinaryOp(l, op, r) ... ... ... ... ... ... ... Checked checked:Expression checked(checked) - - checked Checked(checked) NullConditional a:Expression,b:Literal a?.b - - a != null? a.b: null a?.b
В цій таблиці:
  • Expression; вираз, що має значення, що повертається.
  • Statement; затвердження (інструкція), не має возвращемого значення.
  • Literal; термінальний вузол.
  • Most Common Ast (MCA) найбільш уніфікована AST. Даний вузол будується, якщо всі три мови містять у собі тип такого або подібного вузла (наприклад, IfStatement, AssignmentExpression);
  • Most Detail Ast (MDA) найбільш деталізоване AST. Даний вузол будується, якщо хоча б одна мова містить в собі такий тип вузла (наприклад, FixedStatenemt
    fixed (a) { }
    для C#). Дані вузли більш актуальні для SQL-подібних мов, з-за того що останні декларативні мови і між T-SQL і C# різниця набагато більше, ніж, наприклад, між PHP і C#.
Крім вузлів, представлених на малюнку (і "вузлів-патернів", які описані в наступному розділі), існують ще штучні вузли для того, щоб все ж побудувати вузол Most Common Ast, "втративши" при цьому якомога менше синтаксису. Такими вузлами є:
  • MultichildExpression; має тип Expression, але при цьому містить в собі колекцію інших Expression;
  • WrapperExpression; має тип Expression, але при цьому містить в собі будь AstNode;
  • WrapperStatement; має тип Statement, але при цьому містить в собі будь AstNode.
В імперативних мовах програмування основними конструкціями є вираження Expression та затвердження Statement. Перші мають значення, що повертається, другі ж використовуються для здійснення будь-яких операцій. Тому в нашому модулі ми також сконцетрировались здебільшого на них. Вони є базовими "цеглинками" для реалізації CFG та інших уявлень вихідного коду, необхідних для реалізації taint-аналізу в майбутньому. Варто додати, що знання про синтаксичному цукрі, дженериках та інших специфічних для конкретної мови речей пошуку вразливостей в коді не потрібно. Тому синтаксичний цукор можна розкривати в стандартні конструкції, а інформацію про специфічні речі взагалі видаляти.

Патерн-вузлами є штучні вузли, що представляють шаблони. Наприклад, в якості патернів-літералів використовуються діапазони чисел, регулярні вирази.

Тестування конвертерів
Для аналізатора коду пріоритетним завданням є тестування всього коду, а не окремих його частин. Для вирішення цієї задачі було вирішено перевантажити методи-визиторы для всіх типів вузлів. При цьому, якщо відвідувач не використовується, то він генерує виняток
new ShouldNotBeVisitedException(context)
. Такий підхід спрощує розробку, оскільки IntelliSense враховує, які методи перевантажені, а які — ні, тому легко визначити, які методи визиторы вже були реалізовані.
Також, ми маємо деякі міркування на тему того, як поліпшити тестування покриття всього коду. Кожен вузол уніфікованого AST зберігає в собі координати відповідного йому коду. При цьому всі термінали пов'язані з лексемами, тобто певними послідовностями символів. Так як всі лексеми по можливості необхідно обробити, то загальний коефіцієнт покриття можна виразити наступною формулою, в якій
uterms
— термінали уніфікованого AST, а
terms
— термінали звичайного Roslyn або ANTLR AST:

cover factor

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

Спрощення AST
Після перетворення звичайного AST в UAST, останнім потрібно спростити. Найбільш простою і корисною оптимізацією є згортка констант (constant folding). Наприклад, існує окремий клас нестачі коду, пов'язаний з установкою занадто великого часу життя для cookie:
cookie.setMaxAge(2147483647);
Аргумент в дужках може бути записаний як одним числом, наприклад
86400
, так і яким-то арифметичним виразом, наприклад
60 * 60 * 24
. Інший приклад пов'язаний з конкатенацией рядків при пошуку SQL-ін'єкцій та інших вразливостей.

Для реалізації цієї задачі був реалізований власний інтерфейс і сам Visitor тільки вже для UAST. Так як спрощення AST просто зменшує кількість вузлів дерева, то Visitor був типізованих, приймає і повертає один і той же тип. Завдяки підтримці рефлекции .NET, вийшло реалізувати такий Visitor з невеликою кількістю коду. Так як кожен вузол містить у собі інші вузли або термінальні примітивні значення, то за допомогою рефлексії можливо отримати всі члени певного вузла і обробити їх, викликаючи інші визиторы рекурсивно.

Алгоритм зіставлення AST і шаблонів
При обході уніфікованого AST кожен шаблон "намагається" накластися на шматочок AST поточного вузла. На початку порівнюється тип вузла, а потім, залежно від типу, проводяться наступні операції:
  • Рекурсивне порівняння нащадків.
  • Порівняння простих литеральных типів (ідентифікатор, рядки, числа).
  • Порівняння розширених литеральных типів (регулярні вирази, діапазони). Коментарі входять в цю групу.
  • Порівняння складних розширені типів (вирази, послідовність Statement).
В основі даного алгоритму лежать прості принципи, що дозволяють досягти високої продуктивності при порівняно невеликій кількості що реалізує їх коду. Останнє досягається за рахунок того, що метод CompareTo для порівняння сайтів реалізований для базового класу, терміналів і невеликого числа інших вузлів. Більш просунуті алгоритми співставлення для покращення продуктивності, засновані на кінцевих автоматах, реалізовувати поки не знадобилося. Однак даний алгоритм проблематично (або навіть неможливо) використовувати для більш поглибленого аналізу, наприклад, враховує зв'язки між Statement.

Висновок
У даній статті ми розглянули патерни Visitor і Listener для обробки дерев, а також розповіли про структуру уніфікованого AST. У наступних статтях ми розповімо:
  • про підходів до зберігання шаблонів (Hardcoded, Json, DSL);
  • розробці і використанні DSL для опису шаблонів;
  • прикладах реальних шаблонів і їх пошуку у відкритих проектах;
  • побудові CFG, DFG і taint-аналізі.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.