h1

000956653 001__ 956653
000956653 005__ 20251010144459.0
000956653 0247_ $$2HBZ$$aHT030012666
000956653 0247_ $$2Laufende Nummer$$a42235
000956653 0247_ $$2datacite_doi$$a10.18154/RWTH-2023-04281
000956653 037__ $$aRWTH-2023-04281
000956653 041__ $$aEnglish
000956653 082__ $$a004
000956653 1001_ $$0P:(DE-82)IDM03434$$aVölker, Marcus$$b0$$urwth
000956653 245__ $$aPolicy iteration for value set analysis of PLC programs$$cvorgelegt von Marcus Völker, M.Sc. RWTH$$honline
000956653 260__ $$aAachen$$bRWTH Aachen University$$c2023
000956653 300__ $$a1 Online-Ressource : Illustrationen, Diagramme
000956653 3367_ $$02$$2EndNote$$aThesis
000956653 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
000956653 3367_ $$0PUB:(DE-HGF)3$$2PUB:(DE-HGF)$$aBook$$mbook
000956653 3367_ $$2BibTeX$$aPHDTHESIS
000956653 3367_ $$2DRIVER$$adoctoralThesis
000956653 3367_ $$2DataCite$$aOutput Types/Dissertation
000956653 3367_ $$2ORCID$$aDISSERTATION
000956653 4900_ $$aAachener Informatik-Berichte (AIB)$$v2023,01
000956653 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
000956653 502__ $$aDissertation, RWTH Aachen University, 2023$$bDissertation$$cRWTH Aachen University$$d2023$$gFak01$$o2023-03-06
000956653 5203_ $$aDie Gewährleistung korrekten Verhaltens von Computersystemen ist eine wichtige Aufgabe, um Gefahren von ihren Benutzern abzuwenden. Zu diesem Zweck wurden zahlreiche Analysetechniken entwickelt, mit denen Fehler in Software gefunden werden können oder bewiesen werden kann, dass die Software einer bestimmten Spezifikation korrekten Verhaltens entspricht. Eine dieser Techniken ist die Wertebereichsanalyse (VSA), mit der eine Abschätzung der Werte der Programmvariablen an jedem Punkt des Programms ermittelt werden kann. Mithilfe dieser können viele Fehler gefunden werden, wie z. B. Division durch Null, illegaler Speicherzugriff, oder unerreichbarer Code. Während die Wertbereichsanalyse klassischerweise mittels Kleene-Iteration durchgeführt wird, wurde in den letzten Jahren ein anderer Ansatz namens Policy-Iteration entwickelt, der das Potenzial hat, ähnliche oder bessere Ergebnisse in kürzerer Zeit zu erzielen. Bei der Policy-Iteration wird eine Heuristik verwendet, um das Programm erst auf eine bestimmte Weise zu vereinfachen, dann die Wertemengen dieses vereinfachten Programms zu finden und dann zu prüfen, ob das Ergebnis auf das ursprüngliche Programm anwendbar ist. Wenn ja, wird das Ergebnis verwendet, andernfalls müssen verschiedene andere Vereinfachungen geprüft werden, bis ein brauchbares Ergebnis gefunden wird. Da es sich bei der Policy-Iteration um einen heuristischen Algorithmus handelt, macht er bestimmte Annahmen über das Programmverhalten, um gute Ergebnisse zu erzielen. Es stellt sich jedoch heraus, dass diese Annahmen nicht garantiert werden können, wenn das Programm Fehler enthält. Da Programmanalyse genutzt wird, um Fehler zu finden, ist die Annahme eines fehlerfreien Programms nicht allgemeingültig. In dieser Arbeit zeigen wir mehrere Möglichkeiten auf, die Heuristik aus der Literatur zu verbessern, indem wir Programmschleifen betrachten. Zunächst stellen wir eine Möglichkeit vor, mit Hilfe einer Voranalyse bestimmtes Verhalten von Schleifen zu bestimmen, und verwenden diese Informationen, um eine Heuristik zu erstellen, die in vielen Fällen zu genaueren Lösungen führt als die Standardheuristik. Dies geschieht auf Kosten der zusätzlichen Laufzeit, die zur Durchführung dieser Voranalyse erforderlich ist. Danach zeigen wir eine Möglichkeit, Verzweigungen in zyklischem Code—typisch für reaktive Systeme—als Schleifen zu betrachten. Auf diese Weise können wir unsere Schleifenheuristik auf eine breitere Auswahl von Programmen anwenden, auch wenn höhere Zeitkosten dafür sorgen, dass sie nur in bestimmten Fällen nützlich ist. Anschließend zeigen wir, wie die Voranalyse entfernt werden kann, um uns an die Laufzeit der ursprünglichen Policy-Iteration anzunähern, wobei ähnlich gute Ergebnisse wie bei der zuvor eingeführten teuren Version erzielt werden. Dies hat den zusätzlichen Vorteil, dass die Algorithmen wie beim zweiten Ansatz auf Verzweigungen angewendet werden können, ohne dass zusätzliche Kosten anfallen. Wir begründen, dass dies die Version der Policy-Iteration ist, die im Allgemeinen mit einer umfassenden Bewertung der generierten Programme verwendet werden sollte. Schließlich zeigen wir einen Weg, polynomielle Ungleichungen zu analysieren, indem wir sie als Konjunktionen von einfacheren Ungleichungen umdeuten. Dadurch können wir nicht nur die Ergebnisse der Wertebereichsanalyse für Programme mit solchen Ungleichungen verbessern, sondern diese Programme auch für die Policy-Iteration zugänglich machen.$$lger
000956653 520__ $$aEnsuring the correct behaviour of computing systems is an important task to prevent danger to the users of such systems. To do this, many analysis techniques have been developed that can find bugs in software, or prove that it complies to some specification of correct behaviour. Among these techniques, a fundamental analysis is value set analysis (VSA), which can determine an approximation of the program variables' values at each point of the program. This is very important information, as many faulty behaviours can be traced back to variables taking unexpected values, such as division by zero, access to uninitialised memory or outside a buffer, or unreachable code. While classically, value set analysis is performed with the algorithm of Kleene iteration, another approach called policy iteration has been developed in recent years that provides an alternative with the potential of finding similar or better results than Kleene iteration in less time. Policy iteration works by using a heuristic to simplify the program in a certain way, finding the value sets of that program, and then checking whether the result is applicable to the original program. If yes, the results are used, otherwise different simplifications have to be checked, until a usable result is found. As policy iteration is a heuristic algorithm, it makes certain assumptions about program behaviour in order to achieve good results. It turns out, however, that these assumptions are not guaranteed if the program contains errors which cause it to behave differently than expected. As we use program analysis to find errors such as this, assuming an error-free program is not necessarily a good assumption. In this thesis, we show several ways to improve the original heuristic by focusing on program loops. First, we present a way to use a pre-analysis to determine some aspect of the loops' behaviours, and use this information in order to build a heuristic that leads to more accurate solutions than the standard heuristic in many cases, at the cost of additional running time necessary to perform this pre-analysis. Then, we show a way to reinterpret branches as loops if they occur in cyclical code, which is typical for programs in reactive systems, such as the systems used for factory automation. This allows us to use our loop heuristic on a wider variety of programs, even though the cost becomes even greater, and it is useful only in specific cases. Afterwards, we show how to remove the pre-analysis to gain back the lost time, while still retaining similarly good results to the expensive version introduced before. This has the additional benefit of allowing usage of the algorithms on branches as in the second approach, without incurring any additional costs. We motivate that this is the version of policy iteration that should be used in general with an extensive evaluation of generated programs. Finally, we show a way to analyse polynomial inequalities with value set analysis by reinterpreting them as conjunctions of simpler inequalities. This not only allows us to improve value set analysis results on programs that feature such inequalities, but also makes these programs accessible to policy iteration.$$leng
000956653 591__ $$aGermany
000956653 7001_ $$0P:(DE-82)IDM06137$$aKowalewski, Stefan$$b1$$eThesis advisor$$urwth
000956653 7001_ $$0P:(DE-82)959033$$aBeckert, Bernhard$$b2$$eThesis advisor
000956653 8564_ $$uhttps://publications.rwth-aachen.de/record/956653/files/956653.pdf$$yOpenAccess
000956653 8564_ $$uhttps://publications.rwth-aachen.de/record/956653/files/956653_source.zip$$yRestricted
000956653 909CO $$ooai:publications.rwth-aachen.de:956653$$popenaire$$popen_access$$pVDB$$pdriver$$pdnbdelivery
000956653 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM03434$$aRWTH Aachen$$b0$$kRWTH
000956653 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)000779$$aRWTH Aachen$$b1$$kRWTH
000956653 9141_ $$y2023
000956653 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000956653 9201_ $$0I:(DE-82)122810_20140620$$k122810$$lLehrstuhl für Informatik 11 (Embedded Software)$$x0
000956653 9201_ $$0I:(DE-82)120000_20140620$$k120000$$lFachgruppe Informatik$$x1
000956653 961__ $$c2023-06-01T14:27:57.340699$$x2023-04-21T20:02:28.612267$$z2023-06-01T14:27:57.340699
000956653 9801_ $$aFullTexts
000956653 980__ $$aI:(DE-82)120000_20140620
000956653 980__ $$aI:(DE-82)122810_20140620
000956653 980__ $$aUNRESTRICTED
000956653 980__ $$aVDB
000956653 980__ $$abook
000956653 980__ $$aphd