Structural testing is one of the basic approaches for identifying test cases. Because of complexity of programming languages and variety of applications, an efficient approach to automated generation of structural test data is to breed search iteratively by profiling of program execution. Based on Messy GA, an automated approach for generating such data is proposed in this paper by solving F(X), a test coverage function of test data set. It utilizes Messy GA’s prominent feature that can optimize complicated problems without prior knowledge about schema arrangement in chromosomes, so that it can improve concurrency level of searching and test coverage. Compared with other approaches based on GA, the experimental results for several typical programs and real-world applications show that it can generate higher quality test data more efficiently, and can be applied to larger applications.