Software Partitioning for Effective Automated Unit Testing

Abstraction
We discuss preliminary experimental results shownig that automatic software partitinoing can significantly increase test coverage without generating too many false alarms caused by unrealistic inputs being injected at interfaces between units.

1. INTRODUCTION
A new idea in this area is Directed Automated Random Testing(DART), which fully automateds software testing by combining three main techniques: 

(1) automated extraction of the interface of a program with its external environment using static source-code parsing;
(2) automatic generation of a test friver for this interface that performs random testing to simulate the most general environment the program can operate in; and
(3) dynamic analysis of how the program behaves under random testing and automatic generation of new test inputs that direct the execution along alternative program paths.

For simplicity, we consider in this work partitioning algorithms that make use of information exposed by control interfaces only.

4.1 Callee Popularity
Formalizing the above intuition, our first algorithm generates a partition of units in which functions f and g are more likely to be assigned to the same unit if f calls g and g is not very popular.

Theorem: For a call graph G over a set of functions S and given a set of control interfaces of S, the algorithm PartitionCP(S) creates a partition of G.

4.2 Shared Code
If two functinos f and g call many of the same functions, then it is likely that the higher-level operations they perform are functionally more related than with other functions that call a completely disjoint set of sub-functions. Therefore, functions that share a lot of sub-functions should perhaps be grouped in a same unit.

Theorem: For a call graph G over a set of functions S and given a set of control interfaces of S, the algorithm PartitionSC(S) creates a partitino of G.

5. EXPERIMENTAL RESULTS