Say you are parsing a complicated binary file but there is 1 extra byte inserted somewhere. This could completely mess up the entire parse, but if you just looked ahead one token you would see the whole file is in tact minus that extra byte (or bit, whatever). You could have a record in the binary file like this:

  name: foo
  offset: 12
  length: 100
  x: 10
  y: 20
  z: 15
  x: 0
  y: 0
  z: 15
  name: bar
  filter: abc

And it would end up looking something like this in the working case (in bit form):

foo 12 100 10 20 15 0 0 15 bar abc ...

But if you inserted another value or set of bits in there, it might look like:

foo 12 100 10 20 143901 15 0 0 15 bar abc ...

My question is what the state of the art is regarding how to print out helpful error messages that say stuff like "it looks like record 1 is split into two parts accidentally, by value 143901", or at least show that table "foo" and table "bar" are both present in the binary (even though that inserted value throws it off).

Wondering what sort of research exists on this topic and how far they've come in making the user experience better in terms of error messages. The naive approach is to say "Unknown token 143901 found in table foo", and not even recognize that table "bar" is present. But I've noticed some font parsers are pretty smart in that they can at least get notified of all the records/tables in the binary, and most of their fields, even if the fields have the wrong length or size or are misplaced. I'm wondering if this is just an ad-hoc thing or there is any science or research around it.

  • $\begingroup$ Depending on the grammar, you may be able to modify the CYK algorithm to find an inserted terminal symbol. $\endgroup$ – Pseudonym Jan 30 '19 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.