libTriton version 1.0 build 1590
Loading...
Searching...
No Matches
liftingToDot.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 <algorithm>
9#include <vector>
10#include <string>
11
12#include <triton/astEnums.hpp>
15
16
17
18namespace triton {
19 namespace engines {
20 namespace lifters {
21
23 : astCtxt(astCtxt), symbolic(symbolic) {
24 this->uniqueid = 0;
25 }
26
27
28 std::ostream& LiftingToDot::liftToDot(std::ostream& stream, const triton::engines::symbolic::SharedSymbolicExpression& expr) {
29 /* Slice expressions */
30 this->expressions = this->symbolic->sliceExpressions(expr);
31
32 /* Link abstract node to their symbolic expression to collect information later */
33 for (const auto& se : this->expressions) {
34 this->information[se.second->getAst().get()] = se.second.get();
35 }
36
37 return this->liftToDot(stream, expr->getAst());
38 }
39
40
41 void LiftingToDot::spreadInformation(std::ostream& stream) {
42 for (const auto& i : this->information) {
43 auto* node = i.first;
44 auto* se = i.second;
45
46 stream << "subgraph cluster_" << reinterpret_cast<size_t>(node) << " {" << std::endl;
47 stream << " rank=max;" << std::endl;
48 stream << " bgcolor=lightgrey;" << std::endl;
49 stream << " node [style=filled, color=black, fillcolor=white];" << std::endl;
50 stream << " label=\"" << se->getDisassembly() << "\";" << std::endl;
51 stream << " " << reinterpret_cast<size_t>(node) << ";" << std::endl;
52 stream << "}" << std::endl;
53 }
54 }
55
56
57 void LiftingToDot::defineLegend(std::ostream& stream) {
58 /* Do not create legend if there is no extra information */
59 if (this->expressions.empty())
60 return;
61
62 /* Get all id of symbolic expression */
63 std::vector<triton::usize> ssa;
64 for (const auto& se : this->expressions) {
65 ssa.push_back(se.first);
66 }
67
68 /* Sort ssa form */
69 std::sort(ssa.begin(), ssa.end());
70
71 stream << "legend [fontname=mono style=filled fillcolor=lightyellow color=black shape=box label=\"Instructions involved in the expression" << std::endl << std::endl;
72 for (const auto& id : ssa) {
73 const auto& se = this->expressions[id];
74 stream << se->getDisassembly() << "\\l";
75 }
76 stream << std::endl << "\"];" << std::endl;
77 }
78
79
80 void LiftingToDot::iterateNodes(const triton::ast::SharedAbstractNode& root) {
81 auto ttnodes = triton::ast::childrenExtraction(root, true /* unroll*/, false /* revert */);
82
83 for (auto const& node : ttnodes) {
84 switch (node->getType()) {
85
87 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"MEMORY\"];"});
88 break;
89 }
90
92 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"ASSERT\"];"});
93 break;
94 }
95
97 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BSWAP\"];"});
98 break;
99 }
100
102 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVADD\"];"});
103 break;
104 }
105
107 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVAND\"];"});
108 break;
109 }
110
112 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVASHR\"];"});
113 break;
114 }
115
117 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVLSHR\"];"});
118 break;
119 }
120
122 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVMUL\"];"});
123 break;
124 }
125
127 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVNAND\"];"});
128 break;
129 }
130
132 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVNEG\"];"});
133 break;
134 }
135
137 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVNOR\"];"});
138 break;
139 }
140
142 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVNOT\"];"});
143 break;
144 }
145
147 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVOR\"];"});
148 break;
149 }
150
152 auto RHS = node->getChildren()[1];
153 auto rot = triton::ast::getInteger<std::string>(RHS);
154
155 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVROL\"];"});
156 this->nodes.insert({reinterpret_cast<size_t>(RHS.get()), "[label=\"" + rot + "-bit\"];"});
157 break;
158 }
159
161 auto RHS = node->getChildren()[1];
162 auto rot = triton::ast::getInteger<std::string>(RHS);
163
164 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVROR\"];"});
165 this->nodes.insert({reinterpret_cast<size_t>(RHS.get()), "[label=\"" + rot + "-bit\"];"});
166 break;
167 }
168
170 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSDIV\"];"});
171 break;
172 }
173
175 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSGE\"];"});
176 break;
177 }
178
180 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSGT\"];"});
181 break;
182 }
183
185 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSHL\"];"});
186 break;
187 }
188
190 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSLE\"];"});
191 break;
192 }
193
195 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSLT\"];"});
196 break;
197 }
198
200 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSMOD\"];"});
201 break;
202 }
203
205 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSREM\"];"});
206 break;
207 }
208
210 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVSUB\"];"});
211 break;
212 }
213
215 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVUDIV\"];"});
216 break;
217 }
218
220 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVUGE\"];"});
221 break;
222 }
223
225 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVUGT\"];"});
226 break;
227 }
228
230 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVULE\"];"});
231 break;
232 }
233
235 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVULT\"];"});
236 break;
237 }
238
240 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVUREM\"];"});
241 break;
242 }
243
245 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVXNOR\"];"});
246 break;
247 }
248
250 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"BVXOR\"];"});
251 break;
252 }
253
255 auto LHS = node->getChildren()[0];
256 auto RHS = node->getChildren()[1];
257 auto value = triton::ast::getInteger<triton::uint512>(LHS);
258 auto size = triton::ast::getInteger<triton::uint512>(RHS);
259
260 std::stringstream s;
261 s << "[label=\"0x" << std::hex << value << std::dec << " : " << size << "-bit\" style=filled, color=black, fillcolor=lightblue];";
262
263 this->nodes.insert({reinterpret_cast<size_t>(node.get()), s.str()});
264 break;
265 }
266
268 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"COMPOUND\"];"});
269 break;
270 }
271
273 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"CONCAT\"];"});
274 break;
275 }
276
278 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"DECLARE\"];"});
279 break;
280 }
281
283 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"!=\"];"});
284 break;
285 }
286
288 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"==\"];"});
289 break;
290 }
291
293 auto nhi = node->getChildren()[0];
294 auto nlo = node->getChildren()[1];
295 auto hi = triton::ast::getInteger<std::string>(nhi);
296 auto lo = triton::ast::getInteger<std::string>(nlo);
297
298 this->nodes.insert({reinterpret_cast<size_t>(nhi.get()), "[label=\"hi:" + hi + "\"];"});
299 this->nodes.insert({reinterpret_cast<size_t>(nlo.get()), "[label=\"lo:" + lo + "\"];"});
300 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"EXTRACT\"];"});
301 break;
302 }
303
305 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"FORALL\"];"});
306 break;
307 }
308
310 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"IFF\"];"});
311 break;
312 }
313
315 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"ITE\"];"});
316 break;
317 }
318
320 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"LAND\"];"});
321 break;
322 }
323
325 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"LET\"];"});
326 break;
327 }
328
330 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"LNOT\"];"});
331 break;
332 }
333
335 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"LOR\"];"});
336 break;
337 }
338
340 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"LXOR\"];"});
341 break;
342 }
343
345 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"SELECT\"];"});
346 break;
347 }
348
350 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"STORE\"];"});
351 break;
352 }
353
355 std::stringstream s;
356 s << "[label=\"" << node << "\"];";
357 this->nodes.insert({reinterpret_cast<size_t>(node.get()), s.str()});
358 break;
359 }
360
362 auto LHS = node->getChildren()[0];
363 auto sx = triton::ast::getInteger<std::string>(LHS);
364
365 this->nodes.insert({reinterpret_cast<size_t>(LHS.get()), "[label=\"" + sx + "-bit\"];"});
366 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"SX\"];"});
367 break;
368 }
369
371 auto LHS = node->getChildren()[0];
372 auto zx = triton::ast::getInteger<std::string>(LHS);
373
374 this->nodes.insert({reinterpret_cast<size_t>(LHS.get()), "[label=\"" + zx + "-bit\"];"});
375 this->nodes.insert({reinterpret_cast<size_t>(node.get()), "[label=\"ZX\"];"});
376 break;
377 }
378
380 const triton::ast::AbstractNode* ptr = node.get();
381 while (ptr->getType() == triton::ast::REFERENCE_NODE) {
382 const triton::ast::ReferenceNode* ref = reinterpret_cast<const triton::ast::ReferenceNode*>(ptr);
383 const triton::ast::AbstractNode* next = ref->getSymbolicExpression()->getAst().get();
384 triton::usize refId = ref->getSymbolicExpression()->getId();
385 this->nodes.insert({reinterpret_cast<size_t>(ref), "[label=\"Ref #" + std::to_string(refId) + "\"];"});
386 this->edges.insert({reinterpret_cast<size_t>(ptr), reinterpret_cast<size_t>(next)});
387 ptr = next;
388 }
389 break;
390 }
391
392 default:
393 break;
394 };
395
396 if (node->getType() == triton::ast::BV_NODE) {
397 /* Skip bv node because we have a custom repr */
398 continue;
399 }
400
401 if (node->getType() == triton::ast::ARRAY_NODE) {
402 /* Skip array node because we have a custom repr */
403 continue;
404 }
405
406 /* Link the current node with its children */
407 for (auto const& child : node->getChildren()) {
408 /* Handle variable repr */
409 if (child->getType() == triton::ast::VARIABLE_NODE) {
410 this->handleVariable(node, child);
411 }
412 /* Link by default */
413 else {
414 this->edges.insert({reinterpret_cast<size_t>(node.get()), reinterpret_cast<size_t>(child.get())});
415 }
416 }
417 }
418 }
419
420
421 void LiftingToDot::handleVariable(const triton::ast::SharedAbstractNode& parent, const triton::ast::SharedAbstractNode& child) {
422 /* Variables are displayed on several nodes for a better visibility */
423 this->uniqueid++;
424
425 std::stringstream s;
426 s << "[label=\"" << child << "\" rank=max style=filled, color=black, fillcolor=lightgreen];";
427
428 this->nodes.insert({this->uniqueid, s.str()});
429 this->edges.insert({reinterpret_cast<size_t>(parent.get()), this->uniqueid});
430 }
431
432
433 std::ostream& LiftingToDot::liftToDot(std::ostream& stream, const triton::ast::SharedAbstractNode& root) {
434 /* Prologue of Dot format */
435 stream << "digraph triton {" << std::endl;
436 stream << "ordering=\"out\";" << std::endl;
437 stream << "fontname=mono;" << std::endl;
438
439 /* Spread information */
440 this->defineLegend(stream);
441 this->spreadInformation(stream);
442
443 /* Iterate over nodes */
444 this->iterateNodes(root);
445
446 /* Print nodes */
447 for (const auto& node : this->nodes) {
448 stream << node.first << " " << node.second << std::endl;
449 }
450
451 /* Print edges */
452 for (const auto& edge : this->edges) {
453 stream << edge.first << " -> " << edge.second << std::endl;
454 }
455
456 /* Link the legend to the root node */
457 if (this->expressions.empty() == false) {
458 stream << "legend -> " << reinterpret_cast<size_t>(root.get()) << " [style=dotted];" << std::endl;
459 }
460
461 /* Epilogue of Dot format */
462 stream << "}" << std::endl;
463
464 return stream;
465 }
466
467 }; /* lifters namespace */
468 }; /* engines namespace */
469}; /* triton namespace */
Abstract node.
Definition ast.hpp:68
TRITON_EXPORT triton::ast::ast_e getType(void) const
Returns the type of the node.
Definition ast.cpp:55
Reference node.
Definition ast.hpp:789
TRITON_EXPORT std::ostream & liftToDot(std::ostream &stream, const triton::ast::SharedAbstractNode &node)
Lifts an AST and all its references to Dot format.
TRITON_EXPORT LiftingToDot(const triton::ast::SharedAstContext &astCtxt, triton::engines::symbolic::SymbolicEngine *symbolic)
Constructor.
TRITON_EXPORT std::unordered_map< triton::usize, SharedSymbolicExpression > sliceExpressions(const SharedSymbolicExpression &expr)
Slices all expressions from a given one.
std::shared_ptr< triton::ast::AbstractNode > SharedAbstractNode
Shared Abstract Node.
Definition ast.hpp:59
std::vector< SharedAbstractNode > childrenExtraction(const SharedAbstractNode &node, bool unroll, bool revert)
Returns node and all its children of an AST sorted topologically. If unroll is true,...
Definition ast.cpp:3700
std::shared_ptr< triton::ast::AstContext > SharedAstContext
Shared AST context.
Definition ast.hpp:65
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.
The Triton namespace.