Forward dataflow analysis for collecting comparison facts by ppashakhanloo · Pull Request #657 · checkedc/checkedc-clang

ppashakhanloo · 2019-08-07T23:36:26Z

This pull request adds a forward dataflow analysis for collecting facts in every function for each CFG block.
I have added some new tests under test/CheckedC/dump_dataflow_facts.c.
~~Some comments still need to be added.~~

The main function that runs the analysis is AvailableFactsAnalysis::Analyze() which implements the iterative worklist algorithm. This function must be called before checking the bounds declarations.

For each CFG block B, the following sets are computed:

Gen[B]: For every if-node, if the condition is a binary operator where opcode is one of <, <=, >, or >=, add the condition to Gen[B]
Kill[B]: First, collect all the variables that are defined in block B, and if any expression in the program contains any of these variables, add it to Kill[B]
In[B]: The intersection of the Out set of Predecessors of B
Out[B]: First, compute the set union between In[B] and Gen[B]. Next, remove any comparison in Kill[B].

For using the collected facts, the following functions can be used:

void Next(); // moving to the next block in CFG
void GetFacts(std::set<std::pair<Expr *, Expr *>>& InequalityFacts); // getting the collected facts of the current CFG block

Representation of the comparison facts:

Each fact is represented by a pair of two Expr*s. By (Expr1, Expr2), we mean Expr1 <= Expr2 or Expr1 < Expr2.

…into collect-facts

ppashakhanloo · 2019-08-09T16:49:03Z

@dtarditi I believe this PR is ready for a review of this stage.

dtarditi

Great start! I have a number of suggestions for the code.

dtarditi · 2019-08-09T18:56:38Z

+  // - Expr1 <= Expr2
+  // - Expr2 > Expr1
+  // - Expr2 >= Expr1
+  void ExtractComparisons(const Stmt *St, ComparisonSet &ISet) {


Can St be an Expression? I'd like you to use the Expr::ignoreParens() method to ignore parenthesis, so that this is more general.

dtarditi · 2019-08-09T18:57:13Z

+  // This function looks recursively for comparisons in statement `S`.
+  // Then, it records them as elements of type Comparison in `ISet`.
+  // Each Comparison is a pair in form of (Expr1, Expr2) where both
+  // Expr1 and Expr2 are of type Expr*.


The comment is confusing. It should just say that for each expression, Expr1 <= Expr2 holds.

dtarditi · 2019-08-09T18:59:01Z

  };
 }

+namespace {


I think the code for this analysis should be broken out into separate files: a .h file for the class declaration and cpp for the class implementation.

dtarditi · 2019-08-09T18:59:55Z

 namespace {
  class CheckBoundsDeclarations {
+  public:
+    typedef llvm::SmallPtrSet<const Stmt *, 16> StmtSet;


Instead of hard-wiring 16 into the code, can we use a constant expression?

dtarditi · 2019-08-09T19:01:41Z

+  }
+
+  // This function fills `ComparisonFacts` with pairs (Expr1, Expr2) where
+  // Expr1 < Expr2, Expr1 <= Expr2, Expr2 > Expr1, or Expr2 >= Expr1.


I think this comment is confusing. The invariant is that Expr1 <= Expr2.

dtarditi · 2019-08-09T19:09:22Z

+  }
+
+  // Given a set of Comparisons `InputSet`, this function negates them
+  // by swaping the element of pairs, and records them in `OutputSet`.


Typo: swaping->swapping.

dtarditi · 2019-08-09T19:11:33Z

@@ -0,0 +1,213 @@
+// Tests for dumping of datafow analysis for collecting facts
+//
+// RUN: %clang_cc1 -DDEBUG_DATAFLOW -fcheckedc-extension %s 2>&1 | FileCheck %s


You need to add a compiler flag. After the analysis, you'd check the compiler flag and dump the results accordingly. You can look at the recent commit by @mgrang to see how to do this.

Done. The new flag is -fdump-extracted-comparison-facts.

dtarditi · 2019-08-09T19:12:36Z

+      b = c;
+}
+
+// CHECK: {


This should include block number information. Otherwise this will be very difficult to debug in the future.

Could you add more test cases for more complicated expressions?

dtarditi · 2019-08-09T19:15:05Z

+          WorkList.push(GetByCFGBlock(*I));
+    }
+
+  //if(DEBUG_DATAFLOW)


This needs to be moved out to a separate routine. The dumps should be controlled by a compiler flag.

dtarditi · 2019-08-09T19:19:51Z

+    return false;
+  }
+
+  // This function looks recursively for comparisons in statement `S`.


I think the proper invariant is this: this function computes a list of comparisons E1 <= E2 that will be true if the expression S evaluates to true. Clearly if S is simple direct comparison expression E3 op E4, a comparison can be created if op is one of LE, LT, GE, GT, or EQ. If S has the form A && B, comparisons can be created for A and B.

Could you add a TODO for handling logical negation the (!) operator?

dtarditi · 2019-08-09T19:29:11Z

We also need to conservative in the set of comparisons that we collect with respect to pointers and calls.

We can't include comparisons whose expressions involve calls. The call could produce a different value.
Similarly a comparison shouldn't include a reference to a volatile variable.
If an expression in a comparison contains a pointer dereference, we need to kill the comparison at any potential pointer assignment expression (assignment via a pointer or a call).

…into collect-facts

sunnychatterjee

Hi Pardis,

I've left some comments in the PR for your consideration.

Thank you,
Sunny

sunnychatterjee · 2019-08-09T21:22:15Z

 namespace {
  class CheckBoundsDeclarations {
+  public:
+    typedef llvm::SmallPtrSet<const Stmt *, 16> StmtSet;


Nit: "using" is the preferred syntax over C-style typedef :) Similar suggestion for other places where you've used a typedef.

sunnychatterjee · 2019-08-09T21:25:27Z

+    ComparisonSet Kill, GenThen, GenElse;
+
+  public:
+    ElevatedCFGBlock(const CFGBlock *Block) : Block(Block) {}


Nit: ElevatedCFGBlock(const CFGBlock *Block) : Block(Block) {} -> Can we use a different variable name than the data member?

@sunnychatterjee I followed a similar naming convention that appears in the existing constructors in this file. Should I change it?

@ppashakhanloo You don't have to change this if it appears in the existing convention. Personally, I don't prefer this style since you have to qualify member access with a "this" in such cases.

sunnychatterjee · 2019-08-09T21:26:37Z

+
+  class ElevatedCFGBlock {
+  private:
+    const CFGBlock *Block;


Can we add default initializations for the data members? For example:

private:
const CFGBlock *Block = nullptr;

Similarly, for other data members.

@sunnychatterjee ElevatedCFGBlock has one constructor with const CFGBlock *Block as input. And there is no default constructor for it. I am not sure why we need to add default initializations for the data members here.

@ppashakhanloo For a single data member like in your example, it's fine. I usually follow the rule to always initialize data members of the object: http://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#Res-always.
This way, we avoid errors when constructors sometimes don't initialize all the data members of a class.

sunnychatterjee · 2019-08-09T21:32:06Z

+  public:
+    ElevatedCFGBlock(const CFGBlock *Block) : Block(Block) {}
+
+    friend class AvailableFactsAnalysis;


friend class AvailableFactsAnalysis; --> Is there a way to avoid the "friend"? For example, we can have public methods to access the data members of "ElevatedCFGBlock".

@sunnychatterjee I used friend since AvailableFactsAnalysis should be the only class that manipulates an object of ElevatedCFGBlock. (I thought of it as an Iterator class.)
If I make public methods to access the data members of it, I think I share more than necessary with the world outside AvailableFactsAnalysis. Is there a better way to achieve this goal?

@ppashakhanloo Thanks for the explanation. I try to avoid "friend" wherever possible since it tends to break encapsulation. However, there are exceptions to this like iterators as you mention. Given that the two classes are so close to each other (nested), let's leave them as is.

sunnychatterjee · 2019-08-09T21:34:38Z

+      if (Block->getBlockID() > MaxBlockID)
+        MaxBlockID = Block->getBlockID();
+
+    BlockIDs.resize(MaxBlockID + 1, 0);


Should we clear BlockIDs before calling resize?

sunnychatterjee · 2019-08-09T21:44:32Z

+          WorkList.push(GetByCFGBlock(*I));
+    }
+
+  //if(DEBUG_DATAFLOW)


You meant to remove the comment here right?

Yes, I added a compiler flag for debugging purposes and removed this comment.

sunnychatterjee · 2019-08-09T21:46:56Z

+    return Blocks[BlockIDs[B->getBlockID()]];
+  }
+
+  // Given two sets S1 and S2, the return value is S1 \ S2.


Nit: You meant: S1 - S2, right?

@sunnychatterjee I will change this comment to S1 - S2 for more clarity. I meant \ which is the set difference operator.

@ppashakhanloo This was a clarifying question. Feel free keep the set difference operator.

sunnychatterjee · 2019-08-09T21:53:39Z

+    if (const Expr *E = dyn_cast<Expr>(St))
+      AllExprs.insert(E);
+    for (auto I = St->child_begin(); I != St->child_end(); ++I)
+      CollectExpressions(*I, AllExprs);


You can use range-for loop here.

sunnychatterjee · 2019-08-09T21:58:40Z

+      CollectDefinedVars(*I, DefinedVars);
+  }
+
+//#if DEBUG_DATAFLOW


You meant to remove the comment for DEBUG_DATAFLOW, right? I'd expect the pattern to look like this in the production code. Alternatively, you can use some debug flags to enable this.

#DEBUG_DATAFLOW 0 // Set this to 1 for debugging

#if DEBUG_DATAFLOW
...
#endif // DEBUG_DATAFLOW

Yes, I removed this comment and added a new compiler flag which is only used when testing the functionality of this part of the code.

sunnychatterjee · 2019-08-09T21:59:49Z

  std::unique_ptr<CFG> Cfg = CFG::buildCFG(nullptr, Body, &getASTContext(), CFG::BuildOptions());
  CheckBoundsDeclarations Checker(*this, Body, Cfg.get(), FD->getBoundsExpr());
-  if (Cfg != nullptr)
+  AvailableFactsAnalysis Collector(*this, Cfg.get());


Move this inside the if-block below.

dtarditi

The tests for assignments via pointers or dereferences via pointers need to be corrected.

The operators are defined in clang/include/clang/AST/OperationKinds.def. The *', '->and[]` operators all produce lvalues. In the clang AST, memory is read by using an LValueToRvalue Cast. Memory is modified in the lvalue appearing as the left-hand side of an assignment or as the subexpression of increment or decrement operator.

dtarditi · 2019-08-15T22:47:01Z

                                   ///< enable code coverage analysis.
 CODEGENOPT(DumpCoverageMapping , 1, 0) ///< Dump the generated coverage mapping
                                       ///< regions.
-


It appears a newline was deleted here. Could you add it back?

dtarditi · 2019-08-15T22:50:24Z

 def : Flag<["-"], "no-integrated-as">, Alias<fno_integrated_as>,
      Flags<[CC1Option, DriverOption]>;

+def fdump_extracted_comparison_facts : Flag<["-"], "fdump-extracted-comparison-facts">, Group<f_Group>, Flags<[CC1Option]>,


Could you move this next to the other Checked C flags? The flags beging at def fcheckedc_extension.

dtarditi · 2019-08-15T22:59:05Z

+
+bool AvailableFactsAnalysis::ContainsFunctionCall(const Expr *E) {
+  if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
+    if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(DRE->getDecl()))


This isn't the right check for whether an expression contains a call expression. You should for CallExpr, not the presence of a function call.

ppashakhanloo · 2019-08-16T21:17:12Z

@dtarditi I addressed your comments and added more tests.
Then, I updated CompareUpperOffsets/CompareLowerOffsets to use Facts of the current block that is passed by reference to them. Instead of the function EqualExtended that was used before, I added LessThanOrEqualExtended which is similar to EqualExtended except that it also looks up facts when comparing two offsets. The corresponding test is in test/CheckedC/static-checking/bounds-decl-checking.c .

The code is ready for review.

dtarditi

I have some additional suggestions for the code. I think you can simplify the code by using the existing function Sema::CheckIsNonModifying also. You'll want to pass an argument so that CheckIsNonModifying doesn't report an error if it s find a modifying expression.

dtarditi · 2019-08-20T00:05:25Z

+        return true;
+  }
+  if (const CallExpr *CE = dyn_cast<CallExpr>(E)) {
+    for (int ArgIndex = 0; ArgIndex < CE->getNumArgs(); ArgIndex++) {


Any call expression must be considered as possibly doing a pointer assignment. We should not consider the types of the arguments passed to the function call. It's possible that a pointer could be accessible to a function via a global variable or through a structure type.

dtarditi · 2019-08-20T00:07:37Z

+  return false;
+}
+
+// This function return true if an expression is volatile, and false otherwise.


Typo: return->returns

dtarditi · 2019-08-20T00:19:08Z

+// - If the child of `E` is `e`, then `f(e)` must be true. `f(e)` is defined in
+//   a separate function `IsPointerDerefLValue`.
+// Otherwise, the function returns false;
+bool AvailableFactsAnalysis::IsPointerDeref(const Expr *E) {


You need to check whether E contains a pointer dereference. That means you need to check the children recursively also. I think you should rename this function.

dtarditi · 2019-08-20T00:19:43Z

+  return false;
+}
+
+bool AvailableFactsAnalysis::IsPointerAssignment(const Expr *E) {


You need to check whether E contains a pointer assignment. You need to recursively check the children too. I think you should rename this function.

dtarditi · 2019-08-20T00:24:29Z

+  CollectExpressions(I.first, Exprs);
+  CollectExpressions(I.second, Exprs);
+  for (auto InnerExpr : Exprs)
+    if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(InnerExpr))


A variable v produces an lvalue. For the variable to be used, the lvalue must be the used by an LValueToRValue cast expression.

Thanks for explaining this. Fixed.

dtarditi · 2019-08-20T00:38:46Z

+// - `E` has the form `E1 && E2`: ExtractComparisons in E1 and E2 and add them to `ISet`.
+// TODO: handle the case where logical negation operator (!) is used.
+void AvailableFactsAnalysis::ExtractComparisons(const Expr *E, ComparisonSet &ISet) {
+  if (IsVolatile(E) || ContainsCallExpr(E))


You can use the function Sema::CheckIsNonModifying instead.

dtarditi · 2019-08-20T00:38:57Z

+// - `E` has the form `E1 || E2`: ExtractNegatedComparisons in E1 and E2 and add
+//   them to `ISet`.
+void AvailableFactsAnalysis::ExtractNegatedComparisons(const Expr *E, ComparisonSet &ISet) {
+  if (IsVolatile(E) || ContainsCallExpr(E))


You can use the function Sema::CheckIsNonModifying instead.

dtarditi · 2019-08-20T00:40:15Z

+
+// This function return true if an expression is volatile, and false otherwise.
+// An expression is volatile if there is at least one volatile variable in it.
+bool AvailableFactsAnalysis::IsVolatile(const Expr *E) {


This is overly conservative: it would flag an expression that used &v, where v is a volatile variable, as being volatile. I suggest that you use the existing function CheckIsNonModifying in the functions that are calling this instead.

dtarditi · 2019-08-20T00:47:18Z

+// We assume a variable is defined if it appears in the lhs of an assignment:
+// 1. increment or decrement operator (a++)
+// 2. assignment operator (a += 1, a = 2)
+void AvailableFactsAnalysis::CollectDefinedVars(const Stmt *St, std::set<const VarDecl *> &DefinedVars) {


This function could miss some definitions of variables. In the unary operator case, the expression being incremented/decremented could be parenthesized. In both cases, the LValueBitCast could also be parenthesized. I think you need a loop that ignores parentheses and lvalue bit casts until nothing changes. This should be factored into a separate function.

dtarditi · 2019-08-20T00:48:34Z

+        return false;
+
+      bool EqualWithoutFacts = EqualValue(Ctx, VariablePart1, VariablePart2, EquivExprs);
+      bool LEWithFacts = FactExists(Ctx, VariablePart1, VariablePart2, EquivExprs, Facts);


The logic would be clearer to return true if EqualWithoutFact is true, and similarly return true if LEWtihFacts is true. Then return false otherwise.

ppashakhanloo · 2019-08-20T17:54:47Z

@dtarditi Thanks for your comments. I addressed all of them.
The code is ready for review.

…into collect-facts

dtarditi

Looks good! Thank you.

There is one change in a comment that I'd like you to make. I don't need to re-review it before you complete the PR.

dtarditi · 2019-08-21T19:00:28Z

    }

+    // This function is an extension of EqualExtended. It looks into the provided `Facts`
+    // in order to prove `Base1 + Offset1 <= Offset2 + Offset2`.


There's typo here: Offset2 is used twice.

Could you add a TODO comment: we are ignoring the possibility of overflow in the addition.

The most important changes: - Clean up the multi-decl detection and rewriting code, and unify the code paths for global variables, fields, and local variables. - Automatically generate names for unnamed inline structs if they need to be rewritten, and remove 3C's previous workarounds that tried to avoid needing to rewrite multi-decls with unnamed inline structs that 3C couldn't handle correctly. - Inside a struct, when rewriting a field multi-decl that contains an inline struct, correctly detect the presence of the inline struct to avoid losing it completely, and additionally move it to the top level to avoid a compiler warning. - Add support for typedef multi-decls on par with variable and field multi-decls. See correctcomputation#657 for more details.

ppashakhanloo added 19 commits July 31, 2019 17:56

initial commit

bff84d1

Add First Version of Condition Analysis

bda3b92

Collecting only if-condition facts

b2b15b7

Fix bug in intersection

cbaee9d

Add path-sensitivity

24f0ffd

Remove deadcode

9b19bdd

Process logical-and inside conditions

c0f8d2c

Fix bug in computing In set

6e66c8e

Add null check before deref

83ed290

Add Next() and GetFacts()

82edf83

Rename the main class for dataflow analysis

2ab8bd0

Remove commented code

734cd3a

Improve performance by eliminating search

0e710ae

Add the forgotten memory allocation

affa3f0

Change directive

c1302f4

Rename inequality to comparison

e6fdc19

Add initial tests for dataflow analysis

0010dfb

Add a new test for non-early return

2d348b6

Merge branch 'master' of https://github.com/microsoft/checkedc-clang …

896a7f2

…into collect-facts

ppashakhanloo changed the title ~~WIP: Forward dataflow analysis for collecting inequality facts~~ Forward dataflow analysis for collecting inequality facts Aug 9, 2019

ppashakhanloo added 2 commits August 9, 2019 10:00

Update comments

e3478bd

Add more tests

3d0cbb3

ppashakhanloo changed the title ~~Forward dataflow analysis for collecting inequality facts~~ Forward dataflow analysis for collecting comparison facts Aug 9, 2019

dtarditi reviewed Aug 9, 2019

View reviewed changes

ppashakhanloo added 2 commits August 9, 2019 12:54

Merge branch 'master' of https://github.com/microsoft/checkedc-clang …

2e9f615

…into collect-facts

Correct the logic in multiple spots

69fbc7c

sunnychatterjee reviewed Aug 9, 2019

View reviewed changes

Separate AvailableFactsAnalysis from SemaBounds.cpp

b095fb6

ppashakhanloo added 2 commits August 15, 2019 16:38

Bug fix in InSet-KillSet check

eb09c50

Add a new test

d0f41c9

dtarditi reviewed Aug 15, 2019

View reviewed changes

ppashakhanloo added 9 commits August 15, 2019 16:50

Add back new line

38dc911

Move fdump-extracted-comparison-facts next to other checkedc facts

ace9d3c

Correct test for pointer deref

e95c32d

Bug fix for (*a).b

fe7d250

Correct pointer assignment

0e93ea5

GetBlock should be private

b9e9989

Update comments

415aabc

Add more tests

8919507

Correct testing of pointer deref and assignment

120d338

dtarditi reviewed Aug 20, 2019

View reviewed changes

ppashakhanloo added 7 commits August 19, 2019 18:00

Change the order in flow function

b1ad0f8

add more tests

a692073

Add more tests

dfeea37

Make the logic more clear

3c1a89f

Bug fix in various functions for analysis

018ed8e

Resolve conflicts

5d55dde

Remove unnecessary bitcast check

d1e3a3a

ppashakhanloo added 2 commits August 20, 2019 16:20

Add more tests

c881aab

Merge branch 'master' of https://github.com/microsoft/checkedc-clang …

5978b5c

…into collect-facts

dtarditi approved these changes Aug 21, 2019

View reviewed changes

Update a comment

bf80c10

ppashakhanloo merged commit 8bb1425 into master Aug 22, 2019

dtarditi deleted the collect-facts branch August 26, 2019 21:17

secure-sw-dev-bot mentioned this pull request Jan 16, 2022

Forward dataflow analysis for collecting comparison facts checkedc/checkedc-llvm-project#653

Closed

Conversation

ppashakhanloo commented Aug 7, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ppashakhanloo commented Aug 9, 2019

Uh oh!

dtarditi left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ppashakhanloo Aug 12, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

dtarditi commented Aug 9, 2019

Uh oh!

sunnychatterjee left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

ppashakhanloo commented Aug 7, 2019 •

edited

Loading

ppashakhanloo Aug 12, 2019 •

edited

Loading