Migrating

Hi all.

I'm migrating my blog from here over to http://rorytulk.wordpress.com, soon to become www.rorytulk.com. Please adjust accordingly.

Software Testing Techniques, an Empirical Approach

Proper software testing regimes are a cornerstone of effective software engineering. Progress has been made to teach students sound testing techniques, but improvement can still be made. My master's research supervisor and I conducted a study designed to empirically determine the difference in ability between student and professional software testers, and elicit from the experts behaviours or techniques which may be used to enhance undergraduate curriculum.

Our experimental setup consisted of in-lab observational sessions where subjects wrote thorough suites of JUnit tests for sample software we'd created. Subjects were drawn from the University of Toronto’s undergraduate computer science student body and professional developers from the Greater Toronto Area. The test code and video logs created during these sessions were examined for trends present in the student and professional groups.

Our intuition going into the study was that professionals would find more defects with their test suites, an advantage stemming from some metric such as number of tests written, lines per test, code coverage per test, etc. Analysis of these metrics did not confirm these hypotheses, however. Students and professionals performed equally well in terms of number of bugs found. However, student code contained more defects and, more importantly, the types of bugs found differed strikingly between the two groups.

Bugs in the sample code were broken down into two categories: stateless and stateful. A stateless bug is uncovered by inputting invalid values into a method invocation, and the method returns invalid results or throws an exception. A stateful bug occurs when a method call corrupts the object's state, and so subsequent calls perform incorrectly. Students found a mix of stateless and stateful bugs in the code, with a strong majority being stateless. The professionals sampled found strictly stateful defects. There are several possible explanations for this effect, although no evidence to support one over the others is immediately apparent.

The full text can be found here.

Left-Fold for Bash

I'd like to share a recent bash programming experience I've had. It began while processing the reams of data generated in my M.Sc. research study. I was producing long lists of frequency data in text files, and had the need to sum up all the lines in these tables. This is of course a trivial problem in many languages, and I had a wide array of options available to me:

• I could write another ant task to do the summing (this required more work that I was willing to invest, as ant isn't really suited for computational tasks)
• I could write a python script that took the contents of the specified file and returned the sum. I didn't really like this approach because it involved yet another file in my build process, invoked from the ant task. I always sort of thought that if you were forced to use , you were performing a task beyond the scope of your tool.
• I could skip the generation of the table and go straight to the sum. A few of the tables were created with XSLT, so this was a valid option. However, my XSLT programming ability is very much trial-and-error based, so I thought this might take some time. Also, some of the other tables, created with grep would not be affected.
  
• Write it in shell. I liked this idea. I really liked the feel of being able to just pipe something to 'sum' and have the sum returned. So this is what I chose.

My first version looked like this:

#!/bin/bash

sum=0
while read line
do
sum=$(($sum + $line))
done

echo $sum
exit 0

It did the trick quite well. I had suggestions from office mates for the following alternatives:
Using python (courtesy Aran Donohue):

python -c "import sys;print sum(float(x) for x in sys.stdin.read().split())"

Using tr (courtesy Zak Kincaid):

cat numbers | tr '\n' '+'|head --bytes='-1'|bc
(Note that this version doesn't quite work. bc throws a syntax error. not exactly sure why.)

Using my original design, I realized that if I abstracted out the operator, I could use this script to perform any 2-operand function I wished on the list, essentially creating a basic left fold:

#!/bin/bash
op=""
if [ "$1" == "" ]; then
op="+"
else
op=$1
fi

sum=0
while read line
do
sum=$(($sum$op$line))
done

echo $sum
exit 0

I've done a little bit of error checking, to see if the parameter supplied is blank, and if so replace it with + by default.

I've only seen this work for '+' and '-'. If I use '*', it breaks because it replaces the wildcard/multiplication character with the listing of the current directory.

Unifying Visual theme

A discussion this morning over coffee has prompted me to again consider creating a personal web presence, more than just a facebook or twitter page. A public, hosted site with data about my work and research. Inevitably, whenever I begin to consider this, I always get hung up on the visual theme for said space. In a perfect world, I would create a site in which the visuals closely match my personality, in a cool-hip sort of way, be cleanly unified across all the pages, and indeed could even integrate well into my local operating system's visuals (this doesn't serve any particular pupose, the idea of total uniformity just seems sort of cool to me). Anyway, looking at hosting and gnome-look.org for inspiration right now. Probalby won't lead me anywhere :P

Multi-User SVN on a Single Debian Account

Just finished setting up a multi-user subversion repository, based on the instructions found here. The catch here is that the SVN server is running on a single server-side user account, and the multi-user support is done by multiplexing on the incoming ssh rsa key. Every key gets its own artificial user name, so we can track who has been doing what. The process was fairly straight forward, just backup your .ssh directory in case you bork something, like I did:P

Algonquin Park Map

After doing some looking around for an electronic map of the canoe routes in Algonquin Provincial Park, I was only able to come up with the following :

http://www.cs.cmu.edu/~crpalmer/algonquin/map.html

It's pretty old, and the site hosting it looks like it may be somewhat unreliable, so I duplicated the file and made it available here for posterity:

http://www.cs.toronto.edu/~rtulk/alg2-1.pdf

In Praise of the TS&CC

This past weekend, while enjoying a leisurely walk along the waterfront between High Park and Ontario Place, I came across the Toronto Sail & Canoe Club (TS&CC). I headed back there, by bike, last night, in hopes of getting some more information about the club. Within minutes of arrival I was on the crew list, and had spoken to a few skippers who were looking for crew. I ended up on a Beneteau First 235, which is a nice little racer. After 45 minutes or so of reconfiguring the race course, we were off! Just in time for a the storm front to get close enough to steal away all our wind! The race was uneventful, but relaxing, and I got to meet some new people, so it was an overall positive experience. I think I'll be going back next week for more of the same.

Oh, did I also mention that a Crew membership at the TS&CC is extremely affordable? Well, it is!

Creating Defects

I'm in the process of inserting defects into three pieces of software I've written - for the purpose of creating testing samples for the study. This process is a lot more painful that I would have anticipated. I expect it is due to being trained for so long at removing defects, not deliberately creating them. Every time I break something, I realize the cool test case that will fail because of it, and then I feel bad. Also, trying to create non-obvious errors, or defects that are a little more human than those created by my java mutator, is challenging. For example, consider a class constructor like the following:


public MyAccount(int account, int initialBalance)
{
m_accountNum=account;
m_balance=initialBalance;
}

The mutator would do something like this

public MyAccount(int account, int initialBalance)
{
m_accountNum=account;
m_balance=++initialBalance;
}

following its set of one-line operator rules. I think I a more 'human' error would be something like this:


public MyAccount(int account, int initialBalance)
{
m_accountNum=initialBalance;
m_balance=account;
}

or this:

public MyAccount(int account, int initialBalance)
{
m_accountNum=account;
}

All still valid java programs, but definitely erroneous, and certainly slips that an overworked developer could make. What sets them apart from some of the mutation bugs is that many of the mutation rules require more effort on the part of the developer, rather than less (ie. a ++ at the end of a variable manipulation command is more likely to be omitted than included by accident).

Think Aloud and Coding Analysis

Chris pointed me at a paper by Mayrhauser and Vans "Identification of Dynamic Comprehension Processes During Large Scale Maintenance" that seems fairly relevant, in that they are using methods that align with mine so far. They've used a Think Aloud process and recorded participant actions while performing a maintenance change request. The activity took approx. 2 hours per subject (11 subjects. I think I can do better). Video and audio recordings were transcribed and coded. The authors posit that a) coding should be based on categories defined a priori (before the video/audio is recorded), and that b) Think Aloud does not work out of phase with the change action (thinking aloud after doing the task). This concerns me as a) I don't have a set of codes yet (I could certainly come up with some rather quickly, but they would be without significant justification), and b) I kind of liked the idea of the post-task interview.
These concerns aside, the data analysis in this paper is excellent. The authors code all the transcripts, and derive a set of patterns that the participants take while performing the tasks. These are formulated as finite state machines, in which each state represents a code. This, to me, validates their choice of codes. This may be a good model to follow for at least part of my analysis procedure.

Nielsen's Heuristics for Software Testing

I had a quick conversation today with Dustin, of DGP and MSR fame, and he asked me if there was anything similar to Nielsen's heuristics for usability that might be used when looking for errors in code. There wasn't anything that jumped to my mind, but that certainly doesn't mean that nothing in fact exists. However, the first 10 hits for "software testing heuristics", "nielsen heuristics code", "nielsen heuristics software testing errors" didn't contain what I was looking for, either. It makes me think that the imagined output from my research study could be a valid contribution to knowledge. I think the list would probably contain things like:

• always try negative numbered parameters
• always try null values
• how well does the .equals() method work?
• add-remove-add to/from the collection, is it the same semantically?
• always check date-based roll-overs
  

Simple Web Services are Too Hard to Find

So I'm building some software to use as a System Under Test for my thesis experiment, and found several seminal examples in Paul Jorgensen's "Software Testing". Since I had already implemented the Simple ATM problem (well, a variant of it, without any GUI), and the Triangle problem, I decided that the Currency Exchange problem might fit well in between these two, in terms of complexity and size of code. Basically, the program takes in a value and source currency, and converts it to a destination currency of your choice (4 options in Jorgensen's text). This seemed a bit outdated to me, as it relies on the programmer hard-coding the exchange rates by hand. Boo-urns, I say! So, I figured I'd use some benevolent, free web service to pull down live exchange rates and use them in my program. This should be simple, I imagine, because a) this is the type of service presented in every tutorial on making web services, and b) it provides exactly the type of functionality for which web services are suited: some mysterious online entity that has a little glob of information that I want to use in my application. Google searching for such a web service turned up a disappointing lack of results. There are several online currency converters, of which I'm sure the reader is aware, but none of those are particularly machine friendly - I would have to hack up and throw away a bunch of HTML to get a single number out of the page. I encountered one service that was designed to be machine readable, but it used the bloated WS* XML web service stack, requiring me to auto-generate hundreds of lines of code, all so that I can read a single number (this is not an option for me, because I don't want my subjects attempting to write tests for a bunch of machine created JAX-WS goop). If that wasn't enough, I also had to apply for a Trial API Key which would allow me to access the single number I needed for a period of two weeks, after which I would need to purchase a commercial API license. Grrrrrrr! A subsequent search of "REST currency exchange web service" turned up bupkiss. Why is this so hard? There should be dozens of services like this. Maybe I'm just not looking in the right place.

Idea for a Meta-Study

Idea for a meta-study: lots of papers have been published in which a controlled experiment is performed to examine the potential benefits of TDD. These are mostly all of the flavor: have control group implement some spec, using code-first-test-last, have experimental group implement same spec using TDD, measure time to complete and defect count of both groups. It seems (at least in my experience), that there are two possible outcomes from this, either the results are inconclusive, or they tend slightly towards the author's own feelings on the subject, either for or against TDD. I think an interesting, and probably easy to conduct, meta-study would be to pull down copies of all papers that are performing studies like these and see what the trend is, as well as analyzing things like geographic region of the authors or other relevant, although maybe not immediately obvious, correlations.

Iteratvie Thesis Development

Yesterday I decided to try a new way of organizing my time. In 'the real world', summer time always correlated with reduced productivity of a development team, in part due to developers taking vacation time, but also supervisors being absent and leaving the team with a lack of direction. I have proactively given myself this direction by dividing my summer into 3 iterations, which coincide with the three remaining months of the season. In each iteration, there are four phases, in which I will examine and refine the methodology, data acquisition, and analysis of this thesis I'm pursuing, and in the 4th phase I will write up my results. I figure that by doing three iterations in this way, the pilot study this summer should give me a really good idea on how to run a successful study in the fall, as well as a head start on some of the write-up.

A User Study for Mutation-based Testing Analysis

I recently read some material by Andreas Zeller in which he discusses the merits of using mutation testing as a method of verifying the quality of a test suite for a piece of software. These methods are meant to expose tests which perform an action, and assume that it was performed properly so long as an error is not thrown by the system under test - they do not verify that the action resulted in the desired program state. Code mutation (either on source or directly on the bytecode), when combined with accurate code coverage data, can identifiy these deficient tests by mutating the code they cover and observing tests that do not fail.

I believe that there is value in using this data, if it can be presented in the appropriate manner. If a developer has to spend an hour to generate the mutation report and cross-reference it with code coverage, then the investment likely outweighs the benefit. However, if I can arrive at my desk at 9am, and have in my inbox a build report, test report with coverage, and a mutation report for every branch, all of which are properly hyperlinked to each other and backed up on a central storage, then I would certainly use it. The problem here seems to be that this degree of automation and integration is hard to set up, and often times delicate when in place. It seems that some sort of standard platform for use by build engineers for integrating all of their reports, packaging operations, tests, etc, is called for. However, I have yet to see anything more sophisticated than Ant or Perl in widespread use by engineers. Maybe I just have an unrepresentative sample, though.

Testing Heuristics and Static Analysis at ICSE 09

I had a very critical talk with two grad students from Queen's yesterday, whom I unfortunately can only identify as Jackie and Brahm. They had a difficult time accepting the immediate usefulness/significance of the study I was proposing, and that's fine, as they came up with a few useful suggestions that I can leverage, primarily to keep a narrow focus and always be aware of the result I'm trying to generate. Two interesting opinions they shared with me are below:

Are the good testers simply those who are most familiar with the SUT (software under test)? This seems entirely plausable (in my own work experience, I was a vastly better tester of sotware that I had written, or at least software written by someone on my team). If so, then the correlation between programming experience and software testing would be much weaker if we are inventing the SUT for our subjects to test. However, I believe to have some empirical evidence to the contrary, in the form of a man called Scott Tindal, who is one of the most skilled QA engineers I've ever had the pleasure of working with. Scott was of the caliber that he could almost single-handedly test every product in the OpenText/Hummingbird line. An interesting configuration of our study may be to experiment with developers testing their own code versus devlopers testing new code that they've never seen before.

Will the heuristics extracted with this study be the same as those already in use by static analysis tools like FindBugs?
It appears that determining a correlation between the techniques that experienced testers use and the heuristics employed by static analysis tools such as FindBugs could be an interesting topic. If there is no correlation between these two, may it be possible to integrate these into SA suites for any significant improvement? If there is a correlation, why haven't more testers adopted static analysis to aid in their efforts? Is it a matter of usability of SA tools? Is it that the formalism used to express the SA heuristics isn't understood by everyday testers, and so they aren't aware of what SA has to offer? I plan to talk to Nathaniel Ayewah, University of Maryland, who is working on the FindBugs team, about this further.

ICSE 09 - Day Three

Andreas Zeller, professor at Saarland University in Germany, apart from being on of the nicest people I've met so far this week, also had some very positive feedback on my research idea. He agreed with it's principle, and that research in this area would be valid. One of his first questions after I finished presenting my idea was about incentive for participation. I thought he was asking about how we would convince students and pros to give up their time to participate in our study, but this wasn't the case. he recounted results found at Saarland when teaching students to test their code. Traditional methods obviously didn't work effectively, so they switched tracks. Student assignments were assigned with a spec and a suite of unit tests that the students could use to validate their work as they progressed. Once nightly a second set of tests were run by the instructor, the source of which was kept secret, and the students were informed in the morning of the number of tests they passed and failed. To grade the assignment, a third set of (secret) tests were run. Students begin with a mark of 100%. The first failing test reduces their mark to 80%. The second, to 70%. The third to 60%. The grading continues in a similarly harsh fashion. The first assignment in the course is almost universally failed, as students drastically underestimate how thorough they need to be with their tests. Subsequent assignments are much better, and the students focus strongly on testing, and indeed collaborate by sharing test cases and testing each others assignments to eliminate as many errors as possible before the submission date. Once the students have the proper motivation to test, they eagerly consume any instruction in effective testing techniques. Andreas found that simple instruction in JUnit and maybe TDD was all that was required, and the rest the students figured out for themselves. This type of self-directed learning is encouraging, but the whole situation makes me think that these students may be working harder, but not smarter, to test their software. It may be possible that by providing instruction not only in the simple operation of an XUnit framework, but also in things like effective test case selection, they may be able to reach similar test coverage or defect discovery rates, while expending less frantic effort.
Thought: drop the first assignment from the course's final mark, as it is not used for evaluation as much as it is a learning experience (of course, don't tell the students this, otherwise the important motivational lesson will be lost).
In addition to this, Andreas, just as other folks I've spoken to so far, emphasized the need to keep my study narrowly focused on a single issue, as well as controlling the situation in a way that enables precise measurements to be made both before and after implementing the curriculum changes we hope to elicit from the study, to accurately determine the improvements (if any exist). I am beginning to see a loose correlation between a researcher's viewpoint regarding empiricism in SE research (positivist on the right and constructivist on the left) and their amount of emphasis on narrowness of focus. Often times, those people who advocate exploratory qualitative studies also recommend wider bands of observation while conducting these studies. This is likely an over generalization, and I apologize in advance to anyone who may disagree with this.

ICSE 09 - Day Two

Day Three of ICSE 09 was another great success! It began with a rousing keynote by Tom Ball of Microsoft Research fame. He described the early beginnings of version control and the emergence of mining techniques for these version systems, and continued the narrative through to the latest version of visual studio and the tool Microsoft calls CRANE, which suggests to developers area of the code which should be examined given that they are changing some other area. Pretty cool. I got to talk to him one-on-one about it over lunch.

On the previously blogged march through stanley park, I had a talk with Tom Ostrand from AT&T Labs in New Jersey. One thing I wanted to talk about (besides pitching my research idea) was leveraging the version history and reports generated from a test suite to predict bugs in target code using MSR techniques to augment the existing tools, such as mining deltas and bug trackers. This topic came up in the morning's MSR session, but aparently Tom missed it (making me look much smarter than can be measured in reality). He seemed interested in the possibility, but of course there are barriers to getting it going. Primarily, assuming that the dev team for the software we're analyzing is writing tests and putting them into the vcs, the error and coverage reports almost certainly aren't, making it difficult to to versioned history analysis over them. I thought that maybe, given the source code of the target software and the test code (both of which at some version), the MSR tool could build the code and execute the tests to create the needed reports. This will likely be extremely difficult to get going in the field, however, and make MSR mining, which is already an extremely expensive, long running process, even slower.

Farewell to the Borkenstocks

The time has finally come to retire the Canadian Tire brand cork bottomed sandals, so lovingly referred to as the 'Borkenstocks'. After a season in the closet and a plane ride to Vancouver, the sandals got their first taste of summer today, as they accompanied me on a walk through Stanley Park. The results of this were as follows: blisters and uncomfortableness.

Feedback on my Research Proposal

Over the last 24 hours I've had the chance to talk to a few individuals about my research idea. It seems to go as follows: I give my 30 second pitch, the marks stares at me blankly. Then, I elaborate. The mark gets it. They tell me first a problem they see, and then what they'd like to see out of the results. In a couple of cases, the mark got particularly excited about the outcome. I've summarized below.

Chris Bird
Chris has a strong background in empirical software engineering, with particular emphasis on qualitative exploratory studies. As such, the quantitative analysis aspects of my pitch fell on deaf ears, but he was extremely interested in the in-lab observation sessions I was proposing. He felt that 5 or 6 actionable recommendations that might come out of observing professionals would be invaluable. He suggested that I find an older Microsoft Research study in which they trained new hires by having them monitor a screen shared by a senior developer for some amount of time (probably a few days), and had the new hire ask questions with the senior at a later date, by reviewing the video logs. I like this idea because it allows us to elicit the information from the developer directly, instead of trying to infer it ourselves, but since we're not bothering them during the initial testing session, we wouldn't be affecting their performance. This isn't without problems, though. Primarily, there is the risk that the subject isn't always sure why they do the things they do, and so are likely to invent reasons, or invent foresight where none necessarily exists. Interesting idea, though. Also, should we interview students in the same way? On one hand, they students likely don't have any special insights that we can leverage (assuming they are less effective at testing than pros). On the other hand, it may illuminate any areas of misconception or misunderstanding which we could address in future curriculum changes.

Jim Cordy
Jim is a professor at Queens, and was my instructor in my 4th year compilers course. After he heard my pitch, he had a warning about an affect he had seen in his industrial work, and it comes from a generational difference in the training of developers. Developers who were trained more than 15 or 20 years ago had a delay between changing the source code and the results of program execution on the order of hours; new developers are used to delays on the order of minutes. Also, the current state of the art in debugging utilizes interactive debuggers, which were either unavailable or unreliable in earlier days. This has lead to 'old-school' programmers to a) rely heavily on source code inspection and b) insert enormous amounts of instrumentation (debugging statements) when running the program becomes required. In comparison, new generation developers often use smaller amounts of instrumentation, relying on quick turn around times to find the cause of errors. In Jim's experience, the old school programmers were orders of magnitude more effective (in terms of bugs found or solved per hour) than younger programmers. If this is in fact the case, it should be an effect we can see if we recruit subjects trained during this era of computer science research.

ICSE 09 - Day One

We're wrapping up the first day of talks here at ICSE 2009. I've talked my way into the Mining Software Repositories (MSR) workshop. Here's a quick breakdown of some noteworthy points:

Keynote: Dr. Michael McAllister, Director of Academic Research Centers for SAP Business Objects
An hour and a half long talk in which he sells BI to the masses. Spoke a lot about integrating data silos, and providing an integrated, unified view of the data to business level decision makers. Also interesting anicdotes on how BI helped cure SARS. Forgot what OLAP stands for. Kind of concerning. This talk made me (after spending 2+ years working for a BI company) want a running example of what BI is and how it is used in the context of an expanding organization - from the point before any computational logistics assistance is required, and progressing forward to a Wallmart sized operation. Most examples I've seen start with a huge complex organization, complete with established silos, and then installs things like supply chain management, repository abstraction, customer relations management, document management, etc.


Mining GIT Repositories - presented the difficulties in mining data out of GIT (or DVCS systems in general) as opposed to traditional centralized systems like svn. Noteworthy items include high degree of branching and the lack of a 'mainline' of development.

Universal VCS - by looking for identical files in the repos of different projects, a single unified version control view is established for nearly all available software. Developed by creating a spider program which crawled the repos of numerous projects, downloading metadata and inferring links where appropriate.

Map Reduce - blah blah blah use idle PCs for quick pluggable clustering to chuck away on map reduce problems. Look @ Google MapReduce and Hardoop.

Alitheei Core - A software engineering research platform. Plugin framework for performing operations on heterogeneous repositories. Can define a new Metric by implementing an interface, and then evaluate the metric against all repositories in the framework. Look @ SQO OSS.

Many of these previous talks created tools for mining repositories, but with no greater purpose than that. When asked about this ('mining for the sake of mining'), none of the authors seemed to have a problem. The conclusion of the discussion was that this lack of purpose was a problem, and that the professional community should be surveyed to find out what needs they have for mining repos.

Research extensions/ideas:
The third MSR session today focused heavily on defect prediction. After showing off 3 or 4 methods of mining vcs systems to predict buggy code that improved prediction probability by 4% or 5%, the discussion boiled down to this, "What do managers/developers want in these reports to help them do their jobs?" Obviously, the room full of academics didn't have a definitive answer. One gentleman asked the question I had written down, which was "has anyone used the history and coverage of a software's test suite in combination with data from the VCS as a defect predictor (in theory, heavily tested areas are less likely to contain bugs)?" I found this particularly interesting. Also, I began to wonder, if we had one of these defect prediction reports, does it improve a developer's ability to find bugs, and if so, to what extent? Would it be measurable in the same way as I intend to measure testing ability with students and professionals?

Stay tuned for more info (and pictures of beautiful vancouver)!