Reducing False Positives

Given that the tools generated about 500 type errors, one may conclude that the false positive rate is unmanageable, but we do not find this to be the case. A significant number of the errors are in functions in which it is easy to verify that no security compromises are present, such as those caused by ``safe'' functions described in Section 4.1.2. ``Safe'' functions are falsely marked as controlling functions because they modify field members of controlled data structures. However, since the modification is for the purpose of reference counting or initialization, the modification does not require security authorizations.

To identify what these functions are, we (slightly) modified CQUAL to print the inferencing path that leads to a type error. Figure 11 shows an example error path involving a ``safe'' function iput(). iput() decreases the usage count for the given inode and releases it if the usage count hits zero.

**Figure:** An example error path ending in function iput. Each line represents an inference according to the CQUAL rules, e.g. the first line means that inode_p is a super class of the unchecked qualifier type. The first column shows the source file and line number where the inference occurs.
$\begin{figure}\begin{small} \begin{verbatim}inode.ii:8383 $unchecked <= inode_... ...ut_arg0 inode.ii:8831 iput_arg0 <= $checked\end{verbatim}\end{small}\end{figure}$

We then report the list of controlling functions that are the sinks of the error paths. Because hot controlling functions often contribute to multiple type errors, the number of controlling functions are much smaller than the number of type errors. We then manually go through the list and identify ``safe'' functions, which are removed from the list of controlling functions. Appendix A lists the ``safe'' functions we identified. The CQUAL analysis process is then restarted.

It is painful to manually identify ``safe'' functions. But two reasons make it a manageable task. First, there are only a few such functions, even though they accounted for a significant portion of the type errors (Table 2). Secondly, these functions are relatively stable across kernel releases. So with a high probability this task only needs to be done once and the results can be reused in future kernel releases. After the ``safe'' functions are identified, we only need to verify that they do not change in new kernel releases, or that the changes do not affect their intended functionality.

Table 2 shows the reduction in terms of both path and source type errors after removing the ``safe'' functions for the four kernel subsystems we tested. This reduces the number of type errors by around 75% for both path and source type errors.

Table 2: Error reduction after eliminating ``safe'' functions.

	Path Type Errors			Source Type Errors
	With ``Safe''	Without ``Safe''	%	With ``Safe''	Without ``Safe''	%
Subsystems	Functions	Functions	Reduction	Functions	Functions	Reduction
File System	73	37	49%	57	31	45%
Memory Management	18	14	22%	17	13	24%
Networking	431	73	83%	308	55	82%
IPC	2	2	0%	2	2	0%

While this is a significant improvement, other means for removing false positives are being examined. First, there may be a significant number of other ``safe'' functions. Second, there are several cases where a variable is assigned from another variable that is checked. In the file system, often the dentry is authorized, then the inode is assigned from the dentry->d_inode. Unfortunately, CQUAL cannot yet reason that a field extracted from a checked structure is also checked (see Section 5.2). Third, we have not yet fully examined kernel-initiated paths that lead to type errors.