Technischer Bericht TR-2006-09

Bibliograph.
Daten
Suwimonteerabuth, Dejvuth; Schwoon, Stefan; Esparza, Javier: Efficient Algorithms for Alternating Pushdown Systems: Application to Certificate Chain Discovery with Threshold Subjects.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2006/09.
21 Seiten, englisch.
CR-Klassif.D.4.6 (Operating Systems Security and Protection)
F.1.1 (Models of Computation)
F.1.2 (Modes of Computation)
KeywordsAuthorization SPKI/SDSI Pushdown Systems Alternation
Kurzfassung

Motivated by recent applications of pushdown systems to computer security problems, we present an efficient algorithm for the reachability problem of alternating pushdown systems. Although the algorithm is exponential, a careful analysis reveals that the exponent is usually small in typical applications. We show that the algorithm can be used to compute winning regions in pushdown games. In a second contribution, we observe that the algorithm runs in polynomial time for a certain subproblem, and show that the computation of certificate chains with threshold certificates in the SPKI/SDSI authorization framework can be reduced to this subproblem. We present a detailed complexity analysis of the algorithm and its application, and report on experimental results obtained with a prototype implementation.

Volltext und
andere Links
PostScript (495430 Bytes)
Kontaktsuwimodh@fmi.uni-stuttgart.de
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Sichere und Zuverlässige Softwaresysteme
Projekt(e)DFG-Projekt Älgorithms for Software Model Checking" SFB 627 Nexus, Teilprojekt A6
Eingabedatum13. Dezember 2006
   Publ. Informatik