The goal of path-sensitive analysis is to achieve accuracy by accounting precisely for the execution behavior along each path of a control flow graph (CFG). A practical adoption of PSA is hampered by two roadblocks: (a) the exponential growth of the number of CFG paths, and (b) the exponential complexity of a path feasibility check. We introduce projected control graph (PCG) as an optimal mathematical abstraction to address these roadblocks.

The PCG follows from the simple observation that for any given analysis problem, the number of distinct relevant execution behaviors may be much smaller than the number of CFG paths. The PCG is a projection of the CFG to retain only the relevant execution behaviors and elide duplicate paths with identical execution behavior. A mathematical definition of PCG and an efficient algorithm to transform CFG to PCG are implemented in this utility.

Website: https://ensoftcorp.github.io/pcg-toolbox

The PCG Toolbox project supports the following.

• Smart View: Select events to create a PCG within a function
• PCG Builder: Select events across multiple functions to create an interprocedural PCG
• PCG and IPCG factory classes to support third party analysis