Retrograde software analysis is a set of software techniques related to software design

Design

Design as a noun informally refers to a plan or convention for the construction of an object or a system while “to design” refers to making this plan...

, development, software testing

Software testing

Software testing is an investigation conducted to provide stakeholders with information about the quality of the product or service under test. Software testing can also provide an objective, independent view of the software to allow the business to appreciate and understand the risks of software...

, debugging

Debugging

Debugging is a methodical process of finding and reducing the number of bugs, or defects, in a computer program or a piece of electronic hardware, thus making it behave as expected. Debugging tends to be harder when various subsystems are tightly coupled, as changes in one may cause bugs to emerge...

 and code analysis.
All these methods emanate from executing a program backward - instead of taking input data and following the execution path, we start from the output data and, by executing the program backward, command by command, analyze data that could lead to the current output. The techniques are closely related to data-flow analysis

Data-flow analysis

Data-flow analysis is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program's control flow graph is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The...

 and retrograde analysis

Retrograde analysis

In chess, retrograde analysis is a computational method used to solve game positions for optimal play by working backward from known outcomes , such as the construction of endgame tablebases. In game theory at large, this method is called backward induction...

 used in game theory

Game theory

Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...

. Somewhat counter-intuitive for a standard development cycle, where we switch a program between development and testing team, it offers many advantages.

Debugging techniques

After a bug is found, normally, the first task is to find which line is the last executed, then we follow the code backward calculating all possible values of variables and the state of objects before that line, step by step, until we discover the problem. All operations are reversed. Incrementing becomes decrementing, multiplication - division, we enter the loop by the opposite condition etc.

Testing techniques

Every program has the set of actions, values or attributes which we expect at the exit. For example, for sorting, an array should be sorted at the exit. In order to analyze what a program does for each input, we start with the required output conditions or values and going backward, line by line, we collect the states that lead precisely to the output. Once we reached the program's entry point, we have got the complete set of initial states that cause the required output. The remaining input states and values are those that will not lead to the output. For example, in order to test a sorting algorithm, we start with all sorted outputs and then, by reversing the code execution, we try to find at the input all different permutations of values; any missing permutation is the one that the algorithm will not sort for. This technique can greatly reduce the number of test cases, for example, for sorting network

Sorting network

A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other...

it reduces the number of test cases from 2ⁿ to just n.

Development and design techniques

We start from the universal operation that would solve our problem, but it is, on its own, infeasible with the current computer architecture. (For example, to obtain an inverse permutation of an array 5,3,1,4,2 we should mark the positions 5₁, 3₂, 1₃, 4₄, 2₅ and exchange the position for the value 1₅, 2₃, 3₁, 4₄, 5₂, which leads to the solution 3₁, 5₂, 2₃, 4₄, 1₅, but we cannot do that directly in-place.) We continue the task by removing one one by one all found obstacles until we close a feasible solution with the same functionality.

Algorithm verification techniques

This is similar to the testing techniques with the difference that we can use an appropriately abstracted representation of data and then starting from the expected final result follow the program backward until we collect all input data which lead to the correct output. This analysis is always strict and applicable to any algorithm. Abstract level of representation could be, for example for sorting networks, a binary representation of possible outputs: 0, 1, 01, 11, 001, 011, 111, 0000, 0001, 0011, 0111, 1111, knowing that it is sufficient to use binary arrays to test any sorting procedure.

Future

Retrograde software analysis is extremely powerful both theoretically and practically. Still, it is somewhat difficult to create a real-time environment that would be able to execute a program in backward manner. The main obstacle is that the number of possible states even for a few chained conditional statements grows exponentially. However, in reality, if we are not able to perform a retrograde software analysis due to the huge number of possible essentially different states, we would have trouble claiming that a program works properly anyway. One of the solutions is in creating a layer of abstract data representation for different classes of states. Creating a development tool capable of executing a program backward would create a new powerful platform, because a developer would be able to immediately analyze the effect of any decision made through a development cycle.

External links

Mohnen, Markus A Graph—Free Approach to Data—Flow Analysis 2002 Springer http://dx.doi.org/10.1007/3-540-45937-5_6