Package Libs ::
Module immvcglib
|
|
1
2
3 """
4 Reads vcg buffer and creates the graph using Immunity Debugger lib
5
6 (c) Immunity, Inc. 2004-2007
7
8
9 U{Immunity Inc.<http://www.immunityinc.com>}
10
11
12 """
13
14 __VERSION__ = '1.2'
15
16
17 """
18 NOTES:
19 need to divide graph in layers
20 save max layer in graph
21 every set of childs [unique and different part vertex] E a different layer
22 save vertex of layer in each layer
23 mark blank path points in each layer [i preffer path points to dummy vertices]
24
25 for layer in layers:
26 move east and west vertices, depending on their type *
27
28 pathfinder(graph)
29 search empy spots where edge lines might travel
30
31
32 a cool thing might be mark the whole graph as east-slanted or west-slanted, according the graph
33 the n east or n west it will move
34
35 if the graph is slanting too much to east from center point, we can start thinking on going west
36 that can be too fuzzy, but will try to make an aproach for human eye
37
38
39 new lib against old lib:
40 orphan vertices from old lib has been solved, now every vertex has at least 1 relationship saved
41 parent<->child type of vertex are correctly relationed now
42
43 """
44
45 import graphclass
46
47 import immlib
48 import debugger
49
50
51
52
53 from random import randint
54
55
56 PALETTE = []
57
58 PALETTE.append("manhattan_edges: yes\r\n")
59 PALETTE.append("layoutalgorithm: mindepth\r\n")
60 PALETTE.append("finetuning: no\r\n")
61 PALETTE.append("layout_downfactor: 100\r\n")
62 PALETTE.append("layout_upfactor: 0\r\n")
63 PALETTE.append("layout_nearfactor: 0\r\n")
64 PALETTE.append("xlspace: 12\r\n")
65 PALETTE.append("yspace: 30\r\n")
66 PALETTE.append("colorentry 32: 0 0 0\r\n")
67 PALETTE.append("colorentry 33: 0 0 255\r\n")
68 PALETTE.append("colorentry 34: 0 0 255\r\n")
69 PALETTE.append("colorentry 35: 128 128 128\r\n")
70 PALETTE.append("colorentry 36: 128 128 128\r\n")
71 PALETTE.append("colorentry 37: 0 0 128\r\n")
72 PALETTE.append("colorentry 38: 0 0 128\r\n")
73 PALETTE.append("colorentry 39: 0 0 255\r\n")
74 PALETTE.append("colorentry 40: 0 0 255\r\n")
75 PALETTE.append("colorentry 41: 0 0 128\r\n")
76 PALETTE.append("colorentry 42: 0 128 0\r\n")
77 PALETTE.append("colorentry 43: 0 255 0\r\n")
78 PALETTE.append("colorentry 44: 0 128 0\r\n")
79 PALETTE.append("colorentry 45: 255 128 0\r\n")
80 PALETTE.append("colorentry 46: 0 128 0\r\n")
81 PALETTE.append("colorentry 47: 128 128 255\r\n")
82 PALETTE.append("colorentry 48: 255 0 0\r\n")
83 PALETTE.append("colorentry 49: 128 128 0\r\n")
84 PALETTE.append("colorentry 50: 1 1 1\r\n")
85 PALETTE.append("colorentry 51: 192 192 192\r\n")
86 PALETTE.append("colorentry 52: 0 0 255\r\n")
87 PALETTE.append("colorentry 53: 0 0 255\r\n")
88 PALETTE.append("colorentry 54: 0 0 255\r\n")
89 PALETTE.append("colorentry 55: 128 128 128\r\n")
90 PALETTE.append("colorentry 56: 128 128 255\r\n")
91 PALETTE.append("colorentry 57: 0 128 0\r\n")
92 PALETTE.append("colorentry 58: 0 0 128\r\n")
93 PALETTE.append("colorentry 59: 0 0 255\r\n")
94 PALETTE.append("colorentry 60: 128 0 128\r\n")
95 PALETTE.append("colorentry 61: 0 128 0\r\n")
96 PALETTE.append("colorentry 62: 0 128 0\r\n")
97 PALETTE.append("colorentry 63: 0 128 64\r\n")
98 PALETTE.append("colorentry 64: 0 0 128\r\n")
99 PALETTE.append("colorentry 65: 0 0 128\r\n")
100 PALETTE.append("colorentry 66: 255 0 255\r\n")
101 PALETTE.append("colorentry 67: 128 128 0\r\n")
102 PALETTE.append("colorentry 68: 0 0 128\r\n")
103 PALETTE.append("colorentry 69: 0 0 255\r\n")
104 PALETTE.append("colorentry 70: 0 0 128\r\n")
105 PALETTE.append("colorentry 71: 0 0 255\r\n")
106 PALETTE.append("colorentry 72: 0 0 0\r\n")
107 PALETTE.append("colorentry 73: 255 255 255\r\n")
108 PALETTE.append("colorentry 74: 192 192 192\r\n")
109 PALETTE.append("colorentry 75: 0 255 255\r\n")
110 PALETTE.append("colorentry 76: 0 0 0\r\n")
111 PALETTE.append("colorentry 77: 128 0 0\r\n")
112 PALETTE.append("colorentry 78: 128 128 128\r\n")
113 PALETTE.append("colorentry 79: 128 128 0\r\n")
114 PALETTE.append("colorentry 80: 255 0 255\r\n")
115 PALETTE.append("colorentry 81: 0 0 0\r\n")
116 PALETTE.append("colorentry 82: 0 0 255\r\n")
117 PALETTE.append("colorentry 83: 0 0 0\r\n")
118
120
122 """ Init the graphing object """
123 self.imm = imm
124 self.callTree = imm.getCallTree(address)
125 self.address = address
126
128 """ return a call ordered list of nodes """
129
130
131
132
133
134
135
136
137
138 TARGET = []
139 PARENTS = []
140 CHILDREN = []
141
142 for call in self.callTree:
143 if call[3]:
144 if "0x%X"%call[3] not in TARGET:
145 TARGET.append("0x%X"% call[3])
146 if call[4]:
147 if "0x%X"%call[4] not in PARENTS:
148 PARENTS.append("0x%X"% call[4])
149 if call[5]:
150 if "0x%X"%call[5] not in CHILDREN:
151 CHILDREN.append("0x%X"% call[5])
152
153 return TARGET, PARENTS, CHILDREN
154
155 - def makeNode(self, title, content = "", vertical_order = 0):
156 """ build a simple node VCG buf entry """
157 node = []
158 node.append('node: {\r\n')
159 node.append('title: "%s"\r\n'% title)
160 node.append('vertical_order: %d\r\n'% vertical_order)
161 if content != "":
162 node.append('label: "\x0c69%s\x0c31\r\n%s"\r\n'% (title, content))
163 else:
164 node.append('label: "\x0c69%s\x0c31\r\n'% title)
165 node.append('}\r\n')
166 return node
167
168 - def makeEdge(self, source, target, label = "", color = "green"):
169 """ work out the relations between the boxies """
170
171 edge = []
172
173 edge.append('edge: {\r\n')
174 edge.append('sourcename: "%s"\r\n'% source)
175 edge.append('targetname: "%s"\r\n'% target)
176 if label != "":
177 edge.append('label: "%s"\r\n'% label)
178 edge.append('color: %s\r\n'% color)
179 edge.append('}\r\n')
180
181 return edge
182
183 - def makeVCG(self, title, nodes = [], edges = []):
184 """ build a simple node tree VCG buffer """
185 vcg = []
186
187 vcg.append('graph: {\r\n')
188
189 vcg.append('title: "%s"\r\n'% title)
190
191
192 for line in PALETTE:
193 vcg.append(line)
194
195
196 for node in nodes:
197 for line in node:
198 vcg.append(line)
199
200
201 for edge in edges:
202 for line in edge:
203 vcg.append(line)
204
205
206 vcg.append('}\r\n')
207
208 return vcg
209
211 """ pop up a call tree graph for this address """
212 TARGET, PARENTS, CHILDREN = self.orderNodesFromTree()
213
214 nodes = []
215 unique = []
216
217 for title in TARGET+PARENTS+CHILDREN:
218 if title not in unique:
219 unique.append(title)
220
221
222 for title in unique:
223
224 if title in PARENTS:
225 order = 0
226 if title in TARGET:
227 order = 1
228 if title in CHILDREN:
229 order = 2
230
231
232 node_content = self.imm.decodeAddress(int(title, 16))
233 nodes.append(self.makeNode(title, content = node_content, vertical_order = order))
234
235 edges = []
236
237 target = TARGET[0]
238
239 for parent in PARENTS:
240
241 edges.append(self.makeEdge(parent, target))
242 for child in CHILDREN:
243 edges.append(self.makeEdge(target, child))
244
245
246 vcg = self.makeVCG("Call Graph <-for-> %s [0x%X]"% (self.imm.decodeAddress(self.address), self.address), nodes, edges)
247
248
249 fd = open("CALLTREE.vcg", "w")
250 for line in vcg:
251 fd.write(line)
252 fd.close()
253
254
255 generateGraphFromBuf(vcg)
256
258 """ recursive VCG parser """
259
261 """ pre-process our shiznit """
262 self.sep = '!SEP!'
263 self.DEBUG = False
264
265
266
267
268
269 self.MODETOKENS = [ 'graph:', 'node:', 'edge:' ]
270
271 self.VARTOKENS = [ 'title:', 'label:', 'vertical_order:', 'horizontal_order:', 'manhattan_edges:', 'layoutalgorithm:' ]
272 self.VARTOKENS += [ 'finetuning:', 'layout_downfactor:', 'layout_upfactor:' ]
273 self.VARTOKENS += [ 'layout_nearfactor:', 'xlspace:', 'yspace:' ]
274 self.VARTOKENS += [ 'sourcename:', 'targetname:', 'color:' ]
275
276
277 cleanVCG = []
278
279 sMode = False
280
281 for line in vcgList:
282
283
284 if line[:2] == "//":
285 continue
286
287 clean = []
288 lineList = list(line)
289
290 for c in lineList:
291 if c == '"':
292
293 sMode = not sMode
294
295 if sMode == True:
296 clean.append(c)
297 else:
298 if c in ['\r']:
299 continue
300 if c in ['\n', ' ']:
301 clean.append(self.sep)
302 else:
303 clean.append(c)
304
305 line = ''.join(clean)
306
307 if len(line):
308 cleanVCG.append(line)
309
310 self.vcgText = ''.join(cleanVCG)
311
312 self.nodeList = []
313 self.edgeList = []
314 self.graphList = []
315
316 self.lastMode = ""
317
319 """ raise an error exception """
320 raise error
321
322 - def reParse(self, vcgItems, mode = ""):
323 """ used for recursive parse """
324
325
326 if self.DEBUG:
327 logger = immlib.Debugger()
328 logger.Log(repr(vcgItems))
329
330
331 if vcgItems:
332
333 if vcgItems[0] in self.MODETOKENS:
334 mode = vcgItems[0]
335 self.lastMode = mode
336 self.reParse(vcgItems[1:], mode = mode)
337
338 elif vcgItems[0] in self.VARTOKENS or 'colorentry' in vcgItems[0]:
339
340
341 if 'colorentry' in vcgItems[0]:
342 vcgItems[0] = " ".join([vcgItems[0], vcgItems[1]])
343 del vcgItems[1]
344
345 args = []
346 key = vcgItems[0]
347
348 i = 1
349 while vcgItems[i] not in self.VARTOKENS and vcgItems[i] not in self.MODETOKENS and 'colorentry' not in vcgItems[i]:
350 if '}' in vcgItems[i]:
351 break
352 args.append(vcgItems[i])
353 i += 1
354
355 if mode == 'node:' and len(self.nodeList):
356 self.nodeList[len(self.nodeList)-1][key] = " ".join(args)
357
358 if mode == 'edge:' and len(self.edgeList):
359 self.edgeList[len(self.edgeList)-1][key] = " ".join(args)
360
361 if mode == 'graph:' and len(self.graphList):
362 self.graphList[len(self.graphList)-1][key] = " ".join(args)
363
364 self.reParse(vcgItems[i:], mode = self.lastMode)
365
366 elif '{' in vcgItems[0]:
367
368
369 if mode == 'graph:':
370 self.graphList.append({})
371 elif mode == 'node:':
372 self.nodeList.append({})
373 elif mode == 'edge:':
374 self.edgeList.append({})
375
376 self.reParse(vcgItems[1:], mode = mode)
377
378
379 elif '}' in vcgItems[0]:
380 self.reParse(vcgItems[1:], mode = '')
381
382
383 return self.graphList, self.nodeList, self.edgeList
384
386 """ Parse a VCG graph .. not 100% proper .. but proper enough """
387 vcgItems = self.vcgText.split(self.sep)
388 return self.reParse(vcgItems)
389
391 """ test our new VCG parsing logic """
392 vcgList = []
393
394 fd = open(path, 'r')
395 for line in fd:
396 vcgList.append(line)
397 fd.close()
398
399 parser = ParseVCGList(vcgList)
400
401
402 graph, nodes, edges = parser.parseGraph()
403
404 logger = immlib.Debugger()
405
406 logger.Log("GRAPH:")
407 for gDict in graph:
408 for key in gDict:
409 logger.Log("KeyVal: %s"% key)
410 logger.Log(repr(gDict[key]))
411 logger.Log("EDGES:")
412 for eDict in edges:
413 for key in eDict:
414 logger.Log("KeyVal: %s"% key)
415 logger.Log(repr(eDict[key]))
416 logger.Log("NODES:")
417 for nDict in nodes:
418 for key in nDict:
419 logger.Log("KeyVal: %s"% key)
420 logger.Log(repr(nDict[key]))
421
422 return
423
424
426
427
428
429
430 parser = ParseVCGList(buf)
431
432 GRAPH, NODES, EDGES = parser.parseGraph()
433
434
435 title = GRAPH[0]['title:']
436
437
438 try:
439
440 start_address = title.split("(")[1][:8]
441 except:
442 start_address = "0xcafebabe"
443
444
445 Draw = graphclass.Draw()
446
447 DrawHandler = Draw.createGraphWindow(title, start_address)
448 G = graphclass.Graph()
449
450 G.setHandler(DrawHandler)
451
452
453 vertices = createVertexList(NODES, DrawHandler)
454
455
456 for vertex in vertices:
457 vertex.calculateAbsoluteSize(vertex.getVertexBuffer())
458
459 G.addVertices(vertices)
460
461 createAdjacencyList(G, vertices, EDGES)
462
463 """
464 at this point we have:
465 * draw instance [graph window inside debugger]
466 * graph instance
467 * vertex instances list
468 * edges lists + properties [true, false, direct]
469 * vertex instances list
470 * buffers
471 * absolute sizes
472 * adj lists of in and out edges
473 we now need to iterate our lists and define the best way to place
474 vertices
475 """
476
477
478 firstAttemptToPlace(vertices)
479
480 finalAttemptToPlace(vertices)
481
482 adjustStartCoords(vertices, G)
483
484 G.setBitSize(vertices)
485
486 edgelist = pathFinder(vertices)
487
488 drawEdges(edgelist, DrawHandler)
489
490 drawVertices(vertices)
491
492
493
494 G.splashTime()
495
496
498 """ generates a VCG given a function address """
499 try:
500 vcg = generateVCG(address)
501 except:
502 print "[XXX] Error generating VCG"
503 return
504
505
506 generateGraphFromBuf(vcg)
507
508
516
517
518
520 """ iterate vcg file to get vertex list and vertices's buffers"""
521 vertices = []
522
523 for node in nodes:
524 vertexbuf = []
525 v = graphclass.Vertex(handler)
526
527 logger = immlib.Debugger()
528
529 label = node['label:']
530 content = label[label.find("\x0c31") + 3:]
531 content = content.replace('"', '')
532 label = label[label.find("\x0c69") + 3 : label.find("\x0c31")]
533
534 v.setLabel(label)
535
536 title = node['title:']
537 v.setName(title)
538 vertices.append(v)
539
540 vertexbuf += [v.getLabel()]
541 for key in node:
542 if key not in ['vertical_order:', 'title:', 'label:']:
543 nodeLine = node[key]
544 vertexbuf += [' '.join([key, node[key]])]
545
546
547 content = content.split('\r\n')
548 for line in content:
549
550 if len(line):
551 vertexbuf += [line]
552
553 v.setVertexBuffer(vertexbuf)
554
555 return vertices
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
580
581
582
583
584
585
586 for a in range(1,15):
587 for vertex in vertices:
588 checkForPlacedVertex(vertex,vertices)
589
591 templist=edgelist
592 vertexlist=[]
593 (xl,yl,x2l,y2l,color) = edgelist[-1]
594 for vertex in vertices:
595 (x,y,x2,y2) = vertex.getCoords()
596
597
598 if xl >= x-5 and xl <= x2+5 and yl < y and y2l > y:
599 vertexlist.append(vertex)
600
601 return applyDummyPathsH2South(vertexlist,edgelist)
602
604 templist=edgelist
605 vertexlist=[]
606 (xl,yl,x2l,y2l,color) = edgelist[-1]
607 for vertex in vertices:
608 (x,y,x2,y2) = vertex.getCoords()
609 if xl >= x-5 and xl <= x2+5 and yl > y and y2l < y:
610 vertexlist.append(vertex)
611
612 return applyDummyPathsH2North(vertexlist,edgelist)
613
614 """
615 NOTES:
616
617 if i use an edge templist i might be able to grep off
618 the non usefull bendings:
619
620 --|
621 __|
622
623 =>
624
625 |
626 |
627
628 another nice thing would be to check wheter im nearest to east or west of
629 the overlapped vertex, so i can decide where to escape
630 """
631
632
634 (xl,yl,x2l,y2l,color) = edgelist[-1]
635 vertexlist.sort()
636 for vertex in vertexlist:
637 (x,y,x2,y2) = vertex.getCoords()
638 cm = randint(-20,-10)
639
640 if y2l-5 > y and y2l <= y2 and len(vertexlist) == 1:
641 (tx,ty,tx2,ty2,color) = edgelist[-1]
642 edgelist[-1] = (( tx,ty,tx2, y-10, color))
643 else:
644 if vertexlist.index(vertex) == 0:
645 edgelist[-1] = ((xl,yl,xl,y-10,color))
646 else:
647 pass
648
649
650 edgelist.append((xl,y-10,x-10+cm,y-10,color))
651 edgelist.append((x-10+cm,y-10,x-10+cm,y2+10,color))
652 if vertex != vertexlist[-1]:
653 edgelist.append((x-10+cm,y2+10,xl,y2+10,color))
654 endx=xl
655 endy=y2+10
656
657
658 return edgelist
659
661 (xl,yl,x2l,y2l,color) = edgelist[-1]
662 vertexlist.sort()
663 for vertex in vertexlist:
664 (x,y,x2,y2) = vertex.getCoords()
665 if y2l > y and y2l <= y2 and len(vertexlist) == 1:
666 (tx,ty,tx2,ty2,color) = edgelist[-1]
667 edgelist[-1] = (( tx,ty,tx2, y-10, color))
668 else:
669 if vertexlist.index(vertex) == 0:
670 edgelist[-1] = ((xl,yl,xl,y-10,color))
671 else:
672 pass
673 edgelist.append((endx,endy,endx,y-10,color))
674
675 if x2 - xl < xl -x:
676 cm = randint(-5,5)
677 edgelist.append((xl,y-10,x2+20+cm,y-10,color))
678 edgelist.append((x2+20+cm,y-10,x2+20+cm,y2+10,color))
679 if vertex != vertexlist[-1]:
680 edgelist.append((x2+20+cm,y2+10,xl,y2+10,color))
681 endx=xl
682 endy=y2+10
683 else:
684 cm = randint(-20,-10)
685 edgelist.append((xl,y-10,x-10+cm,y-10,color))
686 edgelist.append((x-10+cm,y-10,x-10+cm,y2+10,color))
687 if vertex != vertexlist[-1]:
688 edgelist.append((x-10+cm,y2+10,xl,y2+10,color))
689 endx=xl
690 endy=y2+10
691
692
693
694 return edgelist
695
696
698 (xl,yl,x2l,y2l,color) = edgelist[-1]
699 vertexlist.sort()
700 vertexlist.reverse()
701 for vertex in vertexlist:
702 (x,y,x2,y2) = vertex.getCoords()
703 if y2l > y and y2l <= y2 and len(vertexlist) == 1:
704 pass
705
706
707 else:
708 if vertexlist.index(vertex) == 0:
709 edgelist[-1] = ((xl,yl,xl,y2+10,"Blue"))
710 else:
711 pass
712 edgelist.append((endx,endy,endx,y-10,"Aqua"))
713
714
715 cm = randint(-5,5)
716 edgelist.append((xl,y2+10,x2+20+cm,y2+10,"red"))
717 edgelist.append((x2+20+cm,y2+10,x2+20+cm,y-10,"Yellow"))
718 if vertex != vertexlist[-1]:
719 edgelist.append((x2+20+cm,y2+10,xl,y2+10,"Maroon"))
720 endx=xl
721 endy=y-10
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736 return edgelist
737
739 (xl,yl,x2l,y2l,color) = edgelist[-1]
740 vertexlist.sort()
741 vertexlist.reverse()
742 for vertex in vertexlist:
743 (x,y,x2,y2) = vertex.getCoords()
744 if y2l > y and y2l <= y2 and len(vertexlist) == 1:
745 (tx,ty,tx2,ty2,color) = edgelist[-1]
746 edgelist[-1] = (( tx,ty,tx2, y-10, color))
747 if vertexlist.index(vertex) == 0:
748 edgelist[-1] = ((xl,yl,xl,y2+10,color))
749 else:
750 edgelist.append((endx,endy,endx,y2+10,color))
751
752 cm = randint(-5,5)
753 if x2 - xl < xl -x:
754 edgelist.append((xl,y2+10,x2+20+cm,y2+10,color))
755 edgelist.append((x2+20+cm,y2+10,x2+20+cm,y-10,color))
756 if vertex != vertexlist[-1]:
757 edgelist.append((x2+20+cm,y-10,xl,y-10,color))
758 endx=xl
759 endy=y-10
760 else:
761 edgelist.append((xl,y2+10,x-20+cm,y2+10,color))
762 edgelist.append((x-20+cm,y2+10,x-20+cm,y-10,color))
763 if vertex != vertexlist[-1]:
764 edgelist.append((x-20+cm,y-10,xl,y-10,color))
765 endx=xl
766 endy=y-10
767
768 return edgelist
769
770
772 return
773 (xl,yl,x2l,y2l,a) = edgelist[-1]
774 for vertex in vertices:
775 (x,y,x2,y2) = vertex.getCoords()
776 if xl > x or yl < x2 and x2l > y2:
777 pass
778 else:
779 f=open("ea.txt","w+")
780 f.write("quilombo %s\n" % str(x))
781 f.close()
782 return edgelist
783
785 """find edge's path
786 To find an endge path we start joining two vertex with 3 basic strokes,
787 A -> B -> C
788 after placing each of this basci strokes we check if it is not overlapping a vertex, if so
789 we decide a alternate path based on dummy blank points
790 A -> A' -> A'' -> B -> C
791 where A' (x2,y2) is the original A (x2,y2) so the next basic stroke B, knows how
792 to keep going
793
794 """
795 """note on adding edges to edgelist:
796 since edgelist will self modify with other functions if pretty important
797 to add relative values and not absolute values.
798 ie: before adding a new edge check the last one, and the new values must be relative to edgelist[-1]
799 """
800 edgelist=[]
801 f=open("edges.txt","w")
802 for vertex in vertices:
803 (x,y,x2,y2) = vertex.getCoords()
804 parentw=vertex.getWidth()
805 parenth=vertex.getHeight()
806 outadj=vertex.getOutAdj()
807 for child in outadj:
808 if child[1] == 1:
809 for vertexchild in vertices:
810 if child[0] == vertexchild.getName():
811 if vertex.getName() == vertexchild.getName():
812
813 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,parenth+y+5,"darkgreen"))
814 edgelist.append((parentw*1/4+x+chaosmov,parenth+y+5,x-14,parenth+y+5,"darkgreen"))
815 edgelist.append((x-14,parenth+y+5,x-14,y-10,"darkgreen"))
816 edgelist.append((x-14,y-10,parentw*1/4+x+chaosmov,y-10,"darkgreen"))
817 edgelist.append((parentw*1/4+x+chaosmov,y-10,parentw*1/4+x+chaosmov,y-1,"darkgreen"))
818 else:
819 (xch,ych,x2ch,y2ch) = vertexchild.getCoords()
820 childw=vertexchild.getWidth()
821
822
823
824
825
826 f.write("Edge true from %s (%d,%d,%d,%d) to %s (%d,%d,%d,%d)\n" % (vertex.getName(),x,y,x2,y2,vertexchild.getName(),xch,ych,x2ch,y2ch))
827 chaosmov=randint(-5, 0)
828 if (parenth+y-1) > ych-2-25:
829 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,parenth+y+5,"Blue"))
830 edgelist.append((parentw*1/4+x+chaosmov,parenth+y+5,x-14,parenth+y+5,"Blue"))
831 edgelist.append((x-14,parenth+y+5,x-14,ych-2-20+chaosmov,"Blue"))
832 edgelist=searchForDummyPathsH2North(edgelist,vertices)
833 (tx,ty,tx2,ty2,color) = edgelist[-1]
834 edgelist.append((tx2,ty2,xch+(childw*1/2)+chaosmov,ty2,color))
835 (tx,ty,tx2,ty2,color) = edgelist[-1]
836 if ty2 < y2ch:
837 edgelist.append((tx2,ty2,tx2,ych-2,color))
838 else:
839 edgelist.append((tx2,ty2,tx2,y2ch-2,color))
840
841 else:
842
843 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,ych-2-25+chaosmov,"darkgreen"))
844 edgelist=searchForDummyPathsH2South(edgelist,vertices)
845
846 (tx,ty,tx2,ty2,color) = edgelist[-1]
847 edgelist.append((tx,ty2,xch+(childw*1/2)+chaosmov,ty2,color))
848 (tx,ty,tx2,ty2,color) = edgelist[-1]
849 if ty2 < y2ch:
850 edgelist.append((tx2,ty2,tx2,ych-2,color))
851 else:
852 edgelist.append((tx2,ty2,tx2,y2ch-2,color))
853 edgelist.append((tx2,ty2,tx2,ych-2,color))
854
855
856 addEndPointToEdge(edgelist)
857
858
859 elif child[1] == 2 :
860 for vertexchild in vertices:
861 if child[0] == vertexchild.getName():
862 if vertex.getName() == vertexchild.getName():
863
864 debugger.Error("loop false")
865 edgelist.append((parentw*1/4+x+chaosmov,parenth+y-1,parentw*1/4+x+chaosmov,parenth+y+5,"red"))
866 edgelist.append((parentw*1/4+x+chaosmov,parenth+y+5,x-14,parenth+y+5,"red"))
867 edgelist.append((x-14,parenth+y+5,x-14,y-10,"red"))
868 edgelist.append((x-14,y-10,parentw*1/4+x+chaosmov,y-10,"red"))
869 edgelist.append((parentw*1/4+x+chaosmov,y-10,parentw*1/4+x+chaosmov,y-1,"red"))
870
871 else:
872 (xch,ych,x2ch,y2ch) = vertexchild.getCoords()
873 childw=vertexchild.getWidth()
874 chaosmov=randint(0, 5)
875 if (parenth+y-1) > ych-2-25:
876 edgelist.append((parentw*3/4+x+chaosmov,parenth+y-1,parentw*3/4+x+chaosmov,parenth+y+5,"Blue"))
877 edgelist.append((parentw*3/4+x+chaosmov,parenth+y+5,x2+14,parenth+y+5,"Blue"))
878 edgelist.append((x2+14,parenth+y+5,x2+14,ych-2-20+chaosmov,"Blue"))
879 edgelist=searchForDummyPathsH2North(edgelist,vertices)
880 (tx,ty,tx2,ty2,color) = edgelist[-1]
881 edgelist.append((tx2,ty2,xch+(childw*1/2)+chaosmov,ty2,color))
882 (tx,ty,tx2,ty2,color) = edgelist[-1]
883 if ty2 < y2ch:
884 edgelist.append((tx2,ty2,tx2,ych-2,color))
885 else:
886 edgelist.append((tx2,ty2,tx2,y2ch-2,color))
887 else:
888 edgelist.append((parentw*3/4+x+chaosmov,parenth+y-1,parentw*3/4+x+chaosmov,ych-2-25+chaosmov,"red"))
889 edgelist=searchForDummyPathsH2South(edgelist,vertices)
890 (tx,ty,tx2,ty2,color) = edgelist[-1]
891 edgelist.append((tx,ty2,xch+(childw*1/2)+chaosmov,ty2,color))
892 (tx,ty,tx2,ty2,color) = edgelist[-1]
893 edgelist.append((tx2,ty2,tx2,ych-2,color))
894 edgelist=searchForDummyPathsH2South(edgelist,vertices)
895
896 addEndPointToEdge(edgelist)
897
898
899
900
901
902
903 elif child[1] == 0 :
904 for vertexchild in vertices:
905 if child[0] == vertexchild.getName():
906 if vertex.getName() == vertexchild.getName():
907
908 debugger.Error("loop direct")
909 else:
910 (xch,ych,x2ch,y2ch) = vertexchild.getCoords()
911 f.write("Edge direct from %s (%d,%d,%d,%d) to %s (%d,%d,%d,%d)\n" % (vertex.getName(),x,y,x2,y2,vertexchild.getName(),xch,ych,x2ch,y2ch))
912 chaosmov=randint(-5, 5)
913 chaosmovlastx=randint(-20,20)
914 childw=vertexchild.getWidth()
915 if (parenth+y-1) > ych-2-25:
916 edgelist.append((parentw*1/2+x+chaosmov,parenth+y-1,parentw*1/2+x+chaosmov,parenth+y+5,"Blue"))
917 edgelist.append((parentw*1/2+x+chaosmov,parenth+y+5,x-10,parenth+y+5,"Blue"))
918 edgelist.append((x-10,parenth+y+5,x-10,ych-2-20+chaosmov,"Blue"))
919 edgelist=searchForDummyPathsH2North(edgelist,vertices)
920 (tx,ty,tx2,ty2,color) = edgelist[-1]
921 edgelist.append((tx2,ty2,xch+(childw*1/2)+chaosmov,ty2,color))
922 (tx,ty,tx2,ty2,color) = edgelist[-1]
923 if ty2 < y2ch:
924 edgelist.append((tx2,ty2,tx2,ych-2,color))
925 else:
926 edgelist.append((tx2,ty2,tx2,y2ch-2,color))
927
928 else:
929 edgelist.append((parentw*1/2+x+chaosmov,parenth+y-1,parentw*1/2+x+chaosmov,ych-2-25+chaosmov,"Black"))
930 edgelist=searchForDummyPathsH2South(edgelist,vertices)
931 (tx,ty,tx2,ty2,color) = edgelist[-1]
932 edgelist.append((tx,ty2,xch+(childw*1/2)+chaosmov,ty2,color))
933 (tx,ty,tx2,ty2,color) = edgelist[-1]
934 edgelist.append((tx2,ty2,tx2,ych-2,color))
935
936
937
938
939 addEndPointToEdge(edgelist)
940
941
942
943 return edgelist
944
946 (endx,endy,endx2,endy2,color)=edgelist[-1]
947 edgelist.append((endx2,endy2,endx2,endy2+2,color))
948 edgelist.append((endx2,endy2,endx2,endy2-2,color))
949 edgelist.append((endx2,endy2+2,endx2+2,endy2+2,color))
950 edgelist.append((endx2,endy2+2,endx2-2,endy2+2,color))
951 edgelist.append((endx2+2,endy2-2,endx2+2,endy2+3,color))
952 edgelist.append((endx2-2,endy2-2,endx2-2,endy2+3,color))
953 edgelist.append((endx2-2,endy2-2,endx2+2,endy2-2,color))
954
955 return edgelist
956
971
973 for line in edgelist:
974 linej=graphclass.Line(handler)
975 x_pos=line[0]
976 y_pos=line[1]
977 x_to=line[2]
978 y_to=line[3]
979 color=line[4]
980 linej.draw(x_pos,y_pos,x_to,y_to,color)
981 return
982
983
984
986 """ creates a directed adjacency list for every vertex """
987 for edge in edges:
988 source = edge['sourcename:']
989 target = edge['targetname:']
990
991 type = 0
992 if 'label:' in edge:
993 if 'TRUE' in edge['label:'].upper():
994 type = 1
995 if 'FALSE' in edge['label:'].upper():
996 type = 2
997
998 G.addEdges((source, target, type))
999
1000 for vertex in vertices:
1001 if vertex.getName() == source:
1002 vertex.addOutAdj(target, type)
1003 if vertex.getName() == target:
1004 vertex.addInAdj(source)
1005 return
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1031
1032
1033
1034 return
1035
1037 """First attempt to place vertices
1038 We are going to suppose Graph is planar and
1039 attempt to place vertices directly,
1040 in real world this wont happens, but at least
1041 we'll have temptative coords for every vertex"""
1042
1043 for vertex in vertices:
1044 if vertices.index(vertex) == 0 :
1045 (x,y)=vertex.getStartCoords()
1046 vertex.setRelPos(x,y)
1047 (x,y,x2,y2)=vertex.getCoords()
1048 vertex.setPlaced()
1049 (x,y)=vertex.getRelPos()
1050
1051 outadj=vertex.getOutAdj()
1052
1053 if len(outadj) > 0:
1054 for child in outadj:
1055 if child[1] == 1:
1056 for vertexchild in vertices:
1057 if child[0] == vertexchild.getName() and vertexchild.isPlaced() == False:
1058 (xp,yp)=vertex.getRelPos()
1059 if xp == 0:
1060
1061 """Note: usually we dont want to go back from Point of No Return,
1062 but in this special case of vertex, we need to do it.
1063 we should have in mind, that overlapping might occur, but we wont move south , instead
1064 we need to move east/west"""
1065 inadj=vertex.getInAdj()
1066 for parent in inadj:
1067 for parentvertex in vertices:
1068 if parent == parentvertex.getName():
1069 (xp,yp)=parentvertex.getRelPos()
1070 y=yp+parentvertex.getHeight()+55
1071 x=xp-(parentvertex.getWidth()*0.75)
1072 x=xp-100
1073 vertexchild.setRelPos(x,y)
1074
1075 vertexchild.setPlaced()
1076 else:
1077
1078 y=yp+vertex.getHeight()+55
1079
1080 x=xp-100
1081 vertexchild.setRelPos(x,y)
1082 checkForPlacedVertex(vertexchild, vertices)
1083 vertexchild.setPlaced()
1084
1085
1086 elif child[1] == 2 :
1087 for vertexchild in vertices:
1088 if child[0] == vertexchild.getName() and vertexchild.isPlaced() == False:
1089 (xp,yp)=vertex.getRelPos()
1090 if xp == 0:
1091 """special case"""
1092
1093 inadj=vertex.getInAdj()
1094
1095 for parent in inadj:
1096 for parentvertex in vertices:
1097 if parent == parentvertex.getName():
1098 (xp,yp)=parentvertex.getRelPos()
1099 y=yp+parentvertex.getHeight()+15
1100
1101 x=xp+parentvertex.getWidth()+50
1102 vertexchild.setRelPos(x,y)
1103
1104 vertexchild.setPlaced()
1105
1106 else:
1107 y=yp+vertex.getHeight()+55
1108
1109 x=xp+vertex.getWidth()+50
1110 vertexchild.setRelPos(x,y)
1111 checkForPlacedVertex(vertexchild, vertices)
1112 vertexchild.setPlaced()
1113
1114
1115
1116 if child[1] == 0 :
1117 for vertexchild in vertices:
1118 if child[0] == vertexchild.getName() and vertexchild.isPlaced() == False:
1119 (xp,yp)=vertex.getRelPos()
1120 if xp == 0:
1121 """special case"""
1122
1123 inadj=vertex.getInAdj()
1124
1125 for parent in inadj:
1126 for parentvertex in vertices:
1127 if parent == parentvertex.getName():
1128 (xp,yp)=parentvertex.getRelPos()
1129 y=yp+parentvertex.getHeight()+55
1130 x=xp+(parentvertex.getWidth()/2)
1131 vertexchild.setRelPos(x,y)
1132
1133 vertexchild.setPlaced()
1134
1135
1136 else:
1137 y=yp+vertex.getHeight()+55
1138 x=xp+(vertex.getWidth()/2)
1139 vertexchild.setRelPos(x,y)
1140 checkForPlacedVertex(vertexchild, vertices)
1141 vertexchild.setPlaced()
1142
1143
1144
1145 return
1146
1147
1148
1149
1150
1152
1153 """Note: needs to divide graph in layers
1154
1155 Draft notes:
1156 step 1 get temptative coords to place vertex
1157 step 2 check if coords overlaps already placed vertex
1158
1159 step 2 a)
1160 first we have to check if (y,y2) of vertex is in range of the placed vertex,
1161
1162 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p:
1163
1164 if that condition is true, means we have a vertex in the same y that an already placed vertex, so it might be
1165 possible of an overlapping to exists, so we are going to ask:
1166
1167 if x >= xp and x <= x2p:
1168 if that condition is true, then we have an overlapping over the y coord of the vertex (left point)
1169
1170 if x2 >= xp and x <= x2p:
1171 if that condition is true, then we have an overlapping over the y coord of the vertex (right point)
1172
1173 and if does, check whether x or x2 is overlapping
1174 once we know that, we need to check wheter x or x2 of overlapped vertex is touched
1175 if x , move west x - 10 and recheck
1176 """
1177 ret=False
1178 (x,y,x2,y2) = vertex2check.getCoords()
1179 for vertex in vertices:
1180 if vertex.getName() == vertex2check.getName() :
1181 pass
1182 else:
1183 if 1 == 1:
1184 (xp,yp,x2p,y2p) = vertex.getCoords()
1185 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p:
1186
1187 if x >= xp and x <= x2p:
1188
1189 vertex2check.moveSouth(y2p-y+25)
1190 (xp,yp,x2p,y2p) = vertex.getCoords()
1191 (x,y,x2,y2) = vertex2check.getCoords()
1192 ret=True
1193 if x2 >= xp and x <= x2p:
1194
1195 vertex2check.moveSouth(y2p-y+25)
1196 (xp,yp,x2p,y2p) = vertex.getCoords()
1197 (x,y,x2,y2) = vertex2check.getCoords()
1198 ret=True
1199 return ret
1200
1202
1203 """Note: needs to divide graph in layers
1204
1205 Draft notes:
1206 step 1 get temptative coords to place vertex
1207 step 2 check if coords overlaps already placed vertex
1208
1209 step 2 a)
1210 first we have to check if (y,y2) of vertex is in range of the placed vertex,
1211
1212 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p:
1213
1214 if that condition is true, means we have a vertex in the same y that an already placed vertex, so it might be
1215 possible of an overlapping to exists, so we are going to ask:
1216
1217 if x >= xp and x <= x2p:
1218 if that condition is true, then we have an overlapping over the y coord of the vertex (left point)
1219
1220 if x2 >= xp and x <= x2p:
1221 if that condition is true, then we have an overlapping over the y coord of the vertex (right point)
1222
1223 and if does, check whether x or x2 is overlapping
1224 once we know that, we need to check wheter x or x2 of overlapped vertex is touched
1225 if x , move west x - 10 and recheck
1226 """
1227 ret=False
1228 (x,y,x2,y2) = vertex2check.getCoords()
1229 for vertex in vertices:
1230 if vertex.getName() == vertex2check.getName() :
1231 pass
1232 else:
1233 if 1 == 1:
1234 (xp,yp,x2p,y2p) = vertex.getCoords()
1235 if y >= yp and y <= y2p or y2 >= yp and y2 <= y2p:
1236 immlib.Error("%s and %s are in the same x range" % (vertex.getName(),vertex2check.getName()))
1237 if x >= xp and x <= x2p:
1238 immlib.Error("%s and %s overlaps LEFT: %d" % (vertex.getName(),vertex2check.getName(),x2p-x))
1239 vertex2check.moveSouth(20)
1240 (xp,yp,x2p,y2p) = vertex.getCoords()
1241 (x,y,x2,y2) = vertex2check.getCoords()
1242 ret=True
1243 if x2 >= xp and x <= x2p:
1244 vertex2check.moveSouth(20)
1245 immlib.Error("%s and %s overlaps RIGHT" % (vertex.getName(),vertex2check.getName()))
1246 (xp,yp,x2p,y2p) = vertex.getCoords()
1247 (x,y,x2,y2) = vertex2check.getCoords()
1248 ret=True
1249 return ret
1250
1251
1253
1254
1255
1256
1257
1258
1259
1260
1261 return
1262
1263
1265 """ this function will generate a vcg compatible buffer to create the graph """
1266 imm = immlib.Debugger()
1267 ret = imm.getFunctionBegin(address)
1268 if ret:
1269 address = ret
1270 f = imm.getFunction(address)
1271 buf=[]
1272 buf.append('graph: {\x0d\x0a')
1273 buf.append('title: "Graph of %s (0x%08x)"\r\n' % (f.getName(),int(f.start)))
1274 buf.append("//default palette\r\n")
1275
1276 buf += PALETTE
1277 basicblocks = f.getBasicBlocks()
1278 basicblocks.sort()
1279
1280 buf.append('node: { title: "0x%08x" vertical_order: 0 label: "\x0c69%s (0x%08x):\x0c31\r\n' % (int(basicblocks[0].start),f.getName(),int(f.start)))
1281 instr=basicblocks[0].getInstructions(imm)
1282 for i in instr:
1283 if len(i.comment) > 0:
1284 buf.append("%s || %s\r\n" % (i.result,i.comment.replace("\"","")))
1285 else:
1286 buf.append("%s\r\n" % i.result)
1287 buf.append("\"")
1288
1289
1290
1291 for a in range(1,len(basicblocks)):
1292 buf.append(" }\n")
1293 buf.append('node: { title: "0x%08x" label: "\x0c69 0x%08x\x0c31\n' % (int(basicblocks[a].start),int(basicblocks[a].start)))
1294 instr=basicblocks[a].getInstructions(imm)
1295 for i in instr:
1296 if len(i.comment) > 0:
1297 buf.append("%s || %s\r\n" % (i.result,i.comment.replace("\"","")))
1298 else:
1299 buf.append("%s\r\n" % i.result)
1300
1301 buf.append('"\r\n')
1302
1303 buf.append("}\r\n" )
1304
1305 buf.append("//nodes edges\r\n")
1306 for a in range(0,len(basicblocks)-1):
1307 (true,false) = basicblocks[a].getEdges()
1308 if false != 0:
1309 buf.append('edge: { sourcename: "0x%08x" targetname: "0x%08x" label: "false" color: red }\r\n' % (int(basicblocks[a].start),int(basicblocks[a].end)))
1310 buf.append('edge: { sourcename: "0x%08x" targetname: "0x%08x" label: "true" color: darkgreen }\r\n' % (int(basicblocks[a].start),int(true)))
1311 else:
1312 buf.append('edge: { sourcename: "0x%08x" targetname: "0x%08x" }\r\n' % (int(basicblocks[a].start),int(true)))
1313 buf.append("\n}\r\n")
1314 return buf
1315
1316
1318 vcg_buf=generateVCG(address)
1319 if len(vcg_buf) > 0:
1320 fd=open(filename,"wb")
1321 for a in vcg_buf:
1322 fd.write(a)
1323 fd.close()
1324 else:
1325 debugger.Error("There is no VCG graph")
1326
1327
1328 if __name__=="__main__":
1329 main()
1330