Software Test Generation Using Refinement Types

Abstract

A novel approach for automatic software test generation is presented, which combines ideas from structural and functional testing as well as formal verification methods. It involves as an intermediate step, the construction of graphs and refinement types, which can be regarded as an automatically constructed semi-specification and used for formal verification. The technique is illustrated using a simple functional language, with algorithms for assigning refinement types and for test generation. Some desirable theoretical properties of the approach are briefly considered. It is also compared informally to other well-known as well as new techniques for automatic test generation.