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)
|
Keywords | Authorization 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)
|
Kontakt | suwimodh@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
|
Eingabedatum | 13. Dezember 2006 |
---|