In defence of the Siemens Suite: There is nothing wrong with evaluating testing techniques on "small" programs.

Software testing research has an (in my opinion somewhat perverse) obsession with "scalability". When producing empirical results, techniques that have been applied to larger systems are favoured over techniques that have "only" been applied at a unit level. I know this, because many reviewers of my own papers (where empirical results tend to be produced at a unit level) have indicated this.

Take this example from a paper (that was happily accepted despite this comment) from last year:

"The case studies are small (and include the infamous and deprecated Seimans suite... the authors might want to work on **MUCH** bigger programs for future versions of this work."

The reviewer is correct in one respect; the Siemens suite (of seven small-ish C programs) is widely derided. I remember it being contemptuously referred to as "the seven dwarves".

I believe, however, that this derision of small programs is irrational. To support this I put forward three arguments. These are elaborated below.

First, let us set aside the specifics of what is meant by "size". A"small" program can be an executable program with <200 LOC and a simple interface contained within a single module (e.g. TCAS). A "big" program can be a large executable consisting of >10,000 LOC spread across multiple modules, with a complex interface (e.g. Mozilla or JEdit, etc.).

For the sake of terminology, we'll take a "unit" to mean a single executable piece of functionality (e.g. a public method in a class).

Argument 1: To be useful in the industry, a testing technique or tool does not necessarily have to scale up to "large" units or systems.

Complex software systems are commonly decomposed into relatively small units of functionality. Even if some units do happen to be too large for a given technique to test, it might still be capable of handling the majority of smaller units. If this is the case, then it would save time and resources, and would surely be useful.

The argument against the Siemens suite is not necessarily just the size of the units,  but also that they are old -- much of the code originates from the mid nineties. But then again, so is the code in many industrial systems, which commonly contain many legacy components (that are much older and smaller) than the components in the Siemens suite.

Argument 2: Real bugs are often contained within small units of code that can be run in a self-contained manner.

If one looks at some of the "bugs" that hit the headlines in recent years, one can often surmise that these could have been localised to a specific unit of code.

Look at the Apple Goto-Fail bug and Heartbleed, etc.:

https://nakedsecurity.sophos.com/2014/02/24/anatomy-of-a-goto-fail-apples-ssl-bug-explained-plus-an-unofficial-patch/

http://martinfowler.com/articles/testing-culture.html#heartbleed

These are all contained within functions that are of a comparable complexity to TCAS. In fact, Martin Fowler (in the above link) makes this case - they could both have been detected by unit-testing.

In other words, automated tools and techniques that scale only to "small" programs can readily have a huge impact. It brings to mind the formal-methods techniques that have found bugs in the Java implementation of the TimSort algorithm - a reasonably small piece of code, with a bug that ended up affecting billions of android devices and PCs.

http://www.envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/

So, if "much bigger" programs are required, how much bigger should they be? What criterion would they have to meet? And why?

Argument 3: A "small" system can be enormously complex

The critical piece of functionality might be contained within 5-10 lines of code. But one of these lines might call a library function. One can consider as an example a Java method that uses collections, calls Math utilities, IO libraries etc. So a relatively small program could be functionally very complex because a substantial amount of its functionality is delegated.

Even if libraries do not come into play, it is still possible to have compact programs that, within a couple of hundred lines of code, include complex data manipulations, and control structures. I refer again to the above example of the Timsort algorithm - implemented again and again, widely studied, relatively small, but still buggy.

As soon as a piece of code becomes difficult to rapidly verify by manual inspection (which is very soon), an automated tool or technique becomes very useful. Hundreds of lines of code are not necessary for this, and I would argue that the threshold for a useful tool is much lower.

Conclusions

This emphasis on scale has a pernicious effect on research. It focusses efforts on techniques that can feasibly apply to large programs, at the expense of (potentially much more powerful) techniques that can be applied to smaller programs. As a consequence, many of the really fundamental testing problems that have not even been addressed with respect to "small" programs remain untouched.

This attitude also drives an (in my view artificial) wedge between the formal methods and the software engineering communities. Important techniques that have proven to be enormously valuable in practice such as model checking and theorem proving are often dismissed because they "don't scale", and only get consideration in a Software Engineering forum if they are framed in such a way that they can possibly be adapted to "real life" "big" programs.

However, this attitude is again misplaced, for exactly those reasons that I have listed above. These techniques are useful, and are accepted as such in practice. Formal methods events such as FM have an industrial presence that can probably match that of most large software engineering events. I can think of many "unscalable" formal methods techniques to have been successfully spun-off or absorbed into the working practices large organisations such as Facebook and Microsoft.

For many tasks, there are no convincing state-of-the-art techniques that even work on small programs. So getting a technique to work on a small program is important, and is in and of itself potentially useful to the industry.

Let's not dismiss the Siemens suite.

Are Mining & Machine Learning bad for "risky" Software Engineering Research?

Machine Learning and Data Mining are playing an ever greater role in Software Engineering. To an extent this is natural; one of the big Software Engineering challenges is to find ways of dealing with the vast amount of information in the source code, version repositories, stack overflow, etc., and ML/DM algorithms often provide a neat solution.

To an extent, this rapid rise has been prompted by (a) the preponderance of tools that can easily extract mine-able data from software (and repositories etc.), coupled with (b) the rise in easily accessible and customisable ML frameworks such as WEKA, which can be easily used off-the-shelf.

However, I believe there is another factor at play, which is (in my opinion) symptomatic of a potential problem. The quality of an SE paper is often assessed in terms of the scale of the systems to which it is applied (yes - other factors come into play, but these are often treated as secondary factors). To be counted as a "mature" research product, the realism and scale of the evaluation artefacts are key.

Obtaining data for large, real systems is often relatively straightforward (c.f. the PROMISE repository, etc.). Given that ML implementations abound, there are few significant technical hurdles to applying advanced ML algorithms to large volumes of data from real systems. If the novelty of the paper lies in the choice of an existing, implemented ML algorithm to achieve an established SE problem, it is relatively straightforward to produce a proof of concept and a convincing publication.

However, this comes at a potential cost to other research. What if the data in question are harder to obtain, and the collection requires some advanced tooling - e.g. program analysis? What if the data analysis algorithm in question is not available off-the-shelf, and needs to be designed and developed? What if the technique involves a lot of human input, which hampers data collection? I worry that, regardless of their technical contribution, these techniques can be overlooked in favour of techniques for which it is easier to obtain large amounts of data.

Although understandable in one sense, there is a danger. There is a danger that "risky" research is disincentivised if it requires tricky tooling, or requires data that is difficult to obtain. Conversely, research on problems for which data collection is easy, for which tooling is available, is incentivised. This not only risks turning SE into some form of applied data science (which I think does it a disservice), but also risks driving research away from some of SE's most interesting unsolved problems.

Perhaps the implicit charge is that SE research can at times be evaluated in terms that are reminiscent of "Technology Readiness Levels" in the industry. Research techniques at a high TRL are more publishable than research at a low TRL. By implication, research that uses established toolsets (of which there are many in ML), gets a head-start. This could come at a cost to "riskier" research, for which there are fewer established tool/data-sets available.

Is “Software Analysis as a Service” doomed?

Imagine that you have developed an interesting new testing technique, software analysis algorithm, or visualisation approach. You want to do what you can to encourage practitioners and organisations to adopt it. For example, you might attempt to secure some funding to begin a start-up, to develop a self-sustaining company around the tool.

At this point, things become complicated. What business model will you choose? There is the traditional “client-side” approach; you produce a tool, you sell it to customers, or let customers download it for free and offer support for a fee. 

Then there is the “server-side” approach [1]. You host the tool on a central server, and clients can use the tool by uploading their data / giving your tool access to their code repositories. This approach has a huge number of benefits. It is easier to track access to your tool, there is a single point at which to apply updates, fix vulnerabilities, add features etc. You can collect accurate usage statistics, and can offer support in a more direct way. If you wish to come up with some sort of pay-per-use arrangement, you do not need to mess about with messy web-linked license files, as so many client-side tools still require.

It was surprising to me that such centralised tools are not more prevalent. 

The one major factor seems to be privacy and security. For many organisations, their source code can in effect represent their entire intellectual property. Making this available to a third-party represents an unacceptable risk, regardless of how useful an external tool might be. It is only in a few cases (e.g. Atlasssian’s Bitbucket), where there seems to be a sufficient degree of trust to use server-side tools.

Does this mean that, if you have a tool, you must immediately go down the route of a client-side IDE plugin? Otherwise you immediately seemingly rule out an overwhelming proportion of your user-base.

The flip-side is that, as soon as you release a client-side tool, it becomes harder to deploy within a large organisation, and your business case has to be overwhelming (which is not the case for most academic tool).

To me this is a huge “barrier to impact” for academic software engineering tools. Are there workarounds?

One way to operate the server-side option would be to perhaps have a “data-filtering” step that removes any sensitive information (e.g. identifiers) from the code, but maintains the information required for analysis. Though I’m sceptical that this would be enough to satisfy potential customers. 

Are there any more reliable cryptographic approaches that enable a client to use a server-side tool, without the server being able to make use of the data? Could there be something akin to the “Zero Knowledge Protocol” [1] that could be applied to server-side software analysis tools? 

[1] Ghezzi, Giacomo, and Harald C. Gall. "Towards software analysis as a service". Automated Software Engineering-Workshops, 2008. ASE Workshops 2008. 23rd IEEE/ACM International Conference on, 2008.

[2] Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). "How to Explain Zero-Knowledge Protocols to Your Children" (PDF). Advances in Cryptology – CRYPTO '89: Proceedings 435: 628–631.

Epistemology in Software Engineering and AI

Last week was a significant week for Computer Science. Engineers at Google demonstrated how their DeepMind AI engine was able to beat a European champion at Go - achieving a major milestone that at the very least matches the significance of Deep Blue beating Kasparov 1996. The week also saw the passing of AI pioneer Marvin Minsky.

I was struck by a blog-post by Gary Marcus that drew upon these two events. It touched upon the well-established rift between two opposed schools of thought within the field of AI. On the one hand you have the “Classical” school (espoused by Minsky), who argue that artificial intelligence must be a process of symbolic reasoning, underpinned by a logic and some formal framework within which to represent knowledge, such as Expert Systems, Inductive Logic Programming, etc. On the other you have systems that are not underpinned by logics or symbolic reasoning. Systems such as DeepMind are more “organic” in nature, relying entirely on the statistical analysis of training data (by way of mechanisms such as Neural Nets or Kernel Methods) to derive suitable models. The question of which school is right or wrong is something I’ll return to.

This split within AI is strongly reminiscent of a similar divide within my field of Software Engineering. On the one hand we have the “Formal Methods” school of thought which argues that it is possible develop a program that is “correct by construction” by the disciplined application of techniques that are founded upon logic and symbolic reasoning, such as program refinement and abstract interpretation, and that it is possible to establish whether or not an existing program is correct without having to execute it. On the other hand we have the “Proof is in the pudding” school of thought, which ignores the construction of the program, and focusses entirely on reasoning about its correctness by observing its input / output behaviour (i.e. testing).

In essence, both of these divides are concerned with the question of how one can establish knowledge. On the one hand you have the logicians who argue that knowledge is a product logic and reasoning. On the other hand you have the empiricists who argue that knowledge depends upon observation.

I find these divisions interesting, because they are fundamentally philosophical — they are concerned with the very question of what knowledge is and how it can come to be, otherwise referred to as Epistemology. The rift between the logicians and the empiricists is a continuation of a long-standing argument. This is nicely characterised by Popper in his volume on “Conjectures and Refutations” as follows:

“… the old quarrel between the British and the Continental schools of philosophy — the quarrel between the classical empiricism of Bacon, Locke, Berkeley, Hume, and Mill, and the classical rationalism or intellectualism of Descartes, Spinoza, and Leibniz. In this quarrel the British school insisted that the ultimate source of all knowledge was observation, while the Continental school insisted that it was the intellectual intuition of clear and distinct ideas.”

I find this link between Computer Science and Philosophy interesting for several reasons. The very fact that such an old argument of how to establish “truth” is still alive and well, and that it is being played out in the arena of Computer Science is exciting to me.

What is, however, just as interesting is the fact that this fundamental question of epistemology has been written about and debated for so long, and yet very little of this relevant epistemological history seems to filter through to papers within SE (and perhaps AI). For example, Dijkstra’s famous remark that testing can only establish the presence of bugs but not their absence, is merely re-stating an argument against the validity of inductive reasoning first put forward by Hume (that one cannot assume “that those instances of which we have had no experience, resemble those, of which we have had experience”) in 1740 (apparently - I admit, I didn’t read it, and am quoting from Popper).

Popper’s essay is interesting because he argues that neither of these two world-views adequately explains our “sources of knowledge and ignorance”. Submitting to the authority of logic alone can lead to false conclusions, as can submitting to the authority of empirical observation (Popper suggests that submitting to one school of thought over another “breeds fanatics”). He argues that the process of establishing and reasoning about truth is necessarily a combination of the two; a process of questioning authority (whether the authority of a logic or an observed piece of evidence), of forming conjectures and then seeking to refute them. A process of valuing a fact not by the amount of evidence that supports it, but by the amount of effort that was made to reject and undermine it.

Of course this all sounds intuitive and perhaps even obvious. In AI this lesson does seem to have seeped through. Returning again to Gary Marcus’ blog, the Go winning DeepMind system is not, as it might appear, a pure Neural Net construct. It is a hybridisation between Neural Nets and Tree-Search (a “classical AI” technique).   

In Software Engineering, however, the two tribes seem to remain quite separate (despite some notable efforts to combine them). I suspect that, when faced with the question of how to establish the correctness of a software system, a large proportion of academics would choose testing over FM or vice versa. The two approaches are often couched as (competing) alternatives, instead of techniques that are mutually dependent if the objective is to maximise the correctness and safety of a software system. 

References:

Popper, Karl. Conjectures and refutations: The growth of scientific knowledge. Routledge, 2014 (first published 1963).