Die folgende Frage wurde mehrmals beim Testen der Sicherheit eines Systems oder Modells gestellt.
Motivation: Software-Sicherheitslücken entstehen häufig nicht durch Fehler aufgrund gültiger Eingaben, sondern durch Fehler aufgrund ungültiger Eingaben, die den gültigen Eingaben so nahe kommen, dass viele der einfachen Gültigkeitsprüfungen nicht bestanden werden. Das klassische Beispiel ist natürlich ein Pufferüberlauf, bei dem die Eingabe vernünftig ist, außer dass sie zu groß ist. Compiler und andere Tools können Sie dabei unterstützen, diese Probleme zu beheben, indem Sie das Layout des Stapels und des Heaps sowie andere Verschleierungstechniken ändern. Eine Alternative besteht darin, die Probleme aus dem Quellcode selbst zu entfernen. Eine als Fuzzing Bombards bezeichnete Technik, bei der das Programm Eingaben vornimmt, liegt nahe an den erwarteten Eingaben, ist jedoch an einigen Stellen unangemessen (große Werte für Ganzzahl- oder Zeichenfolgenfelder). Ich möchte das Fuzzing (als ein Beispiel) aus einer formaleren Perspektive verstehen.
Angenommen, der Raum gültiger Eingaben wird durch die Bedingungen . Sei M die Menge von Lösungen solcher Randbedingungen, nämlich M = { m ∈ M | m ⊨ Φ } , wobei M der Raum möglicher Eingaben ist.
Ich suche Arbeit, die die folgenden Begriffe beschreibt:
Die Penumbra von ist , einen Satz M ' ⊆ M derart , daß für jedes m ∈ M ' m ⊭ & Phi; und in einem gewissen Sinne die Elemente M ' sind nahe an den Elementen M . Man kann sich das Halbschattenbild als die beinahe Lösung vorstellen . Natürlich wird dieser Begriff nicht eindeutig sein.
Möglichkeiten der Lockerung der Einschränkungen bis Φ ' , so daß zunächst Φ ⇒ Φ ' und Φ ' ∧ ¬ Φ heißt, in einem gewissen Sinne der syntaktischen Penumbra von Φ .
"Penumbra" ist ein Wort, das ich ausgewählt habe, um das Konzept zu beschreiben. Man könnte es auch etwas anderes nennen.
Ich fand Inspiration in der mathematischen Morphologie , daher meine visuelle Metapher, aber die beiden Welten sind Parsec voneinander entfernt. Gibt es dort eine nützliche Arbeit? Oder vielleicht in der Welt der groben Sets ?
Kann jemand Licht ins Dunkel bringen?
Antworten:
Ein Großteil der Aufmerksamkeit, die Optimierungsvarianten des Constraint-Erfüllungsproblems (CSP) gewidmet wurde, konzentrierte sich auf die Erfüllung einer bestimmten Anzahl von Constraints (MAX-CSP) oder im Booleschen Fall auf die Auswahl der Lösung, bei der möglichst viele Variablen den Wert 1 erhalten ( MAXIMALE, es gibt auch MINIMALE).
Stattdessen fragen Sie nach einer Variante, die MAXIMUM PARTIAL CSP heißen könnte. Dies wurde zumindest schon Ende der 1960er Jahre untersucht, aber mir ist nicht bekannt, dass es einen etablierten Namen hat. Es ist ein natürliches Problem, und es wäre gut zu sehen, wie weitere Arbeiten es untersuchen. Vielen Dank für die Bereitstellung einer weiteren potenziellen Anwendung für dieses Problem!
Eine Menge variabler Wertzuweisungen wird als Teilzuweisung bezeichnet . Man kann eine Variablenwertzuweisung als (Variablen-, Wert-) Tupel schreiben. Teilzuweisungen sind dann einfach Funktionen von Variablen zu Werten. Requisiten sind Teilzuweisungen, die keine Einschränkungen verletzen. Entsprechend enthält eine Requisite keine Teilzuweisung, die durch eine Einschränkung verboten ist (als Teilmenge).
Eine Möglichkeit, das Optimierungsproblem auszudrücken, ist wie folgt.
Der zweite Teil Ihrer Frage erscheint ebenfalls sehr interessant, mir sind jedoch keine Arbeiten dazu bekannt.
Fußnote: Der Begriff Stütze stammt aus meiner Diplomarbeit; es soll die Vorstellung vermitteln, dass solche Teilaufgaben richtig sind und auch die Menge der Lösungen unterstützen. Dies steht im Gegensatz zu nogood , dem akzeptierten Begriff für eine Teilaufgabe, die nicht auf eine Lösung ausgeweitet werden kann. Das Wort "nogood" wurde 1976 von Richard Stallman und Gerald Sussman eingeführt, als RMS noch ein KI-Forscher war und kein Aktivist für Softwarefreiheit.
quelle