Open Systems Laboratory at Illinois

DART: directed automated random testing

By Koushik Sen. In Haifa Verification Conference, volume 6405 of Lecture Notes in Computer Science, 4. Springer, 2009.

Full Text:
Download PDF
Publisher Link:


Testing with manually generated test cases is the primary technique used in industry to improve reliability of software–in fact, such testing is reported to account for over half of the typical cost of software development. I will describe directed automated random testing (also known as concolic testing), an efficient approach which combines random and symbolic testing. Concolic testing enables automatic and systematic testing of programs, avoids redundant test cases and does not generate false warnings. Experiments on real-world software show that concolic testing can be used to effectively catch generic errors such as assertion violations, memory leaks, uncaught exceptions, and segmentation faults. From our initial experience with concolic testing we have learned that a primary challenge in scaling concolic testing to larger programs is the combinatorial explosion of the path space. It is likely that sophisticated strategies for searching this path space are needed to generate inputs that effectively test large programs (by, e.g., achieving significant branch coverage). I will present several such heuristic search strategies, including a novel strategy guided by the control flow graph of the program under test.


    author = "Sen, Koushik",
    editor = "Namjoshi, Kedar S. and Zeller, Andreas and Ziv, Avi",
    title = "{DART}: Directed Automated Random Testing",
    booktitle = "Haifa Verification Conference",
    crossref = "conf/hvc/2009",
    ee = "",
    keywords = "formal methods, software engineering",
    pages = "4",
    year = "2009",

    editor = "Namjoshi, Kedar S. and Zeller, Andreas and Ziv, Avi",
    title = "Hardware and Software: Verification and Testing - 5th
             International Haifa Verification Conference, HVC 2009, Haifa,
             Israel, October 19-22, 2009, Revised Selected Papers",
    ee = "",
    isbn = "978-3-642-19236-4",
    publisher = "Springer",
    series = "Lecture Notes in Computer Science",
    volume = "6405",
    year = "2011",