Static program analysis is a popular software technique performed by automated tools for verifying large scale software systems. It works without executing the program, just analyzing the source code and applying various heuristics to nd possible errors, code smells and style discrepancies. Programming languages with strong static type system, like C, C++, Java are the usual targets of static analysis, as their type system provides additional information for the analyzer. However, there is a growing demand for applying static analysis for dynamically typed languages, like Python. In this paper we overview the current methods and tools available for static analysis on Python code base and describe some new research directions.
3:2
system is still not sufficiently supported by static analysis tools. Python is very attractive
implementing Machine Learning and Cloud based applications among others, and in July 2019 it is already the
third most popular language by the
In this paper we investigate how static analysis methods could be adapted for Python based software systems. The authors believe that in spite of the difficulties caused by the dynamic type system many of the methods applied for the classical languages could be utilized for Python too.
This paper is organized as follows. We discuss the most important analysis techniques in Section 2. We take a survey on static analysis tools used for the Python programming language in Section 3. In Section 4 we evaluate the tools according some typical use cases. This paper concludes in Section 5.
In this section we will overview the most frequently used methods of static analysis for modern programming languages. It is not our goal here to go to very deep technical details, but we intend to compare the advantages and the limitations of each methods. We will cover only methods which are (1) implemented at least for one programming language (2) based only on the source code, i.e. we will not discuss methods, where the user has to supply invariants or semantics of the program.
All static methods apply heuristics, which means that sometimes they may underestimate or overestimate the program behavior. In practice this means static analysis tools sometimes do not report existing issues which situation is called as false negative, and sometimes they report correct code erroneously as a problem, which is called as false positive. Therefore, all reports need to be reviewed by a professional who has to decide whether the report stands.
Here we face an interesting human challenge. Unlike the theoretical program verification methods, we do not strive to minimize the false negatives, i.e. try to find all possible issues, but we aspire to minimize the false positives. If the tool produces a large number of false positives, the necessary review process takes unreasonable large effort by the developers, meanwhile they also lose their trust in the analyser tool.
In this method the source code is first converted to a canonical format, i.e. all branches are converted to simple one liner if-else format, loops to a simple while-command format, comparison expressions are reordered to less-then and less-equal format. The developers express the various issues to detect as regular expressions. The tool tries to match this regular expression to every line in the source and reports each matches.
Earlier versions of CppCheck [Marjama¨ ki 2013] used pattern matching to find issues in C and C++ programs. Experiences with the tool report relatively low level of false positives, as well-written regular expressions have easy to predict results. Apart of the low false positive rate, additional advantage of pattern matching is working on non-complete source, even if we cannot recompile the software system. This means that the method can be applied to software under construction, or when we have only partial information on the system.
In the same time this method has several disadvantages too. As regular expressions are context free grammars, we are restricted to find issues based on information in the close locality of the problem. Having no knowledge about declarations we could not use type information. We cannot use name and overload resolution, cannot follow function calls and generally we have weak understanding on the overall program structure. As a summary, we can consider pattern matching based approaches as easy entry-level methods [Moene 2014].
To provide the necessary context information to the analysis we can use the Abstract Syntax Tree
(AST). AST is the usual internal data structure used by the front-end phase of the compilers [
This representation is suitable for catching errors that the simple pattern matching is unable to detect. These issues include heap allocation using the wrong size, some erroneous implicit conversions, inconsistent design rules, like hurting the rule of three/five in C++ and it proved to be strong enough to detect even some misuses of the STL API.
Such AST based checks are usually relatively fast. Some rules can even be implemented using a
single traversal of the AST. That makes it possible to implement such checks as editor plug-ins. External
tools, like the
While the AST matcher method is more powerful than the simple pattern matching, it has some disadvantages too. To build up a valid AST requires a complete, syntactically correct source file. To resolve external module dependences we need some additional information not represented in the source itself, like include path for C/C++ programs, CLASSPATH for Java or BASE DIR in Python. That usually means, we have to integrate the static analysis tool into the build system which can be painful. Another shortage of the AST matcher method, that it cannot reason about the possible program states which can be dependant from input values, function parameters.
Executing abstract interpretation [Cousot and Cousot 1977] the tool reasons about the possible values
of variables at a certain program point. Symbolic execution [Hampapuram et al. 2005; King 1976] is
a path-sensitive abstract interpretation method. During symbolic execution we interpret the source
code, but instead of using the exact (unknown) run-time values of the variables we use symbolic values
and gradually build up constraints on their possible values. Memory locations and their connections
(e.g. a pointer pointing to some variable, structs and their fields) are represented by a sophisticated
hierarchic
Symbolic execution is the most powerful method for static analysis as it makes profit from the program structure, the type system, the data flow information and is able to follow function calls. However, there is a price for this. To represent the internal state of the analysis, the analyzer uses a data structure called the exploded graph [Reps et al. 1995]. Each vertex of this graph is a (symbolic state, program point) pair. The edges of the graph are transitions between vertices. This graph is exponential in the number of control branches (conditions) of the program. This could be critical, especially for loops, which are represented as unrolled set of conditions and statements. This factor makes symbolic execution also the most resource expensive (in memory and execution time) method. 3:4
Here we give a brief overview of the current most commonly used static analysis tools in Python.
PyLint [
Pyflakes [
Frosted [Crosley 2014] is a fork of pyflakes which focuses on more open contribution development from the outside public.
Pycodestyle [Rocholl 2006] strictly checks only the code style against the style conventions in PEP8. It is usually used in combination with the other tools which are looking for logical errors and warnings. 3.3 flake8
Even though it is still considered experimental and optional static checker, Mypy [Lehtosalo 2016] proves itself to be highly effective, especially in type checking. It focuses on combining the benefits of dynamic typing and static typing. It has a powerful type system that in some cases, as discussed later in this paper, it catches type errors that are not caught by any of the common Python static analysis tools.
PySym [Dahlgren 2016] is an experimental Python package capable of a symbolic manipulation on a minimal scope. None of the previously mentioned tools are in contact with this package, nor with symbolic execution in general as a method of static analysis. Therefore, it is decided to be considered in this paper in the further investigation of symbolic execution in Python static analysis tools. PyExZ3 [Ball and Daniel 2015] is a tool which as part of the research on “Deconstructing Dynamic Symbolic Execution” [Ball and Daniel 2015], adds to the exploration of the dynamic symbolic execution (DSE) through a minimalist implementation of DSE for Python. With symbolic execution not being a common topic in the present static analysis field of Python, the authors of this paper believe they can rely on the PyExZ3 tool for further experimentation on dynamic symbolic execution in Python with the goal to improve the Python static analysis tool set.
On Figure 1 we summarize the connections between the Python static analysis tools.
Here we evaluate the tools by (1) which methods they use, (2) how mature they are, (3) what kind of problems they detect.
It is true that the compiler relies on static analysis, similar to these tools in order to generate its warnings during compilation time. However, its primary task is to translate a compilable code from high-level programming language to a lower level language, and the attention to its essential characteristic – the compilation time, makes it less capable of doing static analysis than the “third-party” static analysis tools. Python compiler misses all of the following discussed bugs and errors. Here is a short overview of the dummy code snippets used as a test examples of typical logical errors and bugs, used in this study to analyze and test the power of the static analysis tools in Python.
4.1.1 Referencing undefined variables. Very often in Python it happens that due to a typing mistake, an undefined variable is referenced. However, due to the dynamic nature of the language, such bugs don not get discovered up until runtime and when they are referenced. Example code for testing this bug with the static analysis tools of Python: 1 import sys 2 3 message = ” Hello there ! ” 4 i f ” greetMe ” in sys . argv : 5 print ( mesage ) 6 print ( ” This code i s fine , no problems . ” )
It can be noticed that at the line 6 the variable “mesage” is mistyped, and does not refer to the string “Hello there!” even though it looks similar. It is possible that error like this might not appear even during runtime. For example if this Python code is run without the “–greetMe” as an argument, then the code will just print out “This code is fine, no problems.” without errors or warnings.
4.1.2 Too many positional arguments. The following dummy code beside the “too many positional arguments” error in the call of the method getAge, has 3 more issues. The getAge method itself does not have a “self ” argument. Further, the platform variable is undefined, this is similar to the previous example. And the last issue the sys package is imported but never used. Unused imports might slow down the program.
4.1.3 Passing parameter of a different type then intended. Since Python is a dynamic language variables do not have types in Python, but rather values do, and the type of the values as well as the purpose for what an object can be used is decided during runtime. Python annotations were introduced to add hints for the type of a variable, however the type annotations issues are not caught by the compiler, so it is of a big importance for the other static analysis tools to discover that. The following code snippet is used to test the tools against and describes the importance of type annotations in Python:
Considering the sum function here, Python compiler does not report any issue, but during runtime the program throws an error which explains function sum can not be called with string since int and str types can not be sum up together with the + operator in Python.
1 import sys 2 3 c l a s s Person : 4 5 6 7 8 9 10 11 12 13 14 15 16 1 def sum( x : int , y : i n t ) : 2 return x + y 3 print (sum( 3 , 4 ) ) 4 print (sum( 3 , ’ 4 ’ ) ) def i n i t ( s e l f , first name , last name , age ) : s e l f . first name = first name s e l f . last name = last name s e l f . age = age i f ”Windows” in platform . platform ( ) :
print ( ”You ’ re using Windows ! ” ) s e l f . age = s e l f . getAge ( 1 , 2 , 3) def getAge ( t h i s ) : return ” 18 ” 4.1.4 Non-existing class member. The following example is used to test the tools against a code which refers to an unexisting class member. As it can be seen, the program tries to print the PERSON1’s height, but height does not exists as an attribute in the class Person.
1 c l a s s Person ( ) : 2 def i n i t ( s e l f , name, age ) : 3 s e l f . name = name 4 s e l f . age = age 5 PERSON1 = Person ( ” Hristina ” , 23) 6 print (PERSON1. age ) 7 print (PERSON1. height ) 1 def outer ( ) : 2 x=3 3 def inner ( ) : 4 print ( x ) 5 inner ( ) 6 outer ( ) 7 inner ( ) 4.1.5 Nested function call. A call to a nested function is a big logical error, but still the Python compiler does not generate any warning about it. The following dummy code is used to test the static analysis tools against call of a nested function outside its scope:
4.1.6 Closure bugs. In Python, Closure is a concept that allows function object to remember values in enclosing scopes even if they are not present in memory. 1 def greet ( greet word , name) : 2 print ( greet word , name) 3 greeters = l i s t ( ) 4 names = [ ” Kiki ” , ” Riki ” , ” Joe ” ] 5 f o r name in names : 6 greeters . append ( lambda x : greet ( x , name) ) 7 8 f o r greeter in greeters : 9 greeter ( ” Hi ” )
The following is an example code used to test the Python static analysis tools against a closure bugs in Python which is not reported by the Python compiler and the program runs just fine, with an unexpected output: 3:8 We may expect that this code would printout:
But instead it is printing: 4.2 Test results discussion 1 Hi Kiki 2 Hi Riki 3 Hi Joe 1 Hi Joe 2 Hi Joe 3 Hi Joe # Typical error 1. Referencing undefined variables 2. Too many positional arguments 3. Passing a parameter of a different type then intended 4. Nonexistent class members 5. Nested function call 6. Closure bugs
On Table I we summarize our test results. The accent of the discussed code tests is mostly put on the logical errors that are slipping into Python developers everyday work, thus at this point, code style focused static analysis tools (such as Pycodestyle) are not considered in the result table. This result discussion is based on catching-coverage of the logical errors, confirming if the tool’s behavior is as it is described in their documentation as well as a general overview of spotted pros and cons of each of the tools used against the test code examples. Currently, just a short general overview of the output format of the tools is given, but since this is also an important aspect of the tool’s functionality, especially when they are used against a bigger Python code based, more detailed analysis of this will take part further in the study. To clarify, all the tools are tested while in their default configuration. The results might differ if the tool’s configuration is separately tuned according the code tested.
Upon initial inspection of the table results, Pylint outperformed the other tools when run against the described test examples. It gave the most accurate reports and it was also the most descriptive in the generated output. However, if we look at the output format and style (which is not the focus of the table results at present), it is apparent that in many cases Pylint is “too talkative”, meaning the output can quickly get noisy and not so easily readable as the code base expands. Yet, the convenience of Pylint is again proven as it is the only tool that reports the errors “Too many positional arguments” and “Closure bugs”, which are easily made mistakes and the first one is especially trivial, but left to be caught during runtime, which is much more expensive. As such, they are of a great importance to the static analysis and the tools clearly need a support in their improvement. The “Closure bug” is a bit more complex. Closure in Python is an important concept and it is prone to bugs which in many cases, shown in the dummy test example as well, is hardly caught even during runtime. Such errors can take even days of debugging and manual reviews by the developers. This is notably true for bugs hiding in the Python closure concept. The authors believe that with the implementations of symbolic execution, the Closure is one of the concepts in Python that might see great improvements regarding static analysis by moving it ahead from the current benefits of the AST approach.
There is only one test case where Pylint did not report any warning nor error, and to a positive surprise, Mypy was the only tool that caught it. This was a type annotation related bug where Mypy proved that even though it is still considered as an experimental tool and far from the commonly preferred Pylint, it justified its focus to perform well on type annotation errors. This makes Mypy an essential static analysis tool to be considered in a Python code that uses type annotations gain on the benefits of the predefined variable types, which is not in the core of Python as a dynamic programming language. The importance of type annotation static analysis is shown in the “Passing parameter of a different type then intended” example and its “sum” function. Seeing that analyzing type annotations is one important point of the static analysis tools that needs to be improved, and at the same time noticing that the tools lack the symbolic execution as a method technique behind the scenes which seems to be a great factor of this improvement, encourages author’s further directions of the research to go towards implementing and testing symbolic execution in Python static analysis. On the brighter side of the results table, there are two tests that were covered with a warning report by all of the static analysis tools under test. These are “Referencing undefined variables” and “Nested function call”, both of which are quite trivial errors. The example “Referencing undefined variables” in a strictly typed language such as C, C++ and Java, this will be immediately reported by the compiler, but since Python is a dynamically typed language, its compiler does not catch it. Thus, this is one of the crucial moments for the Python static analyzers to shine up above the Python compiler. Anyhow, the strong believe that symbolic execution can improve the performance even in the most crucial and trivial examples, stays alive and will be considered in the future of this research.
Since the focus now is in the logical errors caught by the static analysis tools, it is important to notice that Pyflakes and flake8 are expected to, and they do give, the same results in the table. This is mainly because flake8 just combines pyflakes, pycodestyle and mccabe, so they have the same approach in catching the logical errors. However, noticing that Pyflakes did not catch many of the logical errors that were caught by the other tools, knowing that as a tool it focuses mostly on the logical errors avoiding the style reports, it raises a lot of questions. Moreover, leaves the believes that its very strict avoidance of false negative error, adds more cons than pros to its convenience as a static analysis tool, since because of this, many errors were left not reported at all. Frosted as a tool during this test examples did not show that catches any different errors than what Pyflakes and flake8 caught, which is to a certain degree expectable, since it is a fork of pyflakes, with the main difference being that its open to a public development.
To sum up this brief introductory discussion and analysis of the existing Python static analysis tools, it can be said that there is no tool presently that can stand alone as the best of all. Best results at the moment would be achieved when using several of the existing tools at the same time, thanks to their manually configurable and customizable capabilities. Exploring Python symbolic execution further in the research, promises that would bring great improvements in the currently existing Python static analysis world.
Static analysis is a powerful technique to validate large software systems in the early phase of the Continuous Integration (CI) loop. There are sophisticated methods for analyzing mainstream languages with static type system, like C, C++ and Java. The current support for the Python programming language is way behind. Tools are in experimental phase and lacking large development communities. The main reason is the dynamic nature of the language which makes harder to apply the usual analyzer techniques. However, this can be improved as tools can step forward from the current AST based methods. The most promising direction is symbolic execution, which can handle the dynamic language features in a more straightforward way. The authors suggest future researches to implement further symbolic execution techniques and test them in industrial environment.