Re: [DynInst_API:] Dyninst and Data flow analysis

[Bill Williams <bill@xxxxxxxxxxx>]

On 06/07/2013 05:04 PM, Milind Chabbi wrote:
> Thanks Bill.
>
> I have more questions:
>
> Wrt slicing and flow of values through memory (stack/heap) what kind of
> assumptions does dataflowAPI make wrt multi-threading?
> Are heap locations that are targets of an atomic instructions assumed to
> contain UNKNOW values even if a known value was written to the location?
>
> In fact, in my use case, I am looking for ignoring multi-threading. That
> is, I am expecting the dataflowAPI to assume that a value written to a
> location will be same when read later even if in real executions another
> thread could change the value.
We make no assumptions about multithreading, and we don't presently 
disambiguate heap locations IIRC--you can of course do that on top of 
dataflowAPI based on whatever analysis you want.
--bw

> -Milind
>
> On Tue, Jun 4, 2013 at 4:40 PM, Bill Williams <bill@xxxxxxxxxxx
> <mailto:bill@xxxxxxxxxxx>> wrote:
>
>     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>
>         <mailto: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>
>         <mailto:Dyninst-api@xxxxxxxxxxxxx <mailto:Dyninst-api@xxxxxxxxxxx>>
>         https://lists.cs.wisc.edu/____mailman/listinfo/dyninst-api
>         <https://lists.cs.wisc.edu/__mailman/listinfo/dyninst-api>
>
>
>         <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>
>         <mailto:bill@xxxxxxxxxxx <mailto:bill@xxxxxxxxxxx>>
>              ___________________________________________________
>              Dyninst-api mailing list
>         Dyninst-api@xxxxxxxxxxx <mailto:Dyninst-api@xxxxxxxxxxx>
>         <mailto:Dyninst-api@xxxxxxxxxxxxx <mailto:Dyninst-api@xxxxxxxxxxx>>
>         https://lists.cs.wisc.edu/____mailman/listinfo/dyninst-api
>         <https://lists.cs.wisc.edu/__mailman/listinfo/dyninst-api>
>              <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>

--
--bw

Bill Williams
Paradyn Project
bill@xxxxxxxxxxx