좀 열심히 쓴 글

LibFuzzer code coverage 분석(8bit counter) / LibFuzzer 수정

ch4rli3kop 2020. 6. 14. 18:12
반응형

[BoB8_박찬희] HW#3

Contents : LibFuzzer code coverage 분석(8bit counter) / LibFuzzer 수정

제출기한 : 01/23/2020 PM:11:59:59

제출방법 : singi.bob8@gmail.com / 7z / password : bob8

Index

LibFuzzer 분석

Inline 8bit Counters

LLVM에서 제공하는 Code Coverage 기능 중 Inline 8bit-counters 기능은 다음과 같은 코드를 삽입함으로써 이루어지게 됩니다.

   mov    al,BYTE PTR ds:0x60104d
  add   al,0x1
  mov   BYTE PTR ds:0x60104d,al

각 edge마다 1바이트의 공간이 할당되며, 해당 edge를 지나갈 때마다 1씩 counter를 증가시킵니다.

다음은 할당된 counter 영역의 예시입니다.

pwndbg> x/10bx 0x60104d
0x60104d: 0x01 0x11 0x00 0x01 0x00 0x00 0x00 0x00
0x601055: 0x00 0x00

coverage 측정을 위한 inline 8bit counters 기능은 __sanitizer_cov_8bit_counters_init()으로 정의할 수 있습니다. libfuzzer에서 해당 함수는 다음과 같이 동작하게 됩니다.

ATTRIBUTE_INTERFACE
void __sanitizer_cov_8bit_counters_init(uint8_t *Start, uint8_t *Stop) {
 fuzzer::TPC.HandleInline8bitCountersInit(Start, Stop);
}

void TracePC::HandleInline8bitCountersInit(uint8_t *Start, uint8_t *Stop) {
 if (Start == Stop) return;
 if (NumModules &&
     Modules[NumModules - 1].Start() == Start)
   return;
 assert(NumModules <
        sizeof(Modules) / sizeof(Modules[0]));
 auto &M = Modules[NumModules++];
 uint8_t *AlignedStart = RoundUpByPage(Start);
 uint8_t *AlignedStop  = RoundDownByPage(Stop);
 size_t NumFullPages = AlignedStop > AlignedStart ?
                      (AlignedStop - AlignedStart) / PageSize() : 0;
 bool NeedFirst = Start < AlignedStart || !NumFullPages;
 bool NeedLast  = Stop > AlignedStop && AlignedStop >= AlignedStart;
 M.NumRegions = NumFullPages + NeedFirst + NeedLast;;
 assert(M.NumRegions > 0);
 M.Regions = new Module::Region[M.NumRegions];
 assert(M.Regions);
 size_t R = 0;
 if (NeedFirst)
   M.Regions[R++] = {Start, std::min(Stop, AlignedStart), true, false};
 for (uint8_t *P = AlignedStart; P < AlignedStop; P += PageSize())
   M.Regions[R++] = {P, P + PageSize(), true, true};
 if (NeedLast)
   M.Regions[R++] = {AlignedStop, Stop, true, false};
 assert(R == M.NumRegions);
 assert(M.Size() == (size_t)(Stop - Start));
 assert(M.Stop() == Stop);
 assert(M.Start() == Start);
 NumInline8bitCounters += M.Size();
}

Start, Stop은 할당된 counter 영역의 시작과 끝 주소를 나타내는데, 해당 영역을 PageSize(0x1000) 단위로 나누어 각 각 하나의 Region 구조체로 관리합니다. 시작 Region과 끝 Region은 페이지의 중간에 존재하는 경우가 있기 때문에, Aligned된 주소가 아닌 Start, Stop을 시작/끝 주소로 합니다. OneFullPage를 false로 하는 것도 같은 이유입니다. 일반적으로 다음과 같은 구조가 될 것입니다.

  Region[0]  |  Region[1]  |  ...  |  Region[last-1]  |  Region[last]
      start |   full     |       |       full       |   last

하나의 Module은 하나의 Target을 뜻하므로, 결국 하나의 Target에 대해서 Region 배열로 이루어진 8bit counter bitmap을 가지게 됩니다. (M.Regions = new Module::Region[M.NumRegions]; 참고)

FuzzerTracePC.h

// Module represents the array of 8-bit counters split into regions
// such that every region, except maybe the first and the last one, is one
// full page.
struct Module {
struct Region {
  uint8_t *Start, *Stop;
  bool Enabled;
  bool OneFullPage;
};
Region *Regions;
size_t NumRegions;
uint8_t *Start() { return Regions[0].Start; }
uint8_t *Stop() { return Regions[NumRegions - 1].Stop; }
size_t Size()   { return Stop() - Start(); }
size_t  Idx(uint8_t *P) {
  assert(P >= Start() && P < Stop());
  return P - Start();
}
};

Module Modules[4096];
size_t NumModules;  // linker-initialized.
size_t NumInline8bitCounters;

따라서 정리하자면 TracePC::HandleInline8bitCountersInit()은 counter에 대한 bitmap을 초기화하는 단계입니다.

Summary

LibFuzzer의 주요 동작은 다음과 같습니다.

main() -> FuzzerDriver()

FuzzerDriver() +-> ReadCorpora()
              +-> F->Loop()
             
F->Loop() +-> ReadAndExecuteSeedCorpora() +-> ExecuteCallback()
        |                               +-> RunOne() -> ExecuteCallback()
        |                               +-> RunOne() -> ExecuteCallback()
        |                               |...
         +-> MutateAndTestOne()
         
MutateAndTestOne() -> RunOne() -> ExecuteCallback()

FuzzerMain.cpp / main

#include "FuzzerDefs.h"

extern "C" {
// This function should be defined by the user.
int LLVMFuzzerTestOneInput(const uint8_t *Data, size_t Size);
}  // extern "C"

ATTRIBUTE_INTERFACE int main(int argc, char **argv) {
 return fuzzer::FuzzerDriver(&argc, &argv, LLVMFuzzerTestOneInput);
}

LLVMFuzzerTestOneInput() 함수를 세 번째 인자인 Callback 함수로 등록합니다.

FuzzerDriver.cpp / FuzzerDriver()

int FuzzerDriver(int *argc, char ***argv, UserCallback Callback) {
 using namespace fuzzer;
 assert(argc && argv && "Argument pointers cannot be nullptr");
 std::string Argv0((*argv)[0]);
 EF = new ExternalFunctions();
 if (EF->LLVMFuzzerInitialize)
   EF->LLVMFuzzerInitialize(argc, argv);
 if (EF->__msan_scoped_disable_interceptor_checks)
   EF->__msan_scoped_disable_interceptor_checks();
 const Vector<std::string> Args(*argv, *argv + *argc);
 assert(!Args.empty());

포인터 Null 초기화, 인자 정리 등의 초기화 과정들이 수행됩니다.

ProgName = new std::string(Args[0]);
 if (Argv0 != *ProgName) {
   Printf("ERROR: argv[0] has been modified in LLVMFuzzerInitialize\n");
   exit(1);
}
 ParseFlags(Args, EF);
 if (Flags.help) {
   PrintHelp();
   return 0;
}

...
 
unsigned Seed = Flags.seed;
 // Initialize Seed.
 if (Seed == 0)
   Seed =
       std::chrono::system_clock::now().time_since_epoch().count() + GetPid();
 if (Flags.verbosity)
   Printf("INFO: Seed: %u\n", Seed);

...

 Random Rand(Seed);
 auto *MD = new MutationDispatcher(Rand, Options);
 auto *Corpus = new InputCorpus(Options.OutputCorpus);
 auto *F = new Fuzzer(Callback, *Corpus, *MD, Options);

...
   
 if (Flags.fork)
   FuzzWithFork(F->GetMD().GetRand(), Options, Args, *Inputs, Flags.fork);

 if (Flags.merge)
   Merge(F, Options, Args, *Inputs, Flags.merge_control_file);

ParseFlags()를 통해 인자를 파싱하여 읽어온 플래그를 FuzzingOptions 구조체에 저장하고, 지정된 옵션에 따라 각각의 동작을 호출합니다. 그 외에 시스템 시간 정보와 pid 정보를 활용하여 Seed를 생성하고, MutationDispatcher, InputCorpus, Fuzzer 객체들을 생성하는 작업을 수행합니다.

...
   
 auto CorporaFiles = ReadCorpora(*Inputs, ParseSeedInuts(Flags.seed_inputs));
 F->Loop(CorporaFiles);

 if (Flags.verbosity)
   Printf("Done %zd runs in %zd second(s)\n", F->getTotalNumberOfRuns(),
          F->secondsSinceProcessStartUp());
 F->PrintFinalStats();

 exit(0);  // Don't let F destroy itself.
}

Inputs은 corpus 디렉토리가 들어가고, ParseSeedInuts()는 -seed_inputs 옵션으로 추가적인 corpus로 제공할 파일이 들어가게 됩니다. ReadCorpora()는 이러한 corpus 파일들을 {파일 이름, 크기} 형태로 저장한 벡터를 리턴합니다. ReadCorpora()의 자세한 코드는 다음과 같습니다.

FuzzerDriver.cpp / ReadCorpora()

static Vector<SizedFile> ReadCorpora(const Vector<std::string> &CorpusDirs,
const Vector<std::string> &ExtraSeedFiles) {
Vector<SizedFile> SizedFiles;
size_t LastNumFiles = 0;
for (auto &Dir : CorpusDirs) {
GetSizedFilesFromDir(Dir, &SizedFiles);
Printf("INFO: % 8zd files found in %s\n", SizedFiles.size() - LastNumFiles,
       Dir.c_str());
LastNumFiles = SizedFiles.size();
}
for (auto &File : ExtraSeedFiles)
if (auto Size = FileSize(File))
  SizedFiles.push_back({File, Size});
return SizedFiles;
}

Corpus 디렉토리 내에 존재하는 파일들은 다음의 GetSizedFilesFromDir()을 이용하여 SizedFile 벡터에 저장됩니다.

FuzzerIO.cpp / GetSizedFilesFromDir()

void GetSizedFilesFromDir(const std::string &Dir, Vector<SizedFile> *V) {
Vector<std::string> Files;
ListFilesInDirRecursive(Dir, 0, &Files, /*TopDir*/true);
for (auto &File : Files)
if (size_t Size = FileSize(File))
  V->push_back({File, Size});
}

남은 부분을 마저 살펴보겠습니다.

...
   
 auto CorporaFiles = ReadCorpora(*Inputs, ParseSeedInuts(Flags.seed_inputs));
 F->Loop(CorporaFiles);

 if (Flags.verbosity)
   Printf("Done %zd runs in %zd second(s)\n", F->getTotalNumberOfRuns(),
          F->secondsSinceProcessStartUp());
 F->PrintFinalStats();

 exit(0);  // Don't let F destroy itself.
}

F->Loop()에서 Corpus를 읽고 Mutation 하고 Execute 등의 작업이 수행됩니다. 그 외에 verbosity 옵션에 따른 추가적인 출력과 다음과 같이 퍼져 동작과 관련된 상태 정보를 출력하는 F->PrintFinalStats()가 수행됩니다.

FuzzerLoop.cpp / PrintFinalStats()

void Fuzzer::PrintFinalStats() {
if (Options.PrintCoverage)
TPC.PrintCoverage();
if (Options.PrintCorpusStats)
Corpus.PrintStats();
if (!Options.PrintFinalStats)
return;
size_t ExecPerSec = execPerSec();
Printf("stat::number_of_executed_units: %zd\n", TotalNumberOfRuns);
Printf("stat::average_exec_per_sec:     %zd\n", ExecPerSec);
Printf("stat::new_units_added:         %zd\n", NumberOfNewUnitsAdded);
Printf("stat::slowest_unit_time_sec:   %zd\n", TimeOfLongestUnitInSeconds);
Printf("stat::peak_rss_mb:             %zd\n", GetPeakRSSMb());
}

FuzzerLoop.cpp / F->Loop()

퍼져의 동작과 관련된 주요 코드입니다. DFT는 Data-Flow-Guided Fuzzing과 관련된 부분이므로 건너뛰고 설명을 진행하겠습니다. 다음은 FuzzerDriver()auto *F = new Fuzzer(Callback, *Corpus, *MD, Options);에서 생성한 Fuzzer()의 생성자입니다.

Fuzzer::Fuzzer(UserCallback CB, InputCorpus &Corpus, MutationDispatcher &MD,
              FuzzingOptions Options)
  : CB(CB), Corpus(Corpus), MD(MD), Options(Options) {
 if (EF->__sanitizer_set_death_callback)
   EF->__sanitizer_set_death_callback(StaticDeathCallback);
 assert(!F);
 F = this;
 TPC.ResetMaps();
 IsMyThread = true;
 if (Options.DetectLeaks && EF->__sanitizer_install_malloc_and_free_hooks)
   EF->__sanitizer_install_malloc_and_free_hooks(MallocHook, FreeHook);
 TPC.SetUseCounters(Options.UseCounters);
 TPC.SetUseValueProfileMask(Options.UseValueProfile);

 if (Options.Verbosity)
   TPC.PrintModuleInfo();
 if (!Options.OutputCorpus.empty() && Options.ReloadIntervalSec)
   EpochOfLastReadOfOutputCorpus = GetEpoch(Options.OutputCorpus);
 MaxInputLen = MaxMutationLen = Options.MaxLen;
 TmpMaxMutationLen = 0;  // Will be set once we load the corpus.
 AllocateCurrentUnitData();
 CurrentUnitSize = 0;
 memset(BaseSha1, 0, sizeof(BaseSha1));
}

해당 부분에서는 TPC와 관련된 동작을 수행합니다. TPC.ResetMaps()를 이용하여 counters Regions를 모두 0으로 초기화함으로써 counter bitmap을 초기화합니다. 그 외에 퍼징 과정에서 사용되는 데이터의 length, size 등을 0으로 초기화합니다.

TPC.SetUseCounters(Options.UseCounters)에서 coverage counters 옵션을 켜게됩니다. 인자를 따라가보면, 다음과 같이 되고, Options.UseCounters = Flags.use_counters; -> FUZZER_FLAG_INT(use_counters, 1, "Use coverage counters"). void SetUseCounters(bool UC) { UseCounters = UC; }으로 인해 UseCounters라는 변수가 True로 세팅이 됩니다.

F->Loop()에서 동작하는 Loop()에 대하여 분석해보겠습니다.

namespace fuzzer {
static const size_t kMaxUnitSizeToPrint = 256;

thread_local bool Fuzzer::IsMyThread;

bool RunningUserCallback = false;

// Only one Fuzzer per process.
static Fuzzer *F;
   
  ...
       
void Fuzzer::Loop(Vector<SizedFile> &CorporaFiles) {
 auto FocusFunctionOrAuto = Options.FocusFunction;
 DFT.Init(Options.DataFlowTrace, &FocusFunctionOrAuto, CorporaFiles,
          MD.GetRand());
 TPC.SetFocusFunction(FocusFunctionOrAuto);
 ReadAndExecuteSeedCorpora(CorporaFiles);
 DFT.Clear();  // No need for DFT any more.
 TPC.SetPrintNewPCs(Options.PrintNewCovPcs);
 TPC.SetPrintNewFuncs(Options.PrintNewCovFuncs);
 system_clock::time_point LastCorpusReload = system_clock::now();

 TmpMaxMutationLen =
     Min(MaxMutationLen, Max(size_t(4), Corpus.MaxInputSize()));

...

먼저 Fuzzer::Loop()의 앞 부분을 살펴보면, DFT와 PC Table과 관련된 부분들이 존재합니다. 그 외에는 ReadAndExecuteSeedCorpora()과 옵션들에 대한 설정을 해주는 부분, 시간을 측정하는 부분, Mutation length의 최댓 값을 정해주는 부분이 존재합니다. 여기서는 ReadAndExecuteSeedCorpora()에 대해 살펴보겠습니다.

FuzzerLoop.cpp / ReadAndExecuteSeedCorpora()

void Fuzzer::ReadAndExecuteSeedCorpora(Vector<SizedFile> &CorporaFiles) {
const size_t kMaxSaneLen = 1 << 20;
const size_t kMinDefaultLen = 4096;
size_t MaxSize = 0;
size_t MinSize = -1;
size_t TotalSize = 0;
for (auto &File : CorporaFiles) {
MaxSize = Max(File.Size, MaxSize);
MinSize = Min(File.Size, MinSize);
TotalSize += File.Size;
}
if (Options.MaxLen == 0)
SetMaxInputLen(std::min(std::max(kMinDefaultLen, MaxSize), kMaxSaneLen));
assert(MaxInputLen > 0);

// Test the callback with empty input and never try it again.
uint8_t dummy = 0;
ExecuteCallback(&dummy, 0);

if (CorporaFiles.empty()) {
Printf("INFO: A corpus is not provided, starting from an empty corpus\n");
Unit U({'\n'}); // Valid ASCII input.
RunOne(U.data(), U.size());
} else {
Printf("INFO: seed corpus: files: %zd min: %zdb max: %zdb total: %zdb"
       " rss: %zdMb\n",
       CorporaFiles.size(), MinSize, MaxSize, TotalSize, GetPeakRSSMb());
if (Options.ShuffleAtStartUp)
  std::shuffle(CorporaFiles.begin(), CorporaFiles.end(), MD.GetRand());

if (Options.PreferSmall) {
  std::stable_sort(CorporaFiles.begin(), CorporaFiles.end());
  assert(CorporaFiles.front().Size <= CorporaFiles.back().Size);
}

// Load and execute inputs one by one.
for (auto &SF : CorporaFiles) {
  auto U = FileToVector(SF.File, MaxInputLen, /*ExitOnError=*/false);
  assert(U.size() <= MaxInputLen);
  RunOne(U.data(), U.size());
  CheckExitOnSrcPosOrItem();
  TryDetectingAMemoryLeak(U.data(), U.size(),
                          /*DuringInitialCorpusExecution*/ true);
}
}

PrintStats("INITED");
if (!Options.FocusFunction.empty())
Printf("INFO: %zd/%zd inputs touch the focus function\n",
       Corpus.NumInputsThatTouchFocusFunction(), Corpus.size());
if (!Options.DataFlowTrace.empty())
Printf("INFO: %zd/%zd inputs have the Data Flow Trace\n",
       Corpus.NumInputsWithDataFlowTrace(), Corpus.size());

if (Corpus.empty() && Options.MaxNumberOfRuns) {
Printf("ERROR: no interesting inputs were found. "
       "Is the code instrumented for coverage? Exiting.\n");
exit(1);
}
}

ReadAndExecuteSeedCorpora()는 Seed 디렉토리 내의 파일들을 Input으로 실행시킵니다. 파일들의 최대/최소 사이즈를 구하는 작업 이 후, ExecuteCallback(&dummy, 0)을 통해 더비 데이터를 먼저 input으로 실행해봅니다. ExecuteCallback()은 앞서 Callback으로 등록해 둔 퍼징 대상을 호출하는 함수인데, 이에 대해서는 뒤에서 자세히 설명하겠습니다.

Input으로 넣을 파일들의 순서 및 추가 기능에 대한 옵션은 넘어가면, CorporaFile 즉 Seed 파일의 유무에 따라 동작이 달라지게 됩니다. 만약 Seed 파일이 존재하지 않는다면, '\n'으로 기본적인 Data를 만들어줘서 RunOne()을 호출하고, 파일이 존재한다면 하나씩 읽어들여 RunOne()을 호출합니다. RunOne()ExecuteCallback()을 호출하고 해당 결과로 생성된 coverage 정보에 따라 Corpus를 추가하는 등의 작업을 수행하는 함수입니다. 이에 대해서도 뒤에서 자세히 설명하겠습니다.

다음은 Loop() 안에 존재하는 while 문입니다.

...  
 while (true) {
   auto Now = system_clock::now();
   if (!Options.StopFile.empty() &&
       !FileToVector(Options.StopFile, 1, false).empty())
     break;
   if (duration_cast<seconds>(Now - LastCorpusReload).count() >=
       Options.ReloadIntervalSec) {
     RereadOutputCorpus(MaxInputLen);
     LastCorpusReload = system_clock::now();
  }
   if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
     break;
   if (TimedOut())
     break;

   // Update TmpMaxMutationLen
   if (Options.LenControl) {
     if (TmpMaxMutationLen < MaxMutationLen &&
         TotalNumberOfRuns - LastCorpusUpdateRun >
             Options.LenControl * Log(TmpMaxMutationLen)) {
       TmpMaxMutationLen =
           Min(MaxMutationLen, TmpMaxMutationLen + Log(TmpMaxMutationLen));
       LastCorpusUpdateRun = TotalNumberOfRuns;
    }
  } else {
     TmpMaxMutationLen = MaxMutationLen;
  }

   // Perform several mutations and runs.
   MutateAndTestOne();

   PurgeAllocator();
}

 PrintStats("DONE ", "\n");
 MD.PrintRecommendedDictionary();
}

시간과 관련된 부분들을 설정해주며, 파일이 비었거나 최대 실행 횟수, 타임 아웃 등에 대한 처리를 수행합니다. 해당 작업들이 완료되면, Input을 Mutation하고 실행하는 MutateAndTestOne()을 호출합니다.

FuzzerLoop.cpp / MutateAndTestOne()

MutateAndTestOne()은 다음과 같습니다.

void Fuzzer::MutateAndTestOne() {
 MD.StartMutationSequence();

 auto &II = Corpus.ChooseUnitToMutate(MD.GetRand());
 if (Options.DoCrossOver)
   MD.SetCrossOverWith(&Corpus.ChooseUnitToMutate(MD.GetRand()).U);
 const auto &U = II.U;
 memcpy(BaseSha1, II.Sha1, sizeof(BaseSha1));
 assert(CurrentUnitData);
 size_t Size = U.size();
 assert(Size <= MaxInputLen && "Oversized Unit");
 memcpy(CurrentUnitData, U.data(), Size);

 assert(MaxMutationLen > 0);

 size_t CurrentMaxMutationLen =
     Min(MaxMutationLen, Max(U.size(), TmpMaxMutationLen));
 assert(CurrentMaxMutationLen > 0);

 for (int i = 0; i < Options.MutateDepth; i++) {
   if (TotalNumberOfRuns >= Options.MaxNumberOfRuns)
     break;
   MaybeExitGracefully();
   size_t NewSize = 0;
   if (II.HasFocusFunction && !II.DataFlowTraceForFocusFunction.empty() &&
       Size <= CurrentMaxMutationLen)
     NewSize = MD.MutateWithMask(CurrentUnitData, Size, Size,
                                 II.DataFlowTraceForFocusFunction);

   // If MutateWithMask either failed or wasn't called, call default Mutate.
   if (!NewSize)
     NewSize = MD.Mutate(CurrentUnitData, Size, CurrentMaxMutationLen);
   assert(NewSize > 0 && "Mutator returned empty unit");
   assert(NewSize <= CurrentMaxMutationLen && "Mutator return oversized unit");
   Size = NewSize;
   II.NumExecutedMutations++;

   bool FoundUniqFeatures = false;
   bool NewCov = RunOne(CurrentUnitData, Size, /*MayDeleteFile=*/true, &II,
                        &FoundUniqFeatures);
   TryDetectingAMemoryLeak(CurrentUnitData, Size,
                           /*DuringInitialCorpusExecution*/ false);
   if (NewCov) {
     ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
     break;  // We will mutate this input more in the next rounds.
  }
   if (Options.ReduceDepth && !FoundUniqFeatures)
     break;
}
}

가장 먼저 보이는 MD는 아까 FuzzerDriver의 auto *MD = new MutationDispatcher(Rand, Options);에서 생성했던 MutationDispatcher 입니다. MD.StartMutationSequence()를 통해 Mutation Sequence와 관련된 벡터를 초기화합니다. Corpus.ChooseUnitToMutate()를 이용하여 II에는 Input 벡터 중에 랜덤으로 선택된 Input이 들어가게 됩니다. 이 Input은 아까 ReadAndExecuteSeedCorpora()에서 호출했던 RunOne()을 통해 처음 생성됩니다.

선택한 Input 데이터를 CurrentUnitData로 관리하는데, 이 데이터를 MD.MutateWithMask()를 사용하여 처음 Mutation 하게되고, Size가 0이라면 MD.Mutate()로 또 Mutation 작업을 수행하게 됩니다. 이후 RunOne()을 통해 생성한 CurrentUnitData로 퍼징을 수행하고, 새로운 coverage를 발견했다면 CurrentUnitData의 sha1을 이름으로 하는 corpus 파일을 생성합니다. 앞의 과정에서 coverage 정보를 가져온다면 TryDetectingAMemoryLeak()을 통해서 ExecuteCallback()을 한 번 더 호출하여 Crash 여부를 확인합니다. LLVM 내에 정의된 함수를 이용하여 Leak된 여부를 확인합니다.

위 과정은 새로운 coverage를 발견할 때까지 설정된 MutationDepth 만큼 반복됩니다.

FuzzerMutate.cpp / MutateWithMask() , Mutate()

Mutation 시 사용한 함수는 다음과 같습니다.

size_t MutationDispatcher::MutateWithMask(uint8_t *Data, size_t Size,
                                      size_t MaxSize,
                                      const Vector<uint8_t> &Mask) {
size_t MaskedSize = std::min(Size, Mask.size());
// * Copy the worthy bytes into a temporary array T
// * Mutate T
// * Copy T back.
// This is totally unoptimized.
auto &T = MutateWithMaskTemp;
if (T.size() < Size)
T.resize(Size);
size_t OneBits = 0;
for (size_t I = 0; I < MaskedSize; I++)
if (Mask[I])
  T[OneBits++] = Data[I];

if (!OneBits) return 0;
assert(!T.empty());
size_t NewSize = Mutate(T.data(), OneBits, OneBits);
assert(NewSize <= OneBits);
(void)NewSize;
// Even if NewSize < OneBits we still use all OneBits bytes.
for (size_t I = 0, J = 0; I < MaskedSize; I++)
if (Mask[I])
  Data[I] = T[J++];
return Size;
}

size_t MutationDispatcher::Mutate(uint8_t *Data, size_t Size, size_t MaxSize) {
return MutateImpl(Data, Size, MaxSize, Mutators);
}

위와 같이 구현되어 있는데, 두 과정 모두 결국 Mutate() -> MutateImpl()를 거칩니다. 따라가보면 다음과 같이 DefaultMutators와 Custom Mutator 등으로 구현된 Mutator를 사용하는 것을 확인 할 수 있습니다.

...
DefaultMutators.insert(
  DefaultMutators.begin(),
  {
      {&MutationDispatcher::Mutate_EraseBytes, "EraseBytes"},
      {&MutationDispatcher::Mutate_InsertByte, "InsertByte"},
      {&MutationDispatcher::Mutate_InsertRepeatedBytes,
       "InsertRepeatedBytes"},
      {&MutationDispatcher::Mutate_ChangeByte, "ChangeByte"},
      {&MutationDispatcher::Mutate_ChangeBit, "ChangeBit"},
      {&MutationDispatcher::Mutate_ShuffleBytes, "ShuffleBytes"},
      {&MutationDispatcher::Mutate_ChangeASCIIInteger, "ChangeASCIIInt"},
      {&MutationDispatcher::Mutate_ChangeBinaryInteger, "ChangeBinInt"},
      {&MutationDispatcher::Mutate_CopyPart, "CopyPart"},
      {&MutationDispatcher::Mutate_CrossOver, "CrossOver"},
      {&MutationDispatcher::Mutate_AddWordFromManualDictionary,
       "ManualDict"},
      {&MutationDispatcher::Mutate_AddWordFromPersistentAutoDictionary,
       "PersAutoDict"},
  });
...
if (EF->LLVMFuzzerCustomMutator)
Mutators.push_back({&MutationDispatcher::Mutate_Custom, "Custom"});
else
Mutators = DefaultMutators;

if (EF->LLVMFuzzerCustomCrossOver)
Mutators.push_back(
    {&MutationDispatcher::Mutate_CustomCrossOver, "CustomCrossOver"});

FuzzerLoop.cpp / RunOne()

RunOne()은 다음과 같습니다.

bool Fuzzer::RunOne(const uint8_t *Data, size_t Size, bool MayDeleteFile,
                   InputInfo *II, bool *FoundUniqFeatures) {
 if (!Size)
   return false;

 ExecuteCallback(Data, Size);

 UniqFeatureSetTmp.clear();
 size_t FoundUniqFeaturesOfII = 0;
 size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
 TPC.CollectFeatures([&](size_t Feature) {
   if (Corpus.AddFeature(Feature, Size, Options.Shrink))
     UniqFeatureSetTmp.push_back(Feature);
   if (Options.ReduceInputs && II)
     if (std::binary_search(II->UniqFeatureSet.begin(),
                            II->UniqFeatureSet.end(), Feature))
       FoundUniqFeaturesOfII++;
});

먼저 ExecuteCallback()이 호출되고, TPC.CollectFeatures()이 호출됩니다.

FuzzerLoop.cpp / ExecuteCallback()

ExecuteCallback()은 다음과 같습니다. 스택을 초기화시키고, 실행 횟수 늘리기, 시간 측정, bitmap 초기화 등의 작업을 수행한 뒤, Main에서 UserCallback으로 등록한 CB에 Data와 사이즈를 인자로 주고, 호출합니다.

void Fuzzer::ExecuteCallback(const uint8_t *Data, size_t Size) {
TPC.RecordInitialStack();
TotalNumberOfRuns++;
assert(InFuzzingThread());
// We copy the contents of Unit into a separate heap buffer
// so that we reliably find buffer overflows in it.
uint8_t *DataCopy = new uint8_t[Size];
memcpy(DataCopy, Data, Size);
if (EF->__msan_unpoison)
EF->__msan_unpoison(DataCopy, Size);
if (EF->__msan_unpoison_param)
EF->__msan_unpoison_param(2);
if (CurrentUnitData && CurrentUnitData != Data)
memcpy(CurrentUnitData, Data, Size);
CurrentUnitSize = Size;
{
ScopedEnableMsanInterceptorChecks S;
AllocTracer.Start(Options.TraceMalloc);
UnitStartTime = system_clock::now();
TPC.ResetMaps();
RunningUserCallback = true;
int Res = CB(DataCopy, Size);
RunningUserCallback = false;
UnitStopTime = system_clock::now();
(void)Res;
assert(Res == 0);
HasMoreMallocsThanFrees = AllocTracer.Stop();
}
if (!LooseMemeq(DataCopy, Data, Size))
CrashOnOverwrittenData();
CurrentUnitSize = 0;
delete[] DataCopy;
}

FuzzerTracePC.h / CollectFeatures()

UseCounters가 True로 설정되어 있기 때문에, Handle8bitCounter()가 호출되는 경우 HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));가 호출됩니다. 각 각의 8bit counter마다 한 번씩 호출됩니다.

FirstFeature는 0부터 시작하여 Region 증가할 때마다 커지는 값으로, 구간 별로 구분하기 위한 베이스가 되는 값입니다. Idx는 Region 첫 aligned 된 주소부터 현재 counter까지의 offset을 나타내는데, 여기에 8을 곱한 값에 counter 값에 따른 각 구간 별 특정 값을 더함으로써, Feature 값이 최대한 다른 counter와 동일한 값을 갖지 않도록 하기 위함입니다.

template <class Callback>  // void Callback(size_t Feature)
ATTRIBUTE_NO_SANITIZE_ADDRESS
ATTRIBUTE_NOINLINE
void TracePC::CollectFeatures(Callback HandleFeature) const {
auto Handle8bitCounter = [&](size_t FirstFeature,
                           size_t Idx, uint8_t Counter) {
if (UseCounters)
  HandleFeature(FirstFeature + Idx * 8 + CounterToFeature(Counter));
else
  HandleFeature(FirstFeature + Idx);
};

size_t FirstFeature = 0;

for (size_t i = 0; i < NumModules; i++) {
for (size_t r = 0; r < Modules[i].NumRegions; r++) {
  if (!Modules[i].Regions[r].Enabled) continue;
  FirstFeature += 8 * ForEachNonZeroByte(Modules[i].Regions[r].Start,
                                         Modules[i].Regions[r].Stop,
                                         FirstFeature, Handle8bitCounter);
}
}

FirstFeature +=
  8 * ForEachNonZeroByte(ExtraCountersBegin(), ExtraCountersEnd(),
                         FirstFeature, Handle8bitCounter);

if (UseValueProfileMask) {
ValueProfileMap.ForEach([&](size_t Idx) {
  HandleFeature(FirstFeature + Idx);
});
FirstFeature += ValueProfileMap.SizeInBits();
}

// Step function, grows similar to 8 * Log_2(A).
auto StackDepthStepFunction = [](uint32_t A) -> uint32_t {
if (!A) return A;
uint32_t Log2 = Log(A);
if (Log2 < 3) return A;
Log2 -= 3;
return (Log2 + 1) * 8 + ((A >> Log2) & 7);
};
assert(StackDepthStepFunction(1024) == 64);
assert(StackDepthStepFunction(1024 * 4) == 80);
assert(StackDepthStepFunction(1024 * 1024) == 144);

if (auto MaxStackOffset = GetMaxStackOffset())
HandleFeature(FirstFeature + StackDepthStepFunction(MaxStackOffset / 8));
}

FuzzerTracePC.h / CounterToFeature()

각 count 구간마다 미리 정의해놓은 Feature number를 리턴합니다.

// Given a non-zero Counter returns a number in the range [0,7].
template<class T>
unsigned CounterToFeature(T Counter) {
// Returns a feature number by placing Counters into buckets as illustrated
// below.
//
// Counter bucket: [1] [2] [3] [4-7] [8-15] [16-31] [32-127] [128+]
// Feature number: 0   1   2   3     4       5       6       7
//
// This is a heuristic taken from AFL (see
// http://lcamtuf.coredump.cx/afl/technical_details.txt).
//
// This implementation may change in the future so clients should
// not rely on it.
assert(Counter);
unsigned Bit = 0;
/**/ if (Counter >= 128) Bit = 7;
else if (Counter >= 32) Bit = 6;
else if (Counter >= 16) Bit = 5;
else if (Counter >= 8) Bit = 4;
else if (Counter >= 4) Bit = 3;
else if (Counter >= 3) Bit = 2;
else if (Counter >= 2) Bit = 1;
return Bit;
}

FuzzerTracePC.h / ForEachNonZeroByte()

Region 단위로 제공된 인자의 counter 영역에서 1바이트씩 각 counter 마다 콜백 함수를 호출합니다.

두 번째 구간에서 Step을 통해 8바이트 단위로 빠르게 이동할 수 있도록 하였습니다. 첫 번째 구간은 aligned 된 메모리 영역에서 시작하지 않는 첫 번째 region을 8바이트 단위로 aligned 될 때까지 처리하기 위함이고, 마찬가지로 세 번째 구간은 가장 마지막 region이 8바이트 단위로 aligned 된 나머지를 처리하기 위함입니다.

template <class Callback>
// void Callback(size_t FirstFeature, size_t Idx, uint8_t Value);
ATTRIBUTE_NO_SANITIZE_ALL
size_t ForEachNonZeroByte(const uint8_t *Begin, const uint8_t *End,
                    size_t FirstFeature, Callback Handle8bitCounter) {
typedef uintptr_t LargeType;
const size_t Step = sizeof(LargeType) / sizeof(uint8_t);
const size_t StepMask = Step - 1;  // 0xb0111
auto P = Begin;

// Iterate by 1 byte until either the alignment boundary or the end.
for (; reinterpret_cast<uintptr_t>(P) & StepMask && P < End; P++)
if (uint8_t V = *P)
  Handle8bitCounter(FirstFeature, P - Begin, V);

// Iterate by Step bytes at a time.
for (; P < End; P += Step)
if (LargeType Bundle = *reinterpret_cast<const LargeType *>(P))
  for (size_t I = 0; I < Step; I++, Bundle >>= 8)
    if (uint8_t V = Bundle & 0xff)
      Handle8bitCounter(FirstFeature, P - Begin + I, V);

// Iterate by 1 byte until the end.
for (; P < End; P++)
if (uint8_t V = *P)
  Handle8bitCounter(FirstFeature, P - Begin, V);
return End - Begin;
}

필요한 정보들을 다 얻었으니 다시 한번 코드를 살펴보도록 하겠습니다.

...
   
 UniqFeatureSetTmp.clear();
 size_t FoundUniqFeaturesOfII = 0;
 size_t NumUpdatesBefore = Corpus.NumFeatureUpdates();
 TPC.CollectFeatures([&](size_t Feature) {
   if (Corpus.AddFeature(Feature, Size, Options.Shrink))
     UniqFeatureSetTmp.push_back(Feature);
   if (Options.ReduceInputs && II)
     if (std::binary_search(II->UniqFeatureSet.begin(),
                            II->UniqFeatureSet.end(), Feature))
       FoundUniqFeaturesOfII++;
});

위에서 분석한 바에 따르면, Feature는 각 각의 counter가 갖는 특별한 값입니다. libfuzzer에서는 이 Feature 값을 인덱스로 활용해서 현재 Input의 Size를 저장해놓은 InputSizesPerFeature 배열을 통해 coverage 정보를 관리합니다. 매 counter마다의 Feature를 모두 모아 UniqFeatureSetTmp 벡터에 저장합니다. Input을 최대한 줄이는 옵션에 대한 추가적인 동작 또한 수행할 수 있습니다.

FuzzerCorpus.h / AddFeature()

GetFeature()를 이용하여 InputSizesPerFeature 배열로부터 Feature를 Idx로 하는 값을 가져옵니다. 만약 기존 값이 존재하지 않는다면, NumUpdatedFeatures를 증가시키며, 해당 위치에 현재 Input의 사이즈를 넣어줍니다. Input을 최대한 줄이는 옵션이 존재한다면, 사이즈를 비교하여 현재 Input의 사이즈가 더 작을 경우 현재의 사이즈를 넣어줍니다.

bool AddFeature(size_t Idx, uint32_t NewSize, bool Shrink) {
assert(NewSize);
Idx = Idx % kFeatureSetSize;
uint32_t OldSize = GetFeature(Idx);
if (OldSize == 0 || (Shrink && OldSize > NewSize)) {
  if (OldSize > 0) {
    size_t OldIdx = SmallestElementPerFeature[Idx];
    InputInfo &II = *Inputs[OldIdx];
    assert(II.NumFeatures > 0);
    II.NumFeatures--;
    if (II.NumFeatures == 0)
      DeleteInput(OldIdx);
  } else {
    NumAddedFeatures++;
  }
  NumUpdatedFeatures++;
  if (FeatureDebug)
    Printf("ADD FEATURE %zd sz %d\n", Idx, NewSize);
  SmallestElementPerFeature[Idx] = Inputs.size();
  InputSizesPerFeature[Idx] = NewSize;
  return true;
}
return false;
}

남은 부분을 살펴보겠습니다. FoundUniqFeatures의 경우 RunOne()을 호출할 때 인자가 False로 주어졌으므로 넘어가겠습니다. size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;가 중요한데, 만약 현재의 실행에서 새로운 coverage Feature가 발견되었다면, Corpus.NumFeatureUpdates() 값이 증가했을 것이므로 NumNewFeatures 값이 1 이상이 됩니다. TPC.UpdateObservedPCs()은 PC Table과 연관되어 있으므로 넘어가면, 이제 새로운 coverage를 발견한 Input을 Corpus에 추가합니다.

...
   
 if (FoundUniqFeatures)
   *FoundUniqFeatures = FoundUniqFeaturesOfII;
 PrintPulseAndReportSlowInput(Data, Size);
 size_t NumNewFeatures = Corpus.NumFeatureUpdates() - NumUpdatesBefore;
 if (NumNewFeatures) {
   TPC.UpdateObservedPCs();
   auto NewII = Corpus.AddToCorpus({Data, Data + Size}, NumNewFeatures,
                                   MayDeleteFile, TPC.ObservedFocusFunction(),
                                   UniqFeatureSetTmp, DFT, II);
   WriteFeatureSetToFile(Options.FeaturesDir, Sha1ToString(NewII->Sha1),
                         NewII->UniqFeatureSet);
   return true;
}
 if (II && FoundUniqFeaturesOfII &&
     II->DataFlowTraceForFocusFunction.empty() &&
     FoundUniqFeaturesOfII == II->UniqFeatureSet.size() &&
     II->U.size() > Size) {
   auto OldFeaturesFile = Sha1ToString(II->Sha1);
   Corpus.Replace(II, {Data, Data + Size});
   RenameFeatureSetFile(Options.FeaturesDir, OldFeaturesFile,
                        Sha1ToString(II->Sha1));
   return true;
}
 return false;
}

AddToCorpus()를 이용하여 현재 Input의 정보를 Corpus에 추가합니다. 또한, WriteFeatureSetToFile()을 호출하여 AddToCorpus()에서 생성한 SHA1 스트링을 이름으로 하는 Feature 파일을 디렉토리에 저장합니다. 그 외에 Input을 줄이는 옵션에 대한 동작 등이 존재합니다. 최종적으로 새로운 Coverage를 발견했다면 true를 리턴합니다.

FuzzerCorpus.h / AddToCorpus()

libFuzzer의 Corpus는 Input 벡터로 관리됩니다. 해당 벡터에 새로운 InputInfo를 생성한 뒤, 현재의 Input과 관련된 데이터로 초기화합니다.

InputInfo *AddToCorpus(const Unit &U, size_t NumFeatures, bool MayDeleteFile,
                     bool HasFocusFunction,
                     const Vector<uint32_t> &FeatureSet,
                     const DataFlowTrace &DFT, const InputInfo *BaseII) {
assert(!U.empty());
if (FeatureDebug)
  Printf("ADD_TO_CORPUS %zd NF %zd\n", Inputs.size(), NumFeatures);
Inputs.push_back(new InputInfo());
InputInfo &II = *Inputs.back();
II.U = U;
II.NumFeatures = NumFeatures;
II.MayDeleteFile = MayDeleteFile;
II.UniqFeatureSet = FeatureSet;
II.HasFocusFunction = HasFocusFunction;
std::sort(II.UniqFeatureSet.begin(), II.UniqFeatureSet.end());
ComputeSHA1(U.data(), U.size(), II.Sha1);
auto Sha1Str = Sha1ToString(II.Sha1);
Hashes.insert(Sha1Str);
if (HasFocusFunction)
  if (auto V = DFT.Get(Sha1Str))
    II.DataFlowTraceForFocusFunction = *V;
// This is a gross heuristic.
// Ideally, when we add an element to a corpus we need to know its DFT.
// But if we don't, we'll use the DFT of its base input.
if (II.DataFlowTraceForFocusFunction.empty() && BaseII)
  II.DataFlowTraceForFocusFunction = BaseII->DataFlowTraceForFocusFunction;
UpdateCorpusDistribution();
PrintCorpus();
// ValidateFeatureSet();
return &II;
}

LibFuzzer Patch

LibFuzzer를 분석하며 제가 느낀 아쉬운 점은 새로운 Input을 생성하는데에 무작위성에 많이 의지하고 있었다는 점입니다. Corpus로부터 인자를 생성하는데 밀접한 연관이 있는 두 가지 함수, ChooseUnitToMutate()MutationDispatcher::MutateImpl() 함수 모두 Rand를 이용하여 데이터 및 동작 방식을 선택합니다.

InputInfo &ChooseUnitToMutate(Random &Rand) {
   InputInfo &II = *Inputs[ChooseUnitIdxToMutate(Rand)];
   assert(!II.U.empty());
   return II;
}

size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
                                     size_t MaxSize,
                                     Vector<Mutator> &Mutators) {
 assert(MaxSize > 0);
 for (int Iter = 0; Iter < 100; Iter++) {
   auto M = Mutators[Rand(Mutators.size())];
   size_t NewSize = (this->*(M.Fn))(Data, Size, MaxSize);
   if (NewSize && NewSize <= MaxSize) {

ChooseUnitToMutate()의 경우 Input 벡터에 존재하는 Input 중 랜덤하게 선택하는 방식이고, MutationDispatcher::MutateImpl()의 경우 Mutation에 사용할 Mutator를 Mutators 벡터에 존재하는 Mutator 중 랜덤하게 선택하는 방식입니다.

위와 같은 방식은 만약 아주 좋은 Seed 데이터가 존재하더라도 확률에 의해 해당 Seed 데이터가 선택되지 않을 가능성이 존재하며, 퍼징에 효율적인 Mutation 방법이 존재하더라도 해당 방법이 선택되지 않을 가능성이 존재합니다.

또한, 저는 특정 Seed와 특정 Mutation 방법으로 새로운 Coverage를 발견하였다면, 동일한 Seed와 Mutation 방법으로 Input을 생성했을 때, 또 다른 Coverage를 찾을 가능성이 높다고 생각합니다. 특정 데이터 값에 대한 switch 문, if 문 등이 많이 쓰인다는 사실로 미루어 볼 때, 충분히 더 효율적일 것이라고 생각했습니다.

따라서 저는 새로운 Coverage가 발견되었을 때, 현재의 Seed(Mutate 하기위해 선택한 Input)와 Mutator를 기억하여, 다음 번 Seed 선택과 Mutator 선택에서 동일한 것을 이용할 수 있도록 패치하였습니다.

Input Vector의 순서를 정하여 우선순위를 놓는 방법과 Rand의 결과를 저장하여 새로운 Coverage가 발견되었을 때 이전과 동일한 Rand 값을 사용할 수 있도록 하는 방법, 두 가지를 떠올렸는데, 비교적 원본 코드에 Side Effect가 발생하지 않도록 하기 위해 후자를 선택하였습니다.

FuzzerLoop.cpp

다음과 같이 새로운 Coverage를 발견했는지 여부를 확인하기 위한 전역 변수 FindNewCovInput 벡터와 Mutator 벡터의 index를 저장할 두 개의 전역 변수를 선언합니다. FindNewCov에는 NewCov를 저장합니다.

bool FindNewCov = false;
size_t SaveInputIdx = 0;
size_t SaveMutatorIdx = 0;

void Fuzzer::MutateAndTestOne() {
  ...
                           /*DuringInitialCorpusExecution*/ false);
   if (NewCov) {
     ReportNewCoverage(&II, {CurrentUnitData, CurrentUnitData + Size});
     break;  // We will mutate this input more in the next rounds.
  }
   FindNewCov = NewCov;
  ...
}

FuzzerCorpus.h

기본적으로 SaveInputIdx = idx이 되도록 하였고, 이전 Input으로 새로운 Coverage를 발견했을 때는 이전에 사용했던 InputIdx를 다시 사용하도록 하였습니다.

  InputInfo &ChooseUnitToMutate(Random &Rand) {
   size_t idx = ChooseUnitIdxToMutate(Rand);
   if (FindNewCov){
     idx = SaveInputIdx;
  }
   
   InputInfo &II = *Inputs[idx];
   SaveInputIdx = idx;

FuzzerMutate.cpp

위와 마찬가지로 기본적으로 SaveMutatorIdx = idx가 되도록 하였고, 새로운 Coverage를 발견했을 때 이전에 사용했던 MutatorIdx를 사용할 수 있도록 했습니다.

size_t MutationDispatcher::MutateImpl(uint8_t *Data, size_t Size,
                                     size_t MaxSize,
                                     Vector<Mutator> &Mutators) {
 assert(MaxSize > 0);
 for (int Iter = 0; Iter < 100; Iter++) {
   size_t idx = Rand(Mutators.size());
   if (FindNewCov){
     idx = SaveMutatorIdx;
  }
   auto M = Mutators[idx];
   SaveMutatorIdx = idx;

ETC..

FuzzerDriver.cpp의 ParseSeedInuts()-> ParseSeedInputs()



반응형

'좀 열심히 쓴 글' 카테고리의 다른 글

Bypass SNI Filtering  (1) 2020.06.29
How to handle Sections in PE  (0) 2020.06.17
RDP Client fuzzer 개선 보고서  (0) 2020.06.14
OpenJPEG Code Coverage 코드 작성 및 알고리즘 설명  (0) 2020.06.14
Android 동작 구조  (0) 2020.06.08