Попытка разоблачения черной магии

[beldmit]

Некоторое время назад vitus_wagner опубликовал пост, описывающий результаты экспертизы некоего прибора для анализа алкоголя в крови (оригинал у Брюса Шнайера). К софту, использованному внутри прибора, предъявлялись следующие претензии (у Витуса они есть по-русски, скопировал от Шнайера):

2. Readings are Not Averaged Correctly: When the software takes a series of readings, it first averages the first two readings. Then, it averages the third reading with the average just computed. Then the fourth reading is averaged with the new average, and so on. There is no comment or note detailing a reason for this calculation, which would cause the first reading to have more weight than successive readings. Nonetheless, the comments say that the values should be averaged, and they are not.

3. Results Limited to Small, Discrete Values: The A/D converters measuring the IR readings and the fuel cell readings can produce values between 0 and 4095. However, the software divides the final average(s) by 256, meaning the final result can only have 16 values to represent the five-volt range (or less), or, represent the range of alcohol readings possible. This is a loss of precision in the data; of a possible twelve bits of information, only four bits are used. Further, because of an attribute in the IR calculations, the result value is further divided in half. This means that only 8 values are possible for the IR detection, and this is compared against the 16 values of the fuel cell.

4. Catastrophic Error Detection Is Disabled: An interrupt that detects that the microprocessor is trying to execute an illegal instruction is disabled, meaning that the Alcotest software could appear to run correctly while executing wild branches or invalid code for a period of time. Other interrupts ignored are the Computer Operating Property (a watchdog timer), and the Software Interrupt.

По 4 пункту ничего сказать не могу. Смотреть надо.
3 пункт сам по себе тоже не особо интересен.

Смотрим на п.2. Что видим? Сразу хочу отметить, что высказанное мной - не плод исключительно моих заключений, а результат обсуждений с друзьями, выпускником ВМК и действующим преподавателем мехмата.

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

Описанный алгоритм куда сложнее среднего арифметического. Но программисты просто так обычно ничего не делают. Посмотрим, что этот алгоритм дает.

Во-первых, дает он экономию одного регистра долговременной памяти.
Во-вторых, там нет деления на произвольное число. Есть только деление пополам. То есть - сдвиг.

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

Прошу этот пост комментировать только с технической точки зрения.

Comments

[yakov-sirotkin.livejournal.com]

А что собственно комментировать? Есть некоторый программно-аппаратный комплекс, уважаемые эксперты обнаружили внутри него код "обычного" качества. Есть ли несоответствие между обещаниями производителя и реальностью - не понятно. Насколько качественно производитель сделал QA - не понятно. Если бы код был написан более понятно, то у нас было бы больше Assurance в Quality, но, возможно, производитель просто не смог или пожадничал делать повторный QA, а новый софт у него лежит на полке.

[p_govorun.livejournal.com]

Там, кажется, 32 измерения. Из них последнее идёт с весом 1/2, а первое -- с весом 1/8192. Это бред, и нет смысла искать в нём смысл.

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

[beldmit.livejournal.com]

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

Для 32 измерений - бред, не вопрос, учитывая 12-битность датчика...

[p_govorun.livejournal.com]

А как можно не считать измерения? Надо же знать, сколько раз мерить.

[beldmit.livejournal.com]

Начал мерить. Кончил мерить. Авторский алгоритм позволяет не считать и в любой момент остановиться.

[p_govorun.livejournal.com]

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

[beldmit.livejournal.com]

Все-таки не по таймеру, а не зашивая в код число попыток.

[p_govorun.livejournal.com]

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

Я именно об этом. Если мы как-то считаем измерения, то без регистра счётчика не обойдёмся.

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

[yurikhan]

При достаточной памяти измерения можно считать счётчиком команд.

[p_govorun.livejournal.com]

Похоже, начинается Obfuscated C Contest: запрограммировать алкотестер наиболее хитроумным образом. :-) Но тут главное условие -- чтобы он при этом ещё и работал правильно.

[yurikhan]

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

measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();
measure(); measure(); measure(); measure();

[p_govorun.livejournal.com]

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

Теоретиков надо душить

[vitus_wagner]

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

Re: Теоретиков надо душить

[beldmit.livejournal.com]

Какое это отношение имеет к шнайеровским претензиям к коду?

Изучал я кинетику в аспирантуре. Так или иначе, авторский алгоритм дает этому самому периоду установления меньшие веса. Что не так?

[shigin.livejournal.com]

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

По пункту 2 "я ваших академиев не кончал", но вообще доверять последним измерениям больше, чем первым выглядит очень странно. Предположим последнее измерение у нас плохое "вверх". Согласно пункту 8, это измерение не будет отброшено, а будет преобразовано к максимальному возможному значению. То есть у нас есть значение 12 и результаты [9, 13, 12, 14, 12, 18, 14, 10, 14, 12, 13, 14, 10, 12, 13, 255]. 27 против 133. Хорошее округление.

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

Но пункт 8, конечно, заруливает всё остальное.

[yurikhan]

Если у нас такое железо, что возможны результаты [9, 13, 12, 14, 12, 18, 14, 10, 14, 12, 13, 14, 10, 12, 13, 255], то софт должен, кроме всего прочего, считать среднее (m = 27.8) и дисперсию (σ = 60.6) и отбрасывать результаты, отстоящие от среднего больше чем на три сигмы (> 209.67), давая более правдоподобное m′ = 12.67, σ′ = 2.16, m′ ± 3σ′ = [6.19, 19.15].

[shigin.livejournal.com]

Между тем пункт 8 говорит: 8. Range Limits Are Substituted for Incorrect Average Measurements: In a manner similar to the diagnostics, voltage values are read and averaged into a value. If the resulting average is a value out of range, the averaged value is changed to the low or high limit value. If the value is out of range after averaging, this should indicate a serious problem, such as a failed A/D converter.

Я из этого абзаца вывожу, что битые данные у них бывают не так уж редко. Да и вообще я не верю в железо без глюков.

[gegmopo4.livejournal.com]

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