A fast algorithm for data dependency tracking in Software and Firmware analysis and testing
Data dependency analysis plays an important role in Software and Firmware testing and, generally, in scenario exploration and analysis. 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 process control flow graph (CFG). This means at least quadratic complexity w. r. t. the program size by itself. As planner’s interest to particular data may change dynamically, one should implement 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 preobserved 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 the 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 was obtained 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.