Search papers, labs, and topics across Lattice.
This paper introduces Ranger, a refinement type system aimed at reducing annotation overhead while enhancing expressivity in static verification for imperative programming languages. By utilizing a bidirectional type system and lightweight flow-sensitive static analysis, Ranger effectively minimizes the need for user-written annotations while maintaining the ability to verify complex properties related to integer ranges. Experimental results demonstrate that Ranger can express and verify a broader range of properties than traditional type systems like Java and Scala, and it outperforms other extended type systems in terms of usability and expressiveness.
Ranger slashes annotation overhead while enabling powerful range verification, making static type systems more practical for real-world programming.
Refinement types are a static verification technique that aims at increasing the expressivity of traditional type systems while remaining easy and natural to use. While systems based on refinement types have been developed for several mainstream languages, their practical adoption remains limited by their annotation overhead, which is often a more significant burden than when using the "plain" type annotations of languages like Java or Scala. To improve the state of the art, this paper introduces Ranger: a refinement type system designed to keep the annotation overhead small and to seamlessly integrate with imperative-style constructs like variables and loops. As the name suggests, Ranger focuses on integer range types: a particular kind of refinement types that express bounded integer ranges. Such types are widely useful to verify correct index manipulation and in-bounds data accesses, among others. To combine expressiveness and succinctness, Ranger is based on a bidirectional type system, which runs a type inference algorithm to provide the typechecking pass with information useful to reduce the need for user-written auxiliary annotations. Ranger also integrates other forms of lightweight flow-sensitive static analysis techniques that precisely capture the program's behavior without explicit annotations. We implemented Ranger on top of the Licorne experimental programming language. Our experiments show that Ranger's implementation can concisely express and verify a variety of useful properties that fall beyond the capabilities of standard static type systems like those of Java and Scala, and that Ranger compares favorably to other extended type systems, such as the Java Checker Framework and Liquid Java, that can also check properties about ranges.
