Initializer List

This discussion took place in https://reviews.llvm.org/D35216 "Escape symbols when creating std::initializer_list".

It touches problems of modelling C++ standard library constructs in general, including modelling implementation-defined fields within C++ standard library objects, in particular constructing objects into pointers held by such fields, and separation of responsibilities between analyzer's core and checkers.

Artem:

I've seen a few false positives that appear because we construct C++11 std::initializer_list objects with brace initializers, and such construction is not properly modeled. For instance, if a new object is constructed on the heap only to be put into a brace-initialized STL container, the object is reported to be leaked.

Approach (0): This can be trivially fixed by this patch, which causes pointers passed into initializer list expressions to immediately escape.

This fix is overly conservative though. So i did a bit of investigation as to how model std::initializer_list better.

According to the standard, std::initializer_list<T> is an object that has methods begin(), end(), and size(), where begin() returns a pointer to continuous array of size() objects of type T, and end() is equal to begin() plus size(). The standard does hint that it should be possible to implement std::initializer_list<T> as a pair of pointers, or as a pointer and a size integer, however specific fields that the object would contain are an implementation detail.

Ideally, we should be able to model the initializer list's methods precisely. Or, at least, it should be possible to explain to the analyzer that the list somehow "takes hold" of the values put into it. Initializer lists can also be copied, which is a separate story that i'm not trying to address here.

The obvious approach to modeling std::initializer_list in a checker would be to construct a SymbolMetadata for the memory region of the initializer list object, which would be of type T* and represent begin(), so we'd trivially model begin() as a function that returns this symbol. The array pointed to by that symbol would be bindLoc()``ed to contain the list's contents (probably as a ``CompoundVal to produce less bindings in the store). Extent of this array would represent size() and would be equal to the length of the list as written.

So this sounds good, however apparently it does nothing to address our false positives: when the list escapes, our RegionStoreManager is not magically guessing that the metadata symbol attached to it, together with its contents, should also escape. In fact, it's impossible to trigger a pointer escape from within the checker.

Approach (1): If only we enabled ProgramState::bindLoc(..., notifyChanges=true) to cause pointer escapes (not only region changes) (which sounds like the right thing to do anyway) such checker would be able to solve the false positives by triggering escapes when binding list elements to the list. However, it'd be as conservative as the current patch's solution. Ideally, we do not want escapes to happen so early. Instead, we'd prefer them to be delayed until the list itself escapes.

So i believe that escaping metadata symbols whenever their base regions escape would be the right thing to do. Currently we didn't think about that because we had neither pointer-type metadatas nor non-pointer escapes.

Approach (2): We could teach the Store to scan itself for bindings to metadata-symbolic-based regions during scanReachableSymbols() whenever a region turns out to be reachable. This requires no work on checker side, but it sounds performance-heavy.

Approach (3): We could let checkers maintain the set of active metadata symbols in the program state (ideally somewhere in the Store, which sounds weird but causes the smallest amount of layering violations), so that the core knew what to escape. This puts a stress on the checkers, but with a smart data map it wouldn't be a problem.

Approach (4): We could allow checkers to trigger pointer escapes in arbitrary moments. If we allow doing this within checkPointerEscape callback itself, we would be able to express facts like "when this region escapes, that metadata symbol attached to it should also escape". This sounds like an ultimate freedom, with maximum stress on the checkers - still not too much stress when we have smart data maps.

I'm personally liking the approach (2) - it should be possible to avoid performance overhead, and clarity seems nice.

Gabor:

At this point, I am a bit wondering about two questions.

• When should something belong to a checker and when should something belong to the engine? Sometimes we model library aspects in the engine and model language constructs in checkers.
• What is the checker programming model that we are aiming for? Maximum freedom or more easy checker development?

I think if we aim for maximum freedom, we do not need to worry about the potential stress on checkers, and we can introduce abstractions to mitigate that later on. If we want to simplify the API, then maybe it makes more sense to move language construct modeling to the engine when the checker API is not sufficient instead of complicating the API.

Right now I have no preference or objections between the alternatives but there are some random thoughts:

• Maybe it would be great to have a guideline how to evolve the analyzer and follow it, so it can help us to decide in similar situations
• I do care about performance in this case. The reason is that we have a limited performance budget. And I think we should not expect most of the checker writers to add modeling of language constructs. So, in my opinion, it is ok to have less nice/more verbose API for language modeling if we can have better performance this way, since it only needs to be done once, and is done by the framework developers.

Artem: These are some great questions, i guess it'd be better to discuss them more openly. As a quick dump of my current mood:

• To me it seems obvious that we need to aim for a checker API that is both simple and powerful. This can probably by keeping the API as powerful as necessary while providing a layer of simple ready-made solutions on top of it. Probably a few reusable components for assembling checkers. And this layer should ideally be pleasant enough to work with, so that people would prefer to extend it when something is lacking, instead of falling back to the complex omnipotent API. I'm thinking of AST matchers vs. AST visitors as a roughly similar situation: matchers are not omnipotent, but they're so nice.
• Separation between core and checkers is usually quite strange. Once we have shared state traits, i generally wouldn't mind having region store or range constraint manager as checkers (though it's probably not worth it to transform them - just a mood). The main thing to avoid here would be the situation when the checker overwrites stuff written by the core because it thinks it has a better idea what's going on, so the core should provide a good default behavior.
• Yeah, i totally care about performance as well, and if i try to implement approach, i'd make sure it's good.

Artem:

> Approach (2): We could teach the Store to scan itself for bindings to > metadata-symbolic-based regions during scanReachableSymbols() whenever > a region turns out to be reachable. This requires no work on checker side, > but it sounds performance-heavy.

Nope, this approach is wrong. Metadata symbols may become out-of-date: when the object changes, metadata symbols attached to it aren't changing (because symbols simply don't change). The same metadata may have different symbols to denote its value in different moments of time, but at most one of them represents the actual metadata value. So we'd be escaping more stuff than necessary.

If only we had "ghost fields" (https://lists.llvm.org/pipermail/cfe-dev/2016-May/049000.html), it would have been much easier, because the ghost field would only contain the actual metadata, and the Store would always know about it. This example adds to my belief that ghost fields are exactly what we need for most C++ checkers.

Devin:

In this case, I would be fine with some sort of AbstractStorageMemoryRegion that meant "here is a memory region and somewhere reachable from here exists another region of type T". Or even multiple regions with different identifiers. This wouldn't specify how the memory is reachable, but it would allow for transfer functions to get at those regions and it would allow for invalidation.

For std::initializer_list this reachable region would the region for the backing array and the transfer functions for begin() and end() yield the beginning and end element regions for it.

In my view this differs from ghost variables in that (1) this storage does actually exist (it is just a library implementation detail where that storage lives) and (2) it is perfectly valid for a pointer into that storage to be returned and for another part of the program to read or write from that storage. (Well, in this case just read since it is allowed to be read-only memory).

What I'm not OK with is modeling abstract analysis state (for example, the count of a NSMutableArray or the typestate of a file handle) as a value stored in some ginned up region in the store. This takes an easy problem that the analyzer does well at (modeling typestate) and turns it into a hard one that the analyzer is bad at (reasoning about the contents of the heap).

I think the key criterion here is: "is the region accessible from outside the library". That is, does the library expose the region as a pointer that can be read to or written from in the client program? If so, then it makes sense for this to be in the store: we are modeling reachable storage as storage. But if we're just modeling arbitrary analysis facts that need to be invalidated when a pointer escapes then we shouldn't try to gin up storage for them just to get invalidation for free.

Artem:

> In this case, I would be fine with some sort of AbstractStorageMemoryRegion > that meant "here is a memory region and somewhere reachable from here exists > another region of type T". Or even multiple regions with different > identifiers. This wouldn't specify how the memory is reachable, but it would > allow for transfer functions to get at those regions and it would allow for > invalidation.

Yeah, this is what we can easily implement now as a symbolic-region-based-on-a-metadata-symbol (though we can make a new region class for that if we eg. want it typed). The problem is that the relation between such storage region and its parent object region is essentially immaterial, similarly to the relation between SymbolRegionValue and its parent region. Region contents are mutable: today the abstract storage is reachable from its parent object, tomorrow it's not, and maybe something else becomes reachable, something that isn't even abstract. So the parent region for the abstract storage is most of the time at best a "nice to know" thing - we cannot rely on it to do any actual work. We'd anyway need to rely on the checker to do the job.

> For std::initializer_list this reachable region would the region for the > backing array and the transfer functions for begin() and end() yield the > beginning and end element regions for it.

So maybe in fact for std::initializer_list it may work fine because you cannot change the data after the object is constructed - so this region's contents are essentially immutable. For the future, i feel as if it is a dead end.

I'd like to consider another funny example. Suppose we're trying to model

std::unique_ptr. Consider::

  void bar(const std::unique_ptr<int> &x);

  void foo(std::unique_ptr<int> &x) {
    int *a = x.get();   // (a, 0, direct): &AbstractStorageRegion
    *a = 1;             // (AbstractStorageRegion, 0, direct): 1 S32b
    int *b = new int;
    *b = 2;             // (SymRegion{conj_$0<int *>}, 0 ,direct): 2 S32b
    x.reset(b);         // Checker map: x -> SymRegion{conj_$0<int *>}
    bar(x);             // 'a' doesn't escape (the pointer was unique), 'b' does.
    clang_analyzer_eval(*a == 1); // Making this true is up to the checker.
    clang_analyzer_eval(*b == 2); // Making this unknown is up to the checker.
  }

The checker doesn't totally need to ensure that *a == 1 passes - even though the pointer was unique, it could theoretically have .get()-ed above and the code could of course break the uniqueness invariant (though we'd probably want it). The checker can say that "even if *a did escape, it was not because it was stuffed directly into bar()".

The checker's direct responsibility, however, is to solve the *b == 2 thing (which is in fact the problem we're dealing with in this patch - escaping the storage region of the object).

So we're talking about one more operation over the program state (scanning reachable symbols and regions) that cannot work without checker support.

We can probably add a new callback "checkReachableSymbols" to solve this. This is in fact also related to the dead symbols problem (we're scanning for live symbols in the store and in the checkers separately, but we need to do so simultaneously with a single worklist). Hmm, in fact this sounds like a good idea; we can replace checkLiveSymbols with checkReachableSymbols.

Or we could just have ghost member variables, and no checker support required at all. For ghost member variables, the relation with their parent region (which would be their superregion) is actually useful, the mutability of their contents is expressed naturally, and the store automagically sees reachable symbols, live symbols, escapes, invalidations, whatever.

> In my view this differs from ghost variables in that (1) this storage does > actually exist (it is just a library implementation detail where that storage > lives) and (2) it is perfectly valid for a pointer into that storage to be > returned and for another part of the program to read or write from that > storage. (Well, in this case just read since it is allowed to be read-only > memory).

> What I'm not OK with is modeling abstract analysis state (for example, the > count of a NSMutableArray or the typestate of a file handle) as a value stored > in some ginned up region in the store.This takes an easy problem that the > analyzer does well at (modeling typestate) and turns it into a hard one that > the analyzer is bad at (reasoning about the contents of the heap).

Yeah, i tend to agree on that. For simple typestates, this is probably an overkill, so let's definitely put aside the idea of "ghost symbolic regions" that i had earlier.

But, to summarize a bit, in our current case, however, the typestate we're looking for is the contents of the heap. And when we try to model such typestates (complex in this specific manner, i.e. heap-like) in any checker, we have a choice between re-doing this modeling in every such checker (which is something analyzer is indeed good at, but at a price of making checkers heavy) or instead relying on the Store to do exactly what it's designed to do.

> I think the key criterion here is: "is the region accessible from outside > the library". That is, does the library expose the region as a pointer that > can be read to or written from in the client program? If so, then it makes > sense for this to be in the store: we are modeling reachable storage as > storage. But if we're just modeling arbitrary analysis facts that need to be > invalidated when a pointer escapes then we shouldn't try to gin up storage > for them just to get invalidation for free.

As a metaphor, i'd probably compare it to body farms - the difference between ghost member variables and metadata symbols seems to me like the difference between body farms and evalCall. Both are nice to have, and body farms are very pleasant to work with, even if not omnipotent. I think it's fine for a FunctionDecl's body in a body farm to have a local variable, even if such variable doesn't actually exist, even if it cannot be seen from outside the function call. I'm not seeing immediate practical difference between "it does actually exist" and "it doesn't actually exist, just a handy abstraction". Similarly, i think it's fine if we have a CXXRecordDecl with implementation-defined contents, and try to farm up a member variable as a handy abstraction (we don't even need to know its name or offset, only that it's there somewhere).

Artem:

We've discussed it in person with Devin, and he provided more points to think about:

• If the initializer list consists of non-POD data, constructors of list's objects need to take the sub-region of the list's region as this-region In the current (v2) version of this patch, these objects are constructed elsewhere and then trivial-copied into the list's metadata pointer region, which may be incorrect. This is our overall problem with C++ constructors, which manifests in this case as well. Additionally, objects would need to be constructed in the analyzer's core, which would not be able to predict that it needs to take a checker-specific region as this-region, which makes it harder, though it might be mitigated by sharing the checker state traits.
• Because "ghost variables" are not material to the user, we need to somehow make super sure that they don't make it into the diagnostic messages.

So, because this needs further digging into overall C++ support and rises too many questions, i'm delaying a better approach to this problem and will fall back to the original trivial patch.