Telegram на go: часть 1, парсим схему

в 20:30, , рубрики: fuzzing, Go, mtproto, telegram, Анализ и проектирование систем, тестирование

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

Разработка все еще в процессе (и полностью open source), но уже пройден увлекательный путь от полного непонимания протокола до относительно стабильного клиента. В серии статей я расскажу, с какими сложностями я столкнулся и как с ними боролся. Приёмы, которые я применил, могут быть полезны при разработке клиента для любого бинарного протокола со схемой.


Type Language

Начнем с Type Language или TL, схемы описания протокола. Не буду углубляться в описание формата, на хабре уже есть его разбор, расскажу про него лишь кратко. Он чем-то похож на gRPC и описывает схему взаимодействия между клиентом и сервером: структуру данных и набор методов.

Вот пример описания типа:

error#1fbadfee code:int32 message:string = Error;

Тут 1fbadfee это id типа, error его имя, code и message — поля, а Error это имя класса.

Аналогичным образом описываются методы, только вместо имени типа будет имя метода, а вместо класса — тип результата:

sendPM#3faceff text:string habrauser:string = Error;	

Это значит, что метод sendPM принимает аргументы text и habrauser, а возвращает Error, варианты (конструкторы) которого описаны ранее, например, error#1fbadfee.

Чтобы начать работать с протоколом, нужно как-то научиться парсить его схему. Есть два пути: использовать обобщенный парсер или писать ad-hoc, т.е. специализированный парсер для конкретного протокола. Для первого пути есть participle, на первый взгляд неплохой обобщенный парсер на go, через которого можно было бы описать грамматику. Я решил выбрать путь ad-hoc и этот выбор себя оправдал.

Тестовые данные

Нам придется тестировать наш парсер, подавая ему на вход данные и проверяя результат, а разнообразие тестовых данных позволит нам не беспокоиться во время рефакторинга и быть уверенным в том, что наш парсер стабильный. Первая сложность: написать парсер так, чтобы он не ломался от изменений, позволив нам быстрее итерироваться в его разработке.

Табличные тесты

Для небольшого набора данных вполне подойдёт их хранение прямо в тестах, рядом с ожидаемым результатом парсинга. Вот пример для парсинга Definition, определения для конкретного типа:

func TestDefinition(t *testing.T) {
	for _, tt := range []struct {
		Case       string
		Input      string
		String     string
		Definition Definition
	}{
		{
			Case:  "inputPhoneCall",
			Input: "inputPhoneCall#1e36fded id:long access_hash:long = InputPhoneCall",
			Definition: Definition{
				ID:   0x1e36fded,
				Name: "inputPhoneCall",
				Params: []Parameter{
					{
						Name: "id",
						Type: bareLong,
					},
					{
						Name: "access_hash",
						Type: bareLong,
					},
				},
				Type: Type{Name: "InputPhoneCall"},
			},
		},
    // ...
  } {
		t.Run(tt.Case, func(t *testing.T) {
			var d Definition
			if err := d.Parse(tt.Input); err != nil {
				t.Fatal(err)
			}
			require.Equal(t, tt.Definition, d)
		})
  } 
}  

Такие тесты можно написать для каждой сущности, начиная от Flag (определение опциональности поля, в котором указывается имя битового поля и смещения в нём), заканчивая полной схемой.

Проверять необходимо не только положительный, но и негативный случай, ведь невалидный вход должен вызывать ошибку и это тоже нужно закрепить в тестах. Делается это аналогично:

	t.Run("Error", func(t *testing.T) {
		for _, invalid := range []string{
			"=0",
			"0 :{.0?InputFi00=0",
		} {
			t.Run(invalid, func(t *testing.T) {
				var d Definition
				if err := d.Parse(invalid); err == nil {
					t.Error("should error")
				}
			})
		}
	})

Файлы в testdata

Объёмные входные данные уже проблематично хранить прямо в коде и удобнее вынести в отдельное место. Я использую поддиректорию _testdata: подчеркивание вначале нужно для того, чтобы отделить пакеты с кодом и просто данные, а тулинг go игнорирует директории с таким префиксом.

В этом тесте мы читаем Sample.tl из _testdata и пытаемся его распарсить:

func TestParseSample(t *testing.T) {
	data, err := ioutil.ReadFile(filepath.Join("_testdata", "Sample.tl"))
	if err != nil {
		t.Fatal(err)
	}
	schema, err := Parse(bytes.NewReader(data))
	if err != nil {
		t.Fatal(err)
	}
  // ...
}

Тесты в go запускаются в контексте директории их пакета, так что нужный путь получить довольно легко, но важно не забыть использовать filepath.Join для кросс-платформенности.

Эталонные (golden) файлы

Более распространённое название для них это "golden files". Эталоном в нашем случае является результат парсинга, записанный в файл. Такие файлы обновляются автоматически, если тесты запущены в специальном режиме (обычно это просто флаг -update). Они позволят нам не набирать вручную ожидаемый результат парсинга, а генерировать его из тестов. Я использовал goldie в качестве утилиты для работы с подобными файлами.

func TestParser(t *testing.T) {
	for _, v := range []string{
		"td_api.tl",
		"telegram_api.tl",
		"telegram_api_header.tl",
		"layer.tl",
	} {
		t.Run(v, func(t *testing.T) {
			data, err := ioutil.ReadFile(filepath.Join("_testdata", v))
			if err != nil {
				t.Fatal(err)
			}
			schema, err := Parse(bytes.NewReader(data))
			if err != nil {
				t.Fatal(err)
			}
			t.Run("JSON", func(t *testing.T) {
				g := goldie.New(t,
					goldie.WithFixtureDir(filepath.Join("_golden", "parser", "json")),
					goldie.WithDiffEngine(goldie.ColoredDiff),
					goldie.WithNameSuffix(".json"),
				)
				g.AssertJson(t, v, schema)
			})
		})
	}
}

Этот пример парсит все файлы из списка, сериализует результат в json и сравнивает с эталонным (как json). Если передан флаг -update, то код перед сравнением обновляет эталонный файл, сохраняя его в папку _golden.

Сериализуйте выходные данные в текстовый формат (например, json с идентацией) и храните их в системе контроля версий, тогда будет легко отслеживать в них изменения.

Decode-Encode-Decode

Если научиться не только парсить, а генерировать схему, то можно применить принцип decode-encode-decode, сравнивая результат генерации с входом на парсинг.

Для этого я каждой сущости имплементировал метод String() string:

// Annotation represents an annotation comment, like //@name value.
type Annotation struct {
	Name  string `json:"name"`
	Value string `json:"value"`
}

func (a Annotation) String() string {
	var b strings.Builder
	b.WriteString("//")
	b.WriteRune('@')
	b.WriteString(a.Name)
	b.WriteRune(' ')
	b.WriteString(a.Value)
	return b.String()
}

Оказалось, что удобнеее всего для такой цели использовать strings.Builder, вызывая метод String() для сущностей уровнем ниже.

Добавив результат генерации схемы в эталонные файлы, мы еще больше стабилизируем наш парсер, но самый интересный способ еще впереди.

Fuzzing

Для обеспечения еще большей стабильности нашего парсера я применил технику (ниндзя) фаззинга. Это когда на вход парсеру подаётся случайный набор данных, автоматически изменяемый так, чтобы покрыть как можно больше строк кода (coverage-guided fuzzing). Для фаззинга в go есть замечательный проект go-fuzz от Дмитрия Вьюкова. Это фаззер очень помог мне (и не только мне) во множестве проектов, и я применил его и для парсера. Примечательно, что Дмитрий Вьюков также является автором syzkaller, утилиты на go, предназначенной для фаззинга ядра Linux и нашедшей в нём уже сотни багов.

Для того, чтобы начать фаззинг, необходимо определить для него входную точку, функцию, которую фаззер будет вызывать в попытках разломать наш код.

Например, вот функция фаззинга для Definition:

// +build fuzz

package tl

import "fmt"

func FuzzDefinition(data []byte) int {
	var d Definition
	if err := d.Parse(string(data)); err != nil {
		return 0
	}

	var other Definition
	if err := other.Parse(d.String()); err != nil {
		fmt.Printf("input: %sn", string(data))
		fmt.Printf("parsed: %#vn", d)
		panic(err)
	}

	return 1
}

Она сначала парсит вход, потом генерирует схему и пытается распарсить полученный результат снова.

Decode-encode-decode-encode

We need to go deeper. Для фаззинга полной схемы я применил подход еще интересней:

  1. Парсинг входных данных

  2. Генерация схемы

  3. Парсинг данных из (2)

  4. Генерация схемы на основании (3)

  5. Сравнение (4) и (2)

В идеале межу (4) и (2) разницы не должно быть, т.к. мы сравниваем уже более-менее нормализованную схему без мусора. На практике фаззинг помог мне найти и исправить огромное количество багов, и мы его еще применим в других частях проекта.

Немного о go-fuzz

Фаззинг важен для защиты от Denial of Service атак, т.к. поможет найти потенциальные паники или даже OOM. Фаззинг довольно ресурсоёмкий процесс, поэтому у go-fuzz есть режим распределенной работы, где запускается один координатор и несколько воркеров к нему подключаются по сети, так что фаззить можно и на удалённом сервере.

Результатом фаззинга является corpus, набор входных данных, который был обнаружен фаззером (а также crashers, набор данных, вызывающих падение парсера, если таковые есть). Нужно исправлять crashers до тех пор, пока их останется ровно 0, а фаззер перестанет находить новые данные. Для того, чтобы помочь фаззеру, можно в corpus заранее добавить данных, тогда поиск будет выполняться быстрее.

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

Вместо заключения

Подходы к тестированию, которые я описал, довольно универсальны и могут быть применены для любого проекта, где есть какие-то входные и выходные данные. Они были сформированны за время работы над множеством протоколов (STUN, TURN, SDP, MTProto, ...) и должны помочь писать парсеры или сериализаторы без страха и с удовольствием.

Надеюсь, статья будет кому-то полезна. Если будет интересно, я дальше продолжу рассказывать про то, как создавался клиент (а возможно и сервер) Telegram на go:

  • Генерация кода на основании схемы

  • Парсинг документации (и добавление её в сгенерированный код)

  • Криптография

  • Тестирование сетевого взаимодействия (unit, e2e)

  • Тестирование работы с сайд-эффектами (время, таймауты, ГПСЧ)

  • CI, или настраиваем пайплайн так, чтобы кнопку Merge не было страшно нажимать

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

Автор: Александр Разумов

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js