libTriton version 1.0 build 1592
Loading...
Searching...
No Matches
pathManager.cpp
Go to the documentation of this file.
1
2/*
3** Copyright (C) - Triton
4**
5** This program is under the terms of the Apache License 2.0.
6*/
7
12
13
14
15namespace triton {
16 namespace engines {
17 namespace symbolic {
18
20 : modes(modes), astCtxt(astCtxt) {
21 }
22
23
25 : modes(other.modes), astCtxt(other.astCtxt) {
26 this->pathConstraints = other.pathConstraints;
27 }
28
29
31 this->astCtxt = other.astCtxt;
32 this->modes = other.modes;
33 this->pathConstraints = other.pathConstraints;
34 return *this;
35 }
36
37
39 return this->pathConstraints.size();
40 }
41
42
43 /* Returns the logical conjunction vector of path constraint */
44 const std::vector<triton::engines::symbolic::PathConstraint>& PathManager::getPathConstraints(void) const {
45 return this->pathConstraints;
46 }
47
48
49 /* Returns the logical conjunction vector of path constraint of a given thread */
50 std::vector<triton::engines::symbolic::PathConstraint> PathManager::getPathConstraintsOfThread(triton::uint32 threadId) const {
51 std::vector<triton::engines::symbolic::PathConstraint> ret;
52
53 for (auto& pc : this->pathConstraints) {
54 if (pc.getThreadId() == threadId) {
55 ret.push_back(pc);
56 }
57 }
58
59 return ret;
60 }
61
62
63 /* Returns the logical conjunction vector of path constraint from a given range */
64 std::vector<triton::engines::symbolic::PathConstraint> PathManager::getPathConstraints(triton::usize start, triton::usize end) const {
66
67 if (start > pcsize) {
68 return {};
69 }
70
71 if (start < pcsize && end > pcsize) {
72 std::vector<triton::engines::symbolic::PathConstraint>::const_iterator first = this->pathConstraints.begin() + start;
73 std::vector<triton::engines::symbolic::PathConstraint>::const_iterator last = this->pathConstraints.end();
74 return {first, last};
75 }
76
77 if (start < pcsize && end < pcsize && end > start) {
78 std::vector<triton::engines::symbolic::PathConstraint>::const_iterator first = this->pathConstraints.begin() + start;
79 std::vector<triton::engines::symbolic::PathConstraint>::const_iterator last = this->pathConstraints.begin() + end;
80 return {first, last};
81 }
82
83 throw triton::exceptions::PathManager("PathManager::getPathConstraints(): Invalid items extraction.");
84 }
85
86
87 /* Returns the current path predicate as an AST of logical conjunction of each taken branch. */
89 std::vector<triton::engines::symbolic::PathConstraint>::const_iterator it;
90
91 /* by default PC is T (top) */
92 auto node = this->astCtxt->equal(
93 this->astCtxt->bvtrue(),
94 this->astCtxt->bvtrue()
95 );
96
97 /* Then, we create a conjunction of path constraint */
98 for (it = this->pathConstraints.begin(); it != this->pathConstraints.end(); it++) {
99 node = this->astCtxt->land(node, it->getTakenPredicate());
100 }
101
102 return node;
103 }
104
105
106
107 std::vector<triton::ast::SharedAbstractNode> PathManager::getPredicatesToReachAddress(triton::uint64 addr) const {
108 std::vector<triton::ast::SharedAbstractNode> predicates;
109
110 /* by default PC is T (top) */
111 auto node = this->astCtxt->equal(
112 this->astCtxt->bvtrue(),
113 this->astCtxt->bvtrue()
114 );
115
116 /* Go through all path constraints */
117 for (auto pc = this->pathConstraints.begin(); pc != this->pathConstraints.end(); pc++) {
118 auto branches = pc->getBranchConstraints();
119 bool isMultib = (branches.size() >= 2);
120
121 /* Check if one of the branch constraint may reach the targeted address */
122 for (auto branch = branches.begin(); branch != branches.end(); branch++) {
123 /* if source branch == target, add the current path predicate */
124 if (std::get<1>(*branch) == addr) {
125 predicates.push_back(node);
126 }
127 /*
128 * if dst branch == target, do the conjunction of the current
129 * path predicate and the branch constraint.
130 */
131 if (std::get<2>(*branch) == addr) {
132 predicates.push_back(this->astCtxt->land(node, std::get<3>(*branch)));
133 }
134 /*
135 * if it's a direct branch (call reg, jmp reg) and not a standalone
136 * constraint. Try to reach the targeted address.
137 */
138 if (isMultib == false && std::get<1>(*branch) != 0 && std::get<2>(*branch) != 0) {
139 if (std::get<3>(*branch)->getType() == triton::ast::EQUAL_NODE) {
140 auto ip = std::get<3>(*branch)->getChildren()[0];
141 predicates.push_back(this->astCtxt->land(node, this->astCtxt->equal(ip, this->astCtxt->bv(addr, ip->getBitvectorSize()))));
142 }
143 }
144 } /* branch constraints */
145
146 /* Continue to create the conjunction of the current path predicate */
147 node = this->astCtxt->land(node, pc->getTakenPredicate());
148 } /* path constraint */
149
150 return predicates;
151 }
152
153
154 /* Pushs constraints of a branch instruction to the path predicate. */
157 triton::uint64 srcAddr = 0;
158 triton::uint64 dstAddr = 0;
159 triton::uint32 size = 0;
160
161 triton::ast::SharedAbstractNode pc = expr->getAst();
162 if (pc == nullptr)
163 throw triton::exceptions::PathManager("PathManager::pushPathConstraint(): The node cannot be null.");
164
165 /* If PC_TRACKING_SYMBOLIC is enabled, Triton will track path constraints only if they are symbolized. */
166 if (this->modes->isModeEnabled(triton::modes::PC_TRACKING_SYMBOLIC) && !pc->isSymbolized())
167 return;
168
169 /* If ONLY_ON_TAINTED is enabled and the expression untainted, Triton will skip the storing process. */
170 if (this->modes->isModeEnabled(triton::modes::ONLY_ON_TAINTED) && !expr->isTainted)
171 return;
172
173 /* Basic block taken */
174 srcAddr = inst.getAddress();
175 dstAddr = static_cast<triton::uint64>(pc->evaluate());
176 size = pc->getBitvectorSize();
177
178 if (size == 0)
179 throw triton::exceptions::PathManager("PathManager::pushPathConstraint(): The node size cannot be zero.");
180
181 if (pc->getType() == triton::ast::ZX_NODE)
182 pc = pc->getChildren()[1];
183
184 /* Setting the thread id */
185 pco.setThreadId(inst.getThreadId());
186
187 /* Multiple branches */
188 if (pc->getType() == triton::ast::ITE_NODE) {
189 /* Condition */
190 triton::ast::SharedAbstractNode cond = pc->getChildren()[0];
191
192 /* Then */
193 triton::uint64 bb1 = static_cast<triton::uint64>(pc->getChildren()[1]->evaluate());
195
196 /* Else */
197 triton::uint64 bb2 = static_cast<triton::uint64>(pc->getChildren()[2]->evaluate());
198 triton::ast::SharedAbstractNode bb2pc = this->astCtxt->lnot(cond);
199
200 /* Branch A */
202 bb1 == dstAddr, /* is taken ? */
203 srcAddr, /* from */
204 bb1, /* to */
205 bb1pc /* expr which must be true to take the branch */
206 );
207
208 /* Branch B */
210 bb2 == dstAddr, /* is taken ? */
211 srcAddr, /* from */
212 bb2, /* to */
213 bb2pc /* expr which must be true to take the branch */
214 );
215
216 this->pathConstraints.push_back(pco);
217 }
218
219 /* Direct branch */
220 else {
222 true, /* always taken */
223 srcAddr, /* from */
224 dstAddr, /* to */
225 /* expr which must be true to take the branch */
226 this->astCtxt->equal(pc, this->astCtxt->bv(dstAddr, size))
227 );
228 this->pathConstraints.push_back(pco);
229 }
230 }
231
232
233 /* Pushes constraint created from node to the current path predicate. */
234 void PathManager::pushPathConstraint(const triton::ast::SharedAbstractNode& node, const std::string& comment) {
236
237 if (node->isLogical() == false)
238 throw triton::exceptions::PathManager("PathManager::pushPathConstraint(): The node must be a logical node.");
239
240 /* If PC_TRACKING_SYMBOLIC is enabled, Triton will track path constraints only if they are symbolized. */
241 if (this->modes->isModeEnabled(triton::modes::PC_TRACKING_SYMBOLIC) && !node->isSymbolized())
242 return;
243
245 true, /* always taken */
246 0, /* from: not used */
247 0, /* to: not used */
248 node /* expr which must be true to take the branch */
249 );
250
251 pco.setComment(comment);
252
253 this->pathConstraints.push_back(pco);
254 }
255
256
257 /* Pushes constraint to the current path predicate. */
261
262
263 /* Pops the last constraints added to the path predicate. */
265 if (this->pathConstraints.size())
266 this->pathConstraints.pop_back();
267 }
268
269
270 /* Clears the current path predicate. */
272 this->pathConstraints.clear();
273 }
274
275 }; /* symbolic namespace */
276 }; /* engines namespace */
277}; /*triton namespace */
This class is used to represent an instruction.
TRITON_EXPORT triton::uint64 getAddress(void) const
Returns the address of the instruction.
TRITON_EXPORT triton::uint32 getThreadId(void) const
Returns the thread id of the instruction.
TRITON_EXPORT void setComment(const std::string &comment)
Sets a comment to the path constraint.
TRITON_EXPORT void setThreadId(triton::uint32 tid)
Sets the thread id of the constraint.
TRITON_EXPORT void addBranchConstraint(bool taken, triton::uint64 srdAddr, triton::uint64 dstAddr, const triton::ast::SharedAbstractNode &pc)
Adds a branch to the path constraint.
TRITON_EXPORT triton::ast::SharedAbstractNode getPathPredicate(void) const
Returns the current path predicate as an AST of logical conjunction of each taken branch.
TRITON_EXPORT PathManager(const triton::modes::SharedModes &modes, const triton::ast::SharedAstContext &astCtxt)
Constructor.
TRITON_EXPORT std::vector< triton::ast::SharedAbstractNode > getPredicatesToReachAddress(triton::uint64 addr) const
Returns path predicates which may reach the targeted address.
TRITON_EXPORT const std::vector< triton::engines::symbolic::PathConstraint > & getPathConstraints(void) const
Returns the logical conjunction vector of path constraints.
TRITON_EXPORT triton::usize getSizeOfPathConstraints(void) const
Returns the size of the path constraints.
TRITON_EXPORT PathManager & operator=(const PathManager &other)
Copies a PathManager.
TRITON_EXPORT std::vector< triton::engines::symbolic::PathConstraint > getPathConstraintsOfThread(triton::uint32 threadId) const
Returns the logical conjunction vector of path constraint of a given thread.
TRITON_EXPORT void pushPathConstraint(const triton::arch::Instruction &inst, const triton::engines::symbolic::SharedSymbolicExpression &expr)
Pushs constraints of a branch instruction to the path predicate.
TRITON_EXPORT void clearPathConstraints(void)
Clears the current path predicate.
std::vector< triton::engines::symbolic::PathConstraint > pathConstraints
The logical conjunction vector of path constraints.
TRITON_EXPORT void popPathConstraint(void)
Pops the last constraints added to the path predicate.
The exception class used by the path manager.
std::shared_ptr< triton::ast::AbstractNode > SharedAbstractNode
Shared Abstract Node.
Definition ast.hpp:59
std::shared_ptr< triton::ast::AstContext > SharedAstContext
Shared AST context.
Definition ast.hpp:65
std::shared_ptr< triton::modes::Modes > SharedModes
Shared Modes.
Definition modes.hpp:66
@ PC_TRACKING_SYMBOLIC
[symbolic] Track path constraints only if they are symbolized.
@ ONLY_ON_TAINTED
[symbolic] Perform symbolic execution only on tainted instructions.
std::shared_ptr< triton::engines::symbolic::SymbolicExpression > SharedSymbolicExpression
Shared Symbolic Expression.
Definition ast.hpp:40
std::size_t usize
unsigned MAX_INT 32 or 64 bits according to the CPU.
std::uint64_t uint64
unisgned 64-bits
std::uint32_t uint32
unisgned 32-bits
The Triton namespace.