SVF::LeakChecker Class Reference

#include <LeakChecker.h>

Inheritance diagram for SVF::LeakChecker:

Public Types
enum	LEAK_TYPE { NEVER_FREE_LEAK , CONTEXT_LEAK , PATH_LEAK , GLOBAL_LEAK }
typedef Map< const SVFGNode *, const CallICFGNode * >	SVFGNodeToCSIDMap
typedef FIFOWorkList< const CallICFGNode * >	CSWorkList
typedef ProgSlice::VFWorkList	WorkList
typedef NodeBS	SVFGNodeBS
Public Types inherited from SVF::SrcSnkDDA
typedef ProgSlice::SVFGNodeSet	SVFGNodeSet
typedef Map< const SVFGNode *, ProgSlice * >	SVFGNodeToSliceMap
typedef SVFGNodeSet::const_iterator	SVFGNodeSetIter
typedef CxtDPItem	DPIm
typedef Set< DPIm >	DPImSet
	dpitem set
typedef Map< const SVFGNode *, DPImSet >	SVFGNodeToDPItemsMap
	map a SVFGNode to its visited dpitems
typedef Set< const CallICFGNode * >	CallSiteSet
typedef NodeBS	SVFGNodeBS
typedef ProgSlice::VFWorkList	WorkList
Public Types inherited from SVF::GraphReachSolver< GraphType, DPIm >
typedef SVF::GenericGraphTraits< GraphType >	GTraits
	Define the GTraits and node iterator.
typedef GTraits::NodeType	GNODE
typedef GTraits::EdgeType	GEDGE
typedef GTraits::nodes_iterator	node_iterator
typedef GTraits::ChildIteratorType	child_iterator
typedef SVF::GenericGraphTraits< SVF::Inverse< GNODE * > >	InvGTraits
	Define inverse GTraits and note iterator.
typedef InvGTraits::ChildIteratorType	inv_child_iterator
typedef FIFOWorkList< DPIm >	WorkList
	Define worklist.

Public Member Functions
	LeakChecker ()
	Constructor.
virtual	~LeakChecker ()
	Destructor.
virtual bool	runOnModule (SVFIR *pag)
	We start from here.
virtual void	initSrcs () override
	Initialize sources and sinks.
virtual void	initSnks () override
virtual bool	isSourceLikeFun (const FunObjVar *fun) override
	Whether the function is a heap allocator/reallocator (allocate memory)
virtual bool	isSinkLikeFun (const FunObjVar *fun) override
	Whether the function is a heap deallocator (free/release memory)
Public Member Functions inherited from SVF::SrcSnkDDA
	SrcSnkDDA ()
	Bug Reporter.
	~SrcSnkDDA () override
	Destructor.
virtual void	analyze ()
	Start analysis here.
virtual void	initialize ()
	Initialize analysis.
virtual void	finalize ()
	Finalize analysis.
SVFIR *	getPAG () const
	Get SVFIR.
const SVFG *	getSVFG () const
	Get SVFG.
CallGraph *	getCallgraph () const
	Get Callgraph.
bool	isGlobalSVFGNode (const SVFGNode *node) const
	Whether this svfg node may access global variable.
virtual void	setCurSlice (const SVFGNode *src)
	Slice operations.
ProgSlice *	getCurSlice () const
void	addSinkToCurSlice (const SVFGNode *node)
bool	isInCurForwardSlice (const SVFGNode *node)
bool	isInCurBackwardSlice (const SVFGNode *node)
void	addToCurForwardSlice (const SVFGNode *node)
void	addToCurBackwardSlice (const SVFGNode *node)
bool	isInAWrapper (const SVFGNode *src, CallSiteSet &csIdSet)
	Identify allocation wrappers.
const SVFGNodeSet &	getSources () const
	Get sources/sinks.
SVFGNodeSetIter	sourcesBegin () const
SVFGNodeSetIter	sourcesEnd () const
void	addToSources (const SVFGNode *node)
const SVFGNodeSet &	getSinks () const
SVFGNodeSetIter	sinksBegin () const
SVFGNodeSetIter	sinksEnd () const
void	addToSinks (const SVFGNode *node)
SaberCondAllocator *	getSaberCondAllocator () const
	Get saber condition allocator.
const SVFBugReport &	getBugReport () const
bool	isSource (const SVFGNode *node) const
bool	isSink (const SVFGNode *node) const

Protected Member Functions
virtual void	reportBug (ProgSlice *slice) override
	Report leaks.
void	testsValidation (const ProgSlice *slice)
	Validate test cases for regression test purpose.
void	validateSuccessTests (const SVFGNode *source, const FunObjVar *fun)
void	validateExpectedFailureTests (const SVFGNode *source, const FunObjVar *fun)
void	addSrcToCSID (const SVFGNode *src, const CallICFGNode *cs)
	Record a source to its callsite.
const CallICFGNode *	getSrcCSID (const SVFGNode *src)
Protected Member Functions inherited from SVF::SrcSnkDDA
void	FWProcessCurNode (const DPIm &item) override
	Forward traverse.
void	BWProcessCurNode (const DPIm &item) override
	Backward traverse.
void	FWProcessOutgoingEdge (const DPIm &item, SVFGEdge *edge) override
	Propagate information forward by matching context.
void	BWProcessIncomingEdge (const DPIm &item, SVFGEdge *edge) override
	Propagate information backward without matching context, as forward analysis already did it.
bool	forwardVisited (const SVFGNode *node, const DPIm &item)
	Whether has been visited or not, in order to avoid recursion on SVFG.
void	addForwardVisited (const SVFGNode *node, const DPIm &item)
bool	backwardVisited (const SVFGNode *node)
void	addBackwardVisited (const SVFGNode *node)
void	clearVisitedMap ()
virtual bool	isAllPathReachable ()
	Whether it is all path reachable from a source.
virtual bool	isSomePathReachable ()
	Whether it is some path reachable from a source.
void	dumpSlices ()
	Dump SVFG with annotated slice information.
void	annotateSlice (ProgSlice *slice)
void	printZ3Stat ()
Protected Member Functions inherited from SVF::GraphReachSolver< GraphType, DPIm >
	GraphReachSolver ()
	Constructor.
virtual	~GraphReachSolver ()
	Destructor.
const GraphType	graph () const
	Get/Set graph methods.
void	setGraph (GraphType g)
GNODE *	getNode (NodeID id) const
virtual NodeID	getNodeIDFromItem (const DPIm &item) const
virtual void	forwardTraverse (DPIm &it)
	CFL forward traverse solve.
virtual void	backwardTraverse (DPIm &it)
	CFL forward traverse solve.
virtual void	FWProcessCurNode (const DPIm &)
	Process the DP item.
virtual void	BWProcessCurNode (const DPIm &)
virtual void	FWProcessOutgoingEdge (const DPIm &item, GEDGE *edge)
	Propagation for the solving, to be implemented in the child class.
virtual void	BWProcessIncomingEdge (const DPIm &item, GEDGE *edge)
DPIm	popFromWorklist ()
	Worklist operations.
bool	pushIntoWorklist (DPIm &item)
bool	isWorklistEmpty ()
bool	isInWorklist (DPIm &item)

Private Attributes
SVFGNodeToCSIDMap	srcToCSIDMap

Additional Inherited Members
Protected Attributes inherited from SVF::SrcSnkDDA
SaberSVFGBuilder	memSSA
SVFG *	svfg
CallGraph *	callgraph
SVFBugReport	report

Detailed Description

Static Memory Leak Detector

Definition at line 42 of file LeakChecker.h.

Member Typedef Documentation

CSWorkList

typedef FIFOWorkList<const CallICFGNode*> SVF::LeakChecker::CSWorkList

Definition at line 47 of file LeakChecker.h.

SVFGNodeBS

typedef NodeBS SVF::LeakChecker::SVFGNodeBS

Definition at line 49 of file LeakChecker.h.

SVFGNodeToCSIDMap

typedef Map<const SVFGNode*,const CallICFGNode*> SVF::LeakChecker::SVFGNodeToCSIDMap

Definition at line 46 of file LeakChecker.h.

WorkList

typedef ProgSlice::VFWorkList SVF::LeakChecker::WorkList

Definition at line 48 of file LeakChecker.h.

Member Enumeration Documentation

LEAK_TYPE

enum SVF::LeakChecker::LEAK_TYPE

Enumerator
NEVER_FREE_LEAK
CONTEXT_LEAK
PATH_LEAK
GLOBAL_LEAK

Definition at line 50 of file LeakChecker.h.

    {
        NEVER_FREE_LEAK,
        CONTEXT_LEAK,
        PATH_LEAK,
        GLOBAL_LEAK
    };

Constructor & Destructor Documentation

LeakChecker()

SVF::LeakChecker::LeakChecker ( )

inline

Constructor.

Definition at line 59 of file LeakChecker.h.

    {
    }

~LeakChecker()

virtual SVF::LeakChecker::~LeakChecker ( )

inlinevirtual

Destructor.

Definition at line 63 of file LeakChecker.h.

    {
    }

Member Function Documentation

addSrcToCSID()

void SVF::LeakChecker::addSrcToCSID ( const SVFGNode *  src, const CallICFGNode *  cs  )

inlineprotected

Record a source to its callsite.

Definition at line 105 of file LeakChecker.h.

    {
        srcToCSIDMap[src] = cs;
    }

getSrcCSID()

const CallICFGNode * SVF::LeakChecker::getSrcCSID ( const SVFGNode *  src )

inlineprotected

Definition at line 109 of file LeakChecker.h.

    {
        SVFGNodeToCSIDMap::iterator it =srcToCSIDMap.find(src);
        assert(it!=srcToCSIDMap.end() && "source node not at a callsite??");
        return it->second;
    }

initSnks()

void LeakChecker::initSnks ( )

overridevirtual

Initialize sinks

we only choose pointer parameters among all the actual parameters

Implements SVF::SrcSnkDDA.

Definition at line 105 of file LeakChecker.cpp.

{
 
    SVFIR* pag = getPAG();
 
    for(SVFIR::CSToArgsListMap::iterator it = pag->getCallSiteArgsMap().begin(),
            eit = pag->getCallSiteArgsMap().end(); it!=eit; ++it)
    {
 
        CallGraph::FunctionSet callees;
        getCallgraph()->getCallees(it->first,callees);
        for(CallGraph::FunctionSet::const_iterator cit = callees.begin(), ecit = callees.end(); cit!=ecit; cit++)
        {
            const FunObjVar* fun = *cit;
            if (isSinkLikeFun(fun))
            {
                SVFIR::ValVarList &arglist = it->second;
                assert(!arglist.empty() && "no actual parameter at deallocation site?");
                for (SVFIR::ValVarList::const_iterator ait = arglist.begin(),
                        aeit = arglist.end(); ait != aeit; ++ait)
                {
                    const SVFVar *svfVar = *ait;
                    if (svfVar->isPointer())
                    {
                        const SVFGNode *snk = getSVFG()->getActualParmVFGNode(svfVar, it->first);
                        addToSinks(snk);
 
                        // For any multi-level pointer e.g., XFree(void** svfVar) that passed into a ExtAPI::EFT_FREE_MULTILEVEL function (e.g., XFree),
                        // we will add the DstNode of a load edge, i.e., dummy = *svfVar
                        SVFStmt::SVFStmtSetTy& loads = const_cast<SVFVar*>(svfVar)->getOutgoingEdges(SVFStmt::Load);
                        for(const SVFStmt* ld : loads)
                        {
                            if(SVFUtil::isa<DummyValVar>(ld->getDstNode()))
                                addToSinks(getSVFG()->getStmtVFGNode(ld));
                        }
                    }
                }
            }
        }
    }
}

initSrcs()

void LeakChecker::initSrcs ( )

overridevirtual

Initialize sources and sinks.

Initialize sources and sinks

Initialize sources

if this callsite return reside in a dead function then we do not care about its leaks for example instruction int* p = malloc(size) is in a dead function, then program won't allocate this memory for example a customized malloc int p = malloc() returns an integer value, then program treat it as a system malloc

Implements SVF::SrcSnkDDA.

Definition at line 40 of file LeakChecker.cpp.

{
 
    SVFIR* pag = getPAG();
    for(SVFIR::CSToRetMap::iterator it = pag->getCallSiteRets().begin(),
            eit = pag->getCallSiteRets().end(); it!=eit; ++it)
    {
        const RetICFGNode* cs = it->first;
        if(cs->getFun()->isUncalledFunction() || !cs->getType()->isPointerTy())
            continue;
 
        CallGraph::FunctionSet callees;
        getCallgraph()->getCallees(cs->getCallICFGNode(),callees);
        for(CallGraph::FunctionSet::const_iterator cit = callees.begin(), ecit = callees.end(); cit!=ecit; cit++)
        {
            const FunObjVar* fun = *cit;
            if (isSourceLikeFun(fun))
            {
                CSWorkList worklist;
                SVFGNodeBS visited;
                worklist.push(it->first->getCallICFGNode());
                while (!worklist.empty())
                {
                    const CallICFGNode* cs = worklist.pop();
                    const RetICFGNode* retBlockNode = cs->getRetICFGNode();
                    const ValVar* svfVar = pag->getCallSiteRet(retBlockNode);
                    const SVFGNode* node = getSVFG()->getDefSVFGNode(svfVar);
                    if (visited.test(node->getId()) == 0)
                        visited.set(node->getId());
                    else
                        continue;
 
                    CallSiteSet csSet;
                    // if this node is in an allocation wrapper, find all its call nodes
                    if (isInAWrapper(node, csSet))
                    {
                        for (CallSiteSet::iterator it = csSet.begin(), eit =
                                    csSet.end(); it != eit; ++it)
                        {
                            worklist.push(*it);
                        }
                    }
                    // otherwise, this is the source we are interested
                    else
                    {
                        // exclude sources in dead functions or sources in functions that have summary
                        if (!cs->getFun()->isUncalledFunction() && !isExtCall(cs->getBB()->getParent()))
                        {
                            addToSources(node);
                            addSrcToCSID(node, cs);
                        }
                    }
                }
            }
        }
    }
 
}

isSinkLikeFun()

virtual bool SVF::LeakChecker::isSinkLikeFun ( const FunObjVar *  fun )

inlineoverridevirtual

Whether the function is a heap deallocator (free/release memory)

Reimplemented from SVF::SrcSnkDDA.

Reimplemented in SVF::FileChecker.

Definition at line 86 of file LeakChecker.h.

    {
        return SaberCheckerAPI::getCheckerAPI()->isMemDealloc(fun);
    }

isSourceLikeFun()

virtual bool SVF::LeakChecker::isSourceLikeFun ( const FunObjVar *  fun )

inlineoverridevirtual

Whether the function is a heap allocator/reallocator (allocate memory)

Reimplemented from SVF::SrcSnkDDA.

Reimplemented in SVF::FileChecker.

Definition at line 81 of file LeakChecker.h.

    {
        return SaberCheckerAPI::getCheckerAPI()->isMemAlloc(fun);
    }

reportBug()

void LeakChecker::reportBug ( ProgSlice *  slice )

overrideprotectedvirtual

Report leaks.

Implements SVF::SrcSnkDDA.

Reimplemented in SVF::FileChecker, and SVF::DoubleFreeChecker.

Definition at line 148 of file LeakChecker.cpp.

{
 
    if(isAllPathReachable() == false && isSomePathReachable() == false)
    {
        // full leakage
        GenericBug::EventStack eventStack =
        {
            SVFBugEvent(SVFBugEvent::SourceInst, getSrcCSID(slice->getSource()))
        };
        report.addSaberBug(GenericBug::NEVERFREE, eventStack);
    }
    else if (isAllPathReachable() == false && isSomePathReachable() == true)
    {
        // partial leakage
        GenericBug::EventStack eventStack;
        slice->evalFinalCond2Event(eventStack);
        eventStack.push_back(
            SVFBugEvent(SVFBugEvent::SourceInst, getSrcCSID(slice->getSource())));
        report.addSaberBug(GenericBug::PARTIALLEAK, eventStack);
    }
 
    if(Options::ValidateTests())
        testsValidation(slice);
}

runOnModule()

virtual bool SVF::LeakChecker::runOnModule ( SVFIR *  pag )

inlinevirtual

We start from here.

start analysis

Reimplemented in SVF::FileChecker, and SVF::DoubleFreeChecker.

Definition at line 68 of file LeakChecker.h.

    {
        analyze();
        return false;
    }

testsValidation()

void LeakChecker::testsValidation ( const ProgSlice *  slice )

protected

Validate test cases for regression test purpose.

Validate test cases for regression test purpose

Definition at line 178 of file LeakChecker.cpp.

{
    const SVFGNode* source = slice->getSource();
    const CallICFGNode* cs = getSrcCSID(source);
    const FunObjVar* fun = cs->getCalledFunction();
    if(fun==nullptr)
        return;
 
    validateSuccessTests(source,fun);
    validateExpectedFailureTests(source,fun);
}

validateExpectedFailureTests()

void LeakChecker::validateExpectedFailureTests ( const SVFGNode *  source, const FunObjVar *  fun  )

protected

Definition at line 261 of file LeakChecker.cpp.

{
 
    const CallICFGNode* cs = getSrcCSID(source);
 
    bool expectedFailure = false;
 
    if(fun->getName() == "NFRLEAKFP")
    {
        if(isAllPathReachable() == false && isSomePathReachable() == false)
            expectedFailure = true;
    }
    else if(fun->getName() == "PLKLEAKFP")
    {
        if(isAllPathReachable() == false && isSomePathReachable() == true)
            expectedFailure = true;
    }
    else if(fun->getName() == "LEAKFN")
    {
        if(isAllPathReachable() == true && isSomePathReachable() == true)
            expectedFailure = true;
    }
    else if(fun->getName() == "SAFEMALLOC" || fun->getName() == "NFRMALLOC"
            || fun->getName() == "PLKMALLOC" || fun->getName() == "CLKLEAKFN")
    {
        return;
    }
    else
    {
        writeWrnMsg("\t can not validate, check function not found, please put it at the right place!!");
        return;
    }
 
    std::string funName = source->getFun()->getName();
 
    if (expectedFailure)
    {
        if (!(getSrcCSID(source))->hasLLVMValue())
        {
            outs() << sucMsg("\t EXPECTED-FAILURE :") << funName <<"\n";
            return;
        }
        outs() << sucMsg("\t EXPECTED-FAILURE :") << funName << " check <src id:" << source->getId()
               << ", cs id:" << (getSrcCSID(source))->valueOnlyToString() << "> at ("
               << cs->getSourceLoc() << ")\n";
    }
    else
    {
        if (!(getSrcCSID(source))->hasLLVMValue())
        {
            SVFUtil::errs() << errMsg("\t UNEXPECTED FAILURE :") << funName <<"\n";
            assert(false && "test case failed!");
            return;
        }
        SVFUtil::errs() << errMsg("\t UNEXPECTED FAILURE :") << funName
                        << " check <src id:" << source->getId()
                        << ", cs id:" << (getSrcCSID(source))->valueOnlyToString() << "> at ("
                        << cs->getSourceLoc() << ")\n";
        assert(false && "test case failed!");
    }
}

validateSuccessTests()

void LeakChecker::validateSuccessTests ( const SVFGNode *  source, const FunObjVar *  fun  )

protected

Definition at line 191 of file LeakChecker.cpp.

{
 
    const CallICFGNode* cs = getSrcCSID(source);
 
    bool success = false;
 
    if(fun->getName() == "SAFEMALLOC")
    {
        if(isAllPathReachable() == true && isSomePathReachable() == true)
            success = true;
    }
    else if(fun->getName() == "NFRMALLOC")
    {
        if(isAllPathReachable() == false && isSomePathReachable() == false)
            success = true;
    }
    else if(fun->getName() == "PLKMALLOC")
    {
        if(isAllPathReachable() == false && isSomePathReachable() == true)
            success = true;
    }
    else if(fun->getName() == "CLKMALLOC")
    {
        if(isAllPathReachable() == false && isSomePathReachable() == false)
            success = true;
    }
    else if(fun->getName() == "NFRLEAKFP" || fun->getName() == "PLKLEAKFP"
            || fun->getName() == "LEAKFN")
    {
        return;
    }
    else
    {
        writeWrnMsg("\t can not validate, check function not found, please put it at the right place!!");
        return;
    }
 
    std::string funName = source->getFun()->getName();
 
    if (success)
    {
        if ((getSrcCSID(source))->hasLLVMValue())
        {
            outs() << sucMsg("\t SUCCESS :") << funName << " check <src id:" << source->getId()
                   << ", cs id:" << (getSrcCSID(source))->valueOnlyToString() << "> at ("
                   << cs->getSourceLoc() << ")\n";
        }
        else
        {
            outs() << sucMsg("\t SUCCESS :") << funName<<"\n";
        }
    }
    else
    {
        if ((getSrcCSID(source))->hasLLVMValue())
        {
            SVFUtil::errs() << errMsg("\t FAILURE :") << funName << " check <src id:" << source->getId()
                            << ", cs id:" << (getSrcCSID(source))->valueOnlyToString() << "> at ("
                            << cs->getSourceLoc() << ")\n";
            assert(false && "test case failed!");
        }
        else
        {
            SVFUtil::errs() << errMsg("\t FAILURE :") << funName <<  "\n";
            assert(false && "test case failed!");
        }
    }
}

Member Data Documentation

srcToCSIDMap

SVFGNodeToCSIDMap SVF::LeakChecker::srcToCSIDMap

private

Definition at line 117 of file LeakChecker.h.

---

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

• /home/runner/work/SVF/SVF/svf/include/SABER/LeakChecker.h
• /home/runner/work/SVF/SVF/svf/lib/SABER/LeakChecker.cpp