Об упрощении выражений со смешанной битовой и целочисленной арифметикой

Выражения со смешанной булевой и целочисленной арифметикой (далее — MBA-выражения, от англ. Mixed Boolean- Arithmetic) от $t$ целочисленных $n$-битных переменных часто находят применение при обфускации (запутывании) программного кода. Запутывание заключается в замене коротких выражений более длинными эквивалентными выражениями, на исследование которых, как представляется, аналитиком может быть затрачено больше времени. В работе показано, что для упрощения линейных MBA-выражений (сокращения количества слагаемых) может быть применена техника, аналогичная технике декодирования линейных кодов по информационным совокупностям. На основе этой техники в работе построены алгоритмы упрощения линейных MBA-выражений: алгоритм нахождения выражения с минимальным числом слагаемых и алгоритм сокращения числа слагаемых. На основе алгоритма сокращения числа слагаемых построен алгоритм, позволяющий оценить стойкость MBA-выражения к упрощению. В работе экспериментально оценена зависимость среднего числа слагаемых в линейном MBA-выражении, возвращаемом алгоритмами упрощения, от разрядности $n$, числа итераций декодирования и мощности набора булевых функций, по которому ищется линейная комбинация с минимальным числом ненулевых коэффициентов. Результаты экспериментов для всех рассмотренных $t$ и $n$ показывают, что если до обфускации линейное MBA-выражение содержало $r=1,2,3$ слагаемых, то разработанные алгоритмы упрощения с вероятностью, близкой к единице, позволяют по обфусцированному варианту этого выражения найти эквивалентное с числом слагаемых не более $r$. В этом заключается главное отличие техники декодирования по информационным совокупностям от известных техник упрощения линейных MBA-выражений, в которых целью является сокращение числа слагаемых до не более чем $2^t$. В работе также установлено, что для случайно сгенерированных линейных MBA-выражений с ростом $n$ среднее число слагаемых в возвращаемом выражении стремится к $2^t$ и не отличается от среднего числа слагаемых в линейном выражении, возвращаемом известными алгоритмами упрощения. Полученные результаты, в частности, позволяют определить $t$ и $n$, для которых количество слагаемых в упрощенном линейном MBA-выражении в среднем будет не менее заданного.