Нужна помощь программистов с оптимизацией PAC-файла

antizapret.prostovpn.org
1

PAC-файл (Proxy Auto-Configuration) АнтиЗапрета не обновляется с 28 января, из-за слишком большого количества заблокированных доменов в Реестре запрещённых сайтов, которые не укладываются в лимит браузеров на основе Chrome.

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

Поэтому принимаются любые предложения, идеи, реализации в виде кода, которые помогут уменьшить размер файла.
Задача заключается в реализации алгоритма сжатия (упаковки) доменов и IP-адресов, который бы уменьшил размер файла до приемлемого (<950 КиБ), а также алгоритмов исключения нерабочих, разделегированных и припаркованных доменов из списка, «мусорных» зеркал сайтов.

Сейчас реализовано:

Что нужно учитывать:

  • PAC это Javascript, но с особым API/Runtime. В нём нельзя выполнять HTTP-запросы (вроде fetch/XMLHttpRequest), но можно резолвить DNS. В нём нет доступа до DOM/document, нет HTML.
  • Нет поддержки Unicode, содержимое парсится как однобитовая кодировка cp1252. Русскоязычные домены должны паковаться в punycode, бинарные данные — в base64/base85 сотоварищи.
  • Скрипт исполняется целиком при инициализации контекста JS (на каждый поток/процесс), в это время можно однократно выполнить какую-то затратную по CPU/RAM операцию. Затем на каждый сетевой запрос вызывается функция FindProxyForURL, которая возвращает результат необходимости проксирования.
  • Файл должен работать в очень старых браузерах, вроде Internet Explorer 9/10/11. Если установить ссылку на PAC-файл в старой версии Windows, все программы, использующие функции wininet для общения по сети, будут исполнять файл в системной версии IE. Если в файле используются слишком новые технологии, старые клиенты в случае ошибки начнут бесконтрольно запрашивать файл по сто раз в секунду.
  • В браузерах есть (неустановленное и разное) ограничение на количество потребляемой оперативной памяти PAC-файлом, поэтому алгоритмы инициализации и сжатия должны укладываться во вменяемые размеры heap. Самый ограниченный в этом плане — Firefox 52 на Windows XP 32 bit, с лимитом в 4 МБ.
  • Сжатие в идеале не должно требовать инициализации при запуске: лучше сжимать/преобразовывать запрашиваемый домен при каждом запросе, а не разжимать списки блокировок в память.

Более-менее детальную информацию о структуре и функциях PAC-файла можно найти на сайте http://findproxyforurl.com/, дополнительная информация:

Исходный код генератора: Bitbucket (branch fixmeplz)
Скачивание листов и резолвинг отключён, запускайте doall.sh и проверяйте размер result/proxy-host-ssl.pac.
Если хотите тестировать nxdomain-резолвер, запускайте только его: scripts/resolve-dns-nxdomain.py result/hostlist_zones.txt

3

Ой только не питухон

4

Пора уже отказаться о поддержки старого софта, раз это уже реально мешает развитию – XP, IE и всё такое.

5

Присылайте на клиент вместо полного списка простой bloom-фильтр - он супер дешевый. O(1) по процессору и O(1) по памяти. Минус - это вероятностный алгоритм, и есть шанс ложноположительных срабатываний (ложноотрицательных быть не может). Вероятность коллизий будет зависеть от числа записей и размера таблицы.

Я не знаю, сколько записей сейчас в списках РКН, но допустим 1 миллион. Тогда скажем при таблице размером 10 мегабайт вероятность ложного срабатывания будет 1 из 7 миллионов. То есть вам придется какие-то редкие незаблокированные домены через себя проксировать.

В интернете полно калькуляторов, чтобы рассчитать вероятности коллизий - Bloom filter calculator. Заведите туда ваши реальные параметры (сколько доменов в списке и сколько памяти готовы пожертвовать), и получите вероятность коллизии.

Если случайно попадется какой-то дорогой домен (ну не дай бог Ютуб будет ложноположительным), вы можете рядом с блум-фильтром ещё и черный список положить доменов, которые ни при каких условиях нельзя проксировать. И будете туда добавлять домены, если вдруг от какой-то коллизии больно будет. Но скорее всего вам никогда в жизни не придется туда ничего класть.

6

От этого можно избавиться, установив проверку user-agent на сервере.
Выдавать что-то вроде 404. Посмотреть какая реакция будет на разные кода.
От дятлов может спасти iptables/nftables limit /sec
Против гигантских дятлов что-то на подобии fail2ban

7

Вопрос как её впилить в плейнтекст-файл. Текущий размер pac-файла в районе мегабайта

8

@ValdikSS, сколько у тебя остаётся адресов после выкидывания ненужных? Для оценки того, сколько необходимо в таблицу Блума засунуть.

9

Ну это уже чисто технический вопрос. От кодировок типа base64 до встраивания png-файла и чтения попиксельно.

10

есть странный вопрос, а пробовали упаковать в формате privoxy ? что-то кажется, что PAC файлы это немного тупиковое

11

PAC-и я покопаю. может что придумается

12

Но при этом все еще надо как-то влезть в мегабайт. Base64 дает примерно +30% к размеру, вариант с png не звучит как реализуемый в принципе в рамках pac.

13

@p13dz, @goodrussian666 PAC-скрипт – это скрипт, написанный на JS, но с особым API/Runtime. В нём нельзя делать HTTP-запросы, по типу fetch, только DNS. В нём нет DOM/document и никакого HTML. Подробнее см. GitHub - anticensority/about-pac-scripts: What we know about PAC scripts и about-pac-scripts/pac-script-api-chrome-55.md at master · anticensority/about-pac-scripts · GitHub.

14

да, я в курсе, я имел в виду privoxy вместо pac

15

Некий вариант префиксного дерева?

16

Более эффективное использование всего диапазона значений символов, а не только разрешенных в DNS ?

17

Это не вариант, т.к. сломает часть сайтов. Чтобы проксировать случайные ложноположительные срабатывания, придётся на прокси-серверах разрешать всё.

Записей 1.7 млн, ограничение файла — 1 048 576 байт.

18 
$ wc -l hostlist_zones.txt
127293 hostlist_zones.txt

Но это с исключёнными доменами, начинающимися на цифру, и другими хаками.

19

А ограничение на 4 Mb в браузерах на основе chrome возможно обойти? Сделать больше по размеру или разделить их по частям.Выбирать ту часть которая необходимо в данное время для прокси

20

Как вы это представляете реализовывать технически?