A fast Algorithm for Finding Vertices Accessible via Constrained Paths in a Control Flow Graph
Modem techniques of directed software and firmware testing widely use symbolic exploration of conditions for program execution branch control. However, they are usually ignorant of possible influence of data value assignments to the symbolic representation of an expression. Instead, they tend to use behavioral observations for building iteratively converging sets of weak and strong hypotheses. The cause lays in the fact that although data assignment dependency information is relatively easy to extract, deriving reasonable solutions on desirable branch alternation at program branching points is a rather complicated task. One of the main challenges is high complexity of finding branch points that control interdependent assignment/usage code fragments execution patterns in a control flow graph. It requires considering graph vertex search tasks with some control vertices being restricted (in order to avoid repeating already seen paths). We propose a fast and scalable algorithm for finding sets of accessible vertices in a control flow graph being given a start vertex and a dynamically supplied list of excepted vertices. This empirically supported algorithm essentially relies on the typical structure of a program compiled from a source code. We prove experimentally that the expected complexity of each query processing is lower than O(log N), where N is total number of code fragments. The algorithm is based on substitution of a control flow graph with its spanning tree, and considering a set of vertices accessible from somewhere as a union of a vertex interval and a set of outstanding (out-of-cone) vertices. To collect the latter at a low complexity, we propose the usage of specially designed expression-graph powered version of heap containers. We also consider building (more) balanced back-off versions of spanning tree to ensure a lower complexity when walking around an excepted vertex. As well, we consider the alignment of back-off tree to its control flow graph.