Статический анализ ассоциативных массивов в Go
https://doi.org/10.15514/ISPRAS-2024-36(3)-2
Аннотация
В статье описывается статический анализ ассоциативных массивов в языке Go для поиска разыменования нулевого указателя при извлечении ключа. Кратко вводятся внутреннее представление и алгоритмы анализатора Svace, в рамках которого выполнялась работа, затем описываются необходимые изменения внутреннего представления, моделирование семантики ассоциативных массивов, как для внутрипроцедурного, так и для межпроцедурного анализа на основе резюме, предлагается детектор поиска разыменований нулевого указателя. Приводятся экспериментальные результаты на широком круге открытых проектов.
Об авторах
Даниил Николаевич СУББОТИН
Институт системного программирования им. В.П. Иванникова РАН
Московский государственный университет им. М.В. Ломоносова
Россия
Россия
Сотрудник ИСП РАН, студент магистратуры факультета ВМК МГУ. Сфера научных интересов: компиляторные технологии, статический анализ, анализ языков Go и Python, универсальное абстрактное синтаксическое дерево.
Алексей Евгеньевич БОРОДИН
Институт системного программирования им. В.П. Иванникова РАН
Россия
Россия
Кандидат физико-математических наук, старший научный сотрудник ИСП РАН. Сфера научных интересов: статический анализ исходного кода программ для поиска ошибок.
Варвара Викторовна ДВОРЦОВА
Институт системного программирования им. В.П. Иванникова РАН
Московский государственный университет им. М.В. Ломоносова
Россия
Россия
Сотрудник ИСП РАН, студентка магистратуры факультета ВМК МГУ. Сфера научных интересов: компиляторные технологии, статический анализ, анализ Golang.
Список литературы
1. A. Belevantsev, A. Borodin, I. Dudina, V. Ignatiev, A. Izbyshev, S. Polyakov, D. Zhurikhin. Design and development of Svace static analyzers. In 2018 Ivannikov Memorial Workshop (IVMEM):3—9, 2018.
2. A. Borodin, V. Dvortsova, S. Vartanov и A. Volkov. Static analyzer for go. В 2021 Ivannikov Ispras Open Conference (ISPRAS), страницы 17—25. IEEE, 2021.
3. A. Borodin, A. Goremykin, S. Vartanov и A. Belevancev. Searching for tainted vulnerabilities in static analysis tool svace. Proceedings of the Institute for System Programming of the RAS, 33(1):7—32, 2021.
4. Ssadump: инструмент для вывода и интерпретации формы ssa программ на go. https://pkg.go.dev/golang.org/x/tools@v0.19.0/cmd/ssadump. Дата обращения: 2024-02-01.
5. R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman и F. K. Zadeck. An efficient method of computing static single assignment form. В Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, страницы 25—35, 1989.
6. Пакет ssa. https://godoc.org/golang.org/x/tools/go/ssa. Дата обращения: 2024-02-01.
7. А. Е. Бородин и И. А. Дудина. Внутрипроцедурный анализ для поиска ошибок на основе символьного выполнения. Труды ИСП РАН, 1:3—4, 2020.
8. V. B. Livshits и M. S. Lam. Tracking pointers with path and context sensitivity for bug detection in c programs. В Proceedings of the 9th European software engineering conference held jointly with 11th ACM SIGSOFT international symposium on Foundations of software engineering, страницы 317—326, 2003.
9. R. Ghiya и L. J. Hendren. Is it a tree, a dag, or a cyclic graph? a shape analysis for heap-directed pointers in c. В Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, страницы 1—15, 1996.
10. U. P. Khedker, A. Sanyal и A. Karkare. Heap reference analysis using access graphs. ACM Transactions on Programming Languages and Systems (TOPLAS), 30(1):1—es, 2007.
11. E. Bodden. The secret sauce in efficient and precise static analysis: the beauty of distributive, summary-based static analyses (and how to master them). В Companion Proceedings for the ISSTA/ECOOP 2018 Workshops, страницы 85—93, 2018.
12. А. Е. Бородин. Межпроцедурный контекстно-чувствительный статический анализ для поиска ошибок в исходном коде программ на языках Си и Си++. Дис.канд.физ.-мат.наук, Москва, 2016 г.
13. N. Malyshev, I. Dudina, D. Kutz, A. Novikov и S. Vartanov. Smt solvers in application to static and dynamic symbolic execution: a case study. В 2019 Ivannikov Ispras Open Conference (ISPRAS), страницы 9—15. IEEE, 2019.
14. L. De Moura и N. Bjørner. Z3: an efficient smt solver, 2008.
15. Tidb open-source distributed sql database. https://github.com/pingcap/tidb. Дата обращения::2024-02-10
16. F. Alberti, S. Ghilardi и N. Sharygina. Decision procedures for flat array properties. Journal of Automated Reasoning, 54:327—352, 2015.
17. Nilaway инструмент статического анализа. https://github.com/uber-go/nilaway. Дата обращения: 2024-01-10.
18. Nilness инструмент статического анализа. https://pkg.go.dev/ golang.org/x/tools/go/analysis/passes/nilness. Дата обращения: 2024-01-10.
19. Go vet main page. https://golang.org/cmd/vet/. Дата обращения: 2023-10-01.
20. Golang.org/x/tools модуль для статического анализа. https://pkg.go.dev/golang.org/x/tools. Дата обращения: 2024-02-10.
21. W. G. Biktimirov, V. N. Ignatyev и M. V. Belyaev. Improving the accuracy of library function modeling in the static analyzer. В 2023 Ivannikov Ispras Open Conference (ISPRAS). IEEE.
Рецензия
Для цитирования:
СУББОТИН Д.Н., БОРОДИН А.Е., ДВОРЦОВА В.В. Статический анализ ассоциативных массивов в Go. Труды Института системного программирования РАН. 2024;36(3):21-34. https://doi.org/10.15514/ISPRAS-2024-36(3)-2
For citation:
SUBBOTIN D.N., BORODIN A.E., DVORTSOVA V.V. Static Analysis of Go Maps. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2024;36(3):21-34. (In Russ.) https://doi.org/10.15514/ISPRAS-2024-36(3)-2
Послать статью по эл. почте 