Re: [DynInst_API:] Dyninst and Data flow analysis

[Bill Williams <bill@xxxxxxxxxxx>]

On 06/04/2013 02:24 PM, Milind Chabbi wrote:
> Thanks Bill.
>
> Is there a documentation for DataflowAPI or should I browse the source code?
Unfortunately, the thing standing between DataflowAPI and removal of the 
"beta" tag is documentation. Browse the source and ask for help as you 
need it; we've got several people on-list who've used the slicer (and 
other DataflowAPI stuff) and any of us can help you out.
--bw

> -Milind
>
> On Tue, Jun 4, 2013 at 1:09 PM, Bill Williams <bill@xxxxxxxxxxx
> <mailto:bill@xxxxxxxxxxx>> wrote:
>
>     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 <mailto:Dyninst-api@xxxxxxxxxxx>
>         https://lists.cs.wisc.edu/__mailman/listinfo/dyninst-api
>         <https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api>
>
>
>
>     --
>     --bw
>
>     Bill Williams
>     Paradyn Project
>     bill@xxxxxxxxxxx <mailto:bill@xxxxxxxxxxx>
>     _________________________________________________
>     Dyninst-api mailing list
>     Dyninst-api@xxxxxxxxxxx <mailto:Dyninst-api@xxxxxxxxxxx>
>     https://lists.cs.wisc.edu/__mailman/listinfo/dyninst-api
>     <https://lists.cs.wisc.edu/mailman/listinfo/dyninst-api>

--
--bw

Bill Williams
Paradyn Project
bill@xxxxxxxxxxx