Going with the Flow in Static Analysis

As part of my ongoing series about Static Analysis issues I want to talk about the relationship between the traditional static method and the newer dynamic or flow analysis method. People seem to misunderstand how the techniques relate and what each is good at. In particular, many seem to think that flow analysis is a replacement for non-dynamic analysis, which couldn’t be more wrong.

For the sake of having a simple term to identify both methods, I’ll refer to the older “static” method of static analysis and “pattern-based” and the newer flow-based method as “flow-based”. This is somewhat of a misnomer in that both types are really based on patterns, but seems to be a somewhat common way of referring to the two methods. If the terms I use bother you, feel free to do a search-replace function in your head when reading. I’m not too worried at this point about a strict technical explanation of each, but rather to their relationship. The goal is to have a way to differentiate in terms these two particular types of static analysis. Of course there are other types of static analysis as well, but I’ll leave that for another day.

Let me begin by saying that there is in fact a very strong relationship between pattern-based and flow-based static analysis, at least at an academic level. In almost every situation there are a set of pattern-based rules that would allow you to code in such a way that would prevent the occurrence of the issue being found by the flow-based rule. Given the nature of how flow analysis works, it can never find all possible paths through an application. This makes it a good idea to start programming in a more pro-active way to prevent the possibility of issues you’re concerned about.

For example, in security, one of the basic problems is using tainted data. Somewhere in the application between getting data from the user and operating on the data, you need to check if the data is safe. Depending on how far apart the operations are, it can be extremely difficult if not impossible to check every possible path. Security code scanners that rely on flow-based analysis attempt to find possible paths between user input and uses of the input that allow tainted data to be operated on. They can never find every possible path even if you let them run for an incredibly long time.

Instead, if you restructure your code so that input validation is done at the moment of input, then you don’t have any paths to chase, and you don’t have to worry about tainted data in your application. Flow-based tools won’t find anything anymore, because you won’t have any unprotected paths. This is sometimes a more difficult sell for developers, since it doesn’t provide them with a single broken piece of code that needs to be fixed. Rather it tells them that the way they’re writing code now could be improved – a bitter pill to swallow.

However applying this same principle to things like memory corruption, resource consumption, etc. can make the program far more robust than chasing possible paths ever could.

An excellent methodology is to start with flow-based analysis and fix the low-hanging fruit. Once you have compliance with your flow-based rule set, then review what you’re doing with flow and compare it to pattern-based static analysis. Determine as best you can how to apply static analysis and catch all possible potential problems before they happen, and put that into place. This moves you from a reacting to issues in your software to a more preventative stance.

There are those who say that flow-based analysis is preventative, but it’s still symptom driven – namely trying to find the openings and bugs you left in your code. Pattern-based analysis, when deployed properly, can be used to address the root problems. In our tainted data example, this means changing our coding style so that we don’t have paths where data could be tainted – root problem handled.

Essentially, flow-based analysis finds real bugs in possible paths. When you get a message from it, you just decide whether you care about that path or not. Static on the other hand tells you about the potential for a bug, not necessarily about the existence of a bug. Again, with our security example, Flow-based says “you used tainted data” where pattern-based says “this data could be tainted before use”.

When compared, you can see that flow-based analysis is a great way to find low-hanging fruit, because it’s looking for bugs instead of you doing it. On the other hand, because it works by guessing (flow fans hate the “guessing” term) at possible paths through your code, it will always be by it’s very nature incomplete.

Pattern-based analysis on the other hand requires restructuring your code and behavior if you want to achieve it’s full value. Some code is not well suited to such change, such as working legacy code.

Used together you have a very powerful solution that is much more robust than either technique on it’s own.

[Disclaimer]
As a reminder, I work for Parasoft, a company that among other things make static analysis tools. This is however my personal blog, and everything said here is my personal opinion and in no way the view or opinion of Parasoft or possibly anyone else at all.
[/Disclaimer]

Resources

Leave a Reply