#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 SVFFunction *fun) override
	Whether the function is a heap allocator/reallocator (allocate memory)

virtual bool	isSinkLikeFun (const SVFFunction *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 (SVFModule *module)
	Start analysis here.

virtual void	initialize (SVFModule *module)
	Initialize analysis.

virtual void	finalize ()
	Finalize analysis.

SVFIR *	getPAG () const
	Get SVFIR.

const SVFG *	getSVFG () const
	Get SVFG.

PTACallGraph *	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 SVFFunction fun)

void	validateExpectedFailureTests (const SVFGNode source, const SVFFunction 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

PTACallGraph *	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.

60 {

61 }

◆ ~LeakChecker()

virtual SVF::LeakChecker::~LeakChecker ( )

inlinevirtual

Destructor.

Definition at line 63 of file LeakChecker.h.

64 {

65 }

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)
    {
 
        PTACallGraph::FunctionSet callees;
        getCallgraph()->getCallees(it->first,callees);
        for(PTACallGraph::FunctionSet::const_iterator cit = callees.begin(), ecit = callees.end(); cit!=ecit; cit++)
        {
            const SVFFunction* fun = *cit;
            if (isSinkLikeFun(fun))
            {
                SVFIR::SVFVarList &arglist = it->second;
                assert(!arglist.empty() && "no actual parameter at deallocation site?");
                for (SVFIR::SVFVarList::const_iterator ait = arglist.begin(),
                        aeit = arglist.end(); ait != aeit; ++ait)
                {
                    const PAGNode *pagNode = *ait;
                    if (pagNode->isPointer())
                    {
                        const SVFGNode *snk = getSVFG()->getActualParmVFGNode(pagNode, it->first);
                        addToSinks(snk);
 
                        // For any multi-level pointer e.g., XFree(void** pagNode) that passed into a ExtAPI::EFT_FREE_MULTILEVEL function (e.g., XFree),
                        // we will add the DstNode of a load edge, i.e., dummy = *pagNode
                        SVFStmt::SVFStmtSetTy& loads = const_cast<PAGNode*>(pagNode)->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;
 
        PTACallGraph::FunctionSet callees;
        getCallgraph()->getCallees(cs->getCallICFGNode(),callees);
        for(PTACallGraph::FunctionSet::const_iterator cit = callees.begin(), ecit = callees.end(); cit!=ecit; cit++)
        {
            const SVFFunction* 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 PAGNode* pagNode = pag->getCallSiteRet(retBlockNode);
                    const SVFGNode* node = getSVFG()->getDefSVFGNode(pagNode);
                    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 SVFFunction * 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 SVFFunction * 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(pag->getModule());
        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 SVFFunction* fun = cs->getCalledFunction();
    if(fun==nullptr)
        return;
 
    validateSuccessTests(source,fun);
    validateExpectedFailureTests(source,fun);
}

◆ validateExpectedFailureTests()

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

protected

Definition at line 246 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)
    {
        outs() << sucMsg("\t EXPECTED-FAILURE :") << funName << " check <src id:" << source->getId()
               << ", cs id:" << (getSrcCSID(source))->valueOnlyToString() << "> at ("
               << cs->getSourceLoc() << ")\n";
    }
    else
    {
        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 SVFFunction *	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)
    {
        outs() << sucMsg("\t SUCCESS :") << funName << " check <src id:" << source->getId()
               << ", cs id:" << (getSrcCSID(source))->valueOnlyToString() << "> at ("
               << cs->getSourceLoc() << ")\n";
    }
    else
    {
        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!");
    }
}

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

Public Types

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ CSWorkList

◆ SVFGNodeBS

◆ SVFGNodeToCSIDMap

◆ WorkList

Member Enumeration Documentation

◆ LEAK_TYPE

Constructor & Destructor Documentation

◆ LeakChecker()

◆ ~LeakChecker()

Member Function Documentation

◆ addSrcToCSID()

◆ getSrcCSID()

◆ initSnks()

◆ initSrcs()

◆ isSinkLikeFun()

◆ isSourceLikeFun()

◆ reportBug()

◆ runOnModule()

◆ testsValidation()

◆ validateExpectedFailureTests()

◆ validateSuccessTests()

Member Data Documentation

◆ srcToCSIDMap