SVF::AliasCFLGraphBuilder Class Reference

AliasCFLGraphBuilder: a CFLGraphBuilder specialized for handling aliasing. More...

#include <CFLGraphBuilder.h>

Inheritance diagram for SVF::AliasCFLGraphBuilder:

Public Member Functions
CFLGraph *	buildBigraph (ConstraintGraph *graph, Kind startKind, GrammarBase *grammar)
	Builds a bidirectional CFL graph by copying nodes and edges from a const graph that inherits from GenericGraph.
CFLGraph *	buildBiPEGgraph (ConstraintGraph *graph, Kind startKind, GrammarBase *grammar, SVFIR *pag)
Public Member Functions inherited from SVF::CFLGraphBuilder
template<class N , class E >
CFLGraph *	build (GenericGraph< N, E > *graph, GrammarBase *grammar, BuildDirection direction=BuildDirection::plain)
CFLGraph *	build (std::string fileName, GrammarBase *grammar, BuildDirection direction=BuildDirection::plain)
	Method to build a CFL graph from external file.
Map< std::string, Kind > &	getLabelToKindMap ()
	Returns a reference to the map that associates string labels with their corresponding Kind.
Map< Kind, std::string > &	getKindToLabelMap ()
	Returns a reference to the map that associates Kinds with their corresponding string labels.
Map< CFGrammar::Kind, Set< CFGrammar::Attribute > > &	getKindToAttrsMap ()
	Returns a reference to the map that associates Kinds with their corresponding attributes.

Private Member Functions
void	connectVGep (CFLGraph *cflGraph, ConstraintGraph *graph, ConstraintNode *src, ConstraintNode *dst, u32_t level, SVFIR *pag)
	Connects VGep (Variable GEP)
void	addBiCFLEdge (CFLGraph *cflGraph, ConstraintNode *src, ConstraintNode *dst, CFGrammar::Kind label)
	Handles edges, with the exception of the GEP.
void	addBiGepCFLEdge (CFLGraph *cflGraph, ConstraintNode *src, ConstraintNode *dst, CFGrammar::Attribute attri)
	Adds bidirectional GEP edges with attributes.

Additional Inherited Members
Protected Types inherited from SVF::CFLGraphBuilder
typedef CFGrammar::Kind	Kind
typedef CFGrammar::Symbol	Symbol
Protected Member Functions inherited from SVF::CFLGraphBuilder
void	addAttribute (CFGrammar::Kind kind, CFGrammar::Attribute attribute)
	Method to add an attribute to a specific kind.
void	buildlabelToKindMap (GrammarBase *grammar)
	build label and kind connect from the grammar
CFLNode *	addGNode (u32_t NodeID)
	add src and dst node from file
CFLGraph *	buildFromText (std::string fileName, GrammarBase *grammar, BuildDirection direction=BuildDirection::plain)
	Method to build a CFL graph from a Text file.
CFLGraph *	buildFromDot (std::string filename, GrammarBase *grammar, BuildDirection direction=BuildDirection::plain)
	Method to build a CFL graph from a Dot file.
CFLGraph *	buildFromJson (std::string filename, GrammarBase *grammar, BuildDirection direction=BuildDirection::plain)
	Method to build a CFL graph from a Json file.
Protected Attributes inherited from SVF::CFLGraphBuilder
Map< std::string, Kind >	labelToKindMap
	Maps to maintain mapping between labels and kinds.
Map< Kind, std::string >	kindToLabelMap
Map< CFGrammar::Kind, Set< CFGrammar::Attribute > >	kindToAttrsMap
	Map to maintain attributes associated with each kind.
Kind	current
CFLGraph *	cflGraph

Detailed Description

AliasCFLGraphBuilder: a CFLGraphBuilder specialized for handling aliasing.

Definition at line 120 of file CFLGraphBuilder.h.

Member Function Documentation

addBiCFLEdge()

void SVF::AliasCFLGraphBuilder::addBiCFLEdge ( CFLGraph *  cflGraph, ConstraintNode *  src, ConstraintNode *  dst, CFGrammar::Kind  label  )

private

Handles edges, with the exception of the GEP.

Definition at line 461 of file CFLGraphBuilder.cpp.

{
    cflGraph->addCFLEdge(cflGraph->getGNode(src->getId()), cflGraph->getGNode(dst->getId()), kind);
    std::string label = kindToLabelMap[kind];
    label.append("bar");
    cflGraph->addCFLEdge(cflGraph->getGNode(dst->getId()), cflGraph->getGNode(src->getId()), labelToKindMap[label]);
    return;
}

addBiGepCFLEdge()

void SVF::AliasCFLGraphBuilder::addBiGepCFLEdge ( CFLGraph *  cflGraph, ConstraintNode *  src, ConstraintNode *  dst, CFGrammar::Attribute  attri  )

private

Adds bidirectional GEP edges with attributes.

Definition at line 470 of file CFLGraphBuilder.cpp.

{
    CFLEdge::GEdgeFlag edgeLabel = CFGrammar::getAttributedKind(attri, ConstraintEdge::NormalGep);
    cflGraph->addCFLEdge(cflGraph->getGNode(src->getId()), cflGraph->getGNode(dst->getId()), edgeLabel);
    std::string label = kindToLabelMap[ConstraintEdge::NormalGep];
    label.append("bar");
    cflGraph->addCFLEdge(cflGraph->getGNode(dst->getId()), cflGraph->getGNode(src->getId()), CFGrammar::getAttributedKind(attri, labelToKindMap[label]));
    return;
}

buildBigraph()

CFLGraph * SVF::AliasCFLGraphBuilder::buildBigraph	(	ConstraintGraph *	graph,
		Kind	startKind,
		GrammarBase *	grammar
	)

Builds a bidirectional CFL graph by copying nodes and edges from a const graph that inherits from GenericGraph.

Definition at line 280 of file CFLGraphBuilder.cpp.

{
    cflGraph = new CFLGraph(startKind);
 
    buildlabelToKindMap(grammar);
    for(auto it = graph->begin(); it!= graph->end(); it++)
    {
        CFLNode* node = new CFLNode((*it).first);
        cflGraph->addCFLNode((*it).first, node);
    }
    for(auto it = graph->begin(); it!= graph->end(); it++)
    {
        ConstraintNode* node = (*it).second;
        for(ConstraintEdge* edge : node->getOutEdges())
        {
            CFGrammar::Kind edgeLabel = edge->getEdgeKind();
            // Need to get the offset from the Const Edge
            // The offset present edge is only from Normal Gep CG at moment
            if(NormalGepCGEdge::classof(edge))
            {
                NormalGepCGEdge *nGepEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge);
                CFGrammar::Attribute attr =  nGepEdge->getConstantFieldIdx();
                addAttribute(edgeLabel, attr);
                edgeLabel = CFGrammar::getAttributedKind(attr, edgeLabel);
                cflGraph->addCFLEdge(cflGraph->getGNode(edge->getSrcID()), cflGraph->getGNode(edge->getDstID()), edgeLabel);
                std::string label = kindToLabelMap[edge->getEdgeKind()];
                label.append("bar");   // for example Gep_i should be Gepbar_i, not Gep_ibar
                cflGraph->addCFLEdge(cflGraph->getGNode(edge->getDstID()), cflGraph->getGNode(edge->getSrcID()), CFGrammar::getAttributedKind(attr, labelToKindMap[label]));
                addAttribute(labelToKindMap[label], attr);
            }
            else
            {
                cflGraph->addCFLEdge(cflGraph->getGNode(edge->getSrcID()), cflGraph->getGNode(edge->getDstID()), edgeLabel);
                std::string label = kindToLabelMap[edge->getEdgeKind()];
                label.append("bar");
                cflGraph->addCFLEdge(cflGraph->getGNode(edge->getDstID()), cflGraph->getGNode(edge->getSrcID()), labelToKindMap[label]);
            }
        }
    }
    return cflGraph;
}

buildBiPEGgraph()

CFLGraph * SVF::AliasCFLGraphBuilder::buildBiPEGgraph	(	ConstraintGraph *	graph,
		Kind	startKind,
		GrammarBase *	grammar,
		SVFIR *	pag
	)

Builds a bidirectional CFL graph by copying nodes and edges from any graph that inherits from GenericGraph Transfers Load and Store to copy edge and address edge to construct PEG style CFLGraph

Process Store

Check Dst of Store Dereference Node

Add Addr Edge

Add Copy Edge

Process Load

Check Src of Load Dereference Node

Add Addr Edge

Add Copy Edge

Handle VGep normalize to Normal Gep by connecting all geps' srcs to vgep dest Example: In Test Case: Ctest field-ptr-arith-varIdx.c.bc BFS Search the 8 LEVEL up to find the ValueNode, and the number of level search is arbitrary the more the level search the more valueNode and the Vgep Dst will possibly connect

Definition at line 322 of file CFLGraphBuilder.cpp.

{
    cflGraph = new CFLGraph(startKind);
 
    buildlabelToKindMap(grammar);
    for(auto it = graph->begin(); it!= graph->end(); it++)
    {
        CFLNode* node = new CFLNode((*it).first);
        cflGraph->addCFLNode((*it).first, node);
    }
    for(auto it = graph->begin(); it!= graph->end(); it++)
    {
        ConstraintNode* node = (*it).second;
        for(ConstraintEdge* edge : node->getOutEdges())
        {
            if (edge->getEdgeKind() == ConstraintEdge::Store)
            {
                if (pag->isNullPtr(edge->getSrcID()))
                    continue;
                ConstraintNode* Dst = edge->getDstNode();
                ConstraintNode* DerefNode = nullptr;
                CFLNode* CFLDerefNode = nullptr;
                for (ConstraintEdge* DstInEdge : Dst->getInEdges())
                {
                    if (DstInEdge->getEdgeKind() == ConstraintEdge::Addr)
                    {
                        DerefNode = DstInEdge->getSrcNode();
                        CFLDerefNode = cflGraph->getGNode(DstInEdge->getSrcID());
                        break;
                    }
                }
                if (DerefNode == nullptr)
                {
                    NodeID refId = pag->addDummyValNode();
                    CFLDerefNode = new CFLNode(refId);
                    cflGraph->addCFLNode(refId, CFLDerefNode);
                    cflGraph->addCFLEdge(CFLDerefNode, cflGraph->getGNode(edge->getDstID()), ConstraintEdge::Addr);
                    std::string label = kindToLabelMap[ConstraintEdge::Addr];
                    label.append("bar");
                    cflGraph->addCFLEdge(cflGraph->getGNode(edge->getDstID()), CFLDerefNode, labelToKindMap[label]);
                }
                cflGraph->addCFLEdge(cflGraph->getGNode(edge->getSrcID()), cflGraph->getGNode(CFLDerefNode->getId()), ConstraintEdge::Copy);
                std::string label = kindToLabelMap[ConstraintEdge::Copy];
                label.append("bar");
                cflGraph->addCFLEdge(cflGraph->getGNode(CFLDerefNode->getId()), cflGraph->getGNode(edge->getSrcID()), labelToKindMap[label]);
            }
            else if ( edge->getEdgeKind() == ConstraintEdge::Load)
            {
                ConstraintNode* Src = edge->getSrcNode();
                ConstraintNode* DerefNode = nullptr;
                CFLNode* CFLDerefNode = nullptr;
                for (ConstraintEdge* SrcInEdge : Src->getInEdges())
                {
                    if (SrcInEdge->getEdgeKind() == ConstraintEdge::Addr)
                    {
                        DerefNode = SrcInEdge->getSrcNode();
                        CFLDerefNode = cflGraph->getGNode(SrcInEdge->getSrcID());
                    }
                }
                if (DerefNode == nullptr)
                {
                    NodeID refId = pag->addDummyValNode();
                    CFLDerefNode = new CFLNode(refId);
                    cflGraph->addCFLNode(refId, CFLDerefNode);
                    cflGraph->addCFLEdge(CFLDerefNode, cflGraph->getGNode(edge->getSrcID()), ConstraintEdge::Addr);
                    std::string label = kindToLabelMap[ConstraintEdge::Addr];
                    label.append("bar");
                    cflGraph->addCFLEdge(cflGraph->getGNode(edge->getSrcID()), CFLDerefNode, labelToKindMap[label]);
                }
                cflGraph->addCFLEdge(cflGraph->getGNode(CFLDerefNode->getId()), cflGraph->getGNode(edge->getDstID()),  ConstraintEdge::Copy);
                std::string label = kindToLabelMap[ConstraintEdge::Copy];
                label.append("bar");
                cflGraph->addCFLEdge(cflGraph->getGNode(edge->getDstID()), cflGraph->getGNode(CFLDerefNode->getId()),  labelToKindMap[label]);
            }
            else if ( edge->getEdgeKind() == ConstraintEdge::VariantGep)
            {
                connectVGep(cflGraph, graph,  edge->getSrcNode(), edge->getDstNode(), 8, pag);
            }
            else
            {
                CFGrammar::Kind edgeLabel = edge->getEdgeKind();
                // Need to get the offset from the Const Edge
                // The offset present edge is only from Normal Gep CG at moment
                if(NormalGepCGEdge::classof(edge))
                {
                    NormalGepCGEdge *nGepEdge = SVFUtil::dyn_cast<NormalGepCGEdge>(edge);
                    CFGrammar::Attribute attr =  nGepEdge->getConstantFieldIdx();
                    addAttribute(edgeLabel, attr);
                    edgeLabel = CFGrammar::getAttributedKind(attr, edgeLabel);
                    cflGraph->addCFLEdge(cflGraph->getGNode(edge->getSrcID()), cflGraph->getGNode(edge->getDstID()), edgeLabel);
                    std::string label = kindToLabelMap[edge->getEdgeKind()];
                    label.append("bar");   // for example Gep_i should be Gepbar_i, not Gep_ibar
                    cflGraph->addCFLEdge(cflGraph->getGNode(edge->getDstID()), cflGraph->getGNode(edge->getSrcID()), CFGrammar::getAttributedKind(attr, labelToKindMap[label]));
                    addAttribute(labelToKindMap[label], attr);
                }
                else
                {
                    cflGraph->addCFLEdge(cflGraph->getGNode(edge->getSrcID()), cflGraph->getGNode(edge->getDstID()), edgeLabel);
                    std::string label = kindToLabelMap[edge->getEdgeKind()];
                    label.append("bar");
                    cflGraph->addCFLEdge(cflGraph->getGNode(edge->getDstID()), cflGraph->getGNode(edge->getSrcID()), labelToKindMap[label]);
                }
            }
        }
    }
    return cflGraph;
}

connectVGep()

void SVF::AliasCFLGraphBuilder::connectVGep ( CFLGraph *  cflGraph, ConstraintGraph *  graph, ConstraintNode *  src, ConstraintNode *  dst, u32_t  level, SVFIR *  pag  )

private

Connects VGep (Variable GEP)

---

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

• /home/runner/work/SVF/SVF/svf/include/CFL/CFLGraphBuilder.h
• /home/runner/work/SVF/SVF/svf/lib/CFL/CFLGraphBuilder.cpp