Комментарии 21
Идеальный SAST
Можете вкратце рассказать, что из себя представляет ваш SAST, какие уязвимости
находит, и почему он идеальный?
свертка блоков {} в токен, с обработкой этих токенов позднее в новом парсере,
Расскажите подробней, как это сворачивается в один токен? Из статьи и исходников я так этого и не понял. Вы пользуйтесь тем, что ANTLR лексер контекстно-свободный, как и парсер, что дает возможность задавать рекурсивные токены? Примерно так:
FoldBlock
: '{' (FoldBlock | .)* '}'
;Ключи запуска JVM: -Xmx4G -XX:+UseG1GC -XX:MaxHeapFreeRatio=30 -XX:MinHeapFreeRatio=10
Для файла tsserver.js ключ -Xmx32G, при этом потребление памяти достигло 22 гб!
Насколько понял, вы формируете свое представление для использования на последующих этапах, а не используете дефолтное ANTLR дерево разбора? Если так, то мне кажется, что если не строить дерево по-умолчанию, т.е. устанавливать BuildParseTree = false, а в Listener методах строить свое, то результат по памяти получился бы не особо хуже. Да и грамматика упростилась — не пришлось бы в каждом блоке прописывать код для создания конкретного узла.
Добавил в статью код, вообще можно вот тут посмотреть: лексер
Предлагаю самостоятельно разобраться, почему эта свертка будет работать быстрее, чем правило, написанное на ANTLR, а так же почему то, что вы предлагаете не будет работать.
Можете вкратце рассказать, что из себя представляет ваш SAST, какие уязвимости
находит, и почему он идеальный?
Без холиваров.
Да и грамматика упростилась — не пришлось бы в каждом блоке прописывать код для создания конкретного узла.
Грамматика не станет проще, вы пытаетесь смотреть на частности, не увидев всю картину, причем даже в том участке проекта, который был раскрыт на гитхабе — уже можно увидеть причину, почему строится собственное дерево.
AST — это абстрактное синтаксное дерево подходящее для любого, у чего есть синтаксис. Языки разработки — более конкретное множество, поэтому те операции, что создаются в обход ANTLR — имеют более строгие ограничения, чем обычный AST. При этом весь вывод уже имеет многочисленные маркировки и преобразования, из-за которых потом обработка будет проходить быстрее.
Если вы посмотрите, как например выглядит декларация переменной, то увидите, что будет что-то такое:
LANG at /ex.js[1:0-1:49]
Language: JavaScript
Children:
RAW_DECL_LOCAL at /ex.js[1:12-1:48]
Children:
NAME at /ex.js[1:12-1:33]
Children:
UNRESOLVED_ID at /ex.js[1:12-1:33]
Name: regexUnnecessaryIndex
MODIFIERS at /ex.js[1:12-1:48]
Modifiers: const
INIT at /ex.js[1:36-1:48]В будущем работать именно с такими структурами будет куда как проще, так же как и юнит-тестировать саму грамматику и всякие штуки для обработки такого сырого документа.
Я предлагаю вам все же посмотреть проект и убедится, что то, что вы сейчас говорите не позволит экономить память. Попробуйте закоментировать вот эту строку, найти файл на 130+ кб и запустить анализ с -Xmx128m. Чудеса — правда? Памяти почему-то потребляется не столько же.
PS можно свертки (такие же как в статье, а не то, что вы написали в виде правила) реализовать и с листенерами/визиторами, просто будете ловить напрямую токен FoldBlock и обрабатывать его другим способом. Но это долго и много мороки, сложно тестировать, вариант с кодом непосредственно в грамматике гораздо лучше.
Вопрос вам: сколько времени нужно вашему анализатору Positive Tech, что бы получить AST для tsserver.js? Можно приблизительно. Достаточно измерить время между началом работы начального правила и его окончания.
Без холиваров.
Холивар начали вы, употребив слово "идеальный" в заголовке. Ничего идеального не существует, тем более в сфере статического анализа, включая и наши анализаторы от "Positive Tech". Либо быстро, либо качественно.
Грамматика не станет проще, вы пытаетесь смотреть на частности, не увидев всю картину, причем даже в том участке проекта, который был раскрыт на гитхабе — уже можно увидеть причину, почему строится собственное дерево.
А я где-то спрашивал зачем строится собственное? Если вы так поняли мои слова, то извините за сумбурное изложение.
В будущем работать именно с такими структурами будет куда как проще, так же как и юнит-тестировать саму грамматику и всякие штуки для обработки такого сырого документа.
Мы для этого используем таблицу типов, которая отображается на AST. Но это тема уже для другого топика.
Я предлагаю вам все же посмотреть проект и убедится, что то, что вы сейчас говорите не позволит экономить память. Попробуйте закоментировать вот эту строку, найти файл на 130+ кб и запустить анализ с -Xmx128m. Чудеса — правда?
Позволяет — я об этом не так давно писал в компиляторном чате в Telegram.
Мы парсим PL/SQL файл в 900К строк кода (30 Мб) примерно за 12 секунд при условии, что используется быстрый SLL режим. При этом затрачивается 1 Гб оперативной памяти, 99% из которых — наше внутреннее представление UST (проверял профилировщиком). Его можно оптимизировать, но сейчас не вижу в этом особого смысла, т.к. такие файлы редкие. Т.е. все ANTLR объекты в основном отсеиваются в первом поколении, а это быстро.
OS: Microsoft Windows NT 6.2.9200.0
Config: RELEASE (no debugger)
Peak virtual/working set: 5553.0078125 / 1081.6484375 MB, 64-bit
Finish date: 02/11/2020 15:48:52
Stage: Ust
Files count: 1
Lines/chars count: 891868 / 30870339
File time ratio: 01.82%
Language time ratio: 00.62%
Tokens time ratio: 11.49%
ParseTree time ratio: 51.57%
Ust time ratio: 32.00%
Pattern time ratio: 02.50%
Time elapsed: 00:24.964Вот график CPU и Memory traffic из Process Hacker:
Сам файл выложить не могу, т.к. он, увы, проприетарный. Может дойдут потом руки сгенерировать подобный.
В случае полного LL все намного печальней — примерно 11.5 минут на парсинг, т.е. почти в 60 раз медленней, а это уже неприлично долго. Это коррелирует с вашими советами из прошлой статьи.
А 130Кб — уж извините, но ни о чем.
Вопрос вам: сколько времени нужно вашему анализатору Positive Tech, что бы получить AST для tsserver.js? Можно приблизительно. Достаточно измерить время между началом работы начального правила и его окончания.
А можно ссылку на этот файл для начала? Для парсинга JavaScript мы сейчас используем Esprima.NET — порт оригинального парсера Esprima на JavaScript. Но, боюсь, это не то, что вас интересует, т.к. работает он побыстрее ANTLR, правда не обладает такой же гибкостью, поддерживает не все синтаксические конструкции.
Когда-то использовали JavaScript грамматику, но натыкались как раз на файлы, где происходило переключение SLL -> LL, и парсинг сильно замедлялся. Примерно по минуте на 100Кб+. Да и то это не особо было критично, т.к. остальные стадии ядра работали не особо быстро. Возможно в будущем вернемся на ANTLR с учетом накопленного опыта.
А 130Кб — уж извините, но ни о чем.
Зависит от языка. Для PLSQL — действительно ни о чем, но в случае минифицированного javascript — это очень много. В распакованном виде будет 2 мб исходников с очень нетривиальной логикой внутри.
Видимо я неясно выразился.
А можно ссылку на этот файл для начала? Для парсинга JavaScript мы сейчас используем Esprima.NET — порт оригинального парсера Esprima на JavaScript. Но, боюсь, это не то, что вас интересует, т.к. работает он побыстрее ANTLR, правда не обладает такой же гибкостью, поддерживает не все синтаксические конструкции.
Нет смысла сравнивать тогда универсальные решения и специализированные. Написать под конкретный язык можно и без ANTLR.
Когда-то использовали JavaScript грамматику, но натыкались как раз на файлы, где происходило переключение SLL -> LL,
Переключение через эксепшн? Значит вы грамматику неправильно готовили. Впрочем я ее видел. Использовать в проде ее действительно нельзя. Она просто не работает, большая часть фичей стандарта не поддерживается. Надеятся на простые случаи — бессмысленно.
В общем советую вам отказываться от LL грамматик, они не могут работать быстро по определению.
Насчет производительности — согласен, можно оптимизировать. С другой стороны, зачем использовать ANTLR 4, если ради парсера нужно сделать столько телодвижений (как у вас в JSParser.g4)? Можно же обойтись ANTLR 3 или вообще свой парсер написать. Ради левой рекурсии?
Насчет поддержки фичей — откуда такая уверенность? Покрывать все случаи — бессмысленно, т.к. нужно те, которые как-то влияют на анализ. Например, обработка курсоров (отслеживание незакрытых). Также там много тестовых файлов, на которых парсинг производится без ошибок.
Много — это когда берешь базу из 17 тысяч файлов на JS — различные библиотеки, которые можно скачать всего лишь создав пустой проект react, а дальше получить только десяток ошибочных файлов. При этом ошибки из-за того, что какой-то умник пишет дженерики для массивов, которые в JS не поддерживаются, потому что файл препроцессируется какой-то либой.
Вот это тесты, а предложенные вами несколько файлов не позволят вам провести анализ реальных проектов.
ANTLR4 работает быстрее, чем ANTLR3.
Зачем писать свой парсер, если мне нужно универсальное решение, которое не потребует на каждый язык тратить килотонны времени?
Нужно такое решение, которое с минимальными затратами после написания грамматики даст возможность использовать весь остальной инструментарий сканера с минимальным тюнингом под специфику конкретного языка.
ANTLR4 работает быстрее, чем ANTLR3.
За счет чего? Если ли тесты производительности?
Нужно такое решение, которое с минимальными затратами после написания грамматики даст возможность использовать весь остальной инструментарий сканера с минимальным тюнингом под специфику конкретного языка.
А какие еще языки поддерживаете, помимо JavaScript?
За счет чего? Если ли тесты производительности?
Я еще с ANTLR 2.7.7 разработки делал, будучи студентом. И третью версию гонял. С ними очень много мороки и проблем, даже если они быстрее (что вряд ли), то смысла их использовать все равно нет — фичи не поддерживаются необходимые мне.
А какие еще языки поддерживаете, помимо JavaScript?
TypeScript, через него массу метаданных можно собрать, которые очень нужны в JavaScript. По сути сейчас пытаться делать SAST для JavaScript, не делая параллельно поддержку для TypeScript — все равно что выкидывать деньги на ветер.
В MVP еще будет какой-нибудь язык запросов для БД, MySql или Postgres. Пока не брался. Нужно довести с первыми двумя до нужной кондиции и уже после браться за запросы.
Кстати TypeScript парсер тоже будет публиковаться, потому что на нем лучше всего показывать особенности модели R, только не скоро это будет и по частям.
Много — это когда берешь базу из 17 тысяч файлов на JS — различные библиотеки, которые можно скачать всего лишь создав пустой проект react, а дальше получить только десяток ошибочных файлов.
Кстати, а имеет ли смысл анализировать все минифицированные библиотеки? По крайней мере их можно проанализировать один раз, а дальше использовать закешированный результат.
Нужно такое решение, которое с минимальными затратами после написания грамматики даст возможность использовать весь остальной инструментарий сканера с минимальным тюнингом под специфику конкретного языка.
Я рад, что у вас хватает времени на разработку оптимизированной грамматики. К сожалению, порой нет времени и на это.
Кстати, а имеет ли смысл анализировать все минифицированные библиотеки? По крайней мере их можно проанализировать один раз, а дальше использовать закешированный результат.
Это не всегда возможно, и есть требование анализировать все зависимости на каждом анализе. Версии могут отличаться, даже если разница в одной функции — может повлиять на результат. Поэтому работать парсер должен на всем, а в случае минифицированных библиотек — обязательно, так как там набито куча всего и из-за одной ошибки можно много чего потерять.
Я рад, что у вас хватает времени на разработку оптимизированной грамматики. К сожалению, порой нет времени и на это.
Суммарно на грамматики JS и TS ушло примерно 80 человекочасов — не очень много. Если пишешь код внутри грамматики и можешь ее юнит-тестировать — сильно ускоряет процесс разработки и анализа.
Это всего лишь вопрос инструментария, который вы написали для себя (потому что с формальными грамматиками мало кто работает — соответственно все что есть — кактус). А так же понимания функционирования библиотек, которые вы используете.
Думаю, тут больше уместен тег scala, чем java. Все-таки код в статье на скале, а не на яве (а исходники самого ANTLR-а не в счет).
Без холиваров.
Ну человек же нормальный вопрос задал, меня тоже это интересует в превую очередь… а не сколько оно там памяти потребляет и как быстро бегает.
а на сколько оно там памяти потребляет и как быстро бегает.
Парсер в 8 потоков все файлы меньше 10 кб парсит при 128 мб хипа, можно ужать до 64 мб, работать будет, но кроме парсера есть еще штуки, которые память по умолчанию щадить не могут.
Если речь про большие файлы, то при однопоточном анализе, минифицированный вендор.js на 100-130 кб можно запихнуть в те же рамки, просто сборщик мусора будет работать больше.
По быстродействию скажу, что текущие универсальные решения (не специализированные, как например в браузере), будут работать минимум в 2 раза медленнее, чем rscan, во всяком случае уж точно быстрее Positive Tech =) Сложно быть медленее…
В целом планирую, что 90% проектов будут taint-анализироваться с хипом в 1 гб, этого должно быть достаточно, да и разработчику будет удобнее пользоваться непосредственно в процессе разработки, и видеть проблемные места. Насколько мне известно, уж 4 гб ОЗУ у разработчиков как правило есть, значит и для SAST место найдется. Для всяких мелкосервисов и онлайн-магазов самое то!
А почему вас интересуют такие вопросы? Спиён? =)
Все же лучше задавать вопросы по теме статьи, мы же не rscan в целом обсуждаем сейчас, а конкретно оптимизацию ANTLR. Есть ли у вас по этой теме вопросы?
Если речь про большие файлы, то при однопоточном анализе, минифицированный вендор.js на 100-130 кб можно запихнуть в те же рамки, просто сборщик мусора будет работать больше.
Маленькие файлы =)
По быстродействию скажу, что текущие универсальные решения (не специализированные, как например в браузере), будут работать минимум в 2 раза медленнее, чем rscan, во всяком случае уж точно быстрее Positive Tech =) Сложно быть медленее…
В два раза медленней — это не на порядок. Ну и не всегда критично: если скан не в реальном времени и абсолютные цифры невелики, то не так важно: будет скан на CI занимать 30 секунд или минуту. Если в реальном времени, то да, производительность крайне важна. Кстати, этап конвертации в универсальное UST у нас почти ничего не занимает в относительных цифрах. А какой язык Positive Tech вы имеете в виду и как вы замерили разницу? Опять Java?
да и разработчику будет удобнее пользоваться непосредственно в процессе разработки, и видеть проблемные места.
Поддерживается ли у вас межпроцедурный и межфайловый taint анализ?
Маленькие файлы =)
Зависит от языка программирования. Вы бы еще сравнили 100 кб ассемблерного кода и 100 кб С++.
В два раза медленней — это не на порядок.
Написано же — минимум. И я не делал оптимизаций специальных для грамматики, процесса работы и прочего.
По памяти гарантированно на порядок лучше, так как вы же сами писали, что требует 1 ГБ ОЗУ для 100 кб вашего кода. Сравните это с 128 мб. Причем я еще и выгружать данные на диск в процессе анализа могу :D В том числе в процессе резолва — маппинга типов на исходный код.
Поддерживается ли у вас межпроцедурный и межфайловый taint анализ?
Модель R для того и разрабатывалась, вернее это минимум, что должно быть. Больше говорить не стану. Межпроцедурным и межфайловым анализом как раз 5 лет и занимался, так что с этим проблем точно не будет =) Цель покрупнее идет, именно поэтому все что отвечает за SAST должно быть "идеальным". Ресурсы нужны для других целей.
Зависит от языка программирования. Вы бы еще сравнили 100 кб ассемблерного кода и 100 кб С++.
Между PL/SQL и JavaScript намного больше общего, чем ассемблером и C++. В PL/SQL есть императивное программирование и даже ООП. Кроме того, там много ключевых слов и обширный синтаксис для запросов. Думаю для JavaScript представление будет занимать ненамного больше, если вообще больше.
Написано же — минимум. И я не делал оптимизаций специальных для грамматики, процесса работы и прочего.
Ну почему — FoldToken как минимум такой оптимизацией и является. Я спрашивал к тому, что у нас есть разные ядра, которые используют разные алгоритмы (символьное исполнение и taint без учета условий). Разумеется время и качество будет разниться, странно пихать все это в одну кучу.
По памяти гарантированно на порядок лучше, так как вы же сами писали, что требует 1 ГБ ОЗУ для 100 кб вашего кода. Сравните это с 128 мб.
Как бы выше я писал для 30 Мб кода, это в 300 раз больше. Ваше JS представление в этом случае сколько будет в памяти занимать?
Причем я еще и выгружать данные на диск в процессе анализа могу :D В том числе в процессе резолва — маппинга типов на исходный код.
Это скоро появится и у нас.
Не могу ничего сказать по поводу PLSQL, потому что не занимался им и пока на него нет времени.
То что известно — синтаксис у него простой, в большинстве своем работать нужно именно с запросами, а у них не бывает перестановок или чего-то в таком духе, жесткий формат.
То что есть возможность писать хранимые процедуры — это отдельная тема и их очень легко парсить отдельно. Или у вас есть процедуры на 1000 строк?
Как бы выше я писал для 30 Мб кода, это в 300 раз больше. Ваше JS представление в этом случае сколько будет в памяти занимать?
8 мб умещается в 512 мб хипа без проблем — как раз tsserver.js.
Грамматика ANTLR для JavaScript отличается по сложности в разы для PLSQL и сравнивать их бессмысленно.
Я уже не говорю о том, что для PLSQL можно сделать разбиение на небольшие куски кода и обработку их в ANTLR вообще параллельно. Для JS такое не всегда возможно сделать.
FoldToken как минимум такой оптимизацией и является
Есть другие оптимизации для работы грамматики и ANTLR, а так же генерации объектов, уменьшения потребления ресурсов объектами парсера и т.д.
Есть еще способы уменьшения lookahead ANTLR. Причем они же очевидны! Неужели не умеете делить входной файл на независимые блоки и парсить отдельно?
function a(){}
function b(){}
Такие штуки можно парсить отдельно и скорость будет выше, другой вопрос, что сделать такое разделение корректно с точки зрения синтаксиса будет непросто =)
Из ANTLR можно еще 30-40% производительности выжать без злобных хаков, но влоб кидать этой библиотеке мегабайты исходных кодов — бред.
Кстати, а что вы думаете по поводу замены токенов по-умолчанию на собственную реализацию, которая хранит локацию строки в тексте (span), вместо самой строки, чтобы аллоцированные объекты занимали меньше места в памяти? У нас для этого используется LightToken и соответствующей инфраструктуры. У вас это особенно актуально с учетом сверток. Хотя наверное и так реализовано в RScanToken.scala.
Идеальный SAST. Парсер