Case StudiesWe illustrate two case studies that show how CUTE can detect errors. In the second case study, we also present results that show how CUTE achieves branch coverage of the code under test. We performed all experiments on a Linux machine with a dual 1.7 GHz Intel Xeon processor.Data Structures of CUTEWe applied CUTE to test its own data structures. CUTE uses a number of non-standard data structures at runtime, such as cu_linear to represent linear expressions, cu_pointer to represent pointer expressions, cu_depend to represent dependency graphs for path constraints etc. Our goal in this case study was to detect memory leaks in addition to standard errors such as segmentation faults, assertion violation etc. To that end, we used CUTE in conjunction with valgrind [3]. We discovered a few memory leaks and a couple of segmentation faults that did not show up in other uses of CUTE. This case study is interesting in that we applied CUTE to partly unit test itself and discovered bugs. We briefly describe our experience with testing the cu_linear data structure. We tested the cu_linear module of CUTE in the depth-first search mode of CUTE along with valgrind. In 537 iterations, CUTE found a memory leak. The following is a snippet of the function cu_linear_add relevant for the memory leak:
cu_linear *
cu_linear_add(cu_linear *c1, cu_linear *c2, int add) {
int i, j;
cu_linear* ret=(cu_linear*)malloc(sizeof(cu_linear));
... // skipped 18 lines of code
if(ret->count==0) return NULL;
If the sum of the two linear expressions passed as arguments
becomes constant, the function returns NULL without freeing
the memory allocated for the local variable ret. CUTE
constructed this scenario automatically at the time of testing.
Specifically, CUTE constructed the sequence of function calls
l1=cu_linear_create(0); l1=cu_linear_create(0);
l1=cu_linear_negate(l1); l1=cu_linear_add(l1,l2,1); that
exposes the memory leak that valgrind detects.
SGLIB LibraryWe also applied CUTE to unit test SGLIB [2] version 1.0.1, a popular, open-source C library for generic data structures. The library has been extensively used to implement the commercial tool Xrefactory. SGLIB consists of a single C header file, sglib.h, with about 2000 lines of code consisting only of C macros. This file provides generic implementation of most common algorithms for arrays, lists, sorted lists, doubly linked lists, hash tables, and red-black trees. Using the SGLIB macros, a user can declare and define various operations on data structures of parametric types. The library and its sample examples provide verifier functions (can be used as repOk) for each data structure except for hash tables. We used these verifier functions to test the library using the technique of repOk mentioned in [1]. For hash tables, we invoked a sequence of its function. We used CUTE with bounded depth-first search strategy with bound 50. Figure 1 shows the results of our experiments. We chose SGLIB as a case study primarily to measure the efficiency of CUTE. As SGLIB is widely used, we did not expect to find bugs. Much to our surprise, we found two bugs in SGLIB using CUTE. The first bug is a segmentation fault that occurs in the doubly-linked-list library when a non-zero length list is concatenated with another zero-length list. CUTE discovered the bug in 140 iterations (about 1 seconds) in the bounded depth-first search mode. This bug is easy to fix by putting a check on the length of the second list in the concatenation function. The second bug, which is a more serious one, was found by CUTE in the hash table library in 193 iterations (in 1 second). Specifically, CUTE constructed the following valid sequence of function calls which gets the library into an infinite loop:
typedef struct ilist { int i; struct ilist *next; } ilist;
ilist *htab[10];
main() {
struct ilist *e,*e1,*e2,*m;
sglib_hashed_ilist_init(htab);
e=(ilist *)malloc(sizeof(ilist)); e->next = 0; e->i=0;
sglib_hashed_ilist_add_if_not_member(htab,e,&m);
sglib_hashed_ilist_add(htab,e);
e2=(ilist *)malloc(sizeof(ilist)); e2->next = 0; e2->i=0;
sglib_hashed_ilist_is_member(htab,e2);
}
where ilist is a struct representing an
element of the hash table. We reported these bugs to the SGLIB
developers, who confirmed that these are indeed bugs.
References
File translated from TEX by TTH, version 3.71. On 28 Jan 2006, 15:22. |