Traces of SVal in BugReporterVisitor

Clang Frontend
#1

I am trying to write a new BugReporterVisitor to mark the traces of an SVal.
This BugReporterVisitor will be created an SVal usage causes a report, and
it needs to mark the traces of this SVAL.

In the following example, when checking the function call in line 5, I can
see that this is an allocation and by looking at the SVal of the argument, I
see that the allocation is of 0 bytes:

1 void *f(int i) {
2 int a = 0;
3 int b = a/i;
4 int c = b;
5 return malloc(c);
6 }

In the report for line 5 I would like to mark all the expressions that led
to the computation of the SVal.

My questions:
1. Can any of the existing BugReporterVisitor assist me?
2. If not, can anyone suggest guidelines to coding such a
BugReporterVisitor?

Thanks, Gerard.

#2

I am trying to write a new BugReporterVisitor to mark the traces of an SVal.
This BugReporterVisitor will be created an SVal usage causes a report, and
it needs to mark the traces of this SVAL.

In the following example, when checking the function call in line 5, I can
see that this is an allocation and by looking at the SVal of the argument, I
see that the allocation is of 0 bytes:

1 void *f(int i) {
2 int a = 0;
3 int b = a/i;
4 int c = b;
5 return malloc(c);
6 }

In the report for line 5 I would like to mark all the expressions that led
to the computation of the SVal.

My questions:

  1. Can any of the existing BugReporterVisitor assist me?

No, we do not have any visitors that track ALL the expressions that participate in a computation of a particular value. However, marking a symbol as interesting in the BugReport (BugReport::markInteresting) is intended to address this case. Have you tried marking your symbol as interesting? Is it sufficient?

  1. If not, can anyone suggest guidelines to coding such a
    BugReporterVisitor?

The amount of tracking we can do is bounded by the info recorded in ExplodedNodes. For example, we should be able to identify the ExplodedNode where the value (‘0’) was first assigned to the symbol which we are tracking, as this information will be recoded in the constraint manager.

See MallocChecker.cpp, BugReporterVisitors.cpp for more info and examples of the visitors.

Cheers,
Anna.

#3

Hi Gerard, Anna,

I have been trying to do the same thing, or should I say "failing to do the
same thing..." :slight_smile:

I tried adding a checker that will add sval-s to the state as they are
created, and then let the BugReporterVisitor trace the state in which they
were added. This requires a ProgramStateTrait that is known both to the
checker and to the visitor, and though I try following the Taint examole, I
am currently stuck in this direction too.

I also tried marking the sval (and the sval->getAsSymbol()) as important, as
Anna suggested, but that didn't seem to do anything... I think it would have
satisfied me, but I cannot make it work.
Anna, Can you please help here?

Thanks, Yuval.

#4

Thanks Anna.

I did try the "mark interesting" and it didn't do anything.
Could you elaborate in this direction?

Many thanks, Gerard.

#5

You both mention tracking SVals. I just want to highlight that SVals are transient values, so symbols or regions should be tracked (added to state) instead. See Representing Values here:
http://clang-analyzer.llvm.org/checker_dev_manual.html

You can take a look at visitors implemented in BugReporterVisitors and add the ones that are useful for your checker on BugReport creation. For example, DereferenceChecker and DivZeroChecker call bugreporter::trackNullOrundefValue helper, which adds a few visitors to the bug report. It contains heuristics, which decide what expressions along the path would be important to show when the user needs an explanation on why a an expression evaluates to zero or is undefined.

You can play with the existing checkers to see what to expect. For example:
// Null ptr dereference
int f(int i) {
  int *a = 0;
  int *c = a;
  return *c;
}

/Users/zaks/tmp/ex.c:26:5: note: Variable 'a' initialized to a null pointer value
  int *a = 0;
  ^
/Users/zaks/tmp/ex.c:28:5: note: Variable 'c' initialized to a null pointer value
  int *c = a;
  ^
/Users/zaks/tmp/ex.c:29:12: note: Dereference of null pointer (loaded from variable 'c')
  return *c;
         ^

The original example, has a division operation "int b = a/i;". Here, the analyzer doesn't even know that 'b' is zero. (Due to constraint manager not modeling division.)
int f2(int i) {
  int a = 0;
  int b = a/i;
  int c = b;
  return 5/c;
}
// no warning reported

Hi Gerard, Anna,

I have been trying to do the same thing, or should I say "failing to do the
same thing..." :slight_smile:

I tried adding a checker that will add sval-s to the state as they are
created, and then let the BugReporterVisitor trace the state in which they
were added. This requires a ProgramStateTrait that is known both to the
checker and to the visitor, and though I try following the Taint examole, I
am currently stuck in this direction too.

If the notes you are trying to add are checker-specific, you need to implement a visitor in the same file as the checker. The ProgramStateTrait will be visible. See Malloc checker and RetainCount checker - they both have custom visitors.

If the notes are generic (could apply to symbols from any checker). You should add/enhance visitors in BugReporterVisitor.cpp. Please, let us know if you decide to take this direction and need more help.

I also tried marking the sval (and the sval->getAsSymbol()) as important, as
Anna suggested, but that didn't seem to do anything... I think it would have
satisfied me, but I cannot make it work.

My previous explanation was not right. Currently, interesting symbols are only used to find out if a function call along analyzes path is interesting - or important to step into during diagnostics.

#6

You both mention tracking SVals. I just want to highlight that SVals are transient values, so symbols or regions should be tracked (added to state) instead. See Representing Values here:
http://clang-analyzer.llvm.org/checker_dev_manual.html

You can take a look at visitors implemented in BugReporterVisitors and add the ones that are useful for your checker on BugReport creation. For example, DereferenceChecker and DivZeroChecker call bugreporter::trackNullOrundefValue helper, which adds a few visitors to the bug report. It contains heuristics, which decide what expressions along the path would be important to show when the user needs an explanation on why a an expression evaluates to zero or is undefined.

You can play with the existing checkers to see what to expect. For example:
// Null ptr dereference
int f(int i) {
int *a = 0;
int *c = a;
return *c;
}

/Users/zaks/tmp/ex.c:26:5: note: Variable 'a' initialized to a null pointer value
int *a = 0;
^
/Users/zaks/tmp/ex.c:28:5: note: Variable 'c' initialized to a null pointer value
int *c = a;
^
/Users/zaks/tmp/ex.c:29:12: note: Dereference of null pointer (loaded from variable 'c')
return *c;
        ^

The original example, has a division operation "int b = a/i;". Here, the analyzer doesn't even know that 'b' is zero. (Due to constraint manager not modeling division.)
int f2(int i) {
int a = 0;
int b = a/i;
int c = b;
return 5/c;
}
// no warning reported

Hi Gerard, Anna,

I have been trying to do the same thing, or should I say "failing to do the
same thing..." :slight_smile:

I tried adding a checker that will add sval-s to the state as they are
created, and then let the BugReporterVisitor trace the state in which they
were added. This requires a ProgramStateTrait that is known both to the
checker and to the visitor, and though I try following the Taint examole, I
am currently stuck in this direction too.

If the notes you are trying to add are checker-specific, you need to implement a visitor in the same file as the checker. The ProgramStateTrait will be visible. See Malloc checker and RetainCount checker - they both have custom visitors.

If the notes are generic (could apply to symbols from any checker). You should add/enhance visitors in BugReporterVisitor.cpp. Please, let us know if you decide to take this direction and need more help.

I also tried marking the sval (and the sval->getAsSymbol()) as important, as
Anna suggested, but that didn't seem to do anything... I think it would have
satisfied me, but I cannot make it work.

My previous explanation was not right. Currently, interesting symbols are only used to find out if a function call along analyzes path is interesting - or important to step into during diagnostics.

#7

Anna,

Thanks for your answers.

I really hoped that there is a way to mark the SVal's symbol as interesting
will do the trick :frowning:
Would implementing this be difficult?
Could you guide me through this?

If it is to complicated for a newbie like me, I will try to follow the
example in bugreporter::trackNullOrundefValue.

Thanks, Gerard.

#8

Anna,

Thanks for your answers.

I really hoped that there is a way to mark the SVal’s symbol as interesting
will do the trick :frowning:
Would implementing this be difficult?

It will not be trivial from the implementation point - there is no notion of a value being propagated through the analysis path, instead you have a sequence of ExplodedNodes, so you would have to walk the path and examine exploded nodes to see what changed and use heuristics to see if the change is something you should be observing. In addition, it is also not clear what to track. For example, for ‘x = a + b’ if ‘x’ is being tracked, should you start tracking ‘a’ and ‘b’? What if the value of ‘x’ depends on a condition, ex: ‘if (c) x = a else x = b’, should you start tracking assignments to ‘c’ as well? Determining what is interesting might require some sort of program slicing solution (http://en.wikipedia.org/wiki/Program_slicing). Also, we do not want to overpower users with too much info.

I would suggest starting with small incremental improvements. For example, use the existing visitors, which other checkers use. Adding a visitor to the BugReport is as easy as marking a symbol interesting.

The next step would be to see what is missing and try to enhance those visitors or write your own version, which solves a particular problem - adds a missing node along a path.

Anna.

#9

To get more familiar with the code, take a look at BugReporter.cpp::GenerateExtensivePathDiagnostic this is the logic that walks the chain of ExplodedNodes (the path) and constructs PathDiagnostics. You can see how interesting symbols are being used here and also how they get propagated by tracing interesting calculations, similar to what you want(reversePropagateIntererstingSymbols). (However, as I mentioned before, the interesting symbols are only used to prune the uninteresting calls.) You can also see how visitors are called to generate extra notes at the end of each loop iteration. The visitors are defined in BugRreporterVisitor.h. If you look at the implementation of some, you’ll see that a visitor tracking a particular region, might register an additional visitor to track a related region.

Cheers,
Anna.