Компилятор не может здесь ничего "оптимизировать" (как минимум без flto), в случае с копированием вектора (без std::move), вы обязаны создать копию, а вектор-аргумент останется не-пустым (и естественно должен указывать на другую память, иначе при вызове деструкторов случился бы "double-free"), в случае с std::move вы перекидываете указатели на уже выделенную память, а вектор аргумент содержит nullptr-ы. Если например тестирующая обертка логгирует size у тестового вектора после вызова нашей функции - то и flto никак не поможет.
Я бы сказал это архетипичный пример мув-семантики, недоступный до её введения в стандарт. До С++11 приходилось делать так:
Работает полностью аналогично, и тут как раз срабатывает корректная оптимизация NRVO (обязательная с C++17), и кстати с таким подходом std::move будет только всё портить.
Строчка с nums.erase только отвлекает, она тут не причём. Главное что мы не просто используем входную память для своих вычислений, а то что мы не выделяем никакую другую.
Ну и если нам разрешают менять аргумент функции, значит и разрешают сделать его пустым, украв его память. И естественно что выкинув из решения аллокацию на полмегабайта оно станет быстрее.
Буквально первый комментарий на скриншоте про "putting kernel level anti-cheat". Ну и на сайте Denuvo честно признаются чем они (с позиции критики конкурентов) там занимаются:
(3) Anti-cheat 1, 2 and 3 access all files on your disk that are opened while the anti-cheat is running by using a file system minifilter, a formal operating system hook. This minifilter passes all opened files to the anti-cheat software, not just those that interact with the game.
Anti-cheat 3 uses Windows’ Early Launch AntiMalware (ELAM) security feature which allows the kernel-mode driver to start before all others. This behavior is often mistakenly referred to as a rootkit, which it is not because it does not attempt to hide from the user and is effortless to remove.
Никаких проблем подключиться к процессу и читать его память нет, `Cheat Engine/Artmoney` 100 лет в обед, и никаких "особенных" привилегий для их работы не нужно.
У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с 27,223 до 21,820 . Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы _mullo_epi32 в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).
Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.
подмешивается немного мусора
Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить man ssh_config; /Obf)
Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.
Но в таком случае происходит утечка данных не только о тайминге нажатий, но и о количестве клавиш, что соответствует длине пароля
Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.
В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).
в SSH автоматически включается Nagel's и передаваемые символы начинают группироваться и объединяться, что портит хакерам весь праздник
/* Informs that the current session is interactive. Sets IP flags for that. */
void
ssh_packet_set_interactive(struct ssh *ssh, int interactive, int qos_interactive, int qos_bulk)
{
...
set_nodelay(state->connection_in);
...
}
/* disable nagle on socket */
void
set_nodelay(int fd)
{
...
if (setsockopt(fd, IPPROTO_TCP, TCP_NODELAY, &opt, sizeof opt) == -1)
error("setsockopt TCP_NODELAY: %.100s", strerror(errno));
}
Статья про анализ серверного "пинга" со стороны собеседника в IM.
Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.
Пусть пользователь A, B живут в стране, где некие вредоносные агенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.
Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.
Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.
Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.
Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).
Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.
Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)
Определение местоположения пользователя популярных "защищенных" мессенджеров
Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.
P.S. Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).
Еще я сомнительным способом генерировал случайное целое, uniform_uint64() % (HI-LO) + LO В районе 10^18 там уже значительный перекос в пользу меньших чисел.
Было бы любопытно узнать, как график ведёт себя на бесконечности
Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где x=y, но так как их немного, погрешность должна быть небольшой).
Просто взял p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;
Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.
@cuda.jit
def cuda_run_core(A, oA, oB, B):
B0 = B // BASE
pos = cuda.grid(1)
if pos + 1 < A.size:
b_lo = A[pos]
b_hi = A[pos + 1]
for b in range(b_lo, b_hi):
if b % BASE == 0:
continue
rb = rev(b)
a0 = uint64(math.ceil(rb * 1.0 * B / b))
for a in range(a0, a0 + BASE):
if not (B0 <= a < B):
continue
ra = rev(a)
err = uint64(a * b - rb * B)
if err == ra:
oA[pos] = a
oB[pos] = b
if err > B:
break
Проверяет все до m=12 за минуту на видюшке. Посмотрим что будет с m=14 через пару часов.
Hidden text
@cuda.jit(device=True)
def cuda_rev(x):
r = uint64(0)
while x > 0:
r = r * BASE + x % BASE
x = x // BASE
return uint64(r)
def run_cuda(d):
# 10 -> 0.638
# 11 -> 6.601
# 12 -> 68.787
# 13 -> 775.907
num = 2**18
A = np.linspace(pow(BASE, d - 1), pow(BASE, d), num).astype(np.uint64)
oA, oB = np.zeros_like(A), np.zeros_like(A)
threadsperblock = 2**9
blockspergrid = (A.size - 1 + (threadsperblock - 1)) // threadsperblock
A, oA, oB = cuda.to_device(A), cuda.to_device(oA), cuda.to_device(oB)
cuda_run_core[blockspergrid, threadsperblock](A, oA, oB, uint64(pow(BASE, d)))
A, oA, oB = A.copy_to_host(), oA.copy_to_host(), oB.copy_to_host()
for x, y in zip(oA, oB):
if x:
print(x, '*', y, '=', rev(y), rev(x))
def main():
for d in range(8, 16):
t0 = time.perf_counter()
run_cuda(d)
t1 = time.perf_counter()
print(f'{d} -> {t1-t0:.3f}')
Компилятор не может здесь ничего "оптимизировать" (как минимум без flto), в случае с копированием вектора (без
std::move), вы обязаны создать копию, а вектор-аргумент останется не-пустым (и естественно должен указывать на другую память, иначе при вызове деструкторов случился бы "double-free"), в случае сstd::moveвы перекидываете указатели на уже выделенную память, а вектор аргумент содержитnullptr-ы. Если например тестирующая обертка логгирует size у тестового вектора после вызова нашей функции - то и flto никак не поможет.Я бы сказал это архетипичный пример мув-семантики, недоступный до её введения в стандарт. До С++11 приходилось делать так:
Работает полностью аналогично, и тут как раз срабатывает корректная оптимизация NRVO (обязательная с C++17), и кстати с таким подходом
std::moveбудет только всё портить.Строчка с
nums.eraseтолько отвлекает, она тут не причём. Главное что мы не просто используем входную память для своих вычислений, а то что мы не выделяем никакую другую.Ну и если нам разрешают менять аргумент функции, значит и разрешают сделать его пустым, украв его память. И естественно что выкинув из решения аллокацию на полмегабайта оно станет быстрее.
Вместо того что бы выделять новый вектор под ответ, можно отдать уже выделенную память, раз уж нам разрешили менять аргумент.
В ML выборку принято делить на Training, validation, and test как раз что бы избежать переобучения во время подбора модели/гиперпараметров, это база.
Буквально первый комментарий на скриншоте про "putting kernel level anti-cheat". Ну и на сайте Denuvo честно признаются чем они (с позиции критики конкурентов) там занимаются:
Никаких проблем подключиться к процессу и читать его память нет, `Cheat Engine/Artmoney` 100 лет в обед, и никаких "особенных" привилегий для их работы не нужно.
Школьное "подгоняем под ответ" вышло на новый нейросетевой уровень.
Надеюсь вы знаете что такое train validation test split, а то мне страшно за АЭС.
Поздравляю победителей!
У меня получилось сжать переведённую "Войну и Мир" обычным RLE вне зависимости от числа повторений, попробуйте Энтропийное кодирование для потока битовых флагов.
Вот код. Вроде бы и немного (21+18 строк), но он довольно таки ёмок на математику, легко допустить ошибку. Если будет несложно дополните статью, так она станет гораздо информативнее.
Максимально дубовая реализация монтгомери вместе с делением по Лемиру улучшила мой результат с
27,223до21,820. Даже обидно как-то, получается раньше я вообще не в ту сторону смотрел. Но теперь до первых мест рукой подать, скорее всего можно те же вызовы_mullo_epi32в два раза реже делать (у меня на 1 mulmod 3 simd умножения, из которых только два полноценное, и одно урезанное), или от бранча для переполнения вычитания как-то отказаться, его обработка съедает четверть всего времени. Теоретически можно оптимально распланировать умножения по битам степени, и вместо маскировки делать их только тогда когда нужно, это тоже может дать до трети всего времени (умножаем только на половину всех битов).Да, проверяю по 4 числа одновременно. Главное заранее отсекать большую часть работы (5/6) проверкой на делимость на маленькие делители, довольно красиво сделано, но видимо можно сделать лучше, я использовал для больших libdivide_u32_do_vec256, а для маленьких (2,3,5,7) сообразил трюк с _mm256_shuffle_epi8. Тоже в восторге от результатов первой тройки. Ах да, еще нужно чтение через mmap организовать, в справке от сайта есть пример.
О, я примерно тем же путём шел когда решал https://highload.fun/tasks/10
Правда у меня в итоге векторизованная где-то в 2 раза быстрее не векторизованной, но и другие трюки использовал. Обязательно поделитесь результатом.
Все так говорят (на один символ отправка 8 байт если между ними меньше ~20ms), пробежал по коду и не вижу ничего противоречащего этому. Тестить правда лень, если хотите оспорить — wireshark/tcpdump вам в помощь.
Действительно в прошлом году появился патч и опция в конфиге, мне интересно, а в вашем дистрибутиве есть эта опция? (проще всего проверить
man ssh_config; /Obf)Презентация про ssh, тут статья. Текст об этом на хабре, но я не рекомендую ни комментарии ни статью: там какая-то отсебятина про visual feedback.
Вместе с таймингом утекает и длина пароля, ответных пакетов со стороны сервера не нужно.
В комментариях тоже какая-то дичь, например: (проблема не в комментарии или в комментаторе, а в том что его никто не поправил, так и висит).
Статья про анализ серверного "пинга" со стороны собеседника в IM.
Напишу на тот случай если кто-то не понимает какую конкретно безопасность обеспечивает E2EE и для/от кого. Для любого мессенджера с моментальной доставкой сообщений и без серьёзного "замусоривания" траффика легко понять кто с кем общается используя глобальное наблюдение (без MitM) и элементарные корреляции.
Пусть пользователь A, B живут в стране, где некие
вредоносныеагенты Е установили специальное оборудование сохраняющее метаданные всего оконечного трафика на всех провайдерах связи. Пусть агенты E знают A, но не знают B, про B известно что он один из множества U.Теперь каждый раз когда A пишет сообщение B, он инициирует обмен сетевым трафиком с серверами напрямую (Telegram), через peer-to-peer сеть(Tor), либо даже с использованием туннеля с дополнительным шифрованием ( Wireguard или OpenVPN). Но во всех популярных любительских сценариях использования (за редким исключением вроде i2p) размеры пакетов меняются крайне предсказуемо, а то и не меняются вовсе. Теперь E, зная паттерны трафика нового сообщения (а в случае push уведомлений можно опираться и на ip-подсеть как на показатель пуша), запоминает текущее время.
Затем это сообщение должно прийти B, где ситуации повторится. Так как множество людей из U могут получить подобный трафик случайно, E может лишь ограничить размер множества U - даже для довольно таки большого окна доставки в минуты (типично для пуш-уведомлений) с каждым сообщением размер U будет сокращаться в разы, если не в десятки. Для однозначного установления B потребуется около 27 бит информации (
|U|~=1.4e8), что вполне себе достижимо при регулярном общении. Даже если утекать будут малые доли бита (т.е. агенты E очень не уверены в том что произошло общение), из того что нам их нужно собрать буквально десятки, при достаточном количестве сообщений легко вычислить весь граф общения.Эту картину не меняет даже вменяемый false-positive (пусть например фоном запущенный ютуб раз в 15 секунд даёт картину похожую на сообщение, тогда мы должны учесть шанс того что A ничего не отправлял). В таком случае мы не выкидываем кандидатов из U, а честно обновляем ожидания по Байесу. Если проделать подобное в итоге получатся что граф общения оказывается (ребро между вершинами если они общаются) равен попарной временной корреляции "интересного" трафика относительно U.
Подправив параметры можно узнать например на какие каналы в youtube вы подписаны не залезая в шифрованный трафик, достаточно посмотреть корреляцию жирного потока на сервера гугла с расписанием публикации новых видео, (если вы конечно открываете их сразу по уведомлению).
Да, это вычислительно сложная задача, но явно не сложнее подсчета условного PageRank-a для поискового индекса с MapReduce, естественно считать в лоб (O(|U|^2)) нельзя.
Слайды про утечку пользователя по паролю при наборе его используя SSH (не совсем в тему, но идея похожая)
Определение местоположения пользователя популярных "защищенных" мессенджеров
Тут исследователи не пользуются глобальным мониторингом траффика, смотрят только на раундтрипы оповещения о доставке.
P.S.
Задумался над тем что бы комментарий до статьи добить, но об подобном на хабре уже писали еще в 2011 (в контексте Tor, Tarzan и Morphmix).
Еще я сомнительным способом генерировал случайное целое,
uniform_uint64() % (HI-LO) + LOВ районе 10^18 там уже значительный перекос в пользу меньших чисел.Прогнал Монте-Карло на равномерных неупорядоченных парах, (это не точно учтёт пары где
x=y, но так как их немного, погрешность должна быть небольшой).Просто взял
p:=cnt_good/cnt_iters; estimate:=81*10^{d-2}*p/2;Скорость симуляции получилась около 5 миллиардов итераций в секунду, что не впечатляет. Пришлось немного попотеть что бы правильно работать с 36-значными числами.
Monte-Carlo
Относительная точность падает при уменьшении p, поэтому оценку для d=18 получилось посчитать с точностью
±0.3%Hidden text
Попробовал ваш алгоритм на видяшке, работает 4.5 секунды для
n=6.Заодно и осилил
n=7Лобовой подсчет без каких-либо алгоритмов на видяшке работает 4 секунды! (задача с парами). Если не лень ждать 16 часов сможете узнать ответ для n=7.
Hidden text
Ничего не нашлось, а пятнадцать нужно 16 часов ждать. Расширил пространство на несколько порядков, вдруг пригодится потомкам.
Другие основания, из не указанного выше
Проверяет все до
m=12за минуту на видюшке. Посмотрим что будет сm=14через пару часов.Hidden text