Im-C – A Memory-Safe C Interpreter Providing a Better Learning, Testing, and Debugging Experience

The C programming language [3] is used in a wide range of fields, including missing-critical applications such as systems programs, operating systems, and embedded systems. However, its high degree of freedom and relatively low level semantics makes it prone to bugs, especially those caused by memory manipulation errors and undefined behaviors. Students who are not already familiar with machine language programming also suffer a steep learning curve when trying to understand how to safely manipulate memory and pointers. Error messages from C compilers can be difficult for beginners to decode, creating a barrier to understanding the exact causes of problems and the programming techniques that can mitigate them. In the most extreme case, a student might have nothing more informative than “bus error” or “segmentation fault” to indicate their program is not correct.

In this study we reports on an early experimental component of the Im-C system. Im-C is a project whose goal is to mitigate some of the problems that accompany C programming, especially those related to memory and pointers, improving the learning experience for novice programmers and students.

Im-C aims to provide a safe and easy-to-understand C programming environment and an (optionally) simplified C grammar. In the current phase we have developed a C interpreter with enhanced error detection and reporting.

In addition to the usual out-of-bounds, dangling pointer, and other run-time errors traditionally detected by C safety checkers, Im-C aims to warn students about undefined behaviors. These often do not produce warnings or fatal run-time behavior, but they do have platform-dependent results which makes the program non-portable. This will help learners quickly understand problems in their code, make effective corrections, rapidly learn the “rules” (often subtle and not widely discussed) of safe and portable C programming.

We hope that Im-C will help not only early stage programmers but also in some cases professional programmers working on production-quality code. For example, data structures are often written as small, self-contained components with their own unit tests. Running those unit tests under Im-C can potentially uncover errors that would otherwise go undetected.

The rest of this paper is organized as follows. Section 2 discusses the two popular run-time C verifiers whose goals are most similar to ours. Section 3 describes our approach to detecting run-time errors in C programs. Section 4 presents some of the design of the Im-C interpreter, particularly those aspects most closely related to detecting memory and pointer manipulation errors. Section 5 describes the test suite we use to evaluate error detection, Section 6 presents the results of running the tests with the three verifiers, and Section 7 discusses those results. Finally, Section 8 presents some concluding remarks and our intentions for future work on Im-C.

Program verifiers have been around for a long time. Perhaps the first static verifier was lint [2], which picked fluff out of C programs by parsing and analyzing them. Dynamic behavior verification arrived later with a few commercial tools which in turn inspired open-source projects including Valgrind and then ASan. Since the latter two are now the most widely-used run-time behaviour verification tools we will concentrate on them.

The address space sanitizer ASan [7] was introduced by Google in 2012 and is now included as a compilation option in several popular C compilers such as gcc [8] and Clang [9]. ASan modifies a program at compile time, inserting additional code to monitor memory accesses and detect errors. Several data structures are used at runtime including red zones, which are regions of memory added around allocated blocks to catch out-of-bounds accesses, and shadow memory, which tracks the state of each byte in the application’s memory to detect invalid accesses. ASan also quarantines freed memory blocks to detect use-after-free errors. These mechanisms help ASan to identify a number of different memory errors including out-of-bounds accesses, dangling pointers (use-after-free errors), and memory leaks.

Valgrind [5] began in the early 2000s as a cache profiling and memory debugging tool. It is language-independent and works directly with machine instructions, dynamically recompiling them into a program with additional instrumentation that measures or verifies the program’s behavior. Various “sub tools” are available, each of which adds different instrumentation to the recompiled program. Memcheck is the default and most commonly used tool. It verifies the addressability (whether an address refers to a valid region of memory) and the validity (whether the contents of memory are initialized) of every memory access as the program runs. It also inserts red zones around allocated memory to detect off-by-one errors, where a program might inadvertently attempt to access memory just before, or just after, an allocated region of memory.

CCured [4] accepts a mostly C89-compatible language as input and performs static analyses of pointer usage. Additional code is then inserted into the program, when necessary, for bounds checking or to ensure the results of arbitrary casts are used safely.

Im-C takes a very different approach to detecting memory- and pointer-related errors. Whereas ASan modifies a compiled program at compile time and Valgrind modifies a compiled program at run time, Im-C interprets the C source program directly without any compilation. Addressability and validity of addresses and the data they refer to are verified by tracking how each address is created, how it is subsequently modified, and how uses of it relate to the object from which it was created – in particular whether they are legal and have well-defined behavior.

Fail-Safe C [6] is a compiler for C89 that includes run-time checks of memory and pointer use. It has the most similar run-time safety strategy compared to Im-C, keeping meta data for allocated memory and pointers that allow uses of them to be checked. Like Im-C, it uses a garbage collector to reclaim memory; the free() function marks memory as unusable but does not actually de-allocate it until it becomes unreachable.

CINT [1] is a C interpreter that can call, or be called from, compiled code. It is used primarily for rapid prototyping (eliminating the compiler from the development cycle), documentation (running example statements stored in text files and inserting up-to-date output into the documentation), and to allow tools to interoperate with compiled code through C statements generated as plain text. It does not have any special features that enhance error detection or safety. Its relationship to Im-C is therefore limited to the execution mechanism and not to the enhancement of the end-user experience.

The goal of Im-C is to provide an environment in which C programs can be run safely, with most memory manipulation errors, in particular, being detected and properly reported instead of leading to “segmentation fault” or “bus error” at run time. It is aimed at student writing terminal-based projects, or professional programmers who are writing standalone software components with unit tests.

Im-C executes C programs from source code. It parses the program into an intermediate representation which is then immediately interpreted. In the absence of programming errors, the program should behave exactly as it would if statically compiled to a binary executable by a standard compiler, and produce identical output.

Im-C does not currently aspire to be a complete implementation of the C language, including its many runtime libraries. It does aim to provide just enough of the language and runtime libraries to support writing useful programs, especially those that students might write or that implement common data structures and pointer-based algorithms with their unit tests.

To encourage good programming practices, Im-C is slightly more strict than standard C when parsing the program. At run-time, Im-C detects a wide range of programming errors that would be silently undetected, or would exhibit platform-dependent behavior, when run as a fully-compiled program.

Im-C is implemented as a typical interpreted language. Source code is parsed, converted into a tree representation, verified for type correctness, and then tree nodes are interpreted by a recursive evaluator function to execute the program.

In the following sections we describe those aspects of Im-C’s design that are most closely related to detecting memory and pointer errors.

We evaluated ASan, Valgrind, and Im-C using a test suite written specifically for the purpose of exposing many common memory errors as well as some typically found in student programs. The source code of the test suite is presented in Appendix A. The programs and the errors they contain are described briefly in Table 1.

To pass a test the verifier must detect the error, classify it correctly, and provide relevant information to let the programmer locate and address the problem. Detecting an error but mis-classifying it or failing to provide useful contextual information is counted as a partial pass. A test fails if the verifier does not detect the error.

The four “pointer-” tests perform operations that have undefined behaviour. The C standard only guarantees correct, reproducible results for comparisons and arithmetic involving pointers that both refer to the same block of allocated memory or to the same array object (or to the byte following the end of that array). Other pointer arithmetic and comparisons are undefined behavior and the result is implementation dependent, and therefore non-portable. We consider these rules to apply equally to a pointer to a variable, which we treat essentially as a pointer to an array of that variable’s type containing a single element.

Table 2 shows the results of running the test suite (see Appendix A) with the three error detectors on GNU/Linux using gcc (ASan) version 13.3.0, libc version 6.8.0, and Valgrind version 3.22.0.

ASan passed 14 of the tests and failed 4. Valgrind passed 11 of the tests, partially passed 1, and failed 6. Im-C passed 17 of the tests and partially passed 1.

ASan mis-diagnosed dangling-pointer-2 as a heap use-after-free even though the pointer involved was to a dead local variable in the stack (note 1). The output was as follows.

==1514299==ERROR: AddressSanitizer: heap-use-after-free on
address 0x502000000010
READ of size 4 at 0x502000000010
    #0 0x571a51afb302 in main dangling-pointer-2.c:12

Im-C correctly identified leaked heap memory blocks but currently does not track or report the location in the source program where the memory was allocated (note 2).

heap memory not freed at end of program: <0x101142d50+4>
heap memory not freed at end of program: <0x101142d20+4>
 …  (18 more similar messages)

Valgrind detects the use of uninitialized values but does not detect, for example, the initialization of a variable from another uninitialized variable (note 3). Instead Valgrind propagates the uninitialized value through copies and will report it only when eventually used in an expression.

Table 3 shows the performance of two benchmarks running normally (“none”) and under each of the three verifiers. In all cases (except for Im-C) the program was compiled with “-O2” optimization enabled. For perspective, the performance of Python (a highly optimised interpreted language) for the same benchmark is also shown.

The first benchmark is a doubly recursive function nfib(n) which calculates the n^th member of a sequence closely related to the Fibonacci sequence except that the result of nfib(n) is the number of function calls needed to calculate that result:

The value of n was modified for each scenario to keep the running time just over one second. For each scenario the table shows the value of n, the result (number of function calls made by the program), the time taken in seconds, the number of calls per second, and the percentage of the speed (measured in calls per second) compared to the non-verified case.

The second benchmark is a prime number generator using the sieve of Eratosthenes which counts the number of primes between 2 and 2048000:

It is memory intensive, making heavy use of a large array but no function calls. For the faster running times an outer loop was added to the benchmark to keep the running time over one second and a corresponding scaling applied to the recorded time to yield the values shown in the table.

Im-C performed well in all but one test. It failed to report the location where leaked memory blocks were allocated. The parser will soon add information indicating where in the source each AST node was generated which will allow us to report this information.

Valgrind failed to detect the out-of-bounds-access-2 error, which accesses a local variable in the stack as a pointer offset from an adjacent variable in the stack. This is because Valgrind works with the compiled executable only, and does not consider the semantics of the source program. In particular, it has no information about the sizes of arrays or other program elements that contain a given memory location. It therefore cannot distinguish adjacent variables in a stack from an array, and will not report any misbehavior when a pointer to one variable is de-referenced with an offset that leads to an adjacent variable. ASan catches this error because of the red zones it places around variables. However, if the offset happens to exceed the size of the red zone then ASan would also fail to catch this error. Im-C can always catch this error because part of the semantic information it preserves during execution is the identity of the variable whose address was taken to create the pointer. When using that address to access the stack, if any offset applied does not precisely cancel any increment applied to the address then an error can be reported.

The pointer-out-of-bounds and pointer-out-of-bounds-2 errors were correctly detected by both ASan and Im-C, because of ASan’s use of red zones around all objects and Im-C’s verification that an index lies within the bounds of the array or memory object that is being accessed.

Both Valgrind and ASan failed to detect or report an error with the pointer-compare and pointer-increment tests. For Valgrind, this is understandable since it has no semantic information from the original source code to determine when a pointer is being moved outside the immediate vicinity of the object to which it refers. ASan, however, could include a check on this kind of pointer manipulation, but it chooses not to. Im-C detects these issues because every points knows the kind and size of the object to which it refers.

Valgrind failed to detect errors in the pointer-out-of-bounds test. These errors are illegal references to memory just beyond an array, or relative to a pointer beyond the array with a negative index to the element just before the array. Again this is because Valgrind has no information about the boundaries of variables and arrays allocated on the stack. ASan caught these errors because of the red zones it places around such objects. Im-C caught these errors because pointers know which object they refer to and so all accesses to them through pointers, with or without an offset, can be verified to lie within the memory allocated for that object.

For uninitialized and uninitialized-2, both ASan and Valgrind failed to detect a variable being initialized from the value of an uninitialized variable. In the case of ASan, this is because it does not track uninitialized memory. Valgrind differentiates between initialized and uninitialized memory but allows uninitialized values to be copied to other locations, propagating the uninitialized value without reporting an error. Valgrind will eventually report an error when an uninitialized value is used in an expression. Im-C detects the initialisation of a variable from an uninitialized variable immediately which we consider to be more useful, and safer, behavior.

While ASan comes close to the detection rate of Im-C, and is certainly a lot faster, we think Im-C has a valuable role to play informing students, in particular, about errors in pointer manipulation and comparisons. We do not expect students to have read the C standard, and so highlighting issues with undefined behavior, such as comparing pointers based on different objects in memory, is valuable. The diagnostics currently produced indicate incompatible pointer comparisons but in future could be improved to explain exactly why the incompatibility exists, for example, highlighting that not only are they different but one object resides in the stack and the other in the heap.

Many more pointer manipulation errors and questionable practices could be detected by Im-C. An example is verification of pointer casts such as

in which Im-C detects the out-of-bounds access to an 8-byte value in a 4-byte block of memory while fetching the second argument of printf, but misses the opportunity to report (at least) a warning for the line before that, when a pointer to memory containing a struct foo is cast to a pointer to memory containing a struct bar.

ASan exhibited only a slight performance penalty for verification, running the benchmark at more than 83% normal speed. ASan benefits from being part of the normal compiler, with optimizations applied to the additional instrumentation it adds to the program.

Valgrind imposed significant performance penalty, running the benchmark at just over 3% normal speed or 26 times slower than ASan. Valgrind is essentially a virtual machine that dynamically re-compiles the program while it is running to add the instrumentation, although such a high penalty was surprising. Investigating the causes are outside the scope of this paper but we speculate that some of the instrumentation such as propagating uninitialised values might be costlier than ASan’s simpler handling of them, and that the dynamic code generator in Valgrind might perform fewer, or less aggressive, optimizations than the compiler hosting ASan.

As expected, Im-C was by far the worst performer achieving only 0.13% the speed of normal C – 24 times slower than Valgrind, 640 times slower than ASan, and 770 times slower than the program running unverified. In spite of this, it still achieved close to 5 million interpreted function calls per second. We believe this is sufficient for student programs and unit tests that exercise self-contained data structures and other non-compute intensive algorithms.³³3To put this in perspective, Python 3.10 (which is heavily optimized for speed) runs the same benchmark 4.5 times faster than Im-C. Changing Im-C’e execution mechanism from an AST interpreter to a VM would easily close that gap.

We presented an experimental component of Im-C, which aims to detect errors related to memory and pointer manipulation that novices tend to make, or which are more subtle and even professional programmers might overlook. It provides a runtime C verification environment using a C interpreter. We validated its effectiveness compared to the two most popular and mature, modern tools, ASan and Valgrind.

Using the test suite we created, we were able to detect all the errors that ASan and Valgrind could detect. In addition, we were able to detect pointer comparisons with undefined behavior and pointer manipulations that resulted in pointers that would, if used, result in undefined behavior, that the other tools did not detect.

Our method of representing values with rich semantic meta-information was helpful in informing the user of why an error occurred, although at present the location of the error is not always reported. In future, by recording source location in each AST node, we will be able to pinpoint the exact location of all errors. By including this information in the object that are created during execution we will be able to report the statement responsible for allocating memory that is involved in a run-time error.

It is not yet possible to describe the cause of every error. Future work will consider how to enhance the traceability of values and program code to try to better explain the cause of errors.

Being an AST interpreter, Im-C is much slower than ASan and Valgrind which both execute an instrumented version of the program as native machine instructions. While Im-C can never close the gap completely, we intend to narrow it by converting the AST to a flat intermediate representation and executing it using a virtual machine.