Refactor Internal Graph Representation #8
Description
SandBlaster stores the ReducedGraph mainly as two lists: vertices and edges. Because of this storing strategy, retrieving the neighbours of a node is done by calling the get_next_vertices method [1], which iterates the edges list and returns those edges which start at the vertex given to it as a parameter.
This method of storing the graph is inefficient and, in the future, may cause SandBlaster to run slow when there are large numbers of nodes and edges, as a traversal of this graph (which is necessary when reversing a sandbox profile) is performed in O(num_nodes * num_edges) time, as opposed to the typical O(num_nodes + num_edges) of a graph traversal. Up to iOS 10, there are no more than a few thousand nodes and edges in each graph, for which the running time of the traversal is still low. For newer iOS versions, however, these numbers grow and this traversal can significantly increase reversing times.
For this reason, this internal representation needs to be refactored so that the ReducedVertice class store the node's neighbours list, instead of storing them at the graph level. This would help bring down the traversal complexity to the desired O(num_nodes + num_edges).
[1]
sandblaster/reverse-sandbox/operation_node.py
Line 1180 in 2318f0c