In the C programming language, the union construct is a double-edged sword. While it allows developers to optimize memory by storing different data types in the same physical location, it lacks the type safety found in more modern languages. The compiler remains "blind" to which member of a union is currently active, leaving the responsibility of safe access entirely to the programmer. This paper presents a novel approach to automatically verifying the safety of union accesses by treating them as a form of subtyping and using Craig Interpolation to infer the necessary safety conditions.
The Challenge of C Unions
Programmers typically manage unions using an informal "tagging" protocol. For instance, a packet structure might contain a type field; if type equals 5, the programmer knows it is safe to access the redirect member of the union. However, these protocols are rarely documented formally and never enforced by the compiler. A single missed check or a logic error can lead to memory corruption, where a pointer is misinterpreted as an integer, creating critical security vulnerabilities.
Methodology: Unions as Subtype Hierarchies
The authors propose a formal framework that maps the messy reality of C unions onto the clean theory of object-oriented subtyping. In this model, a union is viewed as a parent type, and its individual members are treated as subtypes. Accessing a union member is then formalized as a "downcast" from the parent to a specific subtype.
To ensure safety, these downcasts are guarded by "predicated refinements"—logical conditions that must hold true for the access to be valid. For example, in an ICMP packet, the access to a redirect struct is only valid if the icmp_type field is equal to 5. Crucially, the system requires these predicates to be pairwise inconsistent (mutually exclusive), ensuring that a memory location cannot be interpreted as two different subtypes simultaneously.
Automated Inference via Craig Interpolation
The core innovation of this work is the use of Craig Interpolation to automatically discover these guard predicates. Instead of requiring manual annotations—which would be prohibitive for legacy codebases—the algorithm analyzes the program's control flow in Static Single Assignment (SSA) form.
When the code accesses a union member, the algorithm looks at the preceding logic. Craig Interpolation is used to find a predicate $P$ that is implied by the program's preconditions but is also sufficient to justify the safety of the access. This allows the tool to "learn" the implicit tagging protocols already present in the code by finding the simplest logical condition that explains why an access is safe.
Empirical Evaluation
The approach was tested on approximately 350,000 lines of open-source C code across nine diverse projects, including networking tools like snort, system utilities like sendmail, and language interpreters like lua and bash.
The results were highly promising:
- Accuracy: The tool successfully inferred correct dependent types for 80 out of 90 identified "predicated edges," covering 1,472 of the 1,684 union access points.
- Bug Detection: In instances where inference failed, such as in the
luacodebase, the tool often highlighted genuine logical inconsistencies where programmers made unchecked assumptions about variables satisfying the same predicate. - Performance: The entire 350KLOC suite was processed in just under an hour (3,242 seconds), demonstrating that the method is efficient enough for integration into real-world development pipelines.
Conclusion
By combining subtyping theory with Craig Interpolation, this research provides a practical path toward securing legacy C code. It transforms informal programmer habits into a formal, checkable safety property, offering a powerful defense against one of C's most persistent sources of memory bugs without requiring a total rewrite of existing software.
Summary updated