Inferring Concise Specifications of APIs
This addresses the problem of making API specifications usable for software engineers by reducing complexity, though it is incremental as it builds on existing strongest postcondition methods.
The paper tackles the problem of inferring formal postconditions for APIs, which are often exponentially large and hard to use, by developing an algorithm that converts these into concise specifications. The result is that the technique inferred specifications for 75.7% of over 2,300 methods in Java libraries, reducing SMT proof length by 76.7% and prover execution time by 26.7%.
Modern software relies on libraries and uses them via application programming interfaces (APIs). Correct API usage as well as many software engineering tasks are enabled when APIs have formal specifications. In this work, we analyze the implementation of each method in an API to infer a formal postcondition. Conventional wisdom is that, if one has preconditions, then one can use the strongest postcondition predicate transformer (SP) to infer postconditions. However, SP yields postconditions that are exponentially large, which makes them difficult to use, either by humans or by tools. Our key idea is an algorithm that converts such exponentially large specifications into a form that is more concise and thus more usable. This is done by leveraging the structure of the specifications that result from the use of SP. We applied our technique to infer postconditions for over 2,300 methods in seven popular Java libraries. Our technique was able to infer specifications for 75.7% of these methods, each of which was verified using an Extended Static Checker. We also found that 84.6% of resulting specifications were less than 1/4 page (20 lines) in length. Our technique was able to reduce the length of SMT proofs needed for verifying implementations by 76.7% and reduced prover execution time by 26.7%.