[checker] PoC : Unsequenced Modification Checker

[paulsemel]

Summary

\!/ This is only a proof of concept !

The purpose of this checker is to improve the detection of unsequenced modifications. Indeed, there is a warning the tries to detect those, but this is not efficient at all.
The goal of this checker is to detect more complicated UM.

[a.sidorin]

Hi Paul,

You didn't add any reviewer. Do you need a review for this checker? Are you going to contribute this code to the upstream?

[paulsemel]

Hi Aleksei,

In D44154#1028612, @a.sidorin wrote:

Hi Paul,

You didn't add any reviewer. Do you need a review for this checker? Are you going to contribute this code to the upstream?

I was actually uploading this because Artem Dergachev told me that he was curious about this checker, but I'm pretty sure that this implementation is not good enough to be upstreamed !

include/clang/StaticAnalyzer/Checkers/Checkers.td

   HelpText<"Check for assigning uninitialized values">,
   DescFile<"UndefinedAssignmentChecker.cpp">;
 
+def UnsequencedModificationChecker : Checker<"UB">,
+  HelpText<"Check for unsequenced modifications">,
+  DescFile<"UnsequencedModificationChecker.cpp">;
+
 def UndefBranchChecker : Checker<"Branch">,
   HelpText<"Check for uninitialized values used as branch conditions">,
   DescFile<"UndefBranchChecker.cpp">;

lib/StaticAnalyzer/Checkers/CMakeLists.txt

   UndefResultChecker.cpp
   UndefinedArraySubscriptChecker.cpp
   UndefinedAssignmentChecker.cpp
+  UnsequencedModificationChecker.cpp
   UnixAPIChecker.cpp
   UnreachableCodeChecker.cpp
   VforkChecker.cpp

lib/StaticAnalyzer/Checkers/UnsequencedModificationChecker.cpp

+//=== UnsequencedModificationChecker.cpp -------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This defines UnsequencedModificationChecker, a builtin check in ExprEngine
+// that performs checks for unsequenced modifications.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
+#include "clang/StaticAnalyzer/Core/Checker.h"
+#include "clang/StaticAnalyzer/Core/CheckerManager.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
+#include "llvm/ADT/SmallString.h"
+#include "llvm/Support/raw_ostream.h"
+#include <memory>
+#include <list>
+#include <algorithm>
+#include <iostream>
+#include <functional>
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+  enum UBType
+  {
+    UB_VAR,
+    UB_ARRAY,
+    UB_POINTER,
+    UB_POINTERINDEX
+  };
+
+  class UBDecl
+  {
+    public:
+      UBDecl(const VarDecl *vd)
+      {
+        this->idx = SVal();
+        this->type = UB_VAR;
+        this->vd = vd;
+      };
+      UBDecl(const VarDecl *vd, enum UBType t)
+        : vd(vd), type(t)
+      {
+        this->idx = SVal();
+      }
+      UBDecl(const VarDecl *vd, SVal index)
+      {
+        this->type = UB_ARRAY;
+        this->vd = vd;
+        this->idx = index;
+      };
+      void changeType(enum UBType t)
+      {
+        this->type = t;
+      };
+      bool operator==(const UBDecl& ub)
+      {
+        if (this->type != ub.type)
+          return false;
+        switch(this->type)
+        {
+          case UB_VAR:
+          case UB_POINTER:
+            return this->vd == ub.vd;
+          case UB_ARRAY:
+          case UB_POINTERINDEX:
+            return this->vd == ub.vd && this->idx == ub.idx;
+        };
+        return false;
+      };
+      const VarDecl *vd;
+      SVal idx;
+      enum UBType type;
+    private:
+  };
+
+  enum UBAction
+  {
+    UBUSED = 1,
+    UBMODIFIED = 2,
+    UBMULTIPLE = 4,
+  };
+
+  class UBListElement
+  {
+    public:
+      UBListElement(std::shared_ptr<UBDecl>& ub, enum UBAction action)
+        :ub(ub), action(action)
+      { };
+      UBListElement(std::shared_ptr<UBDecl>& ub, uint32_t action)
+        :ub(ub), action(action)
+      { };
+      bool operator==(const UBDecl& elt)
+      {
+        return *ub == elt;
+      };
+      std::shared_ptr<UBDecl> ub;
+      uint32_t action;
+  };
+
+  class UBList
+  {
+    public:
+      UBList() = default;
+      void push(std::shared_ptr<UBDecl> ub, enum UBAction action)
+      {
+        auto it = std::find(list.begin(), list.end(), *ub);
+        if (it != list.end())
+        {
+          if (it->action == action && action == UBMODIFIED)
+            it->action = UBMULTIPLE;
+          else
+            it->action |= action;
+        }
+        else
+          list.push_back(UBListElement(ub, action));
+      };
+      void pushCallExpr(std::shared_ptr<UBDecl> ub, uint32_t action)
+      {
+        auto it = std::find(list.begin(), list.end(), *ub);
+        if (it != list.end())
+        {
+          if (action != it->action)
+            it->action = UBMODIFIED;
+        }
+        else
+          list.push_back(UBListElement(ub, action));
+      }
+      void push(std::shared_ptr<UBDecl> ub, uint32_t action)
+      {
+        auto it = std::find(list.begin(), list.end(), *ub);
+        if (it != list.end())
+        {
+          if (it->action == action && action == UBMODIFIED)
+            it->action = UBMULTIPLE;
+          else
+            it->action |= action;
+        }
+        else
+          list.push_back(UBListElement(ub, action));
+      };
+      size_t size()
+      {
+        return list.size();
+      };
+      std::shared_ptr<UBDecl> find_UB()
+      {
+        for (auto &elt : list)
+        {
+          if (elt.action == UBMULTIPLE || elt.action == (UBMODIFIED|UBUSED))
+            return elt.ub;
+        }
+        return nullptr;
+      };
+      std::list<UBListElement> list;
+  };
+
+  class UnsequencedModificationChecker
+    : public Checker< check::PreStmt<Stmt> > {
+
+      mutable std::unique_ptr<BugType> BT;
+
+      public:
+      void checkPreStmt(const Stmt *, CheckerContext &) const;
+
+      private:
+      void BinOpUnsequencedChecker(const BinaryOperator *, CheckerContext&, UBList&) const;
+      void CallExprChecker(const CallExpr *, CheckerContext&, UBList&) const;
+      std::shared_ptr<UBDecl> DetermineType(const Stmt*, UBList&, CheckerContext&) const;
+      std::shared_ptr<UBDecl> DetermineTypeExpr(const Expr*, UBList&, CheckerContext&) const;
+      std::shared_ptr<UBDecl> UnaryOperatorChecker(const UnaryOperator*, UBList&, CheckerContext&) const;
+      std::shared_ptr<UBDecl> DeclarationChecker(const DeclRefExpr*, UBList&, CheckerContext&) const;
+      std::shared_ptr<UBDecl> ArraySubChecker(const ArraySubscriptExpr*, UBList&, CheckerContext&) const;
+      const Expr* CleanExpr(const Expr*) const;
+      std::shared_ptr<UBDecl> DeclStmtChecker(const DeclStmt*, UBList&, CheckerContext&) const;
+      void ReturnStmtChecker(const ReturnStmt* , UBList&, CheckerContext&) const;
+    };
+
+} // end anonymous namespace
+
+const Expr* UnsequencedModificationChecker::CleanExpr(const Expr *E) const
+{
+  const Expr *tmp;
+  do {
+    tmp = E;
+    E = E->IgnoreParens()->IgnoreCasts();
+  } while (E != tmp);
+  return E;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DetermineType(const Stmt* S, UBList& Set,
+    CheckerContext& C) const
+{
+  if (!S)
+    return nullptr;
+  if (const Expr *E = dyn_cast<Expr>(S))
+    return this->DetermineTypeExpr(E, Set, C);
+  else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S))
+    return this->DeclStmtChecker(DS, Set, C);
+  else if (const ReturnStmt *RS = dyn_cast<ReturnStmt>(S))
+    this->ReturnStmtChecker(RS, Set, C);
+  return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DetermineTypeExpr(const Expr* E, UBList& Set,
+    CheckerContext& C) const
+{
+  if (!E)
+    return nullptr;
+  E = this->CleanExpr(E);
+  if (const BinaryOperator* BO = dyn_cast<BinaryOperator>(E))
+    this->BinOpUnsequencedChecker(BO, C, Set);
+  else if (const UnaryOperator* UO = dyn_cast<UnaryOperator>(E))
+    return this->UnaryOperatorChecker(UO, Set, C);
+  else if (const DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E))
+    return this->DeclarationChecker(DR, Set, C);
+  else if (const ArraySubscriptExpr *AS = dyn_cast<ArraySubscriptExpr>(E))
+    return this->ArraySubChecker(AS, Set, C);
+  else if (const CallExpr* CE = dyn_cast<CallExpr>(E))
+    this->CallExprChecker(CE, C, Set);
+  return nullptr;
+}
+
+void UnsequencedModificationChecker::ReturnStmtChecker(const ReturnStmt* RS, UBList& Set, CheckerContext& C) const
+{
+  std::shared_ptr<UBDecl> ub = this->DetermineTypeExpr(RS->getRetValue(), Set, C);
+  if (ub)
+    Set.push(ub, UBUSED);
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::UnaryOperatorChecker(const UnaryOperator* UO,
+    UBList& Set,
+    CheckerContext &C) const
+{
+  std::shared_ptr<UBDecl> UB = this->DetermineTypeExpr(UO->getSubExpr(), Set, C);
+  if (!UB)
+    return nullptr;
+  if (UO->isDecrementOp() || UO->isIncrementOp())
+    Set.push(UB, UBMODIFIED);
+  else
+  {
+    UB->changeType(UB_POINTER);
+    return UB;
+  }
+  return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DeclStmtChecker(const DeclStmt* DS, UBList& Set,
+    CheckerContext& C) const
+{
+  if (DS->isSingleDecl())
+  {
+    std::cout << "SingleDecl" << std::endl;
+    if (const VarDecl* VD = dyn_cast<VarDecl>(DS->getSingleDecl()))
+    {
+      if (VD->hasInit())
+      {
+        std::shared_ptr<UBDecl> ptr = this->DetermineTypeExpr(VD->getInit(), Set, C);
+        if (ptr)
+          Set.push(ptr, UBUSED);
+      }
+      return std::make_shared<UBDecl>(VD);
+    }
+  }
+  else
+    std::cout << "GroupDecl" << std::endl;
+  return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::DeclarationChecker(const DeclRefExpr* DR, UBList& Set,
+    CheckerContext& C) const
+{
+  if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
+    return std::make_shared<UBDecl>(VD);
+  return nullptr;
+}
+
+std::shared_ptr<UBDecl>
+UnsequencedModificationChecker::ArraySubChecker(const ArraySubscriptExpr* AS,
+    UBList& Set, CheckerContext& C) const
+{
+  SVal index = C.getState()->getSVal(AS->getIdx(), C.getLocationContext());
+  const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(AS->getBase()->IgnoreImpCasts());
+  if (DR)
+  {
+    const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
+    if (VD)
+      return std::make_shared<UBDecl>(VD, index);
+  }
+  return nullptr;
+}
+
+void
+UnsequencedModificationChecker::BinOpUnsequencedChecker(const BinaryOperator* Ope,
+    CheckerContext &C,
+    UBList &Set) const
+{
+
+  if (Ope->isAssignmentOp() || Ope->isCompoundAssignmentOp())
+  {
+    std::shared_ptr<UBDecl> ptr = DetermineTypeExpr(Ope->getLHS(), Set, C);
+    if (ptr)
+      Set.push(ptr, UBMODIFIED);
+
+    ptr = DetermineTypeExpr(Ope->getRHS(), Set, C);
+    if (ptr)
+      Set.push(ptr, UBUSED);
+  }
+  else
+  {
+    std::shared_ptr<UBDecl> ptr = DetermineTypeExpr(Ope->getLHS(), Set, C);
+    if (ptr)
+      Set.push(ptr, UBUSED);
+    ptr = DetermineTypeExpr(Ope->getRHS(), Set, C);
+    if (ptr)
+      Set.push(ptr, UBUSED);
+    if ((ptr = Set.find_UB()))
+    {
+      ExplodedNode *N = C.generateErrorNode();
+      if (!N)
+        return;
+
+      if (!BT)
+        BT.reset(
+            new BuiltinBug(this, "Operation leads to an undefined behaviour"));
+
+      SmallString<256> sbuf;
+      llvm::raw_svector_ostream OS(sbuf);
+
+
+      OS << "Unsequenced modifications to '";
+      if (ptr->type == UB_ARRAY)
+      {
+        OS << *ptr->vd << "[";
+        ptr->idx.dumpToStream(OS);
+        OS << "]";
+      }
+      else if (ptr->type == UB_POINTER)
+        OS << "*" << *ptr->vd;
+      else
+        OS << *ptr->vd;
+      OS << "'";
+
+      auto report = llvm::make_unique<BugReport>(*BT, OS.str(), N);
+
+      C.emitReport(std::move(report));
+    }
+  }
+}
+
+void
+UnsequencedModificationChecker::CallExprChecker(const CallExpr* CE,
+    CheckerContext &C,
+    UBList &Set) const
+{
+  const Expr *const *args = CE->getArgs();
+  std::shared_ptr<UBDecl> ptr;
+  for (unsigned i = 0; i < CE->getNumArgs(); i++)
+  {
+    ptr = this->DetermineTypeExpr(args[i], Set, C);
+    if (ptr)
+      Set.push(ptr, UBUSED);
+  }
+
+  if ((ptr = Set.find_UB()))
+  {
+    ExplodedNode *N = C.generateErrorNode();
+    if (!N)
+      return;
+
+    if (!BT)
+      BT.reset(
+          new BuiltinBug(this, "Operation leads to an undefined behaviour"));
+
+    SmallString<256> sbuf;
+    llvm::raw_svector_ostream OS(sbuf);
+
+
+    OS << "Unsequenced modifications to '";
+    if (ptr->type == UB_ARRAY)
+    {
+      OS << *ptr->vd << "[";
+      ptr->idx.dumpToStream(OS);
+      OS << "]";
+    }
+    else if (ptr->type == UB_POINTER)
+      OS << "*" << *ptr->vd;
+    else
+      OS << *ptr->vd;
+    OS << "'";
+
+    auto report = llvm::make_unique<BugReport>(*BT, OS.str(), N);
+
+    C.emitReport(std::move(report));
+  }
+
+  const FunctionDecl *FD = CE->getDirectCallee();
+  if (FD && (FD = FD->getDefinition()) && FD->hasBody())
+  {
+    const Stmt *Body = FD->getBody();
+    const CompoundStmt *CS;
+    UBList Bodyset;
+    if (Body && (CS = dyn_cast<CompoundStmt>(Body)))
+    {
+      for (auto it = CS->body_begin(); it != CS->body_end(); it++)
+      {
+        UBList Tmpset = UBList();
+        std::shared_ptr<UBDecl> ub = this->DetermineType(*it, Tmpset,C);
+        /* True for all non local */
+        if (ub && ub->vd->hasGlobalStorage())
+          Set.push(ub, UBUSED);
+        for (auto elt = Tmpset.list.begin(); elt != Tmpset.list.end(); elt++)
+        {
+          if (elt->ub->vd->hasGlobalStorage())
+            Bodyset.pushCallExpr(elt->ub, elt->action);
+        }
+      }
+    }
+    for (auto it = Bodyset.list.begin(); it != Bodyset.list.end(); it++)
+      Set.push(it->ub, it->action);
+  }
+
+}
+
+void UnsequencedModificationChecker::checkPreStmt(const Stmt *S,
+    CheckerContext &C) const {
+
+  UBList Set = UBList();
+  if (const Expr* E = dyn_cast<Expr>(S))
+    this->DetermineTypeExpr(E, Set, C);
+}
+
+void ento::registerUnsequencedModificationChecker(CheckerManager &mgr) {
+  mgr.registerChecker<UnsequencedModificationChecker>();
+}