PySonar: a Static Analyzer for Python

PySonar is a static analyzer for Python. It uses a similar technique (abstract interpretation) as Coverity or CodeSonar, but does it in a much simpler and more principled way. Although it does not gather as much information as them, it produces results that are surprisingly accurate in the realms that it works on. To the best of my knowledge, it is the state-of-the-art of Python static analysis.

Demo

To get a quick feel about what kind of information it provides, here is a demo generated by PySonar demonstrating most of its features.

Features

1. A static type system.
   It is no surprise that a dynamic language can be statically typed. In fact, all languages can be statically typed. It is just a matter of how accurate the approximations are. PySonar’s type system has a blend of features that match Python’s semantics: structural subtyping (duck typing), record types, union types, parametric types, recursive types. Types are first-class citizens — it can analyze code that operates on types (e.g., take types as input or produce types as output). Because Python doesn’t have type annotations and its flexible semantics precludes unification-based type inference, all types in PySonar are inferred by interprocedual analysis.
2. Treatment of Python’s dynamism.Static analysis for Python is hard because it has many “dynamic” features. They help to make programs concise, but they also make automated reasoning about Python programs hard. Fortunately, some of these features can be reasonably handled. For example, function or class redefinition can be handled by inferring the effective scope of the old and new definitions. For code that are really undecidable, PySonar uses a universal honest answer: “I don’t know.” Well, not quite so. It attempts to report all known possibilities. For example, if a function is “conditionally defined” (e.g., defined differently in two branches of an if-statement) and the condition is undecidable, then PySonar gives it a union type which contains all possible types it can possibly have. By doing that, PySonar reduces false negative rates.
   
3. Path-sensitive analysis.The analysis performed by PySonar is path-sensitive, which enhances the accuracy of type inference and reduces false positive rates. We can see this in an example:

   def g(x):
     if (x > 10):
       y = 1
     else:
       y = A()
       ...
       y = "hi"
     return y

   In this function g, because we can’t statically know the input value of x, we must assume that it’s possible to take either branch. In the true branch, y is assigned an int. In the false branch, y is assigned an instance of A, but is later overwritten by a string. At the end of the false branch, y can only have the type string. The output type should be the union of the two branches, so the path-sensitive analysis gives function g the type int -> {int, string}. If the analysis were path-insensitive, g would be typed int -> {int, string, A}. Notice the extra A in the output type. Since it is not possible for g to output a value of type A, some call sites of g may rely on this fact and will not even test whether the output is of type A. At these call sites, a path-insensitive analysis will report a false positive type error, while a path-sensitive analysis will know that there is no problem.

4. Accurate semantic indexing.
   Generating code indexes for an Eclipse-like code browser was the main purpose of the project (although I discovered other interesting uses later). PySonar parses the code into an AST and performs type inference on it, and at the same time it builds indexes that respects scopes and types. Because it performs inter-procedural analysis, it is able to find the definitions of attributes inside function parameters.The following image shows that it can accurately locate the field x.z which refers to the “z” fields in classes B1 and C1, but not A1.
5. Semantic error reports.PySonar catches type errors statically. The type system is conservative — it reports possible type errors on possible inputs even if some of them may not actually happen. This is a usual trade-off to ensure soundness type systems, and PySonar is no exception. An interesting fact is that because of Python’s duck typing, most of the time type errors appear as “trying to access undefined field”. It also reports some other errors that can be easily catched, such as “unreachable code”.

Limitations

1. It does whole-program analysis and has exponential worst-case time complexity. Fortunately, like the Hindley-Milner system, the worst case happens very rarely.
2. It requires all source code to be available. This could be a problem for closed-source projects.

Availability

There had been two versions of PySonar. Version 1 is open-sourced and merged into Jython. It is available from Jython’s indexer package. Version 1 hasn’t interprocedual flow analysis, so some variables cannot be resolved. Version 2 has all the features described above and lots of clean-ups, but it is not open-sourced.

About these ads