Add support for recognizing and propagation error conditions

pgoodman commented 3 years ago

We should be able to mark functions as being no-return, e.g. _Exit, exit, abort, __assert_fail, etc.

We should propagate error-ness as follows:

[ ] A jump to a non-decodable instruction is an error EA
[ ] A jump to an error instruction DestEA is an error EA
[ ] A jump to an error DestEA is an error EA
[ ] A fall-through to an error instruction is a no-return EA
[ ] A fall-through to a non-decodable instruction is a no-return EA
[ ] A fall-through to an error DestEA is an error EA
[ ] A call to an non-decodable instruction DestEA is an error EA
[ ] A call to an error instruction DestEA is an error EA
[ ] A call to an error DestEA is an error EA
[ ] A conditional branch, where TakenEA and NotTakenEA are errors, is also an error EA

Eventually, we'd also want to augment error flows with:

[ ] Have a command-line flag that tells us to include/exclude privileged instructions as decodable
[ ] Introduce semantics support and look for things like dereferencing the NULL pointer, dividing by zero, etc.

Error flows should be omitted from the usual control-flows, as they are guaranteed to error.

stevenagy commented 3 years ago

Should error / no-return EA's be constructed as edgetypes?

pgoodman commented 3 years ago

No, I think it's a relation / property that you'd model. So here's an example of how you could start:

; Tells us whether or not the execution of an the instruction at `EA` is
; guaranteed to lead to an error. An error could be code that can't execute
; (i.e. a non-decodable instruction), or could be something far down the
; line like a jump into a `hlt` instruction.
#local leads_to_error(EA)

; Base case: Something like `foo ; <junk>` where `foo` is a normal instruction.
leads_to_error(InsnEA)
  : instruction(InsnEA, INSN_NORMAL, _)
  , raw_transfer(InsnEA, ToEA, EDGE_FALL_THROUGH)
  , !plausible_instruction(ToEA).

; TODO: more base cases.

; Inductive case for fall-throughs.
leads_to_error(InsnEA)
  : instruction(InsnEA, INSN_NORMAL, _)
  , raw_transfer(InsnEA, ToEA, EDGE_FALL_THROUGH)
  , leads_to_error(ToEA).

; TODO: More inductive cases.

stevenagy commented 3 years ago

I think the following should cover the cases you mentioned above: https://github.com/lifting-bits/dds/blob/master/dds/datalog/instruction.dr#L14 (and onwards).

stevenagy commented 3 years ago

Closing as the following commits address this for now: https://github.com/lifting-bits/dds/commit/ef5ec7220e0f42eb6159d0a287b3dceea142e703 https://github.com/lifting-bits/dds/commit/65c033a8641f3120f0cfe7620f3fceacff2b7fb5

lifting-bits / dds

Add support for recognizing and propagation error conditions #6