«Керосинка» против «Патриотов»: как американские военные программисты научились правильно округлять

    11 февраля 1991 года Patriot Project Office получил израильские данные о дефекте в ракетной системе Patriot. Они нашли, что если система работает 8 часов, она начинает мазать на 20%. Они прикинули, что после 20 часов работы система начинает промахиваться настолько, что перестанет быть способной захватывать, отслеживать и поражать баллистические ракеты. Американские военные не приняли во внимание всю важность открытия, заявив, что система предназначена для портативных и краткосрочных защитных операций и что никто никогда не будет использовать систему больше 8 часов.

    16 февраля был выпущен Bug Fix, но чтобы его внедрить во все единицы боевой техники, требовалось время, ибо война.

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

    25 февраля в Дахране (Саудовская Аравия) в казарму в гости к американцам прилетела баллистичекая ракета "керосинка" (она же Р-17, она же Scud). 28 убито 96 ранено, потому что ЗРК «Патриот» промахнулся из-за программной ошибки.

    26 февраля Bug Fix был доставлен в Дахран.






    Р-17 (по классификации МО США и НАТО — SS-1c Scud B, экспортное обозначение R-300, неофициально — «керосинка») — советская жидкостная одноступенчатая баллистическая ракета на долгохранимых компонентах топлива.

    фотки Р-17



    Военные осматривают ракету типа Р-17 сбитую в пустыне ЗРК MIM-104 «Патриот» во время операции Desert Storm


    MIM-104 «Патриот» (англ. MIM-104 Patriot, перевод с английского — Патриот) — американский зенитный ракетный комплекс (ЗРК), используемый армией США и их союзниками.

    фотки Patriot





    A detailed view of an AN/MPQ-53 radar set. The circular pattern on the front of the vertical component is the system's main phased array, consisting of over 5,000 individual elements, each about 39 millimeters (1.535 in) diameter.


    PAC-3 missile launcher, note four missiles in each canister


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

    Системное время хранилось как integer в 24-битном регистре с точностью до одной десятой секунды. Поэтому на каждом такте по 0.1 сек «терялась» часть времени. При рассчете данные переводились в real numbers.
    [источник]

    Число 1/10 равно 1/24+1/25+1/28+1/29+1/212+1/213+… Другими словами, бинарное разложение 1/10 = 0.0001100110011001100110011001100… Поэтому 24 bit регистр в системе Patriot хранил вместо этого 0.00011001100110011001100 внося ошибку равную 0.0000000000000000000000011001100… в двоичном исчислении, или примерно 0.000000095 в десятичном. За сто часов работы набегает 0.000000095×100×60×60×10=0.34 секунды

    «Керосинка» летит со скоростью 1676 метров в секунду, и проходит за 0.34 секунды больше полукилометра. Этого больше чем достаточно, чтоб прошмыгнуть радиус поражения Патриотов. Забавно, что кривое вычисление времени пофиксили в некоторых частях программы, но не во всех.

    Софт был написан на ассемблере 15-20 лет назад и с тех пор несколько раз модифицировался различными командами программистов.

    Несколько слайдов из отчета, где выявляется проблемы с системой Patriot:







    Золотые правила


    • Правильно подбирайте размер. Всегда тщательно перепроверяйте, сколько бит вам требуется для хранения каждой переменной выбрать (long, int, double, float, и пр) в конкретном языке и конкретной операционной системе.
    • Используйте целые числа вместо float где только возможно. Храните деньги в центах, а не долларах (а лучше в сатоси). Если все же необходимо использовать float, используйте двойную точность.
    • Никогда не используйте float в качестве счетчика цикла.
    • Избегайте смешанных типов (signed, unsigned; integer, floating point; single precision, double precision). Тщательно производите конвертацию.
    • Проверяйте возможные ситуации переполнения. Проверяйте деление на ноль.

    Статья от PVS: Почему все-таки мы получаем разный результат в 32-битном и 64-битном коде?
    Статья от хабраавтора (229 комментов): Фатальные ошибки двоичной арифметики при работе с числами с плавающей точкой.

    Читать еще про Patriot



    Заключение


    Мы хотим привлечь внимание людей к проблемам надежности программного обеспечения. Программы — это давно не только странные непонятные расчёты ученых на Fortran или компьютерные игры. Это то, что давно и повсеместно нас окружает.

    Раньше серьезные баги наносили вред в узких специфичных областях — ракетостроение мирное (Ariane 5) и военное (Patriot). Сейчас же с ошибкой в программе вы можете столкнуться не только сидя за компьютером, но и сидя в автомобиле (Toyota) или посещая больницу (Therac-25). Мы одни из тех, кто сражается на стороне программистов против багов. Нами разработан статический анализатор кода PVS-Studio, позволяющий выявлять ещё на этапе кодирования многие ошибки в программах на языке С, С++ и С#. И пользуясь случаем, хочу напомнить, что с 25 октября 2016 года будет доступна не только Windows, но и Linux версия этого анализатора.

    PVS-Studio

    447,00

    Ищем ошибки в C, C++ и C# на Windows, Linux, macOS

    Поделиться публикацией
    Комментарии 28
      +5
      Да-да… я же говорил, что программисты погубят мир: https://habrahabr.ru/post/310026/
        –5
        :)
        +8
        > позволяющий выявлять ещё на этапе кодирования многие ошибки в программах на языке С, С++ и С#

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

            Но у вас здесь получилось как в анекдоте «у рыбы нет шерсти, поэтому нет блох, а вот кстати о блохах».
              0
              Почитал вашу статью про разный результат в 32битном и 64битном коде. Есть ещё одно объяснение. Не знаю, что там конкретно в MSVC, но общая ситуация выглядит так:
              1) Регистры плавающей арифметики на IBM PC — 80 бит (long double)
              2) При вычислении общих подвыражений используется long double
              3) Таким образом, результат зависит от оптимизации. Если делать строго по коду — значение одно. А если оптимизировать — то все считается в 80 битах и лишь потом превращается в 32 бита float.

              Можете проверить на MSVC, принудительно отключив все оптимизации. Скорее всего, дефолтный набор оптимизаций просто разный.
            +1
            Не так давно было обсуждение, человек тоже долго возмущался, что точные десятичные дроби в двоичном виде бесконечны и поэтому всегда записываются с погрешностью.
            https://habrahabr.ru/post/309812
              +2
              точные десятичные дроби в двоичном виде бесконечны и поэтому всегда записываются с погрешностью.

              Не все, а только непредставимые.
              А теперь по теме.В статье говорится:
              За сто часов работы набегает 0.000000095×100×60×60×10=0.34 секунды

              Однако, причина сбоя в комплексе Patriot связана не столько с накоплением с течением времени ошибок при работе с числами с плавающей точкой, сколько с природой самих real numbers. Если исходить из тех условий работы программы, которые представлены в отчете, то можно увидеть, что при достижении таймером числа 1048576, которое в 24-разрядном двоичном слове записывается как 000 100 000 000 000 000 000 000, следующая добавка в 0.1≈0.000 110 011 001 100 110 011 001 101 дает число, равное 100 000 000 000 000 000 000.000 1100110≈100 000 000 000 000 000 000.000=1048576. Т.е. дальнейшего накопления в счетчике не происходит. И достигается это значение за 1048576*0.1/60/60=29,127 часа работы комплекса.
              Полученный эффект, как мы видим, не связан с переполнением таймера в классическом понимании.
              0
              (del)
                +6

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


                Если ошибка накапливалась с момента включения — значит, в системе было два независимых таймера, один из которых был точный, а второй — "приближенный".

                  +2
                  (а лучше в сатоси)
                  можно подробней что это?
                    +6
                    satoshi = 10−8 Bitcoin
                      –8
                      я так понимаю речь о битках, по имени их мифического разраба — Сатоши Накамото. Возможно новая крипто-валюта.
                        +1
                        В системе Биткоина это минимальная возможная сумма, этакий квант валюты. Тут имеется ввиду, что нужно желательно измерять все валюты в аналогах таких квантов.
                        0
                        Всё-таки конкретно с теми «скад-ами» — вопрос нужно ли было их вообще сбивать — до сих пор дискуссионный. Т.е. если бы они несли ОМП (хим или атомное) — это одно дело, а так — точность его на его дальности совершенно никакая, а «сбитый» он наносил ущерб сопоставимый с «несбитым» — как по силе взрыва так и по месту попадания…
                          0
                          >«Керосинка» летит со скоростью 1676 метров в секунду
                          Да ну, 5 махов? Когда SR-71 может максимум 3.2М, раскаляясь при этом до свечения.
                            +1
                            Все так, вот только SR-71 летает в более плотной атмосфере. Верхняя точка траектории Р-17 — около 86 км, у Blackbird потолок всего 25 км.
                              0
                              Скорость звука не константа, она зависит от температуры и, следовательно, высоты (http://tehtab.ru/Guide/GuidePhysics/Sound/SoundSpeedAirHeight/). Поэтому реальный Мах еще выше 5. Кстати число Маха больше 10 на некоторых участках траекторий современных ракет совсем не редкость.
                              И кстати Мах — удобная единица для аэродинамических расчетов(подобие течения для одинаковых числел Маха), но о нагреве она напрямую судить не позволяет.
                                0
                                Это баллистическая ракета — она проникает в атмосферу сверху и проводит в ней достаточно немного времени.
                                  0
                                  Баллистическая ракета же! Она необитаема и спроектирована для одного полета. Можно испарить часть обшивки боеголовки в процессе полета, если начинка долетит.
                                  0
                                  Интересно, а можно совместить статический анализатор кода с git? чтобы ошибки и подозрительные места вылавливались и подсвечивались при помещении кода в репозиторий? можно ли обучить нейронную сеть на выявление наиболее частых ошибок например в Си коде? им ведь всё равно что распознавать? статистика у Вас большая
                                    +3
                                    А что мешает взять статический анализатор и прикрутить к post/pre хукам репозитория? Ничего! Как и прикрутить к этому добру проверку тестов (что уже делает много продуктов).
                                      0
                                      Одно время был озадачен подобной проблемой. Как раз пытался прикрутить PVS-studio для этой цели. Но возникла одна сложность — у PVS-studio нет возможности проанализировать отдельный файл (а хотелось анализировать именно те файлы, которые в данный момент пушатся в репозиторий).

                                      Будь добр анализировать либо весь проект, либо на худой конец весь solution.
                                      0

                                      Coverity Scan предлагает всем желающим бесплатно сканировать их open-source репозитории на github.

                                    –1
                                    Когда будет анализатор для PHP?
                                      –1
                                      Нет, ну серьезно! Как бы глупо это не звучало — хотелось бы услышать мнение специалиста по поводу статического анализа динамически типизированных языков. Не хотите обсуждать PHP — давайте обсудим хотя бы Python.
                                        –1
                                        Странный какой-то способ отвечать минусами. Все ясно и понятно сразу, да. Спасибо :)

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

                                    Самое читаемое