4.4 const Allows Deep Subtyping

As described in Section 2.3, we use a conservative rule for pointer subtyping. This rule can lead to non-intuitive reverse taint flow, which often causes false positives. For example, consider the following code:

  f(const char *x);
  char *unclean, *clean;
  unclean = getenv("PATH");
  f(unclean);
  f(clean); /* 'clean' gets tainted */

Here the getenv() function call imposes the condition $\textit{unclean\_p} = \texttt{tainted}$. The first call to f adds the constraint $\textit{f\_arg0\_p} = \textit{unclean\_p}$. The second function call generates the constraint $\textit{f\_arg0\_p} = \textit{clean\_p}$, thereby marking *clean as tainted, which is counter-intuitive.

Observe, however, that f's argument x is of type const char *, so f can not make *x tainted if it is not tainted in the first place. Consequently, we modify the constraints in Section 2 as follows: For an assignment

  const char *s;
  char *t;
  ...
  s = t;

we add the constraints $\textit{t} \le \textit{s}$ and $\textit{t\_p} \le \textit{s\_p}$, if *s has a const qualifier. This is to be compared with the constraint $\textit{s\_p} = \textit{t\_p}$ which we would otherwise have imposed. In this way we can use ``deep subtyping'' to improve precision for formal parameters marked const.

This extra precision, which helps avoid many false positives (especially in library functions), is the main reason we work in a subtyping system. Note that we rely on the C compiler to warn the programmer about any casts which discard the const qualifier, i.e., we assume that a variable that is const is never cast to anything that is not const.