¿Por qué es tan incorrecto usar un lexer / parser en datos binarios?

13

A menudo trabajo con lexer / parsers , a diferencia de un combinador de analizadores y veo personas que nunca tomaron una clase de análisis, preguntan sobre el análisis de datos binarios. Por lo general, los datos no solo son binarios, sino también sensibles al contexto. Básicamente, esto lleva a tener solo un tipo de token, un token para byte.

¿Alguien puede explicar por qué analizar datos binarios con un lexer / analizador es tan incorrecto con suficiente claridad para un estudiante de CS que no ha tomado una clase de análisis, pero con una base teórica?

Guy Coder
fuente
Supongo que el lexer probablemente no pueda encontrar tokens que sean más pequeños que un byte / palabra. Si lo necesita, Erlang tiene un excelente soporte para analizar binarios: user.it.uu.se/~pergu/papers/JFP_06.pdf
Dave Clarke
3
No creo que su suposición sea cierta. Obviamente, los datos no libres de contexto plantean problemas (que a menudo pueden ser evasivos), pero puede dar gramáticas para palabras binarias. Probablemente no va a ser capaz de utilizar generadores de analizadores sintácticos populares, como las que suponen la introducción de texto. Sin embargo, ese es otro problema.
Raphael
S0 0S10S
1
28
55
@GuyCoder: todos los datos generados por otro programa pueden describirse mediante una gramática. Sin embargo, podría no ser un contexto libre.
Raphael

Respuestas:

10

En principio, no hay nada malo.

En la práctica,

  • La mayoría de los formatos de datos no textuales que conozco no están libres de contexto y, por lo tanto, no son adecuados para generadores de analizadores comunes. La razón más común es que tienen campos de longitud que indican la cantidad de veces que una producción tiene que estar presente.

    Obviamente, tener un lenguaje sin contexto nunca ha impedido el uso de generadores de analizadores: analizamos un superconjunto del lenguaje y luego usamos reglas semánticas para reducirlo a lo que queremos. Ese enfoque podría usarse para formatos no textuales si el resultado fuera determinista. El problema es encontrar algo más que recuentos para sincronizar, ya que la mayoría de los formatos binarios permiten incrustar datos arbitrarios; los campos de longitud te dicen cuánto es.

    Luego puede comenzar a jugar trucos como tener un lexer escrito manualmente capaz de manejar eso con la retroalimentación del analizador (el manejo de lex / yacc de C usa ese tipo de trucos para manejar typedef, por ejemplo). Pero luego llegamos al segundo punto.

  • La mayoría de los formatos de datos no textuales son bastante simples (incluso si no están libres de contexto). Cuando se ignoran los recuentos mencionados anteriormente, los idiomas son regulares, LL1 en el peor de los casos, y por lo tanto son muy adecuados para las técnicas de análisis manual. Y el manejo del conteo es fácil para las técnicas de análisis manual, como el descenso recursivo.

Un programador
fuente
"los idiomas son regulares" Si "pero también sensible al contexto" se tomó para significar que los datos binarios son una gramática, aclararé en la respuesta. Eso sí llega a parte del problema; las personas tienden a pensar en gramáticas o idiomas regulares una vez que mencionar analizador.
Guy Coder
7

Clasifiquemos los datos en tres categorías: datos legibles por humanos (generalmente textos, que varían de libros a programas), datos destinados a ser leídos por computadoras y otros datos (análisis de imágenes o sonido).

Para la primera categoría, necesitamos procesarlos en algo que una computadora pueda usar. Como los lenguajes utilizados por los humanos generalmente pueden ser capturados relativamente bien por los analizadores sintácticos, generalmente usamos analizadores para esto.

Un ejemplo de datos en la tercera categoría sería una imagen escaneada de una página de un libro que desea analizar en texto. Para esta categoría, casi siempre necesita un conocimiento muy específico sobre su entrada y, por lo tanto, necesita un programa específico para analizarlo. La tecnología de análisis estándar no lo llevará muy lejos aquí.

Su pregunta es sobre la segunda categoría: si tenemos datos que están en binario, casi siempre es un producto de un programa de computadora, destinado a otro programa de computadora. Esto también significa inmediatamente que el programa responsable de su creación elige el formato en el que se encuentran los datos.

Los programas de computadora casi siempre producen datos en un formato que tiene una estructura clara. Si analizamos alguna entrada, esencialmente estamos tratando de descubrir la estructura de la entrada. Con datos binarios, esta estructura es generalmente muy simple y fácil de analizar por computadoras.

En otras palabras, normalmente es un desperdicio descubrir la estructura de una entrada para la que ya conoce la estructura. Como el análisis no es gratuito (lleva tiempo y agrega complejidad a su programa), esta es la razón por la cual el uso de lexers / analizadores en datos binarios es 'tan incorrecto'.

Alex ten Brink
fuente
2
Esta es una buena perspectiva, pero siento que no responde la pregunta.
Raphael
LANGSEC: Language-theoretic SecurityOfrece una perspectiva interesante. Uno de los artículos habla de "máquinas extrañas": analizadores ad hoc de un formato conocido que forman las instalaciones de manejo de entrada de un sistema. Puede que en realidad no funcionen según lo previsto. Debido a suposiciones incorrectas, la máquina defectuosa realizará transiciones de estado no anticipadas dadas entradas especialmente diseñadas, realizando cálculos que no deberían ser posibles. Esto crea un vector de ataque. El uso de gramáticas formales produciría algoritmos probablemente correctos.
Matheus Moreira
0

Si un lenguaje necesita analizarse de una manera no trivial, generalmente significa que los elementos estructurales deben coincidir, por lo que el idioma de entrada contiene redundancia , ya sea porque varias entradas se asignan al mismo árbol de análisis o porque algunas cadenas de entrada no son válidas. A los humanos les gusta la redundancia. Por ejemplo, la mayoría de los humanos encuentran que los operadores binarios son más legibles que un prefijo puro o una notación de sufijo para la aritmética elemental:un+si×(C-re)+mien lugar de (+ a (* b (- c d)) e)o a b c d - * + e +. La notación matemática habitual tiene más redundancia que Lisp (que requiere más paréntesis, pero obtiene aridades variables de forma gratuita, por lo que requiere menos símbolos para expresar expresiones usando aridades grandes) o RPL (que nunca necesita paréntesis). Tal redundancia rara vez es útil para las computadoras, y donde lo es, es decir, cuando puede haber errores en los datos, la lógica de corrección de errores generalmente se mantiene separada del significado funcional de los datos, por ejemplo, utilizando códigos de corrección de errores que se aplican a secuencias de bytes independientemente de lo que representan.

Los formatos binarios generalmente están diseñados para ser compactos, lo que significa pocas características simples del lenguaje, como paréntesis equilibrados que se expresan mediante gramáticas libres de contexto. Además, a menudo es útil que las representaciones binarias de datos sean canónicas, es decir, que tengan una única representación de cada objeto. Esto descarta características a veces redundantes, como paréntesis. Otra consecuencia menos encomiable de tener menos redundancia es que si cada entrada es sintácticamente correcta, ahorra en la comprobación de errores.

Otro factor contra los analizadores no triviales para datos binarios es que muchos formatos binarios están diseñados para ser analizados por código de bajo nivel que le gusta operar en memoria constante con poca sobrecarga. Se prefieren los tamaños fijos cuando corresponde para permitir la repetición arbitraria de un elemento. Un formato como TLV que permite que un analizador de izquierda a derecha asigne primero la cantidad correcta de memoria para un objeto y luego lea la representación del objeto. Analizar de izquierda a derecha es una ventaja porque permite que los datos se procesen como vienen, sin búfer intermedio.

Gilles 'SO- deja de ser malvado'
fuente
¿Cuál es el punto de los dos primeros párrafos? Incluso si no tiene redundancia, necesita un analizador. Además, el primer párrafo es incorrecto: hay ejemplos en los que se permiten todas las palabras pero se analiza para obtener la estructura (por ejemplo, predicción de estructura secundaria de ARN).
Raphael
@Raphael Un analizador no trivial generalmente implica redundancia (sí, como usted señala, hay excepciones). No había considerado lenguajes que no fueron diseñados para humanos ni para computadoras, este es un ejemplo interesante. Los primeros dos párrafos discuten las diferencias típicas entre formatos binarios y legibles por humanos (significado típico de que si busca excepciones, las encontrará).
Gilles 'SO- deja de ser malvado'