Re: [DynInst_API:] Dyninst and Data flow analysis

[Milind Chabbi <Milind.Chabbi@xxxxxxxx>]

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.

-Milind

On Tue, Jun 4, 2013 at 4:40 PM, Bill Williams <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>> 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@xxxxxxxxedu>
        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@xxxxxxxxedu>
    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