Bestimmung wahrscheinlicher Ursachen des Scheiterns von Unit-Tests

Diesen Monat wurde mein Buch mit meiner Abschlussarbeit veröffentlicht. Erschienen ist es unter dem Titel “Bestimmung wahrscheinlicher Ursachen des Scheiterns von Unit-Tests” mit der ISBN 3639139119. Kaufen kann man es in jedem Buchladen oder z.B. bei bookzilla.de wo man mit seinem Kauf noch freie Software unterstützt.

Advertisements

My camera ready bachelor thesis.

I ended my thesis on 2008-05-05. The thesis has the title: “Integration und Evaluation von Verfahren zur Bestimmung wahrscheinlicher Ursachen des Scheiterns von Unit-Tests in Eclipse”. It is written in german. But there is a paper with the title “Towards Raising the Failure of Unit Tests to the Level of Compiler-Reported Errors” (in the book “Objects, Components, Models and Patterns” or for download only the paper as pdf) which was hold in July 2008 on the Tools Europe 2008 conference which is in english and contains some of the material from my thesis.

Eclipse Test & Performance Tools Platform Project troubles

After using TPTP for about a half year for my bachelor I am at a point where I would remove it. But I don’t have to decide it. I reported so far 6 bugs. Everyone of them detains me on profiling. I can create single traces but if I repeat tracing I am in trouble. JVM crashes, 100% CPU usages and so on. I have now written my own “profiler” two classes that give me the covered lines back of a profiled program. It uses the Java debugging interface (JDI).

The first class is called Agent that starts a event catcher thread (the debugging agent) if it is called without any arguments. This debugging agent waits for a connecting JVM. With a argument it calls a sample method to test profiling. You have to supply the debugging agent port and host like -agentlib:jdwp=transport=dt_socket,suspend=y,address=localhost:55555. The other class is EventCatcherThread which enables the single step event and waits for a connecting JVM to profile a program. Only 278 lines of java code are necessary.

Agent.java

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.sun.jdi.connect.IllegalConnectorArgumentsException;
import com.sun.jdi.connect.VMStartException;

public class Agent {

	private ArrayList<String> _linesPassed = new ArrayList<String>();

	public void addSourceCodeLine() {
		_linesPassed.add("bla");
	}

	public List<String> getLinesPassed() {
		return _linesPassed;
	}

	public static void debug() throws Exception {
		List<String> passedLine = new ArrayList<String>();
		EventCatcherThread eventThread = EventCatcherThread.connectToVm(55555);
		eventThread.setPassedCodeLines(passedLine);
		eventThread.start();
		eventThread.resumeVM();
		eventThread.join();

		for (Iterator<String> iterator = passedLine.iterator(); iterator
				.hasNext();) {
			String lineKey = (String) iterator.next();
			System.out.println(lineKey);
		}
	}

	public static void main(String[] args) throws Exception,
			IllegalConnectorArgumentsException, VMStartException {
		if (args.length != 0) {
			debug();
		} else {
			Agent agent = new Agent();
			agent.traceTest();
		}
	}

	public void traceTest() {
		String string = new String();
		string = string + " fdgvdf ";
		string = string.concat("bla");
		System.out.println(string);
	}
}

EventCatcherThread.java

package org.projectory.ezunit;

import java.io.IOException;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.eclipse.jdi.Bootstrap;

import com.sun.jdi.AbsentInformationException;
import com.sun.jdi.ThreadReference;
import com.sun.jdi.VMDisconnectedException;
import com.sun.jdi.VirtualMachine;
import com.sun.jdi.connect.AttachingConnector;
import com.sun.jdi.connect.IllegalConnectorArgumentsException;
import com.sun.jdi.connect.Connector.Argument;
import com.sun.jdi.event.Event;
import com.sun.jdi.event.EventIterator;
import com.sun.jdi.event.EventQueue;
import com.sun.jdi.event.EventSet;
import com.sun.jdi.event.StepEvent;
import com.sun.jdi.event.VMDeathEvent;
import com.sun.jdi.event.VMDisconnectEvent;
import com.sun.jdi.event.VMStartEvent;
import com.sun.jdi.request.EventRequest;
import com.sun.jdi.request.EventRequestManager;
import com.sun.jdi.request.StepRequest;

public class EventCatcherThread extends Thread {

	private final VirtualMachine _vm;

	private String[] _excludes;

	private boolean _connected = true;

	private String[] _includes;

	private Map<String, Location> _lineStat = new HashMap<String, Location>();

	private List<String> _passedCodeLines;

	EventCatcherThread(VirtualMachine vm, String[] excludes, String[] includes) {
		super("event-handler");
		_vm = vm;
		_excludes = excludes;
		_includes = includes;
	}

	public void run() {
		EventQueue queue = _vm.eventQueue();
		List<ThreadReference> allThreads = _vm.allThreads();
		for (ThreadReference thread : allThreads) {
			if (thread.uniqueID() == 1) {
				enableSingleStepEvent(thread);
			}
		}

		while (_connected) {
			try {
				EventSet eventSet = queue.remove();
				EventIterator it = eventSet.eventIterator();
				while (it.hasNext()) {
					Event nextEvent = it.nextEvent();
					handleEvent(nextEvent);
				}
				eventSet.resume();
			} catch (InterruptedException exc) {
				// Ignore
			} catch (VMDisconnectedException discExc) {
				handleDisconnectedException();
				break;
			}
		}
	}

	private void enableSingleStepEvent(ThreadReference thread) {
		EventRequestManager mgr = _vm.eventRequestManager();
		StepRequest req = mgr.createStepRequest(thread, StepRequest.STEP_LINE,
				StepRequest.STEP_INTO);
		req.setSuspendPolicy(EventRequest.SUSPEND_EVENT_THREAD);
		for (int i = 0; i < _excludes.length; ++i) {
			req.addClassExclusionFilter(_excludes[i]);
		}
		for (int i = 0; i < _includes.length; ++i) {
			req.addClassFilter(_includes[i]);
		}
		req.enable();
	}

	private void singleStepEvent(StepEvent event) {
		if (_passedCodeLines != null) {
			try {
				final String sourcePath = event.location().sourcePath();
				final int lineNumber = event.location().lineNumber();
				final String method = event.location().method().toString();
				final String lineKey = sourcePath + ":" + method  + ":" + lineNumber;
				if (_lineStat.containsKey(lineKey)) {
					Location location = _lineStat.get(lineKey);
					location.countCall();
				} else {
					Location location = new Location(sourcePath, method, lineNumber);
					location.countCall();
					_lineStat.put(lineKey, location);
				}
				if (!_passedCodeLines.contains(lineKey)) {
					_passedCodeLines.add(lineKey);
				}
			} catch (AbsentInformationException e) {
				e.printStackTrace();
			}
		} else {
			System.err
					.println("Cannot set line numbers, because the container is null!");
		}
	}

	/**
	 * Dispatch incoming events
	 */
	private void handleEvent(Event event) {
		if (event instanceof StepEvent) {
			singleStepEvent((StepEvent) event);
		} else if (event instanceof VMStartEvent) {
			vmStartEvent((VMStartEvent) event);
		} else if (event instanceof VMDisconnectEvent) {
			vmDisconnectEvent((VMDisconnectEvent) event);
		} else if (event instanceof VMDeathEvent) {
			// application exit
		} else {
			System.out.println("Unhandled event type: " + event.getClass());
		}
	}

	private void handleDisconnectedException() {
		EventQueue queue = _vm.eventQueue();
		while (_connected) {
			try {
				EventSet eventSet = queue.remove();
				EventIterator iter = eventSet.eventIterator();
				while (iter.hasNext()) {
					Event event = iter.nextEvent();
					if (event instanceof VMDisconnectEvent) {
						vmDisconnectEvent((VMDisconnectEvent) event);
					}
				}
				eventSet.resume();
			} catch (InterruptedException exc) {
				// ignore
			}
		}
	}

	/**
	 * Enable the SingleStepEvent if the VM was started in suspend mode.
	 * @param event
	 */
	private void vmStartEvent(VMStartEvent event) {
		EventRequestManager mgr = _vm.eventRequestManager();
		StepRequest req = mgr.createStepRequest(event.thread(),
				StepRequest.STEP_LINE, StepRequest.STEP_INTO);
		req.setSuspendPolicy(EventRequest.SUSPEND_EVENT_THREAD);
		for (int i = 0; i < _excludes.length; ++i) {
			req.addClassExclusionFilter(_excludes[i]);
		}
		for (int i = 0; i < _includes.length; ++i) {
			req.addClassFilter(_includes[i]);
		}
		req.enable();
	}

	private void vmDisconnectEvent(VMDisconnectEvent event) {
		_connected = false;
	}

	@SuppressWarnings("unchecked")
	public static EventCatcherThread connectToVm(int port) throws Error,
			IOException, InterruptedException,
			IllegalConnectorArgumentsException {
		AttachingConnector c = getConnector();
		Map<String, Argument> arguments = c.defaultArguments();
		Argument portArg = arguments.get("port");
		portArg.setValue("" + port);
		// FIXME: localhost doesn't work
		Argument hostArg = arguments.get("hostname");
		hostArg.setValue("elaste");
		VirtualMachine myVM = c.attach(arguments);
		myVM.setDebugTraceMode(0);
		final String[] excludes = { "org.hibernate.*", "net.sf.cglib.*",
				"org.junit.*", "java.*", "javax.*", "sun.*", "com.sun.*" };
		final String[] includes = { };
		EventCatcherThread eventThread = new EventCatcherThread(myVM, excludes,
				includes);

		return eventThread;
	}

	private static AttachingConnector getConnector() {
		AttachingConnector result = null;
		List<AttachingConnector> allConnectors = Bootstrap
				.virtualMachineManager().attachingConnectors();
		if (allConnectors.size() > 0) {
			result = allConnectors.get(0);
		}
		return result;
	}

	public void resumeVM() {
		_vm.resume();
	}

	public List<String> getPassedCodeLines() {
		return _passedCodeLines;
	}

	public void setPassedCodeLines(List<String> codeLines) {
		_passedCodeLines = codeLines;
	}

	public Location getLineStat(String lineKey) {
		return _lineStat.get(lineKey);
	}
}

Cyclomatic Complexity

Cyclomatic Complexity is added as a new approach to find methods that are possible failures. It is implemented in the way that McCabe describes it in its original paper on page 7 and 8. The cyclomatic complexity number is computed by counting all if, for and which statements of a method. For every if statement that contains a && 2 is add to the cyclomatic complexity.

Complex

The cyclomatic complexity doesn’t have a maximum value but the likelihood evaluator has to return a value between 0 and 1 including 0 and 1. To have a maximum for converting the cyclomatic complexity between 0 and 1 complexity values bigger than 10 are set to 10. This is the upper bound that McCabe terms in his paper on page 7.

Case statements

McCabe says in his paper on page 9: “The only situation in which this limit has seemed unreasonable is when a large number of independent cases followed a selection function (a large case statement), which was allowed.” To have a “reasonable” upper limit the case statements aren’t count.

Enhancements

To have a complete implementation of the cyclomatic complexity measurement the case statements should also be taken in account, but then it should be possible to configure the upper limit.

Automated evaluation

How to evaluate? First my colleagues should only test it. But my professor thought that this isn’t enough for an expressive and compareable result. So the idea is to set errors and start the evaluation when tests fail. And everything should work automatically. The user start it and after a month or so you have the result without any intervention by the user

Jesting

There exists a tool called Jester that changes the source code of programms and run the tests after every change. If no tests fail it will remember the position and what changed. With this procedure it is possible to find source code that isn’t well tested. But this isn’t exactly what we need. We need failed tests to test how good an evaluator finds the changed method.

EzUnit and Jester

The procedure is as follow. First we get all methods of a projects source folder from the Eclipse (JDT). Then we do one style of change, there are 11 variants of changing the source code, after each other for every method. These variants are taken from Jester. I will explain them later. Then the test suite is started. If compilation is necessary the launch waits for completion and continues thereafter. There are three cases after the test site launch. Junit can give an error back this means something not test specific goes wrong. In the case Junit returns with a failure the evaluation is started because thento reverse there are failed tests. The third case is that nothing failed after the change. Then there is nothing to evaluate like after an error and you know that there is bad tested code in the project. The next step is to take all made changes back. If all methods are changed with all variants of source code changes a csv file is written with all results in the project root folder.

Changing source code

Jester has 11 variant of changing source code. All are implemented by EzUnit. There is an number changer that searches for one digit and add 1 to it. This Jester implementation can lead to compilation errors because it changes an octal number representation from 0x … to 1x… If such a change happens it is ignored. The other methods replace java language constructs to reverse there meaning like “true” to “false”, “if (” to “if (true ||”, “if (” to “if (false &&”, “==” to “!=”, “!=” to “==”, “++” to “−−” and “−−” to “++”. Such changes can lead to endless loops. To avoid an ever blocking test the timeout annotation (@Test(timeout = 60000) for Junit4 should be used. But we saw also endless loops where the cause is unknown for now and where the setting of the timeout are not working. In this cases the launch has an timeout set so that it continues with another change.

The time

First tests show that a evaluation run can take very long dependent on the number of methods and tests a project has and the time for one test run. An evaluation run with commons-codec (191 tests) needs 4 hours on double processor with 1.66GHz and for commons-math (1022 tests) about 4 days.

Framework for calculation and presentation of likelihoods

My first addition to EzUnit is the implementation of a likelihood framework. Needed things are a view that displays the likelihood for a failure of a method, an extension point where different likelihood calculation methods can be added and some methods for calculating a likelihhod.

Likelihood calculation

I implemented four likelihood calculation methods. The first computes the quotient from the count of failures and the count of all calls of a method. The second calculates the test coverage of a method as the quotient from the count of all calls and the sum of all method calls. Then it calculates the failure likelihood and the passed likelihood as quotient from failures/passes and the count of all calls of a method. These three values are now taken to calculate the end likelihood in the following way. A difference is build from the failure and passed likelihood and this value is multiplied with the test coverage. This method should rate methods higher that are more tested. The third and the fourth are of the same type. They calculate a complexity of a method by there length in characters. In the one hand it is calculated the quotient from the length of method and the sum of the length of all methods and on the other hand it is calculated the quotient from a methods length and the length of the biggest method.

Displaying the result

The result is displayed as a tree. First comes the methods that have possible failures and under this methods there come the test name from where they called. Here it is defferenciated between failed and passed tests. Then it is displayed a overall likelihood and under this overall likelihood come all single likelihoods. The overall likelihood is calculated as the sum from all likelihoods. All single likelihoods go in this sum with the same weight.

Rate likelihood methods

To adjust the result you can vote or disable a likelihood method. A method should be voted if it helps to find the failure. The user has to decide when this is the case.

Eclipse Test & Performance Tools Platform Project

I had to try this Eclipse project out. On trying it I got every time the error that the profiler agent cannot be accessed, becaused it isn’t started. But I need this project running and had to find the problem. I use Eclipse 3.3 on Ubuntu Linux 7.04. First I find the scripts on starting the agent server in /eclipse/plugins/org.eclipse.tptp.platform.ac.linux_ia32_4.4.0.v200706020100/agent_controller/bin and found out that they are missing the execute rights. Then I started the script by hand ./ACStart.sh and get the following error [: 46: ==: unexpected operator. The solution is to set in the first line the interpreter to bash instead of sh, because Ubuntu uses a small replacment for the bash called dash. Again. Now I get a new error that’s saying libtptpUtils.so.4 needs /usr/lib/libstdc++-libc6.2-2.so.3. Where to get this library? After some web searching I found out that I had to install the following package libstdc++2.10-glibc2.2. Now the agent starts. Let’s start profiling.