CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Random Structured Test Data Generation for Black-Box Testing

Michal H. Palka (Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers))
Göteborg : Chalmers University of Technology, 2014. ISBN: 978-91-7385-996-7.- 168 s.

We show how automated random testing can be used to effectively find bugs in complex software, such as an optimising compiler. To test the GHC Haskell compiler we created a generator of simple random programs, used GHC to compile them with different optimisation levels, and then compared the results of running them. Using this simple approach we found a number of optimisation bugs in GHC. This approach for finding bugs proved to be very effective, but we found that implementing a generator of random programs by hand required a large amount of effort. Therefore, we developed an automatic method for deriving random generators of complex test data based on computable boolean predicates that specify the well-formed values of the data type. Defining such a predicate is usually much quicker than implementing a dedicated generator, even if its performance might be comparably lower. In addition, we discovered that the pseudorandom number generator used by us for random testing is unreliable, and that no reliable contruction exists that supports our particular requirements. Consequently, we designed and implemented a high-quality pseudorandom number generator, which is based on a known and reliable cryptographic construction, and whose correctness is supported by a formal argument. Finally, we present how random testing can be used to rank a group of programs according to their relative correctness with respect to their observed behaviour. The ranking method removes the influence of the distribution of the random data generator used for testing, which results in a reliable ranking.

Denna post skapades 2014-03-28. Senast ändrad 2014-10-10.
CPL Pubid: 195849


Läs direkt!

Lokal fulltext (fritt tillgänglig)

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Programvaruteknik (Chalmers)



Chalmers infrastruktur

Relaterade publikationer

Inkluderade delarbeten:

Ranking programs using black box testing

Testing an Optimising Compiler by Generating Random Lambda Terms

Splittable Pseudorandom Number Generators using Cryptographic Hashing

Generating Constrained Random Data with Uniform Distribution


Datum: 2014-04-25
Tid: 10:00
Lokal: Lecture room EA, ED&IT building, Rännvägen 6B, Chalmers University of Technology
Opponent: Prof. John Regehr, School of Computing, University of Utah

Ingår i serie

Doktorsavhandlingar vid Chalmers tekniska högskola. Ny serie