La siguiente pregunta ha surgido varias veces al probar la seguridad de un sistema o modelo.
Motivación: las fallas de seguridad del software a menudo no provienen de errores debidos a entradas válidas, sino de errores resultantes de entradas no válidas que están lo suficientemente cerca de las entradas válidas para superar muchas de las verificaciones de validez directas. El ejemplo clásico es, por supuesto, desbordamientos de búfer, donde la entrada es razonable, excepto que es demasiado grande. Los compiladores y otras herramientas pueden ayudar a abordar estos problemas modificando el diseño de la pila y el montón y mediante otras técnicas de ofuscación. Una alternativa es eliminar los problemas del código fuente en sí. Una técnica llamada bombardeo difuso, el programa con entradas está cerca de las entradas esperadas, pero en algunos lugares no son razonables (valores grandes para campos enteros o de cadena). Me gustaría entender el fuzzing (como un ejemplo) desde una perspectiva más formal.
Suponga que el espacio de entradas válidas se describe mediante restricciones . Sea M el conjunto de soluciones de tales restricciones, a saber, M = { m ∈ M | m ⊨ Φ } , donde M es el espacio de posibles entradas.
Estoy buscando trabajo que describa las siguientes nociones:
La penumbra de es un conjunto M ' ⊆ M tal que para cada m ∈ M ' m ⊭ Phi y en cierto sentido, los elementos de M ' son cerca de los elementos de M . Uno puede pensar en la penumbra como las casi soluciones . Por supuesto, esta noción no será única.
"Penumbra" es una palabra que seleccioné para describir el concepto. Bien podría llamarse otra cosa.
Encontré inspiración en la morfología matemática , de ahí mi metáfora visual, pero los dos mundos son parsecs separados. ¿Hay algún trabajo útil allí? ¿O tal vez en el mundo de los juegos rudos ?
¿Alguien puede arrojar luz?
Respuestas:
Gran parte de la atención prestada a las variantes de optimización del problema de satisfacción de restricciones (CSP) se ha centrado en satisfacer cierto número de restricciones (MAX-CSP) o, en el caso booleano, en elegir la solución que asigna el mayor valor posible a tantas variables como sea posible ( MAX-ONES, también hay MIN-ONES).
En cambio, está preguntando acerca de una variante que podría llamarse CSP MÁXIMO PARCIAL. Esto se estudió al menos desde fines de la década de 1960, pero no sé si tenga un nombre establecido. Es un problema natural, y sería bueno ver más trabajo investigándolo. ¡Gracias por proporcionar otra aplicación potencial para este problema!
Un conjunto de asignaciones de valores variables se denomina asignación parcial . Se puede escribir una asignación de valor variable como una tupla (variable, valor). Las asignaciones parciales son simplemente funciones de variables a valores. Los accesorios son tareas parciales que no violan ninguna restricción. De manera equivalente, un accesorio no contiene ninguna asignación parcial prohibida por alguna restricción (como un subconjunto).
Una forma de expresar el problema de optimización es la siguiente.
La segunda parte de su pregunta también parece muy interesante, pero no conozco ningún trabajo relacionado con ella.
Nota al pie: El término prop es de mi tesis; está destinado a transmitir la idea de que tales asignaciones parciales son adecuadas y también de que respaldan el conjunto de soluciones. Esto está en contraste con un nogood , que es el término aceptado para describir una asignación parcial que no se puede extender a una solución. La palabra "nogood" fue introducida por Richard Stallman y Gerald Sussman en 1976, cuando RMS todavía era un investigador de IA en lugar de un activista por la libertad del software.
fuente