Gibt es irgendwelche Arbeiten zur Entwicklung der Differenzrechnung von Turingmaschinen (oder einfacheren formalen Sprachen)?

8

Ich versuche, einige Begriffe einer Differenzrechnung zwischen einer von einem Entwickler konzipierten fiktiven Ideal Turing-Maschine (z. B. was auch immer von einem Softwareentwickler beabsichtigt ist), und den Maschinen zu entwickeln, die die Software darstellen, die tatsächlich entworfen wird, und implementiert, sagen wir M α bzw. M β .MIMαMβ

Insbesondere ist es mein Interesse, Einschränkungen (zum Beispiel aufgrund des Satzes von Rice) bei der automatisierten Erkennung von Fehlern in Softwareprogrammen zwischen der von der idealen Maschine verarbeiteten Sprache und der von den entwickelten / implementierten Maschinen verarbeiteten Sprache zu untersuchen.

Jegliche Bezugnahme auf frühere Arbeiten, die mit einigen Vorstellungen von der Untersuchung von Unterschieden zwischen zwei spezifizierten Turing-Maschinen arbeiten, oder der Hinweis, dass eine niedrigere formale Sprache äußerst hilfreich und geschätzt wäre; weil ich lieber zitieren als schreiben möchte :-).

Ahmed Masud
quelle
4
Klingt nach modellbasiertem Testen . Man entwickelt ein Modell des gewünschten Systems und generiert daraus Tests für das eigentliche System.
Dave Clarke
@ DaveClarke Vielen Dank für den Querverweis auf modellbasiertes Testen. Mir hätte einfallen müssen, dass das Betrachten modellbasierter Tests definitiv Vorteile bringt. Ich frage mich, ob ich nur mit FSA beginne und mich aufbaue in der Lage, einen Großteil der bestehenden Theorie zur Fehlermodellierung zu nutzen. (nur laut nachdenken)
Ahmed Masud
1
Ich würde auch die Theorien der Programmverfeinerung und der Verfeinerungsrechnung betrachten. R.-J. Back und J. von Wright haben diese Theorie entwickelt. In der Welt der gleichzeitigen Programmierung gibt es das verwandte Konzept der Aktionsverfeinerung.
Martin Berger
@MartinBerger, vielen Dank für den Vorschlag, sich mit der Verfeinerung von Aktionen zu befassen. Insbesondere die Verfeinerung von Aktionen in Prozessalgebra- und Sicherheitsproblemen dsi.unive.it/~srossi/Papers/lopstr07.pdf war mit Sicherheit ein interessanter Fund!
Ahmed Masud
Allgemeines Update: Der technische Bericht "Angriffsmodellierung für Informationssicherheit und Überlebensfähigkeit" von Moore, AP und Ellison, RJ und Linger, RC; bietet eine gute Ausgangsbasis. PS Ich werde möglicherweise eine Antwort auf meine eigene Frage veröffentlichen, die sich aus all den wunderbaren Vorschlägen aller ergibt. Ist das üblich?
Ahmed Masud

Antworten:

3

Wie sich herausstellt, gibt es einige faszinierende Arbeiten in dieser Richtung.

Insbesondere im Jahr 2003 haben Michael Howard, Jon Pincus und Jeannette M. Wing im Rahmen eines Workshops über fortgeschrittene Entwicklungen in der Software- und Systemsicherheit, Taipeh, Dezember 2003, Relative Attack Surfaces gemessen.

Weitere Arbeiten der gleichen Autoren im Laufe der Jahre sind sehr interessant ... Für alle, die meine Frage von Interesse fanden, können Sie ihre Arbeit unter http://www.cs.cmu.edu/~pratyus/as.html nachlesen. Und wenn Sie sie interessant finden, hoffe ich, dass Sie meine Arbeit auch interessant finden :)

Ahmed Masud
quelle
2

Ich denke, dass die Überprüfung von Softwaremodellen im Sinne von Alloy wahrscheinlich mit dem zusammenhängt, wonach Sie suchen. Sie schreiben ein Modell und eine Spezifikation, die das Modell erfüllen soll, und prüfen, ob sie in angemessener Beziehung zueinander stehen.

Sam Tobin-Hochstadt
quelle
Legierung ist ein sehr interessanter Vorschlag :)
Ahmed Masud