{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Control Flow Graph\n",
"\n",
"The code in this notebook helps with obtaining the control flow graph of python functions."
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"**Prerequisites**\n",
"\n",
"* This notebook needs some understanding on advanced concepts in Python, notably \n",
" * classes"
]
},
{
"cell_type": "markdown",
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Control Flow Graph\n",
"\n",
"The class `PyCFG` allows one to obtain the control flow graph.\n",
"\n",
"```Python\n",
"from ControlFlow import gen_cfg, to_graph\n",
"from graphviz import Source\n",
"cfg = gen_cfg(inspect.getsource(my_function))\n",
"graph = to_graph(cfg)\n",
"Source(graph)\n",
"```\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import fuzzingbook_utils"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import ast\n",
"import re\n",
"import astor\n",
"from graphviz import Source, Graph, Digraph"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Registry"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"REGISTRY_IDX = 0"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"REGISTRY = {}"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def get_registry_idx():\n",
" global REGISTRY_IDX\n",
" v = REGISTRY_IDX\n",
" REGISTRY_IDX += 1\n",
" return v"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def reset_registry():\n",
" global REGISTRY_IDX\n",
" global REGISTRY\n",
" REGISTRY_IDX = 0\n",
" REGISTRY = {}"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def register_node(node):\n",
" node.rid = get_registry_idx()\n",
" REGISTRY[node.rid] = node"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def get_registry():\n",
" return dict(REGISTRY)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### CFGNode\n",
"We start with the `CFGNode` representing each node in the control flow graph.\n",
"\\todo{Augmented and annotated assignments (`a += 1`), (`a:int = 1`)}."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class CFGNode(dict):\n",
" def __init__(self, parents=[], ast=None):\n",
" assert type(parents) is list\n",
" register_node(self)\n",
" self.parents = parents\n",
" self.ast_node = ast\n",
" self.update_children(parents) # requires self.rid\n",
" self.children = []\n",
" self.calls = []\n",
"\n",
" def i(self):\n",
" return str(self.rid)\n",
"\n",
" def update_children(self, parents):\n",
" for p in parents:\n",
" p.add_child(self)\n",
"\n",
" def add_child(self, c):\n",
" if c not in self.children:\n",
" self.children.append(c)\n",
"\n",
" def lineno(self):\n",
" return self.ast_node.lineno if hasattr(self.ast_node, 'lineno') else 0\n",
"\n",
" def __str__(self):\n",
" return \"id:%d line[%d] parents: %s : %s\" % (\n",
" self.rid, self.lineno(), str([p.rid for p in self.parents]),\n",
" self.source())\n",
"\n",
" def __repr__(self):\n",
" return str(self)\n",
"\n",
" def __eq__(self, other):\n",
" return self.rid == other.rid\n",
"\n",
" def __neq__(self, other):\n",
" return self.rid != other.rid\n",
"\n",
" def set_parents(self, p):\n",
" self.parents = p\n",
"\n",
" def add_parent(self, p):\n",
" if p not in self.parents:\n",
" self.parents.append(p)\n",
"\n",
" def add_parents(self, ps):\n",
" for p in ps:\n",
" self.add_parent(p)\n",
"\n",
" def add_calls(self, func):\n",
" self.calls.append(func)\n",
"\n",
" def source(self):\n",
" return astor.to_source(self.ast_node).strip()\n",
"\n",
" def to_json(self):\n",
" return {\n",
" 'id': self.rid,\n",
" 'parents': [p.rid for p in self.parents],\n",
" 'children': [c.rid for c in self.children],\n",
" 'calls': self.calls,\n",
" 'at': self.lineno(),\n",
" 'ast': self.source()\n",
" }"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"REGISTRY_IDX = 0"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"REGISTRY = {}"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def get_registry_idx():\n",
" global REGISTRY_IDX\n",
" v = REGISTRY_IDX\n",
" REGISTRY_IDX += 1\n",
" return v"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def reset_registry():\n",
" global REGISTRY_IDX\n",
" global REGISTRY\n",
" REGISTRY_IDX = 0\n",
" REGISTRY = {}"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def register_node(node):\n",
" node.rid = get_registry_idx()\n",
" REGISTRY[node.rid] = node"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### PyCFG\n",
"\n",
"Next, the `PyCFG` class which is responsible for parsing, and holding the graph."
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class PyCFG:\n",
" def __init__(self):\n",
" self.founder = CFGNode(\n",
" parents=[], ast=ast.parse('start').body[0]) # sentinel\n",
" self.founder.ast_node.lineno = 0\n",
" self.functions = {}\n",
" self.functions_node = {}"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def parse(self, src):\n",
" return ast.parse(src)"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def walk(self, node, myparents):\n",
" fname = \"on_%s\" % node.__class__.__name__.lower()\n",
" if hasattr(self, fname):\n",
" fn = getattr(self, fname)\n",
" v = fn(node, myparents)\n",
" return v\n",
" else:\n",
" return myparents"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_module(self, node, myparents):\n",
" \"\"\"\n",
" Module(stmt* body)\n",
" \"\"\"\n",
" # each time a statement is executed unconditionally, make a link from\n",
" # the result to next statement\n",
" p = myparents\n",
" for n in node.body:\n",
" p = self.walk(n, p)\n",
" return p"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_augassign(self, node, myparents):\n",
" \"\"\"\n",
" AugAssign(expr target, operator op, expr value)\n",
" \"\"\"\n",
" p = [CFGNode(parents=myparents, ast=node)]\n",
" p = self.walk(node.value, p)\n",
"\n",
" return p"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_annassign(self, node, myparents):\n",
" \"\"\"\n",
" AnnAssign(expr target, expr annotation, expr? value, int simple)\n",
" \"\"\"\n",
" p = [CFGNode(parents=myparents, ast=node)]\n",
" p = self.walk(node.value, p)\n",
"\n",
" return p"
]
},
{
"cell_type": "code",
"execution_count": 21,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_assign(self, node, myparents):\n",
" \"\"\"\n",
" Assign(expr* targets, expr value)\n",
" \"\"\"\n",
" if len(node.targets) > 1:\n",
" raise NotImplemented('Parallel assignments')\n",
"\n",
" p = [CFGNode(parents=myparents, ast=node)]\n",
" p = self.walk(node.value, p)\n",
"\n",
" return p"
]
},
{
"cell_type": "code",
"execution_count": 22,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_pass(self, node, myparents):\n",
" return [CFGNode(parents=myparents, ast=node)]"
]
},
{
"cell_type": "code",
"execution_count": 23,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_break(self, node, myparents):\n",
" parent = myparents[0]\n",
" while not hasattr(parent, 'exit_nodes'):\n",
" # we have ordered parents\n",
" parent = parent.parents[0]\n",
"\n",
" assert hasattr(parent, 'exit_nodes')\n",
" p = CFGNode(parents=myparents, ast=node)\n",
"\n",
" # make the break one of the parents of label node.\n",
" parent.exit_nodes.append(p)\n",
"\n",
" # break doesn't have immediate children\n",
" return []"
]
},
{
"cell_type": "code",
"execution_count": 24,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_continue(self, node, myparents):\n",
" parent = myparents[0]\n",
" while not hasattr(parent, 'exit_nodes'):\n",
" # we have ordered parents\n",
" parent = parent.parents[0]\n",
" assert hasattr(parent, 'exit_nodes')\n",
" p = CFGNode(parents=myparents, ast=node)\n",
"\n",
" # make continue one of the parents of the original test node.\n",
" parent.add_parent(p)\n",
"\n",
" # return the parent because a continue is not the parent\n",
" # for the just next node\n",
" return []"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_for(self, node, myparents):\n",
" # node.target in node.iter: node.body\n",
" # The For loop in python (no else) can be translated\n",
" # as follows:\n",
" # \n",
" # for a in iterator:\n",
" # mystatements\n",
" #\n",
" # __iv = iter(iterator)\n",
" # while __iv.__length_hint() > 0:\n",
" # a = next(__iv)\n",
" # mystatements\n",
" \n",
" init_node = CFGNode(parents=myparents,\n",
" ast=ast.parse('__iv = iter(%s)' % astor.to_source(node.iter).strip()).body[0])\n",
" ast.copy_location(init_node.ast_node, node.iter)\n",
" \n",
" _test_node = CFGNode(\n",
" parents=[init_node],\n",
" ast=ast.parse('_for: __iv.__length__hint__() > 0').body[0])\n",
" ast.copy_location(_test_node.ast_node, node)\n",
"\n",
" # we attach the label node here so that break can find it.\n",
" _test_node.exit_nodes = []\n",
" test_node = self.walk(node.iter, [_test_node])\n",
"\n",
" extract_node = CFGNode(parents=test_node,\n",
" ast=ast.parse('%s = next(__iv)' % astor.to_source(node.target).strip()).body[0])\n",
" ast.copy_location(extract_node.ast_node, node.iter)\n",
"\n",
" \n",
" # now we evaluate the body, one at a time.\n",
" p1 = [extract_node]\n",
" for n in node.body:\n",
" p1 = self.walk(n, p1)\n",
"\n",
" # the test node is looped back at the end of processing.\n",
" _test_node.add_parents(p1)\n",
"\n",
" return _test_node.exit_nodes + test_node"
]
},
{
"cell_type": "code",
"execution_count": 26,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_while(self, node, myparents):\n",
" # For a while, the earliest parent is the node.test\n",
" _test_node = CFGNode(\n",
" parents=myparents,\n",
" ast=ast.parse(\n",
" '_while: %s' % astor.to_source(node.test).strip()).body[0])\n",
" ast.copy_location(_test_node.ast_node, node.test)\n",
" _test_node.exit_nodes = []\n",
" test_node = self.walk(node.test, [_test_node])\n",
"\n",
" # we attach the label node here so that break can find it.\n",
"\n",
" # now we evaluate the body, one at a time.\n",
" assert len(test_node) == 1\n",
" p1 = test_node\n",
" for n in node.body:\n",
" p1 = self.walk(n, p1)\n",
"\n",
" # the test node is looped back at the end of processing.\n",
" _test_node.add_parents(p1)\n",
"\n",
" # link label node back to the condition.\n",
" return _test_node.exit_nodes + test_node"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_if(self, node, myparents):\n",
" _test_node = CFGNode(\n",
" parents=myparents,\n",
" ast=ast.parse(\n",
" '_if: %s' % astor.to_source(node.test).strip()).body[0])\n",
" ast.copy_location(_test_node.ast_node, node.test)\n",
" test_node = self.walk(node.test, [ _test_node])\n",
" assert len(test_node) == 1\n",
" g1 = test_node\n",
" for n in node.body:\n",
" g1 = self.walk(n, g1)\n",
" g2 = test_node\n",
" for n in node.orelse:\n",
" g2 = self.walk(n, g2)\n",
" return g1 + g2"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_binop(self, node, myparents):\n",
" left = self.walk(node.left, myparents)\n",
" right = self.walk(node.right, left)\n",
" return right"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_compare(self, node, myparents):\n",
" left = self.walk(node.left, myparents)\n",
" right = self.walk(node.comparators[0], left)\n",
" return right"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_unaryop(self, node, myparents):\n",
" return self.walk(node.operand, myparents)"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_call(self, node, myparents):\n",
" def get_func(node):\n",
" if type(node.func) is ast.Name:\n",
" mid = node.func.id\n",
" elif type(node.func) is ast.Attribute:\n",
" mid = node.func.attr\n",
" elif type(node.func) is ast.Call:\n",
" mid = get_func(node.func)\n",
" else:\n",
" raise Exception(str(type(node.func)))\n",
" return mid\n",
" #mid = node.func.value.id\n",
"\n",
" p = myparents\n",
" for a in node.args:\n",
" p = self.walk(a, p)\n",
" mid = get_func(node)\n",
" myparents[0].add_calls(mid)\n",
"\n",
" # these need to be unlinked later if our module actually defines these\n",
" # functions. Otherwsise we may leave them around.\n",
" # during a call, the direct child is not the next\n",
" # statement in text.\n",
" for c in p:\n",
" c.calllink = 0\n",
" return p"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_expr(self, node, myparents):\n",
" p = [CFGNode(parents=myparents, ast=node)]\n",
" return self.walk(node.value, p)"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_return(self, node, myparents):\n",
" if type(myparents) is tuple:\n",
" parent = myparents[0][0]\n",
" else:\n",
" parent = myparents[0]\n",
"\n",
" val_node = self.walk(node.value, myparents)\n",
" # on return look back to the function definition.\n",
" while not hasattr(parent, 'return_nodes'):\n",
" parent = parent.parents[0]\n",
" assert hasattr(parent, 'return_nodes')\n",
"\n",
" p = CFGNode(parents=val_node, ast=node)\n",
"\n",
" # make the break one of the parents of label node.\n",
" parent.return_nodes.append(p)\n",
"\n",
" # return doesnt have immediate children\n",
" return []"
]
},
{
"cell_type": "code",
"execution_count": 34,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def on_functiondef(self, node, myparents):\n",
" # a function definition does not actually continue the thread of\n",
" # control flow\n",
" # name, args, body, decorator_list, returns\n",
" fname = node.name\n",
" args = node.args\n",
" returns = node.returns\n",
"\n",
" enter_node = CFGNode(\n",
" parents=[],\n",
" ast=ast.parse('enter: %s(%s)' % (node.name, ', '.join(\n",
" [a.arg for a in node.args.args]))).body[0]) # sentinel\n",
" enter_node.calleelink = True\n",
" ast.copy_location(enter_node.ast_node, node)\n",
" exit_node = CFGNode(\n",
" parents=[],\n",
" ast=ast.parse('exit: %s(%s)' % (node.name, ', '.join(\n",
" [a.arg for a in node.args.args]))).body[0]) # sentinel\n",
" exit_node.fn_exit_node = True\n",
" ast.copy_location(exit_node.ast_node, node)\n",
" enter_node.return_nodes = [] # sentinel\n",
"\n",
" p = [enter_node]\n",
" for n in node.body:\n",
" p = self.walk(n, p)\n",
"\n",
" for n in p:\n",
" if n not in enter_node.return_nodes:\n",
" enter_node.return_nodes.append(n)\n",
"\n",
" for n in enter_node.return_nodes:\n",
" exit_node.add_parent(n)\n",
"\n",
" self.functions[fname] = [enter_node, exit_node]\n",
" self.functions_node[enter_node.lineno()] = fname\n",
"\n",
" return myparents"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def get_defining_function(self, node):\n",
" if node.lineno() in self.functions_node:\n",
" return self.functions_node[node.lineno()]\n",
" if not node.parents:\n",
" self.functions_node[node.lineno()] = ''\n",
" return ''\n",
" val = self.get_defining_function(node.parents[0])\n",
" self.functions_node[node.lineno()] = val\n",
" return val"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def link_functions(self):\n",
" for nid, node in REGISTRY.items():\n",
" if node.calls:\n",
" for calls in node.calls:\n",
" if calls in self.functions:\n",
" enter, exit = self.functions[calls]\n",
" enter.add_parent(node)\n",
" if node.children:\n",
" # # until we link the functions up, the node\n",
" # # should only have succeeding node in text as\n",
" # # children.\n",
" # assert(len(node.children) == 1)\n",
" # passn = node.children[0]\n",
" # # We require a single pass statement after every\n",
" # # call (which means no complex expressions)\n",
" # assert(type(passn.ast_node) == ast.Pass)\n",
"\n",
" # # unlink the call statement\n",
" assert node.calllink > -1\n",
" node.calllink += 1\n",
" for i in node.children:\n",
" i.add_parent(exit)\n",
" # passn.set_parents([exit])\n",
" # ast.copy_location(exit.ast_node, passn.ast_node)\n",
"\n",
" # #for c in passn.children: c.add_parent(exit)\n",
" # #passn.ast_node = exit.ast_node"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def update_functions(self):\n",
" for nid, node in REGISTRY.items():\n",
" _n = self.get_defining_function(node)"
]
},
{
"cell_type": "code",
"execution_count": 38,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def update_children(self):\n",
" for nid, node in REGISTRY.items():\n",
" for p in node.parents:\n",
" p.add_child(node)"
]
},
{
"cell_type": "code",
"execution_count": 39,
"metadata": {
"button": false,
"new_sheet": false,
"run_control": {
"read_only": false
},
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"class PyCFG(PyCFG):\n",
" def gen_cfg(self, src):\n",
" \"\"\"\n",
" >>> i = PyCFG()\n",
" >>> i.walk(\"100\")\n",
" 5\n",
" \"\"\"\n",
" node = self.parse(src)\n",
" nodes = self.walk(node, [self.founder])\n",
" self.last_node = CFGNode(parents=nodes, ast=ast.parse('stop').body[0])\n",
" ast.copy_location(self.last_node.ast_node, self.founder.ast_node)\n",
" self.update_children()\n",
" self.update_functions()\n",
" self.link_functions()"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Supporting Functions"
]
},
{
"cell_type": "code",
"execution_count": 40,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def compute_dominator(cfg, start=0, key='parents'):\n",
" dominator = {}\n",
" dominator[start] = {start}\n",
" all_nodes = set(cfg.keys())\n",
" rem_nodes = all_nodes - {start}\n",
" for n in rem_nodes:\n",
" dominator[n] = all_nodes\n",
"\n",
" c = True\n",
" while c:\n",
" c = False\n",
" for n in rem_nodes:\n",
" pred_n = cfg[n][key]\n",
" doms = [dominator[p] for p in pred_n]\n",
" i = set.intersection(*doms) if doms else set()\n",
" v = {n} | i\n",
" if dominator[n] != v:\n",
" c = True\n",
" dominator[n] = v\n",
" return dominator"
]
},
{
"cell_type": "code",
"execution_count": 41,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def compute_flow(pythonfile):\n",
" cfg, first, last = get_cfg(pythonfile)\n",
" return cfg, compute_dominator(\n",
" cfg, start=first), compute_dominator(\n",
" cfg, start=last, key='children')"
]
},
{
"cell_type": "code",
"execution_count": 42,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def gen_cfg(fnsrc, remove_start_stop=True):\n",
" reset_registry()\n",
" cfg = PyCFG()\n",
" cfg.gen_cfg(fnsrc)\n",
" cache = dict(REGISTRY)\n",
" if remove_start_stop:\n",
" return {\n",
" k: cache[k]\n",
" for k in cache if cache[k].source() not in {'start', 'stop'}\n",
" }\n",
" else:\n",
" return cache"
]
},
{
"cell_type": "code",
"execution_count": 43,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def get_cfg(src):\n",
" reset_registry()\n",
" cfg = PyCFG()\n",
" cfg.gen_cfg(src)\n",
" cache = dict(REGISTRY)\n",
" g = {}\n",
" for k, v in cache.items():\n",
" j = v.to_json()\n",
" at = j['at']\n",
" parents_at = [cache[p].to_json()['at'] for p in j['parents']]\n",
" children_at = [cache[c].to_json()['at'] for c in j['children']]\n",
" if at not in g:\n",
" g[at] = {'parents': set(), 'children': set()}\n",
" # remove dummy nodes\n",
" ps = set([p for p in parents_at if p != at])\n",
" cs = set([c for c in children_at if c != at])\n",
" g[at]['parents'] |= ps\n",
" g[at]['children'] |= cs\n",
" if v.calls:\n",
" g[at]['calls'] = v.calls\n",
" g[at]['function'] = cfg.functions_node[v.lineno()]\n",
" return (g, cfg.founder.ast_node.lineno, cfg.last_node.ast_node.lineno)"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def to_graph(cache, arcs=[]):\n",
" graph = Digraph(comment='Control Flow Graph')\n",
" colors = {0: 'blue', 1: 'red'}\n",
" kind = {0: 'T', 1: 'F'}\n",
" cov_lines = set(i for i, j in arcs)\n",
" for nid, cnode in cache.items():\n",
" lineno = cnode.lineno()\n",
" shape, peripheries = 'oval', '1'\n",
" if isinstance(cnode.ast_node, ast.AnnAssign):\n",
" if cnode.ast_node.target.id in {'_if', '_for', '_while'}:\n",
" shape = 'diamond'\n",
" elif cnode.ast_node.target.id in {'enter', 'exit'}:\n",
" shape, peripheries = 'oval', '2'\n",
" else:\n",
" shape = 'rectangle'\n",
" graph.node(cnode.i(), \"%d: %s\" % (lineno, unhack(cnode.source())), shape=shape, peripheries=peripheries)\n",
" for pn in cnode.parents:\n",
" plineno = pn.lineno()\n",
" if hasattr(pn, 'calllink') and pn.calllink > 0 and not hasattr(\n",
" cnode, 'calleelink'):\n",
" graph.edge(pn.i(), cnode.i(), style='dotted', weight=100)\n",
" continue\n",
"\n",
" if arcs:\n",
" if (plineno, lineno) in arcs:\n",
" graph.edge(pn.i(), cnode.i(), color='green')\n",
" elif plineno == lineno and lineno in cov_lines:\n",
" graph.edge(pn.i(), cnode.i(), color='green')\n",
" # child is exit and parent is covered\n",
" elif hasattr(cnode, 'fn_exit_node') and plineno in cov_lines:\n",
" graph.edge(pn.i(), cnode.i(), color='green')\n",
" # parent is exit and one of its parents is covered.\n",
" elif hasattr(pn, 'fn_exit_node') and len(\n",
" set(n.lineno() for n in pn.parents) | cov_lines) > 0:\n",
" graph.edge(pn.i(), cnode.i(), color='green')\n",
" # child is a callee (has calleelink) and one of the parents is covered.\n",
" elif plineno in cov_lines and hasattr(cnode, 'calleelink'):\n",
" graph.edge(pn.i(), cnode.i(), color='green')\n",
" else:\n",
" graph.edge(pn.i(), cnode.i(), color='red')\n",
" else:\n",
" order = {c.i():i for i,c in enumerate(pn.children)}\n",
" if len(order) < 2:\n",
" graph.edge(pn.i(), cnode.i())\n",
" else:\n",
" o = order[cnode.i()]\n",
" graph.edge(pn.i(), cnode.i(), color=colors[o], label=kind[o])\n",
" return graph"
]
},
{
"cell_type": "code",
"execution_count": 45,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def unhack(v):\n",
" for i in ['if', 'while', 'for', 'elif']:\n",
" v = re.sub(r'^_%s:' % i, '%s:' % i, v)\n",
" return v"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Examples"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### check_triangle"
]
},
{
"cell_type": "code",
"execution_count": 46,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def check_triangle(a,b,c):\n",
" if a == b:\n",
" if a == c:\n",
" if b == c:\n",
" return \"Equilateral\"\n",
" else:\n",
" return \"Isosceles\"\n",
" else:\n",
" return \"Isosceles\"\n",
" else:\n",
" if b != c:\n",
" if a == c:\n",
" return \"Isosceles\"\n",
" else:\n",
" return \"Scalene\"\n",
" else:\n",
" return \"Isosceles\""
]
},
{
"cell_type": "code",
"execution_count": 47,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import inspect"
]
},
{
"cell_type": "code",
"execution_count": 48,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"graph = to_graph(gen_cfg(inspect.getsource(check_triangle)))"
]
},
{
"cell_type": "code",
"execution_count": 49,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 49,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### cgi_decode\n",
"\n",
"Note that we do not yet support _augmented assignments_: i.e assignments such as `+=`"
]
},
{
"cell_type": "code",
"execution_count": 50,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def cgi_decode(s):\n",
" hex_values = {\n",
" '0': 0, '1': 1, '2': 2, '3': 3, '4': 4,\n",
" '5': 5, '6': 6, '7': 7, '8': 8, '9': 9,\n",
" 'a': 10, 'b': 11, 'c': 12, 'd': 13, 'e': 14, 'f': 15,\n",
" 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15,\n",
" }\n",
"\n",
" t = \"\"\n",
" i = 0\n",
" while i < len(s):\n",
" c = s[i]\n",
" if c == '+':\n",
" t += ' '\n",
" elif c == '%':\n",
" digit_high, digit_low = s[i + 1], s[i + 2]\n",
" i += 2\n",
" if digit_high in hex_values and digit_low in hex_values:\n",
" v = hex_values[digit_high] * 16 + hex_values[digit_low]\n",
" t += chr(v)\n",
" else:\n",
" raise ValueError(\"Invalid encoding\")\n",
" else:\n",
" t += c\n",
" i += 1\n",
" return t"
]
},
{
"cell_type": "code",
"execution_count": 51,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"graph = to_graph(gen_cfg(inspect.getsource(cgi_decode)))"
]
},
{
"cell_type": "code",
"execution_count": 52,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 52,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### gcd"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def gcd(a, b):\n",
" if a\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 55,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph)"
]
},
{
"cell_type": "code",
"execution_count": 56,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def compute_gcd(x, y): \n",
" if x > y: \n",
" small = y \n",
" else: \n",
" small = x \n",
" for i in range(1, small+1): \n",
" if((x % i == 0) and (y % i == 0)): \n",
" gcd = i \n",
" \n",
" return gcd "
]
},
{
"cell_type": "code",
"execution_count": 57,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"graph = to_graph(gen_cfg(inspect.getsource(compute_gcd)))"
]
},
{
"cell_type": "code",
"execution_count": 58,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 58,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### fib\n",
"\n",
"Note that the *for-loop* requires additional massaging. While we show the labels correctly, the *comparison node* needs to be extracted. Hence, the representation is not accurate."
]
},
{
"cell_type": "code",
"execution_count": 59,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"def fib(n,):\n",
" l = [0, 1]\n",
" for i in range(n-2):\n",
" l.append(l[-1]+l[-2])\n",
" return l"
]
},
{
"cell_type": "code",
"execution_count": 60,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"graph = to_graph(gen_cfg(inspect.getsource(fib)))"
]
},
{
"cell_type": "code",
"execution_count": 61,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 61,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"#### quad_solver"
]
},
{
"cell_type": "code",
"execution_count": 62,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def quad_solver(a, b, c):\n",
" discriminant = b^2 - 4*a*c\n",
" r1, r2 = 0, 0\n",
" i1, i2 = 0, 0\n",
" if discriminant >= 0:\n",
" droot = math.sqrt(discriminant)\n",
" r1 = (-b + droot) / (2*a)\n",
" r2 = (-b - droot) / (2*a)\n",
" else:\n",
" droot = math.sqrt(-1 * discriminant)\n",
" droot_ = droot/(2*a)\n",
" r1, i1 = -b/(2*a), droot_\n",
" r2, i2 = -b/(2*a), -droot_\n",
" if i1 == 0 and i2 == 0:\n",
" return (r1, r2)\n",
" return ((r1,i1), (r2,i2))"
]
},
{
"cell_type": "code",
"execution_count": 63,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"graph = to_graph(gen_cfg(inspect.getsource(quad_solver)))"
]
},
{
"cell_type": "code",
"execution_count": 64,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 64,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Source(graph)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Call Graph\n",
"### Install: Pyan Static Call Graph Lifter"
]
},
{
"cell_type": "code",
"execution_count": 65,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import os\n",
"import networkx as nx\n",
"from graphviz import Source"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Call Graph Helpers"
]
},
{
"cell_type": "code",
"execution_count": 66,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def construct_callgraph(code, name=\"callgraph\"):\n",
" file_name = name + \".py\"\n",
" with open(file_name, 'w') as f:\n",
" f.write(code)\n",
" cg_file = name + '.dot'\n",
" os.system(f'pyan {file_name} --uses --defines --colored --grouped --annotated --dot > {cg_file}')\n",
" \n",
"def callgraph(code, name=\"callgraph\"):\n",
" if not os.path.isfile(name + '.dot'):\n",
" construct_callgraph(code, name)\n",
" return Source.from_file(name + '.dot')\n",
"\n",
"def get_callgraph(code, name=\"callgraph\"):\n",
" if not os.path.isfile(name + '.dot'):\n",
" construct_callgraph(code, name)\n",
" return nx.drawing.nx_pydot.read_dot(name + '.dot')"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"### Example: Maze\n",
"To provide a meaningful example where you can easily change the code complexity and target location, we generate the maze source code from the maze provided as string. This example is loosely based on an old [blog post](https://feliam.wordpress.com/2010/10/07/the-symbolic-maze/) on symbolic execution by Felipe Andres Manzano (Quick shout-out!).\n",
"\n",
"You simply specify the maze as a string. Like so."
]
},
{
"cell_type": "code",
"execution_count": 67,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"maze_string = \"\"\"\n",
"+-+-----+\n",
"|X| |\n",
"| | --+ |\n",
"| | | |\n",
"| +-- | |\n",
"| |#|\n",
"+-----+-+\n",
"\"\"\""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Each character in `maze_string` represents a tile. For each tile, a tile-function is generated. \n",
"* If the current tile is \"benign\" (` `), the tile-function corresponding to the next input character (D, U, L, R) is called. Unexpected input characters are ignored. If no more input characters are left, it returns \"VALID\" and the current maze state.\n",
"* If the current tile is a \"trap\" (`+`,`|`,`-`), it returns \"INVALID\" and the current maze state.\n",
"* If the current tile is the \"target\" (`#`), it returns \"SOLVED\" and the current maze state.\n",
"\n",
"The code is generated using the function `generate_maze_code`. "
]
},
{
"cell_type": "code",
"execution_count": 68,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def generate_print_maze(maze_string):\n",
" return \"\"\"\n",
"def print_maze(out, row, col):\n",
" output = out +\"\\\\n\"\n",
" c_row = 0\n",
" c_col = 0\n",
" for c in list(\\\"\\\"\\\"%s\\\"\\\"\\\"):\n",
" if c == '\\\\n':\n",
" c_row += 1\n",
" c_col = 0\n",
" output += \"\\\\n\"\n",
" else:\n",
" if c_row == row and c_col == col: output += \"X\"\n",
" elif c == \"X\": output += \" \"\n",
" else: output += c\n",
" c_col += 1\n",
" return output\n",
"\"\"\" % maze_string"
]
},
{
"cell_type": "code",
"execution_count": 69,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def generate_trap_tile(row, col):\n",
" return \"\"\"\n",
"def tile_%d_%d(input, index):\n",
" try: HTMLParser().feed(input)\n",
" except: pass\n",
" return print_maze(\"INVALID\", %d, %d)\n",
"\"\"\" % (row, col, row, col)"
]
},
{
"cell_type": "code",
"execution_count": 70,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def generate_good_tile(c, row, col):\n",
" code = \"\"\"\n",
"def tile_%d_%d(input, index):\n",
" if (index == len(input)): return print_maze(\"VALID\", %d, %d)\n",
" elif input[index] == 'L': return tile_%d_%d(input, index + 1)\n",
" elif input[index] == 'R': return tile_%d_%d(input, index + 1)\n",
" elif input[index] == 'U': return tile_%d_%d(input, index + 1)\n",
" elif input[index] == 'D': return tile_%d_%d(input, index + 1)\n",
" else : return tile_%d_%d(input, index + 1)\n",
"\"\"\" % (row, col, row, col,\n",
" row, col - 1, \n",
" row, col + 1, \n",
" row - 1, col, \n",
" row + 1, col,\n",
" row, col)\n",
" \n",
" if c == \"X\":\n",
" code += \"\"\"\n",
"def maze(input):\n",
" return tile_%d_%d(list(input), 0)\n",
"\"\"\" % (row, col)\n",
"\n",
" return code"
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def generate_target_tile(row, col):\n",
" return \"\"\"\n",
"def tile_%d_%d(input, index):\n",
" return print_maze(\"SOLVED\", %d, %d)\n",
"\n",
"def target_tile():\n",
" return \"tile_%d_%d\"\n",
"\"\"\" % (row, col, row, col, row, col)"
]
},
{
"cell_type": "code",
"execution_count": 72,
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"outputs": [],
"source": [
"def generate_maze_code(maze, name=\"maze\"):\n",
" row = 0\n",
" col = 0\n",
" code = generate_print_maze(maze)\n",
" \n",
" for c in list(maze):\n",
" if c == '\\n':\n",
" row += 1\n",
" col = 0\n",
" else: \n",
" if c == \"-\" or c == \"+\" or c == \"|\":\n",
" code += generate_trap_tile(row, col)\n",
" elif c == \" \" or c == \"X\":\n",
" code += generate_good_tile(c, row, col)\n",
" elif c == \"#\":\n",
" code += generate_target_tile(row, col)\n",
" else: \n",
" print(\"Invalid maze! Try another one.\")\n",
" col += 1\n",
"\n",
" return code"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"Now you can generate the maze code for an arbitrary maze."
]
},
{
"cell_type": "code",
"execution_count": 73,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"maze_code = generate_maze_code(maze_string)\n",
"exec(maze_code)"
]
},
{
"cell_type": "code",
"execution_count": 74,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"VALID\n",
"\n",
"+-+-----+\n",
"| | |\n",
"| | --+ |\n",
"| | | |\n",
"| +-- |X|\n",
"| |#|\n",
"+-----+-+\n",
"\n"
]
}
],
"source": [
"print(maze(\"DDDDRRRRUULLUURRRRDDD\")) # Appending one more 'D', you have reached the target."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "subslide"
}
},
"source": [
"This is the corresponding call graph."
]
},
{
"cell_type": "code",
"execution_count": 75,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [
{
"data": {
"image/svg+xml": [
"\n",
"\n",
"\n",
"\n",
"\n"
],
"text/plain": [
""
]
},
"execution_count": 75,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"callgraph(maze_code)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Cleanup\n",
"\n",
"We're done, so we clean up:"
]
},
{
"cell_type": "code",
"execution_count": 76,
"metadata": {
"slideshow": {
"slide_type": "skip"
}
},
"outputs": [],
"source": [
"import shutil"
]
},
{
"cell_type": "code",
"execution_count": 77,
"metadata": {
"slideshow": {
"slide_type": "fragment"
}
},
"outputs": [],
"source": [
"if os.path.exists('callgraph.dot'):\n",
" os.remove('callgraph.dot')\n",
" \n",
"if os.path.exists('callgraph.py'):\n",
" os.remove('callgraph.py')"
]
}
],
"metadata": {
"ipub": {
"bibliography": "fuzzingbook.bib",
"toc": true
},
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.8"
},
"toc": {
"base_numbering": 1,
"nav_menu": {},
"number_sections": true,
"sideBar": true,
"skip_h1_title": true,
"title_cell": "",
"title_sidebar": "Contents",
"toc_cell": false,
"toc_position": {},
"toc_section_display": true,
"toc_window_display": true
},
"toc-autonumbering": false,
"varInspector": {
"cols": {
"lenName": 16,
"lenType": 16,
"lenVar": 40
},
"kernels_config": {
"python": {
"delete_cmd_postfix": "",
"delete_cmd_prefix": "del ",
"library": "var_list.py",
"varRefreshCmd": "print(var_dic_list())"
},
"r": {
"delete_cmd_postfix": ") ",
"delete_cmd_prefix": "rm(",
"library": "var_list.r",
"varRefreshCmd": "cat(var_dic_list()) "
}
},
"types_to_exclude": [
"module",
"function",
"builtin_function_or_method",
"instance",
"_Feature"
],
"window_display": false
}
},
"nbformat": 4,
"nbformat_minor": 2
}