Pregunta:
Gramática libre de contexto a partir de muestras
mrduclaw
2013-03-31 05:13:13 UTC
view on stackexchange narkive permalink

¿Existe una herramienta disponible que genere una gramática a partir de un corpus de entradas de muestra, similar a lo que hace HotFuzz para los protocolos de red?

Por ejemplo, dada una colección de Archivos MP3, estoy buscando una herramienta que genere una gramática BNF para describir el formato de MP3.

One responder:
Daniel W. Steinbrook
2013-04-02 07:59:33 UTC
view on stackexchange narkive permalink

Yo tampoco lo he usado, pero Peach Fuzzer, en el que se basa HotFuzz, tiene una interfaz gráfica de usuario "Peach Fuzz Bang" para archivos fuzzing.

Tenga en cuenta, sin embargo, los fuzzers intentan generar entradas inválidas que bloquean un programa, no determinan la gramática exacta que describe todas las entradas válidas.

Además, estrictamente hablando, no es matemáticamente posible para hacer lo que estás pidiendo. Si una computadora pudiera aprender un idioma de manera integral simplemente leyendo texto en ese idioma, entonces la traducción automática sería un problema resuelto. (Esta es una analogía un poco pobre ya que no todos los lenguajes humanos están libres de contexto, pero la idea es clara).

Probablemente estoy mostrando mi ignorancia, pero no parece que deba ser un problema tan imposible, ¿verdad? Dado un montón de datos de muestra, debería poder diferenciar y determinar la estructura general (por ejemplo, un encabezado de 4 bytes que permanece igual, seguido de un int de 4 bytes, tal vez le sigue una cadena terminada en NULL, etc.). ¿Por qué sería imposible hacer eso?
@mrduclaw: Es solo el título de su pregunta que es la parte imposiblemente general, y es el tema de [investigación] (http://aclweb.org/anthology-new/O/O06/O06-1004.pdf). Si solo desea averiguar la estructura de encabezado común de un conjunto de archivos binarios, consulte [esta pregunta SO] (http://stackoverflow.com/questions/492751/tools-to-help-reverse-engineer-binary-file -formatos), que tiene algunas buenas respuestas.
Gran sugerencia de papel, parece lejos de ser imposible, ¡gracias!
[El artículo de Angluin sobre L *] (http://www.cse.iitk.ac.in/users/chitti/thesis/references/learningRegSetsFromQueriesAndCounterExamples.pdf) da una prueba de que la inferencia gramatical se puede lograr en tiempo polinomial si un oráculo es disponible para responder consultas de membresía. [Este artículo] (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.53.5084) incluye descripciones y discusión del desempeño de otros algoritmos para inferencia gramatical. Sin embargo, un enfoque utilizado por [Polyglot] (http://repository.cmu.edu/cgi/viewcontent.cgi?article=1007&context=ece) podría escalar mejor.
Aquí hay algunos artículos sobre una técnica para derivar una gramática libre de contexto basada en el análisis binario del motor polimórfico de un virus [[1] (http://ieeexplore.ieee.org/ielx5/6044613/6059944/06059958.pdf? tp = & arnumber = 6059958 & isnumber = 6059944), [2] (http://www.labri.fr/perso/tabary/publis/polysigns.pdf), [3] (http://www.labri.fr/perso/ tabary / publis / nss2011-slides.pdf)]. No estoy seguro de que sea realmente relevante aquí ... Pero, tal vez puedas encontrarle algún uso.


ⓘ
Esta pregunta y respuesta fue traducida automáticamente del idioma inglés.El contenido original está disponible en stackexchange, a quien agradecemos la licencia cc by-sa 3.0 bajo la que se distribuye.
Loading...