Re: [DynInst_API:] Dyninst and Data flow analysis

[Bill Williams <bill@xxxxxxxxxxx>]

On 06/03/2013 10:38 PM, Milind Chabbi wrote:
> I am considering using Dyninst for a binary analysis (not rewriting).
>   My particular use case involves answering questions such as:
> 1. Is the memory address accessed by this instruction loop invariant or not?
> 2. Is the value read/written in this instruction loop invariant or not?
> 3. May/Must given two memory accesses alias?
>
> Does Dyninst have facilities for such data flow analysis on x86_64
> binaries?
Depends on how much effort you're willing to add to our existing tools 
and what quality of results you need; as you know, these are not 
necessarily simple data flow problems.
Our slicer in dataflowAPI will help with all of these, but slicing in 
general is a tricky problem both with respect to how to bound the slice 
and how to handle stack/heap accesses. We make a best effort at tracking 
dependencies through stack slots and punt on the heap; that's a 
long-standing "would be nice if we have time" feature.
General outline of approach:

1) Get effective address expression from InstructionAPI, slice on that 
expression within the loop, verify that all data dependencies are 
external (or on expressions that are themselves loop invariants).
2) As per 1 but for the other operand.
3) Tricky. In cases that can be broken into (base + index), you can use 
slicing to prove that index1 == index2 and base1 == base2; from our 
package of slicing + symbolic evaluation + instruction semantics you 
*could* do pretty much any analysis you wanted. Not going to be easy though.

> -Milind
>
>
> _______________________________________________
> Dyninst-api mailing list
> Dyninst-api@xxxxxxxxxxx
> https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api

--
--bw

Bill Williams
Paradyn Project
bill@xxxxxxxxxxx