History of static analysis tools for defect identification

Question

As part of an article I'm writing, I wanted to give a sense of how long static analysis tools have been with us. There was no mention of them in my copy of The Mythical Man-month (1982 edition). This 2022 CACM article cites lint as the earliest example, and Lint, a C Program Checker doesn't reference any prior work.

Does anyone have an example of public prior work before 1978?

"Public" would include university research, but not something developed internally for a corporation but not released. I'm also not interested in static analysis performed as part of an optimizing compiler; I'm looking for a separate tool, focused on finding defects in code.

A static analysis tool is not necessarily after finding defects in code; it could be used to compute metrics of some sort. For example, I've seen a mid-1980s tool which purpose was to compute the max depth of stack a (non-recursive) Pascal program may require, given its source. — Leo B., Nov 06 '23 at 17:44
@LeoB. is right - though static analysis these days does refer primarily to checking for errors - it's scope is actually wider. And as in so many of these "programmer's helpers" things, I'd look to the LISP community for earliest developments. For example, consider MasterScope, part of Interlisp - and documented in my 1974 Interlisp ref man. See the article "The Interlisp Programming Environment" (Teitelman, Masinter, 1981) (page 4 of the PDF) for a very brief description. (And keep reading for DWIM, prog. assistant, and more) — davidbak, Nov 06 '23 at 18:17
You may not consider that kind of thing - cross-reference utility - to be "static analysis" - and it isn't as we know it today - but it was for the time! And it was pretty good for its time too! Anyway, if you're specifically thinking of defect-finding tools you can clarify your question - but IMO letting the question stand for all kinds of "static analysis" history would be nice. (Oh, and I wasn't suggestion that DWIM or Programmer's Assistant were static analysis of any kind - just that they're interesting facilities Interlisp had way back then ...) — davidbak, Nov 06 '23 at 18:34
Once upon a time in the early 1980s I was using a version of Spice (which has a long, convoluted history between multiple universities, companies, and government entities). The version we were using had ... issues ... and I was trying to figure out why. Turned out getting the compiler listing of variable names showed an amazing number of typos that had not been caught, leading to all kinds of gymnastics to get the 'right' answer from a complete mess. — Jon Custer, Nov 06 '23 at 18:50
The earliest analysis tools I remember are going back to assembly programming in punch card times. They were all about counting empty lines vs. comments vs code. Some even distinguishing code lines into instructions, macro usage and data definition. Or comments in 'empty' vs. meaningful. Those metrics were used for various purpose, including estimations of code quality and/or productivity of programmers. Management always tried hard to quantify what those pesky engineers did. — Raffzahn, Nov 06 '23 at 19:29
In that context it might be useful to acknowledge that back in the early days there wasn't such thing as a clear distinction between internal or external, product or single use. — Raffzahn, Nov 06 '23 at 20:27
Technically, the error and warning messages from any compiler should probably count as static analysis tools. Lint largely exists because C compilers were historically so crappy at it. In the 90's it didn't do anything that you didn't get with Ada compilers right out of the box. — T.E.D., Nov 07 '23 at 17:13

score 11 · Accepted Answer · answered Nov 06 '23 at 22:51

MALPAS was developed in the 1970s at the Royal Signals Radar Establishment (in Malvern in the UK). The Wikipedia page has an overview of the different software analysers and what they do. The article omits saying how much manual effort is needed to perform a good analysis. The analysis tends to be done when the software is largely completed. Several of the MALPAS software analysis projects have done by an entirely different company to the authors of the software being analysed.

I am not sure how "public" the first versions of MALPAS were, but it was actively used in the 1980s and is still being used now (in 2023). I went to an internal RSRE lecture by one of its primary authors in 1976, sadly I forget the persons name and my notes are long lost.

I think MALPAS comes closest to what I'm looking for, even though its usage post-dated lint. I'm going to assume that the research was ongoing in the 1970s. I also used the Wikipedia page to explore other options, but didn't see anything relevant. — kdgregory, Nov 12 '23 at 13:44

score 4 · Answer 2 · answered Nov 07 '23 at 07:48

4

I'd suggest that your identification of Lint is correct, at least as far as publicly-accessible tools were concerned.

Prior to the C family of languages it was generally considered part of the compiler's job to catch errors using type checking etc.

It was only with the rise of C, which intentionally skimped on that sort of thing, that separate tools became necessary.

answered Nov 07 '23 at 07:48

Mark Morgan Lloyd

2,428
6
22

1

The last sentence might be central here. – Raffzahn Nov 07 '23 at 14:11
@Raffzahn It was certainly still considered to be a major innovation in the mid-80s, and one that not many people could implement well hence the successful business of Gimpel. However it would be interesting to know whether anything equivalent existed for IBM mainframe assembler which by that time had pretensions of having high-level structures. – Mark Morgan Lloyd Nov 07 '23 at 14:17
Sure we're talking about the same? I wanted to underline the part that lint only became necessary due C falling short compared with (most) previous languages. THE situation with assembler is a bit more diverse. IBM's HLLASM is a product of the 1980s, but other companies had macro based extensions already ca. 1975. The product we used did all tests (nesting, valid parameters, etc.) during compile, external tools focused on the beautification part for source and listing. We also used an editor extension for syntax and nesting checks during edit. – Raffzahn Nov 07 '23 at 14:41
@Raffzahn But HLLASM was- as I understand it- also weak on type checking, so it's interesting to consider (a) whether there was some separate checking tool and (b) whether or not it was public. – Mark Morgan Lloyd Nov 07 '23 at 18:37
HLASM is still an assembler, so type checking past basic types (byte/halfword/word) isn't something that can be done on a generic base. That's why next to all findings those macros/tools could tell were remarks, not errors. The macro set we used did further checks during compile for parts they controlled. It was a standard product. Originally tobe bought on it's own. During the late 1990s its basic version became part of the standard Assembler setup. – Raffzahn Nov 07 '23 at 22:38

score 1 · Answer 3 · answered Nov 07 '23 at 21:19

In the summer of 1983 I was a summer student on an electronics project, tasked with making a number of transistor and diode measurements in the lab, and then based on those construct Gummel-Pool models of the various devices to deliver to the design engineers.

These models would be used in a variant of Spice (circuit emulation not spacecraft locations). Spice had first come out of UC Berkeley in 1973, and as public domain was taken up by various places to update and tweak, and those version then moved around and got further changed. The company I was working for had picked up their install from some other university. Spice was in Fortran, and we had compiled it for use on a Vax under VMS.

Well, I started putting together models, and then ran them in Spice simulations of the measurements I'd done in the lab. The models in Spice did not match the transistor curve traces off the oscilloscope. OK, checked and double checked my data interpretation to get the model parameters. That all seemed fine.

So, what was Spice doing with the model parameters? Hey, we've got source code so I can go look. Well, the source was pretty messy. Really messy. But I started seeing some weird things - things like a GOTO XXX, where XXX was a terminal page or two down the file. And there was no way to get into the code between the GOTO and the XXX label. So, a big chunk of skipped code, followed by a bunch of code that looked pretty similar.

Since it was pretty painful to trace the logic of the combined FORT4 and Fortran 77 dialects, I chose a simple first (well, now second or third) step - compile the code and have the compiler spit out a list of variables used.

Inspection of the variables revealed a number of near-alike variables. Often the difference was '1' vs 'l' or '0' vs 'O'. These were quite hard to see using the VT100 terminal fonts in use at our site, and would have been on various IBM terminals I had used at the time elsewhere.

Now that I had a list of funny variables I could search more easily. Well, all those weird skipped blocks contained one version or another of at least one near-alike variable name. But, the skipped block and the now-executed blocks of code were not precisely the same either.

My take was that various editors at various times had made typos and not recognized them. Then tried to get the code to work somehow. Once someone 'rewrote' a block and got something to kind of work, the next person would tweak something, but perhaps edited the wrong block and assumed it would be fine.

Anyway, I used the compiler dump of variables to go in an straighten out all those weird blocks and eliminate all the typos and recompile that code. And then, miracle of miracle, the Gummel-Poon models worked properly (sometimes to the disgust of the designers who had hoped the devices would behave somehow else).

Not sure that using compiler-provided data counts as 'static analysis tool'.

History of static analysis tools for defect identification

3 Answers3