[analyzer] Add MagentaHandleChecker for the Magenta kernel

[haowei]

Summary

This patch supersedes D34724. We have finished the checker but it is too big to be submitted as a single commit. So we split it into several pieces to help with the review process. This patch includes the annotation attribute support in MagentaHandleChecker. It basically detect functions that have special annotation attributes and parse these annotations strings to function spec information which would used by the actual analysis. In this patch, the checker will not report any bugs. We will follow up with another commit that contains the code of actual analysis.

[haowei]

An updated version was landed in f4c26d993bdc . This diff is no longer needed.

include/clang/StaticAnalyzer/Checkers/Checkers.td

 def Unix : Package<"unix">;
 def UnixAlpha : Package<"unix">, InPackage<Alpha>, Hidden;
 def CString : Package<"cstring">, InPackage<Unix>, Hidden;
 def CStringAlpha : Package<"cstring">, InPackage<UnixAlpha>, Hidden;
 
 def OSX : Package<"osx">;
 def OSXAlpha : Package<"osx">, InPackage<Alpha>, Hidden;
 def OSXOptIn : Package<"osx">, InPackage<OptIn>;
+def Magenta : Package<"magenta">, InPackage<Alpha>;
 
 def Cocoa : Package<"cocoa">, InPackage<OSX>;
 def CocoaAlpha : Package<"cocoa">, InPackage<OSXAlpha>, Hidden;
 def CocoaOptIn : Package<"cocoa">, InPackage<OSXOptIn>;
 
 def CoreFoundation : Package<"coreFoundation">, InPackage<OSX>;
 def Containers : Package<"containers">, InPackage<CoreFoundation>;
 

 
 let ParentPackage = PortabilityOptIn in {
 
 def UnixAPIPortabilityChecker : Checker<"UnixAPI">,
   HelpText<"Finds implementation-defined behavior in UNIX/Posix functions">,
   DescFile<"UnixAPIChecker.cpp">;
 
 } // end optin.portability
+
+//===----------------------------------------------------------------------===//
+// Magenta Specified Checkers
+//===----------------------------------------------------------------------===//
+
+let ParentPackage = Magenta in {
+
+def MagentaHandleChecker : Checker<"MagentaHandleChecker">,
+  HelpText<"A Checker that detect leaks related to Magenta handles">,
+  DescFile<"MagentaHandleChecker.cpp">;
+
+} // end "magenta"

lib/StaticAnalyzer/Checkers/CMakeLists.txt

add_clang_library(clangStaticAnalyzerCheckers
   GTestChecker.cpp
   IdenticalExprChecker.cpp
   IteratorChecker.cpp
   IvarInvalidationChecker.cpp
   LLVMConventionsChecker.cpp
   LocalizationChecker.cpp
   MacOSKeychainAPIChecker.cpp
   MacOSXAPIChecker.cpp
+  MagentaHandleChecker.cpp
   MallocChecker.cpp
   MallocOverflowSecurityChecker.cpp
   MallocSizeofChecker.cpp
   MisusedMovedObjectChecker.cpp
   MPI-Checker/MPIBugReporter.cpp
   MPI-Checker/MPIChecker.cpp
   MPI-Checker/MPIFunctionClassifier.cpp
   NSAutoreleasePoolChecker.cpp

lib/StaticAnalyzer/Checkers/MagentaHandleChecker.cpp

+//== MagentaHandleChecker.cpp - Magenta Handle Checker------------*- C++-*--==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This checker checks if the handle of magenta kernel is properly used
+// according to following rules.
+//   - If a handle is acquired, it should be closed/released before execution
+//        ends.
+//   - If a handle is closed/released, it should not be closed/released again.
+//   - If a handle is closed/released, it should not be used for other purposes
+//        such as I/O.
+//
+// In this checker, each tracked handle is associated with a state. When the
+// handle variable is passed to different function calls or syscalls, its state
+// changes. The state changes can be generally represented by following ASCII
+// Art:
+//
+//                             release_func failed
+//                                +---------+
+//                                |         |
+//                                |         |
+//                                |         |      As argument
+//                              +-+---------v-+    in uninlined   +---------+
+//       acquire_func succeeded |             |    calls          |         |
+//            +----------------->  Allocated  +-------------------> Escaped |
+//            |                 |             |     As return     |         |
+//            |                 +-----+------++     value or      +---------+
+//            |                       |      |      assigned
+//            |         release_func  |      |      back to argument.
+//            |          succeeded    |      +--+
+//            |                       |         |handle out+--------+
+//            |                  +----v-----+   |of scope  |        |
+//            |                  |          |   +----------> Leaked |
+// +----------+--+               | Released |              |(REPORT)|
+// |             |               |          |              +--------+
+// | Not tracked <--+            +----+---+-+
+// |             |  |                 |   |       As argument
+// +------+------+  |    release_func |   +------+in function
+//        |         |                 |          |call
+//        |         |            +----v-----+    |     +-----------+
+//        +---------+            |          |    |     |           |
+//        acquire_func failed    | Double   |    +-----> Use after |
+//                               | released |          | released  |
+//                               | (REPORT) |          | (REPORT)  |
+//                               +----------+          +-----------+
+//
+//
+// acquire_func represents the functions or syscalls that may acquire a handle.
+// release_func represents the functions or syscalls that may release a handle.
+//
+// If a tracked handle ends up in "Released" or "Escaped" state, we assume it
+// is properly used. Otherwise a bug and will be reported.
+//
+// Due to the fact that the number of handle related syscalls in magenta kernel
+// is too large, we adopt the annotation attributes to descript syscalls'
+// operations(acquire/release/use/escape) on handles instead of hardcoding
+// everything in the checker.
+//
+// We use following annotation attributes for handle related syscalls or
+// functions:
+//  1. __attribute__((annotate("mx_handle_acquire"))) |handle will be acquired
+//  2. __attribute__((annotate("mx_handle_release"))) |handle will be released
+//  3. __attribute__((annotate("mx_handle_release_always"))) |handle will be
+//     released and the function will not fail.
+//  4. __attribute__((annotate("mx_handle_escape"))) |handle will transit to
+//     escaped state. This is the default behavior if there is no annotation.
+//  5. __attribute__((annotate("mx_handle_use"))) |handle will not transit to
+//     escaped state.
+//  6. __attribute__((annotate("mx_may_fail"))) |function may fail and return a
+//     negative status code. ProgramState bifurcation is required.
+//  7. __attribute__((annotate("suppress_warning"))) |If a bug is discovered but
+//     one of function in callstack has this annotation. The bug will not be
+//     reported. This annotation is used to suppress warnings on known false
+//     positives.
+//
+// For example, an annotated syscall:
+//   mx_status_t mx_channel_create(
+//   uint32_t options,
+//   __attribute__((annotate("mx_handle_acquire"))) mx_handle_t* out0,
+//   __attribute__((annotate("mx_handle_acquire"))) mx_handle_t* out1)
+//   __attribute__((annotate("mx_may_fail")));
+// denotes a syscall which will acquire two handles and save them to 'out0' and
+// 'out1' when succeeded and will return negative status code when failed.
+//
+// Similarly, another annotated syscall:
+//   mx_status_t mx_handle_close(
+//   __attribute__((annotate("mx_handle_release_always"))) mx_handle_t handle);
+// denotes a syscall which will release the handle in argument 'handle'.
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "ClangSACheckers.h"
+#include "clang/AST/Attr.h"
+#include "clang/Basic/SourceManager.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/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
+#include "llvm/ADT/SmallString.h"
+
+using namespace clang;
+using namespace ento;
+
+namespace {
+
+enum FuncKind {
+  // Calls, including syscalls that have inline annotation or
+  // hard coded annotation.
+  ANNOATATED_FUNC,
+  // Functions that do not have any annotation at all
+  UNANNOTATED_FUNC,
+  // Functions have annotations, but cannot be processed correctly due to
+  // mismatch to the arguments.
+  UNPROCESSED_FUNC,
+  // When a bug is found in function with this flag, do not report this bug
+  // Used to suppress known false positives.
+  DONOTREPORT_FUNC
+};
+
+enum AnnotationFlag {
+  ALLOCATE,
+  RELEASE,
+  // Same as RELEASE but will not cause bifurcation in evalCall. Added due to
+  // Magenta syscalls changes.
+  RELEASE_ALWAYS,
+  ESCAPE,
+  NOESCAPE,
+  // Annotated function will return 0 on succeess and less than 0 on failure
+  // functions with this annotation will cause checker to bifurcate to two
+  // during during evaluation, the successful state and failed state.
+  BIFURCATE,
+  // Annotated function can return any value.
+  // The checker will not bifurcate the states
+  SYMBOLIC,
+  // This value is not describing the possible return value of a annotated
+  // function. It basically tell the checker do not report any bugs found in
+  // this function. Used to suppress false positive reports.
+  DONOTREPORT
+};
+
+struct ArgSpec {
+  enum Kind { VALUE, POINTER, ARRAY } K;
+  // The index of the argument, start from 0.
+  int ArgIdx;
+  // The action of this argument. handle acquire/release/escape/noescape
+  AnnotationFlag ArgAction;
+  // For array kind, the index to the argument of the count of input handles
+  int ArrayHandleInputCountIdx;
+  // For array kind, the index to the argument of the count of actual processed
+  // handles
+  int ArrayHandleOutputCountIdx;
+
+  bool isAllocation() const { return ArgAction == ALLOCATE; }
+  bool isRelease() const {
+    return ArgAction == RELEASE || ArgAction == RELEASE_ALWAYS;
+  }
+  bool isEscape() const { return ArgAction == ESCAPE; }
+  bool isNoEscape() const { return ArgAction == NOESCAPE; }
+  bool isPointer() const { return K == POINTER; }
+  bool isValue() const { return K == VALUE; }
+  bool isArray() const { return K == ARRAY; }
+  int getIndex() const { return ArgIdx; }
+  int getInputCArgIdx() const { return ArrayHandleInputCountIdx; }
+  int getOutputCArgIdx() const { return ArrayHandleOutputCountIdx; }
+
+  ArgSpec(int Id, AnnotationFlag Tag, Kind k)
+      : K(k), ArgIdx(Id), ArgAction(Tag), ArrayHandleInputCountIdx(-1),
+        ArrayHandleOutputCountIdx(-1) {}
+};
+
+// Function description parsed from annotation attribute.
+struct FuncSpec {
+  SmallVector<ArgSpec, 2> ArgSpecVec;
+  AnnotationFlag RetAction;
+
+  size_t getArgSpecCount() { return ArgSpecVec.size(); }
+  FuncSpec(AnnotationFlag RetF) : RetAction(RetF) {}
+  FuncSpec() : RetAction(SYMBOLIC) {}
+
+  void pushArgSpec(size_t Id, AnnotationFlag Tag, ArgSpec::Kind k) {
+    ArgSpec argTag(Id, Tag, k);
+    ArgSpecVec.push_back(argTag);
+  }
+};
+
+static const char *ANNOTATION_PREFIX = "mx_";
+static const char *HANDLE_TYPE_NAME = "mx_handle_t";
+static const char *SYSCALL_RETURN_TYPE_NAME = "mx_status_t";
+
+class MagentaHandleChecker : public Checker<eval::Call> {
+
+  mutable llvm::DenseMap<const FunctionDecl *, FuncSpec> FuncDeclMap;
+  mutable llvm::StringMap<FuncSpec> SpecialFuncDeclMap;
+  mutable llvm::DenseMap<const FunctionDecl *, FuncKind> FuncKindMap;
+  mutable llvm::StringMap<AnnotationFlag> AnnotationMap;
+
+public:
+  MagentaHandleChecker();
+  // Checker callbacks
+  bool evalCall(const CallExpr *CE, CheckerContext &Ctx) const;
+
+private:
+  // Evaluate handle related function call with annotation information
+  bool evalCallWithFuncSpec(const CallExpr *CE, const FunctionDecl *FD,
+                            CheckerContext &Ctx, FuncSpec &FS) const;
+  // Generate function spec info based on inline annotations in declaration
+  bool generateSpecForFuncionDecl(const FunctionDecl *FuncDecl) const;
+  // Extract magenta related annotation string from declarations
+  StringRef extractAnnotationWithoutPrefix(const Decl *D) const;
+};
+} // end anonymous namespace
+
+MagentaHandleChecker::MagentaHandleChecker() {
+
+  // Initialize the map for supported annotations.
+  AnnotationMap = {{"handle_acquire", ALLOCATE},
+                   {"handle_release", RELEASE},
+                   {"handle_release_always", RELEASE_ALWAYS},
+                   {"handle_escape", ESCAPE},
+                   {"handle_use", NOESCAPE},
+                   {"may_fail", BIFURCATE},
+                   {"suppress_warning", DONOTREPORT}};
+
+  // Hard coded FuncSpec for mx_channel_read and mx_channel_write
+  // We currently don't have a clean way to annotate handles passed through
+  // arrays, as it requires another argument for the counts. So stay with
+  // this hard coded solution for now. We will clean it up once we have an
+  // enhanced annotation in the future.
+  FuncSpec ChannelReadSpec(BIFURCATE);
+  ArgSpec ChannelReadArg0(0, NOESCAPE, ArgSpec::VALUE);
+  ArgSpec ChannelReadArg1(3, ALLOCATE, ArgSpec::ARRAY);
+  ChannelReadArg1.ArrayHandleInputCountIdx = 5;
+  ChannelReadArg1.ArrayHandleOutputCountIdx = 7;
+  ChannelReadSpec.ArgSpecVec.push_back(ChannelReadArg0);
+  ChannelReadSpec.ArgSpecVec.push_back(ChannelReadArg1);
+
+  FuncSpec ChannelWriteSpec(BIFURCATE);
+  ArgSpec ChannelWriteArg0(0, NOESCAPE, ArgSpec::VALUE);
+  ArgSpec ChannelWriteArg1(4, RELEASE, ArgSpec::ARRAY);
+  ChannelWriteArg1.ArrayHandleInputCountIdx = 5;
+  ChannelWriteSpec.ArgSpecVec.push_back(ChannelWriteArg0);
+  ChannelWriteSpec.ArgSpecVec.push_back(ChannelWriteArg1);
+
+  SpecialFuncDeclMap = {{"mx_channel_read", ChannelReadSpec},
+                        {"mx_channel_write", ChannelWriteSpec}};
+}
+
+bool MagentaHandleChecker::evalCall(const CallExpr *CE,
+                                    CheckerContext &C) const {
+  const FunctionDecl *FuncDecl = C.getCalleeDecl(CE);
+  if (!FuncDecl)
+    return false;
+
+  // Check if this function is known not to have annotation or known to contain
+  // error in annotation
+  if (FuncKindMap.count(FuncDecl)) {
+    if (FuncKindMap[FuncDecl] == UNANNOTATED_FUNC ||
+        FuncKindMap[FuncDecl] == UNPROCESSED_FUNC ||
+        FuncKindMap[FuncDecl] == DONOTREPORT_FUNC)
+      return false;
+  }
+  // Check if the function has annotation and has already been processed before
+  if (FuncDeclMap.count(FuncDecl))
+    return evalCallWithFuncSpec(CE, FuncDecl, C, FuncDeclMap[FuncDecl]);
+
+  // Check if function has annotation
+  if (generateSpecForFuncionDecl(FuncDecl)) {
+    FuncSpec FS = FuncDeclMap[FuncDecl];
+    return evalCallWithFuncSpec(CE, FuncDecl, C, FS);
+  }
+
+  // The function does not have annotation. It is not a special function as well
+  FuncKindMap[FuncDecl] = UNANNOTATED_FUNC;
+  return false;
+}
+
+//  Evaluate functions with annotation attributes.
+//  If process failed, fallback to conservativeEvalCall by returning false.
+bool MagentaHandleChecker::evalCallWithFuncSpec(const CallExpr *CE,
+                                                const FunctionDecl *FD,
+                                                CheckerContext &Ctx,
+                                                FuncSpec &FS) const {
+  // Here is just a place holder. The real handle analysis code will be
+  // included in follow up commits
+  FuncKindMap[FD] = ANNOATATED_FUNC;
+  return false;
+}
+// Parse annotation attributes from given FunctionDecl. If the annotation is
+// not valid or no annotation available, return false.
+bool MagentaHandleChecker::generateSpecForFuncionDecl(
+    const FunctionDecl *FuncDecl) const {
+  if (!FuncDecl)
+    return false;
+  FuncSpec FS;
+  // First check if the function is a hard coded function
+  DeclarationName DeclName = FuncDecl->getDeclName();
+  if (DeclName.isIdentifier()) {
+    // If false, calling getName() will crash
+    StringRef FuncName = FuncDecl->getName();
+    if (SpecialFuncDeclMap.count(FuncName)) {
+      FuncDeclMap[FuncDecl] = SpecialFuncDeclMap[FuncName];
+      return true;
+    }
+  }
+  bool HasValidAnnotation = false;
+  bool HasFuncDeclAnnotation = false;
+  // Extract FunctionDecl's annotation, which indicates whether return value
+  // bifurcation is required. By default, bifurcation is not necessary.
+  StringRef FuncAnnotation =
+      extractAnnotationWithoutPrefix(cast<Decl>(FuncDecl));
+  // Test return type of the function. Only function with return type
+  // "mx_status_t" can have annotation other than SYMBOLIC or DONOTREPORT
+  FS.RetAction = SYMBOLIC;
+  QualType RetType = FuncDecl->getReturnType();
+  if (!FuncAnnotation.empty() && AnnotationMap.count(FuncAnnotation)) {
+    FS.RetAction = AnnotationMap[FuncAnnotation];
+    HasFuncDeclAnnotation = true;
+    HasValidAnnotation = true;
+  }
+  // Return type is not mx_status_t but has annotation other than
+  // SYMBOLIC|DONOTREPORT Consider it as an error
+  if (RetType.getAsString().find(SYSCALL_RETURN_TYPE_NAME) &&
+      (FS.RetAction != SYMBOLIC && FS.RetAction != DONOTREPORT))
+    return false;
+
+  if (FS.RetAction != BIFURCATE && FS.RetAction != SYMBOLIC &&
+      FS.RetAction != DONOTREPORT)
+    return false;
+  // Extract ParamDecl's annotation.
+  int ArgId = -1;
+  for (auto &PD : FuncDecl->parameters()) {
+    ++ArgId;
+    QualType ParamType = PD->getOriginalType();
+    // We only process mx_handle_t type arguments
+    if (ParamType.getAsString().find(HANDLE_TYPE_NAME))
+      continue;
+    StringRef ArgAnnotation = extractAnnotationWithoutPrefix(cast<Decl>(PD));
+    // By default, handle should escape if no annotation is present
+    AnnotationFlag ArgFlag = ESCAPE;
+    ArgSpec::Kind ArgKind = ArgSpec::VALUE;
+    if (ParamType->isPointerType())
+      ArgKind = ArgSpec::POINTER;
+    // Note: the ArgKind can be an array. But annotation for an array of handles
+    // is not finalized, it is now ignored here.
+    if (!ArgAnnotation.empty() && AnnotationMap.count(ArgAnnotation)) {
+      // It contains valid annotation
+      ArgFlag = AnnotationMap[ArgAnnotation];
+      if (ArgFlag != ALLOCATE && ArgFlag != RELEASE &&
+          ArgFlag != RELEASE_ALWAYS && ArgFlag != ESCAPE && ArgFlag != NOESCAPE)
+        return false;
+      HasValidAnnotation = true;
+    } else if (!ArgAnnotation.empty()) {
+      // invalid annotation
+      return false;
+    }
+    // If no FunctionDecl's annotation is present, assume its annotation based
+    // on argument annotation
+    if (!HasFuncDeclAnnotation && (ArgFlag == ALLOCATE || ArgFlag == RELEASE)) {
+      FS.RetAction = BIFURCATE;
+      HasFuncDeclAnnotation = true;
+    }
+    FS.pushArgSpec(ArgId, ArgFlag, ArgKind);
+  }
+  if (HasValidAnnotation)
+    FuncDeclMap[FuncDecl] = FS;
+  return HasValidAnnotation;
+}
+
+// Return an empty string when suitable annotations are not found.
+StringRef
+MagentaHandleChecker::extractAnnotationWithoutPrefix(const Decl *D) const {
+  if (D && D->hasAttrs()) {
+    for (const auto *AnnAttr : D->specific_attrs<AnnotateAttr>()) {
+      StringRef AnnAttrStr = AnnAttr->getAnnotation();
+      if (AnnAttrStr.startswith(ANNOTATION_PREFIX))
+        return AnnAttrStr.substr(std::strlen(ANNOTATION_PREFIX));
+    }
+  }
+  return StringRef();
+}
+
+void ento::registerMagentaHandleChecker(CheckerManager &mgr) {
+  mgr.registerChecker<MagentaHandleChecker>();
+}