If we classify the variables of a program into various security levels, then a secure information flow analysis aims to verify statically that information in the program can flow only in ways consistent with the specified security levels. To make such analysis more practical, this paper proposes a novel type inference approach that gives programmers the freedom to specify the security levels of whichever variables are of interest, leaving the security levels of other variables to be inferred automatically. Type inference in this context is not new, but previous approaches have been based on gathering a set of subtyping constraints from the program, and then solving them with an abstract constraint solver. As a result, it has been difficult to report type errors to users in an informative way. Our inference approach stays closer to the original program, making it easier for us to explain precisely the source of each type error. We develop our type inference algorithm for a small imperative language with arrays, and prove that it is sound and complete. We also discuss our techniques for informative error reporting, and illustrate their effectiveness through examples. Copyright 2006 ACM.
