[cfe-dev] On heap variables and Clang SA

[Manuel Klimek]

+jordan who has more context, too (Bhargava has expressed interest in
helping to fix the remaining problems)
(cc' delesley mainly for FYI, as he was curious about some of the
limitations of the C++ cfg)

The state of the temporary destructor problem is the following (Jordan will
correct me if I'm wrong):
Currently, the SA doesn't cannot inline (which in SA terms means
"symbolically execute") constructors and destructors of temporary values of
class type due to a couple of problems.

1. The CFG doesn't handle lifetime-extended temporaries correctly.
I had a patch out that addressed this (http://reviews.llvm.org/D4706); look
at the changes to CFG.cpp for what the CFG changes necessary here.
Basically, the core of the problem is that lifetime extended temporaries
have a rather complex encoding in clang's AST, and one has to actually run
over the full statement to see what comes out as liftime extended; to
construct the CFG, the static analyzer runs over the AST multiple times
(iirc):
a) it figures out the scopes needed (for this it needs to figure out which
variables are lifetime extended)
b) it runs again to fill in the scopes
c) during b) it visits parts again to figure out the temporary destructors
that need to run
The fact that it visits multiple times makes the code contain a bit of
duplication (see the patch) that I wanted to remove, but never got around
to. I think the patch was pretty close to being able to be submitted, and I
don't fully remember what was missing (iirc some tests were breaking and I
didn't know how to deal with it).
I think getting that patch submitted would be a great way to get started on
this :)

2. The static analyzer has an incorrect model for the representation of
temporaries; it encodes them as immutable symbolic values, which they are
not (they have memory regions that the constructor / destructor or other
methods on the temporary need to work on). This is a rather intricate
change. During the last LLVM dev meeting, Jordan had hacked together a
proof of concept for some of this, but so far I haven't gotten back around
to pull out all those patches, understand them, and clean them up (patch
from Jordan from back then attached).

3. An idea for an intermediate step towards (1) was to only inline
temporary constructors/destructors if we know they are not bound to
parameters (which is where the problem with the memory region hits). Patch
http://reviews.llvm.org/D4740 was an attempt to go that way (this is
similar as the patch in (1)).

Let me know if you have more questions :)

Cheers,
/Manuel

On Tue, Mar 17, 2015 at 4:02 PM Manuel Klimek <klimek at google.com> wrote:

> On Tue, Mar 17, 2015 at 4:00 PM Bhargava Shastry <
> bshastry at sec.t-labs.tu-berlin.de> wrote:
>
>> On a tangent, does Google use Clang SA on large codebases esp. Chromium
>> that has a massive C++ LoC count? If not, what are the top reasons for
>> not doing so? Lack of C++ support seems to be the Google position on
>> this [1] but am wondering if that is the only reason.
>>
>
> Yes, this is the only reason; we'd *love* to be able to use it. I already
> shot considerable time and effort into trying to get this good enough, but
> I think I'd need to spend another couple of weeks, which I currently just
> don't have.
>
>
>>
>> [1]: https://code.google.com/p/chromium/wiki/ClangStaticAnalyzer
>>
>> Regards,
>> Bhargava
>>
>> On 03/17/2015 03:00 PM, Manuel Klimek wrote:
>> > On Tue, Mar 17, 2015 at 2:50 PM Bhargava Shastry
>> > <bshastry at sec.t-labs.tu-berlin.de
>> > <mailto:bshastry at sec.t-labs.tu-berlin.de>> wrote:
>> >
>> >     Hi,
>> >
>> >     On 03/17/2015 01:09 PM, Manuel Klimek wrote:
>> >     > How can you prove a comparison against garbage value from that
>> code?
>> >     > Seems like somebody can set m_x to anything between the
>> >     constructor and
>> >     > the call to method.
>> >     > If you want to catch this, you'll at least need:
>> >     > void f() {
>> >     >   foo f;
>> >     >   f.method();
>> >     > }
>> >
>> >     Apologies for having left out the crucial function that
>> instantiates a
>> >     foo object. Agree that this is the missing piece.
>> >
>> >     > ... and then the SA needs to "inline" both the call to the
>> constructor
>> >     > and the method call to see the problem.
>> >
>> >     My understanding is that, during symbolic execution, Clang SA
>> ``visits"
>> >     function calls in the procedure under analysis. So, in the function
>> void
>> >     f() above, Clang SA would metaphorically step into foo's
>> constructor and
>> >     subsequently method() and prove garbage value in two steps i.e.,
>> >
>> >
>> > Yes, that's what the SA calls "inlining". I agree that it's confusing :)
>> >
>> >
>> >
>> >     Step 1. Call to f.method() from void f()
>> >     Step 2. Garbage value comparison in method()
>> >
>> >     Is inlining how Clang SA really does this? Afaik, Clang SA visits
>> the
>> >     call graph for a translation unit in topological order. In the
>> example,
>> >     this means, when void f() is being analyzed, both ctor declaration
>> and
>> >     method declarations would be visited, no?
>> >
>> >
>> > Well, it depends. Whether the SA drills into a function depends on many
>> > things.
>> >
>> >
>> >
>> >
>> >     Regards,
>> >     Bhargava
>> >
>> >     --
>> >     Bhargava Shastry <bshastry at sec.t-labs.tu-__berlin.de
>> >     <mailto:bshastry at sec.t-labs.tu-berlin.de>>
>> >     Security in Telecommunications
>> >     TU Berlin / Telekom Innovation Laboratories
>> >     Ernst-Reuter-Platz 7, Sekr TEL 17 / D - 10587 Berlin, Germany
>> >     phone: +49 30 8353 58235
>> >
>>
>> --
>> Bhargava Shastry <bshastry at sec.t-labs.tu-berlin.de>
>> Security in Telecommunications
>> TU Berlin / Telekom Innovation Laboratories
>> Ernst-Reuter-Platz 7, Sekr TEL 17 / D - 10587 Berlin, Germany
>> phone: +49 30 8353 58235
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150703/c31a7c40/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: params-by-value.patch
Type: text/x-patch
Size: 13527 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20150703/c31a7c40/attachment.bin>