Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

A Fast Algorithm for Finding Vertices Accessible via Constrained Paths in a Control Flow Graph
Authors
	Shcherbakov A.S.
Date of publication
	2018
DOI
	10.31114/2078-7707-2018-2-92-98
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.
Library reference
	Shcherbakov A.S. A Fast Algorithm for Finding Vertices Accessible via Constrained Paths in a Control Flow Graph // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2018. Issue 2. P. 92-98. doi:10.31114/2078-7707-2018-2-92-98
URL of paper
	http://www.mes-conference.ru/data/year2018/pdf/D075.pdf