A Fast Algorithm for Finding Vertices Accessible via Constrained Paths in a Control Flow Graph

Shcherbakov A.S. (The University of Melbourne)
Abstract - Modern techniques of directed software and firmware testing widely use the symbolic exploration of conditions important for program execution branch control. However, they are usually ignorant of possible influence of data value assignments to a symbolic representation of an expression. Instead, they tend to use behavioral observation for building alliteratively 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 complexity of finding branch points that control interdependent assignment/usage code fragments execution patterns in a control flow graph. It requires considering of many instances of graph vertex search tasks with some control flow graph vertices to be considered as forbidden (to avoid repeating already seen paths constantly) while. A brute force approach to such a task imposes a too high complexity. 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 program compiled from a source code, and we experimentally prove 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 an 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 the spanning tree for a better complexity when walking around an excepted vertex. As well, we consider approaches to the alignment of such trees to the control flow graph.

Keywords - control flow graph, graph traversing, software testing, software modeling, firmware testing, data dependency, variable assignments, symbolic simulation, directed testing, hammocks, heap.

Быстрый алгоритм нахождения доступных вершин графа управления при ограничениях траекторий

Щербаков А.С. (Университет Мельбурна, г. Москва)
Аннотация - Предлагается эвристически обоснованный алгоритм быстрого вычисления множества доступных вершин графа управления программы, допускающий задание произвольного списка “запрещенных” узлов в динамическом режиме. Исключения. Алгоритм предназначен для ускорения автоматического принятия решений при моделировании и тестировании программно-аппаратных комплексов.

Ключевые слова - граф управления, поиск путей в графе, тестирование программ, моделирование программ, тестирование аппаратно-программных комплексов, направленное тестирование, гамаки, кучи. Heaps.