Package com.kcsl.paths.common

Class PathFactory

  • public class PathFactory
extends java.lang.Object
    This is an Atlas implementation of a path counting algorithm for graphs without enumeration. It will count all possible paths from roots to leaves in a directed graph. There are no constraints on the graph apart from it being directed graph. It runs in O(V+E) time (employs a bottom-up BFS traversal).
    Author:
    Payas Awadhutkar - Core Implementation, Depth First variants, Suresh Kothari - Conceptual oversight, Sharwan Ram - Interprocedural Counting Implementation, Ben Holland - Documentation, Breadth First variants

    • Constructor Summary

      Constructors 
      Constructor Description
      PathFactory()  

    • Method Summary

      Modifier and Type Method Description
      static java.util.List<java.lang.String> computePathExpressions​(com.ensoftcorp.atlas.core.db.graph.Node function)  
      static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countIntermediatePaths​(com.ensoftcorp.atlas.core.db.graph.Node function)
      Counts the paths in a given function's control flow graph ignoring exceptional control flows and returns the intermediate path results.
      static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countIntermediatePaths​(com.ensoftcorp.atlas.core.db.graph.Node function, boolean includeExceptionControlFlows)
      Counts the paths in a given function's control flow graph and returns the intermediate path results.
      static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countIntermediatePaths​(com.ensoftcorp.atlas.core.query.Q graph)
      Counts the number of paths for the specified software graph and returns the intermediate path results.
      java.math.BigInteger countInterProceduralFunctionPaths​(com.ensoftcorp.atlas.core.db.graph.Node function, boolean includeExceptionControlFlows)
      Calculates the number of inter-procedural paths within a given function
      static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countInterProceduralPaths​(com.ensoftcorp.atlas.core.db.graph.Node function, boolean includeExceptionControlFlows)  
      static java.math.BigInteger countInterProceduralPathsInAFunction​(com.ensoftcorp.atlas.core.db.graph.Node function, boolean includeExceptionControlFlows)  
      static java.math.BigInteger countInterProceduralPathsInFunctions​(com.ensoftcorp.atlas.core.query.Q functions)  
      java.math.BigInteger countIntraProceduralFunctionPaths​(com.ensoftcorp.atlas.core.db.graph.Node function, boolean includeExceptionControlFlows)
      Calculates the number of intra-procedural paths within a given function
      static java.math.BigInteger countPaths​(com.ensoftcorp.atlas.core.db.graph.Node function)
      Counts the paths in a given function's control flow graph.
      static java.math.BigInteger countPaths​(com.ensoftcorp.atlas.core.db.graph.Node function, boolean includeExceptionControlFlows)
      Counts the paths in a given function's control flow graph.
      static java.math.BigInteger countPaths​(com.ensoftcorp.atlas.core.query.Q graph)
      Counts for the specified software graph.
      java.math.BigInteger countStructuredGraphPaths​(com.ensoftcorp.atlas.core.query.Q graph)
      Counts the paths in a given control flow based graph including paths through loops Note that the graph does not have to specifically be a control flow graph, but the control flow back edges should be marked as XCSG.ControlFlowBackEdge.
      static void summarizeApplicationPaths​(com.ensoftcorp.atlas.core.query.Q app, boolean includeExceptionControlFlows, java.io.File outputFile)
      Outputs a CSV file of application function paths.
      static void summarizeApplicationPaths​(java.io.File outputFile)
      Outputs a CSV file of application function paths.

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • PathFactory

        public PathFactory()

    • Method Detail

      • summarizeApplicationPaths

        public static void summarizeApplicationPaths​(java.io.File outputFile)
        Outputs a CSV file of application function paths.
        Parameters:
        app -
        filePath -

      • summarizeApplicationPaths

        public static void summarizeApplicationPaths​(com.ensoftcorp.atlas.core.query.Q app,
                                             boolean includeExceptionControlFlows,
                                             java.io.File outputFile)
        Outputs a CSV file of application function paths.
        Parameters:
        app - Defines the functions that should be included in the summary
        includeExceptionControlFlows - If true exception control flow graph edges will be included in the path counts
        outputFile -

      • countPaths

        public static java.math.BigInteger countPaths​(com.ensoftcorp.atlas.core.query.Q graph)
        Counts for the specified software graph. The graph must be a structured program graph with control flow back edges labeled as XCSG.ControlFlowBackEdge
        Returns:

      • countIntermediatePaths

        public static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countIntermediatePaths​(com.ensoftcorp.atlas.core.query.Q graph)
        Counts the number of paths for the specified software graph and returns the intermediate path results. The graph must be a structured program graph with control flow back edges labeled as XCSG.ControlFlowBackEdge
        Parameters:
        input -
        Returns:

      • countPaths

        public static java.math.BigInteger countPaths​(com.ensoftcorp.atlas.core.db.graph.Node function)
        Counts the paths in a given function's control flow graph. Exceptional paths are ignored.
        Parameters:
        function -
        Returns:

      • countPaths

        public static java.math.BigInteger countPaths​(com.ensoftcorp.atlas.core.db.graph.Node function,
                                              boolean includeExceptionControlFlows)
        Counts the paths in a given function's control flow graph.
        Parameters:
        function -
        includeExceptionControlFlows - If true exception control flow graph edges will be included in the path counts
        Returns:

      • countIntermediatePaths

        public static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countIntermediatePaths​(com.ensoftcorp.atlas.core.db.graph.Node function)
        Counts the paths in a given function's control flow graph ignoring exceptional control flows and returns the intermediate path results.
        Parameters:
        function -
        Returns:

      • countIntermediatePaths

        public static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countIntermediatePaths​(com.ensoftcorp.atlas.core.db.graph.Node function,
                                                                                                                       boolean includeExceptionControlFlows)
        Counts the paths in a given function's control flow graph and returns the intermediate path results.
        Parameters:
        function -
        includeExceptionControlFlows - If true exception control flow graph edges will be included in the path counts
        Returns:

      • countIntraProceduralFunctionPaths

        public java.math.BigInteger countIntraProceduralFunctionPaths​(com.ensoftcorp.atlas.core.db.graph.Node function,
                                                              boolean includeExceptionControlFlows)
        Calculates the number of intra-procedural paths within a given function
        Parameters:
        function -
        includeExceptionControlFlows - If true exception control flow graph edges will be included in the path counts
        Returns:

      • countStructuredGraphPaths

        public java.math.BigInteger countStructuredGraphPaths​(com.ensoftcorp.atlas.core.query.Q graph)
        Counts the paths in a given control flow based graph including paths through loops Note that the graph does not have to specifically be a control flow graph, but the control flow back edges should be marked as XCSG.ControlFlowBackEdge. The graph must be a structured graph.
        Parameters:
        graph -
        Returns:

      • countInterProceduralPaths

        public static java.util.Map<com.ensoftcorp.atlas.core.db.graph.Node,​java.math.BigInteger> countInterProceduralPaths​(com.ensoftcorp.atlas.core.db.graph.Node function,
                                                                                                                          boolean includeExceptionControlFlows)

      • countInterProceduralPathsInFunctions

        public static java.math.BigInteger countInterProceduralPathsInFunctions​(com.ensoftcorp.atlas.core.query.Q functions)

      • countInterProceduralFunctionPaths

        public java.math.BigInteger countInterProceduralFunctionPaths​(com.ensoftcorp.atlas.core.db.graph.Node function,
                                                              boolean includeExceptionControlFlows)
        Calculates the number of inter-procedural paths within a given function
        Parameters:
        function -
        includeExceptionControlFlows - If true exception control flow graph edges will be included in the path counts
        Returns:

      • countInterProceduralPathsInAFunction

        public static java.math.BigInteger countInterProceduralPathsInAFunction​(com.ensoftcorp.atlas.core.db.graph.Node function,
                                                                        boolean includeExceptionControlFlows)

      • computePathExpressions

        public static java.util.List<java.lang.String> computePathExpressions​(com.ensoftcorp.atlas.core.db.graph.Node function)