libTriton version 1.0 build 1592
Loading...
Searching...
No Matches
symbolicSimplification.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
8#include <list>
9#include <map>
10
11#include <triton/archEnums.hpp>
12#include <triton/context.hpp>
13#include <triton/exceptions.hpp>
14#include <triton/modesEnums.hpp>
17
18
19
161namespace triton {
162 namespace engines {
163 namespace symbolic {
164
165
167 this->architecture = architecture;
168 this->callbacks = callbacks;
169 }
170
171
173 this->copy(other);
174 }
175
176
177 void SymbolicSimplification::copy(const SymbolicSimplification& other) {
178 this->architecture = other.architecture;
179 this->callbacks = other.callbacks;
180 }
181
182
184 std::list<triton::ast::SharedAbstractNode> worklist;
186
187 if (node == nullptr)
188 throw triton::exceptions::SymbolicSimplification("SymbolicSimplification::simplify(): node cannot be null.");
189
190 if (this->callbacks && this->callbacks->isDefined(triton::callbacks::SYMBOLIC_SIMPLIFICATION)) {
191 snode = this->callbacks->processCallbacks(triton::callbacks::SYMBOLIC_SIMPLIFICATION, node);
192 /*
193 * We use a worklist strategy to avoid recursive calls
194 * and so stack overflow when going through a big AST.
195 */
196 worklist.push_back(snode);
197 while (worklist.size()) {
198 auto ast = worklist.front();
199 worklist.pop_front();
200 bool needs_update = false;
201 for (triton::uint32 index = 0; index < ast->getChildren().size(); index++) {
202 auto child = ast->getChildren()[index];
203 /* Don't apply simplification on nodes like String, Integer, etc. */
204 if (child->getBitvectorSize()) {
205 auto schild = this->callbacks->processCallbacks(triton::callbacks::SYMBOLIC_SIMPLIFICATION, child);
206 ast->setChild(index, schild);
207 needs_update |= !schild->canReplaceNodeWithoutUpdate(child);
208 worklist.push_back(schild);
209 }
210 }
211 if (needs_update) {
212 ast->init(true);
213 }
214 }
215 }
216
217 return snode;
218 }
219
220
222 return this->deadStoreElimination(block, padding);
223 }
224
225
226 triton::arch::BasicBlock SymbolicSimplification::deadStoreElimination(const triton::arch::BasicBlock& block, bool padding) const {
227 std::unordered_map<triton::usize, SharedSymbolicExpression> lifetime;
228 std::map<triton::uint64, triton::arch::Instruction> instructions;
230 triton::arch::BasicBlock in = block;
231
232 if (block.getSize() == 0)
233 return {};
234
235 /* Define a temporary Context */
236 triton::Context tmpctx(this->architecture->getArchitecture());
237
238 /* Synch the concrete state */
239 tmpctx.setConcreteState(*this->architecture);
240
241 /* Execute the block */
242 tmpctx.processing(in);
243
244 /* Get all symbolic registers that were written */
245 for (auto& reg : tmpctx.getSymbolicRegisters()) {
246 for (auto& item : tmpctx.sliceExpressions(reg.second)) {
247 lifetime[item.first] = item.second;
248 }
249 }
250
251 /* Get all symbolic memory cells that were written */
252 for (auto& mem : tmpctx.getSymbolicMemory()) {
253 for (auto& item : tmpctx.sliceExpressions(mem.second)) {
254 lifetime[item.first] = item.second;
255 }
256 }
257
258 /* Keep instructions that build effective addresses (see #1174) */
259 for (auto& inst : in.getInstructions()) {
260 std::set<std::pair<triton::arch::MemoryAccess, triton::ast::SharedAbstractNode>> access;
261 if (inst.isMemoryWrite()) {
262 access = inst.getStoreAccess();
263 }
264 if (inst.isMemoryRead()) {
265 access.insert(inst.getLoadAccess().begin(), inst.getLoadAccess().end());
266 }
267 for (const auto& x : access) {
269 for (const auto& ref : refs) {
270 auto expr = reinterpret_cast<triton::ast::ReferenceNode*>(ref.get())->getSymbolicExpression();
271 auto eid = expr->getId();
272 lifetime[eid] = expr;
273 }
274 if (x.first.getLeaAst()) {
275 auto refs = triton::ast::search(x.first.getLeaAst(), triton::ast::REFERENCE_NODE);
276 for (const auto& ref : refs) {
277 auto expr = reinterpret_cast<triton::ast::ReferenceNode*>(ref.get())->getSymbolicExpression();
278 auto eid = expr->getId();
279 lifetime[eid] = expr;
280 }
281 }
282 }
283 }
284
285 /* Get back the origin assembly of expressions that still alive */
286 for (auto& se : lifetime) {
287 if (se.second->getDisassembly().empty()) {
288 continue;
289 }
290 auto addr = se.second->getAddress();
291 for (auto& inst : in.getInstructions()) {
292 if (inst.getAddress() == addr) {
293 instructions[addr] = inst;
294 break;
295 }
296 }
297 }
298
299 /* Create a new block with sorted instructions */
300 auto lastaddr = in.getFirstAddress();
301 auto nop = tmpctx.getNopInstruction();
302 for (auto& item : instructions) {
303 if (padding) {
304 while (item.second.getAddress() > lastaddr) {
305 out.add(nop);
306 lastaddr += nop.getSize();
307 }
308 }
309 out.add(item.second);
310 lastaddr = item.second.getNextAddress();
311 }
312
313 return out;
314 }
315
316
318 this->copy(other);
319 return *this;
320 }
321
322 }; /* symbolic namespace */
323 }; /* engines namespace */
324}; /*triton namespace */
This is the main Triton Context class.
Definition context.hpp:45
The abstract architecture class.
TRITON_EXPORT triton::arch::architecture_e getArchitecture(void) const
Returns the kind of architecture as triton::arch::architecture_e.
This class is used to represent a basic block.
TRITON_EXPORT triton::usize getSize(void) const
Returns the number of instructions in the block.
TRITON_EXPORT triton::uint64 getFirstAddress(void) const
Returns the first instruction's address.
TRITON_EXPORT void add(const Instruction &instruction)
Add an instruction to the block.
TRITON_EXPORT triton::uint32 getSize(void) const
Returns the size of the instruction.
Reference node.
Definition ast.hpp:789
The callbacks class.
Definition callbacks.hpp:79
TRITON_EXPORT bool isDefined(triton::callbacks::callback_e kind) const
Returns true if the callback is defined.
TRITON_EXPORT triton::ast::SharedAbstractNode processCallbacks(triton::callbacks::callback_e kind, triton::ast::SharedAbstractNode node)
Processes callbacks according to the kind and the C++ polymorphism.
TRITON_EXPORT SymbolicSimplification(triton::arch::Architecture *architecture, triton::callbacks::Callbacks *callbacks=nullptr)
Constructor.
TRITON_EXPORT triton::ast::SharedAbstractNode simplify(const triton::ast::SharedAbstractNode &node) const
Processes all recorded simplifications. Returns the simplified node.
TRITON_EXPORT SymbolicSimplification & operator=(const SymbolicSimplification &other)
Copies a SymbolicSimplification.
The exception class used by symbolic simplifications.
const triton::arch::Instruction nop
AArch64 NOP instruction.
std::shared_ptr< triton::ast::AbstractNode > SharedAbstractNode
Shared Abstract Node.
Definition ast.hpp:59
std::deque< SharedAbstractNode > search(const SharedAbstractNode &node, triton::ast::ast_e match)
Returns a deque of collected matched nodes via a depth-first pre order traversal.
Definition ast.cpp:3710
std::uint32_t uint32
unisgned 32-bits
The Triton namespace.