CUTE: A Concolic Unit Testing Engine for C

Koushik Sen, Darko Marinov, Gul Agha

  • Read: 22 Apr 2025
  • Published: 01 Sept 2005

ACM SIGSOFT Software Engineering Notes, Volume 30, Issue 5, Pages 263 - 272

https://doi.org/10.1145/1095430.1081750

See also: DART.

Q&A (link)

What are the motivations for this work?

  • See Abstract, Introduction.
  • The paper addresses the problem of automating unit testing with memory graphs as inputs.
  • For unit testing, a program is decomposed into units, where each unit is a collection of functions. Unit testing requires specification of values for the inputs to the unit. One wants to automatically generate such inputs to improve the range of behaviors observed.
  • Symbolic execution with depth first backtracking can easily lead to path explosion.
  • A challenge faced by DART is to provide methods which extract and solve the constraints generated by a program. this problem is particularly complex for programs which have dynamic data structures using pointer operations. CUTE proposes a method to prepresent and solve approximate pointer constraints.

What is the proposed solution?

  • See Introduction, Section 2, Section 3.
  • Key idea to deal with pointer constraint is to represent inputs for the unit under test using a logical input map that represents all inputs, including (finite) memory graphs, as a collection of scalar symbolic variables and then to build constraints on these inputs by symbolically executing the code under test.
  • Separate pointer constraints from integer constraints.
  • CUTE implements a solver for both arithmetic and pointer constraints.
  • A highly illustrative example is given in Section 2.
  • Section 3 provides more details of how CUTE works.
  • Like DART, CUTE uses lp_solve as its constraint solver, it solves integer linear constraints.

cute example

What is the work’s evaluation of the proposed solution?

  • See Section 4.
  • Used CUTE to test its own data structures. Memory leak detected after 537 iterations.
  • Used CUTE to unit test SGLIB version 1.0.1, a popular, open-source C library for generic data structures, reached decent branch coverage (96%+) in most library functions. Some unreached branches contain assert statements that were never violated.

What is your analysis of the identified problem, idea and evaluation?

CUTE focuses on dealing with pointer constraints. It’s a clever idea to separate pointer constraints and integer constraints. A limitation is that CUTE needs to instrument tested code.

What are the contributions?

  • See Introduction, Section 6.
  • Symbolic execution tool CUTE.
  • The work shows that approximate symbolic execution for testing code with dynamic data structures is feasible and scalable.
  • The work shows how to efficiently generate dynamic data structures by incrementally adding and removing a node, or by aliasing two pointers.

What are future directions for this research?

  • See Section 6.
  • The authors are working on how to test programs with concurrency using a similar method.

What questions are you left with?

NONE

What is your take-away message from this paper?

NONE

GPT-generated Keynotes

  1. Concolic Execution Strategy: CUTE merges concrete execution (running the program with actual inputs) and symbolic execution (analyzing program paths with symbolic inputs) to efficiently explore feasible execution paths. This hybrid approach allows for systematic test input generation without the redundancy or false positives often associated with purely random or symbolic methods. ​

  2. Handling Pointer-Based Inputs: CUTE addresses the challenges of testing functions with pointer arguments by modeling inputs as memory graphs. It introduces a logical input map that represents these memory graphs using a finite set of scalar symbolic variables, simplifying the representation and analysis of complex pointer structures. ​

  3. Constraint Generation and Solving: During execution, CUTE collects constraints from symbolic execution paths. By negating one of these constraints, it generates new inputs that steer the program along previously unexplored paths. This iterative process continues until all feasible paths are covered or a specified coverage criterion is met. ​

  4. Efficient Constraint Handling: A significant contribution of CUTE is its separation of pointer constraints from scalar constraints. This distinction allows for more efficient constraint solving, as pointer constraints can be simplified and managed independently, reducing the complexity of symbolic expressions and improving the performance of the constraint solver. ​

  5. Instrumentation and Execution Workflow: CUTE instruments the target program to monitor execution and collect necessary data. It then performs both concrete and symbolic executions: the concrete execution provides actual runtime behavior, while the symbolic execution analyzes the program’s logic paths. The tool uses the collected constraints to guide the generation of new test inputs systematically

Written on