8000 step1: remove preAbstrace and use use a temporary state to collect st… by jumormt · Pull Request #1523 · SVF-tools/SVF · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

step1: remove preAbstrace and use use a temporary state to collect st… #1523

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 5 commits into from
Aug 21, 2024
Merged

step1: remove preAbstrace and use use a temporary state to collect st… #1523

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
fa86b5e
remove preAbstrace
jumormt Aug 21, 2024
30a9642
refactor code
jumormt Aug 21, 2024
de2d282
move merge to one location
jumormt Aug 21, 2024
2135f9d
address comments
jumormt Aug 21, 2024
4a79581
address comments
jumormt Aug 21, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
15 changes: 8 additions & 7 deletions svf/include/AE/Svfexe/AbstractInterpretation.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -143,10 +143,10 @@ class AbstractInterpretation
/**
* Check if execution state exist by merging states of predecessor nodes
*
* @param curNode The ICFGNode to analyse
* @param icfgNode The icfg node to analyse
* @return if this node has preceding execution state
*/
bool mergeStatesFromPredecessors(const ICFGNode* curNode);
bool mergeStatesFromPredecessors(const ICFGNode * icfgNode);

/**
* Check if execution state exist at the branch edge
Expand Down Expand Up @@ -179,6 +179,8 @@ class AbstractInterpretation

void handleWTOComponents(const std::list<const ICFGWTOComp*>& wtoComps);

void handleWTOComponent(const ICFGWTOComp* wtoComp);


/**
* handle SVF Statement like CmpStmt, CallStmt, GepStmt, LoadStmt, StoreStmt, etc.
Expand Down Expand Up @@ -378,29 +380,28 @@ class AbstractInterpretation
AbstractState& getAbsStateFromTrace(const ICFGNode* node)
{
const ICFGNode* repNode = _icfg->getRepNode(node);
if (_postAbsTrace.count(repNode) == 0)
if (_abstractTrace.count(repNode) == 0)
{
assert(0 && "No preAbsTrace for this node");
}
else
{
return _postAbsTrace[repNode];
return _abstractTrace[repNode];
}
}

bool hasAbsStateFromTrace(const ICFGNode* node)
{
const ICFGNode* repNode = _icfg->getRepNode(node);
return _postAbsTrace.count(repNode) != 0;
return _abstractTrace.count(repNode) != 0;
}

protected:
// there data should be shared with subclasses
Map<std::string, std::function<void(const CallSite &)>> _func_map;
Set<const CallICFGNode*> _checkpoints;
Set<std::string> _checkpoint_names;
Map<const ICFGNode*, AbstractState> _preAbsTrace;
Map<const ICFGNode*, AbstractState> _postAbsTrace;
Map<const ICFGNode*, AbstractState> _abstractTrace; // abstract states immediately after nodes
std::string _moduleName;
};
}
6 changes: 3 additions & 3 deletions svf/include/AE/Svfexe/BufOverflowChecker.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -178,12 +178,12 @@ class BufOverflowChecker: public AbstractInterpretation
virtual void handleSingletonWTO(const ICFGSingletonWTO *icfgSingletonWto) override
{
AbstractInterpretation::handleSingletonWTO(icfgSingletonWto);
const ICFGNode* repNode = _icfg->getRepNode(icfgSingletonWto->node());
if (_postAbsTrace.count(repNode) == 0)
const ICFGNode* repNode = _icfg->getRepNode(icfgSingletonWto->getICFGNode());
if (_abstractTrace.count(repNode) == 0)
{
return;
}
const std::vector<const ICFGNode*>& worklist_vec = _icfg->getSubNodes(icfgSingletonWto->node());
const std::vector<const ICFGNode*>& worklist_vec = _icfg->getSubNodes(icfgSingletonWto->getICFGNode());

for (auto it = worklist_vec.begin(); it != worklist_vec.end(); ++it)
{
Expand Down
8 changes: 4 additions & 4 deletions svf/include/Graphs/WTO.h
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -341,7 +341,7 @@
}

/// Return the graph node
const NodeT* node() const
const NodeT* getICFGNode() const
{
return _node;
}
Expand Down Expand Up @@ -457,7 +457,7 @@
std::string str;
std::stringstream rawstr(str);
rawstr << "(";
rawstr << _head->node()->getId() << ", ";
rawstr << _head->getICFGNode()->getId() << ", ";

Check warning on line 460 in svf/include/Graphs/WTO.h

View check run for this annotation

Codecov / codecov/patch

svf/include/Graphs/WTO.h#L460 

Added line #L460 was not covered by tests
for (auto it = begin(), et = end(); it != et;)
{
rawstr << (*it)->toString();
Expand Down Expand Up @@ -698,7 +698,7 @@

void visit(const WTOCycleT& cycle) override
{
const NodeT* head = cycle.head()->node();
const NodeT* head = cycle.head()->getICFGNode();
WTOCycleDepthPtr previous_cycleDepth = _wtoCycleDepth;
_nodeToWTOCycleDepth.insert(std::make_pair(head, _wtoCycleDepth));
_wtoCycleDepth =
Expand All @@ -714,7 +714,7 @@
void visit(const WTONodeT& node) override
{
_nodeToWTOCycleDepth.insert(
std::make_pair(node.node(), _wtoCycleDepth));
std::make_pair(node.getICFGNode(), _wtoCycleDepth));
}

}; // end class WTOCycleDepthBuilder
Expand Down
151 changes: 70 additions & 81 deletions svf/lib/AE/Svfexe/AbstractInterpretation.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -167,10 +167,9 @@
/// handle global node
void AbstractInterpretation::handleGlobalNode()
{
AbstractState as;
const ICFGNode* node = _icfg->getGlobalICFGNode();
_postAbsTrace[node] = _preAbsTrace[node];
_postAbsTrace[node][SymbolTableInfo::NullPtr] = AddressValue();
_abstractTrace[node] = AbstractState();
_abstractTrace[node][SymbolTableInfo::NullPtr] = AddressValue();
// Global Node, we just need to handle addr, load, store, copy and gep
for (const SVFStmt *stmt: node->getSVFStmts())
{
Expand All @@ -181,18 +180,18 @@
/// get execution state by merging states of predecessor blocks
/// Scenario 1: preblock -----(intraEdge)----> block, join the preES of inEdges
/// Scenario 2: preblock -----(callEdge)----> block
bool AbstractInterpretation::mergeStatesFromPredecessors(const ICFGNode *block)
bool AbstractInterpretation::mergeStatesFromPredecessors(const ICFGNode * icfgNode)
{
std::vector<AbstractState> workList;
AbstractState as;
for (auto& edge: block->getInEdges())
AbstractState preAs;
for (auto& edge: icfgNode->getInEdges())
{
if (_postAbsTrace.find(edge->getSrcNode()) != _postAbsTrace.end())
if (_abstractTrace.find(edge->getSrcNode()) != _abstractTrace.end())
{
const IntraCFGEdge *intraCfgEdge = SVFUtil::dyn_cast<IntraCFGEdge>(edge);
if (intraCfgEdge && intraCfgEdge->getCondition())
{
AbstractState tmpEs = _postAbsTrace[edge->getSrcNode()];
AbstractState tmpEs = _abstractTrace[edge->getSrcNode()];
if (isBranchFeasible(intraCfgEdge, tmpEs))
{
workList.push_back(tmpEs);
Expand All @@ -204,15 +203,14 @@
}
else
{
workList.push_back(_postAbsTrace[edge->getSrcNode()]);
workList.push_back(_abstractTrace[edge->getSrcNode()]);
}
}
else
{

}
}
_preAbsTrace[block].clear();
if (workList.size() == 0)
{
return false;
Expand All @@ -221,9 +219,12 @@
{
while (!workList.empty())
{
_preAbsTrace[block].joinWith(workList.back());
preAs.joinWith(workList.back());
workList.pop_back();
}
// Has ES on the in edges - Feasible block
// update post as
_abstractTrace[icfgNode] = preAs;
return true;
}
}
Expand Down Expand Up @@ -526,20 +527,8 @@
/// handle instructions in svf basic blocks
void AbstractInterpretation::handleSingletonWTO(const ICFGSingletonWTO *icfgSingletonWto)
{
const ICFGNode* node = icfgSingletonWto->node();
const ICFGNode* node = icfgSingletonWto->getICFGNode();
_stat->getBlockTrace()++;
// Get execution states from in edges
if (!mergeStatesFromPredecessors(node))
{
// No ES on the in edges - Infeasible block
return;
}
else
{
// Has ES on the in edges - Feasible block
// Get execution state from in edges
_postAbsTrace[node] = _preAbsTrace[node];
}

std::deque<const ICFGNode*> worklist;

Expand Down Expand Up @@ -573,20 +562,27 @@
{
for (const ICFGWTOComp* wtoNode : wtoComps)
{
if (const ICFGSingletonWTO* node = SVFUtil::dyn_cast<ICFGSingletonWTO>(wtoNode))
{
handleWTOComponent(wtoNode);
}
}

void AbstractInterpretation::handleWTOComponent(const SVF::ICFGWTOComp* wtoNode)
{
if (const ICFGSingletonWTO* node = SVFUtil::dyn_cast<ICFGSingletonWTO>(wtoNode))
{
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if(mergeStatesFromPredecessors(wtonode->getNode()))
handleSingletonWTO(node);

Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Also rename the following:

ICFGSingletonWTO::getNode=> ICFGSingletonWTO::getICFGNode();
ICFGCycleWTO::getNode=> ICFGCycleWTO::getICFGNode();

if (mergeStatesFromPredecessors(node->getICFGNode()))
handleSingletonWTO(node);
}
// Handle WTO cycles
else if (const ICFGCycleWTO* cycle = SVFUtil::dyn_cast<ICFGCycleWTO>(wtoNode))
{
}
// Handle WTO cycles
else if (const ICFGCycleWTO* cycle = SVFUtil::dyn_cast<ICFGCycleWTO>(wtoNode))
{
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if(mergeStatesFromPredecessors(cycle->head()->node()))
handleCycleWTO(node);

if (mergeStatesFromPredecessors(cycle->head()->getICFGNode()))
handleCycleWTO(cycle);
}
// Assert false for unknown WTO types
else
{
assert(false && "unknown WTO type!");
}
}
// Assert false for unknown WTO types
else
{
assert(false && "unknown WTO type!");

Check warning on line 585 in svf/lib/AE/Svfexe/AbstractInterpretation.cpp

View check run for this annotation

Codecov / codecov/patch

svf/lib/AE/Svfexe/AbstractInterpretation.cpp#L585 

Added line #L585 was not covered by tests
}
}

Expand Down Expand Up @@ -656,7 +652,7 @@
}
}
}
_postAbsTrace[retNode] = as;
_abstractTrace[retNode] = as;
}

bool AbstractInterpretation::isDirectCall(const SVF::CallICFGNode *callNode)
Expand All @@ -670,7 +666,7 @@
const SVFFunction *callfun = SVFUtil::getCallee(callNode->getCallSite());
_callSiteStack.push_back(callNode);

_postAbsTrace[callNode] = as;
_abstractTrace[callNode] = as;

ICFGWTO* wto = _funcToWTO[callfun];
handleWTOComponents(wto->getWTOComponents());
Expand All @@ -679,7 +675,7 @@
// handle Ret node
const RetICFGNode *retNode = callNode->getRetICFGNode();
// resume ES to callnode
_postAbsTrace[retNode] = _postAbsTrace[callNode];
_abstractTrace[retNode] = _abstractTrace[callNode];
}

bool AbstractInterpretation::isIndirectCall(const SVF::CallICFGNode *callNode)
Expand All @@ -704,14 +700,14 @@
if (callfun)
{
_callSiteStack.push_back(callNode);
_postAbsTrace[callNode] = as;
_abstractTrace[callNode] = as;

ICFGWTO* wto = _funcToWTO[callfun];
handleWTOComponents(wto->getWTOComponents());
_callSiteStack.pop_back();
// handle Ret node
const RetICFGNode *retNode = callNode->getRetICFGNode();
_postAbsTrace[retNode] = _postAbsTrace[callNode];
_abstractTrace[retNode] = _abstractTrace[callNode];
}
}

Expand All @@ -720,54 +716,47 @@
/// handle wto cycle (loop)
void AbstractInterpretation::handleCycleWTO(const ICFGCycleWTO*cycle)
{
// Get execution states from predecessor nodes
bool is_feasible = mergeStatesFromPredecessors(cycle->head()->node());
if (!is_feasible)
return;
else
{
const ICFGNode* cycle_head = cycle->head()->node();
// Flag to indicate if we are in the increasing phase
bool increasing = true;
// Infinite loop until a fixpoint is reached,
for (u32_t cur_iter = 0;; cur_iter++)
{
// Start widening or narrowing if cur_iter >= widen threshold (widen delay)
if (cur_iter >= Options::WidenDelay())
const ICFGNode* cycle_head = cycle->head()->getICFGNode();
// Flag to indicate if we are in the increasing phase
bool increasing = true;
// Infinite loop until a fixpoint is reached,
for (u32_t cur_iter = 0;; cur_iter++)
{
// Start widening or narrowing if cur_iter >= widen threshold (widen delay)
if (cur_iter >= Options::WidenDelay())
{
// Widen or narrow after processing cycle head node
AbstractState prev_head_state = _abstractTrace[cycle_head];
handleWTOComponent(cycle->head());
AbstractState cur_head_state = _abstractTrace[cycle_head];
if (increasing)
{
// Widen or narrow after processing cycle head node
AbstractState prev_head_state = _postAbsTrace[cycle_head];
handleSingletonWTO(cycle->head());
AbstractState cur_head_state = _postAbsTrace[cycle_head];
if (increasing)
{
// Widening phase
_postAbsTrace[cycle_head] = prev_head_state.widening(cur_head_state);
if (_postAbsTrace[cycle_head] == prev_head_state)
{
increasing = false;
continue;
}
}
else
// Widening phase
_abstractTrace[cycle_head] = prev_head_state.widening(cur_head_state);
if (_abstractTrace[cycle_head] == prev_head_state)
{
// Widening's fixpoint reached in the widening phase, switch to narrowing
_postAbsTrace[cycle_head] = prev_head_state.narrowing(cur_head_state);
if (_postAbsTrace[cycle_head] == prev_head_state)
{
// Narrowing's fixpoint reached in the narrowing phase, exit loop
break;
}
increasing = false;
continue;
}
}
else
{
// Handle the cycle head
handleSingletonWTO(cycle->head());
// Widening's fixpoint reached in the widening phase, switch to narrowing
_abstractTrace[cycle_head] = prev_head_state.narrowing(cur_head_state);
if (_abstractTrace[cycle_head] == prev_head_state)
{
// Narrowing's fixpoint reached in the narrowing phase, exit loop
break;
}
}
// Handle the cycle body
handleWTOComponents(cycle->getWTOComponents());
}
else
{
// Handle the cycle head
handleSingletonWTO(cycle->head());
}
// Handle the cycle body
handleWTOComponents(cycle->getWTOComponents());
}
}

Expand Down
Loading
0