<div dir="ltr">Hi Artem, <div><br><div>I'm not sure what the protocol is for posting code here. I was trying to abstract the behaviour of a well-known </div></div><div>in memory key-value store into the following program so this may be too much code to post here. Let me know </div><div>if you want me to give you an even more abstract version. And again, thanks for your help! </div><div><br></div><div>/----------- test.c -------------/ </div><blockquote style="margin:0px 0px 0px 40px;border:none;padding:0px"><div><div><font size="1" face="monospace, monospace">#include<stdio.h> </font></div></div><div><div><font size="1" face="monospace, monospace">#include<string.h> </font></div></div><div><div><font size="1" face="monospace, monospace">#include<stdlib.h> </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">typedef struct _item{ </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">        </span>int key;</font></div></div><div><div><font size="1" face="monospace, monospace">        char value; <span class="" style="white-space:pre">  </span></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">  </span>struct _item * next; </font></div></div><div><div><font size="1" face="monospace, monospace">} item; </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">void taint_add(item ** it); </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">item * global_item_list  = NULL; </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">item * alloc_item(int key, char value) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">   </span>item * new_item = malloc(sizeof(item)); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre"> </span>new_item->key = key; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre"> </span>new_item->value = value; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">     </span>new_item->next = NULL; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>return new_item; </font></div></div><div><div><font size="1" face="monospace, monospace">} </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">item * get_item(int key) {</font></div></div><div><div><font size="1" face="monospace, monospace">      <b><i>  item * list = global_item_list; ---- (D)<span class="" style="white-space:pre"> </span></i></b></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">      </span>while(list) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">           </span>if(key == list->key)</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                   </span>return list;       </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">           </span>list = list->next; <span class="" style="white-space:pre">    </span></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">  </span>} </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>return NULL; </font></div></div><div><div><font size="1" face="monospace, monospace">} </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">void put_item(item * new_item) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">     </span>if(!global_item_list) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">         </span><i><b>global_item_list</b></i> = <i><b>new_item</b></i>; -----<b><i> (C)</i></b> </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">        </span>} </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>else { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">          </span>new_item->next = global_item_list; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">           </span>global_item_list = new_item; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">    </span>}</font></div></div><div><div><font size="1" face="monospace, monospace">        return; </font></div></div><div><div><font size="1" face="monospace, monospace">} <span class="" style="white-space:pre">  </span></font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">int dispatch_op(char * command_str) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre"> </span>char *token;</font></div></div><div><div><font size="1" face="monospace, monospace">   <span class="" style="white-space:pre"> </span>const char s[2] = " "; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">        </span>token = strtok(command_str, s);</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">   </span>int key;</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">  </span>char value; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">     </span>item * it; </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">    </span>if(token == NULL) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">             </span>printf ("[Error] No command entered." </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                         </span>"Please enter a valid command\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">            </span>return 1; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>}</font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace"> <span class="" style="white-space:pre">     </span>if(!strcmp(token, "SET")) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">           </span>/* Grab the key */ </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span>int key; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                </span>token = strtok(NULL, s);</font></div></div><div><div><font size="1" face="monospace, monospace">       <span class="" style="white-space:pre">               </span>if( token == NULL ) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                   </span>printf ("[Error] Invalid number of arguments."</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                                  </span>"Please reenter command with correct params\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                      </span>return 1;  </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span>} else { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                        </span>key = atoi(token); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                      </span>if(key == 0) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                          </span>printf("[Error] Key must be greater than 0\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                               </span>return 1; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                       </span>} </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">               </span>} </font></div></div><div><div><span class="" style="white-space:pre"><font size="1" face="monospace, monospace">               </font></span></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">          </span>/* Grab the value */ </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">            </span>char value; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">             </span>token = strtok(NULL, s);</font></div></div><div><div><font size="1" face="monospace, monospace">       <span class="" style="white-space:pre">               </span>if( token == NULL ) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                   </span>printf ("[Error] Invalid number of arguments." </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                                        </span>"Please reenter command with correct params\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                      </span>return 1; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">               </span>} else { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                        </span>value = *token; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">         </span>}</font></div></div><div><div><span class="" style="white-space:pre"><font size="1" face="monospace, monospace">         </font></span></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">          </span>item * it = alloc_item(key,value); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span><b><i>taint_add(&it); ---- (A) </i></b></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span><b><i>put_item(it);  ----- (B) </i></b></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">         </span>printf("[Success] Item added.\n");  </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">           </span>return 1; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>} else if (!strcmp(token,"GET")) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">            </span>/* Grab the key */ </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span>int key; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                </span>token = strtok(NULL, s);</font></div></div><div><div><font size="1" face="monospace, monospace">       <span class="" style="white-space:pre">               </span>if( token == NULL ) { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                   </span>printf ("[Error] Invalid number of arguments."</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                                  </span>"Please reenter command with correct params\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                      </span>return 1;  </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span>} else { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                        </span>key = atoi(token); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span>} </font></div></div><div><div><span class="" style="white-space:pre"><font size="1" face="monospace, monospace">               </font></span></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">          </span><b><i>item *it = get_item(key);  --- (E) </i></b></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">               </span>if(it != NULL) </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                  </span>printf("[Success] Item Found: Key %d, Value %c\n", it->key, it->value); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">         </span>else printf("[Failure] Item Not found.\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">           </span>return 1; </font></div></div><div><div><font face="monospace, monospace"><font size="1"><span class="" style="white-space:pre">   </span>} </font><span style="font-size:x-small">else if (!strcmp(token, "QUIT")) { </span></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">               </span>printf("GoodBye.\n"); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">         </span>return 0; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>} </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>else { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">          </span>printf("[Error] Unknown command: Enter a valid command\n");</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">             </span>return 1; </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">       </span>} </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">} </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">/* Command are GET, SET, QUIT */ </font></div></div><div><div><font size="1" face="monospace, monospace">void process_command() { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">  </span>char *buffer = NULL;</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">      </span>int read;</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre"> </span>unsigned int len;</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre"> </span>do { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">            </span>do { </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                    </span>printf("Please Enter a command: "</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                                       </span>"GET key::int(>0) | SET key::int(>0) val::char | LIST | QUIT\n");</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                 </span>read = getline(&buffer, &len, stdin);</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">                     </span>buffer[strcspn(buffer, "\n")] = 0;</font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">              </span>} while (-1 == read); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">   </span>} while(dispatch_op(buffer)); <span class="" style="white-space:pre">    </span></font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">        </span>return; </font></div></div><div><div><font size="1" face="monospace, monospace">} </font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace"><br></font></div></div><div><div><font size="1" face="monospace, monospace">int main(int argc, char ** argv){ </font></div></div><div><div><font size="1" face="monospace, monospace"><i><span class="" style="font-weight:bold;white-space:pre">     </span>/* item * A = alloc_item(1,'A'); </i></font></div></div><div><div><font size="1" face="monospace, monospace"><i><span class="" style="white-space:pre">     </span>item * B = alloc_item(2,'B'); </i></font></div></div><div><div><font size="1" face="monospace, monospace"><i><span class="" style="white-space:pre">        </span><b>taint_add(&B); -- (P) </b></i></font></div></div><div><div><font size="1" face="monospace, monospace"><i><span class="" style="white-space:pre"> </span>put_item(A); </i></font></div></div><div><div><font size="1" face="monospace, monospace"><i><span class="" style="white-space:pre"> </span>put_item(B);</i></font></div></div><div><div><font size="1" face="monospace, monospace"><i><span class="" style="white-space:pre">   </span><b>item * it = get_item(2); -- (Q) </b></i></font></div></div><div><div><font face="monospace, monospace"><i><font size="1"><span class="" style="white-space:pre">       </span><b>printf("Value of %d is %c\n", it->key, it->value); --(R) </b></font><span style="font-size:x-small"><b> */</b> </span></i></font></div></div><div><font face="monospace, monospace"><span style="font-size:x-small"><br></span></font></div><div><font face="monospace, monospace"><span style="font-size:x-small"><br></span></font></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">      </span>process_command(); </font></div></div><div><div><font size="1" face="monospace, monospace"><span class="" style="white-space:pre">      </span>return 0; </font></div></div><div><div><font size="1" face="monospace, monospace">} </font></div></div></blockquote><div><br></div><div><br></div><div>I run the analysis using the command:<font face="monospace, monospace" size="1"> /llvm-install/bin/scan-build -k -enable-checker alpha.security.taint.TaintPropagation -enable-checker debug.TaintTest clang `-cc1 -analyzer-max-loop=10` test.c </font></div><div>I have added the function taint_add() as one of the sources of taint inside GenericTaintChecker. I was expecting to see the taint flow from A -> B -> C -> D -> E highlighted above with the reasoning that </div><div>the dispatch_op() function can multiplex between SET(put_item) and GET(get_item) requests and taint introduced though the SET request can flow to global variable and then the result of the PUT request </div><div>but this doesn't happen. </div><div><br></div><div>However, if I uncomment the highlighted commented lines in main, I can see that taint flow from P -> Q -> R. </div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Aug 11, 2016 at 5:04 PM, Artem Dergachev <span dir="ltr"><<a href="mailto:noqnoqneo@gmail.com" target="_blank">noqnoqneo@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On 8/11/16 3:42 PM, Gábor Horváth wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Note that the analyzer do not reason about global variables right now.<br>
</blockquote>
<br></span>
@Gábor: Hmm, what do you mean? :o They're present in the Store and work like all other variables, they're just invalidated too often (on every unmodeled function call). If the variables are also const-qualified, then they shouldn't be invalidated, and should always resolve to their initial value (though i think there were some bugs there).<br>
<br>
@Divya: if you think that your own API functions themselves do unnecessary invalidation (rather than user-defined functions or library functions), then you have an option to `evalCall` them - that's a special checker callback in which you can take care of all modeling, but<span class=""><br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
And also not that there are no guarantees about the coverage. Therr might be code that is not covered by the analysis at all.<br>
</blockquote>
<br></span>
@Gábor: Yeah, it might be that as well. The loop might have been to complex, and the analyzer didn't find the proper path through the loop (loops are currently inlined as well.<br>
<br>
@Divya: you may want to increase the `-cc1 -analyzer-max-loop=4` option to a higher value). In the worst case, i'd have had a look at the ExplodedGraph (<a href="http://clang-analyzer.llvm.org/checker_dev_manual.html#visualizing" rel="noreferrer" target="_blank">http://clang-analyzer.llvm.or<wbr>g/checker_dev_manual.html#visu<wbr>alizing</a>) to see what exactly is going on.<br>
<br>
It might also easily be something else, so if you can post some sample code, we'd probably make a better guess.<br>
</blockquote></div><br></div>