<div dir="ltr"><div><font face="georgia, serif" size="6"><u style="">How To Ask The Analyzer The Smart Way</u></font></div><div><br></div><div>I hope the following writing could help checker developers to make sure they understand the problem by asking the Analyzer what could be the problem.</div><div><br></div><div>-------------<br></div><div><br></div>> How to constrain the size of unknown memory regions, eg. pointed by 'raw' char pointers?<div><br><div>Well, the secret is: you do not. The Analyzer tries to give you the best approximation of your program.</div><div><br></div><div>-------------</div><div><br></div><div>> How should tell the analyzer that the array which is pointed by the pointer holds at least/most N elements?</div><div><br></div><div>The Analyzer denote a pointer with a symbolic value and during the analysis it applies constraints on such symbols on their own will using the core facilities and existing API modeling checkers. If your checker models a function call/nullability, so that you need to explicitly create assumptions you can `assume()` values using the ProgramState, like: `std::tie(StateTrue, StateFalse) = State->assume(Value);`. With that you can force out a state split and if your new assumption of `Value` does not contradict with previous assumptions `StateTrue` holds the assumption, and `StateFalse` holds the assumption negated. If such contradiction happens the return value is a `nullptr`.</div><div><br></div><div>-------------<br></div><div><br></div><div>> What would be the right approach to guide (to constrain the size of a memory region) the analyzer?</div><div><br></div><div>Use [1] checkers and know them well, they guide the Analyzer. Otherwise create your own API modeling checkers.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">If you can't solve a problem, then there is an easier problem you can't solve: find it.</blockquote><div>- George Polya. </div><div><br></div><div>First, let me simplify your problem/example and make sure we can work with it:</div><div>```</div><div><font face="monospace">// RUN: %clang_analyze_cc1 \<br>// RUN: -analyzer-checker=core,unix,debug.ExprInspection \<br>// RUN: -verify %s<br><br>typedef __SIZE_TYPE__ size_t;<br>size_t strlen(const char *);<br><br>void clang_analyzer_printState();<br><br>void test(const char *src) {<br> if (strlen(src) < 10)<br> return;<br><br> clang_analyzer_printState();<br> <b>(void)src;</b><br>}</font><br></div><div>```</div><div><br></div><div>It is a <b>runnable</b> test using `llvm-lit` which dumps out the state of the program:</div><div>- The `core` package models the analysis.</div><div>- The `unix` package models memory and string manipulation.</div><div>- The [2] `debug.ExprInspection` checker / `debug` package defines function calls which could be used to make human-readable what the Analyzer thinks of your program at the moment of the function call.</div><div>- `(void)src` makes sure when we print out the state the Analyzer does not throw away the information of `src`. Without that extra call we would print out the state where dead symbols, such as `src` would be purged out from the analysis.</div><div><br></div><div>It dumps out the following:</div><div>```</div><div><font face="monospace">"program_state": {<br> ...<br> "constraints": [<br> { "symbol": "reg_$0<const char * src>", "range": "{ [1, 18446744073709551615] }" },<br> { <b>"symbol"</b>: "meta_$1{SymRegion{reg_$0<const char * <b>src</b>>},unsigned long}", <b>"range"</b>: "{ [10, 4611686018427387903] }" }<br> ],<br> ...<br>}</font><br></div><div>```</div><div><br></div><div>To continue dig into your example, we need to predefine function signatures, which you can find easily using Microsoft Docs [3]:</div><div>```</div><div><font face="monospace">// RUN: %clang_analyze_cc1 \<br>// RUN: -analyzer-checker=core,unix,debug.ExprInspection \<br>// RUN: -verify %s<br><br>typedef __SIZE_TYPE__ size_t;<br>size_t strlen(const char *);<br><b>char *strncpy(char *dst, const char *src, size_t size);</b><br><br>void clang_analyzer_printState();<br><br>void test(char *dst, const char *src, size_t size) {<br> if (strlen(src) < 10)<br> return;<br><br> <b>strncpy</b>(dst, src, size);<br> clang_analyzer_printState();<br><br> (void)dst; (void)src; (void)size;<br>}</font><br></div><div>```</div><div><br></div><div>With that you could see if the Analyzer cannot model something enough precisely for your needs. With `grep` and GitHub's blame system usually you can find out how such API modeling introduced by an LLVM Phabricator review's link. If you want to learn more about symbolic values please visit section 5 from Artem Dergachev's [4] booklet.</div><div><br></div><div>-------------<br></div></div><div><br></div><div>> How can the analyzer inference such constraint?</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Like magic and unicorns</blockquote><div>and we name it ConstraintManager.</div><div><br></div><div>-------------<br></div><div><br></div><div>> <span style="font-family:monospace">assert(&src[n] - &src[-1]);</span></div><div><span style="font-family:monospace"><br></span></div>I do not get what you are trying to do with this expression. Back in the days I have learnt [5] how to ask questions the smart way, which sounds rude for the first time, but this is the best reading on the web: <a href="http://www.catb.org/esr/faqs/smart-questions.html">http://www.catb.org/esr/faqs/smart-questions.html</a><div><div><br></div><div>-------------<br></div><div><br></div><div>[1] Available Analyzer checkers:</div><div><a href="https://clang.llvm.org/docs/analyzer/checkers.html">https://clang.llvm.org/docs/analyzer/checkers.html</a><br></div><div><br></div><div>[2] Debug checkers - ExprInspection:</div><div><a href="https://clang.llvm.org/docs/analyzer/developer-docs/DebugChecks.html#exprinspection-checks">https://clang.llvm.org/docs/analyzer/developer-docs/DebugChecks.html#exprinspection-checks</a><br></div><div><br></div><div>[3] Microsoft Docs:</div><div><a href="https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/strncpy-strncpy-l-wcsncpy-wcsncpy-l-mbsncpy-mbsncpy-l">https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/strncpy-strncpy-l-wcsncpy-wcsncpy-l-mbsncpy-mbsncpy-l</a><br></div><div><br></div><div>[4] Artem Dergachev's booklet: A Checker Developer's Guide:</div><div><a href="https://github.com/haoNoQ/clang-analyzer-guide/releases">https://github.com/haoNoQ/clang-analyzer-guide/releases</a><br></div><div><br></div>[5] How To Ask Questions The Smart Way:<div><a href="http://www.catb.org/esr/faqs/smart-questions.html">http://www.catb.org/esr/faqs/smart-questions.html</a><br></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Mar 12, 2020 at 1:20 PM Balázs Benics via cfe-dev <<a href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi, checker devs<br><br>TLDR:<br>How to constrain the size of unknown memory regions, eg. pointed by 'raw' char pointers?<br><br>longer version:<br>Working on taint analysis I'm facing with the following problem:<br><br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-family:monospace">void strncpy_bounded_tainted_buffer(char *src, char *dst) {</span><br><span style="font-family:monospace"> // assert(strlen(src) >= 10 && "src must have at leas 10 elements");</span><br><span style="font-family:monospace"> int n;</span><br><span style="font-family:monospace"> scanf("%d", &n);</span><br><span style="font-family:monospace"> if (0 < n && n < 10) {</span><br><span style="font-family:monospace"> strncpy(dst, src, n); // Should we warn or not?</span><br><span style="font-family:monospace"> }</span><br><span style="font-family:monospace">}</span><br></blockquote><br><br>In this example we analyze a function taking two raw pointers, so we don't know how big those arrays are.<br>We will check the `<span style="font-family:monospace">strncpy</span>` call, whether it will access <i>(read and write)</i> only valid memory.<br>We will check the pointers (<span style="font-family:monospace">src</span> and <span style="font-family:monospace">dst</span>) separately by checking if <i>`</i>&src[0]` and <span style="font-family:monospace">`&src[n-1]`</span> would be in bound of the memory region pointed by the pointer. Since the analyzer don't know (both states are non-null), we should check if the `<span style="font-family:monospace">length</span>` parameter is tainted, and if so, we should still issue a warning telling that "String copy function might overflow the given buffer since untrusted data is used to specify the buffer size."<br>Obviously, if the `<span style="font-family:monospace">length</span>` parameter is not tainted, we will assume (conservatively) that the access would be valid.<br><br><br>How should tell the analyzer that the array which is pointed by the pointer holds at least/most N elements?<br>For example in the code above, express something similar via an assertion, like saying that `src` points to a c-string, which has at least 10 + 1 element underlying storage.<br>Although this assertion using `<span style="font-family:monospace">strlen</span>` seems like a solution, unfortunately not applicable for example to the `<span style="font-family:monospace">dst</span>` buffer, which is most likely uninitialized - so not a c-string, in other words calling `<span style="font-family:monospace">strlen</span>` would be undefined behavior.<br><br>The only (hacky) option which came in my mind was to abuse the standard regarding pointer arithmetic.<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style="font-family:monospace">assert(&src[n] - &src[-1]);</span><br></blockquote>The standard is clear about that pointer arithmetic is only applicable for pointers pointing to elements of the same array OR to a hypothetical ONE past/before element of that array.<br><a href="http://eel.is/c++draft/expr.add#4.2" target="_blank">http://eel.is/c++draft/expr.add#4.2</a><br><br>This assertion would be undefined behavior if the size of the array pointed by `<span style="font-family:monospace">src</span>` would be smaller than `<span style="font-family:monospace">n</span>`.<br><br>IMO this looks really ugly.<br>I think that no '<i>annotations</i>' should introduce UB even if that assumption expressed via an annotation is turned out to be <u>invalid</u>.<br><br><br>What would be the right approach to guide (to constrain the size of a memory region) the analyzer?<br>How can the analyzer inference such constraint?<br><div><br></div><div>Thanks Balazs.<br></div></div>
_______________________________________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br>
</blockquote></div>