Experimental chill

Давно я не писал, поэтому чуть больше в одном посте

1. Я тут сегодня нашёл интересное применение алгоритма поиска максимального потока, о котором вы вряд ли слышали -- для тестов. В GUnit есть функция UnorderedElementsAre(container), которая сравнивает, что два множества совпадают. Проблема в том, что для общего случая элементы могут быть несравнимы или нехешируемы, тогда проверять на равенство становится сложнее, так как запрещены сортировки и хеш-мапы. Задача решается с помощью максимального паросочетания: между двумя множествами строится граф равенства и после этого находится максимальное паросочетание. В GUnit код находится здесь. UPD. Также в комментариях подсказали, что такая абстракция удобна для того, чтобы иметь разные проверки, скажем, что в множестве есть элементы строго больше, чем в другом (пример).

2. В Google обновился C++ Style Guide на C++20. Ничего не написано про модули, ranges и корутины, потому что всё ещё нет консенсуса. В целом хорошее изменение, вещи прогрессируют.

3. Тут рассказано, сколько фаззеру надо было фаззить, чтобы найти известный сверху баг в WebRTC: https://www.srlabs.de/blog-post/advanced-fuzzing-unmasks-elusive-vulnerabilities . TL;DR 20 независимых байт, что достаточно много для фаззеров. В похожем баге в ZSTD, который мы нашли в марте, надо было около 7-8 специфичных байт после того как фаззер зашёл в нужную строчку кода. Чтобы найти баг в ZSTD и WebRTC нужны более интересные техники. Например, в ZSTD хватило бы добавлять 2^n рандомных байт в конец, а в WebRTC сделать большой if/switch на табличку в 256 байт. Кажется нужен стажёр

4. Google Pixel 8 имеет поддержку Arm MTE. Это фича, которая помечает аллокации специальными тегами на уровне битов указателей и проверяет на уровне железа, читаете ли вы валидную память. Надеюсь, мы найдем очень много всякого разного со временем.

5. Я выложил свою презентацию с CppCon про сортировки https://danlark1.github.io/cppcon_sort_2023 . Запись будет где-то в январе :)

Wikipedia

Задача о максимальном потоке

В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока по транспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.

www.tgoop.com/experimentalchill/259

12.3K viewsedited  Nov 6, 2023 at 12:32

Давно я не писал, поэтому чуть больше в одном посте

1. Я тут сегодня нашёл интересное применение алгоритма поиска максимального потока, о котором вы вряд ли слышали -- для тестов. В GUnit есть функция UnorderedElementsAre(container), которая сравнивает, что два множества совпадают. Проблема в том, что для общего случая элементы могут быть несравнимы или нехешируемы, тогда проверять на равенство становится сложнее, так как запрещены сортировки и хеш-мапы. Задача решается с помощью максимального паросочетания: между двумя множествами строится граф равенства и после этого находится максимальное паросочетание. В GUnit код находится здесь. UPD. Также в комментариях подсказали, что такая абстракция удобна для того, чтобы иметь разные проверки, скажем, что в множестве есть элементы строго больше, чем в другом (пример).

2. В Google обновился C++ Style Guide на C++20. Ничего не написано про модули, ranges и корутины, потому что всё ещё нет консенсуса. В целом хорошее изменение, вещи прогрессируют.

3. Тут рассказано, сколько фаззеру надо было фаззить, чтобы найти известный сверху баг в WebRTC: https://www.srlabs.de/blog-post/advanced-fuzzing-unmasks-elusive-vulnerabilities . TL;DR 20 независимых байт, что достаточно много для фаззеров. В похожем баге в ZSTD, который мы нашли в марте, надо было около 7-8 специфичных байт после того как фаззер зашёл в нужную строчку кода. Чтобы найти баг в ZSTD и WebRTC нужны более интересные техники. Например, в ZSTD хватило бы добавлять 2^n рандомных байт в конец, а в WebRTC сделать большой if/switch на табличку в 256 байт. Кажется нужен стажёр

4. Google Pixel 8 имеет поддержку Arm MTE. Это фича, которая помечает аллокации специальными тегами на уровне битов указателей и проверяет на уровне железа, читаете ли вы валидную память. Надеюсь, мы найдем очень много всякого разного со временем.

5. Я выложил свою презентацию с CppCon про сортировки https://danlark1.github.io/cppcon_sort_2023 . Запись будет где-то в январе :)

BY Experimental chill