<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
Dear Ben,<br>
<br>
Just a few comments on DSA:<br>
<br>
1) I'll try out your example C++ code below and see if I can get the
same results that you do. However, I'm at a conference right now
(Usenix Security), so I don't know exactly when I'll get to it.<br>
<br>
2) DSA can get pessimistic results when dealing with external code
(as Andrew described). It is designed for whole program analysis,
meaning that the entire program should be available (e.g., no
variables defined in other compilation units). Can you:<br>
<br>
a) Modify your example so that all variables are internally
defined. You may need to use volatile keywords or printf() to
ensure that dead code isn't eliminated.<br>
<br>
b) Make sure that you run the -internalize pass before running your
analysis to make sure that all variables are marked with internal
linkage.<br>
<br>
3) As an FYI, we just ported DSA from LLVM 2.7 to LLVM mainline last
week and haven't had time to shake it down and see how well it is
working. We'll be shaking down mainline DSA as we integrate it into
an optional libLTO replacement for use with the SAFECode memory
safety compiler. DSA for LLVM 2.7 is still available in the
release_27 branch of the poolalloc project.<br>
<br>
-- John T.<br>
<br>
On 8/10/11 8:37 AM, Ben Liblit wrote:
<blockquote cite="mid:4E42A5B3.7090702@cs.wisc.edu" type="cite">In
an earlier message
(<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042298.html">http://lists.cs.uiuc.edu/pipermail/llvmdev/2011-August/042298.html</a>),
Andrew Lenharth suggested that EQTDDataStructures (from the
poolalloc project) may only try to resolve indirect function
calls. However, I am now finding that the generated DSCallGraph
over-approximates the callees in a very simple indirect call.
Some over-approximation is unavoidable, but this case seems simple
enough that any reasonable analysis ought to have been able to
give the exact, correct answer.
<br>
<br>
My example C++ source file, compiled to bitcode using clang from
the current llvm trunk, is as follows:
<br>
<br>
struct Base
<br>
{
<br>
virtual void virt();
<br>
};
<br>
<br>
void Base::virt()
<br>
{
<br>
}
<br>
<br>
void red();
<br>
void blue();
<br>
<br>
extern volatile int unknown;
<br>
extern Base *base;
<br>
<br>
void test()
<br>
{
<br>
base->virt();
<br>
(unknown ? red : blue)();
<br>
}
<br>
<br>
Observe that we have a class with a virtual method, and two
indirect calls: one through a vtable to that virtual method, and
another which is a simple non-deterministic choice between two
possible function pointers. I can understand an inexact
(over-approximating) set of callees for the vtable call, as that
is rather complex at the bitcode level. However, I am very
surprised to see an over-approximation at the second indirect
call, which is merely picking between two possible values:
<br>
<br>
%11 = phi void ()* [ @red(), %8 ], [ @blue(), %9 ] #
demangled
<br>
call void %11()
<br>
<br>
Yet my DSCallGraph tester code reports that this instruction might
call either red(), blue(), or Base::virt(). I am at a loss to
explain why.
<br>
<br>
Equally strange: if I comment out the "base->virt();" call,
then DSCallGraph *does* give the expected answer that "(unknown ?
red : blue)()" could call either red() or blue() but not
Base::virt(). Somehow having that vtable-based call present forces
the other call to be unexpectedly conservative in its
over-approximation.
<br>
<br>
Source code for my DSCallGraph tester is attached below. I'd be
most grateful for any clues you good people can provide.
<br>
<br>
Thanks,
<br>
Ben
<br>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>