Pathfinder: software static analyzer based on solving the graph reachability problem with CF constraints

The method and tool for detecting characteristic patterns on graph-structured intermediate representations of programs by solving the reachability problem with context-free (CF) constraints are considered. The areas of applicability of the study are: static and hybrid analysis of code, software execution traces and call-graphs analysis. Article presents the key points of methodology for studying program graphs, working out the architectural and functional components of the analysis tool. An experimental comparison of basic algorithms for checking CF reachability (CFL-R) on graphs with different connectivity is presented. Proof-of-concept is carried out by via detecting the specific memory access patterns during experiments on the developed CFL-R analysis tool. The work also highlights further areas of research, testing and improvement of the presented method and tool.