Wie testet man Code mit Hilfe von Graphstrukturen?

Ich schreibe (rekursiven) Code, der in einem Abhängigkeitsdiagramm navigiert und nach Zyklen oder Widersprüchen in den Abhängigkeiten sucht. Ich bin mir jedoch nicht sicher, wie ich mit Unit-Tests umgehen soll. Das Problem ist, dass eines unserer Hauptprobleme darin besteht, dass der Code alle interessanten Diagrammstrukturen verarbeitet und sicherstellt, dass alle Knoten entsprechend behandelt werden.

Während in der Regel 100% Linien- oder Zweigabdeckung ausreichen, um sicher zu sein, dass ein Teil des Codes funktioniert, haben Sie trotz 100% Pfadabdeckung immer noch Zweifel.

Wie wählt man also Diagrammstrukturen für Testfälle aus, um sicherzugehen, dass ihr Code alle denkbaren Permutationen verarbeiten kann, die man in realen Daten findet?

PS: Wenn es darauf ankommt, sind alle Kanten in meinem Diagramm mit "muss haben" oder "kann nicht haben" gekennzeichnet und es gibt keine trivialen Zyklen, und es gibt nur eine Kante zwischen zwei Knoten.

PPS- Diese zusätzliche Problemstellung wurde ursprünglich vom Autor der Frage in einem Kommentar unten veröffentlicht:

For all vertices N in forest F, for all vertices M, in F, such that if there are any walks between N and M they all must either use only edges labelled 'conflict' or 'requires'.

Wir denken immer wieder, dass wir alle kniffligen Probleme haben, und dann stellen wir fest, dass eine bestimmte Struktur Probleme verursacht, an die wir vorher nicht gedacht hatten. Wir testen jeden Trick, den wir uns vorstellen können.

Das klingt nach einem guten Start. Ich vermute, Sie haben bereits versucht, einige klassische Techniken wie die Grenzwertanalyse oder die Äquivalenzpartitionierung anzuwenden , wie Sie bereits erwähnt haben. Nachdem Sie viel Zeit in die Erstellung guter Testfälle investiert haben, werden Sie zu einem Punkt kommen, an dem Ihnen, Ihrem Team und auch Ihren Testern (falls Sie diese haben) die Ideen ausgehen. Und an diesem Punkt sollten Sie den Pfad des Unit- Testens verlassen und mit möglichst vielen Daten aus der realen Welt beginnen.

Es sollte offensichtlich sein, dass Sie versuchen sollten, eine große Vielfalt von Diagrammen aus Ihren Produktionsdaten auszuwählen. Möglicherweise müssen Sie einige zusätzliche Tools oder Programme nur für diesen Teil des Prozesses schreiben. Das Schwierigste dabei ist wahrscheinlich, die Richtigkeit der Programmausgabe zu überprüfen. Wenn Sie zehntausende verschiedene Diagramme aus der realen Welt in Ihr Programm einfügen, wie können Sie dann feststellen, ob Ihr Programm immer die richtige Ausgabe liefert? Offensichtlich können Sie nicht als manuell überprüfen. Wenn Sie Glück haben, können Sie möglicherweise eine zweite, sehr einfache Implementierung Ihrer Abhängigkeitsprüfung durchführen, die Ihre Leistungserwartungen möglicherweise nicht erfüllt, aber einfacher zu überprüfen ist als Ihr ursprünglicher Algorithmus. Sie sollten auch versuchen, viele Plausibilitätsprüfungen direkt in Ihr Programm zu integrieren (z. B.

Lernen Sie schließlich zu akzeptieren, dass jeder Test nur das Vorhandensein von Fehlern beweisen kann, nicht aber das Fehlen von Fehlern.

1. Randomisierte Testgenerierung

Schreiben Sie einen Algorithmus, der Graphen erzeugt, lassen Sie ihn ein paar hundert (oder mehr) zufällige Graphen erzeugen und werfen Sie jeden auf Ihren Algorithmus.

Behalten Sie die Zufallszahl der Diagramme bei, die interessante Fehler verursachen, und fügen Sie diese als Komponententests hinzu.

2. Schwierige Teile mit hartem Code

Einige Diagrammstrukturen, von denen Sie wissen, dass sie schwierig sind, können Sie sofort einprogrammieren oder Code schreiben, der sie kombiniert und an Ihren Algorithmus weiterleitet.

3. Vollständige Liste erstellen

Wenn Sie jedoch sicher sein möchten, dass "der Code alle denkbaren Permutationen verarbeiten kann, die Sie in Daten der realen Welt finden", müssen Sie diese Daten nicht aus zufälligen Ausgangswerten generieren, sondern indem Sie alle Permutationen durchlaufen. (Dies wird beim Testen von U-Bahn-Signalsystemen durchgeführt und bietet eine enorme Anzahl von Fällen, deren Prüfung Ewigkeiten in Anspruch nimmt. Bei U-Bahnen ist das System beschränkt, sodass die Anzahl der Permutationen nach oben begrenzt ist. Sie sind sich nicht sicher, wie Ihr Fall lautet.) gilt)

In diesem Fall werden keinerlei Tests ausreichen, nicht einmal Tonnen von Daten aus der realen Welt oder Fuzzing. Eine 100% ige Codeabdeckung oder sogar eine 100% ige Pfadabdeckung reicht nicht aus, um rekursive Funktionen zu testen.

Entweder hält die rekursive Funktion einem formalen Beweis stand (sollte in diesem Fall nicht so schwierig sein) oder nicht. Wenn der Code zu stark mit anwendungsspezifischem Code verflochten ist, um Nebenwirkungen auszuschließen, sollten Sie damit beginnen.

Der Algorithmus selbst klingt wie ein einfacher Überflutungsalgorithmus, ähnlich einer einfachen umfassenden ersten Suche, mit der Hinzufügung einer schwarzen Liste, die sich nicht mit der Liste der besuchten Knoten überschneiden darf, die von allen Knoten ausgeführt werden.

foreach nodes as node
    foreach nodes as tmp
        tmp.status = unmarked

    tovisit = []
    tovisit.push(node)
    node.status = required

    while |tovisit| > 0 do
        next = tovisit.pop()
        foreach next.requires as requirement
            if requirement.status = unmarked
                tovisit.push(requirement)
                requirement.status = required
            else if requirement.status = blacklisted
                return false
        foreach next.collides as collision
            if collision.status = unmarked
                requirement.status = blacklisted
            else if requirement.status = required
                return false
return true

Dieser iterative Algorithmus erfüllt die Bedingung, dass für Graphen mit beliebiger Struktur ausgehend von einem beliebigen Artefakt keine Abhängigkeit erforderlich und gleichzeitig auf die schwarze Liste gesetzt werden darf, wobei das Startartefakt immer erforderlich ist.

Es kann zwar so schnell wie Ihre eigene Implementierung sein oder auch nicht, es kann jedoch bewiesen werden, dass es für alle Fälle endet (da für jede Iteration der äußeren Schleife jedes Element nur einmal in die tovisitWarteschlange verschoben werden kann), es überschwemmt das gesamte erreichbare Element Es erkennt alle Fälle, in denen ein Artefakt gleichzeitig benötigt und auf die schwarze Liste gesetzt werden muss, beginnend bei jedem Knoten.

Wenn Sie nachweisen können, dass Ihre eigene Implementierung dieselben Merkmale aufweist, können Sie die Richtigkeit nachweisen, ohne dass dies zu einem Komponententest führt. Es müssen nur die grundlegenden Methoden zum Pushen und Poppen aus Warteschlangen, Zählen der Warteschlangenlänge, Durchlaufen von Eigenschaften usw. getestet werden, und es muss nachgewiesen werden, dass sie frei von Nebenwirkungen sind.

BEARBEITEN: Was dieser Algorithmus nicht beweist, ist, dass Ihr Graph frei von Zyklen ist. Gerichtete azyklische Graphen sind jedoch ein gut recherchiertes Thema, daher sollte es auch einfach sein, einen vorgefertigten Algorithmus zum Nachweis dieser Eigenschaft zu finden.

Wie Sie sehen, muss das Rad keinesfalls neu erfunden werden.

Sie verwenden Ausdrücke wie "alle interessanten Diagrammstrukturen" und "entsprechend behandelt". Sofern Sie nicht die Möglichkeit haben, Ihren Code anhand all dieser Strukturen zu testen und festzustellen, ob der Code das Diagramm ordnungsgemäß verarbeitet, können Sie nur Tools wie die Testabdeckungsanalyse verwenden.

Ich schlage vor, Sie beginnen mit dem Auffinden und Testen einer Reihe interessanter Diagrammstrukturen, ermitteln die geeignete Behandlung und stellen fest, dass der Code dies tut. Dann können Sie anfangen, diese Graphen in a) fehlerhafte Graphen umzuwandeln, die gegen Regeln verstoßen, oder b) nicht so interessante Graphen, die Probleme haben; Überprüfen Sie, ob Ihr Code diese nicht ordnungsgemäß verarbeitet.

Sie könnten versuchen, eine topologische Sortierung durchzuführen und zu prüfen, ob sie erfolgreich ist. Wenn nicht, haben Sie mindestens einen Zyklus.

Wenn es um diese Art von schwer zu testendem Algorithmus geht, würde ich mich für das TDD entscheiden, bei dem Sie den Algorithmus basierend auf Tests erstellen.

TDD kurz gesagt,

• schreibe den Test
• sehe, es scheitert
• Ändern Sie den Code
• Stellen Sie sicher, dass alle Tests bestanden werden
• Refactor

und den Zyklus wiederholen,

In dieser besonderen Situation,

1. Der erste Test wäre ein Graph mit einem einzelnen Knoten, bei dem der Algorithmus keine Zyklen zurückgeben sollte
2. Der zweite wäre ein Drei-Knoten-Graph ohne Zyklus, wobei der Algorithmus keine Zyklen zurückgeben sollte
3. Als nächstes würde man einen Drei-Knoten-Graphen mit einem Zyklus verwenden, bei dem der Algorithmus keine Zyklen zurückgeben sollte
4. Jetzt können Sie es je nach Möglichkeit gegen einen etwas komplexeren Zyklus testen

Ein wichtiger Aspekt bei dieser Methode ist, dass Sie immer einen Test für einen möglichen Schritt hinzufügen müssen (bei dem Sie mögliche Szenarien in einfache Tests aufteilen). Wenn Sie alle möglichen Szenarien abdecken, wird der Algorithmus normalerweise automatisch entwickelt.

Schließlich müssen Sie einen oder mehrere komplizierte Integrationstests hinzufügen, um zu ermitteln, ob unvorhergesehene Probleme vorliegen (z. B. Stapelüberlauffehler / Leistungsfehler, wenn Ihr Diagramm sehr groß ist und Sie die Rekursion verwenden).

Mein Verständnis des Problems, wie es ursprünglich angegeben und dann durch Kommentare unter Mackes Antwort aktualisiert wurde, umfasst Folgendes: 1) Beide Kantentypen (Abhängigkeiten und Konflikte) sind gerichtet. 2) wenn zwei Knoten durch eine Kante verbunden sind, dürfen sie nicht durch eine andere verbunden werden, auch wenn es sich um einen anderen Typ handelt oder umgekehrt; 3) Wenn ein Pfad zwischen zwei Knoten konstruiert werden kann, indem Kanten verschiedener Typen gemischt werden, ist dies eher ein Fehler als ein Umstand, der ignoriert wird. 4) Wenn es einen Pfad zwischen zwei Knoten gibt, die Kanten eines Typs verwenden, gibt es möglicherweise keinen anderen Pfad zwischen ihnen, wenn Kanten des anderen Typs verwendet werden. 5) Zyklen eines einzelnen Kantentyps oder gemischter Kantentypen sind nicht zulässig (nach einer Schätzung der Anwendung bin ich nicht sicher, ob Konfliktzyklen ein Fehler sind, aber diese Bedingung kann entfernt werden, wenn dies nicht der Fall ist.)

Weiterhin gehe ich davon aus, dass die verwendete Datenstruktur Verstöße gegen diese Anforderungen nicht verhindert (zum Beispiel könnte ein Graph, der die Bedingung 2 verletzt, nicht in einer Abbildung von Knotenpaar zu (Typ, Richtung) ausgedrückt werden, wenn das Knotenpaar immer hat zuerst den Knoten mit der niedrigsten Nummer.) Wenn bestimmte Fehler nicht ausgedrückt werden können, wird die Anzahl der zu berücksichtigenden Fälle verringert.

Tatsächlich gibt es drei Diagramme, die hier betrachtet werden können: die zwei mit ausschließlich einem Kantentyp und das gemischte Diagramm, das durch die Vereinigung von einem der beiden Typen gebildet wird. Auf diese Weise können Sie systematisch alle Diagramme bis zu einer bestimmten Anzahl von Knoten erstellen. Erzeugen Sie zunächst alle möglichen Graphen von N Knoten mit nicht mehr als einer Kante zwischen zwei geordneten Knotenpaaren (geordnete Paare, da es sich um gerichtete Graphen handelt). Nehmen Sie nun alle möglichen Paare dieser Graphen, von denen eines Abhängigkeiten und das andere Konflikte darstellt, und bilden die Vereinigung jedes Paares.

Wenn Ihre Datenstruktur Verstöße gegen Bedingung 2 nicht ausdrücken kann, können Sie die zu berücksichtigenden Fälle erheblich reduzieren, indem Sie nur alle möglichen Konfliktdiagramme erstellen, die in die Bereiche der Abhängigkeitsdiagramme passen, oder umgekehrt. Andernfalls können Sie Verstöße gegen Bedingung 2 beim Bilden der Vereinigung erkennen.

Beim Durchlaufen des kombinierten Graphen vom ersten Knoten an können Sie die Menge aller Pfade zu jedem erreichbaren Knoten erstellen und dabei nach Verstößen gegen alle Bedingungen suchen (für die Zykluserkennung können Sie dies tun) benutze Tarjans Algorithmus .)

Sie müssen nur Pfade vom ersten Knoten berücksichtigen, auch wenn das Diagramm nicht verbunden ist, da Pfade von jedem anderen Knoten in einem anderen Fall als Pfade vom ersten Knoten angezeigt werden.

Wenn Pfade mit gemischten Kanten einfach ignoriert werden können, anstatt Fehler zu sein (Bedingung 3), ist es ausreichend, die Abhängigkeits- und Konfliktdiagramme unabhängig voneinander zu betrachten und zu überprüfen, ob ein Knoten in einem erreichbar ist, der andere nicht.

Wenn Sie sich an die Pfade erinnern, die beim Untersuchen von Diagrammen von N-1-Knoten gefunden wurden, können Sie diese als Ausgangspunkt für das Generieren und Auswerten von Diagrammen von N-Knoten verwenden.

Dadurch werden nicht mehrere Kanten desselben Typs zwischen Knoten generiert, es kann jedoch eine Erweiterung vorgenommen werden. Dies würde jedoch die Anzahl der Fälle stark erhöhen. Es wäre daher besser, wenn der getestete Code es unmöglich machen würde, alle derartigen Fälle im Voraus darzustellen, oder wenn dies nicht der Fall wäre.

Der Schlüssel zum Schreiben eines solchen Orakels besteht darin, es so einfach wie möglich zu halten, auch wenn dies ineffizient bedeutet, damit Sie Vertrauen in es aufbauen können (idealerweise durch Argumente für seine Richtigkeit, die durch Tests gestützt werden).

Sobald Sie über die Mittel verfügen, um Testfälle zu generieren, und Sie darauf vertrauen, dass das von Ihnen erstellte Orakel die guten von den schlechten trennt, können Sie damit das automatisierte Testen des Zielcodes vorantreiben. Wenn dies nicht möglich ist, können Sie die Ergebnisse am besten nach Einzelfällen durchsuchen. Das Orakel kann die gefundenen Fehler klassifizieren und Ihnen einige Informationen zu den akzeptierten Fällen geben, z. B. die Anzahl und Länge der Pfade jedes Typs und ob sich am Anfang beider Pfadtypen Knoten befinden könnte Ihnen helfen, nach Fällen zu suchen, die Sie vorher nicht gesehen haben.