Статический анализ на основе обобщённого абстрактного синтаксического дерева

В работе описывается универсальное представление для абстрактного синтаксического дерева (АСД), подходящее для статического анализа нескольких языков программирования. Предлагаемая схема анализа состоит в сохранении промежуточного представления в виде обобщенного АСД из компиляторов соответствующих языков и последующим анализом сохраненных деревьев. Мы реализовали такое представление для Java, Kotlin и Python. В анализаторе обобщенного АСД реализовано 27 детекторов. Мы описываем сущности предлагаемого представления, особенности его реализации для поддержанных языков. Приводим экспериментальные результаты скорости и качества анализа, а также сравнения анализа на обобщенном АСД с анализом, выполненным ранее на АСД конкретного компилятора. В итоге подход демонстрирует некоторое ухудшение скорости анализа, но позволяет разделить построение АСД для анализа и реализацию детекторов, что упрощает разработку АСД-детекторов в случае, когда количество поддерживаемых анализатором языков становится значительным.

1. В. П. Иванников, А. А. Белеванцев, А. Е. Бородин, В. Н. Игнатьев, Д. М. Журихин, А. И. Аветисян и М. И. Леонов. Статический анализатор Svace для поиска дефектов в исходном коде программ. Труды ИСП РАН , 26(1):231—250, 2014. DOI: 10.15514/ISPRAS-2014-26(1)-7.

2. A. Belevantsev, A. Borodin, I. Dudina, V. Ignatiev, A. Izbyshev, S. Polyakov, E. Velesevich and D. Zhurikhin. Design and development of Svace static analyzers. In 2018 Ivannikov Memorial Workshop (IVMEM), pp.3—9. IEEE, 2018.

3. A.E. Borodin and A. A. Belevantsev. A static analysis tool Svace as a collection of analyzers with various complexity levels. Proceedings of the Institute for System Programming of the RAS, 27(6):111—134, 2015.

4. Clang static analyzer. URL: https://clang-analyzer.llvm.org (дата обращения 02.10.2023).

5. V. Afanasyev, S. Polyakov, A. Borodin and A. Belevantsev. Kotlin from the point of view of static analysis developer. Programming and Computer Software, 49(7):549—558, 2023. DOI: 10.1134/S0361768823070022.

6. Compiler tree api. Английский. URL: https://docs.oracle.com/javase/8/docs/jdk/api/javac/tree/index.html (дата обращения 18.09.2023).

7. Intellij platform plugin sdk. Psi elements. Английский. URL: https://plugins.jetbrains.com/docs/intellij/psi-elements.html (дата обращения 18.09.2023).

8. Ast — abstract syntax trees. Английский. URL: https://docs.python.org/3/library/ast.html (дата обращения 18.09.2023).

9. A. Belevantsev, A. Izbyshev and D. Zhurikhin. Monitoring program builds for svace static analyzer. System administrator, (7-8):135—139, 2017.

10. Treesitter. Introduction. Английский. URL: https://tree-sitter.github.io/tree-sitter/ (дата обращения 18.12.2023).

11. Python developer’s guide. Compiler design. Английский. URL: https://devguide.python.org/internals/compiler/ (дата обращения 28.09.2023).

12. Execution model. Английский. URL: https://docs.python.org/3.8/reference/executionmodel.html#execution-model (дата обращения 13.10.2023).

13. The global statement. Английский. URL: https://docs.python.org/3.8/reference/simple_stmts.html#the-global-statement (дата обращения 27.10.2023).

14. The nonlocal statement. Английский. URL: https://docs.python.org/3.8/reference/simple_stmts.html#the-nonlocal-statement (дата обращения 27.10.2023).

15. D. Strein, H. Kratz и W. Lowe. Cross-language program analysis and refactoring. In 2006 Sixth IEEE International Workshop on Source Code Analysis and Manipulation, pp 207—216. IEEE, 2006.

16. R.-H. Pfeiffer и A. Wasowski. Texmo: a multi-language development environment. In European Conference on Modelling Foundations and Applications, pp 178—193. Springer, 2012.

17. Uast – unified abstract syntax tree. Intellij platform plugin sdk. Английский. URL: https://plugins.jetbrains.com/docs/intellij/uast.html (дата обращения 03.10.2023).

18. I. D. Baxter. Dms: program transformations for practical scalable software evolution. In Proceedings of the International Workshop on Principles of Software Evolution, pp 48—51, 2002.

19. A. Raza, G. Vogel и E. Plodereder. Bauhaus–a tool suite for program analysis and reverse engineering. In Reliable Software Technologies–Ada-Europe 2006: 11th Ada-Europe International Conference on Reliable Software Technologies, Porto, Portugal, June 5-9, 2006. Proceedings 11, pp 71—82. Springer, 2006.

20. М. В. Зубов, А. Н. Пустыгин и Е. В. Старцев. Применение универсальных промежуточных представлений для статического анализа исходного программного кода. Доклады Томского государственного университета систем управления и радиоэлектроники , (1 (27)):64—68, 2013.

21. С. В. Сыромятников. Декларативный интерфейс поиска дефектов по синтаксическим деревьям: язык kast. Труды Института системного программирования РАН , 20:51—68, 2011.

22. Н. Л. Луговской и С. В. Сыромятников. Применение языка kast для преобразования исходного кода и автоматического исправления дефектов. Труды Института системного программирования РАН , 25:51—66, 2013.

23. D. Harmim, V. Marcin и O. Pavela. Scalable static analysis using Facebook Infer. I, VI-B, 2019.

24. D. Harmim. Advanced static analysis of atomicity in concurrent programs through Facebook Infer. Proceedings of the Excel@ FIT’21.

25. Ast language (al). Английский. URL: https://fbinfer.com/docs/checker-linters/ (дата обращения 02.10.2023.