Home         Authors   Papers   Year of conference   Themes   Organizations        To MES conference

A fast algorithm for data dependency tracking in Software and Firmware analysis and testing
Authors
	Shcherbakov A.S.
Date of publication
	2016
Abstract
	Data dependency analysis plays an important role in Software and Firmware testing and, generally, in scenario exploration and analysis. A data dependency usually may be easily traced dynamically by watching write and read access to the same data aggregates (variables) from different pieces of code; however, application of such knowledge to further test trajectory planning arouses the necessity to propagate dependency information through a process control flow graph (CFG). This means at least quadratic complexity w. r. t. the program size by itself. As a planner’s interest to particular data may change dynamically, one should implement a distinction between active and outdated targets that means even higher complexity. Those facts make such an approach infeasible in practice. As preliminaries, we choose a formalization reducing the task of trajectory planning to atomic acts of pre-observed trajectory nodes alternation (choosing another branch at a given node). We also use hash vectors for representing collections of trajectory planning targets. As well, we reduce data dependency tracking to node subsequence tracking. Within that framework, we present an algorithm providing a reasonable decision on whether it worth to alternate a given trajectory node based on data dependencies found in all successive CFG nodes. The algorithm demonstrates low mean case complexity (about O(log2 M), where M is program size). That a complexity reduction has achieved in two major steps. (1) We use a hierarchical partitioning of control flow into a number of nesting small size blocks. Examples of such blocks are hammock branching, loop, function or procedure call, exception handler and so on. More complex custom blocks covering unusual code patterns are discouraged but allowed. As for plain sequences of statements, we split each one into trees of nested short sequences. A lightweight dynamic linking between blocks according to the current call stack is employed when needed. (2) We avoid recursive traversal of an already visited nested block’s hierarchy each time when we consider entering it by the control flow from inside an embracing block; instead, we use a stored table of hash vectors representing target prefixes previously found throughout that hierarchy.
Keywords
	Software testing, data dependency, data flow, control flow graph, CFG, hammock, dynamic verification, verification, software verification, alternation, propagation in a graph, scenario analysis.
Library reference
	Shcherbakov A.S. A fast algorithm for data dependency tracking in Software and Firmware analysis and testing // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2016. Proceedings / edited by A. Stempkovsky, Moscow, IPPM RAS, 2016. Part 2. P. 76-83.
URL of paper
	http://www.mes-conference.ru/data/year2016/pdf/D175.pdf