Subcircuit pattern matching in digital designs

Abstract

Design understanding is an essential part of reverse engineering and verification of digital designs. Extracting and subsequently analyzing subcircuits of synthesized designs offers an alternative approach to simulation and analyzing hardware descriptions. In this thesis we develop a search algorithm to extract functional blocks like counters and state machines from synthesized Verilog designs via structural pattern matching. Extracting functional blocks supports reverse- and verification engineers in checking a given design against its specification, identify errors, perform security evaluations, and deepen overall understanding of a design.By analyzing the related work we find three approaches for finding subcircuits in a design: (1) matching based on functional equivalence, (2) matching based in structural equivalence, and (3) mixed approaches. We discuss each of the approaches and analyze their deficiencies. Functional approaches struggle with capturing the full and characteristic functionality of subcircuits to compare them to reference functionality descriptions. Capturing and comparing the full and characteristic functionality may require exhaustive simulation in the worst case. Structural methods struggle with capturing and identifying structural variability of components with similar functionality. Mixed approaches aim at combing the strength and weaknesses of both approaches, resulting in one algorithm per functional class. We extend the state of the art by introducing one single algorithm that efficiently matches a pattern to capture all representatives of a functional class. These patterns use serial and parallel quantification of occurrence of subpatterns to model structuralvariability.We use the pattern graph specification language (PGSL) to describe functional classes for which we search representatives in an abstraction of a digital design called design graph. Design abstraction significantly reduces the complexity of the search problem. We demonstrate pattern modeling on the practical examples state machines, counters and elements of encoders/decoders. The proposed search algorithm searches for pattern matches by subgraph isomorphism. It parses PGSL, effectively filters the search space based on the chosen pattern and uses a search-and-combine approach to find pattern matches. We use a custom constraint satisfaction problem (CSP) solver to combine matches of subpatterns until full matches are found. We implement our search algorithm as plugin to the open-source synthesis suite Yosys.To demonstrate the effectiveness and efficiency of our chosen search approach we conduct a large-scale experiment on 74 open-source designs of increasing complexity and five patterns covering all important features of PGSL. Experimental results show satisfactory search times in the range of seconds to minutes and search results can be used for further design analysis. We demonstrate the usefullness of results for example patterns and designs.Furthermore, we analyze the performance of our algorithm. Subgraph isomorphism is an NP-complete problem which has exponential worst case behavior. Performance estimation is complicated by the fact that we do not search matches for one uniform graph, but rather pattern graphs that are nested and contain quantified subpatterns. This leads to interesting side effects like the search for quantified subpatterns dominating the search. In these cases the subpattern search results in a large amount of matches in the design that all have to be checked during the combination step of the search algorithm.Summing up, we show that we are able to do what has not been possible before: We are able to model abstract, regular-expression-like patterns for subcircuits, search them in an abstract graph of real-world designs, and extract candidate subcircuits that match such patterns

Das Verstehen von digitalen Designs stellt einen wesentlichen Bestandteil von Reverse Engineering und der Verifikation von digitaler Designs dar. Ein alternativer Ansatz zu Simulation und Analyse von Hardwarebeschreibungen bietet das Extrahieren und anschließendes Analysieren von Teilschaltungen synthetisierter Designs. Der Fokus der vorliegenden Arbeit liegt auf der Entwicklung eines Suchalgorithmus um funktionale Blöcke wie Zähler und Zustandsautomaten aus synthetisierten Verilog-Designs mittels strukturellem Mustervergleich zu extrahieren. Die Extraktion von Funktionsblöcken unterstützt Reverse- und Verifikationsingenieure ein gegebenes Design mit dessen Spezifikation zu vergleichen, bei der Identifizierung von Fehlern, bei der Durchführung von Sicherheitsüberprüfungen, sowie der Vertiefung des Gesamtverständnisses eines Designs. In einer umfassenden Literaturstudie konnten drei Ansätze zur Identifizierung von Teilschaltungen in einem Design identifiziert werden: (1) Matching basierend auf funktionaler Äquivalenz, (2) Matching basierend auf struktureller Äquivalenz und (3) gemischte Ansätze. Die vorliegenden Ansätze werden im Zuge dieser Arbeit im Detail analysiert und im Hinblick auf ihre Mängel diskutiert. Funktionale Ansätze sind problematisch im Hinblick auf das Erfassen der vollständigen und charakteristischen Funktionalität von Teilschaltungen und deren Vergleich mit Referenzfunktionsbeschreibungen. Um die vollständige und charakteristische Funktionalität zu erfassen und zu vergleichen, kann im schlimmsten Fall umfangreiche Simulation notwendig sein. Strukturelle Methoden wiederum zeigen Schwierigkeiten bei der Erfassung und Identifizierung von struktureller Variabilität bei Komponenten mit ähnlicher Funktionalität. Gemischte Ansätze, die versuchen die Stärken der beiden zuvor genannten Ansätze zu kombinieren, führen allerdings zu jeweils einem Algorithmus pro funktionaler Klasse. Das Ziel dieser Arbeit ist die Entwicklung eines einzigen, effizienten Algorithmus zum Mustervergleich, wobei ein Muster jeweils alle Vertreter einer funktionalen Klasse erfasst. Diese Muster verwenden serielle und parallele Quantifizierung um Strukturvariabilitäten als quantifiziertes Auftreten von Submustern zu modellieren.Um Funktionsklassen zu beschreiben, die wir in einer Abstraktion von digitalen Designs namens design graph suchen, verwenden wir die pattern graph specification language (PGSL). Die Designabstraktion bietet den Vorteil einer erheblichen Reduktion der Komplexität des Suchproblems. Die Funktionsweise der Mustermodellierung wird an praktischen Beispielen wie Zustandsmaschinen, Zählern und Elementen von Encodern/Decodern demonstriert. Der in dieser Arbeit entwickelte Algorithmus sucht nach Musterübereinstimmungen mittels Subgraph-Isomorphismus. Der Suchalgorithmus analysiert das PGSL Muster, filtert den Suchraum basierend auf dem ausgewählten Muster und verwendeteinen Such- und Kombinationsansatz für die Identifizierung von Musterübereinstimmungen. Wir verwenden einen benutzerdefinierten constraint satisfaction problem (CSP) Löser um Übereinstimmungen von Submuster zu kombinieren bis vollständige Übereinstimmungen für das gesamte Muster gefunden werden. Der Suchalgorithmus wurde als Plugin für die Open-Source Synthesissuite Yosys implementiert. Um die Effizienz und Funktionsfähigkeit des entwickelten Suchalgorithmus zu demonstrieren wird ein umfassendes Experiment durchgeführt. Dies umfasst 74 Open-Source-Designs mit zunehmender Komplexität und 5 Muster welche die wichtigsten Funktionen von PGSL abdecken. Die Ergebnisse der zuvor genannten Untersuchung zeigen zufriedenstellende Suchzeiten im Bereich von Sekunden bis Minuten. Des Weiteren können die Suchergebnisse für weitere Designanalysen verwendet werden. Die Nutzbarkeit der Ergebnisse für Beispielmuster und Designs wird gezeigt. Darüber hinaus befasst sich die vorliegende Arbeit mit der Performance des entwickelten Algorithmus. Bei Subgraph-Isomorphismus handelt es sich um ein NP-vollständiges Problem mit exponentiellem Worst-Case Verhalten. Die Abschätzung der Performance des Suchalgorithmus wird durch die Tatsache erschwert, dass keine Übereinstimmung für einen einheitlichen Graphen gesucht wird, sondern für Mustergraphen die verschachtelt sind und quantifizierte Submuster enthalten. Dies führt zu interessanten Nebeneffekten wie z.B., dass die Suche nach quantifizierten Submuster die Suche dominiert. In diesen Fällen führt die Suche nach Submuster zu einer großen Anzahl von Übereinstimmungen im Design, die alle während des Kombinationsschrittes des Suchalgorithmus überprüft werden müssen. Zusammenfassend zeigen wir, dass wir in der Lage sind, das zu tun, was bisher nicht möglich war: Wir sind in der Lage,abstrakte, an regular expressions angelehnte Muster für Teilschaltungen zu modellieren, sie in einer Graphabstraktion von Designs aus der realen Welt zu suchen und die Suchergebnisse als Teilschaltungen zu extrahieren.