fuzztest/internal/coverage.h

// Copyright 2022 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Coverage interface.
//
// We rely on SanitizerCoverage instrumentation for coverage feedback:
// https://clang.llvm.org/docs/SanitizerCoverage.html
//
// Currently, we use the inline counters feature of SanCov. To enable the
// instrumentation, we need to compile with:
//
//   -fsanitize-coverage=inline-8bit-counters
//
// This will create a 8-bit counter for each edge in the code.

#ifndef FUZZTEST_FUZZTEST_INTERNAL_COVERAGE_H_
#define FUZZTEST_FUZZTEST_INTERNAL_COVERAGE_H_

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <optional>

#include "absl/types/span.h"
#include "./fuzztest/internal/table_of_recent_compares.h"

#if defined(__linux__)
#define FUZZTEST_INTERNAL_ENABLE_STACK_SIZE_CHECK 1
#include <pthread.h>
#endif

namespace fuzztest::internal {

// Stack information for a thread under test.
struct ThreadStackInfo {
  // Stack allocated for the running thread.
  // Frame pointers are compared against it to make sure we are still in the
  // same stack. In some cases, like signal handlers, we might be using a
  // different stack.
  const char* allocated_stack_region_start = nullptr;
  size_t allocated_stack_region_size = 0;
  // The stack frame just before calling into the property function. Used as a
  // the baseline for stack usage calculation.
  const char* stack_frame_before_calling_property_function = nullptr;
};

// Represents the coverage information generated by the SanitizerCoverage
// instrumentation. Used for storing the coverage of a single input's execution.
//
// The counters are non-atomic. Race conditions are ignored. As well as
// overflows. Single threaded processes are more ideal for tests.
class ExecutionCoverage {
 public:
  explicit ExecutionCoverage(absl::Span<uint8_t> counter_map)
      : counter_map_(counter_map) {}

  // not copyable or movable because sanCov will only see one global instance.
  ExecutionCoverage(const ExecutionCoverage&) = delete;
  ExecutionCoverage& operator=(const ExecutionCoverage&) = delete;

  // Returns a view to the counter map.
  absl::Span<uint8_t> GetCounterMap() const { return counter_map_; }

  // Clears the counter map state and cmp/memcmp coverage states.
  // Not clearing tables_of_recent_compares_, this might introduce some
  // false positives in the dictionary, but the probability is low
  // from theory and experiments.
  void ResetState() {
    memset(new_cmp_counter_map_, 0, kCmpCovMapSize);
    memset(counter_map_.data(), 0, counter_map_.size());
    new_coverage_.store(false, std::memory_order_relaxed);

    max_stack_recorded_ = 0;
    auto& stack = test_thread_stack;
    if (!stack) {
      stack.emplace();
#if defined(FUZZTEST_INTERNAL_ENABLE_STACK_SIZE_CHECK)
      // Read the current stack information. This will help us later detect if a
      // stack frame pointer is within bounds.
      pthread_attr_t attr;
      void* addr;
      size_t size;
      if (pthread_getattr_np(pthread_self(), &attr) == 0 &&
          pthread_attr_getstack(&attr, &addr, &size) == 0) {
        stack->allocated_stack_region_start =
            reinterpret_cast<const char*>(addr);
        stack->allocated_stack_region_size = size;
        pthread_attr_destroy(&attr);
      }
#endif  // FUZZTEST_INTERNAL_ENABLE_STACK_SIZE_CHECK
    }
    stack->stack_frame_before_calling_property_function =
        GetCurrentStackFrame();
  }

  static char* GetCurrentStackFrame() {
#if defined(__has_builtin) && __has_builtin(__builtin_frame_address)
    return reinterpret_cast<char*>(__builtin_frame_address(0));
#else
    return nullptr;
#endif
  }

  // The size of cmp coverage maps, it's a randomly picked value. But
  // in the past we observe that it shouldn't be > 1MB otherwise it will
  // be the bottleneck. Now it's 256KB.
  static constexpr size_t kCmpCovMapSize = 1024U * 256;
  // Try update comparison coverage score.
  // If a higher score is found, set new_cmp_ to be mark a new coverage.
  void UpdateCmpMap(size_t index, uint8_t hamming_dist, uint8_t absolute_dist);

  bool NewCoverageFound() {
    return new_coverage_.load(std::memory_order_relaxed);
  }

  auto& GetTablesOfRecentCompares() { return tables_of_recent_compares_; }

  // Flag marking if the control flow is currently in target codes.
  // We don't want to collect unrelated updates to cmp score and dictionary.
  bool IsTracing() { return is_tracing_; }

  // Right before target run, call this method with true; right after
  // target run, call this method with false.
  void SetIsTracing(bool is_tracing) { is_tracing_ = is_tracing; }

  // Most of the time tests are run under the main thread, which has a very
  // large stack limit. On the other hand, code under test will tend to run on
  // threads with a much smaller stack size.
  // Instead of waiting for a stack overflow, we measure the stack usage and
  // abort the process if it finds it to be larger than
  // `MaxAllowedStackUsage()`. This limit can be configured via environment
  // variable `FUZZTEST_STACK_LIMIT`.
  size_t MaxAllowedStackUsage();
  // Update the PC->max stack usage map for `PC`.
  // It compares the current stack frame against the stack frame specified in
  // `test_thread_stack`. Only applies to the thread that sets
  // `test_thread_stack` and it is a noop on other threads.
  void UpdateMaxStack(uintptr_t PC);
  size_t MaxStackUsed() const { return max_stack_recorded_; }

 private:
  // 8-bit counters map, records the hit of edges.
  absl::Span<uint8_t> counter_map_;

  // New cmp coverage map.
  // `counter`: max counts of hits of a cmp instruction.
  // `hamming`: `sizeof(arg)` - hamming distance between the two args of a cmp
  // instruction.
  // `absolute`: 255 - `min(255, abs(arg1 - arg2))`. Absolute distance score.
  // If `counter_new` > `counter_old`, the score increases.
  // Else if `counter_new` == `counter_old`, then compare `hamming` and
  // `absolute`, any one of them has new value larger than old value, the score
  // increases.
  struct CmpScore {
    uint8_t counter;
    uint8_t hamming;
    uint8_t absolute;
  };
  uint8_t new_cmp_counter_map_[kCmpCovMapSize] = {};

  // Temporary map storing the hit counts of cmps for a target run.
  CmpScore max_cmp_map_[kCmpCovMapSize] = {};

  static inline std::optional<ThreadStackInfo> test_thread_stack = std::nullopt;
  // The watermark of stack usage observed on the test thread while tracing is
  // enabled.
  ptrdiff_t max_stack_recorded_ = 0;

  // Like on other coverage maps above, we record the max stack usage on
  // different PC seen. This allows the runtime to mark "more stack usage" as
  // "new coverage" per PC instead of globally.
  static constexpr size_t kMaxStackMapSize = 1024U * 256;
  uint32_t max_stack_map_[kMaxStackMapSize] = {};

  // Flag marking new coverage of any kind.
  std::atomic<bool> new_coverage_{false};

  TablesOfRecentCompares tables_of_recent_compares_ = {};
  bool is_tracing_ = false;
};

// Set the singleton ExecutionCoverage object.
void SetExecutionCoverage(ExecutionCoverage* value);
// Returns the singleton ExecutionCoverage object.
ExecutionCoverage* GetExecutionCoverage();

// Represents the aggregate coverage of all inputs in the corpus. Used for
// detecting if new coverage was triggered by executing an input.
class CorpusCoverage {
 public:
  // Creates initial blank coverage state with `map_size` counters. The map
  // contains one counter per edge.
  explicit CorpusCoverage(size_t map_size);
  ~CorpusCoverage();

  CorpusCoverage(const CorpusCoverage&) = delete;
  CorpusCoverage& operator=(const CorpusCoverage&) = delete;

  // Merges `execution_coverage` into corpus coverage. Returns true if new
  // coverage was triggered.
  bool Update(ExecutionCoverage* execution_coverage);

  // Returns the number of unique edges covered by the corpus.
  size_t GetNumberOfCoveredEdges() const {
    const size_t uncovered_edges =
        std::count(corpus_map_, corpus_map_ + corpus_map_size_, 0);
    return corpus_map_size_ - uncovered_edges;
  }

 private:
  size_t corpus_map_size_;
  uint8_t* corpus_map_;
};

}  // namespace fuzztest::internal

#endif  // FUZZTEST_FUZZTEST_INTERNAL_COVERAGE_H_