centipede/puzzles/callstack.cc

// Copyright 2023 The Centipede Authors.
//
// 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
//
//      https://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.

// Centipede puzzle: crashes when the input triggers a specific call stack.
// Functions F0, FA-FE call themselves recursively to depth up to kMaxDepth.
// Input data bytes are used to choose which function is called.
// All functions but F0 also modify `g_result`.
// The puzzle can be solved if the call sequence is FA->FB->FC->FD->FE.

// clang-format off
// RUN: Run --callstack_level=10 --use_cmp_features=0 --use_dataflow_features=0 // NOLINT
// RUN: SolutionIs ABCDE
// clang-format on
#include <cstddef>
#include <cstdint>

namespace {

// Don't let the compiler be too smart.
static inline void BreakOptimization(const void *arg) {
  __asm__ __volatile__("" : : "r"(arg) : "memory");
}

using F = void (*)(const uint8_t *data, size_t idx);
extern F table[256];

static constexpr size_t kMaxDepth = 5;

void F0(const uint8_t *data, size_t idx) {
  if (idx + 1 < kMaxDepth) table[data[idx + 1]](data, idx + 1);
  BreakOptimization(data);
}

constexpr uintptr_t kMagicA = 0xAA;
constexpr uintptr_t kMagicB = 0xBB;
constexpr uintptr_t kMagicC = 0xCC;
constexpr uintptr_t kMagicD = 0xDD;
constexpr uintptr_t kMagicE = 0xEE;
uintptr_t g_result;

void FA(const uint8_t *data, size_t idx) {
  g_result |= kMagicA << (idx * 8);
  if (idx + 1 < kMaxDepth) table[data[idx + 1]](data, idx + 1);
  BreakOptimization(data);
}

void FB(const uint8_t *data, size_t idx) {
  g_result |= kMagicB << (idx * 8);
  if (idx + 1 < kMaxDepth) table[data[idx + 1]](data, idx + 1);
  BreakOptimization(data);
}

void FC(const uint8_t *data, size_t idx) {
  g_result |= kMagicC << (idx * 8);
  if (idx + 1 < kMaxDepth) table[data[idx + 1]](data, idx + 1);
  BreakOptimization(data);
}

void FD(const uint8_t *data, size_t idx) {
  g_result |= kMagicD << (idx * 8);
  if (idx + 1 < kMaxDepth) table[data[idx + 1]](data, idx + 1);
  BreakOptimization(data);
}

void FE(const uint8_t *data, size_t idx) {
  g_result |= kMagicE << (idx * 8);
  if (idx + 1 < kMaxDepth) table[data[idx + 1]](data, idx + 1);
  BreakOptimization(data);
}

// Table of 256 function pointers.
// Most values are `F0`. The values at indices 'A', 'B', 'C', 'D', 'E'
// are FA, FB, FC, FD, FE respectively.
// clang-format off
F table[256] = {
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,  // 0-15
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,  // 16-31
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,  // 32-47
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,  // 48-63
  // Special values FA, FB, FC, FD, FE in this line:
  F0, FA, FB, FC, FD, FE, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,  // 64-79
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
  F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0, F0,
};
// clang-format on

}  // namespace

// Causes div-by-zero if the input is exactly 'ABCDE'.
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
  g_result = 0;
  if (size != kMaxDepth) return 0;
  table[data[0]](data, 0);
  g_result = 1000 / (0xEEDDCCBBAA - g_result);
  return 0;
}