Property-based Testing mit JUnit QuickCheck

Inhaltsverzeichnis

Die Definition konkreter Testfälle ist eine zentrale Aufgabe beim Entwickeln von Unit-Tests. Doch sie ist auch sehr zeitaufwändig und trotzdem häufig unvollständig. Kann also nicht besser ein Framework viele zufällige Werte für die Tests generieren? Und wenn ja, wie sehen dann die Tests aus? Bei der Antwort soll eine Gegenüberstellung des klassischen Vorgehens auf Basis definierter Beispielwerte und der Idee des Property-based Testing helfen, das auf zufällig generierten Testfällen basiert. Da Letzteres sich nicht für alle zu testenden Algorithmen eignet, sollen konkrete Beispiele den Einsatz illustrieren. Der gesamte Code ist bei GitHub verfügbar

Nachteile des klassischen Testverfahrens

Unit-Tests gehören heute zum guten Ton bei der Softwareentwicklung. Viele Entwickler setzen sogar auf Test Driven Development (TDD) und schreiben ihre Tests vor dem Produktivcode. Ein Beispiel für einen mit TDD entwickelten einfachen Algorithmus zeigt das folgende Listing. Aufgabe ist die Zerlegung von Zahlen in ihre Primfaktoren. Jede natürliche Zahl lässt sich als eindeutiges Produkt aus Primzahlen darstellen, beispielsweise die Zahl 30 als Produkt der Zahlen 2, 3 und 5. Für 27 wäre die Zerlegung 3, 3 und 3.

public List<Long> factor(Long i)
{
  List<Long> primeFactors = new ArrayList<>();
  long divisor = 1;
  double squareRoot = Math.sqrt(i);
  while (i > 1)
  {
    divisor++;
    while (i % divisor == 0)
    {
      primeFactors.add(divisor);
      i /= divisor;
    }
    if (divisor > squareRoot)
    {
      divisor = i - 1;
    }
  }
  return primeFactors;
}

Der eigentliche Algorithmus ist nicht allzu komplex und schnell programmiert. Der Code ist sogar ein wenig auf Performance optimiert. Einige Tests, die nötig waren, um diesen Algorithmus Schritt für Schritt zu entwickeln, zeigt der folgende Code:

public class PrimeFactorCalculatorShould
{
  private PrimeFactorCalculator sut; // system under test

  @BeforeEach
  public void setup()
  {
    sut = new PrimeFactorCalculator();
  }

  @Test
  public void factor2()
  {
    assertThat(sut.factor(2L)).isEqualTo(Arrays.asList(2L));
  }
  @Test
  public void factor3()
  {
    assertThat(sut.factor(3L)).isEqualTo(Arrays.asList(3L));
  }

  @Test
  public void factor4()
  {
    assertThat(sut.factor(4L)).isEqualTo(Arrays.asList(2L, 2L));
  }

  @Test
  public void factor5()
  {
     assertThat(sut.factor(5L)).isEqualTo(Arrays.asList(5L));
  }
}

Wie es bei TDD üblich ist, startet der Vorgang mit dem einfachsten Wert (in diesem Fall 2). Dann folgen weitere Tests (3, 4, ... ), um den Algorithmus zu vervollständigen. Das gezeigte Vorgehen hat zwei Nachteile. Zum einen entstehen ziemlich viele sehr ähnliche Testmethoden (factor2(), factor3(), ... ). Jedes Mal ruft der Vorgang die zu testende Methode factor() auf und vergleicht das Ergebnis mit der jeweils erwarteten Liste. Nur die konkreten Werte unterscheiden sich bei jedem Aufruf. Es gibt somit einige Redundanzen in den Tests.

Des Weiteren können Entwickler nicht sicher sein, ob sie vielleicht bestimmte Testfälle vergessen haben. Insbesondere Sonderfälle oder Grenzwerte sind äußerst interessant. Die Tests sollten ja nicht nur die positiven Fälle abdecken, die sich ohne Weiteres zerlegen lassen, sondern gerade die Werte, die eventuell Probleme bereiten, dürfen nicht fehlen. Hierbei sind Entwickler auf sich gestellt: Niemand gibt ihnen die zu testenden Werte vor, sondern sie müssen sie sich üblicherweise selbsttätig überlegen. Je nach Situation könnte allerdings der Fachbereich Testwerte definieren.

Vermeiden von Redundanzen und Testen zufälliger Werte

Das erste Problem – die Redundanz in den Tests – können moderne Unit-Test-Frameworks lösen. Für Java bietet beispielsweise JUnit seit Version 5 eine einfache Vorgehensweise zum Erzeugen parametrisierter Tests. Folgender Code zeigt ein Beispiel für die obigen Tests in Form eines parametrisierten Tests:

@ParameterizedTest(name = "{0} should be factored as [{1}]")
@CsvSource(
{
  "2, 2",
  "3, 3",
  "4, 2;2",
  "5, 5" })

public void factorSmallNumbers(long n, String factors)
{
  assertThat(sut.factor(n)).isEqualTo(split(factors));
}

Statt den eigentlichen Test mehrfach zu entwickeln, übergibt der Code einer einzigen Testmethode mehrere Parameterkombinationen, die das Unit-Test-Framework einzeln und isoliert von den anderen ausführt.

Das zweite Problem – die Definition der Testfälle – ist jedoch deutlich schwieriger zu lösen. Einen ersten Versuch zeigt folgender Code, der statt eines konkreten Eingangswertes eine Zufallszahl zerlegt:

@Test
public void factorRandomNumber()
{
  Long randomNumber = new Random().nextLong();
  List<Long> expectedPrimeFactors = 
    Arrays.asList(???); // Was wird hier erwartet?
  assertThat(sut.factor(randomNumber))
    .isEqualTo(expectedPrimeFactors);
}

Das Problem ist nun allerdings, dass das zu erwartende Ergebnis unbekannt ist, da die zufällige Zahl in zufällige Primfaktoren zerlegt wird. Wie soll nun ein Test dieser Aufteilung aussehen?

Offensichtlich ist es nicht möglich, mit zufälligen Werten wie gewohnt zu testen. Anstatt erwartete Ergebnisse vorzugeben und Assertions gegen diese durchzuführen, muss sich die Art des Testens verändern. Entwickler können keine konkreten Beispielwerte für den Test verwenden, sondern müssen allgemeingültige Eigenschaften des zu testenden Algorithmus prüfen. Ersteres Vorgehen wird im weiteren Verlauf als "Example-based Testing" (EBT) und letzteres als "Property-based Testing" (PBT) bezeichnet.

Testen allgemeiner Eigenschaften von Algorithmen

Im Beispiel der Primfaktorzerlegung wäre eine allgemeine Eigenschaft der Ergebnisliste, dass das Produkt der einzelnen Elemente der Liste wieder die ursprüngliche Zahl ergeben muss. Diese Eigenschaft muss für alle Beispielwerte gelten, egal wie groß oder klein sie sind. Einen denkbaren Testfall auf Basis zufälliger Werte zeigt folgender erster Property-based Test mit JUnit-Quickcheck:

@RunWith(JUnitQuickcheck.class)
public class PrimeFactorCalculatorProperties
{
  private PrimeFactorCalculator sut;

  @Before
  public void setup()
  {
    sut = new PrimeFactorCalculator();
  }

  @Property
  public void productOfPrimeFactorsShouldBeTheOriginalNumber(
    @InRange(min = "2", max = "9999999999999") Long i)
  {
    assertThat(sut.factor(i).stream()
      .reduce(1L, (a, b) -> a * b))
      .isEqualTo(i);
  }
    
  @Property
  public void primeFactorsShouldBePrimeNumbers(
    @InRange(min = "2", max = "9999999999999") Long i)
  {
    sut.factor(i).stream()
      .forEach(primeFactor -> assertThat(sut.isPrime(primeFactor))
      .as("factor " + primeFactor + " should be a prime number")
      .isTrue());
  }
}

Die Testmethode productOfPrimeFactorsShouldBeTheOriginalNumber() ist als @Property annotiert, und den Parameter i generiert das Framework automatisch zufällig. @InRange beschränkt den Wertebereich im Code auf positive Zahlen zwischen 2 und 9999999999999 (eine möglichst große Zahl, für die der Algorithmus noch einigermaßen performant läuft), da sich nur natürliche Zahlen zerlegen lassen. Der eigentliche Test reduziert die Ergebnisliste auf das Produkt ihrer Elemente und vergleicht es mit der Eingangszahl. Ein zweiter Test könnte sein, dass alle Zahlen in der Ergebnismenge Primzahlen sein müssen. Das überprüft die Testmethode primeFactorsShouldBePrimeNumbers().

Wenn der Algorithmus nun fälschlicherweise einfach nur eine Liste mit der Eingangszahl selbst zurückliefern würde, statt die tatsächliche Zerlegung durchzuführen, sähe ein Fehlschlag für den zufällig generierten Wert 205538718029 aus, wie in Abbildung 1 gezeigt.

PBT-Frameworks und ihre Features

Sobald Entwickler allgemeine Eigenschaften für ihren Algorithmus gefunden haben, können sie sich durch ein Framework beliebige Zufallswerte generieren lassen und damit den Algorithmus testen. Die Beispiele in diesem Artikel basieren auf JUnit-Quickcheck, sind aber sicherlich mit anderen Frameworks ebenso umsetzbar, von denen zahlreiche für verschiedene Programmiersprachen existieren. Auch wenn die Idee von PBT ursprünglich aus der funktionalen Programmierung stammt und mit QuickCheck in Haskell das erste Framework erschien, ist es durchaus möglich, auch in anderen Programmiersprachen dieses Vorgehen beim Testen anzuwenden. Die Frameworks sind recht ausgereift und bereit für den produktiven Einsatz. Folgende Liste zeigt einen Ausschnitt der Produkte für verbreitete Plattformen.

• Java: JUnit-Quickcheck: Property-based-Testing im Stil von JUnit
• .NET: FsCheck: Random Testing
• JavaScript: JSVerify: Property-based Testing ähnlich zu QuickCheck
• Ruby: rubycheck: Eine Portierung des QuickCheck-Unit-Test-Frameworks
• PHP: PhpQuickCheck: Generatives Testing
• Scala: ScalaCheck: Property-based Testing
• Haskell: QuickCheck: Automatisches spezifikationsbasiertes Testing

Viele Frameworks haben Funktionen, die die Arbeit mit PBT in der Praxis erleichtern. Eine zentrale ist das sogenannte "Shrinking": Stellt das Framework fest, dass ein Test fehlschlägt, versucht es selbstständig, die zum Fehlschlag führenden Argumente beispielsweise durch Dekrementieren einer Zahl so weit zu reduzieren, bis es den einfachsten Fall findet, für den der Test fehlschlägt. So erkennt es insbesondere Grenzwerte relativ schnell. In Abbildung 1 ist dieser Vorgang zu erkennen: Das Framework verringert den ursprünglich generierten Wert 205538718029 solange, bis es den ersten Fall findet, der den Test fehlschlagen lässt. Im Beispiel ist das die 4 (Shrunken args: [4]), da sie die erste Zahl nach 2 und 3 ist, die nicht nur sich selbst als Primfaktor enthalten dürfte.

Freilich lassen sich zufällige Werte für die wichtigsten Datentypen der jeweiligen Programmiersprache (z. B. int, String, ArrayList in Java) generieren. Und zusätzlich gibt es wie gezeigt die Möglichkeit, Wertebereiche einzuschränken. Aber auch andere Eigenschaften der Testwerte lassen sich als Voraussetzung bestimmen – beispielsweise, dass eine Zufallszahl gerade sein muss oder ein String eine bestimmte Mindestlänge hat.

Um bei einem Fehlschlag die Fehlerursache schneller finden zu können, lassen sich Tests reproduzierbar durchführen. Dazu können Entwickler sogenannte Seeds vorgeben, auf denen die erzeugten (Pseudo-)Zufallswerte basieren. Das Framework gibt bei jedem Testlauf die verwendeten Seeds aus, anhand derer Entwickler den Lauf exakt nachstellen können.

Der folgende Code zeigt einen Test mit explizit aktiviertem Shrinking, der Vorgabe eines konkreten Seed (-6527596145222155897 aus Abbildung 1) für die Zufallswerte und der Einschränkung, dass die generierten Zahlen gerade (also teilbar durch 2) sein müssen:

@Property(maxShrinkDepth = 100, maxShrinks = 1000)
public void primeFactorsForEvenNumbersShouldContain2(
  @InRange(min = "2", max = "9999999999999")
  @When(seed = -6527596145222155897L)
  Long i)
{
  assumeThat(i % 2, is(0L));
  assertThat(sut.factor(i)).contains(2L);
}