Всем привет! Меня зовут Кирилл, я старший разработчик в группе «Полигоны и ограничения доставки» в Ozon. Cегодня я расскажу про фаззинг, встроенный в Go: что это такое, зачем он нужен в разработке программного обеспечения и как с его помощью найти баг в дикой природе open-source-коде (рассмотрим на примере).

Что такое фаззинг?

Фаззинг — это техника тестирования программного обеспечения, часто автоматическая или полуавтоматическая, заключающаяся в передаче приложению на вход неправильных, неожиданных или случайных данных.

Источник 

Если программа повела себя некорректно или упала, значит, мы нашли баг.

Чем фаззинг отличается от классического юнит-тестирования?

Когда речь идёт о сложном коде, с помощью стандартного юнит-тестирования физически невозможно покрыть все возможные варианты входных данных. Признаем, что программисты ленивы и чаще всего ограничивают юнит-тесты несколькими простыми тест-кейсами. Фаззинг же позволяет разнообразить юнит-тесты случайным вводом и таким образом покрыть больше вариантов входных данных.

Что можно фаззить?

Для тестирования фаззингом лучше всего подходит код, который принимает на вход сложно устроенные данные: разные энкодеры и декодеры, криптографию, сетевые протоколы, кодеки и т. д. В современном мире разработки программного обеспечения методы API часто «торчат наружу» и обрабатывают недоверенные данные, что делает фаззинг-тестирование особенно актуальным.

Какие баги можно найти фаззингом?

С помощью фаззинга можно найти любые баги, как и другими методами тестирования, но чаще всего обнаруживаются следующие:

1. Деление на 0.

2. Аллоцирование слишком большого объёма памяти (Out of memory).

3. Выход за границы массива.

4. Паники.

5. Ошибки сегментации.

6. Слишком большое потребление ресурсов памяти и процессора.

7. Слишком объёмные выходные данные.

8. Попадание программы в бесконечный цикл или в бесконечную рекурсию.

9. Состояние гонки.

10. Запись в закрытый канал.

Некоторые из перечисленных багов могут стать векторами для DoS-атаки на сервер, на котором развёрнуто приложение.

Ещё с помощью фаззинга можно сравнивать результаты работы сложной и быстрой, но предположительно менее надёжной реализации алгоритма с результатами медленной и надёжной.

Как и когда фаззинг появился в Go?

Конечно, фаззеры появились задолго до языка Go. Это, например, CrashMe, AFL, libFuzzer и другие. Что касается фаззеров, заточенных под Go, стоит упомянуть go-fuzz, увидевший свет в 2015 году. Но в этой статье я буду рассматривать фаззер, встроенный в стандартную библиотеку Go.

В Go используется coverage-guided фаззер, он является частью стандартной библиотеки начиная с версии 1.18. Стоит отметить, что Go — это один из первых распространённых языков, в которых есть встроенный фаззер.

В том, что представляет собой фаззер, мы более или менее разобрались. Теперь разберёмся, что означает термин coverage-guided. Если мы просто будем давать программе на вход случайные данные, то может пройти оооооочень много времени, прежде чем мы дойдём до каких-то глубоких частей кода. Coverage-guided фаззер работает умнее. Во время каждого запуска функции он определяет, какие строки кода были затронуты вызовом функции со сгенерированными данными. Если было зафиксировано попадание в какую-то новую ветку кода, то фаззер запоминает ввод и пытается «развить» его дальше. Ввод, который запоминается, называется corpus, а его итеративная мутация называется corpus progression.

Переходим к практике

Поищем на GitHub какой-нибудь проект, реализующий парные функции, которые после их последовательного вызова возвращают изначальный ввод. Например, Marshal → Unmarshal, Compress → Decompress, Encrypt → Decrypt и т. д. Выбор пал именно на парные функции, потому что для них довольно легко написать осмысленный фаззинг-тест, с помощью которого можно обнаружить падение в рантайме или несоответствие возвращаемого результата из этой парной связки её изначальному вводу. Такой тест называется Round Trip тестом. Так мы будем тестировать две функции одновременно.

Мне приходилось иметь дело с двумерными полигонами, которые хранились в формате WKT (well-known text). Это текстовый формат представления векторной геометрии и описания систем координат. На тот момент не существовало декодеров данного формата на Go, так что пришлось писать свой. Могу предположить, что даже если такие парсеры и появились, то они довольно сырые, что даёт нам почву для поиска багов фаззером.

В строке поиска GitHub вбиваем “WKT”, ставим язык Go и тыкаем на первый попавшийся результат.

Создадим тестовый проект, в котором будем фаззить этот пакет, и проинициализируем в нём Go-модули:

mkdir fuzzingExperiments
go mod init github.com/sosiska/fuzzingExperiments

Создадим файл main.go, в котором будем писать вспомогательные функции, и файл main_test.go, в котором будем писать наш фаззинг-тест:

touch main.go
touch main_test.go

В main.go напишем простой код, чтобы убедиться, что Marshal -> Unmarshal WKT действительно являются парными функциями. В качестве ввода возьмём значение из юнит-тестов этого пакета:

package main

import (
  "fmt"

  "github.com/paulmach/orb"
  "github.com/paulmach/orb/encoding/wkt"
)

func main() {
  input := "LINESTRING(1 2,0.5 1.5)"
  fmt.Printf("Initial input: %s\n", input)
  geom, err := Unmarshal(input)
  if err != nil {
     fmt.Printf("can't unmarshal: %v\n", err)
     return
  }
  output := Marshall(geom)
  fmt.Printf("Round-trip output: %s\nEquivalence: %v\n", output, input == output)
}

func Marshall(geom orb.Geometry) string {
  return wkt.MarshalString(geom)
}

func Unmarshal(s string) (orb.Geometry, error) {
  geom, err := wkt.Unmarshal(s)
  if err != nil {
     return nil, err
  }
  return geom, nil
}

Запускаем код:

go run main.go

В выводе видим, что функции действительно парные:

Initial input: LINESTRING(1 2,0.5 1.5)
Round-trip output: LINESTRING(1 2,0.5 1.5)
Equivalence: true

Итак, мы нашли то, что будем тестировать фаззингом. Теперь открываем файл main_test.go, созданный ранее, и пишем фаззинг-тест:

package main

import (
  "testing"
)

// тут начинается Fuzz test
func FuzzWKT(f *testing.F) {
// добавляем seeds в corpus
  f.Add("LINESTRING EMPTY")
  f.Add("LINESTRING(1 2,0.5 1.5)")

// тут начинается Fuzz target
  f.Fuzz(func(t *testing.T, input string) {
     geom, err := Unmarshal(input)
     if err != nil {
        t.Skip()
     }

     output := Marshall(geom)
     if input != output {
        t.Errorf("Before: %s, after: %s", input, output)
     }
  })
}

Рассмотрим этот код. Чтобы обозначить, что это фаззинг-тест, мы используем “Fuzz” в префиксе названия тестирующей функции. На вход этой функции аргументом передаётся testing.F (в отличие от юнит-тестов, которые принимают testing.T). Затем мы добавляем в corpus начальные значения ввода (seeds), от которых фаззер-тест будет отталкиваться (я просто взял их из юнит-тестов этого проекта). f.Add() принимает на вход значения следующих типов:

• string, []byte, rune, byte;

• int, int8, int16, int32, int64;

• uint, uint8, uint16, uint32, uint64;

• float32, float64;

• bool.

Добавление в corpus нескольких разных типов, например добавление строки f.Add("123") и числа f.Add(123), приведёт к панике:

mismatched types in corpus entry: [string], want [int]

На случай если функция, которую планируется тестировать, принимает на вход сразу несколько параметров, f.Add() также умеет принимать сразу несколько параметров. Например, для функции:

func SuperFunc(i int, s string, u uint) {
}

фаззинг-тест будет выглядеть так:

func FuzzSuperFunc(f *testing.F) {
  f.Add(123, "hello", 567)
  f.Fuzz(func(t *testing.T, i int, s string, u uint) {
     SuperFunc(i, s, u)
  })
}

Но в таком случае каждый вызов f.Add() должен принимать значения seeds в corpus в одном и том же порядке, иначе мы также получим панику.

Вернёмся к коду. После добавления в corpus значений далее по коду начинается Fuzz target, который и работает с этим corpus путём многократного запуска кода с разными входными данными. В нём мы так же, как и в main.go, пытаемся сначала выполнить Unmarshal WKT из corpus в структуру, а затем сгенерировать WKT из объекта и сравнить выходной текст с входным. Если они будут различаться, то это верный признак ошибки. Обратите внимание, что если мы получаем ошибку во время вызова Unmarshal, то считаем это нормальным, поскольку, вероятнее всего, это означает, что наш WKT-ввод некорректен. Будем пропускать такой тест с помощью вызова t.Skip().

Запустим тест через go test с добавлением флага --fuzz=Fuzz. По умолчанию тестирование будет продолжаться до первой найденной ошибки. Также есть возможность ограничить время фаззинга, используя флаг -fuzztime.

Используя значение 10s ограничим продолжительность тестирования десятью секундами:

go test --fuzz=Fuzz -fuzztime=10s

fuzz: elapsed: 0s, gathering baseline coverage: 0/47 completed
fuzz: elapsed: 0s, gathering baseline coverage: 47/47 completed, now fuzzing with 8 workers
fuzz: elapsed: 0s, execs: 2550 (49883/sec), new interesting: 1 (total: 48)
--- FAIL: FuzzWKT (0.05s)
	--- FAIL: FuzzWKT (0.00s)
    	testing.go:1356: panic: runtime error: index out of range [0] with length 0
        	goroutine 47 [running]:
        	runtime/debug.Stack()
            	/usr/lib/go/src/runtime/debug/stack.go:24 +0xdb
        	testing.tRunner.func1()
            	/usr/lib/go/src/testing/testing.go:1356 +0x1f2
        	panic({0x5f92c0, 0xc00001c4e0})
            	/usr/lib/go/src/runtime/panic.go:884 +0x212
        	github.com/paulmach/orb/encoding/wkt.trimSpaceBrackets({0x0, 0x0})
            	/home/kirill/go/pkg/mod/github.com/paulmach/orb@v0.7.1/encoding/wkt/unmarshal.go:125 +0x225
        	github.com/paulmach/orb/encoding/wkt.Unmarshal({0xc00001e7c0, 0xa})
            	/home/kirill/go/pkg/mod/github.com/paulmach/orb@v0.7.1/encoding/wkt/unmarshal.go:256 +0xb2e
        	github.com/sosiska/fuzzingExperiments.Unmarshal(...)
            	/home/kirill/go/src/github.com/sosiska/fuzzingExperiments/main.go:27
        	github.com/sosiska/fuzzingExperiments.FuzzWKT.func1(0xc000103860, {0xc00001e7c0, 0xa})
            	/home/kirill/go/src/github.com/sosiska/fuzzingExperiments/main_test.go:20 +0x125
        	reflect.Value.call({0x5d9320?, 0x616e78?, 0x13?}, {0x6081fa, 0x4}, {0xc00007ef60, 0x2, 0x2?})
            	/usr/lib/go/src/reflect/value.go:584 +0x8c5
        	reflect.Value.Call({0x5d9320?, 0x616e78?, 0x51b?}, {0xc00007ef60?, 0x709e10?, 0x72a600?})
            	/usr/lib/go/src/reflect/value.go:368 +0xbc
        	testing.(*F).Fuzz.func1.1(0x0?)
            	/usr/lib/go/src/testing/fuzz.go:337 +0x231
        	testing.tRunner(0xc000103860, 0xc0000ba6c0)
            	/usr/lib/go/src/testing/testing.go:1446 +0x10b
        	created by testing.(*F).Fuzz.func1
            	/usr/lib/go/src/testing/fuzz.go:324 +0x5b9
       	 
    
	Failing input written to testdata/fuzz/FuzzWKT/3b773553ddccf531f4c41ffd77ca73470b8885c61f724edf43908b87f2332e94
	To re-run:
	go test -run=FuzzWKT/3b773553ddccf531f4c41ffd77ca73470b8885c61f724edf43908b87f2332e94
FAIL
exit status 1
FAIL	github.com/sosiska/fuzzingExperiments   0.054

Давайте его рассмотрим. Мы видим несколько параметров:

• elapsed — время, прошедшее с запуска фаззера,

• execs — общее количество вводов, прошедших через тест,

• new interesting — общее количество «интересных» вводов, которые были добавлены к corpus во время фаззинга. Интересным считается такой ввод, который покрыл новую строку кода.

Затем фаззер наткнулся на ошибку, вызванную выходом за границы массива:

panic: runtime error: index out of range [0] with length 0

После того как произошла ошибка, фаззинг-тестирование останавливается и входящие параметры функции, приводящие к ошибке, записываются в папку с проектом по следующему пути: testdata\fuzz\TestName\inputID

Откроем этот файл и посмотрим, что там:

go test fuzz v1
string("LINESTRING")

Первая строка содержит информацию о фаззере. На второй строке указан ввод, который привёл к ошибке. Если в файле main.go присвоить переменной input это значение и запустить программу, то она также завершит выполнение паникой.

Теперь с этими данными можно открыть issue, что я и сделал.

Заключение

В рамках этой статьи мы не затрагиваем тему исправления ошибки выхода за границы массива, поэтому ограничимся заведением issue на GitHub. Однако если вы встретили такой баг в своём проекте, то его, конечно, лучше сразу исправить.

Фаззинг помогает в поиске багов и в Ozon. Например, один из сервисов моей группы работает с полигонами, только хранятся они не в формате WKT, а в WKB (well-known binary). В этом сервисе есть код, который умеет энкодить и декодить полигоны в таком формате. Я написал и запустил фаззинг-тест на метод Decode — и буквально через несколько секунд обнаружилась такая же ошибка, как в этой статье: на одном из вводов код вышел за границы массива. Ошибка была устранена  — и фаззер больше не нашёл вводов, приводящих к каким-либо сбоям.

Мы рассмотрели, что такое фаззинг в контексте Go, после чего с его помощью на реальном примере нашли баг. Теперь вы тоже умеете писать фаззинг-тесты. Это совсем не сложно, но в то же время такие тесты могут найти очень сложновоспроизводимые баги.