source/blog/posts/2009/10/20-klee--automatically-generating-tests-that-achieve-high-coverage.rst

   1 Title: KLEE, automatically generating tests that achieve high coverage
   2 Tags: en, d, llvm, klee, vm, test, coverage, software
   3
   4 This is the abstract_ of the paper_ describing KLEE_, a new LLVM_
   5 sub-project announced with the upcoming `2.6 release`_:
   6
   7     We present a new symbolic execution tool, KLEE_, capable of automatically
   8     generating tests that achieve high coverage on a diverse set of complex and
   9     environmentally-intensive programs. We used KLEE_ to thoroughly check all 89
  10     stand-alone programs in the GNU_ COREUTILS_ utility suite, which form the
  11     core user-level environment installed on millions of Unix systems, and
  12     arguably are the single most heavily tested set of open-source programs in
  13     existence. KLEE_\ -generated tests achieve high line coverage — on average
  14     over 90% per tool (median: over 94%) — and significantly beat the coverage
  15     of the developers' own hand-written test suites. When we did the same for
  16     75 equivalent tools in the BUSYBOX_ embedded system suite, results were even
  17     better, including 100% coverage on 31 of them. We also used KLEE_ as a bug
  18     finding tool, applying it to 452 applications (over 430K total lines of
  19     code), where it found 56 serious bugs, including three in COREUTILS_ that
  20     had been missed for over 15 years. Finally, we used KLEE_ to cross-check
  21     purportedly identical BUSYBOX_ and COREUTILS_ utilities, finding functional
  22     correctness errors and a myriad of inconsistencies.
  23
  24 I **have** to try this...
  25
  26 .. _abstract: http://llvm.org/pubs/2008-12-OSDI-KLEE.html
  27 .. _paper: http://llvm.org/pubs/2008-12-OSDI-KLEE.pdf
  28 .. _KLEE: http://klee.llvm.org/
  29 .. _LLVM: http://llvm.org/
  30 .. _`2.6 release`: http://llvm.org/docs/ReleaseNotes.html
  31 .. _GNU: http://www.gnu.org/
  32 .. _COREUTILS: http://www.gnu.org/software/coreutils/
  33 .. _BUSYBOX: http://www.busybox.net/
  34
  35 .. vim: set et sw=4 sts=4 :