TL;DR
This paper introduces a type inference algorithm for C that automatically infers function signatures (interfaces) from program usage, even without header files. This is crucial for software porting, enabling developers to understand and reconstruct library dependencies in new environments more efficiently.
What Problem Does This Paper Address?
Porting software to new environments is a common but challenging task. A major hurdle is understanding the program's dependencies on external libraries and operating system functions. Traditionally, this involves manual code inspection, which is time-consuming and error-prone, especially when documentation is scarce or lost. The authors tackle this by automating the process of discovering these external function interfaces, providing a formal summary of a program's assumptions about its environment.
Methods
The core of the paper is a type inference algorithm designed for C, which deviates from purely functional language approaches due to C's flexible type system (e.g., implicit conversions, variable argument lists). The algorithm works by:
- Type Lattices: Defining a Hasse diagram for C's basic types, where the "join" operation selects the most restrictive common ancestor type. This handles implicit type promotions (e.g.,
chartoint). - Deduction: Inferring function argument types based on how they are used in function calls. For example, if a function
fis called with anint, the algorithm infersftakes anintargument. - Handling Variable Arguments: Using a special "T" type to represent variable argument lists (ellipses
...) and extending shorter argument lists to match longer ones when inferring signatures. - Unification Algorithm: A relaxation-based algorithm that iteratively refines type signatures. It uses constraints to handle transitive dependencies (e.g., the return type of function
gdepends on the type of an argument to functionf). The algorithm has two passes: one for simple inferences and another for resolving these transitive constraints.
Datasets
The authors evaluated their tool on two real-world C programs:
- iSSL: A network cryptographic service (approx. 13,000 lines of code).
- Pilot-DB: A database system for PalmOS (approx. 27,000 lines of code).
They specifically chose Pilot-DB because it was for a different operating system and they did not have its header files, making it a good test case for their "no header files" scenario.
Key Insights and Ideas
- Porting as Interface Discovery: The paper reframes a significant part of software porting as the problem of discovering and understanding external function interfaces.
- C's Type System Challenges: The authors highlight how C's implicit type conversions and variable argument lists necessitate a tailored type inference approach compared to more disciplined languages like ML.
- The Power of "Join": The use of type lattices and the "join" operation is a clever way to handle the ambiguity and promotions inherent in C's type system, providing a conservative yet useful inferred type.
- Handling Variable Arguments: The approach to T-extending argument lists for variable arguments is a practical solution to a common C feature.
- Transitive Constraints are Key: The unification algorithm's ability to handle transitive constraints is crucial for accurately inferring complex dependencies.
- Beyond Function Signatures: The tool can also act as a "lint-like checker" to flag suspicious implicit typecasts, adding another layer of utility.
Key Results
The tool was able to infer useful function prototype information for both iSSL and Pilot-DB.
- Performance: The analysis took less than three seconds for Pilot-DB and less than two seconds for iSSL on a 1.7 GHz Pentium 4 machine.
- Accuracy:
- For iSSL, the tool correctly deduced most prototypes, with minor differences arising from assuming
intinstead ofunsigned longfor some arguments. It also correctly inferred types for a macro (mpi_get_nlimbs) as if it were a function.
- For iSSL, the tool correctly deduced most prototypes, with minor differences arising from assuming
- For Pilot-DB, the tool successfully inferred many prototypes for PalmOS GUI calls. It correctly identified a pointer argument as
void *when the actual type wasTableType *due to a function usingvoid *for its arguments. It also inferred a variable number of arguments forTblGetRowID, which was a mistake due to an incomplete type definition in the source code.
Limitations and Future Work
- Incomplete Types: The tool struggles with incomplete type definitions (e.g.,
struct _IO_FILE *vs.FILE *) and cannot infer the types of arguments passed through pointers to structs with incomplete definitions (e.g.,EventPtr). - Distinguishing Structs and Unions: The paper notes that distinguishing between C structs and unions, which are syntactically similar, is a difficult problem that remains to be addressed.
- Future Work:
- Modifying the C front end (CIL) to infer missing types, potentially using techniques for aggregate structure inference.
- Extending the ideas to object-oriented languages like C++ and Java, which present new challenges due to function overloading and operator overloading.
- Extracting more behavioral information, such as the order in which library functions are invoked, which could aid in program verification.
Summary updated