Pathfinder: статический анализатор программ на базе решения задач достижимости на графахв КС-ограничениях
Автор: Ефанов Н. Н., Федоров А. Р., Шамбер Э. В., Щербаков А. А., Елесина А. П.
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика и управление
Статья в выпуске: 4 (52) т.13, 2021 года.
Бесплатный доступ
Рассматривается способ и инструмент детектирования характерных паттернов на графо-структурированных промежуточных представлениях программ посредством решения задачи достижимости с контекстно-свободными (КС) ограничениями. Областями применимости исследования являются статический и гибридный анализ кода, анализ трасс исполнения ПО, графов вызовов. Статья представляет ключевые моменты методики исследования графов программ, проработки архитектурной и функциональной составляющих инструмента анализа. Представлено экспериментальное сравнение базовых алгоритмов проверки КС-достижимости на графах различной связности. Проверка концепции производится на примере детектирования специфической ситуации в работе с массивом данных посредством проведения экспериментов на разработанном программном комплексе. В работе также освещены дальнейшие направления исследования, тестирования и доработки представленного способа и инструмента.
Алгоритмы на графах, контекстно-свободная достижимость, формальные языки, анализ программного обеспечения
Короткий адрес: https://sciup.org/142231496
IDR: 142231496 | DOI: 10.53815/20726759_2021_13_4_14
Список литературы Pathfinder: статический анализатор программ на базе решения задач достижимости на графахв КС-ограничениях
- Хопкрофт Д., Momeanu Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. Санкт-Петербург : Вильяме, 2008.
- Lu Y., Shang L., Xie X., Xue J. An incremental points-to analysis with CFL-Reachabilitv // Proceedings of the 22nd international conference on Compiler Construction (CC'13). Berlin : Springer-Verlag, 2013. P. 61-81.
- Steensgaard B. Points-to analysis in almost linear time // Symposium on Principles of Programming Languages (POPL). New York : ACM, 1996. P. 32-41.
- Hollingum N., Scholz B. Cauliflower: a Solver Generator Tool for Context-Free Language Reachability // 21st International Conference on Logic for Programming, Artificial Intelligence and Reasoning. 2017. P. 171-180.
- Tang H., Wang D., Xiong Y., Zhang L., Wang X., Zhang L. Conditional Dvck-CFL Reachability Analysis for Complete and Efficient Library Summarization // Programming Languages and Systems, ESOP 2017. Berlin : Springer, 2017.
- Yuan H., Eugster P. An efficient algorithm for solving the dvck-cfl reachability problem on trees // Programming Languages and Systems, ESOP 2009. Berlin : Springer, 2009. P. 175-189.
- Zhang Q., Lyu M.R., Yuan H., Su Z. Fast algorithms for dvck-cfl reachability with applications to alias analysis // Proceedings of the 34th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI '13. New York : ACM, 2013. P. 435-446.
- Jin R., Hong H., Wang H., Ruan N., Xiang Y. Computing label-constraint reachability in graph databases // Proceedings of the 2010 ACM SIGMOD International Conference on Management of data (SIGMOD TO). New York : ACM, 2010. P. 123-134.
- Dolev D., Even S., Karp R.M. On the security of ping-pong protocols // Information and Control. 1982. P. 57-68.
- Rehof J., Fahndrich M. Type-base flow analysis: from polymorphic subtvping to CFL-reachabilitv // Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '01). New York : ACM, 2001. P. 54-66.
- Wang K., Hussain A., Zuo Z., Xu G., Amiri Sani A. Graspan: A Single-machine Disk-based Graph System for Interprocedural Static Analyses of Large-scale Systems Code // ASPLOS '17. ACM, 2017. P. 389-404.
- CoFRA: Inter-procedural Code Static Analyzer. JetBrains-Research Repository, 2019. https: / / github .com / JetBrains-Research / CoFRA
- Pathfinder: CFL-R Static Software Analysis Tool. MIPT-CS Github Repository, 2021. https : //github .com/mipt-cs/pathfinder
- GCC GIMPLE Intermediate Representation / GNU Compiler Collection Manual, 2021. https://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html
- Chaudhuri S. Subcubic algorithms for recursive state machines // Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL '08). New York : ACM, 2008. P. 159-169.
