Static Analysis of Go Maps
https://doi.org/10.15514/ISPRAS-2024-36(3)-2
Abstract
The paper describes static analysis of map in the Go language for dereferencing a null pointer when extracting a key from a map. The work has been done within the Svace static analyzer. We begin with introducing Svace intermediate representation and algorithms. Then we describe the IR changes needed for modeling Go maps and their semantics. We explain how intraprocedural analysis is performed and how the null dereference detector works. Then we proceed with a summary-based interprocedural analysis. We show evaluation results on a wide range of open source projects.
About the Authors
Daniil Nikolaevich SUBBOTIN
Ivannikov Institute for System Programming of the RAS
Moscow State University
Russian Federation
Russian Federation
ISP RAS researcher, graduate student at the Faculty of Computational Mathematics and Cybernetics of Moscow State University. Research interests: compiler technologies, static analysis, Go and Python languages, universal AST.
Alexey Evgenevich BORODIN
Ivannikov Institute for System Programming of the RAS
Russian Federation
Russian Federation
Cand. Sci. (Phys.-Math.), researcher. Research interests: static analysis for finding errors in source code.
Varvara Viktorovna DVORTSOVA
Ivannikov Institute for System Programming of the RAS
Moscow State University
Russian Federation
Russian Federation
ISP RAS researcher, graduate student at the Faculty of Computational Mathematics and Cybernetics of Moscow State University. Research interests: compiler technologies, static analysis, Golang analysis.
References
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.
Review
For citations:
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
Email this article 