SVF::ExternalPAG Class Reference

#include <ExternalPAG.h>

Public Member Functions
	ExternalPAG (std::string functionName)
	~ExternalPAG ()
std::string	getFunctionName () const
NodeSet &	getValueNodes ()
NodeSet &	getObjectNodes ()
OrderedSet< std::tuple< NodeID, NodeID, std::string, int > > &	getEdges ()
Map< int, NodeID > &	getArgNodes ()
NodeID	getReturnNode () const
void	setReturnNode (NodeID returnNode)
bool	hasReturnNode () const
	Does this function have a return node? More...
bool	addExternalPAG (const SVFFunction *function)

Static Public Member Functions
static void	initialise (SVFModule *svfModule)
static bool	connectCallsiteToExternalPAG (CallSite *cs)
static bool	hasExternalPAG (const SVFFunction *function)
	Whether an external PAG implementing function exists. More...
static void	dumpFunctions (std::vector< std::string > functions)
	Dump individual PAGs of specified functions. Currently to outs(). More...

Private Member Functions
void	readFromFile (std::string filename)

Static Private Member Functions
static std::vector< std::pair< std::string, std::string > >	parseExternalPAGs (llvm::cl::list< std::string > &extpagsArgs)

Private Attributes
std::string	functionName
	Name of the function this external PAG represents. More...
NodeSet	valueNodes
NodeSet	objectNodes
OrderedSet< std::tuple< NodeID, NodeID, std::string, int > >	edges
Map< int, NodeID >	argNodes
NodeID	returnNode
	Node from which return edges connect. More...
bool	hasReturn
	Whether this function has a return or not. More...

Static Private Attributes
static Map< const SVFFunction *, Map< int, PAGNode * > >	functionToExternalPAGEntries
static Map< const SVFFunction *, PAGNode * >	functionToExternalPAGReturns

Detailed Description

Represents the PAG of a function loaded externally (i.e. from file). It's purpose is to be attached to the main PAG (almost) seamlessly.

Definition at line 22 of file ExternalPAG.h.

Constructor & Destructor Documentation

ExternalPAG()

SVF::ExternalPAG::ExternalPAG ( std::string  functionName )

inline

Definition at line 79 of file ExternalPAG.h.

                                        : functionName(functionName),
        returnNode(-1), hasReturn(false) {}

~ExternalPAG()

SVF::ExternalPAG::~ExternalPAG ( )

inline

Definition at line 82 of file ExternalPAG.h.

{}

Member Function Documentation

addExternalPAG()

bool ExternalPAG::addExternalPAG

(

const SVFFunction *

function

)

Adds (creates new equivalents) all the nodes and edges of this extpag to the main PAG. function is used as a key for future lookups. Returns true on success, false otherwise (incl. if it already exists).

Definition at line 377 of file ExternalPAG.cpp.

{
    // The function does not exist in the module - bad arg?
    // TODO: maybe some warning?
    if (function == nullptr) return false;

    PAG *pag = PAG::getPAG();
    if (hasExternalPAG(function)) return false;

    outs() << "Adding extpag " << this->getFunctionName() << "\n";
    // Temporarily trick SVF Module into thinking we are reading from
    // file to avoid setting BBs/Values (as these nodes don't have any).
    std::string oldSVFModuleFileName = SVFModule::pagFileName();
    SVFModule::setPagFromTXT("tmp");

    // We need: the new nodes.
    //        : the new edges.
    //        : to map function names to the entry nodes.
    //        : to map function names to the return node.

    // To create the new edges.
    Map<NodeID, PAGNode *> extToNewNodes;

    // Add the value nodes.
    for (auto extNodeIt = this->getValueNodes().begin();
            extNodeIt != this->getValueNodes().end(); ++extNodeIt)
    {
        NodeID newNodeId = pag->addDummyValNode();
        extToNewNodes[*extNodeIt] = pag->getPAGNode(newNodeId);
    }

    // Add the object nodes.
    for (auto extNodeIt = this->getObjectNodes().begin();
            extNodeIt != this->getObjectNodes().end(); ++extNodeIt)
    {
        // TODO: fix obj node - there's more to it?
        NodeID newNodeId = pag->addDummyObjNode();
        extToNewNodes[*extNodeIt] = pag->getPAGNode(newNodeId);
    }

    // Add the edges.
    for (auto extEdgeIt = this->getEdges().begin();
            extEdgeIt != this->getEdges().end(); ++extEdgeIt)
    {
        NodeID extSrcId = std::get<0>(*extEdgeIt);
        NodeID extDstId = std::get<1>(*extEdgeIt);
        std::string extEdgeType = std::get<2>(*extEdgeIt);
        int extOffsetOrCSId = std::get<3>(*extEdgeIt);

        PAGNode *srcNode = extToNewNodes[extSrcId];
        PAGNode *dstNode = extToNewNodes[extDstId];
        NodeID srcId = srcNode->getId();
        NodeID dstId = dstNode->getId();

        if (extEdgeType == "addr")
        {
            pag->addAddrPE(srcId, dstId);
        }
        else if (extEdgeType == "copy")
        {
            pag->addCopyPE(srcId, dstId);
        }
        else if (extEdgeType == "load")
        {
            pag->addLoadPE(srcId, dstId);
        }
        else if (extEdgeType == "store")
        {
            pag->addStorePE(srcId, dstId, nullptr);
        }
        else if (extEdgeType == "gep")
        {
            pag->addNormalGepPE(srcId, dstId, LocationSet(extOffsetOrCSId));
        }
        else if (extEdgeType == "variant-gep")
        {
            pag->addVariantGepPE(srcId, dstId);
        }
        else if (extEdgeType == "call")
        {
            pag->addEdge(srcNode, dstNode, new CallPE(srcNode, dstNode, nullptr));
        }
        else if (extEdgeType == "ret")
        {
            pag->addEdge(srcNode, dstNode, new RetPE(srcNode, dstNode, nullptr));
        }
        else if (extEdgeType == "cmp")
        {
            pag->addCmpPE(srcId, dstId);
        }
        else if (extEdgeType == "binary-op")
        {
            pag->addBinaryOPPE(srcId, dstId);
        }
        else if (extEdgeType == "unary-op")
        {
            pag->addUnaryOPPE(srcId, dstId);
        }
        else
        {
            outs() << "Bad edge type found during extpag addition\n";
        }
    }

    // Record the arg nodes.
    Map<int, PAGNode *> argNodes;
    for (auto argNodeIt = this->getArgNodes().begin();
            argNodeIt != this->getArgNodes().end(); ++argNodeIt)
    {
        int index = argNodeIt->first;
        NodeID extNodeId = argNodeIt->second;
        argNodes[index] = extToNewNodes[extNodeId];
    }

    functionToExternalPAGEntries[function] = argNodes;

    // Record the return node.
    if (this->hasReturnNode())
    {
        functionToExternalPAGReturns[function] =
            extToNewNodes[this->getReturnNode()];
    }

    // Put it back as if nothing happened.
    SVFModule::setPagFromTXT(oldSVFModuleFileName);

    return true;
}

connectCallsiteToExternalPAG()

bool ExternalPAG::connectCallsiteToExternalPAG ( CallSite *  cs )

static

Connects callsite if a external PAG implementing the relevant function has been added. Returns true on success, false otherwise.

Definition at line 72 of file ExternalPAG.cpp.

{
    PAG *pag = PAG::getPAG();

    Function* function = cs->getCalledFunction();
    std::string functionName = function->getName().str();

    const SVFFunction* svfFun = LLVMModuleSet::getLLVMModuleSet()->getSVFFunction(function);
    if (!hasExternalPAG(svfFun)) return false;

    Map<int, PAGNode*> argNodes =
        functionToExternalPAGEntries[svfFun];
    PAGNode *retNode = functionToExternalPAGReturns[svfFun];

    // Handle the return.
    if (llvm::isa<PointerType>(cs->getType()))
    {
        NodeID dstrec = pag->getValueNode(cs->getInstruction());
        // Does it actually return a pointer?
        if (SVFUtil::isa<PointerType>(function->getReturnType()))
        {
            if (retNode != nullptr)
            {
                CallBlockNode* icfgNode = pag->getICFG()->getCallBlockNode(cs->getInstruction());
                pag->addRetPE(retNode->getId(), dstrec, icfgNode);
            }
        }
        else
        {
            // This is a int2ptr cast during parameter passing
            pag->addBlackHoleAddrPE(dstrec);
        }
    }

    // Handle the arguments;
    // Actual arguments.
    CallSite::arg_iterator itA = cs->arg_begin(), ieA = cs->arg_end();
    Function::const_arg_iterator itF = function->arg_begin(),
                                 ieF = function->arg_end();
    // Formal arguments.
    size_t formalNodeIndex = 0;

    for (; itF != ieF ; ++itA, ++itF, ++formalNodeIndex)
    {
        if (itA == ieA)
        {
            // When unneeded args are left empty, e.g. Linux kernel.
            break;
        }

        // Formal arg node is from the extpag, actual arg node would come from
        // the main pag.
        PAGNode *formalArgNode = argNodes[formalNodeIndex];
        NodeID actualArgNodeId = pag->getValueNode(*itA);

        const llvm::Value *formalArg = &*itF;
        if (!SVFUtil::isa<PointerType>(formalArg->getType())) continue;

        if (SVFUtil::isa<PointerType>((*itA)->getType()))
        {
            CallBlockNode* icfgNode = pag->getICFG()->getCallBlockNode(cs->getInstruction());
            pag->addCallPE(actualArgNodeId, formalArgNode->getId(), icfgNode);
        }
        else
        {
            // This is a int2ptr cast during parameter passing
            //addFormalParamBlackHoleAddrEdge(formalArgNode->getId(), &*itF);
            assert(false && "you need to set the current location of this PAGEdge");
            pag->addBlackHoleAddrPE(formalArgNode->getId());
        }
        // TODO proofread.
    }

    return true;
}

dumpFunctions()

void ExternalPAG::dumpFunctions ( std::vector< std::string >  functions )

static

Dump individual PAGs of specified functions. Currently to outs().

Dump PAGs for the functions

Definition at line 256 of file ExternalPAG.cpp.

{
    PAG *pag = PAG::getPAG();

    // Naive: first map functions to entries in PAG, then dump them.
    Map<const SVFFunction*, std::vector<PAGNode *>> functionToPAGNodes;

    Set<PAGNode *> callDsts;
    for (PAG::iterator it = pag->begin(); it != pag->end(); ++it)
    {
        PAGNode *currNode = it->second;
        if (!currNode->hasOutgoingEdges(PAGEdge::PEDGEK::Call)) continue;

        // Where are these calls going?
        for (PAGEdge::PAGEdgeSetTy::iterator it =
                    currNode->getOutgoingEdgesBegin(PAGEdge::PEDGEK::Call);
                it != currNode->getOutgoingEdgesEnd(PAGEdge::PEDGEK::Call); ++it)
        {
            CallPE *callEdge = static_cast<CallPE *>(*it);
            const Instruction *inst = callEdge->getCallInst()->getCallSite();
            :: Function* currFunction =
                static_cast<const CallInst *>(inst)->getCalledFunction();

            if (currFunction != nullptr)
            {
                // Otherwise, it would be an indirect call which we don't want.
                std::string currFunctionName = currFunction->getName().str();

                if (std::find(functions.begin(), functions.end(),
                              currFunctionName) != functions.end())
                {
                    // If the dst has already been added, we'd be duplicating
                    // due to multiple actual->arg call edges.
                    if (callDsts.find(callEdge->getDstNode()) == callDsts.end())
                    {
                        callDsts.insert(callEdge->getDstNode());
                        const SVFFunction* svfFun = LLVMModuleSet::getLLVMModuleSet()->getSVFFunction(currFunction);
                        functionToPAGNodes[svfFun].push_back(callEdge->getDstNode());
                    }
                }
            }
        }
    }

    for (auto it = functionToPAGNodes.begin(); it != functionToPAGNodes.end();
            ++it)
    {
        const SVFFunction* function = it->first;
        std::string functionName = it->first->getName().str();

        // The final nodes and edges we will print.
        Set<PAGNode *> nodes;
        Set<PAGEdge *> edges;
        // The search stack.
        std::stack<PAGNode *> todoNodes;
        // The arguments to the function.
        std::vector<PAGNode *> argNodes = it->second;
        PAGNode *retNode = nullptr;


        outs() << "PAG for function: " << functionName << "\n";
        for (auto node = argNodes.begin(); node != argNodes.end(); ++node)
        {
            todoNodes.push(*node);
        }

        while (!todoNodes.empty())
        {
            PAGNode *currNode = todoNodes.top();
            todoNodes.pop();

            // If the node has been dealt with, ignore it.
            if (nodes.find(currNode) != nodes.end()) continue;
            nodes.insert(currNode);

            // Return signifies the end of a path.
            if (RetPN::classof(currNode))
            {
                retNode = currNode;
                continue;
            }

            auto outEdges = currNode->getOutEdges();
            for (auto outEdge = outEdges.begin(); outEdge != outEdges.end();
                    ++outEdge)
            {
                edges.insert(*outEdge);
                todoNodes.push((*outEdge)->getDstNode());
            }
        }

        for (auto node = nodes.begin(); node != nodes.end(); ++node)
        {
            // TODO: proper file.
            // Argument nodes use extra information: it's argument number.
            if (std::find(argNodes.begin(), argNodes.end(), *node)
                    != argNodes.end())
            {
                outputPAGNode(outs(), *node,
                              getArgNo(function, (*node)->getValue()));
            }
            else if (*node == retNode)
            {
                outputPAGNode(outs(), *node, "ret");
            }
            else
            {
                outputPAGNode(outs(), *node);
            }
        }

        for (auto edge = edges.begin(); edge != edges.end(); ++edge)
        {
            // TODO: proper file.
            outputPAGEdge(outs(), *edge);
        }

        outs() << "PAG for functionName " << functionName << " done\n";
    }
}

getArgNodes()

Map<int, NodeID>& SVF::ExternalPAG::getArgNodes ( )

inline

Definition at line 117 of file ExternalPAG.h.

    {
        return argNodes;
    }

getEdges()

OrderedSet<std::tuple<NodeID, NodeID, std::string, int> >& SVF::ExternalPAG::getEdges ( )

inline

Definition at line 112 of file ExternalPAG.h.

    {
        return edges;
    }

getFunctionName()

std::string SVF::ExternalPAG::getFunctionName ( ) const

inline

Definition at line 99 of file ExternalPAG.h.

    {
        return functionName;
    }

getObjectNodes()

NodeSet& SVF::ExternalPAG::getObjectNodes ( )

inline

Definition at line 108 of file ExternalPAG.h.

    {
        return objectNodes;
    }

getReturnNode()

NodeID SVF::ExternalPAG::getReturnNode ( ) const

inline

Definition at line 122 of file ExternalPAG.h.

    {
        return returnNode;
    }

getValueNodes()

NodeSet& SVF::ExternalPAG::getValueNodes ( )

inline

Definition at line 104 of file ExternalPAG.h.

    {
        return valueNodes;
    }

hasExternalPAG()

bool ExternalPAG::hasExternalPAG ( const SVFFunction *  function )

static

Whether an external PAG implementing function exists.

Definition at line 148 of file ExternalPAG.cpp.

{
    bool ret = functionToExternalPAGEntries.find(function)
               != functionToExternalPAGEntries.end();
    return ret;
}

hasReturnNode()

bool SVF::ExternalPAG::hasReturnNode ( ) const

inline

Does this function have a return node?

Definition at line 133 of file ExternalPAG.h.

    {
        return hasReturn;
    }

initialise()

void ExternalPAG::initialise ( SVFModule *  svfModule )

static

Parses command line arguments and attaches external PAGs to main PAG.

Definition at line 54 of file ExternalPAG.cpp.

{
    std::vector<std::pair<std::string, std::string>> parsedExternalPAGs
            = ExternalPAG::parseExternalPAGs(ExternalPAGArgs);

    // Build ext PAGs (and add them) first to use them in PAG construction.
    for (auto extpagPair= parsedExternalPAGs.begin();
            extpagPair != parsedExternalPAGs.end(); ++extpagPair)
    {
        std::string fname = extpagPair->first;
        std::string path = extpagPair->second;

        ExternalPAG extpag = ExternalPAG(fname);
        extpag.readFromFile(path);
        extpag.addExternalPAG(getFunction(fname));
    }
}

parseExternalPAGs()

std::vector< std::pair< std::string, std::string > > ExternalPAG::parseExternalPAGs ( llvm::cl::list< std::string > &  extpagsArgs )

staticprivate

For passing that passed to -extpags option, splitting fname into a pair.

Definition at line 36 of file ExternalPAG.cpp.

{
    std::vector<std::pair<std::string, std::string>> parsedExternalPAGs;
    for (auto arg = extpagsArgs.begin(); arg != extpagsArgs.end();
            ++arg)
    {
        std::stringstream ss(*arg);
        std::string functionName;
        getline(ss, functionName, '@');
        std::string path;
        getline(ss, path);
        parsedExternalPAGs.push_back(
            std::pair<std::string, std::string>(functionName, path));
    }

    return parsedExternalPAGs;
}

readFromFile()

void ExternalPAG::readFromFile ( std::string  filename )

private

Reads nodes and edges from file.

File format: Node: nodeID Nodetype [[0|1|2|...]+|ret]

• Giving a number means that node represents such argument.
• Giving ret means that node represents the return node.. Edge: nodeID edgetype NodeID Offset

Example: 1 o 2 v 3 v 4 v 1 addr 2 0 1 addr 3 0 3 gep 4 4

Definition at line 507 of file ExternalPAG.cpp.

{
    std::string line;
    std::ifstream pagFile(filename.c_str());

    if (!pagFile.is_open())
    {
        outs() << "ExternalPAG::buildFromFile: could not open " << filename
               << "\n";
        return;
    }

    while (pagFile.good())
    {
        std::getline(pagFile, line);

        Size_t tokenCount = 0;
        std::string tmps;
        std::istringstream ss(line);
        while (ss.good())
        {
            ss >> tmps;
            tokenCount++;
        }

        if (tokenCount == 0)
        {
            // Empty line.
            continue;
        }

        if (tokenCount == 2 || tokenCount == 3)
        {
            // It's a node.
            NodeID nodeId;
            std::string nodeType;
            std::istringstream ss(line);
            ss >> nodeId;
            ss >> nodeType;

            if (nodeType == "v")
            {
                valueNodes.insert(nodeId);
            }
            else if (nodeType == "o")
            {
                objectNodes.insert(nodeId);
            }
            else
            {
                assert(false
                       && "format not supported, please specify node type");
            }


            if (tokenCount == 3)
            {
                // If there are 3 tokens, it should be 0, 1, 2, ... or ret.
                std::string argNoOrRet;
                ss >> argNoOrRet;

                if (argNoOrRet == "ret")
                {
                    setReturnNode(nodeId);
                }
                else if (std::all_of(argNoOrRet.begin(), argNoOrRet.end(),
                                     ::isdigit))
                {
                    int argNo = std::stoi(argNoOrRet);
                    argNodes[argNo] = nodeId;
                }
                else
                {
                    assert(false
                           && "format not supported, not arg number or ret");
                }

            }
        }
        else if (tokenCount == 4)
        {
            // It's an edge
            NodeID nodeSrc;
            NodeID nodeDst;
            Size_t offsetOrCSId;
            std::string edge;
            std::istringstream ss(line);
            ss >> nodeSrc;
            ss >> edge;
            ss >> nodeDst;
            ss >> offsetOrCSId;

            edges.insert(
                std::tuple<NodeID, NodeID, std::string, int>(nodeSrc, nodeDst,
                        edge,
                        offsetOrCSId));
        }
        else
        {
            if (!line.empty())
            {
                outs() << "format not supported, token count = "
                       << tokenCount << "\n";
                assert(false && "format not supported");
            }
        }
    }

    /*
    TODO: might need to include elsewhere.
    u32_t lower_bound = 1000;
    for(u32_t i = 0; i < lower_bound; i++)
        pag->incNodeNum();
    */
}

setReturnNode()

void SVF::ExternalPAG::setReturnNode ( NodeID  returnNode )

inline

Definition at line 126 of file ExternalPAG.h.

    {
        this->returnNode = returnNode;
        hasReturn = true;
    }

Member Data Documentation

argNodes

Map<int, NodeID> SVF::ExternalPAG::argNodes

private

Nodes in the ExternalPAG which call edges should connect to. argNodes[0] is arg 0, argNodes[1] is arg 1, ...

Definition at line 48 of file ExternalPAG.h.

edges

OrderedSet<std::tuple<NodeID, NodeID, std::string, int> > SVF::ExternalPAG::edges

private

Edges in this external PAG, represented by the parts of an Edge because we will rebuild these edges in the main PAG.

Definition at line 42 of file ExternalPAG.h.

functionName

std::string SVF::ExternalPAG::functionName

private

Name of the function this external PAG represents.

Definition at line 32 of file ExternalPAG.h.

functionToExternalPAGEntries

Map< const SVFFunction *, Map< int, PAGNode * > > ExternalPAG::functionToExternalPAGEntries

staticprivate

Maps function names to the entry nodes of the extpag which implements it. This is to connect arguments and callsites.

Definition at line 28 of file ExternalPAG.h.

functionToExternalPAGReturns

Map< const SVFFunction *, PAGNode * > ExternalPAG::functionToExternalPAGReturns

staticprivate

Definition at line 29 of file ExternalPAG.h.

hasReturn

bool SVF::ExternalPAG::hasReturn

private

Whether this function has a return or not.

Definition at line 53 of file ExternalPAG.h.

objectNodes

NodeSet SVF::ExternalPAG::objectNodes

private

Object nodes in this external PAG, represented by NodeIDs because we will rebuild these nodes in the main PAG.

Definition at line 39 of file ExternalPAG.h.

returnNode

NodeID SVF::ExternalPAG::returnNode

private

Node from which return edges connect.

Definition at line 50 of file ExternalPAG.h.

valueNodes

NodeSet SVF::ExternalPAG::valueNodes

private

Value nodes in this external PAG, represented by NodeIDs because we will rebuild these nodes in the main PAG.

Definition at line 36 of file ExternalPAG.h.

---

The documentation for this class was generated from the following files:

• /home/runner/work/SVF-1/SVF-1/include/Graphs/ExternalPAG.h
• /home/runner/work/SVF-1/SVF-1/lib/Graphs/ExternalPAG.cpp