<br><br><div class="gmail_quote">在 2011年6月2日 下午3:36，Ted Kremenek <span dir="ltr"><<a href="mailto:kremenek@apple.com" target="_blank">kremenek@apple.com</a>></span>写道：<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word"><div><div><div>On Jun 1, 2011, at 7:04 PM, 章磊 wrote:</div><br><blockquote type="cite"><div> </div>
<div class="gmail_quote">2011/6/2 Ted Kremenek <span dir="ltr"><<a href="mailto:kremenek@apple.com" target="_blank">kremenek@apple.com</a>></span><br>
<blockquote class="gmail_quote" style="padding-left:1ex;margin:0px 0px 0px 0.8ex;border-left:#ccc 1px solid">
<div style="word-wrap:break-word">
<div>
<div>
<div>On May 30, 2011, at 10:48 PM, 章磊 wrote:</div><br>
<blockquote type="cite"><span style="word-spacing:0px;font:medium Helvetica;text-transform:none;text-indent:0px;white-space:normal;letter-spacing:normal;border-collapse:separate">Soon i found i was wrong in step 1, i should not use any structure in checker to record path-sensitive states. So i need other ways to handle this:<br>
<ol>
<li>It seems ok that only to update LocalPathMap when end path(so we can record in GRState until the path analysis finished), but how should we take care of the dead symbols? Maybe i could keep that dead symbols instead of removing them?</li>
<li>Keep the <CE, CheckedReturnState> in GRState, so we get it over. But how to effectively keep these information.</li></ol></span><br></blockquote></div><br>
<div><br></div></div>
<div>Hi Lei,</div>
<div><br></div>
<div>Besides aggregating statistics in checkEndPath, another option is to also doing this in checkDeadSymbols. You then don't need to worry about symbols that have been removed from GRState by the time you reach checkEndPath, since you've already done the aggregation. Of course this influences your counting, but in all fairness we aren't enumerating all paths explicitly anyway, so your counts are directly influenced by how we explore paths, which paths are explored, and how paths are coalesced.</div>
<div><br></div><font color="#888888">
<div>Ted</div></font></div></blockquote></div>
<div> </div>
<div>
<div>Hi Ted,</div>
<div> </div>
<div>It's ok to do aggregating in checkDeadSymbols, and that's how i do in my patch.</div></div></blockquote><div><br></div></div><div><div>Hi Lei,</div><div><br></div><div>I don't see that. I see a call to updateCRState, and that sets an entry in LocalPathMap, but I don't see that as counting the number of times a given CallExpr's return value is checked. Is it meant just to record that the value was checked on a given path?</div>
<div><br></div><div>I'm concerned that LocalPathMap isn't the right model of what you want. The analyzer doesn't trace out all paths individually; it will coalesce paths together as it sees them having the same state. It is possible by the time you reach a call to 'checkEndPath' that an infinite number of paths were coalesced together into one by the time you hit the end of a function.</div>
</div><div><br><blockquote type="cite"><div><div> My problem is if we do so, the deadsymbols are path-related, so we must keep the statistics in GRState instead of checker itself. </div></div></blockquote><div>
<br></div></div><div>Why? I'm really confused here.</div><div><br></div><div>I think trying to collect statistics in GRState itself is inherently the wrong approach. Statistics should be about aggregating what you have observed; the checker itself should only focus on the semantics, which in this case is whether or not a return value was checked.</div>
<div><div><br></div><blockquote type="cite"><div>
<div>Is it ok to add some GRState like llvm::immutablemap<CE, CheckedReturnState>, without related to some symbols?</div></div></blockquote><div><br></div></div><div>Yes, but what would it record? What would it represent?</div>
<div><br><blockquote type="cite"><div><div> Or we must keep the GRState like llvm::immutablemap<sym, llvm::DenseMap<CE, CheckedReturnState>>?<br clear="all"></div></div></blockquote></div></div><br>
<div>No, that would not be a good approach. DenseMap is not an immutable data structure, and should not be a value in ImmutableMap.</div><div><br></div><div>Stepping back… how are you trying to count things? A few concerns come to mind…</div>
<div><br></div><div>1) If you are trying to count statistics along individual paths, your current approach isn't really working as you intend. You are essentially relying not he analyzer exploring the state space in a particular way, and (as I've said before) you aren't actually enumerating individual paths. This means the attempt to use LocalPathMap to count such statistics is inherently not measuring per-path information.</div>
<div><br></div><div>2) Even if we could enumerate all paths, is counting them individually really the right answer? There could be an infinite number of paths.</div><div><br></div><div>3) Paths don't measure everything, and they can really over count the same cases.</div>
<div><br></div><div>I think you can make counting far more simple, and simplify your checker.</div><div><br></div><div>Here's my suggestion:</div><div><br></div><div>1) Have the checker track the CheckedReturnState for each symbol, as it does now.</div>
<div><br></div><div>2) When a symbol is dead, or we reach the end of a path, count it in the following way…</div><div><br></div><div> void processSymbol(const GRState *state, SymbolRef Sym) {</div><div> const CheckedReturnState *CS = state->get<CheckedReturnState>(Sym))</div>
<div> if (!CS)</div><div> return;</div><div> std::pair<unsigned,unsigned> &stats = CheckedSymStatistics[Sym];</div><div> if (CS->isChecked())</div><div> stats.first++;</div><div> else</div><div>
stats.second++;</div><div> }</div><div><br></div><div>This will cause you to get statistics for each symbol. The next stage is then to aggregate them per call site.</div><div><br></div><div> void aggregateByCallSite() {</div>
<div> for (llvm::DenseMap<SymbolRef, std::pair<unsigned, unsigned> >::iterator i = CheckedStatistics.begin(); … ) {</div><div> SymbolRef sym = i->first;</div><div> std::pair<unsigned, unsigned> stats = i->second;</div>
<div> </div><div> // Compute normalized statistics for that symbol.</div><div> double sum = stats.first + stats.second;</div><div> std::pair<double, double> normalizedStats(stats.first / sum, stats.second / sum);</div>
<div><br></div><div> // Aggregate that count into the call site count.</div><div> const CallExpr *CE = getCallSite(sym);</div><div> std::pair<double, double> &callsiteStat = CheckedCallsiteStatistics[CE];</div>
<div> callsiteStat.first += normalizedStats.first;</div><div> callsiteStat.second += normalizedStats.second;</div><div> }</div><div> // then loop over CheckedCallSiteStatistics and normalize the statistics for each entry</div>
<div> }</div><div><br></div><div>I've left some details out, but basically there are a variety of ways to go from a symbol to the original call site. Either we can record it in a DenseMap (on the side), or if it is a conjured symbol, we can look at the symbol itself to figure out where it came from.</div>
<div><br></div><div>How this counting works:</div><div><br></div><div>(a) Paths help us figure out the behavior of a given symbol. Since counting paths is problematic, we just normalize the counts for a given symbol. This essentially gives us a probability distribution.</div>
<div><br></div><div>(b) Aggregating normalized counts for symbols into their CallExprs gives us "counts" for a specific CallExpr. This is an arbitrary choice to weigh symbols in this way, but it causes spurious paths to not be over counted.</div>
<div><br></div><div>(c) Normalizing the aggregated counts for CallExprs gives us another probability distribution. It is basically the probability, for a given CallExpr, whether its value was checked, factoring out some redundancy from multiple paths.</div>
<div><br></div><div>(d) Using the normalized counts (probability distribution) for CallExprs, each CallExpr then has a single count, which you can then use to count whether or not a given function has it's return value checked or not.</div>
<div><br></div><div>This counting strategy obviously biases towards inferring properties of functions that are *called in more places* versus *appear in more paths*, which I think is a better balance than trying to make sense of the different paths explored by the analyzer. It also allows you to skirt the path explosion problem entirely. As long as you think you have traced a "representative set of paths", the statistics will yield a confidence measure in how likely a given function's return value should be checked, regardless of whether or not you were able to evaluate all paths (which IMO isn't terribly relevant, as long as you are able to collect representative evidence of behavioral trends in the code).</div>
<div><br></div><div>What do you think? Sorry for sounding so aggressive; it's late here and I'm tired (so my wording isn't as finessed as I would like), but I wanted to strongly get across that I think counting needs to not be so biased by how we count paths. Of course you are free to disagree.</div>
<div><br></div><div>Cheers,</div><div>Ted</div></div></blockquote></div><br>Hi Ted,<div><br></div><div>Thank you very much for your reply and sorry for misunderstanding the word "<span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">aggregate</span>".</div>
<div><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse"><br></span></div><div><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse">I thought that we can do aggregation only when a path is fully analyzed, so when you mention the aggregation in checkDeadSymbols, i didn't get what you mean to do.</span></div>
<div><br></div><div>I think this counting strategy is great, but i have a little problem: <br><br>IMO, it's a trade-off between counting statistics along individual paths and counting statistics in your way. When there is no path explosion, they give the same counts. But when the path explodes, they works different.<br>
<br>In the first way, we will fully analyze part of all the paths and we can give the accurate results of those paths. But we will leave out some paths because of the step limit and the analyzer should work in a particular way.<br>
In the second way, we do not fully analyze a path, we will call checkEndPath while we are not meet the actual path end, so we<span class="short_text" id="result_box" lang="en"><span class="hps" title="点击可显示其他翻译"> can not guarantee the states we are counting are totally right(the aggregation in checkDeadSymbols is ok, since all the dead symbols will not be checked; but in checkEndPath some symbols may be checked after this "step limited end path"). And could this results be the </span></span>"representative evidence of behavioral trends"<span class="short_text" id="result_box" lang="en"><span class="hps" title="点击可显示其他翻译"> ?<br>
<br>If the second way is ok, and since we should not force the analyzer to </span></span>exploring the state space in a particular way, i will do it in the second way.<br></div><div><br>-- <br>Best regards!<br><br>Lei Zhang<br>
</div>