John Carmack on Static Code Analysis
altdevblogaday.com
altdevblogaday.com
- Competitors with Coverity are CodeSonar[1] and Klocwork[2]. I've not seen Klocwork output, but CodeSonar and Coverity are in the same area of quality, with differing strengths. I can not recommend static analysis highly enough if you have a C/C++/Java/C# database. It's very expensive (well into five figures according to Carmack), but how expensive is a bug? What if you have your entire codebase checked daily for bugs? Consider the effect on your quality culture. :-)
- The fact that you are paying "well into five figures" for a tool that essentially covers up design deficiencies in your language should start sounding alarm bells in your head. The proposition more or less goes, "To have reliable C++ code in certain areas, you need a static analyzer; to gain that same advantage in Haskell costs you nothing more than GHC". Of course Haskell doesn't have certain C/C++ capabilities; but it's worth meditating on for your next application, particularly if bugs are more important than performance. N.b- I don't know the ML family enough to say one way or the other in this regard. :-)
My understanding is that their tools don't do "whole program analysis". Is that incorrect (I'd love to hear that I am!)?
Technically, the Microsoft tool only performs local analysis, so it should be inferior to Coverity’s global analysis, but enabling it poured out mountains of errors, far more than Coverity reported. True, there were lots of false positives, but there was also a lot of scary, scary stuff.
Both produce high quality output in their domain. Fortify is widely use in the AppSec world.
They also have better rules sets from what I understand than the open source tools.
The Microsoft compiler was way better than both. Around 10% faster run-time IIRC.
Any time you have dedicated sales staff selling stuff to organizations with a sales process that needs to get buy-in from executives, your prices have to go way up to cover that cost. (Doubly so because the sales process is expensive for you, and your price point lowers your success rate.) Unfortunately many organizations have a rule that every purchase over $X has to be approved by management. Thus there are 3 price points that you can find proprietary software sold at:
1. Small enough that a developer can charge it to a corporate credit card.
2. Relatively modest recurring payments, individually small enough to pass on a corporate credit card.
3. Starting well into 5 figures.
It is certainly true that many of the static errors that Coverity and friends can find aren't possible in Haskell because it won't compile, but I'd like to see a lot more public experience with Haskell and larger projects to see what the result would be for other problems. A lot of what we now know about how C++ should be written is the result of decades of hard experience, and who knows what we might find in Haskell with as much experience.
What Haskell brings to the table in terms of unique flavors of bug, I don't know. I would love to read articles about 1MLoC+ codebases in Haskell and how they play out.
http://code.haskell.org/~dons/talks/padl-keynote-2012-01-24....
The guys on our team have between 4 and 25 years (yes, not a typo) experience with Haskell.
P.S. We are hiring in London, Singapore and Tianjin.
---
A couple of days ago was CUFP, by the way, which includes a series of talks from different business users. http://cufp.org/videos/keyword/2269
Thanks.
As another for instance, partial functions can already be caught by some static analysis tools and we tend to think they are at least bad style (I would rate them as a serious code smell; every time I thought I wanted one, it was trying to tell me I had a fundamental design flaw), but they are certainly syntactically valid Haskell.
Regarding other code smells that the compiler can't catch: one thing I have come to really appreciate about the design of Haskell is that in the vast majority of cases, the path of least resistance is also the path of greatest clarity, correctness, etc. I mean, sure, you can write your entire program in IO, but it would be supremely irritating to do so. It's just simpler and easier to do it the "right" way, via composition of small, independent, pure functions.
When using other languages (for me, this usually means Java, Python, or JavaScript), I feel like I am constantly having to remind myself not to be lazy and to do things the way that I know to be right. Don't catch an overly broad class of exceptions. Don't rely on shared mutable state when an extra function argument will suffice. Avoid using null pointers to represent failure. Be sure not to use type-coercive comparison operators. And so on. These languages give you so many ropes with which to hang yourself, and even the standard libraries make idiomatic usage of them. Programming defensively feels like working completely against the grain.
Haskell, with its strong immutability and airtight type system, has shown me that it is possible for a language to guide programmers safely through the minefield without placing a severe additional burden of vigilance on their shoulders. It would be interesting to see a more conventional, imperative style language that followed similar principles. Or perhaps the "everything is in the IO monad all the time" nature of imperative code is just fundamentally at odds with code correctness, and we'll always have to fight against it.
In some languages, like D, you can fight against that, by declaring functions to be pure. That's a bit like having everything in IO by default, but marking the exceptions.
So, I wrote this module: http://source.git-annex.branchable.com/?p=source.git;a=blob;...
It's imported into every module in my program via a common include which also pulls in other support stuff. Now if I slip up and use head, I get a compile time error as there are two conflicting heads. If I really want to (after all, sometimes you have an invariant) I can use Prelude.head, and I can `git grep Prelude\.` to find all the partial code in my program (currently about 15 occurrences). Or I can read the fine comments in my module for a hint to a non-partial version to use.
There are other approaches, but I've found this to be a fine compromise.
http://www.altdevblogaday.com/2012/04/26/functional-programm...
(I prefer Haskell, it's much more beautiful. But that's more of a religious issue. OCaml is still way better than, say, C++.)
The issues that most people focus on however are : portability to the platforms they're concerned about, performances on these platforms, richness of the ecosystem.
Game programmers cannot consider Haskell or OCaml as real alternatives to C++ for these reasons. Yet.
That said, people learning to use these languages become better programmers overall. They get a better sense of how to structure, validate their data, and avoid a lot of pitfalls. Have look at the answer made by a representative of one of the products mentioned by J.Carmack - she goes through some of the reflexes she acquired while using her product, and there's definitely an overlap with the way people code using Haskell or ML. It's not an accident that C++ is moving toward incorporating features from functional languages.
Just for these reasons alone people should learn to code with languages like that.
BTW, I once considered this (this being a language with Haskell's strengths, suitable for systems programming) a possible idea for a thesis, but at least for now it's put on hold. If anyone has any comments, I'd really love to hear them.
There's also lots of work being put into Haskell right now, to make it more suitable as a low level language---some by direct work on Haskell, some by making it easy to embed DSLs that compile to carefully restricted low level code.
BTW, I wonder if they allow the programmer to better control when and how much memory is allocated, that seems to me like the biggest obstacle for using Haskell for low-level stuff.
I've been doing manual code reviews for a living now (mostly security related) for roughly 3 years now and while I get assisted from time to time by code analysis tools I still find heaps of bugs not caught by any of the tools mentioned by Carmack. The biggest issue for a development shop is to properly integrate these tools and to not overwhelm developers with too much false positives.
I've had cases where a developer got a 1500 page PDF spit out by one of these static analysis tools. After spending two weeks going through everything the developer ended up with 50 pages of actual bugs; the rest were describing false positives. Then I got on-site and I still logged dozens and dozens of security-related bugs that the static analysis tools failed to find.
Edit: also consider that one even needs a SAT solver to even do proper C-style preprocessor dependency checking. A lot of these code analysis tools are being run on debug builds only and then there when the release build is being made these tools are not being run meaning they fail to catch a lot of issues. It's insanely hard to write proper code analysis tools and static source code analysis tools which do not integrate with the compilation process I wouldn't trust at all.
Nowadays with clang there are very nice possibilities for someone to write your own simple checks and integrate them into the build process. But even clang doesn't expose everything about the preprocessor that you might want to have from a static code analysis perspective.
A couple of years ago I ran across an article from Coverity about the challenges that they had getting people to use their tool. One of the most interesting was that the tool would find real bugs, but the developer wouldn't understand that the bug actually was real, and would say, "This tool is crap." Then they would not get a sale.
They had this problem particularly strongly with race conditions. There are a number of checks that they took out because, even though they were finding real bugs, developers were convincing themselves that the bugs were not real even though they really were.
It really does not help that the developers who are asked to evaluate are likely to be the same people who made the mistakes in the first place, so all kinds of defensive behavior are to be expected.
Through the years I've learned how to talk with developers about their bugs and how to help them get better in preventing it. It helps that I've been a developer for years too so I know where they're coming from and how they sometimes tend to get all defensive.
(Full disclosure: I work for HP Fortify.)
I've seen simple cases where a function returned a signed integer value modulo x. Which of course means that this function can only return a value within 0..x-1.
This function was called in another function which then did some allocations based on it and the static analyzer complained about integer overflows which were obviously not possible in this case.
Dependency chains in preprocessors is a big pain in general too.
#ifdef A #define B #endif
#ifdef C #ifdef B blabla #endif #endif
This will yield a dependency chain for B of (A,C) -> B resulting in blabla being compiled. With complex code bases this already becomes quickly unmanageable. As far as I know no code analyzer is able to handle this.
And I haven't even started talking about supporting #if constructs (ex: #if X > 2). You would need to implement SAT solvers for that too.
Some more info on this at the clang mailing list here: http://lists.cs.uiuc.edu/pipermail/cfe-dev/2012-July/022720.....
These are just other reasons why seperating the preprocessor from the rest of the language was such a bad idea; you lose all the static code analysis stuff you can do on C/C++ code because of it and preprocessor directives control a lot of things in modern and big code bases.
Actually, signed modulo can return negative numbers... See, for example, this StackOverflow question:
http://stackoverflow.com/questions/7594508/modulo-operator-w...
Also there's just no guarantees on how the software is built; in a lot of cases that's even outside a developer's reach.
But, yeah, since it's next to impossible to actually get to that state then, yes, sadly the only real option left is to analyze your finite set of builds.
Along with the problem you describe, one occasionally sees stuff like this:
#if A
void foo() {
#else
void foo(int x) {
#endif
Here there are two versions of the beginning of a function definition. There's not even any way to represent that in an ordinary AST, even if you could parse it, which you can't with any ordinary kind of parser. And it's not hard to come up with even nastier examples.I remember the day I actually realized what a clusterfuck the whole preprocessor was when trying to figure out all this precompiled header craziness; it's only there to solve all the horrible shortcomings of the POSIX/C/C++ eco-system as designed and imposed on it by how the preprocessor works. Even Strousup at several occasions admitted that he would like to have the preprocessor removed from C++. That's not going to happen anymore and it's obviously Captain Hindsight speaking here.
Something which corroborates this: When penetration testers break into systems, they're often using new 0-day exploits. Think about that. Most of today's software development practice produces such a steady stream of low-level bugs, that penetration testers can assume that they're there!
> Trying to retrofit a substantial codebase to be clean at maximum levels in PC-Lint is probably futile. I did some “green field” programming where I slavishly made every picky lint comment go away, but it is more of an adjustment than most experienced C/C++ programmers are going to want to make. I still need to spend some time trying to determine the right set of warnings to enable to let us get the most benefit from PC-Lint.
This could be encouraged using game dynamics. Have a mechanism where a programmer can mark parts of the codebase "green-field." A programmer's "green-field score" consists of the number of lines of green-field code (or statements, whichever lousy metric you want) that he's successfully compiled with no warnings whatsoever. Combine this with random sampling code walkthroughs, which has many benefits but will also catch boilerplate, auto-generated, or copy-paste programming by a "Wally" who's trying to "write himself a new minivan."
- I like that the contracts are right there in the code and not in a separate file.
- The actual Contract methods only run once upon loading each class, so they don't cause a performance hit. I'd like a way to make them all noops (so they don't add any instrumentation) when running in "production".
- My thought is that if you can define pre- and post-conditions as you're doing, then you can cut out a lot of the checks in your tests, so that as long as the tests exercise the code, you can rely on the post-conditions to do quite a bit of the validation. Plus you're validating outputs all over the place constantly, so you'd probably catch edge cases you never even expected.
- I'm disappointed that your system seems to offer little more than type checking (unless I'm mistaken). I'd like something that gives me true pre- and post-conditions: basically passing a block of Ruby code for each one, with common idioms abbreviated so I don't need to write a whole block if the conditions are simple.
Good luck on the project!
> I'd like a way to make them all noops
Sure! There's a default failure callback that gets called when a contract fails. You can just clear this callback in prod:
if ENV == PRODUCTION
class Contract
def self.failure_callback(data)
# blank
end
end
end
> I'm disappointed that your system seems to offer little more than type checkingNay! You can write your own contracts to do anything you want. So yes, lambdas are allowed in contracts:
Contract lambda { |x| x.is_valid_email? } => Bool
def save_email(email)
# save an email
end
> with common idioms abbreviatedI provide some common idioms already, but you can make your own abbreviations:
ValidEmail = lambda { |x| x.is_valid_email? }
Contract ValidEmail => Bool
def save_email(email)
Let me know if you have any other questions :)The false-positives are a problem and the general advice to get started is to initially ignore all existing bugs and focus on avoiding adding new bugs. Then, when you get the hang of writing code that passes the checks you go back and look for the worst of the older bugs, etc.
Many a true word spoken in jest!
It does impact Microsoft more, because Microsoft has taken on responsibility for games to be good (well, meet certain baselines for various definitions of good) through their TCRs.
If you haven't read it, do so.
You can read further discussion on this 270 days old article at http://news.ycombinator.com/item?id=3388290
"Google held a global "fixit" day using UMD's FindBugs static analysis tool for finding coding mistakes in Java software. More than 700 engineers ran FindBugs from dozens of offices.
Engineers have already submitted changes that made more than 1,100 of the 3,800 issues go away. Engineers filed more than 1,700 bug reports, of which 600 have already been marked as fixed. Work continues on addressing the issues raised by the fixit, and on supporting the integration of FindBugs into the software development process at Google."
http://checkstyle.sourceforge.net/
http://cppcheck.sourceforge.net/
http://google-styleguide.googlecode.com/svn/trunk/cpplint/cp...
http://www.dwheeler.com/flawfinder/
http://www.dsm.fordham.edu/~ftnchek/
http://community.haskell.org/~ndm/hlint/
http://search.cpan.org/dist/Perl-Critic/bin/perlcritic
http://deployingradius.com/pscan/
http://pychecker.sourceforge.net/
http://pypi.python.org/pypi/pyflakes
http://packages.debian.org/squeeze/rats
http://www.incava.org/projects/303902593
http://packages.debian.org/stable/devel/icheck
Please note: I have not used all of these; one day I was bored and decided to see how many code checking tools I could find packaged for Debian and put them all in a script with the warnings cranked to the max and make that part of my default nightly build and test script. Of course, you can also crank up warnings on your compilers and interpreters as well (-Wall -Wextra, python -tt3 with warnings.simplefilter("always"), perl -tTW with use strict and use warnings, etc)
> If you aren’t deeply frightened about all the additional issues raised by concurrency, you aren’t thinking about it hard enough.
Why exactly is that?
Qamine integrates directly with github and is designed to be used by small and medium companies that cannot afford those expensive tools.
the `Controler' part of my main codebase consists of interwoven PHP and MySQL. Is there static analysis tool that understands both, one in relation to the other?
Imagine a tool that could analyze this:
//sql table T having columns int x, string y
//php
$data = sql_fetch_from_column(T)
//javascript
var d = <?=json_encode($data)?>
for(a in d)
var b = a.x / a.y; //Type error, int division by string not defined public Statement ageFilter(int minimalAge) throws SQLException {
Connection conn = getConnection();
String sql = "SELECT name FROM people WHERE nmae IS NOT NULL";
if (minimalAge > 0)
sql += "AND (age >= " + minimalAge + ")";
return conn.prepareStatement(sql);
}
There are a lot of really interesting challenges in doing this. Their tool uses a powerful technique called "abstract parsing" which can analyze all possible parse trees created by running the SQL parser on a string produced by Java string operations. It's pretty impressive what modern static analysis can do, and just how weak the linters we've gotten used to are in comparison.I also find getting a good set of rules for phpcs is extremely helpful in PHP. You can use its sniffs to catch past mistakes and enforce consistent coding standards.
Another dev and I spent literally the entire day fixing issues - and we had jslint running on every checkin until a few months ago!
But, it was worth it. It feels great to know that those bugs won't happen again without a failing build :)
That's because `for(var i=0...` is completely bogus. What if you have two of those loops? Are you going to put `var` in the first one, but not in the second one? Are you going to use 'i' in the first one and 'k' in the second one?
What if you need some refactoring and those two loops switch places?
It's fine if you like Java, but JavaScript is different. When in Rome, do as the Romans do. I also wish there would be block scope, but merely pretending there is doesn't make it so.
It's better if you declare all of your variables at the very top of the innermost function, because that's where they effectively are (thanks to hoisting). It's better if your code reflects how it's actually working, because that will always make it easier to comprehend.
Once there is `let`, you should switch to Java's "declare on first use" rule and never use `var` again.
And while I agree that declaring vars at the top is closer to whats actually happening, I disagree that it makes it easier to comprehend.
function foo () {
x = 5; // totally fine
...
var x; // because we declare it here
}What's the bug that results from the "var i; for(i=0)" pattern? Someone refactors the "var i" away and you end up with a global var.
So, really, while the pedantic answer is to forbid the pattern, the pragmatic answer is to recommend it.
Wrong. JSLint will complain and then you'll fix it. That's why you use JSLint. It can find stupid things like this easily and accurately.
And then fire that person. (Or rather, see if big commits introduce more bugs than short ones, or whatever else you might find.)
Here's a some for asp.net, http://stackoverflow.com/questions/4419253/seeking-a-code-an...
For .NET you have Code Contracts[2], this requires you to annotate pre- and postconditions for your functions but after that it's for example impossible to pass a possibly null into a function without compile time error. It can even do range-check of numerics after calculations etc.
ReSharper has much better recommendations that require almost no tweaking (variable names you might disagree with). The best part, it tells you these recommendations at the time of writing. This is one of ReSharpers best features (IMO). Not only do programmers write better code with, they often write code that works the first time and compiling becomes just a technicality. Code improvement is noticeably better. So much so, that when my company is hiring and I am reviewing the candidates submission; I can immediately tell whether or not they were using ReSharper.
Cannot recommend this tool enough. I feel crippled without it in VS.
Just be aware of your default shortcuts if you look into ReSharper. I remember that some of them change on you.
Googling "$LANGUAGE lint" will probably find what you need.
I think it's false, and a huge mistake. There is rare cases, but not plenty. Video games (I mean video games for core gamers) are products that demand first and above all quality to be successful. There is rather plenty of common games with a huge quality which become hits (Kingdom Rush for example or Starcraft which was finally kind of common in its time). One of the rules in the delovepment process at Blizzard is that they ship a game when it has less than 100 known bugs. Also, I would add that, it seems that, ID software did not make a successful games since Doom. Quake wasn't a commercial success, Quake2, Quake3, Doom3 and Rage neither (that's why ID software has been bought for only $100M). After all, ID Software lost one of its core value co-founder a long time ago (John Romero) who was responsible of the gameplay of ID's games...
Quality in video games are everything, that's really my opinion. It's also really an edge for every indy developper which want to start a company in this sector, cases are countless.
Well, I wouldn't say nobody. I, for one, play/watch Quakeworld and Quakelive on a regular basis.
Do you have actual sales numbers to back that up or is this based on anecdotal evidence, or is it just because you didn't like the games as much :)? Publicly available internet numbers show that Doom 3 sold 3.5 million, and even Rage sold 2.31 million, making Doom 3 extremely profitable and probably putting Rage a little higher than break even given the long development time and much larger team size.
Two of the Quake games are listed on wikipedia's top selling PC games and sold 1.7 and 1 million. (http://en.wikipedia.org/wiki/List_of_best-selling_PC_video_g...)
Although none of these numbers are 100% accurate unless they are wildly off I wouldn't call any of id's games except Rage unsuccessful.
The argument here is that lots of successful games are buggy, and id Software's games aren't buggy. Trying to run BioShock on my computer is a nightmare (you have to mess with compatibility settings, and even then you get no sound at all). When I played Fallout 3 it crashed about once every few hours of play time, and that was late 2012 with no add-ons -- 4 years after the game's release you'd expect patches to address things. Bethesda has a kind of reputation for releasing buggy games, it seems.
Oh I've always liked ID Software and I still do. But anecdotal evidence show that it's been a very long time that they haven't made a trully hugely successful and highly regarded title.
Doom 3 sold 3.5 million, Rage sold 2.31 million, Two of the Quake games are listed on wikipedia's top selling PC games and sold 1.7 and 1 million
Even if these numbers were real, they wouldn't correspond to trully hugely successful and highly regarded title. For example: Minecraft[1] sold 7 millions of java copies. The Call of Duty series sold more than 50 millions copies. The startcraft series sold more than 10-15 millions copies.
A hit today is 5-10 millions copies per platform. Compared to the 2 millions of Rage, there is a huge gap.
I'd not arguing that id is still a dominant force in the industry (they aren't), but calling all of their games after Doom commercially unsuccessful is a little extreme.
Your definition of a hit being 5-10 million copies per platform means the only hit game is Call of Duty. If an average AAA title sells 5-10 million total it is wildly successful, and 2-3 million is usually still profitable or at least breaking even.
Okay, yes, Blizzard games are nice and stable and polished too. But have you been reading the Starcraft development articles recently? They've been talking about how much of a nightmare the entire experience was, with major bugs until just before launch. From what I gather, one of the senior developers was running around fixing bugs across the entire code base, and personally reviewed and fixed up an astonishingly large percentage of Starcraft code.
One can wonder: if they were using static analysis, could they have shipped the same game earlier?
Quake was/is one of the best games of it's genre, ever. It sold 1.7 million copies, as a shareware release.
Doom 3 sold 3.5 million copies. It wasn't a commercial success?
Not to mention the games that were built on top of id technology, games like Half Life, Call of Duty, et al
Also, Minecraft[2] sold 7+ millions of java copies. It's more than x2 copies than Doom3 on "one platform".
[1] http://www.develop-online.net/news/36960/Tencent-pays-400m-f...