DevBoy: делаем генератор сигналов

Привет, друзья!

В прошлых статьях я рассказывал про свой проект и про его программную часть. В этой статье я расскажу как простенький генератор сигналов на 4 канала — два аналоговых канала и два PWM канала.

Аналоговые каналы

Микроконтроллер STM32F415RG имеет в своем составе 12-тибитный DAC (digital-to-analog) преобразователь на два независимых канала, что позволяет генерировать разные сигналы. Можно напрямую загружать данные в регистры преобразователя, но для генерации сигналов это не очень подходит. Лучшее решение — использовать массив, в который генерировать одну волну сигнала, а затем запускать DAC с триггером от таймера и DMA. Изменяя частоту таймера можно изменять частоту генерируемого сигнала.

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

Функция генерации данных волн в буфере имеет следующий вид

// *****************************************************************************
// ***   GenerateWave   ********************************************************
// *****************************************************************************
Result Application::GenerateWave(uint16_t* dac_data, uint32_t dac_data_cnt, uint8_t duty, WaveformType waveform)
{
  Result result;

  uint32_t max_val = (DAC_MAX_VAL * duty) / 100U;
  uint32_t shift = (DAC_MAX_VAL - max_val) / 2U;

  switch(waveform)
  {
    case WAVEFORM_SINE:
      for(uint32_t i = 0U; i < dac_data_cnt; i++)
      {
        dac_data[i] = (uint16_t)((sin((2.0F * i * PI) / (dac_data_cnt + 1)) + 1.0F) * max_val) >> 1U;
        dac_data[i] += shift;
      }
      break;

    case WAVEFORM_TRIANGLE:
      for(uint32_t i = 0U; i < dac_data_cnt; i++)
      {
        if(i <= dac_data_cnt / 2U)
        {
          dac_data[i] = (max_val * i) / (dac_data_cnt / 2U);
        }
        else
        {
          dac_data[i] = (max_val * (dac_data_cnt - i)) / (dac_data_cnt / 2U);
        }
        dac_data[i] += shift;
      }
      break;

    case WAVEFORM_SAWTOOTH:
      for(uint32_t i = 0U; i < dac_data_cnt; i++)
      {
        dac_data[i] = (max_val * i) / (dac_data_cnt - 1U);
        dac_data[i] += shift;
      }
      break;

    case WAVEFORM_SQUARE:
      for(uint32_t i = 0U; i < dac_data_cnt; i++)
      {
        dac_data[i] = (i < dac_data_cnt / 2U) ? max_val : 0x000;
        dac_data[i] += shift;
      }
      break;

    default:
      result = Result::ERR_BAD_PARAMETER;
      break;
  }

  return result;
}

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

DAC в данном микроконтроллере имеет ограничение: типичное settling time (время от загрузки нового значения в DAC и появлением его на выходе) составляет 3 ms. Но не все так однозначно — данное время является максимальным, т.е. изменение от минимума до максимума и наоборот. При попытке вывести меандр эти заваленные фронты очень хорошо видно:

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

Генерация на 1 KHz (90% амплитуда):

Генерация на 10 KHz (90% амплитуда):

Генерация на 100 KHz (90% амплитуда):

Уже видны ступеньки — потому что загрузку новых данных в DAC осуществляется с частотой в 4 МГц.

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

Генерация на 200 KHz (90% амплитуда):

Тут уже видно как все волны превратились в треугольник.

Цифровые каналы

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

User Interface

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

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

Кроме того, реализована поддержка сенсорного экрана — при нажатии на неактивный канал он становится активным, при нажатии на активный канал меняется форма волны.

Конечно же используется DevCore для осуществления всего этого. Код инициализации пользовательского интерфейса и обновления данных на экране выглядит так:

Структура содержащая все объекты UI

    // *************************************************************************
    // ***   Structure for describes all visual elements for the channel   *****
    // *************************************************************************
    struct ChannelDescriptionType
    {
      // UI data
      UiButton box;
      Image img;
      String freq_str;
      String duty_str;
      char freq_str_data[64] = {0};
      char duty_str_data[64] = {0};
      // Generator data
      ...
    };
    // Visual channel descriptions
    ChannelDescriptionType ch_dsc[CHANNEL_CNT];

Код инициализации пользовательского интерфейса

  // Create and show UI
  int32_t half_scr_w = display_drv.GetScreenW() / 2;
  int32_t half_scr_h = display_drv.GetScreenH() / 2;
  for(uint32_t i = 0U; i < CHANNEL_CNT; i++)
  {
    // Generator data
    ...
    // UI data
    int32_t start_pos_x = half_scr_w * (i%2);
    int32_t start_pos_y = half_scr_h * (i/2);
    ch_dsc[i].box.SetParams(nullptr, start_pos_x, start_pos_y, half_scr_w, half_scr_h, true);
    ch_dsc[i].box.SetCallback(&Callback, this, nullptr, i);
    ch_dsc[i].freq_str.SetParams(ch_dsc[i].freq_str_data, start_pos_x + 4, start_pos_y + 64, COLOR_LIGHTGREY, String::FONT_8x12);
    ch_dsc[i].duty_str.SetParams(ch_dsc[i].duty_str_data, start_pos_x + 4, start_pos_y + 64 + 12, COLOR_LIGHTGREY, String::FONT_8x12);
    ch_dsc[i].img.SetImage(waveforms[ch_dsc[i].waveform]);
    ch_dsc[i].img.Move(start_pos_x + 4, start_pos_y + 4);
    ch_dsc[i].box.Show(1);
    ch_dsc[i].img.Show(2);
    ch_dsc[i].freq_str.Show(3);
    ch_dsc[i].duty_str.Show(3);
  }

Код обновления данных на экране

      for(uint32_t i = 0U; i < CHANNEL_CNT; i++)
      {
        ch_dsc[i].img.SetImage(waveforms[ch_dsc[i].waveform]);
        snprintf(ch_dsc[i].freq_str_data, NumberOf(ch_dsc[i].freq_str_data), "Freq: %7lu Hz", ch_dsc[i].frequency);
        if(IsAnalogChannel(i)) snprintf(ch_dsc[i].duty_str_data, NumberOf(ch_dsc[i].duty_str_data), "Ampl: %7d %%", ch_dsc[i].duty);
        else                   snprintf(ch_dsc[i].duty_str_data, NumberOf(ch_dsc[i].duty_str_data), "Duty: %7d %%", ch_dsc[i].duty);
        // Set gray color to all channels
        ch_dsc[i].freq_str.SetColor(COLOR_LIGHTGREY);
        ch_dsc[i].duty_str.SetColor(COLOR_LIGHTGREY);
      }
      // Set white color to selected channel
      ch_dsc[channel].freq_str.SetColor(COLOR_WHITE);
      ch_dsc[channel].duty_str.SetColor(COLOR_WHITE);
      // Update display
      display_drv.UpdateDisplay();

Интересно реализована обработка нажатия кнопки (представляет собой прямоугольник поверх которого рисуются остальные элементы). Если вы смотрели код, то должны были заметить такую штуку: ch_dsc[i].box.SetCallback (&Callback, this, nullptr, i); вызываемую в цикле. Это задание функции обратного вызова, которая будет вызываться при нажатии на кнопку. В функцию передаются: адрес статической функции статической функции класса, указатель this, и два пользовательских параметра, которые будут переданы в функцию обратного вызова — указатель (не используется в данном случае — передается nullptr) и число (передается номер канала).

Еще с университетской скамьи я помню постулат: "Статические функции не имеют доступа к не статическим членам класса". Так вот это не соответствует действительности. Поскольку статическая функция является членом класса, то она имеет доступ ко всем членам класса, если имеет ссылку/указатель на этот класс. Теперь взглянем на функцию обратного вызова:

// *****************************************************************************
// ***  Callback for the buttons   *********************************************
// *****************************************************************************
void Application::Callback(void* ptr, void* param_ptr, uint32_t param)
{
  Application& app = *((Application*)ptr);
  ChannelType channel = app.channel;
  if(channel == param)
  {
    // Second click - change wave type
    ...
  }
  else
  {
    app.channel = (ChannelType)param;
  }
  app.update = true;
}

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

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

Исходный код генератора загружен на GitHub: https://github.com/nickshl/WaveformGenerator
DevCore теперь выделена в отдельный репозиторий и включена как субмодуль.

Ну а зачем мне нужен генератор сигналов, будет уже в следующей (или одной из следующих) статье.

Let's block ads! (Why?)

[Перевод] Защищаем веб-сервер на Linux

Привет, Хабр!

У нас давно не выходило новых книг по Linux для начинающих — и вот мы беремся за перевод новинки именно такого плана. Книга "Linux in Action" Дэвида Клинтона вышла в издательстве Manning и рассказывает не только о внутреннем устройстве Linux, но и о наиболее распространенных проблемах, и о способах их устранения.

Автор опубликовал на сайте Hackernoon отрывок из 9-й главы, который мы и предлагаем вам оценить.
Собрать LAMP-сервер, как следует его сконфигурировать, обеспечить надежную обработку данных, настроить предметную область и озаботиться TLS-сертификатом – лишь половина пути к победе. Также необходимо убедиться, что ваша инфраструктура защищена от многочисленных устрашающих угроз Интернета.

В этой статье мы исследуем безопасность веб-сайта, научившись правильно работать с системными группами, обеспечивать изоляцию процессов и регулярный аудит системных ресурсов. Разумеется, этот рассказ не полный (в книге Linux в действии рассмотрены и другие темы, например, установка TLS-сертификатов и работа с SELinux), но для начала и этого будет вполне достаточно.

Системные группы и принцип минимальных привилегий

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

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

Разработчики, входящие в состав группы Developers, могут получить доступ к конкретному каталогу, а для пользователей, не относящихся к данной группе, каталог будет закрыт
Попробуйте сами: создайте в текстовом редакторе новый файл. Запишите в него простой текст, например, «Hello World», чтобы сразу было видно, когда к файлу удалось успешно обратиться. Затем отредактируйте права доступа при помощи chmod 770, так, чтобы владелец файла и члены группы, к которой он относится, имели полные права на работу с файлом, а другие не могли его читать.

$ nano datafile.txt
$ chmod 770 datafile.txt

Если в вашей системе пока нет других пользовательских аккаунтов кроме вашего собственного – создайте такой аккаунт либо при помощи adduser — так делается в Debian/Ubuntu — либо при помощи useradd, как принято в CentOS. Команда useradd сработает и в Ubuntu.

Команда useradd в отличие от adduser из Debian требует, чтобы пользовательский пароль генерировался отдельно:

# useradd otheruser
# passwd otheruser
Enter new UNIX password:
Retype new UNIX password:
passwd: password updated successfully

При помощи команды su переключаемся на нового пользователя. После того, как мы введем его пароль, все следующие команды будут выполняться от имени этого пользователя. Вы будете работать от лица именно этого пользователя; ни больше, ни меньше. Если вы попытаетесь считать файл данных datafile.txt (при помощи cat), то ничего у вас больше не выйдет; как вы помните, права на чтение есть только у членов группы. Когда закончите, введите exit, чтобы выйти из оболочки нового пользователя, и вернитесь в свою исходную оболочку.

$ su otheruser
Password:
$ cat /home/ubuntu/datafile.txt
cat: /home/ubuntu/datafile.txt: Permission denied
$ exit

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

Создадим новую группу, при помощи которой сможем управлять данными нашего приложения, а затем отредактируем свойства нашего файла с данными при помощи команды chown. Аргумент ubuntu:app-data-group оставляет права на владение файлом пользователю Ubuntu, но группа его меняется на новую: app-data-group.

# groupadd app-data-group
# chown ubuntu:app-data-group datafile.txt

Запустите ls, чтобы получить «развернутый» вывод этого файла и просмотреть его новые права доступа и статус. Обратите внимание: как и следовало ожидать, файлом владеет пользователь ubuntu, относящийся к группе app-data-group.

$ ls -l | grep datafile.txt
-rwxrwx — — 1 ubuntu app-data-group 6 Aug 9 22:43 datafile.txt

Можно применить usermod, чтобы добавить вашего пользователя к app-data-group, а затем – команду su, чтобы переключиться на оболочку, в которой развернут аккаунт другого пользователя. Теперь, даже несмотря на то, что права доступа к файлу закрывают его от всех «других» — а вы на данный момент определенно «другой» пользователь — вы должны свободно читать этот файл, поскольку относитесь к нужной группе.

# usermod -aG app-data-group otheruser
$ su otheruser
$ cat datafile.txt
Hello World

При помощи команды su переключаемся между пользовательскими аккаунтами. Они и записаны в моем файле datafile.txt. Такая организация – правильный и эффективный способ устранения разнообразных сложных проблем с правами доступа, которые могут возникать в многопользовательской системе.

На самом деле, она применяется не только для предоставления нужных прав доступа отдельным пользователям – многие системные процессы также не могли бы выполнять своих задач, если бы для них не была прописана принадлежность к нужным группам. Можете по диагонали просмотреть файл /etc/group – обратите внимание, как много системных процессов относятся к собственным группам…

Сокращенный листинг содержимого /etc/group file:

$ cat /etc/group
root:x:0:
daemon:x:1:
bin:x:2:
sys:x:3:
adm:x:4:syslog
tty:x:5:
disk:x:6:
lp:x:7:
mail:x:8:
news:x:9:
uucp:x:10:
man:x:12:
proxy:x:13:
[…]

Изоляция процессов в контейнерах

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

Ранее эту проблему было принято решать так: на каждую службу выделяли свою физическую машину. Однако, благодаря виртуализации становится гораздо проще и дешевле выстроить «ячеистую» архитектуру. Сегодня такая архитектура часто именуется микросервисной и позволяет запускать сразу множество контейнеров, в одном из которых может работать, к примеру, база данных, в другом — Apache, а в третьем – медиа-файлы, которые могут встраиваться в ваши веб-страницы. Микросервисная архитектура позволяет не только значительно повысить производительность и эффективность, но и значительно снижают риск взлома каждого отдельного компонента.

«Контейнеры», о которых я говорю, не обязательно должны обладать убедительностью LXC. Сегодня гораздо популярнее становятся и другие контейнерные технологии, например, Docker.

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

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

В данном случае хорошо, что выявить таких самозванцев не составляет труда: их пользовательский и/или групповой ID, как и у админа, будет «0». Взгляните на файл passwd в каталоге /etc/. В этом файле содержится по записи для каждого обычного и системного пользовательского аккаунта, уже существующего в системе. В первом поле содержится имя аккаунта (в данном случае — root и ubuntu), а во втором вместо пароля может стоять x (если пароль существует – он будет в зашифрованном виде находиться в файле/etc/shadow). Но в следующих двух полях содержатся пользовательский и групповой ID. В случае с ubuntu в данном примере оба ID равны 1000. А у администратора, как видите, здесь стоят нули.

$ cat /etc/passwd
root:x:0:0:root:/root:/bin/bash
[…]
ubuntu:x:1000:1000::/home/ubuntu:/bin/bash

Если когда-нибудь встретите обычного пользователя с пользовательским или групповым ID = 0, то можете не сомневаться, что дело тут нечисто, и ситуацию нужно исправить. Быстрый и легкий способ выявить такую проблему – проверить файл passwd командой awk, которая выведет все строки, в третьем поле которых нет ничего кроме 0. В моем случае (можно выдохнуть) нашлась всего одна такая строка – рут. Можете запустить ее повторно, заменив $4 на $3 – так вы проверите поле группового ID.

$ awk -F: ‘($3 == “0”) {print}’ /etc/passwd
root:x:0:0:root:/root:/bin/bash

Аудит ресурсов системы

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

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

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

Сканирование портов

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

Вы уже знаете, что на обычном веб-сервере, вероятно, должны быть открыты порты HTTP (80) и SSH (22), поэтому они вас не удивят. Но гораздо важнее обращать внимание и на другие, неожиданные результаты. Команда netstat выводит все открытые порты, а также массу информации о том, как именно они используются.

В данном примере мы проверяем совершенно типичный многоцелевой сервер, и команда -n приказывает netstat включить все числовые порты и адреса. -l включает лишь слушающие сокеты, а -p добавляет ID процесса слушающей программы. Естественно, если что-то видите — действуйте.

# netstat -npl
Active Internet connections (only servers)
Proto Local Address Foreign Address State PID/Program name
tcp 127.0.0.1:3306 0.0.0.0:* LISTEN 403/mysqld
tcp 0.0.0.0:139 0.0.0.0:* LISTEN 270/smbd
tcp 0.0.0.0:22 0.0.0.0:* LISTEN 333/sshd 
tcp 0.0.0.0:445 0.0.0.0:* LISTEN 270/smbd
tcp6 :::80 :::* LISTEN 417/apache2 
[…]

В последние годы вместо netstat все чаще применяется ss. Просто на всякий случай: если когда-нибудь вечером окажетесь в компании, и кто-то спросит вас о ss, то этот пример (в котором перечислены все установленные SSH-соединения) должен быть достаточно информативен, чтобы вы могли не ударить в грязь лицом:

$ ss -o state established ‘( dport = :ssh or sport = :ssh )’
Netid Recv-Q Send-Q Local Address:Port Peer Address:Port 
tcp 0 0 10.0.3.1:39874 10.0.3.96:ssh 
timer:(keepalive,18min,0)

Проверяем активные службы

Если сделать быстрый мгновенный снимок служб, управляемых system и в настоящее время активных на вашем компьютере, то машина поможет выявить любую нежелательную активность. Команда systemctl может вывести список всех существующих служб, а потом их список можно сузить до тех, в описании которых содержится enabled. Так будут возвращены лишь активные службы.

# systemctl list-unit-files — type=service — state=enabled
autovt@.service                       enabled 
bind9.service                         enabled 
cron.service                          enabled 
dbus-org.freedesktop.thermald.service enabled 
docker.service                        enabled 
getty@.service                        enabled 
haveged.service                       enabled 
mysql.service                         enabled 
networking.service                    enabled 
resolvconf.service                    enabled 
rsyslog.service                       enabled 
ssh.service                           enabled 
sshd.service                          enabled
syslog.service                        enabled 
systemd-timesyncd.service             enabled 
thermald.service                      enabled 
unattended-upgrades.service           enabled 
ureadahead.service                    enabled

Если вы найдете что-то такое, чему тут явно не место – можете воспользоваться командой systemctl, и чтобы остановить службу, и чтобы убедиться, что она не перезапускается при следующей загрузке.

# systemctl stop haveged
# systemctl disable haveged

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

Мог ли кто-то установить в системе программы без вашего ведома? Ну, чтобы узнать – нужно посмотреть. Команда yum list installed или, в случае Debian/Ubuntu, dpkg — list выдаст вам подробную сводку, а команда remove должна удалить все пакеты, которые нам не нужны.

# yum list installed
# yum remove packageName

Вот как то же самое делается в Ubuntu:

# dpkg --list
# apt-get remove packageName

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

Let's block ads! (Why?)

[Из песочницы] Быстрая математика с фиксированной точкой для финансовых приложений на Java

Не секрет, что финансовая информация (счета, проводки и прочая бухгалтерия) не очень дружит с числами с плавающей точкой, и множество статей рекомендует использовать фиксированную точку (fixed point arithmetic). В Java этот формат представлен, по сути, только классом BigDecimal, который не всегда можно использовать по соображениям производительности. Приходится искать альтернативы. Эта статья описывает самописную Java библиотеку для выполнения арифметических операций над числами с фиксированной точностью. Библиотека была создана для работы в высокопроизводительных финансовых приложениях и позволяет работать с точностью до 9 знаков после запятой при сохранении приемлемой производительности. Ссылка на исходники и бенчмарки приведены в конце статьи.

Cовременные компьютеры могут выполнять арифметические операции только с ограниченной точностью. Это дискретные устройства, которые могут работать не со всеми возможными числами, а только с некоторым их счетным подмножеством. Самым распространённым форматом работы с вещественными числами в памяти компьютера является плавающая (двоичная) точка — floating (binary) point, когда числа хранятся в виде M*2^E, где M и E — целые мантисса и порядок числа. Но некоторые числа, например 0.1, невозможно точно представить в этом формате. Поэтому в ходе сложных вычислений неизбежно накапливается некоторая ошибка. То есть результат машинного вычисления, скажем 0.1 + 0.1 + 0.1, не совпадает с математически правильным 0.3. Учитывая вышесказанное, при программировании сложной арифметики можно придерживаться нескольких стратегий:

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

Стратегия 2 — скрупулёзно подсчитать. Формулы для подсчета машинных погрешностей известны не одно десятилетие. Они позволяют оценить сверху относительную погрешность любой арифметической операции. Наверное, так и приходится делать для серьёзного численного моделирования. Проблема в том, что это очень трудоемко. По сути, каждый символ + — * / в коде должен сопровождаться вычислением погрешности. Нужно учесть все зависимости между вычислениями и повторять процедуру каждый раз при изменении кода.

Стратегия 3 — использовать десятичную точку (floating decimal point) вместо двоичной. То есть хранить числа в виде M*10^E. Это не решает проблем с погрешностью (мантисса по-прежнему округляется до конечного числа значащих цифр), но по крайней мере все «простые» для человека числа (вроде 1.1) теперь представлены в памяти точно. Расплатой будет производительность. Любая нормализация чисел (то есть эквивалентное уменьшение мантиссы и увеличение порядка) требует деления на степень 10, что очень не быстро, в отличие от деления на степень 2. А нормализовывать приходится много — при каждом сложении или вычитании с разными порядками.

Стратегия 4 — использовать фиксированную точку (fixed decimal point). Упрощение стратегии 3, когда мы фиксируем порядок E. В этом случае для сложения/вычитания не нужна нормализация. Кроме того, все вычисления будут иметь одинаковую абсолютную погрешность. Именно этой стратегии посвящена статья.

В отличие от физики, где важна относительная погрешность, в финансах нужна как раз абсолютная. Если после проведения сложной финансовой транзакции клиенту выставить счёт в $1000000.23 в то время как он ожидает $1000000.18, то могут возникнуть некоторые трудности. Объяснения типа «да зачем вам точность в 8 значащих цифр??» могут не прокатить. И дело тут не в 5 центах убытка (ошибиться наоборот, «в пользу» клиента, не сильно лучше), а в нестыковках бухгалтерского учёта. Поэтому правила вычислений и округлений четко оговариваются между сторонами, и артефакты от использования double и float переменных порой усложняют жизнь.

В Java есть стандартный класс для fixed point арифметики — BigDecimal. Проблемы с ним две: он медленный (из-за своей универсальности) и он немутабельный. Немутабельность означает что любая операция выделяет объект в куче. Выделение и освобождение в пересчете на объект занимает немного времени, но интенсивные вычисления в «горячем» коде создают приличную нагрузку на GC, неприемлемую в некоторых случаях. Можно понадеяться на escape-analysis и скаляризацию, но они очень нестабильны в том смысле, что даже незначительное изменение в коде или в JIT (типа ленивой загрузки новой реализации интерфейса) может перевернуть вверх ногами всю структуру инлайна, и метод, минуту назад нормально работавший, вдруг начнёт бешено выделять память.

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

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

public class Sample {
    private final Decimal margin;
    private final Quantity cumQuantity = new Quantity();
    private final Quantity contraQuantity = new Quantity();
    private final Quantity cumContraQuantity = new Quantity();
    private final Price priceWithMargin = new Price();
    private final Price avgPrice = new Price();

    public Sample(int marginBp) {
        // 1 + margin / 10000
        this.margin = Decimal.create(marginBp).divRD(10000L).add(1);
    }

    public Price calculateAvgPrice(Quantity[] quantities, Price[] prices) {
        cumQuantity.set(0);
        contraQuantity.set(0);

        // avg = sum(q * p * margin) / sum(q)
        for (int i = 0; i < quantities.length; i++) {
            cumQuantity.add(quantities[i]);
            priceWithMargin.set(prices[i]).mulRD(margin);
            contraQuantity.set(quantities[i]).mulRD(priceWithMargin);
            cumContraQuantity.add(contraQuantity);
        }

        return avgPrice.quotientRD(cumContraQuantity, cumQuantity);
    }

    public static void main(String[] args) throws ParseException {
        Price p1 = Price.create("1.5");
        Price p2 = Price.create(1.6);

        Quantity q1 = Quantity.create("100");
        Quantity q2 = Quantity.create(200);

        // apply 0.05% margin to the prices
        Sample sample = new Sample(5); 
        System.out.println(sample.calculateAvgPrice(new Quantity[]{q1, q2}, new Price[]{p1, p2}));
    }
}

Итак, нам нужна мутабельная обертка целочисленного примитива, если точнее — long’а, который даст нам почти 19 значащих цифр (хватит и на целую и на дробную часть). В long'е мы подразумеваем N десятичных знаков после запятой. Например, при N=2, число 2.56 хранится как 256 (двоичное 100000000). Отрицательные числа хранятся стандартно, в дополнительном коде:

-2.56
-256

(Здесь и далее курсивом обозначены «математические» числа и вычисления, а жирным – их внутреннее представление)

Также мне показалось полезным ввести NaN отдельным значением, которое возвращается в случае арифметических ошибок (вместо исключения или мусора). NaN представлен внутри как Long.MIN_VALUE, «распространяется» (propagated) через все операции и позволяет определить инвертирование знака для всех оставшихся чисел.

Попробуем прикинуть алгоритмы арифметических операций для случая, когда N=2.

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

1.20 + 2.30 = 3.50
120 + 230 = 350

Умножение и деление требуют дополнительной нормализации, то есть умножения/деления на 10^N (на 100 в нашем примере)

1.20 * 2.00 = 2.40
120 * 200 / 100 = 240

1.20 / 2.00 = 0.60
100 * 120 / 200 = 60

Дополнительное деление — не самая быстрая операция. Но в данном случае это деление на константу, ведь мы заранее зафиксировали N=2 и 10^N=100. Деление на константу, особенно на «красивую» (типа 10), интенсивно оптимизируется в CPU и сильно быстрее деления на случайное число. Мы делаем кучу делений на 10 каждый раз, когда преобразовываем любое число в строку (например в логах), и производители CPU об этом знают (подробнее про оптимизации см "Division by a constant").

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

1.00 / 2.00 = 0.50
100 * 100 / 200 = 50

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

Попробуем обратить другое число:

1.00 / 3.00 = 0.33
100 * 100 / 300 = 33

Честный математический результат лежит между 0.33 и 0.34, но мы не можем его точно представить. В какую сторону округлять? Обычно округляют к 0, и это самый быстрый способ (поддерживается аппаратно). Но, возвращаясь к реальным финансовым задачам, это не всегда так. Обычно при обработке транзакций с клиентом округление идёт «в пользу клиента». То есть цена округляется вверх, если клиент продаёт, и вниз, если клиент покупает. Но могут потребоваться и другие варианты, например арифметическое округление к ближайшему числу с подтипами (half-up, half-down, half-even) для минимизации бухгалтерских нестыковок. Или округление к ±бесконечности для отрицательных цен (у некоторых финансовых инструментов). Java BigDecimal уже содержит список стандартных режимов округления, и описываемая библиотека их все поддерживает. Режим UNNECESSARY возвращает NaN, если операция неожиданно потребует округления.

В режиме округления вверх наше вычисление должно давать:

1.00 / 3.00 = 0.34
100 * 100 / 300 + 1 = 34

Как узнать, что нужно добавить единицу? Нужен остаток от деления 10000 % 300 = 100. Который такой же медленный, как и само деление. К счастью, если написать подряд в коде "a/b; a%b", то JIT сообразит что 2 деления не нужно, достаточно одной ассебмлерной команды div возвращающей 2 числа (частное и остаток).

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

В API я намеренно сделал упоминание округления везде, где оно происходит, либо в виде параметра, либо в виде суффикса RoundDown в методах, где оно по умолчанию происходит к нулю.

Мы подходим к самой сложной части. Вспомним ещё раз наше умножение:

1.20 * 2.00 = 2.40
120 * 200 / 100 = 240

Теперь представим, что мы в 1980-х и процессоры у нас 16-битные. То есть нам доступен только short с максимальным значением 65535. Первое умножение переполнится и будет равно 240000 & 0xFFFF = 44392 (это если без знака, со знаком оно будет ещё и отрицательным), что поломает нам результат.

Так не пойдёт. У нас 2 нормальных (влезающих в наш диапазон значений) аргумента, и такой же нормальный ожидаемый результат, но мы переполняемся на полдороге. Точно такая же ситуация возможна и с 64-битным long’ом, просто числа нужны побольше.

В 1980-х нам потребовалось бы умножение, дающее 32-битный результат. Сегодня нам требуется умножение с 128-битным результатом. Самое обидное то, что оба умножения доступны в ассемблерах 8086 и x86-64 соответственно, но мы не можем использовать их из Java! JNI, даже в случае хака с быстрым JavaCritical, даёт оверхед в десятки наносекунд, привносит сложности с деплоем и совместимостью, замораживает GC на время вызова. К тому же нам каким-то образом пришлось бы возвращать 128-битный результат из native метода, а запись по ссылке в массив (в память) — это дополнительная задержка.

В общем пришлось мне писать ручное умножение и деление. Столбиком. Мне требовались 2 вспомогательные операции:

1. A(64) * B(64) = T(128); T(128) / N(32)= Q(64),R(32) — как часть fixed point умножения A*B
2. N(32) * A(64) = T(96); T(96) / B(64) = Q(64),R(64) — как часть fixed point деления A/B
   (в скобках указана размерность данных в битах, T — временная переменная, которая не должна переполняться)

Обе операции возвращают частное и остаток (одно – как результат метода, второе — в поле объекта). Они тоже могут переполняться, но только на последнем шаге, когда это неизбежно. Вот пример (из 1980-х):

500.00 / 0.50 = 1000.00
100 * 50000 / 50 = 100000 — переполнение!

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

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

Обычно (за исключением особых случаев), обе операции содержат 4 умножения и 2 деления. Операция 1 существенно быстрее 2, так как в ней эти деления — на константу.

Кстати, если кто заметил, N(32) — это наша 10^N для нормализации. Она 32-битная, из чего следует, что N может быть максимум 9. В реальных виденных мной приложениях использовалось 2, 4 или 8 знаков после запятой. Больше 9 я не встречал, так что должно хватить. Если делать 10^N 64-битным, код усложняется (и замедляется) ещё сильнее.

Иногда необходимо выполнить операцию над аргументами с разным количеством знаков после запятой. Как минимум – ввести операции с участием обычного long.

К примеру:

2.0000(N=4) + 3.00(N=2) = 5.0000(N=4)
20000 + 300 * 100 = 50000

3.00 (N=2) + 2.0000(N=4) = 5.00(N=2)
300 + 20000 / 100 = 500

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

Количество знаков после запятой НЕ хранится в объекте. Вместо этого, предполагается наличие отдельного подкласса для каждой точности. Имена классов могут быть бизнес-ориентированными, например Price (N=8), Quantity (N=2). А могут быть обобщенными: Decimal1, Decimal2, Decimal3,… Чем больше точность, тем меньше диапазон хранимых значений, минимальный диапазон имеет Decimal9: ±9223372036. Предполагается, что одного-двух классов будет достаточно, чтобы покрыть необходимую функциональность, и в этом случае абстрактный метод getScale скорее всего будет девиртуализирован и заинлайнен. Подклассы (вместо дополнительного поля) позволяют строго типизировать точность аргументов и результата, а также сигнализировать о возможном округлении на этапе компиляции.

Библиотека позволяет производить операции в которых участвуют максимум 2 (но не 3) разных точности. То есть должны совпадать либо точности двух аргументов, либо точность одного из аргументов и результата. Опять-таки, поддержка 3-х разных точностей сильно замедлила бы код и усложнила бы API. В качестве аргументов можно передавать обычный long, для которого предполагается точность N=0.

2.0000 / 3.0 = 0.6667 — ok (2 разных точности)
2 / 3= 0.6667 — ok (long аргументы, decimal результат)
2 / 3.0 = 0.6667 — невозможно! (3 разных точности)

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

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

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

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

Код

Benchmark	Mode	Cnt	Score	Error	Units
DecimalBenchmark.control	avgt	200	10.072	± 0.074	ns/op
DecimalBenchmark.multiplyNative	avgt	200	10.625	± 0.142	ns/op
DecimalBenchmark.multiplyMyDecimal	avgt	200	35.840	± 0.121	ns/op
DecimalBenchmark.multiplyBigDecimal	avgt	200	126.098	± 0.408	ns/op
DecimalBenchmark.quotientNative	avgt	200	70.728	± 0.230	ns/op
DecimalBenchmark.quotientMyDecimal	avgt	200	138.581	± 7.102	ns/op
DecimalBenchmark.quotientBigDecimal	avgt	200	179.650	± 0.849	ns/op

В целом, умножение получается в 4 раза быстрее BigDecimal, деление — в 1.5. Скорость деления сильно зависит от аргументов, отсюда такой разброс значений.

Let's block ads! (Why?)

[Перевод] Курс MIT «Безопасность компьютерных систем». Лекция 10: «Символьное выполнение», часть 1

Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год

Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
Лекция 5: «Откуда берутся ошибки систем безопасности» Часть 1 / Часть 2
Лекция 6: «Возможности» Часть 1 / Часть 2 / Часть 3
Лекция 7: «Песочница Native Client» Часть 1 / Часть 2 / Часть 3
Лекция 8: «Модель сетевой безопасности» Часть 1 / Часть 2 / Часть 3
Лекция 9: «Безопасность Web-приложений» Часть 1 / Часть 2 / Часть 3
Лекция 10: «Символьное выполнение» Часть 1 / Часть 2 / Часть 3

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

Символьное выполнение является рабочей лошадкой современного анализа программ. Это один из методов, который вырос из исследований и затем стал использоваться во множестве приложений. Например, на сегодня в Microsoft есть система под названием SAGE, которая работает с большим количеством важного программного обеспечения Microsoft, начиная от Power Point и заканчивая самой Windows, чтобы реально находить проблемы безопасности и уязвимости.

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

Например, вы действительно хотите быть в состоянии отличить реальные проблемы от ложных срабатываний. Как же это работает?

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

Здесь у нас имеется отрывок очень простого кода из нескольких ветвей и утверждение, что если при некотором условии значение t < х, то это ложное утверждение. Мы хотим узнать, может ли это утверждение когда-либо быть вызвано. Это возможно? Существуют ли какие-то входные данные, которые сделают так, чтобы это утверждение провалилось?

Одна из вещей, которую я могу сделать – это проверить выполнение данной программы на примере конкретных значений входных данных. Предположим, что мы используем входные данные, при которых X= 4 и Y = 4. Величина T равно нулю, как это объявлено в начале программы.

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

Таким образом, состояние может быть полностью охарактеризовано этими тремя переменными вместе со знанием того, в каком месте программы я нахожусь. Поэтому, если я начну выполнение с 4, 4 и 0 и доберусь до конца ветви, то проверю выражение: 4 больше 4? Очевидно, что нет.
Теперь я собираюсь выполнить программу при T = Y, то есть T больше не равно 0, а имеет значение, равное 4. Таково нынешнее состояние моей программы, и теперь я могу оценить эту ветвь.

Правильно ли, что T < X? Нет. Мы увернулись от пули, утверждение false не сработало. Не было никаких проблем в этом частном выполнении.

Но это ничего не говорит нам ни о каком другом выполнении. Мы знаем, что при значениях X=4 и Y=4 программа не подведет. Но это ничего не говорит нам о том, что произойдёт, если входными значениями буду 2 и 1.

При таких значениях входных данных выполнение пойдёт по другому пути. На этот раз мы видим, что T = X, и после выполнения этой строки T примет значение, равное 2. Есть ли какие-либо проблемы в этом выполнении? Возникнет ли при таких входных данных ошибка утверждения?

Что ж, давайте посмотрим. Так, если T равно 2 и Х равно 2, то T никак не меньше Х. Похоже, мы снова увернулись от пули. Верно? Итак, здесь у нас есть два конкретных входных значения, при которых программа работает без ошибок. Но на самом деле это ничего не говорит нам о любых других значениях input.

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

Для такой программы, как эта, её состояние определяется значением этих трех различных переменных: X, Y и T и знанием того, в каком месте программы в данный момент я нахожусь. Но теперь вместо конкретных значений для X и Y у меня будет символьное значение, просто переменная. Переменная, которая позволяет мне дать имя этому значению, которое пользователь использует в качестве input. Это означает, что состояние моей программы больше не характеризуется сопоставлением имен переменных конкретным значениям. Теперь это сопоставление имен переменных этим символьным значениям.

Символьное значение можно рассматривать как формулу. В этом случае формула для Х равна Х и формула для Y равна просто Y, а для T она на самом деле равна значению 0. Мы знаем, что для каждого входного значения не важно, что именно вы делаете. Значение T после первого утверждения будет равно 0.

Вот где теперь становится интересно. Мы добрались до этой ветви, которая говорит, что если X больше Y, мы пойдем в одном направлении. Если X меньше или равно Y, мы пойдем в другом направлении.

Мы знаем что-нибудь об X и Y? Что нам о них известно? По крайней мере, мы знаем их тип, мы знаем, что они будут варьироваться в интервале от min int до max int, но это все, что мы о них знаем. Получается, что информация, которую мы о них знаем, недостаточна для того, чтобы сказать, в каком направлении может идти эта ветка. Она может идти в любом направлении
Существует много вещей, которые мы можем сделать, но что мы можем сделать в данный момент? Попробуйте высказать самое дикое предположение.

Аудитория: мы можем проследить выполнение программы по обеим ветвям.

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

Итак, если мы хотим следовать за обеими ветвями, мы должны следовать сначала за одной, а затем за другой, верно? Допустим, мы начнём с этой ветки – T=X. Мы знаем, что если доберёмся до этого места, то T будет иметь то же значение, что и X. Мы не знаем, каково это значение, но у нас есть для него имя — это скрипт X.

Если мы возьмем противоположную ветвь, что тогда произойдет? Значение T будет равно чему-то другому, так? В этой ветви значением T будет символьное значение Y.

Так что означает это значение T, когда мы дойдем до этой точки в программе? Может быть, это Х, может быть это Y. Мы не знаем точно, какое именно это значение, но почему бы нам не дать ему имя? Назовём его t₀. И что мы знаем о t₀? В каких случаях t₀ будет равно X?

По существу, мы знаем, что если X больше Y, то переменная равна X, а если X меньше или равно Y, то переменная равна Y. Поэтому у нас есть значение, которое мы определили, назовём его t₀, и у него есть эти логические свойства.

Итак, в данной точке программы у нас есть имя для значения T, это t₀. Что же мы здесь сделали? Мы взяли обе ветви оператора if, а затем вычислили символьное значение, посмотрев, при каких условиях будет выполняться одна ветвь программы, а при каких – другая.
Теперь дело доходит до того, что мы должны спросить, может ли T быть меньше Х. Теперь значение T равно t₀, и мы хотим знать, возможно ли, чтобы t₀ было бы меньше, чем Х? Вспомните первую ветвь, которую мы рассмотрели — мы задавали вопрос об X и Y и ничего о них не знали, кроме того, что они имели тип int.

Но имея t₀, мы действительно много о нём знаем. Мы знаем, что в отдельных случаях он будет равен Х, а в некоторых случаях он будет равен Y. Так что теперь это дает нам набор уравнений, которые мы можем решить. Итак, мы можем сказать, возможно ли, что t₀ меньше, чем Х, зная, что t₀ удовлетворяет всем этим условиям? Таким образом, можно выразить это как ограничение, показывающее, возможно ли, чтобы t₀ было меньше, чем Х. И если Х больше Y, то t₀ равно Х, а если Х меньше или равно Y, это означает, что t₀ = Y.

Итак, у нас есть уравнение. Если оно имеет решение, если можно найти значение t₀, значение Х и значение Y, которые удовлетворяют этому уравнению, тогда мы узнаем эти значения, и когда введём их в программу, то при выполнении она пойдёт по этой ветви if t < x и «взорвется», когда попадет в assert false.

Так что мы здесь cделали? Мы выполнили программу, но вместо того, чтобы сопоставить имена переменных конкретным значениям, мы придали этим именам переменных символьные значения. По сути, дали им другие имена переменных. И в этом случае наши другие имена переменных – это скрипт X, скрипт Y, t₀, и кроме того, у нас есть набор уравнений, которые показывают, как эти значения связаны. У нас есть уравнение, которое говорит нам, как t₀ связан с X и Y в этом случае.

Решение этого уравнения позволяет ответить на вопрос, может ли эта ветвь исполняться или нет. Взглянем на уравнение — можно ли взять эту ветвь или нет? Похоже, что нет, потому что мы ищем случаи, где t₀ меньше, чем Х, но если в первом условии t₀ = X, то выражение t₀ < X будет неправдой.

Таким образом, это означает, что когда X > Y, то этого не может произойти, потому что t₀ = X и оно не может одновременно быть равным и меньшим X.

А что произойдёт, если t₀ = Y? Может ли t₀ быть меньше X в этом случае?

Нет, определенно не может, потому что мы знаем, что X < Y. Так что если t₀ будет меньше X, тогда оно будет также меньше Y. Но мы знаем, что в этом случае t₀ = Y. И поэтому, опять же, это условие не может быть удовлетворено. Итак, мы имеем здесь уравнение, которое не имеет решения, при этом не важно, какие значения вы включаете в это уравнение.

Вы не можете решить его, и это говорит нам, что независимо от того, какие входные данные Х и Y мы передадим программе, она не будет спускаться по ветке if t < x.

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

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

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

Аудитория: что, если программа не поддерживает ввод определённого типа переменных?

Профессор: это очень хороший вопрос! Допустим, у нас есть та же самая программа, но вместо t = x у нас будет t = (x-1). Тогда интуитивно мы можем представить, что теперь эта программа может «взорваться», не так ли?

Потому что когда программа пойдет по этому пути, t действительно будет меньше x. Что же случится с такой программой? Как будет выглядеть наше символьное состояние? Чему будет равно t₀, когда x больше y? Исправим строки в наших уравнениях в соответствии с другим значением, когда t = (x-1). Теперь программа может потерпеть неудачу, и вы идёте к разработчику и говорите ему: «эй, эта функция может взорваться, когда x больше y»!

Разработчик смотрит на это и говорит: «о, я забыл сказать вам — фактически эта функция никогда не будет вызываться с параметрами, где x больше y. Я просто написал так по неким историческим соображениям, так что не беспокойтесь, я бы об этом и не вспомнил, если бы вы мне не рассказали».

Допустим, у нас есть предположение, что x будет меньше или равно y.

Это предварительное условие или соглашение для нашей функции. Функция обещает что-то сделать, но только, если значение удовлетворяет этому предположению. Но если оно не удовлетворено, функция говорит: «мне все равно, что произойдет. Я обещаю, что ошибки не будет только в том случае, когда это предположение будет выполнено».

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

Спрашивается, могу ли я найти x и y, которые удовлетворяют всем этим ограничениям и одновременно обладают требуемыми свойствами? Можно увидеть, что это ограничение Х ≤ Y представляет собой разницу межу случаем, когда это ограничение выполняется, и случаем, когда оно не выполняется.

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

Как же сделать это механическим способом? Существуют два аспекта этой проблемы. Аспект номер один — как вы на самом деле придумали эти формулы?

В данном случае интуитивно понятно, как мы пришли к этим формулам, мы просто составили их вручную. Но как создавать эти формулы механическим способом?

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

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

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

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

На практике это звучит немного страшно и немного магически. Большую часть проблем, которые должны решать SMT, представляют NP-полные задачи, то есть задачи с ответом «да» или «нет».
Можем ли мы иметь систему, которая опирается в качестве своего основного строительного блока на решение NP-полных задач? Или нам нужно еще что-нибудь, что работает на практике? Дело в том, что у многих SMT – решателей есть ещё и третий возможный ответ: «Я не знаю».

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

27:30 мин

Курс MIT «Безопасность компьютерных систем». Лекция 10: «Символьное выполнение», часть 2

Полная версия курса доступна здесь.

Спасибо, что остаётесь с нами. Вам нравятся наши статьи? Хотите видеть больше интересных материалов? Поддержите нас оформив заказ или порекомендовав знакомым, 30% скидка для пользователей Хабра на уникальный аналог entry-level серверов, который был придуман нами для Вас: Вся правда о VPS (KVM) E5-2650 v4 (6 Cores) 10GB DDR4 240GB SSD 1Gbps от $20 или как правильно делить сервер? (доступны варианты с RAID1 и RAID10, до 24 ядер и до 40GB DDR4).

VPS (KVM) E5-2650 v4 (6 Cores) 10GB DDR4 240GB SSD 1Gbps до декабря бесплатно при оплате на срок от полугода, заказать можно тут.

Dell R730xd в 2 раза дешевле? Только у нас 2 х Intel Dodeca-Core Xeon E5-2650v4 128GB DDR4 6x480GB SSD 1Gbps 100 ТВ от $249 в Нидерландах и США! Читайте о том Как построить инфраструктуру корп. класса c применением серверов Dell R730xd Е5-2650 v4 стоимостью 9000 евро за копейки?

Let's block ads! (Why?)

Акции Supermicro обвалились на фоне расследования о внедрении в серверы компании китайских шпионских чипов

Издание Bloomberg Businessweek опубликовало большой материал о шпионском микрочипе, который был разработан китайскими спецслужбами. Его в тайне встраивали в конструкцию материнских плат для серверов Supermicro, происводимых в Китае. С помощью микрочипа атакующие получали возможности удаленного контроля сервера. Всего было атаковано около 30 америсканских компаний из сферы финансов и технологий.

Расследование вызвало огромный резонанс, в результате чего акции Supermicro обвалились более чем на 50% за день.

Предыстория

В 2015 году Amazon начала процесс оценки бизнеса стартапа Elemental Technologies для возможной покупки. Команда Elemental занималась разработкой софта для компрессии видео и его форматировании для работы на различных мобильных устройствах. Amazon нужен был этот продукт для использования в собственных видеостриминговых сервисах.

Помимо прочего, среди заказчиков Elemental Technologies были и государственные органы США, что также укладывалось в стратегию развития Amazon – компания занимается созданием облачной инфраструктуры, например, для ЦРУ.

Одним из элементом предпродажной оценки является аудит информационной безопасности. Для его проведения Amazon наняла внешнюю фирму, специализирующуюся на вопросах киберзащиты. Ее специалисты обнаружили странности в конструкции серверов Elemental Technologies, которые компания закупала у Supermicro.

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

Описание атаки

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

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

От атаки пострадали около 30 американских компаний, включая крупный банк, подрядчиков государственных органов США, а также самую дорогую компанию в мире – Apple. Компания из Купертино была одним из крупнейших заказчиков Supermicro и планировала заказать 30 000 серверов для установки в своих дата-центров в разных регионах мира. Служба безопасности Apple также обнаружила шпионский микрочип в 2015 году, что привело к отказу от контрактов с Supermicro.

Реакция на расследование

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

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

Несмотря на все доказательства, официально Amazon, купившая Elemental Technologies осенью 2015 года, Apple и Supermicro отказались признать факт кибератаки. Несмотря на это акции производителя оборудования в день выхода расследования Bloomberg обвалились более чем на 50%. К концу недели потери были отыграны, однако общее падение стоимости акций оказалось крайне значительным – если 5 октября они торговались по цене $21,4 за акцию, то к пятнице уже на уровне $11,7 за акцию.

Как отмечает CNBC, четверг текущей недели оказался для Supermicro худшим днем на бирже с момента IPO в 2007 году.

Помимо реакции инвесторов стало известно и о дальнейших шагах властей США – включили компьютерное оборудование (в том числе материнские платы) в очередной раунд торговых санкций против Китая. Руководство страны хочет добиться переноса цепочек поставок американских компаний из Китая в другие страны.

Другие материалы по теме финансов и фондового рынка от ITI Capital:

Let's block ads! (Why?)

[Перевод] Полностью автоматические такси от Waymo появятся уже в этом году

Waymo готова запустить такси без водителей с минимальным федеральным надзором

Waymo, проект робомобилей от Google, в следующие три месяца планирует запустить такси без водителя в г. Финикс шт. Аризона. Это будет не пробный проект и не рекламный трюк. Waymo планирует запустить общедоступный коммерческий сервис – без человека за рулём.

И пока что технология от Waymo привлекает удивительно мало внимания со стороны правительственных чиновников, как в городе Финикс, так и в Вашингтоне, О.К.

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

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

«Очень сложная задача»

«Если подумать, что потребуется от правительственной организации для проверки схемы работы робомобиля и принятия решения о его безопасности – становится понятно, что это трудная задача», — сказал Эд Фелтен, специалист по информатике из Принстона, бывший советником по технологиям в Белом доме при Обаме.

Федеральное правительство, и при Обаме, и при Трампе, особенно не заботится регулированием робомобилей. Вместо того, чтобы вводить новые правила для безопасности, говорит Фелтен, чиновники пытались «гарантировать, чтобы правила по безопасности для робомобилей не затруднили их выход на улицы».

Робомобилям необходимо удовлетворить существующим правилам безопасности, «федеральным стандартам безопасности для моторизованных транспортных средств» (FMVSS). Но на практике это не такая уж большая проблема. Waymo планирует преодолеть её, просто используя для своего сервиса фургоны Chrysler Pacifica, которые уже удовлетворяют этим стандартам.

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

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

«Я думаю, это просто невероятно», — говорит Кэти Чейз, глава общества «Сторонников безопасности на шоссе и в автомобилях», комментируя тенденцию к ослаблению регулирования.

Мэри Каммингс по прозвищу «Мисси», профессор инженерного дела в Университете Дюка, соглашается с ней. «Я думаю, совершенно бессовестно не требовать никаких проверок перед тем, как выпускать их на дороги».

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

В плане робомобилей «нет всеобщего согласия по поводу того, что такое безопасность или как её обеспечить», — говорит Брайант Уокер Смит, учёный юрист из Университета Южной Каролины.

В других индустриях правила строже

Производство самолётов очень строго контролируется

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

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

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

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

У Waymo не будет ничего подобного. Компания проводила неформальные обсуждения с чиновниками на федеральном уровне, на уровне штата и на местах. Но никакого формального процесса, который бы требовал от компании отправлять информацию о своей технологии и результатах испытаний регуляторам из Финикса или Вашингтона, не существует. Закон просто не требует от Waymo доказать, что её технология робомобилей безопасна, перед тем, как выпустить машины на дорогу.

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

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

Проблемы с регулированием робомобилей

Автомобиль подрезает робомобиль Waymo на испытательном треке Castle в рамках испытаний технологии.

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

Но Эд Фелтен из Принстона задаётся вопросом, реалистично ли это. Он указывает на то, что в деле испытаний робомобилей существуют уникальные препятствия.

«Количество происшествий или жертв на одну милю, пройденную машиной, должно быть очень, очень маленьким», — говорит он. Водители-люди попадают в происшествие с летальным исходом примерно раз на 100 млн миль. Поэтому, чтобы определить, что безопасность робомобиля не ниже человеческого водителя, необходимо понять, как он обрабатывает редкие ситуации – такие, с которыми водитель-человек столкнётся, возможно, раз в жизни.

«Чтобы понять, что это безопасно, требуется огромное количество симуляций и проверок в контролируемых условиях, — говорит Фелтен. – Сложно представить, как правительство сумеет это сделать».

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

И хотя Каммингс сказала мне по поводу машин от Waymo, что «никаких испытаний в реальном мире не проводилось», это было нечестно по отношению к компании. В прошлом году я ездил на испытательный полигон в Калифорнии, где компания помещает машины в сотни контролируемых сценариев. Я смотрел, как машина Waymo замедляется, когда её подрезает другая, останавливается, когда «грузчики» роняли перед ней кучу коробок, давала проехать машине, съезжающей с парковки у дома.

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

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

Waymo могла бы действовать более открыто

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

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

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

«Нам нужна информация по Waymo», — сказал Генри Джасный, юрист из общества «Сторонников безопасности на шоссе и в автомобилях», вскоре после публикации Waymo отчёта в прошлом году.

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

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

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

Но в этот отчёт не вошла подробная информация, которая позволила бы провести независимый анализ испытательного процесса Waymo. Каковы точные параметры тестов? Сколько раз их прогоняли? Как повёл себя автомобиль? В отчёте этого нет.

То же верно и для испытаний машин на дорогах общего пользования. Waymo прошла девять миллионов миль испытаний на таких дорогах [14 млн км], многие из которых машины проехали с водителем за рулём. Но у общественности очень мало информации по поводу того, как проходили эти испытания. Это особенно верно для Аризоны, в которой (в отличие от соседней Калифорнии) компаниям, разрабатывающим робомобили, не обязательно отправлять регулярные отчёты об испытаниях.

К примеру, в августе ресурс The Information опубликовал статью, где было написано, что некоторые жители Финикса были раздражены необходимостью делить дороги с машинами Waymo, которые часто вели себя неуверенно там, где живой водитель так бы себя не вёл. Житель Маунтин-Вью выложил несколько видеороликов, на которых машины от Waymo замирали в ситуациях, которые не смутили бы водителей-людей.

Означают ли эти сообщения, что у ПО от Waymo есть большие проблемы? Или это несколько слишком сильно раздутых отдельных происшествий? Сложно сказать без подробных данных о том, как ведут себя робомобили в реальном мире. У Waymo такие данные, без сомнения, имеются; она просто не сделала их доступными для всех.

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

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

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

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

По имеющимся правилам, «каждый может вывести робомобиль на дорогу, — говорит Чейз. – Джо Гаражкин может построить такую машину, вывести её на дорогу, а потом она попадёт в ужасную аварию».

Модель надёжной компании

Если формальную проверку в стиле FDA провести не получится, что могут сделать регуляторы вместо этого? Брайант Уокер Смит ратует за то, чтобы использовать для регулирования робомобилей то, что он называет моделью «надёжной компании». Вместо прописывания подробных технических стандартов для робомобилей, говорит он, регуляторы должны сконцентрироваться на одобрении процессов разработки и испытаний робомобилей самих компаний.

Смит хочет, чтобы «правительственные чиновники сказали: заслуживают ли эти компании доверия? Честно ли они передают информацию? Подтверждают ли свои заявления?»

«Регулирование – это не просто правила или одобрения, — отмечает Смит. – Регулирование – это все инструменты, доступные чиновникам: расследования, запросы, отзыв разрешений, наказания за неверное представление информации».

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

Пока что Waymo ничего такого не делает – по крайней мере, публично. С момента запуска компании почти два года назад, она подчёркивала безопасность своей технологии. «Безопасность находится в самом сердце миссии Waymo и всего, что мы делаем», — написала мне представитель компании по почте.

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

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

Let's block ads! (Why?)

Как соединить Java, Js и графы с искусством, или история о том, как создавался интерактивный театр

В этом году в Эстонии проходит целая серия театральных представлений, объединенных в серию «История Столетия». В течение года 22 театра страны представили публике в своих спектаклях столетнюю историю Эстонии. Русскому театру Эстонии в ходе жеребьевки досталась тема будущего Эстонии.

Под катом — о том, как совместить технологию и искусство.
У каждого из нас есть представление о том, каким могло бы быть будущее: чего мы боимся, о чем мы мечтаем, каким оно может оказаться на самом деле. Чтобы не получился спектакль, рассказывающий лишь о том, что думает о будущем узкий круг театральных людей, мы обратились с этим вопросом к тем, кому предстоит жить в будущем — к детям, к молодежи Эстонии в возрасте 3-19 лет. Ответивших были сотни, и мы очень им благодарны.

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

Спектакль переносит нас в 2118 год. Эстония находится под защитным куполом. Мы научились многому, в том числе и продлевать жизнь. Главные герои — пожилая пара Линда и Тимо. Сто лет назад, будучи детьми, они фантазировали о будущем, в котором теперь и живут. Это одни из тех самых детей, благодаря которым и получился этот спектакль. Герои попадают в разные миры, в разные Эстонии. В ходе спектакля именно зрители своим решением влияют на то, каким будет их 2118 год.

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

Артем Гареев (режиссер спектакля) показывает на макете основные идеи

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

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

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

Чтобы стало немного понятней, давайте немного войдем в контекст спектакля

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

Иронии добавляет то, что Елена Соломина — ведущая на национальном телевидении и хорошо знакома многим зрителям.

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

После все отправляются на вечеринку.

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

И если ответ оказывается положительным, то…

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

Какое же техническое решение было нам необходимо?

По сути, это был еще один актер ЕМА (по эст. Мама), искусственный интеллект, который стал реальностью в будущем. ЕМА ведет зрителей по сюжету, проявляет себя в различных вариантах будущего, а также объявляет и запускает голосование, подсчитывает и представляет результаты, переходит по сюжетным веткам. Зал вмещал в себя 600 человек. И каждый зритель должен был иметь возможность проголосовать, а система корректно посчитать его голос.

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

Утопия имеет свойство перетекать в антиутопию, а благими намерениями выложена дорога в ад. Сюжеты связаны между собой логикой драматургии. Учитывая количество вариантов будущего, которые предложили дети, получилось большое количество веток. Важно избегать повторов — то, что было сыграно, не должно быть снова вынесено на голосование как возможный вариант. Например, если после просмотренной Информационно-Технологического утопии зрители подтверждают свой выбор такого будущего, то мы попадаем в технологическую антиутопию. Если же зрители отвергают предложенный вариант, то должны вновь сделать выбор между предлагаемыми вариантами — например, Экологическим и Космическо-Колониальным будущим. Очень часто были ситуации, когда зал боролся, голоса делились практически 50% на 50% и все решала разница в несколько голосов.

Вся эта сложность требовала соответствующей структуры, которой и является Граф.

Какие еще функциональные требования были к техническому решению для спектакля? Нам требовались:

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

Итак у нас есть 600 человек, которые должны проголосовать менее чем за минуту. У людей должна быть возможность отдать голос со своего телефона. Вариант мобильного приложения отпадал сразу, поскольку скачать приложение — это дополнительные усилия. Никто не качает приложения, если вы не Фейсбук или Гугл. Разные модели и типы телефонов требуют различной разработки, что нереально в условиях 1,5 месяцев и одного разработчика. Следовательно, нам требуется Web приложение для мобильного телефона.

Еще одно Web приложение требуется для администрирования системы, запуска, активации состояний и прочих технических моментов.

И наконец, самое главное — это то, как ЕМА должна взаимодействовать с залом.

И тут необходимо ввести концепцию «супера», которая была новой и для меня. Супер — это экран, который опускается и закрывает сцену.

Подъемно-опускной занавес
Также известен как «занавес-гильотина» или «немецкий» занавес. Чаще используется в музыкальных театрах. Занавес представляет собой целое полотно, прямое или плиссированное, закрепленное по верхней кромке к несущей балке. Подъем занавеса происходит одновременно с подъемом несущей балки. Такой занавес требует большой высоты пространства над сценой.
(Википедия)

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

Итак, у нас имеется сложный граф, система голосования и три FrontEnd системы, которые должны взаимодействовать со зрителями и админом (невероятным помощником режиссера Светланой Шушиной).

Решение

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

Однозначным выбором была Neo4j, лидирующая система графовых баз данных в мире. 7 из топ 10 технологических компаний в мире используют её. Это очень зрелая технология. Скорость, удобство и отличное коммьюнити не оставляют другого выбора в подобного рода решениях.
Мы смоделировали сюжет, выстроенный драматургами, в виде графа на Neo4j. И вот кусочек сюжетных перипетий, как он выглядит изнутри Neo4j.

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

В плане серверной части были некоторые сомнения — Python vs Java. Выбор склонился в пользу Java. Причины — скорость, меньший риск что-то сломать при понятных требованиях и прямых руках, и наконец Spring Boot, который из коробки поддерживает Neo4j.

Серверная часть имплементирована на Spring Boot. Фактически сервер собирает голоса, переключается по команде с «супера» в следующие состояния, когда голосование закончено, принимает команды от админа, отдает статистику и прочее прочее. Плюс отдает все варианты FrontEnd-ам, а также регистрирует зрителей.

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

В системе получается два центра управления.

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

«Супер» имплементирован на Vue. Изначально мы хотели вызывать аудио с Google Speech API, но мы не могли гарантировать отсутствие задержек по сети. Поэтому был выбран иной вариант — мы записали ответ Google Speech API по кусочкам.

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

Поначалу мобильный клиент (web page) была написана на Vue, но мы получили частичную несовместимость на некоторых моделях телефонов. Мы пробовали транспилеры babel, но из-за кучи настроек обьем страницы разрастался, и хотя на части телефонов голосование начинало работать, но на других ломалось. В итоге мобильный клиент был переписан на Vanilla JS.

По сути это получилась распределенная система.

Финальный обьем системы (jar file) был 146 мегабайт. Телекоммуникационная компания Telia предоставила нам виртуальный сервер по символической цене 1 евро в месяц, за что ей огромная благодарность.

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

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

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

Спектакль получил огромное количество положительных рецензий в прессе
https://rus.postimees.ee/6141942/budet-ne-budet-net-nichego-opasnee-budushchego
https://rus.postimees.ee/6147704/nashe-zavtra-v-zerkalah-utopii-i-antiutopii

На фестивале Драма в Тарту овации длились почти 5 минут.

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

Режиссер и сценограф – Артём Гареев
Композитор, продюсер проекта– Александр Жеделёв
Визуал – Алена Мовко
Художник по костюмам – Росита Рауд
Художник по свету – Антон Андреюк
Хореограф – Ольга Привис
Драматурги: Карин Ламсон, Мари-Лийз Лилль, Елена Чичерина и Лаура Калле
Видео – Николай Алхазов
Программирование и создание приложения – Александр Тавген, Анна Агафонова
Техническое решение лед посветки – Aleksander Sprohgis
Анимация – Martin Yakush
Музыкальный коллектив – Modulshtein
Мартен Альтров – кларнет, бас кларнет
Алексей Семенихин– работа с семплами, эффекты
Александр Жеделёв – гитара, синтезаторы, ableton
Педагог по вокалу – Анна Дыдына
Помощник режиссёра Светлана Шушина
В спектакле заняты:
Наталья Дымченко, Александр Жиленко, Даниил Зандберг, Дмитрий Кордас, Екатерина Кордас, Александр Кучмезов, Виктор Марвин, Наталья Мурина, Елена Тарасенко, Эдуард Тее
Сергей Фурманюк, Леонид Шевцов, Елена Яковлева
Студия Русского театра: Денис Волков, Полина Гринёва, Нина Загвоздкина, Анастасия Коледа, Наташа Кристенсен, Анастасия Масалова, Сандра Миносян, София Михалёва, Катрин Мяги, Михаил Пащук, Катрин Селюгина, Кристина Сорокина, София Стрёмберг, Илья Сутть.

Let's block ads! (Why?)