Cross-Entropy Based Testing

Hana Chockler, Eitan Farchi, Benny Godlin, Sergey Novikov

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

20 Citations (Scopus)
67 Downloads (Pure)

Abstract

In simulation-based verification, we check the correctness of a given program by executing it on some input vectors. Even for medium-size programs, exhaustive testing is impossible. Thus, many errors are left undetected. The problem of increasing the exhaustiveness of testing and decreasing the number of undetected errors is the main problem of software testing. In this paper, we present a novel approach to software testing, which allows us to dramatically raise the probability of catching rare errors in large programs. Our approach is based on the cross-entropy method. We define a performance function, which is higher in the neighborhood of an error or a pattern we are looking for. Then, the program is executed many times, choosing input vectors from some random distribution. The starting distribution is usually uniform, and it is changed at each iteration based on the vectors with highest value of the performance function in the previous iteration. The crossentropy method was shown to be very efficient in estimating the probabilities of rare events and in searching for solutions for hard optimization problems. Our experiments show that the cross-entropy method is also very efficient in locating rare bugs and patterns in large programs.We show the experimental results of our cross-entropy based testing tool and compare them to the performance of ConTest and of Java scheduler.
Original languageEnglish
Title of host publicationProceedings of Formal Methods in Computer-Aided Design (FMCAD)
PublisherIEEE Computer Society
Pages101-108
Number of pages8
Publication statusPublished - 11 Nov 2007

Fingerprint

Dive into the research topics of 'Cross-Entropy Based Testing'. Together they form a unique fingerprint.

Cite this