Automatically generating search heuristics for concolic testing

Sooyoung Cha, Seongjoon Hong, Junhee Lee, Hakjoo Oh

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    28 Citations (Scopus)

    Abstract

    We present a technique to automatically generate search heuristics for concolic testing. A key challenge in concolic testing is how to effectively explore the program's execution paths to achieve high code coverage in a limited time budget. Concolic testing employs a search heuristic to address this challenge, which favors exploring particular types of paths that are most likely to maximize the final coverage. However, manually designing a good search heuristic is nontrivial and typically ends up with suboptimal and unstable outcomes. The goal of this paper is to overcome this shortcoming of concolic testing by automatically generating search heuristics. We define a class of search heuristics, namely a parameterized heuristic, and present an algorithm that efficiently finds an optimal heuristic for each subject program. Experimental results with open-source C programs show that our technique successfully generates search heuristics that significantly outperform existing manually-crafted heuristics in terms of branch coverage and bug-finding.

    Original languageEnglish
    Title of host publicationProceedings of the 40th International Conference on Software Engineering, ICSE 2018
    PublisherIEEE Computer Society
    Pages1244-1254
    Number of pages11
    ISBN (Electronic)9781450356381
    DOIs
    Publication statusPublished - 2018 May 27
    Event40th International Conference on Software Engineering, ICSE 2018 - Gothenburg, Sweden
    Duration: 2018 May 272018 Jun 3

    Publication series

    NameProceedings - International Conference on Software Engineering
    ISSN (Print)0270-5257

    Conference

    Conference40th International Conference on Software Engineering, ICSE 2018
    Country/TerritorySweden
    CityGothenburg
    Period18/5/2718/6/3

    Bibliographical note

    Publisher Copyright:
    © 2018 ACM.

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'Automatically generating search heuristics for concolic testing'. Together they form a unique fingerprint.

    Cite this