Writing an IFDS Analysis

In order to solve a data-flow analysis using IFDS one basically only has to implement a single class. It is a good idea to create name the analysis using the naming conventions that can be found in the corresponding problem directories.

To make the class an analysis problem our solver is able to solve, you let your class inherit from 'DefaultIFDSTabulationProblem' or 'LLVMDefaultIFDSTabulationProblem' when analyzing LLVM IR. The concrete analysis is formulated by overwriting all abstract functions of the interface. The member functions a user has to override are:

• getNormalFlowFunction()

  • Returns flow functions that describe the intra-procedural flows.

• getCallFlowFunction()

  • Express what the solver should do when it hits a call-site. This flow function factory usually returns a flow function that maps the actual parameters to the formal parameters of the called function.

• getRetFlowFunction()

  • Usually propagates the information at the end of the callee back to the caller.

• getCallToRetFlowFunction()

  • Every information that is not involved in the function call is handled here. Usually just passes every information as identity, except for pointer parameters that may be changed in the callee.

• Optional: getSummaryFlowFunction()

  • Default: Implemented to return nullptr. But can be used to model llvm.intrinsic functions or libc function that one does not wish to follow (e.g if no implementation is available).

• initialSeeds()

  • The initial seeds are the starting points of an analysis. An analysis can start at one or more points in the target program. The function must return start points as well as a set of data-flow facts that hold at these program points. Unless the concrete analysis requires something special, one would usually treat the first instruction of the main function as a starting point and use the special zero fact to hold at the analysis start.

• createZeroValue()

  • This function must define what value the analysis should use as the special zero value.

• Constructor

  • The constructor of an analysis receives the ICFG that shall be used to solve the analysis. Furthermore, the constructor of the DefaultIFDSTabulationProblem that one inherits from must be called AND the special zero value must be initialized in a suitable way. Here is an example of how your constructor can looks like:

  IFDSSolverTest::IFDSSolverTest(LLVMBasedICFG &I, vector<string> EntryPoints)
    : DefaultIFDSTabulationProblem<const llvm::Instruction *,
                                   const llvm::Value *, const llvm::Function *,
                                   LLVMBasedICFG &>(I), EntryPoints(EntryPoints) {
    DefaultIFDSTabulationProblem::zerovalue = createZeroValue();
  }

Memory Management

Our IFDS interface functions use the custom type FlowFunctionPtrType as a return type. This type provides a very efficient and low overhead flow function implementation. It also includes a builtin way to let the framework do the memory management for all flow functions. To use this memory manager use getFFMM().make_flow_function<FLOWFUNCTIONTYPE>(FLOWFUNCTIONPARAMS) to construct a new flow function that is directly managed by the flow function memory manager. This is not necessary for the special singleton flow functions such as Identity<d_t>. For these, just use the static member function getInstance().