False Positives and Other Misconceptions in Static Analysis

wrong answer © by Sean MacEntee
In ongoing discussions here at the blog and elsewhere, I keep seeing the topic of false positives in static analysis come up. It’s certainly a very important issue when dealing with static analysis, but the strange thing is that people have very different opinions of what a false positive is, and therefore different opinions of what static analysis can do and how to properly use it.

In the simplest sense, a false positives means that the message that a rule was violated is incorrect, or in other words the rule was not violated – the message was false. In other words, a false positives should mean that static analysis said it found a pattern in your code but the pattern doesn’t actually exist in your code when you review it. Now, that would be a real false positive.

Pattern-based false positives

False positives and “not false positives” (false negatives) are in two different areas. One is pattern based static analysis, which also includes metrics. There is also flow-based static analysis. One thing to remember is that pattern based static analysis doesn’t typically have false positives. If it has a false positive, it’s really a bug in the rule or pattern definition, because the rule should not be ambiguous. If the rule doesn’t have a clear pattern to look for, it’s a bad rule.

This doesn’t mean that when a rule lists a violation that there is necessarily a bug, which is important to note and the source of much of the confusion. A violation simply means that the pattern was found. You have to look and say I am choosing these patterns and flagging these patterns because they are dangerous to my code. When I look at pattern, I ask myself, does this apply to my code, or doesn’t it apply? If it applies, I fix the code, if it doesn’t apply I suppress it.

It’s best to suppress it in the code itself rather than an external location such as your UI or a configuration file, so that it’s visible and others can look at it, and you won’t end up having to review it a second time. It’s a bad idea to not suppress the violation explicitly, because then you will constantly be reviewing the same violation. The beauty of in-code suppression is that it’s independent of the engine. Anyone can look at the code and see that the code has been reviewed and that this pattern has been deemed acceptable in this code.

This is the nature of pattern-based static analysis. It’s based on an understanding that certain things are bad ideas and may not be safe. This doesn’t mean you cannot do them in a particular context, but that such things should be done carefully.

Flow Analysis false positives

In flow analysis you have to address false positives because it will always have false positives. Flow analysis cannot avoid false positives, for the same reason unit testing cannot generate perfect unit test cases. When you have code that uses some kind of library, for instance your java code calls the OS and something come back, who knows what it’s sending? It’s going to be a false positive because we have to make assumptions about what’s coming back.

We try to err on the side of caution. Be careful here, if it’s possible that something strange might be returned protect against this. This finds bugs, that’s why it’s so valuable. You also need to understand the power and weakness of flow analysis. The power of flow analysis is that it goes through the code and tries to find hot spots and find problems around the hot spots.

The weakness is that it is going some number of steps around the code it’s testing, like a star pattern. The problem is that if you start thinking you’ve cleaned all the code because your flow analysis is clean, you are fooling yourself. Really, you’ve found some errors and you should be grateful for that.

The real question with flow analysis is the amount of time you spend going through results to find false positives, suppress them, and fix real bugs quickly before it goes into functional testing where it would be more difficult to find with debugging.

Lets say you spend an hour to fix and suppress a dozen flow analysis items at something like a 50% false positive ratio , which is pretty nasty. Now lets say one or two of these real bugs leaks into field, by the time you get info back from the field report to support and development, it may cost a half-day or even 2-3 days of time to address the issue. It is your decision which way is more time saving and effective.

In addition to flow analysis you should really think about using runtime error detection. Runtime error detection allows you to find much more complicated problems than flow analysis can find. Runtime error detection doesn’t have false positives, because the code is executed with a known value and had an actual failure.

Being Successful

The key to success is to choose which rules you want to adhere to, and then get the code clean progressively. Which means start with code you’re currently modifying and extend it throughout the code base until you are done. At some point when you see that there are very few violations, you can run it on the whole code base, rather than just recently changed code. In other words, set a small initial rule set with a cutoff-date of “today”. Then when you see violations dying out, add new rules, run it on the whole code, and review – we’ll discuss how to do the review in a moment. But we recommend extending the cutoff-date backward before adding new rules, because your initial rule set is only things that you feel are critical.

Rules/configurations should really be based on real issues you’re facing. IE if you take feedback from QA, code review, field reported bugs, etc. and then find static analysis rules to address those problems.

Sometimes developers fall into the trap of labeling any error message they don’t like as a false positive, but this isn’t really correct. They may label it a false positive because they simply don’t agree with the rule, they may label it because they don’t understand how it applies in this situation, or they may label it because they don’t think it’s important in general or in this particular case. The best way to deal with this head-on is to make sure that the initial rule set you start with has a small number of rules that everyone can agree on. It should product reasonable results that can be dealt with in a reasonable amount of time.

Resources

AI Smackdown – Siri vs Eliza

John McCarthy © by eschipul
John McCarthy, creator of LISP, and father of modern artificial intelligence (AI) died today. He was one of the first guys to work seriously on getting computers to do things that you wouldn’t normally have expected computers to do, like play Chess or have a conversation.

One of the most common AI applications programmers have played with over the years is Eliza. Like others at the time, one of my first attempts at writing an interesting piece of software in my youth was to alter an Eliza program written in BASIC (as taken from the pages of Creative Computing, for all you old-timers). Eliza is a simple software psychoanalyst created in the 60’s by Joseph Weizenbaum. While Eliza wasn’t written by McCarthy, she was certainly a product of his inspiration on the industry.

Ever since the new iPhone came out with Siri, the digital assistant, I’ve been thinking about comparing her to Eliza. I don’t often get to play with AI here at Parasoft and the death of McCarthy brought the topic to my mind again. I’ve put together a small comparison of questions and answers from Siri and Eliza. Note that with Siri, your mileage may vary, she doesn’t always answer the same way. I’ve obviously skipped most of the “useful” things that Siri can do, as it would be an unfair comparison for poor old Eliza, who doesn’t have all the modern advantages that Siri does.

It’s interesting because while they share a common logical bond, their personalities are very different. Siri was designed to be helpful and amusing. Eliza was specifically designed not to be helpful, in that she’s supposed to be a therapist and lead you to your own conclusions rather than give you answers. Eliza isn’t an assistant, she’s an attempt to play the “imitation game” also known as the turing test.

For the samples below I used a java version of Eliza that you can try for yourself on the web.

Samples:
Q: Can you help me?
E: You believe I can help you don’t you ?
S: You can say thinks like… (A list of sample queries)

Q: What are you doing?
E: Why do you ask ?
S: Just thinking

Q: Who is your favorite composer?
E: Why are you concerned over my favorite composer?
S: I guess I don’t have one.

Q: Are you married?
E: Why are you interested in whether I am married or not ?
S: We were talking about you, not me.

Q: What is your name?
E: I am not interested in names.
S: My name? It’s Siri.

Q: You are beautiful
E: What makes you think I am beautiful?
S: Oh, Stop.

Q: I love you
E: Perhaps in your fantasies we love each other.
S: Oh, Stop.

Q: How are you?
E: Does that question interest you?
S: I am well ____ (name)

Q: What do you think?
E: What is it you really wanted to know?
S:It’s nice of you to ask, but it doesn’t really matter what I think
or I think differently.

Q: Good night
E: I’m not sure I understand you fully.
S: Ah… it’s still only _____ (fill in the time)
or other answers depending on the time of day.

Q: Can you send a message to my brother?
E: Tell me more about your family.
S: I don’t know who your brother is, To whom shall I send it, I need a contact name, phone number, or email address.
orWhat do you want to say to ____ (your brother)?

I’m not sure about all of the reasons they’re so different. Sure, the state of the art in AI has come a long way since the 60’s. Or is it just that men’s expectations of women have changed? I was tempted to write that perhaps people are more friendly or helpful now than in the 60’s but that’s ridiculous. Perhaps it’s only that computers are now more helpful and friendly than they were. Is it possible that Eliza’s seeming bad mood had something to do with her obvious handicaps in memory and CPU. Maybe she was aware of this, and it caused her to be ill-tempered? In any case, Eliza comes across as a bit cynical, while Siri is much more light-hearted most of the time. Siri’s mood can definitely change as you can see from some of the answers.

It occurs to me that it would be funny to get Siri to talk to Eliza – would Eliza help Siri, or would Siri end up making Eliza more friendly?

So if your computer was nice to you today, thank John McCarthy.

[Update I added a few more links and minor clarification as well as AI resources]

Here’s a list of my favorite fiction books about killer AI.

Some resources on AI artificial intelligence:

Artificial Intelligence: The Basics

Artificial Intelligence for Humans, Volume 1: Fundamental Algorithms

Artificial Intelligence in the 21st Century (Computer Science)

The Artificial Intelligence Revolution: Will Artificial Intelligence Serve Us Or Replace Us?

Books on AI at Amazon

Your Two Cents About What Went Wrong With Static Analysis

I’ve gotten a lot of interesting feedback on the What Went Wrong with Static Analysis? post. So many people had their ideas about what was working, what wasn’t, and how to address it, that I thought I’d give people a chance to give their two cents.

I’ve created a poll which some basic issues as listed in the post and in various comments on it. Feel free to vote – there is a place if you have something not already on the list. After it’s been up for a bit I’ll post some results and commentary as is applicable.

Resources

Dennis Ritchie… Father of C, UNIX, and Much, Much More

I just posted a brief note about Dennis Ritchie at the Parasoft Blog. You can read about this amazing man who helped create C and Unix. Our thanks to him.

Reprinted below:


Dennis Ritchie - The creator of Unix and C
Dennis Ritchie – The creator of Unix and C

Dennis Ritchie, co-creator of the C programming language and UNIX operating system, died this week (2011). Back in the early days of Parasoft, we used to refer to “C” as “K&R C” (for “Kernighan and Ritchie C”). In fact, like lots of other long-time C programmers, many Parasoft veterans still have the classic C Programming Language book sitting on their bookshelves today.

Although he’s hardly a household name, Ritchie has had a tremendous influence on the software development community. Where might we be today if we didn’t have the luxury of building on his foundations?
On the language side, consider all the languages that were derived from C. Without C, there’s no C++…without which there’s no Java, no C#, and no Objective C. An enourmous amount of the software that we use everyday was built on those languages.

And on the OS side, think of all the things that stemmed from UNIX. Without UNIX, there’s no Linux. No Mac OS X. No Solaris. And without Linux, where would the open source community be? Would we have Android? What would the mobile device market look like? The server market?

In many ways, his vision was eerily similar to that of Steve Jobs: have it do what you really need it to do… and no more. It’s the epitome of elegant engineering.

If you compare C to Java, one of the defining differences is that Java is a very rich language. It has a built-in library that will cover pretty much anything you can think of. C has none of this—but it’s fantastically fast. It takes a lot less code to do something in C than it does in Java, VB, C# and the like. That’s really why C is still so popular. It’s a great balance between being close to the computer (and thus efficient) and being human understandable. The newer languages are more human understandable, but the trade off is that they’re rather inefficient compared to C.

The UNIX kernel is the same way. Amazingly, Thompson and Ritchie’s UNIX kernel was only 64K—smaller than the current Linux keyboard driver! UNIX truly respects the concept of having layers in an operating system. At the core, there’s just a kernel that runs the computer. Services lay on top of that. Networking is separate. Hard drives are an add-on (not core to the OS). And the GUI is a very high-level layer. This separation enables extreme efficiency. For example, while moving Windows to a new chip tends to open a can of worms, it’s actually quite simple with UNIX.

A few remarkable quips from Ritchie:

“I am not now, nor have I ever been, a member of the demigodic party.”

“UNIX is very simple, it just needs a genius to understand its simplicity.”

“C is quirky, flawed, and an enormous success.”

As Jon “Maddog” Hall, executive director of Linux International, tweeted: “…all programmers owe him a moment of silence.”

For a nice tribute to Ritchie, see the special Dr. Dobb’s newsletter.

Ranting about Software, Security and Tech