Experiments

To estimate the run time overhead incurred by the range checking for each C library function, we ran a small program that calls each C library function in a tight loop (loop count is 100,000,000).

The range checking (done in C library wrapper functions) involves the following steps.

1. Intercept a C library function
2. Retrieve the buffer size by type table lookup
3. Compare the buffer size with the source string length
4. Call the C library function

The overhead is thus mostly attributed to 1) the time taken for type table lookup (in order to find the size of the buffer), and 2) the time taken for calling strlen() (in order to check whether the buffer size is enough) if needed. According to these two criteria, the C library wrapper functions are roughly partitioned into three classes; 1) functions such as strcpy() require the call to strlen() in addition to type table lookup, 2) functions such as memcpy() needs only type table lookup, and 3) functions such as strncpy() may or may not require strlen() depending on whether the buffer size is greater or equal to the size parameter or not.

Each function was tested 8 times with varying string length (8, 16, 32, 64, 128, 256, 512 and 1024). Our test were performed on a pc with AMD Duron 700MHz running Redhat Linux 6.2. Figure 4 shows the result.

Figure 4: Micro test that shows function overhead by range checking. Each overhead was measured as follows; If an intercepted function is 2.5 times slower then the overhead is 150 percent ((2.5 - 1) * 100).

The table lookup is done by binary search, so the overhead incurred by the table lookup will increase logarithmically as the number of functions and variables in the executable file increases. In sum, the micro test shows the worst case scenario and we expect better performance in real programs (which will, after all, do some useful work besides just calling C-library string functions). Figure 5 is the result of testing three programs (enscript 1.6.1, tar 1.13 and java 1.3.0), and shows the increase in size of executable files due to the augmented type table, the number of calls to C library functions that those program made during the test run, and the run time. Overhead in the macro test is in the range of 4-5% for substantial runtimes, with the short java test showing a 20% overhead (note that the absolute runtime overhead is minimal).

Figure 5: Macro test with enscript, tar and java. Enscript printed a text file of size 100Mbytes (to /dev/null). Tar zipped the linux kernel source directory twice. Java ran antlr to parse the GNU C grammar. The run time is the average of ten runs.