...

суббота, 15 марта 2014 г.

C++11 и 64-битные ошибки

CryEngine 3 SDK and PVS-Studio

Мы решили сделать небольшую паузу в тематике статического анализа кода. Ведь блог C++ читают и те, кто пока еще не использует эту технологию. А между тем в мире C++ происходят явления, которые оказывают влияния на такую «устоявщуюся» тему, как 64-битный мир. Речь идет о том как стандарт C++11 влияет и помогает (если есть чем) в разработке корректных 64-битных программ. Сегодняшняя статья как раз об этом.



64-битные компьютеры давно и успешно используются. Большинство приложений стали 64-битными. Это позволяет им использовать больший объем памяти, а также получить прирост производительности за счёт архитектурных возможностей 64-битных процессоров. Создание 64-битных программ на языке Си/Си++ требует от программиста внимательности. Существует масса причин, из-за которых код 32-битной программы отказывается корректно работать после перекомпиляции для 64-битной системы. Про это написано много статей. Но сейчас нам интересен другой вопрос. Давайте посмотрим, позволяет ли использование новых возможностей, появившихся в C++11, облегчить жизнь программистов, создающих 64-битные программы.

Мир 64-битных ошибок




Существует множество ловушек, в которые может попасть программист, создавая 64-битные приложения на языке Си/Си++. Про это написано большое количество статей, поэтому не будем повторяться. Тем, кто не знаком с нюансами разработки 64-битных программ или тем, кто хочет освежить свою память, можно порекомендовать следующие ресурсы: Время не стоит на месте, и вот уже программисты используют обновлённую версию языка C++, получившего названия C++11. На данный момент большинство нововведений, описанных в стандарте языка C++11, поддерживается современными компиляторами. Давайте посмотрим, могут ли эти нововведения как-то помочь программисту избежать 64-битных ошибок.

Статья будет построена следующим образом. Будет даваться краткое описание типичной 64-битной ошибки, и предлагаться способы, как её избежать, используя C++11. Сразу отметим, что далеко не всегда С++11 может хоть чем-то помочь. Защитить от ошибок может только аккуратное программирование. А новый стандарт лишь помогает в этом, но не решить все проблемы за программиста.


Магические числа




Речь идёт об использовании таких чисел, как 4, 32, 0x7FFFFFFF, 0xFFFFFFFF (подробнее). Плохо, если программист предположил, что размер указателя всегда равен 4 байтам и написал вот такой код:

int **array = (int **)malloc(n * 4);



Здесь стандарт C++11 нам помочь не может. Магические числа, это зло и единственный способ избежать ошибок — это стараться их не использовать.

Примечание. Да, malloc() это не C++, а старый добрый C. Намного лучше использовать оператор new или контейнер std::vector. Но сейчас это к делу не относится. Разговор про магические числа.


Впрочем, С++11 иногда помогает сократить число магических чисел. Некоторые магические числа в программе появляется из-за боязни (часто необоснованной), что компилятор плохо оптимизирует код. В этом случае, стоит обратить внимание на generalized constant expressions (сonstexpr).


Механизм constexpr гарантирует инициализацию выражений во время компиляции. При этом, можно объявить функции, которые гарантированно развернутся в константу на этапе компиляции. Пример:



constexpr int Formula(int a) {
constexpr int tmp = a * 2;
return tmp + 55;
}
int n = Formula(1);




Вызов функции Formula(1) превратится в число. Объяснение конечно слишком краткое. Подробнее про «constexpr» и другие нововведения можно прочитать, перейдя по ссылкам, приведённым в конце статьи.

Функции с переменным количеством аргументов




Речь идёт о неправильном использовании таких функций, как printf, scanf (подробнее). Пример:

size_t value = ....;
printf("%u", value);




Этот код корректно работает в 32-битной программе, но может распечатать некорректные значения, когда программа превратится в 64-битную.

Функции с переменным количеством аргументов — пережиток языка Си. Их недостаток в отсутствии контроля типов фактических аргументов. В Си++ уже давно пора отказаться от них. Есть масса других способов форматирования строк. Например, можно заменить printf на cout, а sprintf на boost::format или std::stringstream.


С языком C++11 жизнь стала ещё лучше. В C++11 появились шаблоны с переменным числом параметров (Variadic Templates). Это позволяет реализовывать вот такой безопасный вариант функции printf:



void printf(const char* s)
{
while (s && *s) {
if (*s=='%' && *++s!='%')
throw runtime_error("invalid format: missing arguments");
std::cout << *s++;
}
}
template<typename T, typename... Args>
void printf(const char* s, T value, Args... args)
{
while (s && *s) {
if (*s=='%' && *++s!='%') {
std::cout << value;
return printf(++s, args...);
}
std::cout << *s++;
}
}




Этот код просто «достает» первый аргумент, не являющийся форматной строкой, и затем вызывает себя рекурсивно. Когда таких аргументов больше не останется, будет вызвана первая (более простая) версия метода printf().

Тип Args… определяет так называемую «группу параметров» («parameter pack»). По сути, это последовательность пар тип/значение, из которых вы можете «доставать» аргументы, начиная с первого. При вызове функции printf() с одним аргументом, будет выбран первый метод (printf(const char*)). При вызове функции printf() с двумя или более аргументами, будет выбран второй метод (printf(const char*, T value, Args… args)), с первым параметром s, вторым – value, и оставшиеся параметры (если они есть) будут запакованы в группу параметров args, для последующего использования. При вызове:



printf(++s, args...);



Группа параметров args сдвигается на один, и следующий параметр может быть обработан в виде value. И так продолжается до тех пор, пока args не станет пустым (и будет вызвана первая версия метода printf()).

Некорректные операции сдвига




Числовой литерал 1 имеет тип int. Значит, его нельзя сдвигать более чем на 31 разряд (подробнее). Про это часто забывают, и в программах можно встретить вот такой код:

ptrdiff_t mask = 1 << bitNum;



Если, значение bitNum будем равно, скажем 40, то результат будет непредсказуем. Формально, это приведёт к undefined behavior (подробнее).

Может нам помочь C++11? К сожалению, ничем.


Рассинхронизация виртуальных функций




Пусть в базовом классе объявлена виртуальная функция:

int A(DWORD_PTR x);



А в классе наследнике есть функция:

int A(DWORD x);



В 32-битной программе типы DWORD_PTR и DWORD совпадают. Однако, в 64-битной программе, это уже два разных типа (подробнее). В результате, вызов функции A из базового класса будет приводить к различным результатам в 32-битной и 64-битной программе.

Бороться с подобными ошибками могут помочь новые ключевые слова, появившиеся в C++11.


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


Этот код не скомпилируется в 64-битном режиме и тем самым ошибка будет обезврежена:



struct X
{
virtual int A(DWORD_PTR) { return 1; }
};
struct Y : public X
{
int A(DWORD x) override { return 2; }
};




Смешанная арифметика




Это достаточно важная и обширная тема. Предлагаю познакомиться с соответствующим заделом «64-битных уроков»: Смешанная арифметика.

Совсем кратко:



  1. Программисты часто забывают, что результат перемножения и сложения двух переменных типа 'int', тоже имеет тип 'int'. При этом может возникнуть переполнение. И не важно, как потом используется результат умножения и сложения.

  2. Опасно смешивать 32-битные и 64-битные типы данных. Последствия: неправильные условия, вечные циклы.




Рассмотрим несколько простых примеров про переполнение



char *p = new char[1024*1024*1024*5];



Программист пытается выделить массив 5 гигабайт памяти, но выделит гораздо меньше. Дело в том, что выражение «1024*1024*1024*5» имеет тип int. В результате произойдёт переполнение, и выражение будет равно 1073741824 (1 гигабайт). Затем, при передачи в оператор 'new', число 1073741824 будет расширено до типа size_t, но это не имеет значения (уже поздно).

Если проблема не понятна, то вот другой аналогичный пример:



unsigned a = 1024, b = 1024, c = 1024, d = 5;
size_t n = a * b * c * d;




Результат выражения помещается в переменную типа 'size_t'. Она способна хранить значения больше, чем UINT_MAX. Но при перемножении переменных типа 'unsigned' возникает переполнение и результат будет некорректен.

Почему мы называем всё это 64-битными ошибками? Дело в том, что в 32-битной программе невозможно выделить массив размером более 2 гигабайт. А значит, переполнения просто не возникают. Проявляют себя такие ошибки только в 64-битных программах, когда они начинают работать с большими объёмами памяти.


Теперь пара примеров про сравнение



size_t Count = BigValue;
for (unsigned Index = 0; Index < Count; ++Index)
{ ... }




Это пример вечного цикла, если Count > UINT_MAX. Предположим, что на 32-битных системах этот код выполнял менее повторения, менее чем UINT_MAX раз. Но 64-битный вариант программы может обрабатывать больше данных, и ему может потребоваться большее количество итераций. Поскольку значения переменной Index лежат в диапазоне [0..UINT_MAX], то условие «Index

Ещё один пример:



string str = .....;
unsigned n = str.find("ABC");
if (n != string::npos)




Этот код некорректен. Функция find() возвращает значение типа string::size_type. Всё будет отлично работать в 32-битной системе. Но давайте посмотрим, что произойдет в 64-битной программе.

В 64-битной программе string::size_type и unsigned перестают совпадать. Если подстрока не находится, функция find() возвращает значение string::npos, которое равно 0xFFFFFFFFFFFFFFFFui64. Это значение урезается до величины 0xFFFFFFFFu и помещается в 32-битную переменную. Вычисляется выражение: 0xFFFFFFFFu != 0xFFFFFFFFFFFFFFFFui64. Получается, что условие (n != string::npos) всегда истинно!


Может здесь как-то помочь C++11?




Ответ — и да, и нет.

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


Если объявить «auto a = .....», то её тип будет вычислен автоматически. Очень важно не запутаться и не написать вот такой неправильный код: «auto n = 1024*1024*1024*5;».


Поговорим о ключевом слове auto. Рассмотрим следующий пример:



auto x = 7;



В данном случае тип переменной 'x' будет 'int', потому что именно такой тип имеет ее инициализатор. В общем случае мы можем написать:

auto x = expression;



И тип переменной 'x' будет равен типу значения, полученному в результате вычисления выражения.

Ключевое слово 'auto' для вывода типа переменной из ее инициализатора, наиболее полезно, когда точный тип выражения не известен, либо сложен в написании. Рассмотрим пример:



template<class T> void printall(const vector<T>& v)
{
for (auto p = v.begin(); p!=v.end(); ++p)
cout << *p << "\n";
}




В С++98, вам бы пришлось писать гораздо более длинный код:

template<class T> void printall(const vector<T>& v)
{
for (typename vector<T>::const_iterator p = v.begin();
p!=v.end(); ++p)
cout << *p << "\n";
}




Очень полезное нововведение в языке C++11.

Вернемся к нашей проблеме. Выражение «1024*1024*1024*5» имеет тип 'int'. Так что для сейчас нам 'auto' никак не поможет.


Не поможет нам 'auto' и в случае цикла:



size_t Count = BigValue;
for (auto Index = 0; Index < Count; ++Index)




Стало лучше? Нет. Число 0 имеет тип 'int'. Значит переменная Index теперь будет иметь тип не 'unsigned', а «int'. Пожалуй, стало даже хуже.

Так есть ли хоть какой-то нам прок от 'auto'? Да, есть. Например, здесь:



string str = .....;
auto n = str.find("ABC");
if (n != string::npos)




Переменная 'n' будет иметь тип string::size_type. Теперь всё хорошо.

Вот наконец нам и пригодилось новое ключевое слово 'auto'. Однако, будьте аккуратны. Нужно понимать, что и зачем вы делаете. Не надо надеяться побороть все ошибки, связанные со смешанной арифметикой, используя повсеместно 'auto'. Это всего лишь один из инструментов, а не панацея.


Кстати, есть ещё один способ защититься от обрезания типа в рассмотренном ранее примере:



unsigned n = str.find("ABC");



Можно использовать новый формат инициализации переменных, который предотвращает сужение (narrowing) типов. Проблема заключается в том, что языки С и С++ неявно обрезают некоторые типы:

int x = 7.3; // Ой!
void f(int);
f(7.3); // Ой!




Однако списки инициализации С++11 не позволяют сужение (narrowing) типов:

int x0 {7.3}; //compilation error
int x1 = {7.3}; //compilation error
double d = 7;
int x2{d}; //compilation error




Для нас сейчас более интересны вот эти пример:

size_t A = 1;
unsigned X = A;
unsigned Y(A);
unsigned Q = { A }; //compilation error
unsigned W { A }; //compilation error




Представим, что код написан так:

unsigned n = { str.find("ABC") };
или так
unsigned n{str.find("ABC")};




Этот код будет компилироваться в 32-битном режиме и перестанет компилироваться в 64-битном режиме.

Опять это не панацея от всех ошибок. Просто ещё один способ писать более надёжные программы.


Адресная арифметика




Проблема во многом схожа с тем, что мы рассмотрели в разделе „Смешанная арифметика“. Отличие лишь в том, что переполнение возникает при работе с указателями (подробнее).

Рассмотрим пример:



float Region::GetCell(int x, int y, int z) const {
return array[x + y * Width + z * Width * Height];
}




Данный код взят из реальной программы математического моделирования, в которой важным ресурсом является объем оперативной памяти. В программах данного класса для экономии памяти часто используют одномерные массивы, осуществляя работу с ними, как с трехмерными массивами. Для этого существуют функции, аналогичные GetCell, обеспечивающие доступ к необходимым элементам. Но приведенный код будет корректно работать только с массивами, содержащими менее INT_MAX элементов. Причина — использование 32-битных типов int для вычисления индекса элемента.

Может здесь как-то помочь C++11? Нет.


Изменение типа массива и упаковка указателей.




Иногда в программах необходимо (или просто удобно) представлять элементы массива в виде элементов другого типа (подробнее). Ещё бывает удобно хранить указатели в переменных целочисленного типа (подробнее).

Ошибки возникают из-за неправильных явных приведений типов. С новым стандартом С++11 здесь никакой взаимосвязи нет. Явные приведения типов всегда делались на свой собственный страх и риск.


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


Сериализация и обмен данными




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

Стандарт C++11 немного облегчил жизнь, введя типы фиксированного размера. Раньше программисты объявляли такие типы самостоятельно или использовали типы, объявленные в одной из системной библиотек.


Теперь есть следующие типы фиксированного размера:



  • int8_t

  • int16_t

  • int32_t

  • int64_t

  • uint8_t

  • uint16_t

  • uint32_t

  • uint64_t




Кроме размера изменяются выравнивание данных в памяти (data alignment). Это тоже может предоставить определённые сложности (подробнее).

Касательно этой темы, стоит упомянуть появление в С++11 нового ключевого слова 'alignment'. Теперь можно написать вот такой код:



// массив символов, выровнен для хранения типов double
alignas(double) unsigned char c[1024];
// выравнивание по 16 байтной границе
alignas(16) char[100];




Существует также оператор 'alignof', который возвращает выравнивание для указанного аргумента (аргумент должен быть типом). Пример:

constexpr int n = alignof(int);



Перегруженные функции




При переносе 32-битных программ на 64-битную платформу может наблюдаться изменение логики ее работы, связанное с использованием перегруженных функций. Если функция перекрыта для 32-битных и 64-битных значений, то обращение к ней с аргументом, например, типа size_t будет транслироваться в различные вызовы на различных системах (подробнее).

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


Проверки размеров типа




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

Часто это делают неправильным способом. Например, так:



assert(sizeof(unsigned) < sizeof(size_t));
assert(sizeof(short) == 2);




Плохой способ. Во-первых, программа всё равно компилируется. Во-вторых, эти проверки проявят себя только в отладочной версии.

Гораздо лучше останавливать компиляцию, если необходимые условия не выполняются. Для этого существует множество решений. Например, можно использовать макрос _STATIC_ASSERT, который доступен разработчикам, использующим Visual Studio. Пример использования:



_STATIC_ASSERT(sizeof(int) == sizeof(long));



C++11 стандартизировал способ, как остановить компиляцию, если что-то пошло не так. В язык введены утверждения времени компиляции (static assertions).

Статические утверждения (утверждения времени компиляции) содержат константное выражение и строковый литерал:



static_assert(expression, string);



Компилятор вычисляет выражение, и если результат вычисления равен false (т.е. утверждение нарушено), выводит строку в качестве сообщения об ошибке. Примеры:

static_assert(sizeof(long)>=8,
"64-bit code generation required for this library.");

struct S { X m1; Y m2; };
static_assert(sizeof(S)==sizeof(X)+sizeof(Y),
"unexpected padding in S");




Заключение




Написание кода с максимальным использованием новых конструкций языка C++11 вовсе не гарантирует отсутствия 64-битных ошибок. Однако, язык представляет несколько новых возможностей, которые позволят сделать код более коротким и надёжным.

Дополнительные ресурсы




В статье не делалась попытка ознакомить читателя как с можно большим количеством нововведений в языке C++11. Для первого знакомства с новым стандартам можно порекомендовать следующие ресурсы:

  1. Bjarne Stroustrup. C++11 — the new ISO C++ standard (Замечательный перевод).

  2. Wikipedia. C++11.

  3. Scott Meyers. An Effective C++11/14 Sampler.


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.


Простая стратегия игры 2048

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

Студентам физфака тоже было весело, поэтому мы придумали простую эвристическую выигрышную (по крайней мере, нам удалось набрать 2048 в 9 из 10 раз) стратегию этой игры.


Занумеруем идущие подряд столбцы (можно и строки, но в дальнейшем я буду говорить о столбцах) от 1 до 4 (последовательно слева направо или справа налево). Основополагающим принципом стратегии является расположение чисел, при котором мы полностью заполняем 1ый столбец наибольшими доступными числами. При этом, во 2ом столбце числа в среднем меньше, чем в 1ом, а в 3ем меньше, чем во 2ом. Причем, только на последних этапах игры в 3ем столбце возможно появление чисел среднего номинала (где-то до 32).


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


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


Для наглядности прилагается картинка и видео из начала, середины и конца игры:


image


Полную версию можно посмотреть здесь.


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.


[Перевод] Голландия одобрила оператор-независимые SIM-карты



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



На прошлой неделе регуляторы связи в Нидерландах открыли возможность любым компаниям – будь то Apple, Audi или небольшие местные электросети, выпускать собственные SIM-карты, не привязанные к какому-либо оператору. Пока что на этот шаг пошел только Амстердам, но если другие страны осмелятся последовать его примеру, это может в корне изменить не только мир интернет-вещей, но и повлиять на привычные нам принципы использования мобильной связи.



Несколько лет назад в своей статье, европейский экономист и политический аналитик Рудольф Ван Дер Берг представил вариант, как такая схема может работать для компании Apple, если она захочет меньше зависеть от операторов, предоставляя связь напрямую покупателям iPhone. Apple могла бы предлагать клиентам собственные SIM-карты, а затем удаленно регистрировать их у различных операторов по мере того, как абоненты используют услуги. Яблочный гигант сможет покупать оптом голосовой и интернет-трафик у сотен разных операторов по всему миру, чтобы затем, в любой момент выбирать для каждого своего клиента наиболее подходящую сеть, в зависимости от его потребностей.

К примеру, если владелец iPhone временно покинет свою страну, чтобы провести отпуск во Франции, он не будет разорен жестокими роуминговыми расценками. Вместо этого, Apple просто перепропишет SIM-карту своего клиента на одну из мобильных сетей Франции. И тогда, вместо того, чтобы попасть в эту сеть в качестве гостевого роумера, клиент окажется в своей новой домашней сети. И так может быть по всему миру. Проявят ли Apple или Samsung какой-то интерес к тому, чтобы стать оператором для своих покупателей нам еще предстоит увидеть – еще в 2010 году ресурс gigaom.com сообщал о том, что Apple вела разработки своего решения Soft SIM. И, хотя из этого, похоже ничего пока не вышло, результат может быть весьма полезен в плане построения взаимодействия M2M (machine-to-machine)-систем по всему миру.


Возьмем другой пример: автопроизводителя, такого, как GM, который встраивает LTE-устройства в каждую свою машину. В США GM жестко привязан только к одному оператору. И не важно, что вы купили свой смартфон у Verizon или T-Mobile; если вы хотите подключить свой шевроле к LTE, у вас только один вариант: AT&T. По мнению Ван Дер Берга, С оператор-независимой SIM-картой, производитель автомобиля смог бы подключать его к любому мобильному оператору, с которым у вас уже есть привычные вам отношения. А так же – менять его каждый раз, когда вы решите сами сменить обслуживающую сеть. Или, к примеру, можно было бы использовать сразу несколько операторов, переключая вас на того, который имеет в нужном для вас месте лучшее покрытие или скорость передачи данных.


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


Конечно, сейчас мы очень далеки от того, чтобы подобные оператор-независимые сервисы стали реальностью. Свои правила смягчили Нидерланды, а GSM-ассоциация одобрила и поддержала этот концепт, однако, перепрограммируемые SIM все еще вне закона в большинстве стран по всему миру. США и Германия делают некоторые шаги в этом направлении, но им еще предстоит решить массу технических сложностей. Будем надеяться, что успех Нидерландов станет примером для подражания и для других прогрессивных стран.


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.


[Перевод] Вирус Chameleon распространяется по WiFi сетям как простуда среди людей



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

Исследователи продемонстрировали WiFi вирус, который получил название Chameleon , способный распространяться в сети так, как «простуда» распространяется между людьми, ученые сделали возможным заменить прошивку уязвимой точки доступа (Access Point, AP) инфицированной версией.

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

Chameleon, является серьезной угрозой для ИТ-безопасности, ведь сценарий атаки использует WiFi сети и уязвимость заключается как раз в том, что нападение не может быть обнаружено любым из существующих защитных механизмамов, в том числе антивирусами и системами обнаружения вторжений (Wireless intrusion detection system, WIDS).



Таким образом, эта атака считается самой современной и трудно обнаружимой, так как для WIDS критериями обнаружения заражения AP обычно являются изменения в учетных данных, или трафике.





Распространение вируса происходит следующим образом:

1. Формируется список уязвимых точек доступа в текущем местоположении.

2. Выполняется взлом шифрования безопасности на AP.

3. Выполняется обход интерфейса администрирования AP.

4. Сохраняется резервная копия конфигурации AP.

5. Подменяется прошивка на уязвимых точках доступа, новой прошивкой, инфицированной вирусом.

6. Восстанавливаются настройки системы.

7. Вирус размножается на подключенные компьютеры (и опять к пункту 1).

Чтобы проанализировать поведение вируса был проведен лабораторный эксперимент, для которого были смоделированы сценарии поведения вируса в двух городах — Белфаст (Северной Ирландии) и Лондон (Англия). Их выбор не случаен, так как эти города, представляют большую (Лондон) и среднюю (Белфаст) инфраструктуры городской беспроводной сети, основанные на плотности точек доступа.


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



В Белфасте содержится около 14 553 точек доступа, из которых 22% являются открытыми, 61% защищены WPA/WPA 2 шифрованием и 14% — WEP.

В Лондоне содержится около 96 433 точек доступа, из которых 24% являются открытыми, 48% имеют WPA/WPA 2 шифрование и 19% — WEP.





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

Ниже представлена динамика распространения вируса в зависимости от радиуса между точками доступа:



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


Этот эксперимент доказывает что плотность связи между точками доступа является более важным фактором распространения вируса, нежели уязвимость.





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

"WiFi соединения становятся все большей мишенью для хакеров из-за хорошо известных уязвимостей, которые затрудняют обнаружение и защиту от вирусов", говорит Маршалл, один из авторов Chameleon.







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

В исследовании представлены также способы обнаружения вируса Chameleon с помощью мониторинга Wi-Fi пакетов. Такой подход является довольно специфичным, но в любом случае он может быть адаптирован для обнаружения вредоносных программ в дальнейшем.


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


Ссылка на исследования — jis.eurasipjournals.com


От переводчика: данные исследования показались довольно смутными. Вроде бы и исследователи делают уклон на практику, но в то же время оригинальная статья дает только теорию, да и то в ограниченном количестве. Боятся послужить руководством для злоумышленников? Так ведь производителям точек доступа тоже бороться нужно. Плюс ко всему эксперимент довольно сферический. Мне кажется, открывая новую уязвимость такого масштаба, неплохо бы понаблюдать за ней в «живой среде».


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.


Popcorn Time закрылся из-за «угрозы юридических преследований и закулисных махинаций»


сегодня в 13:59


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



Приложение Popcorn Time представляет собой очень простой и удобный в использовании торрент-клиент и каталог фильмов, доступных на различных торрент-трекерах, с субтитрами и метаданными. После выбора фильма встроенный торрент-трекер начинал скачивание с поддержкой функции просмотра во время скачивания. Таки образом, при наличии быстрого интернет-соединения практически любой фильм можно посмотреть, пару раз щёлкнув мышкой в каталоге. Бета версия Popcorn Time была доступна для Linux, Windows 7+ и MacOS X 10.7+. Исходники приложения были опубликованы на Гитхабе. Репозиторий Popcorn Time всё ещё доступен. За несколько дней своего существования он набрал больше 4000 звёзд и почти полторы тысячи форков.



Свежий взгляд

на бег


протестируй кроссовки

нового поколения




Стань

первоиспытателем!


Скачай Windows Server 2012 R2

и выиграй почетную футболку!


Скачать




Автоматизированное

продвижение сайтов




  • 50% экономии на ссылках

  • Запуск проекта за 10 минут

  • Вывод и удержание в ТОП 10



Подробнее




Новый 3G-планшет Login 2



2790 р.*


*Условия акции на www.megafon.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.


«Лицеприятное-2», или что стоит за «Лицами»


МегаФон уже писал обзорный пост о том, как работает инсталляция «Лица Олимпиады» в Сочи.

Однако видимая глазу часть — от силы 20% всей инфраструктуры проекта.

Хотелось бы рассказать немного о том, кто и что стоит за «Лицами».

Приготовьтесь, под катом много букв и некоторое количество картинок.



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

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


«Вот эти ребята»:



  • Асиф Хан, самое известное лицо в проекте, придумал идею инсталляции и спроектировал павильон.

  • Маркетинговое агентство AXIS, во-первых, выступило посредником между Асифом и компанией МегаФон, а во-вторых, взяло на себя всю реализацию проекта на местах: как в Сочи, так и в 29 других российских городах.

  • Швейцарские разработчики iart реализовали всю часть проекта, связанную с 3d — инсталляцию в Сочи и будки для сканирования.

  • Digital-эксперты из Deluxe Interactive продумали логику «поддерживающей» части проекта и спроектировали её элементы: планшетный софт для промо-персонала, API для всех участников проекта, а также обеспечили модерацию 3d-моделей и приём/трансляцию видео.

  • Специалисты из MegaLabs обеспечили часть серверных мощностей проекта, SMS-гейт, и выделенный интернет-канал «Сочи → Москва».

  • Обитатели Москва-Сити AdWatch отвечали за сайт faces2014.megafon.ru и конкурсную механику на нём.

  • А питерцы 2Nova обеспечивали в Сочи работу плазменных экранов, где можно было посмотреть расписание ближайших показов.





Но начнём по порядку.

Одним прекрасным днём «в нашу дверь постучали».

Агентству Deluxe Interactive, где я работаю, МегаФон предложил поучаствовать в проекте, размах которого охватывал три десятка российских городов и огромный павильон в Олимпийском Парке Сочи.


Сроки были непростыми: на 26 ноября уже была назначена пресс-конференция, где проект должен работать в полную силу, ведь сканироваться придут олимпийские чемпионы!

А еще к этому моменту стоило протестировать систему на надежность и обучить промо-персонал. Так что в действительности времени было даже меньше.

Но это лишь делало проект интереснее!

Конечно, мы согласились.


Началась кропотливая и, вместе с тем, оперативная работа.

Первым делом нужно было общее понимание проекта. Ребята из AXIS создали огромный spreadsheet с зонами ответственности, а мы набросали простенькую, но в меру наглядную схему в Visio:



Хронологически проект был разделен на два этапа:



  • Первый начинался 26 ноября в Москве. 8 будок с 3d-сканерами начинали своё турне по городам и весям. Олимпийский павильон в это время еще только строился, а пользовательские данные собирались и накапливались, но отображались только на сайте.

  • Второй этап стартовал 7 февраля в Сочи, за несколько часов до церемонии открытия Олимпийских Игр. К этому моменту работать должно было всё, включая видео-трансляцию на сайте.


Первый этап состоял из сбора 3d-моделей пользователей и их персональных данных. Механика была примерно следующей:



  1. Абонент приходит в салон компании МегаФон, где персонал предлагает ему поучаствовать в акции.

  2. Ему выдается карточка участника с QR-кодом.

  3. Промо-персонал считывает QR-код планшетным приложением и в нём же вводит пользовательские данные.

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

  5. В будке пользователь показывает QR-код, который линкуется с только что созданным профилем; и сканируется.

  6. Софт в будке генерирует 3d-модель и отправляет её модераторам на проверку корректности.















QR-коды


Очевидно, QR-код нужен не только для взаимодействия планшета и будки. В нём сразу зашита ссылка на персональную страницу пользователя на сайте http://ift.tt/K03Y7S

Поскольку не стоило давать случайному пользователю возможность получить список всех участников акции простым перебором IDшников, и в то же время хотелось, чтобы ссылка для просмотра не требовала авторизации, — было решено перед ID зашивать 6 символов «соли»: http://ift.tt/1iMFQWl

По прикидкам МегаФона, за весь период в акции должно было поучаствовать около 70,000 человек, но памятуя из институтского сопромата, что всему на свете не помешал бы тройной запас прочности, мы решили сгенерировать в три раза больше.


К сожалению, типография, печатавшая карточки, отказалась работать с PNG-форматом, в котором генерирует коды большинство программных пакетов. IrfanView на обычном рабочем ноутбуке справился с конвертацией двух с лишним сотен тысяч файлов в отдельные PDFки заданного формата за несколько часов.





Так как всемирным партнером Олимпийских игр является Samsung, было решено снабдить промо-персонал планшетами именно этой компании. Из двух доступных на тот момент больших планшетов: Galaxy Tab 3 8.0 и Galaxy Note 8.0, был в итоге выбран первый, не требующий стилуса вариант.

Все планшеты были зарегистрированы на один и тот же e-mail для удобства отслеживания местонахождения в процессе «гастролей» акции по России.

Ни один планшет не был привязан к конкретному городу, а различать их всё же было нужно. Поэтому, благодаря программистам-анимешникам, планшеты во внутреннем реестре были названы именами шестнадцати японских школьниц, от Asuka до Yuki :)


Участвовать в первом этапе проекта могли только абоненты МегаФона, поэтому нужно было отслеживать это.


Ничтоже сумняшеся мы думали, что проверка ограничится банальным списком префиксов в формате «926» — окей, «916» — не окей. Реальность оказалась к программистам куда более жестокой.

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

Во-вторых, файл с разбивкой этих префиксов еще и не высечен на скрижалях, а имеет свойство время от времени обновляться.


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


За первый этап статистика по отсканировавшимся абонентам в городах России выглядела примерно так (Москву из списка специально убрали, чтобы не портить наглядность картины — там отсканировалось более четверти пользователей):



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

Как в плане объема работ, так и в его необратимом влиянии на сознание :)

При нарушении участниками правил сканирования, 3d-модели иногда принимали странные, причудливые и откровенно непонятные формы:



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


Работу с модераторами разделили на две части:



  • Ежедневно пополнявшиеся guidelines от программистов 3d-части проекта.

  • База знаний на стороне самих модераторов — на основе прошлого опыта.




Второй этап в чём-то проще, а в чём-то сложнее первого.

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

  • «Город» сканирования для Сочи заменился на «Страну», гражданином которой был сканирующийся. А иностранцев было много.

  • Помимо русского добавился английский интерфейс. Причём не только для планшетного приложения. Если на планшете при заполнении пользовательских данных использовался русский язык, то и экран будки 3d-сканера приветствовал посетителя по-русски.

  • Для тех, кто сканировался в российских городах и не мог посетить Олимпиаду лично, на сайте появилась 24х7 видеотрансляция

  • А в личные кабинеты каждого, кто успешно прошёл модерацию и был показан на фасаде, подгружалось персональное видео, где было показано именно его лицо: http://ift.tt/1iMFQWl

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






Кстати говоря, за 14-е февраля было показано аж 280 таких пар.








Видео


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

На удивление, с «железной» точки зрения и то и другое решается одной платой за $500.


Технически процесс устроен следующим образом:



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

  • Провода с обеих камер идут на пульт, где специалист определяет, какое из изображений пускать в «суммарный» поток в данный конкретный момент.

  • В свою очередь, от пульта идёт SDI-провод к серверу с вышеуказанной платой Black Magic Design — H.264 Pro Recorder.

  • На этом сервере происходит конвертация потока из 1080p:50fps в 720p с битрейтом 2000kbps и разделение: один поток идёт на ретранслятор для дальнейшего показа на сайте; второй кусками по 120 мегабайт* (примерно 6,5 — 7 минут) накапливается для дальнейшей нарезки/склейки.

  • Ограничение длительности кусков было введено для ускорения нарезки и публикации персонализированных видеороликов.





Я уже упоминал, что иностранцев было много. Вот как разделились среди них первые места по численности (доля от общего числа отсканированных, не являющихся гражданами РФ):

  1. США — 16%

  2. Канада — 11%

  3. Украина — 8%

  4. Япония — 6%

  5. Белоруссия — 5%

  6. Германия — 3,5%

  7. Великобритания — 3,4%

  8. Республика Корея — 2,8%

  9. Нидерланды — 2,6%

  10. Швейцария — 2,5%




Одними из первых на фасаде павильона появились лица волонтёров из разных стран:


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

Даже из Свазиленда, Ангильи и Гернси (да-да, это всё реально существующие государства) отсканировавшихся людей было больше!


В целом через 3d-сканеры прошли представители 91 страны, что на 3 больше числа стран-участниц самой Олимпиады.


Акция близится к завершению. Сегодня — последняя возможность отсканироваться в Москве, завтра — в Санкт-Петербурге и Сочи. И в заключительные дни Паралимпиады ваше лицо будет точно так же показано на фасаде Павильона в Олимпийском Парке, и на сайте http://ift.tt/K03Y7S


P.S. Ещё немного занятной статистики напоследок:



  • За первый и половину второго (только Олимпиада, т.к. Паралимпиада еще только предстоит) этапа проекта было отправлено несколько сотен тысяч SMS-сообщений. В основном это

    • Сообщения об успешной регистрации (логин, пароль)

    • Сообщение об успешной/неудачной модерации

    • Сообщение с примерным временем показа (в случае успешной модерации)

    • Сообщение с точным временем показа (за 15 минут [freeze window] до него)

    • Сообщение о том, что в личном кабинете появилось персонализированное видео (когда оно там появилось)




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

  • Количество отсканированных пользователей на данный момент — более 140 тысяч лиц за время Олимпийских и Паралимпийских игр.

  • Продолжительность показа пользовательского лица на фасаде отличалась в зависимости от длины очереди, и варьировалось от 15 до 60 секунд. Среднее по всем пользователям время — 44 секунды.

  • Среднее время модерации на втором этапе составило 6 минут 14 секунд. Таким образом, среднее время от сканирования пользователя в Сочи до показа его лица на фасаде — 21 минута 14 секунд (модерация + freeze window).




P.P.S. Готовы ответить на любые, самые каверзные, технические вопросы.

Задавайте!

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.


OpenCV участвует в Google Summer of Code 2014

Ура! Организаторы Google Summer of Code приняли проект OpenCV для участия в Google Summer of Code 2014! С 10 марта начался приём заявок от студентов-участников. Давайте разберёмся, что это такое – GSoC, что за проект OpenCV и при чём здесь Itseez. А для начала – мотивирующее видео с результатами прошлого лета.





Начнём с OpenCV. OpenCV – это открытая библиотека алгоритмов компьютерного зрения, активно развивающаяся силами сообщества и множеством больших и маленьких IT-компаний. Будучи открытым проектом, OpenCV заинтересована в расширении сообщества пользователей и разработчиков, и инициатива Google Summer of Code – один из инструментов её развития.

Google Summer of Code – это программа компании Google, предлагающая студентам и аспирантам всего мира поучаствовать в развитии какого-либо открытого проекта и получать за это стипендию. Традиционное время проведения проекта – летние каникулы, когда большинство студентов свободны от занятий и могут посвятить своё свободное время понравившемуся проекту. Список проектов на лето, как понятно из названия, утверждает компания Google. Проект OpenCV в четвёртый раз прошёл отбор и открыл двери для участия.


С проектом OpenCV и инициативой Google разобрались, при чём же здесь Itseez? Как известно, разработку библиотеки OpenCV начала компания Intel. Через некоторое время, как это часто бывает с непрофильными проектами, корпорация утратила интерес к проекту, сделала его открытым и отдала на развитие сообществу. Часть инженеров Intel, работавших над библиотекой и несогласных с таким решением, создали собственную компанию и продолжили разработку. С тех самых пор Itseez развивает и поддерживает полюбившийся многим инструмент разработки и прототипирования приложений компьютерного зрения. Подробнее историю компании можно прочитать в этой хабрастатье.


Но вернёмся к Google Summer of Code. Основная группа разработчиков проекта, а также значительная часть менторов OpenCV находится в России, а если точнее в Нижнем Новгороде. Это даёт хорошую возможность русским студентам и аспирантам поучаствовать в GSoC 2014, даже если вы не очень уверены в своих знаниях английского языка. Кроме того, если у вас есть хорошая идея и вы готовы стать ментором, ещё не поздно подключится к программе.


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


Фотоэффекты



image

High Dynamic Resolution (HDR) Imaging – технология повышения динамического диапазона яркости изображений. Современная фотографическая техника имеет достаточно малый динамический диапазон яркости. Алгоритмы построения HDR изображений и последующей корректировки тона призваны скомпенсировать недостатки аппаратуры. По результатам летней школы GSoC 2013 в библиотеку была добавлена реализация нескольких таких алгоритмов. Предстоящим летом планируется продолжить развитие алгоритмов вычислительной фотографии и реализовать появившиеся за год новые алгоритмы HDR, балансировки цветов, tilt-shift и даже автоматической генерации комиксов.


Детектирование и распознавание объектов



image

Во время прошлогодней летней школы в библиотеку был добавлен робастный алгоритм поиска текстов на изображениях, который может пригодится при реализации OCR или любых других задач поиска и распознавания знаков и указателей. В этом году тема детектирования текстов не попала в перечень заявленных задач, зато есть ряд других алгоритмов детектирования: Softcascade детектор и детектор пешеходов, предложенный командой Piotr Dollár.


3D




С каждым годом задачи обработки данных с сенсоров глубины и RGBD-сенсоров набирают оборот. Способствует тому более глубокое проникновение в нашу жизнь недорогих камер глубины. Недавно такой модуль добрался и до смартфонов. В OpenCV уже есть некоторые наработки в этой области, в том числе и реализованный прошлым летом модуль визуализации Viz. Этому модулю, кстати, будет посвящена отдельная статья на хабре. В новом сезоне в библиотеку предлагается добавить ряд базовых алгоритмов обработки трёхмерных облаков точек и расширить возможности 3D визуализации.


Байндинги



В летнюю сессию 2013 года удалось реализовать полноценные обёртки OpenCV для Matlab и, потенциально, его свободного аналога GNU Octave, которые очень популярны в академических кругах. В этом году мы предлагаем поработать над расширением байндингов к популярным языкам программирования, в частности, поддержкой CUDA- и OpenCL-оптимизаций в Python.

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


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.


Голосования и информационная безопасность

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

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

Другими словами, выборы будем рассматривать как игру с определёнными правилами и ролями. Будем рассматривать также некоторую систему (программно-аппаратно-организационный комплекс) для проведения этой игры и продумаем защиту от читеров.

Замечу, что статья не про политику. Желающим обсудить что-нибудь политическое в контексте этой статьи настоятельно рекомендую заниматься этим не в комментариях, а где-нибудь ещё.

Принципы






  1. Баланс целей



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

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


  2. Фальсифицируемость (проверяемость)



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


  3. Презумпция «виновности»



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


  4. Прозрачность, открытость и гласность



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


  5. «Мыслить как преступник»



    Этот принцип означает, что при проектировании, изменении и использовании системы необходимо постоянно задавать себе вопросы: «А что здесь может пойти не так?», «Могу ли я изменить результаты голосования так, чтобы никто не узнал о моём вмешательстве?», «Есть ли у меня (или у кого-нибудь) возможность добавить или удалить кандидата без формальной процедуры?», «Могу ли я сорвать выборы просто сорвав пару бумажек со штампом ОПЕЧАТАНО?» и т.п.


  6. Непрерывное устранение уязвимостей



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

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




Все эти принципы тесно связаны друг с другом. Отказ от одного делает бессмысленными остальные.

Роли






  1. Организаторы



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

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


  2. Номинируемые



    Это те, кто может стать кандидатом. Например, для конкурса кинофильмов это все фильмы, вышедшие в этом году, а для выборов мейнтейнера open-source проекта — это все активные разработчики.


  3. Номинирующие



    Те, кто имеет право выдвигать Кандидатов. Это могут быть некоторые представители жюри, сами Номинируемые (если это люди) или автомат.


  4. Кандидаты (соискатели)



    Соответственно, те, кто получил номинацию. Из них будут выбирать одного или нескольких. В некоторых случаях, не публикуется (иногда до определения результатов, а иногда и вовсе) информация о том, кем именно являются Кандидаты: доступны только сведения о достижениях, количестве blame строк кода, доходах, характеристиках, параметрах (зачеркнуть лишнее).


  5. Имеющие право голоса



    Право голоса могут иметь все жители планеты страны или города. В множество пользователей с этой ролью могут быть включены или не включены Организаторы, Номинирующие, Кандидаты. В какой-нибудь высоконагруженной компьютерной системе при выборе мастер-сервера правом голоса обладать могут все компьютеры кластера.


  6. Избиратели



    Избиратели — это пользователи системы с правом голоса, которые решили этим правом воспользоваться. Речь идёт не о самом факте волеизъявления, а о принципиальном согласии стать Избирателем, то есть изучить профили Кандидатов и, если среди них будет достойный, отдать свой голос (или голоса). Часто факт принципиального согласия никак не фиксируется и не требуется, то есть все Избиратели = все Имеющие право голоса.

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


  7. Проголосовавшие



    Это Избиратели, которые отдали свой голос. Как правило, после этого они больше не могут проголосовать в текущем голосовании. Исключением, например, является голосование на Евровидении и тому подобные средства относительно честного отъёма денег у населения.


  8. Наблюдатели



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




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

Цели






  1. Выборы должны состояться



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


  2. У Номинирующих должно сформироваться намерение выдвинуть кандидатов



    Организаторы должны:


    • оповестить всех Номинирующих о предстоящих выборах;

    • объяснить Номинирующим их права;

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

    • обеспечить Номинирующим возможность независимого объективного суждения без давления из вне.





  3. У Имеющих на это право должно сформироваться намерение проголосовать



    Организаторы должны:


    • оповестить всех Имеющих право голоса о предстоящих выборах;

    • объяснить потенциальным Избирателям их права;

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





  4. Каждый желающий избиратель должен проголосовать



    Иными словами, намерение проголосовать должно «превратиться» в учтённый голос. (И ничто другое в голос «превратиться» не должно!) Это касается действительно всех Избирателей, даже если они в космосе, не могут ходить, не могут видеть или болеют.


  5. Должна быть обеспечена тайна голосования



    Эта цель есть не всегда, а иногда она присутствует лишь частично. Например, в технических системах она означает лишь требование независимости решений Избирателей-автоматов. А в случае голосования в парламентах, соответствие (избиратель-голос) может держаться в тайне не вечность, а, скажем, несколько лет.

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


  6. Голоса должны быть правильно посчитаны



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


  7. Должны быть оглашены правильные результаты



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


  8. Затраты на организацию выборов должны уложиться в бюджет



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




Этапы






  1. Анализ ситуации и актуализация системы



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


  2. Предварительная агитация



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


  3. Регистрация



    Сначала регистрируются сами Организаторы, потом Номинирующие и Избиратели, затем Номинируемые.


  4. Номинация



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


  5. Объявление Кандидатов



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


  6. Агитация



    Это наиболее трудно формализуемый этап (и потому наиболее часто и успешно атакуемый).

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

    Но чаще всего этого недостаточно для объективных суждений и честного голосования. В таком случае организаторы всё же пытаются формализовать процесс агитации: проще всего для этого вести контроль ресурсов, используемых Кандидатами или их представителями для агитации. Такими ресурсами могут быть деньги, эфирное время в СМИ, количество полос в газетах, время аренды рекламных мест на улицах и др. Изначально ресурсы могут принадлежать кому угодно: Организаторам, Избирателям, Кандидатам, их представителям. Представителями кандидатов могут быть даже те, кто не имеет какой-либо роли в системе. Распределение ресурсов не обязательно должно быть равномерным — какой-то кандидат может получить больше, а какой-то меньше, если Организаторы посчитают (и смогут доказать), что такое распределение сделает агитацию более честной. Главное, чтобы всё это было отражено в итоговом отчёте.


  7. Сбор голосов



    Самый картинный этап любого голосования. Классификация сбора голосов может быть проведена по двум критериям:


    • Очный и заочный



      В случае очного голосования избиратель отдаёт голос, находясь на определённой территории для голосования. В противовес этому существует заочное голосование, в том числе через интернет и по почте.


    • С доказательством и без



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

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




    В конкретном голосовании может применяться один или несколько способов сбора голосов. Также могут применяться экстренные меры типа досрочного голосования. Естественно, соответствующие статистические данные должны быть включены в отчёт.


  8. Подсчёт голосов



    Подсчёт голосов может происходить вручную, после сбора голосов и/или автоматически, в том числе во время сбора. Как отмечено выше, в общем случае машинам нельзя доверять. С другой стороны, ручной подсчёт всегда дороже, и люди чаще ошибаются. Так что хороший компромисс на этом этапе крайне важен. Приведу пример такого компромисса.(Насколько мне известно, лучшего способа подсчёта голосов на крупных выборах до сих пор не придумали.) Голоса считаются дважды. В первый раз — автоматически, во время сбора голосов. После сбора на всех, уже перемешанных, бюллетенях ставят случайные номера. При втором, снова автоматическом, подсчёте создаётся таблица (номер, голоса). Понятно, что результаты обоих подсчётов должны совпасть. Но помимо этого, можно проверить любое количество (например, репрезентативную выборку) бюллетеней вручную на соответствие записи в таблице.


  9. Анализ



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


  10. Объявление результатов



    Итоговый отчёт публикуется, голосование считается завершённым.


  11. Улучшение системы



    За время проведения голосования, особенно за время этапа анализа, могло накопиться много подтверждённых уязвимостей. На этом этапе, который постепенно переходит в этап 1, Организаторы меняют систему для защиты от соответствующих атак. Какие-то временные решения могу становиться постоянными, какие-то отвергаться в пользу более общих и т.д.




Человеческий фактор




Люди — не машины. Мы не всегда поступаем логично, пропускаем важный текст мелким шрифтом, боимся, на наши суждения легко повлиять. Если Избиратели, Организаторы или Наблюдатели — люди, то при организации выборов нужно минимизировать человеческий фактор.


  1. Юзабилити



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


  2. Давление



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


  3. Пропаганда



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


  4. Восприятие данных



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


  5. Лень



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




Цели атакующего




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


  1. Срыв самих выборов



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


  2. Исключение или неправомерное добавление Кандидатов



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


  3. Создание препятствий при формировании намерения проголосовать



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


  4. Создание препятствий при голосовании



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

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




  5. Публикация отметок избирателей



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

    Интересный пример — запись последовательности, в которой отдавались голоса (кандидат1, кандидат2, кандидат1). Зная дополнительно в каком порядке люди голосовали (избиратель1, избиратель2, избиратель3), злоумышленник может «проконтролировать волеизъявление» (избиратель1-кандидат1, избиратель2-кандидат2, избиратель3-кандидат1).




  6. Подтасовка при подсчёте



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


  7. Оглашение неверных результатов от имени организаторов



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


  8. Манипуляции с целью неоптимального использования бюджета



    Пример — атака-отвлечение, используется в сочетании с другими атаками. Злоумышленник имитирует или открыто заявляет о потенциальной угрозе безопасности, требующей ресурсоёмкой проверки. Цель состоит в том, чтобы ресурсов Организаторов не хватило на проверку защиты от действительно реализованных атак.




Классификация атак






  1. Изнутри и снаружи



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


  2. Локальные и глобальные



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


  3. Обратимые и необратимые



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


  4. Анонимные и «авторские»



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


  5. Обнаружимые и необнаружимые



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


  6. Дешёвые и дорогие



    Любая атака требует каких-то ресурсов. Дешёвая атака требует существенно меньше ресурсов для реализации, чем то, что злоумышленник может получить от подделки результатов в своих интересах. Дорогая атака, соответственно, требует больше ресурсов, чем злоумышленник может при помощи неё заработать.




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

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


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.


Анимированные графики в R (и немного про бифуркацию, хаос и аттракторы)

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



install.packages("animation")
library(animation)




Стоит отметить, что animation в процессе обработки изображений использует пакет программ ImageMagick, так что его желательно установить заранее. Под Windows работоспособность этого решения я не проверял.

Для создания анимированного графика нам, в общем-то, понадобится всего одна функция такого вида:

saveGIF({
# Какой-то код, генерирующий последовательность графиков
}, movie.name=..., interval=..., ani.width=..., ani.height=...)


Так получилось, что в то время я проходил весьма познавательный курс Introduction to Dynamical Systems and Chaos, и мне было интересно, как от относительно простых математических объектов переходят к весьма причудливым изображениям. Взять хотя бы логистическое отображение такого вида:





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

logistic.map <- function(r, x0, n, m){
x <- rep(x0, n)
for(i in 1:(n-1)) {
x[i+1] <- r * x[i] * (1 - x[i])
}
return(x[(n-m):n])
}




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

Скрытый текст


nrows <- 6
r.len <- 1500;
# Points of interest on the plot
R <- matrix(c(
seq(2.4, 4, length.out=r.len),
seq(3.442420, 3.639398, length.out=r.len),
seq(3.562297, 3.572910, length.out=r.len),
seq(3.569792, 3.570244, length.out=r.len),
seq(3.570005, 3.571369, length.out=r.len),
seq(3.631992, 3.633301, length.out=r.len)
), nrow=nrows, byrow=T)
X <- matrix(c(
0, 1,
0.8567335, 0.9140401,
0.8887529, 0.8936790,
0.8920580, 0.8925577,
0.8911242, 0.8927333,
0.9066966, 0.9083943
), nrow=nrows, byrow=T)

x0 <- 0.5
n <- 200
m <- 170
saveGIF({
for (i in 1:nrows){
r <- R[i,]
x <- as.vector(sapply(r, logistic.map, x0, n, m))
r <- sort(rep(r, (m+1)))
del_idx <- unlist(sapply(1:length(x), function(j) if (x[j] < X[i, 1] | x[j] > X[i, 2]) j))
if (length(del_idx > 0)){
x <- x[-del_idx]
r <- r[-del_idx]
}
plot(x ~ r, col="gray66", pch=".", main="Bifurcation Diagram for the Logistic Map")
}
}, movie.name = "bifur.gif", interval=2.4, ani.width=600, ani.height=500)







В результате получим примерно такую картинку:




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







Первое уравнение определяет расстояние от одной точки бифуркации до следующей в единицах r. Второе же показывает, насколько ответвление n длиннее ответвления n+1. Так вот, оказывается, что




Число 4.669201… называется универсальной постоянной Фейгенбаума, которая как раз и характеризует скорость перехода динамических систем от порядка к детерминированному хаосу.

Другой интересный и не менее известный объект — аттрактор Лоренца. На Хабре ему даже посвящена отдельная статья. Для описания движения воздушных потоков Эдвард Лоренц использовал систему из трех обыкновенных дифференциальных уравнений, известных теперь как уравнения Лоренца:





Не будем изголяться и решим эту систему численно — методом Эйлера:

lorenz.solution <- function(sigma=10, r=28, beta=8/3, x=0.01, y=0.01, z=0.01, dt=0.001, n=30000){
sol <- array(0, dim=c(n,3))
t <- 0
for(i in 1:n){
x0 <- x; y0 <- y; z0 <- z
x <- x0 + (y0 - x0) * sigma * dt
y <- y0 + ((r - z0) * x0 - y0) * dt
z <- z0 + (x0 * y0 - beta * z0) * dt
t <- t + dt
sol[i,] <- c(x, y, z)
}
return(sol)
}




Решение системы для параметров, заданных по умолчанию, выглядит так:




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

library(scatterplot3d)
saveGIF({
for (r in 2:34){
sol <- lorenz.solution(r=r)
s3d<-scatterplot3d(sol[,1], sol[,2], sol[,3], color="gray66", angle=15, box=F, grid=F, axis=F, pch=".", main=paste0("Lorenz Attractor with rho=", r))
}
}, movie.name = "lorenz.gif", interval=.3, ani.width=500, ani.height=500)







Аттрактора Лоренца не единственный в своем роде. Например, аттрактор Чена описывается так:




Скрытый текст


chen.solution <- function(a=40, c=28, b=3, x=-0.1, y=0.5, z=-0.6, dt=0.001, n=30000){
sol <- array(0, dim=c(n,3))
t <- 0
for(i in 1:n){
x0 <- x; y0 <- y; z0 <- z
x <- x0 + (y0 - x0) * a * dt
y <- y0 + ((c - a) * x0 - x0 * z0 + c * y0) * dt
z <- z0 + (x0 * y0 - b * z0) * dt
t <- t + dt
sol[i,] <- c(x, y, z)
}
return(sol)
}

saveGIF({
for (a in 32:45){
sol <- chen.solution(a=a)
s3d<-scatterplot3d(sol[,1], sol[,2], sol[,3], color="gray66", angle=15, box=F, grid=F, axis=F, pch=".", main=paste0("Chen Attractor with a=", a))
}
}, movie.name = "chen.gif", interval=.25, ani.width=500, ani.height=500)










Орбиты, по которым происходит движение, «стягиваются» к аттрактору; это движение хаотично и чувствительно к начальным условиям, в то же время оно стабильно в глобальном плане. Дэвид Фельдман, который ведет курс «Introduction to Dynamical Systems and Chaos», говорит, что, хотя в хаотичных системах трудно предсказать состояние какой-то конкретной точки, статистические же параметры таких систем вполне точно определены. Таким образом, можно утверждать о статистической предсказуемости системы. Например, погода в конкретную минуту, строго говоря, непредсказуема, зато климат имеет вполне себе определенные параметры. И в этом нет никакого противоречия.

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.


Flappy Bot для Flappy Bird

image

Сумасшедшая игра. Какой хлопец не слышал про Flappy Bird? Про 50 000 долларов дохода в день? Игре посвящены финансовые отчеты, веселые песни, желтые статьи и научные исследования. Китайские ребята даже изобрели механического робота, гоняющего птицу.

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

Да. Погонял птичку минут 20. Дальше 10-ой башни пройти не смог. Потом еще минут десять. 22 башни — мой потолок. Нервы ни к черту.

И решили мы с приятелем Кирилом создать своего ро-бота. Забить китайцам баки, как говорил Остап.

Читайте, как это было и смотрите, что получилось.

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


Монета в пол-франка




Прежде всего, наш робот не механический. Нажатия на экран можно имитировать не механической палкой, а электрическим зарядом. Приклеиваем к экрану iPad монетку. К монетке приматываем синей изолентой провод. Подаешь по проводу ток на монетку — iPad срабатывает на нажатие. В этом месте надо говорить умные слова Ёмкостной экран и важно покачивать головой.

image

Фотограф из меня конечно никакой.

Для управления током необходим iPhone. Он снимает на видео игру, запущенную на iPad, распознает момент времени, когда надо нажать на игровой экран и посылает сигнал монетке. Как? По аудио-проводу. Генерим сигнал частотой 20КГц и длительностью 20 миллисекунд. Можно проиграть wav-файл, а лучше моделировать сигнал программно, так точнее. Тем не менее, задержка от начала команды Пи-и-и-и-и-и-и до момента имитации нажатия составляет 100-110 миллисекунд. Запомним это число.


Пример кода? Боже, это скучнее, чем новости по ОРТ, сегодня без кода, ок?


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


image


Повторим наш план



  • На iPad-е запускаем игру Flappy Bird.

  • К экрану iPad приклеиваем монетку

  • Монетка соединяется с конденсатором

  • Конденсатор соединяется с аудио-входом iPhone

  • На iPhone пишем программу, которая через видео камеру наблюдает за игрой на iPad и посылает звуковой сигнал-команду Жми, Малешкин!

  • Конденсатор посылает ток на монетку, монетка имитирует нажатие на iPad

  • Птичка послушно прыгает


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


Для тех, кто шарит в электротехнике
Конечно, никакой это не конденсатор.

image

При подаче аудиосигнала с уровнем >=1V pnp транзистор открывается и подает логический «1» на вход первого инвертора, вызывая изменение полярности двухзатворного FET транзистора.

Открывание FET соединяет висевшую «в воздухе» монету с землёй, увеличивая измеряемую экраном ёмкость до уровня, принимаемого за касание. Ёмкость канала затвор-сток в закрытом состоянии составляет 5pF. Транзистор смонтирован непосредственно на монете для уменьшения паразитной ёмкости соединительных проводов.

Предшествующие этому решению попытки подключения монеты к транзистору экранированным кабелем были неудачными.


Не показано на схеме: земля платы соединена с землёй планшета аудиокабелем.




Коробка из-под ксерокса




Мини-студия для робота была сделана из б/у коробки. Коробку располовинили, завалили набок, на дно бережно уложили игровой iPad с заранее приклеенной монетой. В потолке коробки проделали отверстие для видеокамеры iPhone и положили телефон сверху, так чтобы камера видела игровой экран низлежащего iPad. Уф-ф, потерпите, уже скоро конец.

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

Все.


Распознавание игрового поля, птички и столбов




Здесь просто.

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

Поскольку углы поля практически прямые, поймать черную рамку не представляет труда. Пробегать весь массив 1280 на 720 точек видео-буфера не надо. Я пускаю диагонали от четырех углов до нахождения первой точки игрового экрана. Это примерно 5000 операций сравнения для каждого угла. Копейки.


Да! Совсем забыл.


Какой режим видео выбрать на нашем iPhone? требуется хорошая частота.


Попробовал Low-режим видео. 192 на 144 пиксела. Частота — 20 кадров в секунду. Не годится.

Стандартный видео-захват 480 на 360 точек. Дает частоту 30 кадров в секунду. Лучше, но мало.

А вот прямой перебор видео-режимов находит 60 кадров в секунду при разрешении видео 1280 на 720. Метод перебора взят со stackoverflow.com.


П-парадоксально получается — чем выше разрешение, тем чаще кадры. А что Вы хотели от Стива Джобса? Он еще и не такие сюрпризы приподносил.


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


Зачем знать скорость? Из-за задержки команды нажатия в 110 миллисекнд. Приходится вычислять параболу движения птички, чтобы заранее пикнуть.


Алгоритм пока не совершенен, поскольку создан в течении сегодняшней пятницы.

Но 100 столбов наша птичка берет довольно часто. Раза два за вечер смогла, золото, а не птичка.


Думаю легко доведем это дело до 1000 и успокоимся.


Всем приятного просмотра.



Внимание, реклама




Разумеется, я написал свой клон этой игры. Игру никто не скачивает, она секретная, но специально для Вас, дорогие читатели я даю ссылку на приложение Winter Jumping.

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

Спасибо




Спасибо за внимание.

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.