The Theory of Testing Programs - An Information Theoretic View

Staff - Faculty of Informatics

Date: / -

USI Lugano Campus, room SI-006, Informatics building (Via G. Buffi 13)

David Clark, University College London, UK

Can we have a more principled approach to testing software? Could a more principled approach be useful in guiding the way we go about it? To be truly useful it would have to explain what we know already, explain what we don't understand well at present, and somehow integrate these understandings. I am interested in the degree to which Shannon's Information Theory (SIT) and Algorithmic Information Theory (AIT) might offer the basis of a pricipled approach. Both are measures of randomness, SIT for probability distributions and AIT for strings, and are linked by one of the fundamental theorems of information theory.
We are, of course, far from a general theory. At present we are at the stage of examining phenomena in testing, devising models for these, deriving measures from the models, and attempting to successfully guide testing strategies using the measures. I will introduce SIT and AIT then conduct a whistlestop tour of models and measures for diversity, coincidental correctness, oracles, and test case prioritisation, and other software testing phenomena.

David Clark is a late convert to Computer Science being formerly interested in teaching high school mathematics and campaigning against apartheid and other injustices. His Computer Science interests since conversion have included formal program analysis, safety critical systems, secure information flow, applications of search methods, and software testing. He currently leads three UK funded projects: GGGP on genetic improvement of programs, InfoTestSS on information theory in software testing, and Malware Triggers which is more or less self explanatory. He also has a number of other interests about which he is very happy to talk if you invite him.

Host: Prof. Paolo Tonella