1# This file is Copyright 2019 Volatility Foundation and licensed under the Volatility Software License 1.0 2# which is available at https://www.volatilityfoundation.org/license/vsl-v1.0 3# 4"""Renderers. 5 6Renderers display the unified output format in some manner (be it text 7or file or graphical output 8""" 9import collections 10import datetime 11from typing import Any, Callable, Iterable, List, Optional, Tuple, TypeVar, Union 12 13from volatility.framework import interfaces 14from volatility.framework.interfaces import renderers 15 16 17class UnreadableValue(interfaces.renderers.BaseAbsentValue): 18 """Class that represents values which are empty because the data cannot be 19 read.""" 20 21 22class UnparsableValue(interfaces.renderers.BaseAbsentValue): 23 """Class that represents values which are empty because the data cannot be 24 interpreted correctly.""" 25 26 27class NotApplicableValue(interfaces.renderers.BaseAbsentValue): 28 """Class that represents values which are empty because they don't make 29 sense for this node.""" 30 31 32class NotAvailableValue(interfaces.renderers.BaseAbsentValue): 33 """Class that represents values which cannot be provided now (but might in 34 a future run) 35 36 This might occur when information packed with volatility (such as 37 symbol information) is not available, but a future version or a 38 different run may later have that information available (ie, it 39 could be applicable, but we can't get it and it's not because it's 40 unreadable or unparsable). Unreadable and Unparsable should be used 41 in preference, and only if neither fits should this be used. 42 """ 43 44 45class TreeNode(interfaces.renderers.TreeNode): 46 """Class representing a particular node in a tree grid.""" 47 48 def __init__(self, path: str, treegrid: 'TreeGrid', parent: Optional['TreeNode'], 49 values: List[interfaces.renderers.BaseTypes]) -> None: 50 if not isinstance(treegrid, TreeGrid): 51 raise TypeError("Treegrid must be an instance of TreeGrid") 52 self._treegrid = treegrid 53 self._parent = parent 54 self._path = path 55 self._validate_values(values) 56 self._values = treegrid.RowStructure(*values) # type: ignore 57 58 def __repr__(self) -> str: 59 return "<TreeNode [{}] - {}>".format(self.path, self._values) 60 61 def __getitem__(self, item: Union[int, slice]) -> Any: 62 return self._treegrid.children(self).__getitem__(item) 63 64 def __len__(self) -> int: 65 return len(self._treegrid.children(self)) 66 67 def _validate_values(self, values: List[interfaces.renderers.BaseTypes]) -> None: 68 """A function for raising exceptions if a given set of values is 69 invalid according to the column properties.""" 70 if not (isinstance(values, collections.Sequence) and len(values) == len(self._treegrid.columns)): 71 raise TypeError( 72 "Values must be a list of objects made up of simple types and number the same as the columns") 73 for index in range(len(self._treegrid.columns)): 74 column = self._treegrid.columns[index] 75 val = values[index] 76 if not isinstance(val, (column.type, interfaces.renderers.BaseAbsentValue)): 77 raise TypeError( 78 "Values item with index {} is the wrong type for column {} (got {} but expected {})".format( 79 index, column.name, type(val), column.type)) 80 # TODO: Consider how to deal with timezone naive/aware datetimes (and alert plugin uses to be precise) 81 # if isinstance(val, datetime.datetime): 82 # tznaive = val.tzinfo is None or val.tzinfo.utcoffset(val) is None 83 84 @property 85 def values(self) -> Iterable[interfaces.renderers.BaseTypes]: 86 """Returns the list of values from the particular node, based on column 87 index.""" 88 return self._values 89 90 @property 91 def path(self) -> str: 92 """Returns a path identifying string. 93 94 This should be seen as opaque by external classes, Parsing of 95 path locations based on this string are not guaranteed to remain 96 stable. 97 """ 98 return self._path 99 100 @property 101 def parent(self) -> Optional['TreeNode']: 102 """Returns the parent node of this node or None.""" 103 return self._parent 104 105 @property 106 def path_depth(self) -> int: 107 """Return the path depth of the current node.""" 108 return len(self.path.split(TreeGrid.path_sep)) 109 110 def path_changed(self, path: str, added: bool = False) -> None: 111 """Updates the path based on the addition or removal of a node higher 112 up in the tree. 113 114 This should only be called by the containing TreeGrid and 115 expects to only be called for affected nodes. 116 """ 117 components = self._path.split(TreeGrid.path_sep) 118 changed = path.split(TreeGrid.path_sep) 119 changed_index = len(changed) - 1 120 if int(components[changed_index]) >= int(changed[-1]): 121 components[changed_index] = str(int(components[changed_index]) + (1 if added else -1)) 122 self._path = TreeGrid.path_sep.join(components) 123 124 125class TreeGrid(interfaces.renderers.TreeGrid): 126 """Class providing the interface for a TreeGrid (which contains TreeNodes) 127 128 The structure of a TreeGrid is designed to maintain the structure of the tree in a single object. 129 For this reason each TreeNode does not hold its children, they are managed by the top level object. 130 This leaves the Nodes as simple data carries and prevents them being used to manipulate the tree as a whole. 131 This is a data structure, and is not expected to be modified much once created. 132 133 Carrying the children under the parent makes recursion easier, but then every node is its own little tree 134 and must have all the supporting tree functions. It also allows for a node to be present in several different trees, 135 and to create cycles. 136 """ 137 138 path_sep = "|" 139 140 def __init__(self, columns: List[Tuple[str, interfaces.renderers.BaseTypes]], 141 generator: Optional[Iterable[Tuple[int, Tuple]]]) -> None: 142 """Constructs a TreeGrid object using a specific set of columns. 143 144 The TreeGrid itself is a root element, that can have children but no values. 145 The TreeGrid does *not* contain any information about formatting, 146 these are up to the renderers and plugins. 147 148 Args: 149 columns: A list of column tuples made up of (name, type). 150 generator: An iterable containing row for a tree grid, each row contains a indent level followed by the values for each column in order. 151 """ 152 self._populated = False 153 self._row_count = 0 154 self._children = [] # type: List[TreeNode] 155 converted_columns = [] # type: List[interfaces.renderers.Column] 156 if len(columns) < 1: 157 raise ValueError("Columns must be a list containing at least one column") 158 for (name, column_type) in columns: 159 is_simple_type = issubclass(column_type, self.base_types) 160 if not is_simple_type: 161 raise TypeError("Column {}'s type is not a simple type: {}".format(name, 162 column_type.__class__.__name__)) 163 converted_columns.append(interfaces.renderers.Column(name, column_type)) 164 self.RowStructure = collections.namedtuple("RowStructure", 165 [self.sanitize_name(column.name) for column in converted_columns]) 166 self._columns = converted_columns 167 if generator is None: 168 generator = [] 169 generator = iter(generator) 170 171 self._generator = generator 172 173 @staticmethod 174 def sanitize_name(text: str) -> str: 175 output = "" 176 for letter in text.lower(): 177 if letter != ' ': 178 output += (letter if letter in 'abcdefghiljklmnopqrstuvwxyz_0123456789' else '_') 179 return output 180 181 def populate(self, function: interfaces.renderers.VisitorSignature = None, initial_accumulator: Any = None) -> None: 182 """Populates the tree by consuming the TreeGrid's construction 183 generator Func is called on every node, so can be used to create output 184 on demand. 185 186 This is equivalent to a one-time visit. 187 """ 188 accumulator = initial_accumulator 189 if function is None: 190 191 def function(_x: interfaces.renderers.TreeNode, _y: Any) -> Any: 192 return None 193 194 if not self.populated: 195 prev_nodes = [] # type: List[TreeNode] 196 for (level, item) in self._generator: 197 parent_index = min(len(prev_nodes), level) 198 parent = prev_nodes[parent_index - 1] if parent_index > 0 else None 199 treenode = self._append(parent, item) 200 prev_nodes = prev_nodes[0:parent_index] + [treenode] 201 if function is not None: 202 accumulator = function(treenode, accumulator) 203 self._row_count += 1 204 self._populated = True 205 206 @property 207 def populated(self): 208 """Indicates that population has completed and the tree may now be 209 manipulated separately.""" 210 return self._populated 211 212 @property 213 def columns(self) -> List[interfaces.renderers.Column]: 214 """Returns the available columns and their ordering and types.""" 215 return self._columns 216 217 @property 218 def row_count(self) -> int: 219 """Returns the number of rows populated.""" 220 return self._row_count 221 222 def children(self, node) -> List[interfaces.renderers.TreeNode]: 223 """Returns the subnodes of a particular node in order.""" 224 return [node for node, _ in self._find_children(node)] 225 226 def _find_children(self, node): 227 """Returns the children list associated with a particular node. 228 229 Returns None if the node does not exist 230 """ 231 children = self._children 232 try: 233 if node is not None: 234 for path_component in node.path.split(self.path_sep): 235 _, children = children[int(path_component)] 236 except IndexError: 237 return [] 238 return children 239 240 def values(self, node): 241 """Returns the values for a particular node. 242 243 The values returned are mutable, 244 """ 245 if node is None: 246 raise TypeError("Node must be a valid node within the TreeGrid") 247 return node.values 248 249 def _append(self, parent, values): 250 """Adds a new node at the top level if parent is None, or under the 251 parent node otherwise, after all other children.""" 252 children = self.children(parent) 253 return self._insert(parent, len(children), values) 254 255 def _insert(self, parent, position, values): 256 """Inserts an element into the tree at a specific position.""" 257 parent_path = "" 258 children = self._find_children(parent) 259 if parent is not None: 260 parent_path = parent.path + self.path_sep 261 newpath = parent_path + str(position) 262 tree_item = TreeNode(newpath, self, parent, values) 263 for node, _ in children[position:]: 264 self.visit(node, lambda child, _: child.path_changed(newpath, True), None) 265 children.insert(position, (tree_item, [])) 266 return tree_item 267 268 def is_ancestor(self, node, descendant): 269 """Returns true if descendent is a child, grandchild, etc of node.""" 270 return descendant.path.startswith(node.path) 271 272 def max_depth(self): 273 """Returns the maximum depth of the tree.""" 274 return self.visit(None, lambda n, a: max(a, self.path_depth(n)), 0) 275 276 _T = TypeVar("_T") 277 278 def visit(self, 279 node: Optional[interfaces.renderers.TreeNode], 280 function: Callable[[interfaces.renderers.TreeNode, _T], _T], 281 initial_accumulator: _T, 282 sort_key: Optional[interfaces.renderers.ColumnSortKey] = None): 283 """Visits all the nodes in a tree, calling function on each one. 284 285 function should have the signature function(node, accumulator) and return new_accumulator 286 If accumulators are not needed, the function must still accept a second parameter. 287 288 The order of that the nodes are visited is always depth first, however, the order children are traversed can 289 be set based on a sort_key function which should accept a node's values and return something that can be 290 sorted to receive the desired order (similar to the sort/sorted key). 291 292 We use the private _find_children function so that we don't have to re-traverse the tree 293 for every node we descend further down 294 """ 295 if not self.populated: 296 self.populate() 297 298 # Find_nodes is path dependent, whereas _visit is not 299 # So in case the function modifies the node's path, find the nodes first 300 children = self._find_children(node) 301 accumulator = initial_accumulator 302 # We split visit into two, so that we don't have to keep calling find_children to traverse the tree 303 if node is not None: 304 accumulator = function(node, initial_accumulator) 305 if children is not None: 306 if sort_key is not None: 307 sort_key_not_none = sort_key # Only necessary because of mypy 308 children = sorted(children, key = lambda x: sort_key_not_none(x[0].values)) 309 if not sort_key.ascending: 310 children = reversed(children) 311 accumulator = self._visit(children, function, accumulator, sort_key) 312 return accumulator 313 314 def _visit(self, 315 list_of_children: List['TreeNode'], 316 function: Callable, 317 accumulator: _T, 318 sort_key: Optional[interfaces.renderers.ColumnSortKey] = None) -> _T: 319 """Visits all the nodes in a tree, calling function on each one.""" 320 if list_of_children is not None: 321 for n, children in list_of_children: 322 accumulator = function(n, accumulator) 323 if sort_key is not None: 324 sort_key_not_none = sort_key # Only necessary because of mypy 325 children = sorted(children, key = lambda x: sort_key_not_none(x[0].values)) 326 if not sort_key.ascending: 327 children = reversed(children) 328 accumulator = self._visit(children, function, accumulator, sort_key) 329 return accumulator 330 331 332class ColumnSortKey(interfaces.renderers.ColumnSortKey): 333 334 def __init__(self, treegrid: TreeGrid, column_name: str, ascending: bool = True) -> None: 335 _index = None 336 self._type = None 337 self.ascending = ascending 338 for i in range(len(treegrid.columns)): 339 column = treegrid.columns[i] 340 if column.name.lower() == column_name.lower(): 341 _index = i 342 self._type = column.type 343 if _index is None: 344 raise ValueError("Column not found in TreeGrid columns: {}".format(column_name)) 345 self._index = _index 346 347 def __call__(self, values: List[Any]) -> Any: 348 """The key function passed as the sort key.""" 349 value = values[self._index] 350 if isinstance(value, interfaces.renderers.BaseAbsentValue): 351 if self._type == datetime.datetime: 352 value = datetime.datetime.min 353 elif self._type in [int, float]: 354 value = -1 355 elif self._type == bool: 356 value = False 357 elif self._type in [str, renderers.Disassembly]: 358 value = "-" 359 elif self._type == bytes: 360 value = b"" 361 return value 362