To find format string bugs, we use a type qualifier system with two qualifiers, tainted and untainted. We mark the types of values that can be controlled by an untrusted adversary with tainted. All other values are given types marked untainted. This is similar to the concept of tainting in Perl [32,42].
Intuitively, cqual extends the type system of C to work over qualified types, which are the combination of some number of type qualifiers with a standard C type. We allow type qualifiers to appear on every level of a type. Examples of qualified types are , , (a pointer to an untainted character), and (an untainted pointer to a character).
The key idea behind our framework is that type qualifiers naturally induce a subtyping relationship on qualified types. The notion of subtyping most commonly appears in object-oriented programming. In Java, for example, if B is a subclass of A (which we will write ), then an object of class B can be used wherever an object of class A is expected.
Consider the following example program:
Now consider another program:
Putting these two examples together, we have the following subtyping relation: