Coyote C++ is an automated testing tool that uses a sophisticated concolic-execution-based approach to realize fully automated unit testing for C and C++. While concolic testing has proven efective for languages such as C and Java, tools have struggled to achieve a practical level of automation for +C+ due to its many syntactical intricacies and overall complexity. Coyote C++ is the first automated testing tool to breach the barrier and bring automated unit testing for C++ to a practical level suitable for industrial adoption, consistently reaching around 90% code coverage. Notably, this testing process requires no user involvement and performs test harness generation, test case generation and test execution with “one-click” automation. In this paper, we introduce Coyote C++ by outlining its high-level structure and discussing the core design decisions that shaped the implementation of its concolic execution engine. Finally, we demonstrate that Coyote +C+ is capable of achieving high coverage results within a reasonable timespan by presenting the results from experiments on both open-source and industrial software.
tinuously escalating, necessitating thorough validation colic execution, a modern variant of symbolic execution, methods such as white-box testing. However, given the and features exquisite harness generation capabilities. rapid increase in code scale and complexity in the software industry, white-box testing can be time-consuming and resource-intensive[1], often leading to budget con
which Coyote C++ achieves a practical level of high coverage through test case generation. In order to practically straints. For this reason, there has been a long-standing utilize automated unit testing tools in the field, we proneed for automation in white-box testing.
Lately, eforts to automate white-box unit testing are
ing showing promising results for Java [2, 3], C [4, 5, 6],
approaching practical feasibility, with automated test- above 90% and branch coverage above 80% should be
ogy for C++ has proven to be challenging due to the by our customers in the automotive industry.
binary code [7, 8], and a few other programming lan- levels of coverage and performance according to these
guages [
harness generation and test case generation to test execution. The automated test case generation is based on conplates with all their intricacies are just two examples testing and then examine design decisions made by existunit testing tool designed for C/C++. With a single click, obtained from open-source projects and real-world induslanguage’s unique features and overall complexity1[2].
Implicitly invoked copy or move constructors and temof C++ language features that are especially dificult to handle in automated white-box unit testing.
In this paper, we introduce Coyote C++, an automated Korea
(S. Oh) CEUR
CEUR
Workshop Proceedings (CEUR-WS.org)
The rest of this paper is organized as follows. We ifrst look at research on concolic-execution-based unit ing systems to build eficient concolic execution engines in related works. Next, we provide an overview of the implementation of Coyote C++, and present test results trial projects. Finally, we conclude the paper by outlining our plans for further improving Coyote C++.
CEUR Workshop Proceedings
ceur-ws.org ISSN1613-0073 rather than concrete values. Due to scalability issues while QSYM [21] and CREST [22] are instrumentationwith symbolic execution, this technique has been ex- based. tended into concolic execution [5, 6]. The main idea of concolic execution is to compute test inputs from path 2.3. Mitigating Path Explosion conditions which are obtained by tracking both concrete values and symbolic values. Concolic execution has been Another important design decision is how to deal with the anticipated in the automated testing domain due to its path explosion problem commonly encountered when known success in test case generation. However, this performing concolic execution on programs with comresearch has not yet reached a practical level of test gen-plex control flow. In such situations, the search space eration for whole programs. of concolic execution can grow exponentially due to the
Nevertheless, concolic execution is known to be re- many possible combinations of branches. To avoid this ismarkably successful in unit test generation, e.g. for sue, concolic execution engines use a variety of heuristic Java [2, 3] and C [4, 5, 6]. For C++ however, automated search strategies. Notable search strategies include DFS testing has still been far from viable for industrial pur- (depth-first search), BFS (breadth-first search), random poses despite recent research eforts [14, 12]. path selection, coverage-optimized search, and adaptive
When implementing concolic execution there are many heuristics [15, 23]. options for realizing various aspects of the engine1[5].
Especially the engine’s execution mode, analysis target, 2.4. Memory Model handling of the path explosion problem, and its memory model can largely afect the performance of the concolic When modelling the symbolic memory of a concolic exeexecution engine in terms of coverage and execution cution engine, one can choose between treating memory time. addresses as symbolic or concrete values. The symbolic approach can theoretically handle all possible paths, but 2.1. Online/Ofline Mode this approach may cause path constraints to become too complex for current SMT solvers. On the other hand, usConcolic execution can be implemented in online or of- ing concrete addresses might not cover all possible paths lfine mode. In online mode, the concolic execution en- due to overly simplified path conditions. In practice, a gine explores multiple paths in a single run by forking on fully symbolic model is used by tools like KLEE [ 16], and branch points. The advantage of this method is that there a concrete address model is used by SAGE [7] among othis no need to re-execute the common prefixes of multi- ers. Additionally, there are tools like Mayhem 1[7] that ple paths. However, it requires a substantial amount of use a combination of symbolic and concrete addressing memory to store all the states of multiple paths. Ofline schemes. mode on the other hand explores only one path in a single run. This method requires less memory than online 3. The Design of Coyote C++ mode, making it better suited for parallelization. However, since ofline mode always starts at the beginning of the program for every path, it spends a considerable 3.1. Overview amount of time on re-examining common path prefixes.
Prominent tools using online mode are KLEE [16], Mayhem [17], and S2E [18], whereas SAGE [7] utilizes ofline concolic execution.
and discuss the core decisions that influenced its design.
As shown in the diagram in Fig.1, the Coyote C++ tool is divided into two main parts. The first part builds executable test files based on harness generation, while 2.2. Emulation/Instrumentation the second part handles generating test cases through concolic execution.
There are two main methods for collecting information In the first phase, Coyote C ++ uses a harness generaabout the execution path taken during concrete execution tor module to automatically generate test stubs and test of the program under test. The first method performs drivers for test execution and inserts instrumentation symbolic execution at the same time as concrete exe- code for concolic execution. This instrumentation is percution by running the program under test inside of an formed on LLVM IR level. Next, the binary generation emulator such as QEMU [19]. The second method in- module compiles the created testbed to executable files stead instruments the program under test with code that used in the second part. handles symbolic execution and the collection of informa- While running the executable test file in the second tion about the concrete execution of the program. Well- phase, the instrumentation code produces trace files conknown emulator-based tools are angr 2[0] and KLEE [16], taining information about the concrete program execution on the level of LLVM IR instructions. These trace ifles are then used to reconstruct their respective execu- during testable binary generation. The main reason for tion paths, and with this information symbolic execution choosing ofline testing over online testing is that it is is performed on the LLVM IR level to generate new test more suitable for parallelization, which is essential for input data. When this concolic execution cycle termi- providing good testing performance. Additionally, ofline nates, the achieved test coverage is calculated based ontesting is more advantageous from a memory managethe generated trace files. ment standpoint.
A key factor for achieving high code coverage is the 3.2. Design Decisions of Coyote C++ search strategy that controls in which order the possible execution paths of a program are explored. During While implementing Coyote C++, many important de- testcase generation, the test files are initially executed sign decisions had to made. In the modules responsi- with all test inputs set to default values. The trace files ble for the testable binary generation, these decisions generated from this are then analyzed using concolic were generally made with the goal of enabling a wide execution techniques to create new test case inputs for range of transformations on intermediate code models visiting new paths. As our search strategy for exploring while retaining a suficiently strong connection between of candidate paths, we adopted a hybrid approach that these models and the original source code. Most design combines CCS (Code Coverage Search) and DFS. CCS decisions afecting the testcase generation phase were focuses on exploring code areas that have not been trastrongly influenced by the need to find a suitable tradeof versed yet, making it advantageous for quickly reaching between the achieved code coverage and performance in high coverage. However, because CCS performs rather terms of test time or resource consumption. aggressive pruning on execution paths, it may produce
A fundamental design decision made in Coyote C++ is unsatisfiable path conditions in certain situations. To using LLVM IR as its symbolic execution target. This al- make up for these issues, we also use the DFS strategy lows for more precision than doing source level symbolic in addition to CCS. DFS is a search strategy that has the execution while retaining more information about the potential to cover code areas not covered by CCS, but it original source code that would be lost when lowering comes with the drawback of substantial time consumpeven further to the assembly level. Also, using LLVM as tion. Usually, either of these strategies terminates once a foundation for Coyote C++ allows for greater freedom every branch it has discovered has been explored. Conin code transformations during harness generation, by- colic execution may however also be terminated early if passing syntactic constraints present on the source code a designated amount of test cases has been generated or level. if a timeout has been reached.
We decided to implement ofline testing by inserting in- Finally, a significant factor influencing the performance strumentation code into the LLVM IR code of the testbed of concolic execution in C++ is the memory model. Similar to Mayhem, the approach implemented in Coyote 4.1. Experiment on Open-Source Projects C++reads values from memory symbolically but writes values to concrete memory addresses. Utilizing sym- For the first evaluation, we chose to reuse the test set bolic reads in contrast to reading from concrete addresses curated by Shin and Yoo for a survey on white-box auleads to a more faithful representation of path constraints, tomated testing tools [24], as it contains open-source thereby enhancing the potential for generating appropri- projects written in C and C++ from a wide variety of ate test cases. For write operations however, we chose application domains and was composed specifically for to rely on concrete addresses because symbolic writes the evaluation of automated testing tools such as Coyare prone to making the process of solving the path con- ote C++. This survey also concluded that currently no straints overly expensive. other commercial tools truly support automated testing for C++ programs. Among open-source tools for C++,
CITRUS [12] is no longer publicly available, and we were 4. Experimental Results not able to successfully apply UTBot [14] to the selected test projects due to its rather limited support for the To showcase the performance of Coyote C++, we present C++ syntax. Thus, unfortunately there were no suitable experimental results for a set of diverse open-source candidates to compare Coyote C++ against in terms of projects as well as several industrial software projects coverage and test time. from one of our customers, Hyundai KEFICO. While our Table 1 shows the statement1 and branch coverage tool allows user to add test cases and write driver func- results achieved by Coyote C++ on the ten open-source tions for achieving higher coverage, all experimental re- projects in the test set as well as the time needed for sults were obtained through one-click automation with- conducting the automated test generation and execution out any user intervention. for each project. Coyote C++ achieves statement coverages between 86.7% (s2n-tls) and 99.9% (mathc) as well
1As statements we consider only executable lines of code. In contrast to physical lines of code, this excludes e.g. whitespace, comments, and type declarations. as branch coverages between 81.3% (s2n-tls) and 100% 5. Conclusion and Future Work (mathc). Summing up the number of overall covered lines/branches and dividing them by the total number In this paper, we presented Coyote C++, an industryof lines and branches in all ten projects yields a remark- grade automated testing tool based on concolic execuable combined statement coverage of 92.5% and branch tion. After describing the general tool architecture, we coverage of 84.9%. discussed the core design decisions for our implementa
The test times presented in table1 were attained from tion of its concolic testing engine. Finally, we evaluated an Intel Core i7-13700 system with 64GB of RAM run- the performance of Coyote C++ in terms of achieved ning Ubuntu 20.04. Overall, the test of all ten projects coverage and testing time on both a test set of diverse combined only took about three and a half hours, with open-source projects and industry code from one of our individual testing times ranging between three minutes corporate customers. We were able to demonstrate that (mathc) and just above one hour (s2n-tls). That makes it Coyote C++ can achieve high statement/branch coverage more than six times faster than the test times reported of around 90% or higher in a reasonable amount of time in the previously mentioned study [24], which we con- for software projects from a wide variety of application sider a significant improvement despite possible minor domains. diferences between test setups. Furthermore, with the While Coyote C++ is already yielding promising reexception of the qnite project, the testing speed on all sults both on open-source projects and in real industry projects surpasses our definition of practicality, with an applications, it is our plan to continuously improve the overall testing speed of roughly 17,000 statements per tool both in terms of reliably achieving high coverage hour. results and broadening its capabilities in the field of automated testing. 4.2. Results on Industry Projects One goal for the near future is target testing for embedded software. Our tool currently performs host testing, Table 2 presents testing results produced by Coyote C++ meaning tests are not executed on the hardware that on automotive control software projects from our cus- would run the program under test in a production envitomer Hyundai KEFICO, a member of Hyundai Motors ronment, but rather on a separate computer, e.g., a test Group. As details about these projects such as their ac- engineer’s computer or a test server. Especially in the tual names are strictly internal information, we will refer embedded domain however, the discrepancy between emto them as target A, B and C. bedded hardware in the production environment and the
The coverage results for these industrial projects are consumer or server hardware in the testing environment quite similar to the open-source projects, with an average may lead to inaccurate test results. Thus, we are planning statement coverage of 92.9% and an average branch cov- to implement target testing support so that tests may be erage of 86.7%. At our customer, Coyote C++ is employed run directly on production hardware. not in a controlled test environment but rather in a busi- Approaching the goal of increasing automated test ness setting on multiple machines with varying hardware coverage from a diferent perspective, we also strive to specifications. Due to these circumstances and the fact provide users of our tool with feedback as to how they that a subset of the test results were produced incremen- should change their code so that Coyote C++ will likely tally over a longer period of time, we presently do not yield better coverage results for it. While we would like have any meaningful test time measurements available to give such guidance on the basis of code metrics, our to report for these projects. initial investigations have shown that traditional code
While project C individually yields a slightly subpar metrics such as cyclomatic complexity have little to no coverage, our notion of practicality in terms of cover- correlation with automated test coverage. Thus, we see age achieved (statement coverage>90%, branch coverage the need for more thorough research involving the de>80%) is upheld both by projects A and B individually velopment of new code metrics that can serve as a better as well as all three projects combined. This again rein- estimate for the coverage results produced by automated forces our claim that Coyote C++ is not simply a research testing and Coyote C++ in particular. prototype which only works on a limited set of specially curated programs but is rather a mature tool that can also handle more challenging industry software. Also, it References should be noted that automated testing with such high [1] L. Luo, Software testing techniques, Institute for coverage results for these projects is only possible be- software research international Carnegie mellon cause Coyote C++ has explicit handling for some common university Pittsburgh, PA 15232 (2001) 19. code patterns in embedded software that would usually [2] G. Fraser, A. Arcuri, A large-scale evaluation of aumake automated testing dificult or plainly impossible, tomated unit test generation using EvoSuite, ACM such as the usage of fixed memory addresses in code.