Как определить вероятность, что имя домена случайно?

Question

[Василий Алексеенко]

Многие вирусы, запрашивают у DNS сервера адреса, генерируя их по своим алгоритмам.
В логах сервера можно видеть подобное этому:
www .8fa0816f.com
www .9849af14.com
www .c33fb23d.com
www .c9423e05.com
или
ascxdcnciz.net
aykjwdbhdx.ws
azsvhzicv.info
bbuiozzcnv.ws
bceuhtw.cc
beift.net

Как человек я делаю вывод, что компьютер, который делает такие запросы, скорее всего заражён.
Какой алгоритм посоветуете прочесть и реализовать, чтобы программно высчитать вероятность «вирусности» запрошенного домена?

Проверять все домены на существование? Но их могут создавать авторы вируса по такому же алгоритму, чтобы с них отдавать «приказы»/«нагрузку».

Рад любому совету и наставлению. Прошу не рекомендовать «просто поставить антивирус», так как он и так ставится на все компьютеры, но мое предприятие просто огромное по площади и по количеству компьютеров, короче «и на старуху бывает проруха».

Answer 1

[Ents]

1. Возьмите список известных доменов, и постройте шкалу вероятностей встречи последовательности 2 символов
2. Имея карту вероятностей 2-символьных последовательностей посчитайте средюю вероятность всех двухбуквенных последовательностей в домене
3. Сравните этот показатель с нормальными доменами, увидете кореляцию

Если хотите почитать теорию — смотрите в сторону энтропии последовательности символов. Ваши слова — те, у которых энтропия максимальна

Answer 2

[signalizator]

Дональд Эрвин Кнут описал критерии определения случайной последовательности, поищите.

Answer 3

[Vitali Borovik]

Думаю решения перебора по словарю будут не очень эффективным, так как занимают n времени.
Я бы сделал так:
Берем google search api, делаем запрос site:habrahabr.ru (Нам нужно кол-во результатов, если оно большое, сайт скорее всего настоящий).
Если не хотите гугл, можно самому считать страницы сайта, при условии что он настоящий.

Comments

[Vitali Borovik]

при условии что он существует.

[AR1ES]

А если не существует, то количество результатов будет равно 0:)

Answer 4

[TheEternal]

Простейшее решение — по словарю.
Можно с наворотами, вроде побуквенного поиска по словарю подстрок доменного имени от цифры до цифры.

Comments

[TheEternal]

Криво сформулировал.
Имел в виду:
Разбиваем доменное имя на подстроки от цифры до цифры.
Каждую подстроку начинаем искать по словарю(он отсортирован лексикографически для ускорения). Не факт, что в словаре есть точное слово, в этом случаем записываем процент от исходной подстроки, который нашелся.
Усредняем значение по всем подстрокам. Если «больше чем» — то ок.
Алгоритм высосан из пальца, но, имхо, как первый рубеж он пойдет — отсеет заведомо корректные сайты.

[Michael Danilov]

Слов 'google', 'yandex', 'habrahabr' нет в словаре, поэтому алгоритм будет считать их такими же вирусными.

[TheEternal]

Во чего нашел, первая ссылка в гугле :)
wwhois.ru/favorite_lists.html

Answer 5

[Николай Турнавиотов]

Если нужен конкретно антиспам решение — может проще купить уже готовое? cisco ironport, например…

Comments

[amarao]

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

[Николай Турнавиотов]

amarao А что, мир сошелся на одной циске?