Vulnerability Detection

Detecting Vulnerabilities with Program Dependencies

Currently our discussions have been focused on the Symbolic Expression Graph, which is ClearBlue’s central structure for reasoning about program dependencies. An important question is, how can a precise understanding of program dependencies help in the detection of software vulnerabilities?

ClearBlue supports the detection of “source-sink value flow” problems, which consist of three major ingredients:

1. Vulnerability Source: the source value introduced in the program that we need to track for possible errors. For instance, the NULL value is a source for Null Pointer Dereference vulnerability; Memory allocation such as p = malloc(sz) is a source for Memory Leak Detection; Reading from sensitive data such as c = get_password() is a source for Taint Flow Detection.

2. Vulnerability sink: the sink use site of the source value that is related to the determination of the bug. For instance, the pointer dereferece site *p is a sink for Null Pointer Dereference vulnerability; Memory deallocation such as free(p) is a sink for Memory Leak Detection; Output statements such as print(c) is a sink for Taint Flow Detection.

3. Value Flow: how does the source value flow into the sink site. ClearBlue utilizes SEG to search for a value flow path from the graph that connects the source and sink. The search is performed efficiently following the program dependencies by the core engine of ClearBlue, while users can easily implement their checkers by describing the characteristics of the problems to check.

Describe Your Vulnerability

Users shoule implement classSailFishVulnerability to describe the particular source-sink problem they intend to detect. The following two interfaces are central to this description:

bool isSource (SEGNodeBase *Node, SEGSiteBase *Site);
 
bool isSink (SEGNodeBase *Node, SEGSiteBase *Site);

isSource() and isSink() are methods that specify the starting and ending point to the value flow analysis for the engine to work with. They work as the selectors on the SEG indentifying the interesting variables, memory locations or instructions, regardless of how the data dependencies between them are gathered. Whether the dependencies are inter-procedurally connected, interact with pointer variables, or involve feasibility, the core analysis engine takes all of them into account.

The two methods take a pair of SEGNodeBase and SEGSiteBase as input, where the SEGSiteBase is the site where the SEGNodeBase occurs. Both methods return a boolean value, which indicates whether or not the given node and site are the interseted.

In the building arg-ret summary example, the implementation could be approached in a different way: we can register a custom vulnerability type by supplying the isSource() and isSink() implementations and leave the complex graph searching work to the engine:

bool isSource(SEGNodeBase *Node, SEGSiteBase *Site) {
  if(isa<SEGArgumentNode>) {
    return true;
  }
  return false;
}

bool isSink(SEGNodeBase *Node, SEGSiteBase *Site) {
  if (isa<SEGReturnNode>(Node)) {
    return true;
  }
  return false;
}

Write a Checker

We demonstrate how to write a checker that finds null pointer deference bugs.

Step One: Choose the right vulnerability class to inherit.

The first step is to clarify the specification of the bug type. In checking null pointer deference, the bug occurs when the source value (i.e., NULL value) reaches the sink site (i.e., dereferece). Thus, we should inherit from the class SrcMustNotReachSinkVulnerability.

class NullPointerDereferenceVS : public SrcMustNotReachSinkVulnerability {
  
public:
  NullPointerDereferenceVS() : SrcMustNotReachSinkVulnerability("NPD") {}
...
}

Step Two: Implement the src and sink specification.

We only need to implement two APIs, isSource() and isSink(), provided by the Vulnerability class to specify the cared sources and sinks:

bool isSource(SEGNodeBase *Node, SEGSiteBase *Site);
  
bool isSink(SEGNodeBase *Node, SEGSiteBase *Site);

In our NPD example, the sources should be the node with constant null pointer values. We first convert the SEGNode into a SEGOperandNode type since only the operand owns values. And then access the value of a SEGOperandNode by the API getSEGValue(). Next, we judge the type of the SEGValue by invoking several APIs. Here we prune the non-pointer type by calling isPointerType(), and then decide whether it’s a constant null pointer by calling isConstantPointerNull().

  virtual bool isSource(SEGNodeBase *Node, SEGSiteBase *Site) override {
    if (auto N = dyn_cast<SEGOperandNode>(Node)) {
      SEGValue *sValue = N->getSEGValue();
  
      if (!sValue->isPointerType()) {
        return false;
      }
  
      if (sValue->isConstantPointerNull()) {
        return true;
      }
    }
    return false;
  }

The sinks should be the dereference statements that dereference a pointer.

First, we inspect whether the given SEGSite is a SEGDereferenceSite and then check if the site dereferences the value represented by the given SEGNode.

Second, we inspect the case when the given SEGSite is a SEGCallSite. If the SEGCallSite has a callee function that dereferences the value, we also label it as a sink.

  
  virtual bool isSink(SEGNodeBase *Node, SEGSiteBase *Site) override {
    auto OpNode = dyn_cast<SEGOperandNode>(Node);
    assert(OpNode);
  
    SEGValue *sValue = OpNode->getSEGValue();
  
    if (auto DS = dyn_cast<SEGDereferenceSite>(Site)) {
      if (DS->deref(OpNode)) {
        return true;
      }
    } else if (const SEGCallSite *CS = dyn_cast<SEGCallSite>(Site)) {
      SEGValue *sValue = OpNode->getSEGValue();
      SEGValue *sValueCS = CS->getSEGValue();
      if (sValueCS->hasCalledFunction() && sValueCS->isDerefPtr(sValue)) {
        return true;
      }
    }
    return false;
  }
  

Step Three: Register your checker to the ClearBlue engine.

We only need to instantiate the template class VulnerabilityRegistry with three parameters:

• checker name: here we name it ‘ps-npd-vs’. It should be a unique identifier of the checker, which ClearBlue uses to locate your checker.
• checker description: A short description of your checker.
• checker group: A optional parameter that specifies which group your checker belongs to.

static VulnerabilityRegistry<NullPointerDereferenceVS>
    X("ps-npd-vs", "Run path-sensitive null-pointer-dereference checker.",
      "ps-stable");

Here is the complete implementation of the example:

#include "Checker/PSA/Vulnerability.h"
#include "Checker/PSA/VulnerabilityRegistry.h"
#include "IR/SEG/SEGCallSite.h"
#include "IR/SEG/SEGSimpleSite.h"
#include "IR/SEG/SEGValue.h"
#include "Utils/Mock/LibMeta.h"
  
using namespace llvm;
  
class NullPointerDereferenceVS : public SrcMustNotReachSinkVulnerability {
  
public:
  NullPointerDereferenceVS() : SrcMustNotReachSinkVulnerability("NPD") {}
  
  virtual bool isSource(SEGNodeBase *Node, SEGSiteBase *Site) override {
    if (auto N = dyn_cast<SEGOperandNode>(Node)) {
      SEGValue *sValue = N->getSEGValue();
  
      if (!sValue->isPointerType()) {
        return false;
      }
  
      if (sValue->isConstantPointerNull()) {
        return true;
      }
    }
    return false;
  }
  
  virtual bool isSink(SEGNodeBase *Node, SEGSiteBase *Site) override {
    auto OpNode = dyn_cast<SEGOperandNode>(Node);
    assert(OpNode);
  
    SEGValue *sValue = OpNode->getSEGValue();
  
    if (auto DS = dyn_cast<SEGDereferenceSite>(Site)) {
      if (DS->deref(OpNode)) {
        return true;
      }
    } else if (const SEGCallSite *CS = dyn_cast<SEGCallSite>(Site)) {
      SEGValue *sValue = OpNode->getSEGValue();
      SEGValue *sValueCS = CS->getSEGValue();
      if (sValueCS->hasCalledFunction() && sValueCS->isDerefPtr(sValue)) {
        return true;
      }
    }
    return false;
  }
};
  
static VulnerabilityRegistry<NullPointerDereferenceVS>
    X("ps-npd-vs", "Run path-sensitive null-pointer-dereference checker.",
      "ps-stable");